Algorithmic issues of sensor-based robot motion planning

This paper presents a brief survey of one approach to planning collision-free paths for a robot - an autonomous vehicle or an arm manipulator - operating in an environment with unknown obstacles. The multiplicity of approaches one finds in this area revolves around two basic models: in one, called path planning with complete information, perfect information about the geometry and positions of the robot and the obstacles is assumed, whereas in the other, called path planning with incomplete information, there is an element of uncertainty compensated by some source of on-line information, such as robot sensors. The approach surveyed here, called dynamic path planning, is based on the latter model and gives rise to algorithmic and computational issues very different from those in the former model. The approach uses topological characteristics of the environment and imposes no constraints on the geometry of the robot or the obstacles. The resulting provable (nonheuristic) path planning algorithms can be used in a highly unstructured environment where no knowledge about the obstacles is available beforehand.