A new algorithm for robot curve-following amidst unknown obstacles, and a generalization of maze-searching

A non-metric path planning algorithm, Curv1, is developed for moving a point automaton between two given points along a guide-track, amidst unknown obstacles. No physical mark is made on the guide-track and no position on distance information is used. The nonheuristic algorithm is shown to converge and an upper bound on the path length is derived. This nonmetric formulation is shown to be related to, and in some sense, a generalization of the maze-searching problem. For the curve-following task, the Curv1 algorithm is shown to be a generalization of the maze-searching Pledge algorithm (H. Abelson and E. DiSessa, 1980). The robustness of the algorithm makes it suitable for an industrial application of autonomous robot guide-track following