Path planning for moving a point object amidst unknown obstacles in a plane: a new algorithm and a general theory for algorithm development

A new algorithm Alg2 is developed to solve the problem of nonheuristically moving a point object (MA) between two given points, amidst unknown obstacles in a plane. The existing algorithms to solve this are Bug1 and Bug2 (J. Lumelsky and A.A. Stepanov, 1987) and Alg1 (A. Sankaranarayanan and M. Vidyasagar, 1990). The existing algorithms make MA follow mostly the contours of the obstacle boundaries. Under Alg2, MA follows the obstacles boundaries less and travels more along straight line segments towards the target point. The worst case path length, convergence, local cycle creation, etc. of Alg2 are presented along the examples of its operation. Alg2 is developed step by step, by adding new procedures to a certain primitive algorithm. This algorithm development brings out the basic requirements of a nonheuristic path planning algorithm, and this knowledge leads to a general algorithm Gen of which the algorithms Bug2, Alg1, and Alg2 are particular cases. This generalization helps understand the basic operating principles of a nonheuristic path planning algorithm