An on-line and deadlock-free path-planning algorithm based on world topology

Proposes a new sensor-based path-planning algorithm running in an uncertain 2D world. In the algorithm, the automaton basically goes straight to the goal, and if it touches some uncertain obstacles, it traces the obstacle boundary until it can go straight to the goal again. Moreover if the automaton finds some loop in the world, it enters into the goal area. As a result, several loops encountered by the automaton become smaller monotonously in the world, and then the automaton arrives at the goal after it has escaped from the minimum loop. This result is ensured in an online manner. The algorithm has several good characteristics: (1) it omits some calculations of the distance from the present point, and therefore it is faster than all previous sensor-based algorithms; (2) it is more robust than the previous sensor-based algorithms for some self-dead-reckoning error; (3) it can generate shorter deadlock-free paths in almost all 2D worlds than the previous sensor-based algorithms