Path planning for moving a point object amidst unknown obstacles in a plane: the universal lower bound on the worst path lengths and a classification of algorithms
Aswin C. Sankaranarayanan, M. Vidyasagar · 2002
The problem of generating a path between any two points for a point object in a 2D plane filled with unknown obstacles of arbitrary shapes is discussed. This problem is termed P1. The issue of worst-case path lengths is analysed in a general setting, independent of any particular algorithm. It is shown that there are two distinct approaches available to solve P1, dividing the set of all possible algorithms that solve P1 into two disjoint classes. The minimum worst-case path length possible in each class is determined and the universal lower bound on the worst case path length of any algorithm is found. The results are shown to be useful in developing algorithms and more general problem models.>