Topology-Guided Roadmap Construction With Dynamic Region Sampling
- 20 July 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 5 (4) , 6161-6168
Abstract
Many types of planning problems require discovery of multiple pathways through the environment, such as multi-robot coordination or protein ligand binding. The Probabilistic Roadmap algorithm (PRM) is a powerful tool for this case, but struggles to efficiently connect the roadmap in the presence of narrow passages. In this paper, we present a guidance mechanism that encourages the rapid construction of well-connected roadmaps with PRM methods. We leverage a topological skeleton of the workspace to track the algorithm's progress in both covering and connecting distinct neighborhoods, and employ this information to focus computation on the uncovered and unconnected regions. We demonstrate how this guidance improves PRM's efficiency in building a roadmap that can answer multiple queries in both robotics and protein ligand binding applications.Keywords
Funding Information
- NSF (CSF-1439145, CCF-1423111, EFRI-1240483, RI-1217991)
This publication has 23 references indexed in Scilit:
- Toggle PRM: A Coordinated Mapping of C-Free and C-Obstacle in Arbitrary Dimension2013
- Mean Curvature SkeletonsComputer Graphics Forum, 2012
- Topological constraints in search-based robot path planningAutonomous Robots, 2012
- Workspace-Based Connectivity Oracle: An Adaptive Sampling Strategy for PRM Planning2008
- Simulating Protein Motions with Rigidity AnalysisJournal of Computational Biology, 2007
- On the Probabilistic Foundations of Probabilistic Roadmap PlanningThe International Journal of Robotics Research, 2006
- Using Workspace Information as a Guide to Non-uniform Sampling in Probabilistic Roadmap PlannersThe International Journal of Robotics Research, 2005
- A Machine Learning Approach for Feature-Sensitive Motion Planning2005
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979