MARRT: Medial Axis biased rapidly-exploring random trees
Authors:
Open Access
- 1 May 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10504729,p. 90-97
Abstract
Motion planning is a difficult and widely studied problem in robotics. Current research aims not only to find feasible paths, but to ensure paths have certain properties, e.g., shortest or safest paths. This is difficult for current state-of-the-art sampling-based techniques as they typically focus on simply finding any path. Despite this difficulty, sampling-based techniques have shown great success in planning for a wide range of applications. Among such planners, Rapidly-Exploring Random Trees (RRTs) search the planning space by biasing exploration toward unexplored regions. This paper introduces a novel RRT variant, Medial Axis RRT (MARRT), which biases tree exploration to the medial axis of free space by pushing all configurations from expansion steps towards the medial axis. We prove that this biasing increases the tree's clearance from obstacles. Improving obstacle clearance is useful where path safety is important, e.g., path planning for robots performing tasks in close proximity to the elderly. Finally, we experimentally analyze MARRT, emphasizing its ability to effectively map difficult passages while increasing obstacle clearance, and compare it to contemporary RRT techniques.Keywords
This publication has 15 references indexed in Scilit:
- Sampling-based algorithms for optimal motion planningThe International Journal of Robotics Research, 2011
- The STAPL parallel container framework2011
- Sampling-Based Path Planning on Configuration-Space CostmapsIEEE Transactions on Robotics, 2010
- An obstacle-based rapidly-exploring random tree2006
- A general framework for sampling on the medial axis of the free space2004
- Fast distance queries with rectangular swept sphere volumes2002
- A framework for using the workspace medial axis in PRM planners2000
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- Complexity of the mover's problem and generalizations1979