On the connection between maze-searching and robot motion planning algorithms

Abstract

It is shown that the path-planning problem for a point automaton operating in a finite or infinite environment filled with unknown obstacles of arbitrary shapes can be reduced to that of searching a finite graph of a special structure. Then, any maze-searching algorithm described in graph theory, and any path planning algorithm developed in robotics, can be used to direct the automaton's motion. A performance criterion is introduced and used to assess and compare the performance of different algorithms, both among themselves and with the best theoretically possible algorithm, as indicated by the universal lower bound.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>