We introduce a hierarchical variant of the probabilistic roadmap method for motion planning. By recursively refining an initially sparse sampling in neighborhoods of the obstacle boundary, our algorithm generates a smaller roadmap that is more likely to find narrow passages than uniform sampling. We analyze the failure probability and computation time, relating them to path length, path clearance, roadmap size, recursion depth, and a local property of the free space. The approach is general, and can be tailored to any variety of robots. In particular, we describe algorithmic details for a planar articulated arm.

This paper addresses the issue of trap design for sensorless automated assembly. First, we present a simple algorithm that determines in O(nm /spl alpha/(nm) log(nm)) time whether an n-sided polygonal part will fall through an m-sided polygonal trap. We then introduce the notion of a minimal trap for a polygonal part, and develop an algorithm to design a family of minimal feeders built from these traps. The algorithm runs in O(kn/sup 3+/spl epsiv//) time, where k is the number of stable orientations of P. Moreover, it is complete in the sense that we can always find a feeder, provided that one exists that rejects and supports the appropriate poses of the part.