Hierarchical Path Planner Using Workspace Decomposition and Parallel Task-Space RRTs

This paper presents a hierarchical path planner consisting of two stages: a global planner that uses workspace information to create collision-free paths for the robot end-effector to follow, and multiple local planners running in parallel that verify the paths in the configuration space by expanding a task-space rapidly-exploring random tree (RRT). We demonstrate the practicality of our approach by comparing it with state-of-the-art planners in several challenging path planning problems. While using a single tree, our planner outperforms other single tree approaches in task-space or configuration space (C-space), while its performance and robustness are comparable to or better than that of parallelized bidirectional C-space planners.

Authors

• George Mesesan
• Máximo A. Roa
• Esra Icer
• Matthias Althoff

Keywords

• Task analysis
• Path planning
• End effectors
• Partitioning algorithms
• Collision avoidance
• Rapidly-exploring Random Tree
• Urban Planning
• Parallelization
• Single Tree
• Global Plan
• Configuration Space
• Path In Space
• Collision-free Path
• Degrees Of Freedom
• Target Region
• Tree Nodes
• Pathfinding
• Vertices
• Robot Manipulator
• Point R
• Ball Of Radius
• Humanoid Robot
• Polytope
• Breadth-first Search
• End-effector Position
• Destination Point
• Adjacency Graph
• Convex Shape
• Robot Workspace
• Convex Polytope
• Robot Path
• Robot Configuration
• Partitioning Algorithm
• Collision Detection