Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages
Citations Over TimeTop 15% of 2014 papers
Abstract
Probabilistic RoadMaps (PRMs) have been successful for many high-dimensional motion planning problems. However, they encounter difficulties when mapping narrow passages. While many PRM sampling methods have been proposed to increase the proportion of samples within narrow passages, such difficult planning areas still pose many challenges. We introduce a novel algorithm, Spark PRM, that sparks the growth of Rapidly-expanding Random Trees (RRTs) from narrow passage samples generated by a PRM. The RRT rapidly generates further narrow passage samples, ideally until the passage is fully mapped. After reaching a terminating condition, the tree stops growing and is added to the roadmap. Spark PRM is a general method that can be applied to all PRM variants. We study the benefits of Spark PRM with a variety of sampling strategies in a wide array of environments. We show significant speedups in computation time over RRT, Sampling-based Roadmap of Trees (SRT), and various PRM variants.
Related Papers
- → Extension of the Rapidly Exploring Random Tree Algorithm with Key Configurations for Nonholonomic Motion Planning(2006)17 cited
- → Research on the Path Planning Algorithm of Mobile Robot(2021)15 cited
- → Motion Planning by T‐RRT with Potential Function for Vertical Articulated Robots(2018)14 cited
- → Unmanned Ship Path Planning Based on RRT(2018)10 cited
- Path Planning Based on Fuzzy Rolling Rapidly-exploring Random Tree for Mobile Robot(2010)