Implementation and extension of the ladder algorithm

The problem of the implementation of exact path-planning algorithms is addressed. The focus is on the implementation of and experimentation with the ladder algorithm of J.T. Schwartz and M. Sharir (1983). The problem is to find a continuous motion for a line segment which is constrained to move in a 2D Euclidean space amid polygonal obstacles. One of the main results is that this algorithm, in spite of its complex structure, provides surprisingly fast running times. The problems involved in the implementation of each step of the algorithm are discussed. The techniques employed to solve them are described with special emphasis on their limitations. It is shown that the original sketch of the algorithm is not guaranteed to find a path. The appropriate modifications to make the algorithm complete are briefly discussed