Topology-Guided Roadmap Construction with Dynamic Region Sampling

Read Sandstrom, Diane Uwacu, Jory Denny, Nancy M. Amato

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number9144398
Pages (from-to)6161-6168
Number of pages8
JournalIEEE Robotics and Automation Letters
Issue number4
StatePublished - Oct 2020
Externally publishedYes


  • Motion and path planning
  • semantic scene understanding

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Biomedical Engineering
  • Human-Computer Interaction
  • Mechanical Engineering
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Control and Optimization
  • Artificial Intelligence


Dive into the research topics of 'Topology-Guided Roadmap Construction with Dynamic Region Sampling'. Together they form a unique fingerprint.

Cite this