ABSTRACT
Motion planning, i.e., the problem of computing a path for a robot, is widely recognized as a fundamental problem in robotics. A typical formulation of this problem is as follows: given a robot and a description of its environment, to plan a path of the robot between two specified positions, which avoids collision with obstacles in the environment. This is a "global" planning problem; to use its results, one would also have to solve low level control theory problems or kinematic and dynamics equations. These latter issues are not considered here: We refer to (Brady et a!., 1983) for a discussion of these matters.
