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.
Funding Information
  • NSF (CSF-1439145, CCF-1423111, EFRI-1240483, RI-1217991)

This publication has 23 references indexed in Scilit: