The geometrical representation of path planning problems

Leo Dorst, Indur Mandhyan, Karen I. Trovato
invited paper in: Robotics and Autonomous Systems, Elsevier, vol.7, 1991 , pp.181-195.

The path planning problem for arbitrary devices is first and foremost a geometrical problem. For the field of control theory, advanced mathematical techniques have been developed to describe and use geometry. In this paper, we use the notions of the flow of vector fields and geodesics in metric spaces to formalize and unify path planning problems. A path planning algorithm based on flow propagation is briefly discussed. Applications of the theory to motion planning for a robot arm, a maneuvering car, and Rubik's Cube are given. These very different problems (holonomic, non-holonomic and discrete, respectively) are all solved by the same unified procedure.

Click here for a postscript version of the entire paper (239k).

home ------