An efficient and simple motion planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers (extended abstract)

Abstract

We present a relatively simple algorithm which runs in time Ο(n2log n) for the above mentioned problem. The algorithm is an optimized variant of the decomposition technique of the configuration space of the ladder, due to Schwartz and Sharir. The algorithm is based on some ideas which may be exploited to improve the efficiency of existing motion-planning algorithms for other more complex robot systems.