Algorithmic Strategies

@inproceedings{shi-icra-2014
, author = "Kensen Shi and Jory Denny and Nancy M. Amato"
, title = "Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages"
, booktitle = "IEEE International Conference on Robotics and Automation (ICRA)"
, location = "Hong Kong"
, month = "May"
, year = "2014"
, pages = "4659-4666"
, doi =10.1109/ICRA.2014.6907540"
}

Probabilistic RoadMaps (PRMs) have been successful for many high-dimensional motion planning problems. However, they encounter difficulties when mapping narrow passages. While many PRM sampling methods have been proposed to increase the proportion of samples within narrow passages, such difficult planning areas still pose many challenges. We introduce a novel algorithm, Spark PRM, that sparks the growth of Rapidly-expanding Random Trees (RRTs) from narrow passage samples generated by a PRM. The RRT rapidly generates further narrow passage samples, ideally until the passage is fully mapped. After reaching a terminating condition, the tree stops growing and is added to the roadmap. Spark PRM is a general method that can be applied to all PRM variants. We study the benefits of Spark PRM with a variety of sampling strategies in a wide array of environments. We show significant speedups in computation time over RRT, Sampling-based Roadmap of Trees (SRT), and various PRM variants.

@INPROCEEDINGS{1545045,
author={O. B. {Bayazit} and {Dawen Xie} and N. M. {Amato}},
booktitle={2005 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={Iterative relaxation of constraints: a framework for improving automated motion planning},
year={2005},
volume={},
number={},
pages={3433-3440},
doi={10.1109/IROS.2005.1545045}}

This paper presents a technique for improving the efficiency of automated motion planners. Motion planning has application in many areas such as robotics, virtual reality systems, computer-aided design, and even computational biology. Although there have been steady advances in motion planning algorithms, especially in randomized approaches such as probabilistic roadmap methods (PRMs) or rapidly-exploring random trees (RRTs), there are still some classes of problems that cannot be solved efficiently using these state-of-the-art motion planners. In this paper, we suggest an iterative strategy addressing this problem where we first simplify the problem by relaxing some feasibility constraints, solve the easier version of the problem, and then use that solution to help us find a solution for the harder problem. We show how this strategy can be applied to rigid bodies and to linkages with high degrees of freedom, including both open and closed chain systems. Experimental results are presented for linkages composed of 9-98 links. Although we use PRMs as the automated planner, the framework is general and can be applied with other motion planning techniques as well.