HAS-RRT: RRT-Based Motion Planning Using Topological Guidance
Open Access
- 14 April 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 10 (6) , 6223-6230
Abstract
We present a hierarchical RRT-based motion planning strategy, Hierarchical Annotated-Skeleton Guided RRT (HAS-RRT), guided by a workspace skeleton, to solve motion planning problems. HAS-RRTprovides up to a 91% runtime reduction and builds a tree at least 30% smaller than competitors while still finding competitive-cost paths. This is because our strategy prioritizes paths indicated by the workspace guidance to efficiently find a valid motion plan for the robot. Existing methods either rely too heavily on workspace guidance or have difficulty finding narrow passages. By taking advantage of the assumptions that the workspace skeleton provides, HAS-RRTis able to build a smaller tree and find a path faster than its competitors. Additionally, we show that HAS-RRTis robust to the quality of workspace guidance provided and that, in a worst-case scenario where the workspace skeleton provides no additional insight, our method performs comparably to an unguided method.Keywords
All Related Versions
Funding Information
- National Science Foundation (IIS-2123781)
- IBM-Illinois Discovery Accelerator Institute and the Center for Networked Intelligent Components and Environments
- University of Illinois
This publication has 21 references indexed in Scilit:
- Hierarchical Planning With Annotated Skeleton GuidanceIEEE Robotics and Automation Letters, 2022
- Topology-Guided Roadmap Construction With Dynamic Region SamplingIEEE Robotics and Automation Letters, 2020
- Dynamic Region-biased Rapidly-exploring Random Trees2020
- MARRT: Medial Axis biased rapidly-exploring random trees2014
- Topological constraints in search-based robot path planningAutonomous Robots, 2012
- Efficient algorithms for computing Reeb graphsComputational Geometry, 2009
- Workspace-Based Connectivity Oracle: An Adaptive Sampling Strategy for PRM Planning2008
- Workspace importance sampling for probabilistic roadmap planning2005
- Using robotics to fold proteins and dock ligandsBioinformatics, 2002
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996