A practical motion planning strategy based on a plane-sweep approach

We discuss a practical motion planning strategy based on a two-step approach. First, an approximation of the C-space is built by a plane-sweep algorithm. Then, the search for a solution path drives the necessary refinement steps. Our claim is that an approach based on the incremental characterization of the C-space can be competitive with the best proposed motion planning techniques. We substantiate this claim in the simple case of planning translations of a convex body in the plane. Since the shape of the free space is incrementally recognized by probing the space via collision detection, every item of geometric information is obtained from the analysis of contact configurations involving convex bodies. At any stage the probes provide a partial characterization, represented by a simple cell subdivision and a suitable set of chains approximating the boundaries of the grown obstacles. The cells and their adjacencies do not change during the refinement step, so that the search strategy is straightforward. Although the performances are not optimal in theory, the planning algorithm shows a good behaviour, as demonstrated by a few experiments where it is compared with a quadtree-based strategy