Efficient Motion Planning for an <i>L</i>-Shaped Object

Abstract

An algorithm that solves the following motion-planning problem is presented. Given an L-shaped body L and a two-dimensional region with n point obstacles, decide whether there is a continuous motion connecting two given positions and orientations of L during which L avoids collision with the obstacles. The algorithm requires $O(n^2 \log ^2 n)$ time and $O(n^2 )$ storage. The algorithm is a variant of the cell-decomposition technique of the configuration space [D. Leven and M. Sharir, J. Algorithms, 8 (1987), pp. 192–215], [J. T. Schwartz and M. Sharir, Comm. Pure Appl. Math., 36 (1983), pp. 345–398], but it employs a new and efficient technique for obtaining a compact representation of the free space, which results in a saving of nearly an order of magnitude. The approach used in our algorithm is also applicable to motion planning of certain robotic arms whose spaces of free placements have a structure similar to that of the L-shaped body.