Since the running time of all exact motion-planning algorithms is exponential in the number of degrees of freedom, probabilistic roadmaps are an effective tool to compute the connectivity of the collision-free subset of high-dimensional robot configuration spaces. Although numerous heuristics have been proposed to expedite the basic probabilistic roadmaps, little work has been done on analyzing their performance. We have developed a hierarchical sampling algorithm and analyzed the number of samples needed to find a path under certain assumptions on the underlying configuration space. The algorithm works in several phases. In every phase it examines each sample that was placed in the previous phase and determines whether more samples should be placed in its neighborhood. The algorithm assumes the existence of an oracle that estimates the distance of a point in the free (configuration) space from the boundary of the free space. We describe how this oracle can be implemented efficiently for the case in which the robot consists of a set of links (e.g., the backbone of a protein).