Algorithmic and complexity issues of robot motion in an uncertain environment

This paper presents a survey of one approach to planning collision-free paths for an automaton operating in an environment with obstacles. Path planning is one of the central problems in robotics. Typically, the task is presented in the two- or three-dimensional space, with the automaton being either an autonomous vehicle or an arm manipulator with a fixed base. 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, an element of uncertainty about the environment is present. The approach surveyed here, called dynamic path planning, has been developed in the last few years; it is based on the latter model and gives rise to algorithmic and computational issues very different from those in the former model. The approach produces provable (nonheuristic) path planning algorithms for an automaton operating in a highly unstructured environment where no knowledge about the obstacles is available beforehand and no constraints on the geometry of the obstacles are imposed.