DRRRT: Dynamic Region RRT
Dynamic Region RRT moves sampling regions along a workspace skeleton to direct RRT growth. It focuses effort on relevant portions of the workspace and quickly discovers feasible paths.
Algorithm overview
Initialization- Locate the skeleton vertices ks,kg nearest to the query start qs and goal qg
- Prune components which are not relevant to the query (qs,qg)Prune components which are not relevant to the query (qs,qg)
- Initialize sampling regions on edges outbound from ks
- Sample RRT growth targets within the sampling regions
- When the tree reaches a region r, advance r forward along its skeleton edge
- When r reaches the end of its skeleton edge, initialize new regions at the target vertex
Evaluation
Dynamic Region RRT was compared with three other workspace-guided planners to evaluate its efficacy.- Workspace Importance Sampling (WIS) analyzes decomposition cells to increase PRM sampling density in narrow passages (Kurniawati, Hsu 2004)
- Dynamic Domain RRT shrinks the extension domain for roadmap nodes near the boundary of the free space (Yershova et. al. 2005)
- Synergistic Combination of Layers of Planning (SyCLoP) finds a path through a decomposition graph and directs RRT grwoth along it (Plaku et. al. 2007)
- Dynamic Region RRT shows significantly better run time with high consistency
- SyCLoP takes longer due to redundant exploration
- Dynamic Domain heuristic hurts because it assumes omnidirectional obstacle space
Grid maze runtime comparison.
DRPRM: Dynamic Region PRM
Dynamic Region PRM evolves the Dynamic Region sampling concepts to account for the growth of multiple connected components.
Algorithm overview
Initialization- Create sampling regions around each skeleton vertex
- Sample and connect several configurations within each region to generate local components
- Initialize sampling regions on the outbound edges for each local component.
- Sample configurations Q in a region r for a local component C
- For all q∈Q that connect to C, add them to C and advance r
- Try to merge C with components from the other side to form bridges
- If C reaches the end of its segment without merging, spawn new outbound regions to continue expansion
Evaluation
Dynamic Regions PRM was compared with its RRT counterpart and Workspace Importance Sampling (WIS) in multi-query problems. The PRM methods build a roadmap of fixed size before answering a number of queries. Dynamic Region RRT must solve each query from scratch to illustrate the importance of multi-query methods. The algorithms were tested on a garage environment with a 6 DOF quadcopter robot and multiple levels and thin separating floors, to measure the planner's ability to find routes through a realistic environment where the shortest valid path does not correlate to the shortest path in configuration space. The results show that:- Dynamic Region PRM has consistent, low path costs and competitive times
- Dynamic Region RRT fails to find some paths in the time limit
- The quality of the skeleton matters, and the skeleton needs to have reasonable clearance to allow roadmap expansion.
Garage runtime comparison.
Related Publications
Topology-Guided Roadmap Construction with Dynamic Region Sampling, Read Sandström, Diane Uwacu, Jory Denny, Nancy M. Amato, IEEE Robotics and Automation Letters (RA-L), vol. 5, no. 4,, pp. 6161-6168, virtual, Oct 2020. DOI: 10.1109/LRA.2020.3010487 @ARTICLE{9144398, 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.
Keywords: Sampling-Based Motion Planning, Workspace Topology
Links : [Published] BibTex
author={R. {Sandström} and D. {Uwacu} and J. {Denny} and N. M. {Amato}},
journal={IEEE Robotics and Automation Letters},
title={Topology-Guided Roadmap Construction With Dynamic Region Sampling},
year={2020},
volume={5},
number={4},
pages={6161-6168},}Abstract
Dynamic Region-biased Rapidly-exploring Random Trees, Jory Denny and Read Sandstrom and Andrew Bregger and Nancy M. Amato, Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics (SPAR). The 2016 Workshop on the Algorithmic Foundations of Robotics (WAFR), Vol: 13, pp. 640-655, May 2020. DOI: 10.1007/978-3-030-43089-4_41 @article{denny-wafr-2016 Current state-of-the-art motion planners rely on samplingbased planning to explore the problem space for a solution. However, sampling valid configurations in narrow or cluttered workspaces remains a challenge. If a valid path for the robot correlates to a path in the workspace, then the planning process can employ a representation of the workspace that captures its salient topological features. Prior approaches have investigated exploiting geometric decompositions of the workspace to bias sampling; while beneficial in some environments, complex narrow passages remain challenging to navigate.
In this work, we present Dynamic Region-biased RRT, a novel samplingbased planner that guides the exploration of a Rapidly-exploring Random Tree (RRT) by moving sampling regions along an embedded graph that captures the workspace topology. These sampling regions are dynamically created, manipulated, and destroyed to greedily bias sampling through unexplored passages that lead to the goal. We show that our approach reduces online planning time compared with related methods on a set of maze-like problems.
Keywords: Sampling-Based Motion Planning, Workspace Topology
Links : [Published] BibTex
, author = "Jory Denny and Read Sandstrom and Andrew Bregger and Nancy M. Amato"
, title = "Dynamic Region-biased Rapidly-exploring Random Trees"
, journal = "Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics (SPAR)"
, volume = "13"
, publisher = "Springer, Cham."
, pages = "640-655"
, year = "2020"
, doi = "10.1007/978-3-030-43089-4\_41"
, note = "Presented at the 2016 Workshop on the Algorithmic Foundations of Robotics (WAFR)."
}
Abstract