Physical Sciences and Mathematics Commons^™

Topology-Guided Roadmap Construction With Dynamic Region Sampling, Read Sandström, Diane Uwacu, Jory Denny, Nancy M. Amato

Department of Math & Statistics Faculty Publications

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 …