ABSTRACT
The current algorithmic interest in motion planning is usually traced to the previously noted work of T. Lozano-Perez and M. Wesley. Motion planning, i.e., the problem of computing a path for a robot, is widely recognized as a fundamental problem in robotics. There are two archetypes of a robot in practice: one is a multijointed robot arm fixed to some base, and the other is an autonomous mobile automaton. The idea of growing obstacles is usually attributed to Udupa: Intuitively, path planning for a robot amidst obstacles can be reduced to moving the robot, shrunken by some amount, amidst the obstacles grown by some corresponding amount. Despite the attraction of this analogy, the concept of "grown obstacles" is essentially limited to the simplest cases of circular or spherical robot bodies. An even more general view is to allow the environment and robot to undergo continuous deformations.
