Sampling near obstacles is important since it improves the configuration coverage in difficult areas of C-space (such as narrow passages). There are several PRM variants proposed to increase sampling in important regions of C-space, particularly near C-obstacle boundaries. None of them could gaurantee the node distribution and those methods are not very efficient. We propose a new obstacle-based sampler, Uniform OBPRM (UOBPRM) which guarantees a uniform distribution near the C-obstacle surfaces. UOBPRM basically generates a set of uniformly distributed segments of fixed length and then finds all the intersections between the segments and the obstacles by checking the validity changes along the segment. The valid configurations adjacent to the invalid configurations are retained as roadmap nodes.
For UOBPRM, if the bounding box is too close to a C-obstacle boundary, then segments that would yield points on C-obstacle surface may be disqualified. Therefore, we temporarily expand the bounding box for node generation which provides enough space to generate line segments around obstacles. Although the bounding box is adjusted, we do not generate nodes outside the original bounding box, because we only retain samples contained in the original bounding box as roadmap nodes.
In order to show how UOBPRM work comparing to other obstacle-based samplers, we study the distribution of configurations and the cost of generating samples .
Related Publications
UOBPRM: A uniformly distributed obstacle-based PRM, Hsin-Yi Yeh, Shawna Thomas, David Eppstein, Nancy M. Amato, IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2655-2662, Oct 2012. DOI: 10.1109/IROS.2012.6385875 @INPROCEEDINGS{6385875, This paper presents a new sampling method for motion planning that can generate configurations more uniformly distributed on C-obstacle surfaces than prior approaches. Here, roadmap nodes are generated from the intersections between C-obstacles and a set of uniformly distributed fixed-length segments in C-space. The results show that this new sampling method yields samples that are more uniformly distributed than previous obstacle-based methods such as OBPRM, Gaussian sampling, and Bridge test sampling. UOBPRM is shown to have nodes more uniformly distributed near C-obstacle surfaces and also requires the fewest nodes and edges to solve challenging motion planning problems with varying narrow passages.
Keywords: obstacle-based, Sampling-Based Motion Planning
Links : [Published] BibTex
author={Yeh, Hsin-Yi and Thomas, Shawna and Eppstein, David and Amato, Nancy M.},
booktitle={2012 IEEE/RSJ International Conference on Intelligent Robots and Systems},
title={UOBPRM: A uniformly distributed obstacle-based PRM},
year={2012},
volume={},
number={},
pages={2655-2662},
doi={10.1109/IROS.2012.6385875}}Abstract
An Obstacle-Based Rapidly-Exploring Random Tree, Samuel Rodriguez, Xinyu Tang, Jyh-Ming Lien, Nancy M. Amato, In Proc. IEEE International Conference on Robotics and Automation (ICRA), Orlando, Florida, USA, May 2006. DOI: 10.1109/ROBOT.2006.1641823 @INPROCEEDINGS{1641823, author={ {Rodriguez} and {Xinyu Tang} and {Jyh-Ming Lien} and N. M. {Amato}}, booktitle={Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006.}, title={An obstacle-based rapidly-exploring random tree}, year={2006}, volume={}, number={}, pages={895-900}, doi={10.1109/ROBOT.2006.1641823}} Tree-based path planners have been shown to be well suited to solve various high dimensional motion planning problems. Here we present a variant of the Rapidly-Exploring Random Tree (RRT) path planning algorithm that is able to explore narrow passages or difficult areas more effectively. We show that both workspace obstacle information and C-space information can be used when deciding which direction to grow. The method includes many ways to grow the tree, some taking into account the obstacles in the environment. This planner works best in difficult areas when planning for free flying rigid or articulated robots. Indeed, whereas the standard RRT can face difficulties planning in a narrow passage, the tree based planner presented here works best in these areas
Keywords: obstacle-based, Rapidly-exploring Random Tree (RRT), Sampling-Based Motion Planning
Links : [Published] BibTex
Abstract
Ligand Binding with OBPRM and Haptic User Input: Enhancing Automatic Motion Planning with Virtual Touch, O. Burchan Bayazit , Guang Song , Nancy M. Amato , ACM Digital Library, College Station, Texas, USA, Oct 2000. @MISC{Bayazit00ligandbinding, In this paper, we present a framework for studying ligand binding which is based on techniques recently developed in the robotics motion planning community. We are especially interested in locating binding sites on the protein for a ligand molecule. Our work investigates the performance of a fully automated motion planner, as well improvements obtained when supplementary user input is collected using a haptic device. Our results applying an obstacle-based probabilistic roadmap motion planning algorithm (obprm) to some known protein-ligand pairs are very encouraging. In particular, we were able to automatically generate congurations close to, and correctly identify, the true binding site in the three protein-ligand complexes we tested. We nd that user input helps the planner, and a haptic device helps the user to understand the protein structure by enabling them to feel the forces which are hard to visualize.
Keywords: Ligand Binding, Sampling-Based Motion Planning
Links : [Published] BibTex
author = {O. Burchan Bayazit and Guang Song and Nancy M. Amato},
title = {Ligand Binding with OBPRM and Haptic User Input: Enhancing Automatic Motion Planning with Virtual Touch},
year = {2000}
}Abstract
OBPRM: An Obstacle-Based PRM for 3DWorkspaces, Nancy M. Amato, O. Burchan Bayazit, Lucia K. Dale, Christopher Jones, Daniel Vallejo, Robotics: The Algorithmic Perspective (Third Workshop on Algorithmic Foundations of Robotics, WAFR 1998), pp. 155-168, Houston, TX, Mar 1998. @inproceedings{ABDJV-wafr98-c Recently, a new class of randomized path planning methods, known as Probabilistic Roadmap Methods (prms) have shown great potential for solving compli cated high-dimensional problems, pr m s use randomiza tion (usually during preprocessing) to construct a graph of representative paths in C-space (a roadmap) whose vertices correspond to collision-free configurations of the robot and in which two vertices are connected by an edge if a path between the two corresponding config urations can be found by a local planning method.
Keywords: obstacle-based, Sampling-Based Motion Planning
Links : [Published] BibTex
, author = "N. M. Amato and O. B. Bayazit and L. K. Dale and C. V. Jones and D. Vallejo"
, title = "{OBPRM:} An Obstacle-Based {PRM} for {3D} Workspaces"
, booktitle = "Proc. of Workshop on Algorithmic Foundations of Robotics {(WAFR'98)}"
, month = "March"
, pages = "155-168"
, year = "1998"
}
Abstract
A Randomized Roadmap Method for Path and Manipulation Planning, Nancy M. Amato, Yan Wu, Proceedings of IEEE International Conference on Robotics and Automation, Vol: 1, pp. 113-120, Minneapolis, MN, Apr 1996. DOI: 10.1109/ROBOT.1996.503582 @INPROCEEDINGS{503582, This paper presents a new randomized roadmap method for motion planning for many DOF robots that can be used to obtain high quality roadmaps even when C-space is crowded. The main novelty in the authors' approach is that roadmap candidate points are chosen on C-obstacle surfaces. As a consequence, the roadmap is likely to contain difficult paths, such as those traversing long, narrow passages in C-space. The approach can be used for both collision-free path planning and for manipulation planning of contact tasks. Experimental results with a planar articulated 6 DOF robot show that, after preprocessing, difficult path planning operations can often be carried out in less than a second.
Keywords: Sampling-Based Motion Planning
Links : [Published] BibTex
author={Amato, N.M. and Wu, Y.},
booktitle={Proceedings of IEEE International Conference on Robotics and Automation},
title={A randomized roadmap method for path and manipulation planning},
year={1996},
volume={1},
number={},
pages={113-120 vol.1},
doi={10.1109/ROBOT.1996.503582}}
Abstract