| dc.description.abstract | Sampling-based motion planning aims to find a valid path from a start to a goal by sampling in the planning space. Planning on surfaces is an important problem in many research problems, including traditional robotics and computational biology. It is also a difficult research question to plan on surfaces as the surface is only a small subspace of the entire planning space. For example, robots are currently widely used for product assembly. Contact between the robot manipulator and the product are required to assemble each piece precisely. The configurations in which the robot fingers are in contact with the object form a surface in the planning space. However, these configurations are only a small proportion of all possible robot configurations. Several sampling-based motion planners aim to bias sampling to specific surfaces, such as Cobst surfaces, as needed for tasks requiring contact, or along the medial axis, which maximizes clearance. While some of these methods work well in practice, none of them are able to provide any information regarding the distribution of the samples they generate. It would be interesting and useful to know, for example, that a particular surface has been sampled uniformly so that one could argue regarding the probability of finding a path on that surface. Unfortunately, despite great interest for nearly two decades, it has remained an open problem to develop a method for sampling on such surfaces that can provide any information regarding the distribution of the resulting samples.
Our research focuses on solving this open problem and introduces a framework that is guaranteed to uniformly sample any surface in Cspace. Instead of explicitly constructing the target surfaces, which is generally intractable, our uniform sampling framework only requires detecting intersections between a line segment and the target surface, which can often be done efficiently. Intuitively, since we uniformly distribute the line segments, the intersections between the segments and the surfaces will also be uniformly distributed. We present two particular instances of the framework: Uniform Obstacle-based PRM (UOBPRM) that uniformly samples Cobst surfaces, and Uniform Medial-Axis PRM (UMAPRM) that uniformly samples the Cspace medial axis. We provide a theoretical analysis for this framework that establishes uniformity and probabilistic completeness and also the probability of sampling in narrow passages. We show applications of this uniform sampling framework in robotics (both UOBPRM and UMAPRM) and in biology (UOBPRM). We are able to solve some difficult motion planning problems more efficiently than other sampling methods, including PRM, OBPRM, Gaussian PRM, Bridge Test PRM, and MAPRM. Moreover, we show that UOBPRM and UMAPRM have similar computational overhead as other approaches. UOBPRM is used to study the ligand binding affinity ranking problem in computational biology. Our experimental results show that UOBPRM is a potential technique to rank ligand binding affinity which can be further applied as a cost-saving tool for pharmaceutical companies to narrow the search for drug candidates. | en |
