DOI
10.1109/LRA.2020.3010487
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 (PRM) algorithm is a powerful tool for this case, but often cannot efficiently connect the roadmap in the presence of narrow passages. In this letter, 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.
Document Type
Post-print Article
Publication Date
10-2020
Publisher Statement
Copyright © 2020, IEEE Robotics and Automation Letters.
DOI: https://doi.org/10.1109/LRA.2020.3010487
The definitive version is available at: IEEE Robotics and Automation Letters Volume: 5, Issue: 4.
Recommended Citation
Sandstrom, Read, Diane Uwacu, Jory Denny, and Nancy M. Amato. “Topology-Guided Roadmap Construction With Dynamic Region Sampling.” IEEE Robotics and Automation Letters 5, no. 4 (October 2020): 6161–68. https://doi.org/10.1109/LRA.2020.3010487.