A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space (Q1102109)

We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a ``ladder'') in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in time O(K log n)\(=O(n^ 2 \log n)\) where n is the number of obstacle corners and where K is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of \textit{D. Leven} and the second author [J. Algorithms 8, 192-215 (1987; see the following review)], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion- planning algorithms for other more complex robot systems.