Planning, Geometry, and Complexity of Robot Motion

Robotics has come to attract the attention of mathematicians and
theoretical computer scientists to a rapidly increasing degree.
Initial investigations have shown that robotics is a rich source of
deep theoretical problems, which range over computational geometry,
control theory, and many aspects of physics, and whose solutions draw
upon methods developed in subjects as diverse as automata theory,
algebraic topology, and Fourier analysis. This volume presents some
of this new theoretical robotics research, emphasizing work relating
to the geometric aspects of robot motion planning.

Contents:

• On the piano mover's problem: I. The case of a two-dimensional
  rigid polygonal body moving amidst polygonal barriers.
• On the piano mover's problem: II. General techniques for
  computing topological properties of real algebraic manifolds.
• On the piano mover's problem: III Coordinating the motion of
  several independent bodies: The special case of circular bodies
  moving amidst polygonal barriers.
• On the piano mover's problem: IV. Various decomposable
  two-dimensional motion planning problems.
• On the piano mover's problem: V. The case of a rod moving in
  three-dimensional space amidst polyhedral obstacles.
• A retraction method for planning the motion of a disc.
• Retraction: a new approach to motion-planning
• Intersection and closet-pair problems for a set of planer
  discs.
• Efficient detection of intersections among spheres.
• Precise implementation of CAD primitives using rational
  paramatizations of standard surfaces.
• Complexity of the generalized mover's problem.
• Movement problems for 2-dimensional linkages
• On the movement of robot arms in 2-dimensional bounded
  regions.