TY - JOUR
T1 - Topology-Guided Roadmap Construction with Dynamic Region Sampling
AU - Sandstrom, Read
AU - Uwacu, Diane
AU - Denny, Jory
AU - Amato, Nancy M.
N1 - Manuscript received February 24, 2020; accepted June 24, 2020. Date of publication July 20, 2020; date of current version August 6, 2020. This letter was recommended for publication by Associate Editor Y. Guo and Editor D. Song upon evaluation of the reviewers’ comments. This work was supported by NSF Awards under Grants CSF-1439145, CCF-1423111, EFRI-1240483, and RI-1217991 (Corresponding author: Nancy Amato.) Read Sandström and Diane Uwacu are with the Parasol Laboratory, Dept. of Computer Science and Engineering, Texas A&M University, College Station, TX 77840 USA (e-mail: [email protected]; [email protected]).
PY - 2020/10
Y1 - 2020/10
N2 - 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.
AB - 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.
KW - Motion and path planning
KW - semantic scene understanding
UR - http://www.scopus.com/inward/record.url?scp=85089945324&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089945324&partnerID=8YFLogxK
U2 - 10.1109/LRA.2020.3010487
DO - 10.1109/LRA.2020.3010487
M3 - Article
AN - SCOPUS:85089945324
SN - 2377-3766
VL - 5
SP - 6161
EP - 6168
JO - IEEE Robotics and Automation Letters
JF - IEEE Robotics and Automation Letters
IS - 4
M1 - 9144398
ER -