Algorithmic and complexity issues of robot motion in an uncertain environment (Q1109740)

Without doubt the path planning for autonomous vehicles or arm manipulators is one of the main problems in robotics. Usually two basic approaches are considered: path planning with complete information, in which full information is given on the geometry and positions of the robot and the obstacle and the other approach, called path planning with incomplete information, in which an element of uncertainty about the environment is contained. In the reviewed paper a new approach is presented, called dynamic path planning; it is based on the latter model and gives rise to algorithmic and computational issues very different from those by the former approach. This new approach provides provable (nonheuristic) path planning algorithms for a robot 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. The paper consists of an introduction and four main parts. The introduction contains basic models of the path planning problem and discusses previous work in this domain. In the first part the problem of moving a point automaton in the plane is presented and, in the second part, the problem of moving a planar arm manipulator. In the third part, the problem for three-dimensional arm manipulators is sketched. The fourth part includes an experimental validation of the algorithms of dynamic path planning. An application of sensor devices for robot arms is also mentioned. Finally, the autor concludes that although the models are incompatible much would be gained if they could be combined.