OBPRM: Obstacle-Based PRM

@INPROCEEDINGS{6385875,
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}}

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.

@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

@INPROCEEDINGS{1570589,
author={M. A. {Morales A.} and L. {Tapia} and R. {Pearce} and S. {Rodriguez} and N. M. {Amato}},
booktitle={Proceedings of the 2005 IEEE International Conference on Robotics and Automation},
title={C-space Subdivision and Integration in Feature-Sensitive Motion Planning},
year={2005},
volume={},
number={},
pages={3114-3119},
doi={10.1109/ROBOT.2005.1570589}}

There are many randomized motion planning techniques, but it is often difficult to determine what planning method to apply to best solve a problem. Planners have their own strengths and weaknesses, and each one is best suited to a specific type of problem. In previous work, we proposed a meta-planner that, through analysis of the problem features, subdivides the instance into regions and determines which planner to apply in each region. The results obtained with our prototype system were very promising even though it utilized simplistic strategies for all components. Even so, we did determine that strategies for problem subdivision and for combination of partial regional solutions have a crucial impact on performance. In this paper, we propose new methods for these steps to improve the performance of the meta-planner. For problem subdivision, we propose two new methods: a method based on ‘ gaps’ and a method based on information theory. For combining partial solutions, we propose two new methods that concentrate on neighboring areas of the regional solutions. We present results that show the performance gain achieved by utilizing these new strategies.

@MISC{Bayazit00ligandbinding,
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}
}

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.

@inproceedings{ABDJV-wafr98-c
, 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"
}

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.

@INPROCEEDINGS{503582,
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}}

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.