Probabilistic path planning for multiple robots with subdimensional expansion

Probabilistic planners such as Rapidly-Exploring Random Trees (RRTs) and Probabilistic Roadmaps (PRMs) are powerful path planning algorithms for high dimensional systems, but even these potent techniques suffer from the curse of dimensionality, as can be seen in multirobot systems. In this paper, we apply a technique called subdimensional expansion in order to enhance the performance of probabilistic planners for multirobot path planning. We accomplish this by exploiting the structure inherent to such problems. Subdimensional expansion initially plans in each individual robot's configuration space separately. It then couples those spaces when robots come into close proximity with one another. In this way, we constrain a probabilistic planner to search a low dimensional space, while dynamically generating a higher dimensional space where necessary. We show in simulation that subdimensional expansion enhanced PRMs can solve problems involving 32 robots and 128 total degrees of freedom in less than 10 minutes. We also demonstrate that enhancing RRTs and PRMs with subdimensional expansion can decrease the time required to find a solution by more than an order of magnitude.

Authors

• Glenn Wagner
• Minsu Kang
• Howie Choset

Keywords

• Robot kinematics
• Collision avoidance
• Probabilistic logic
• Path planning
• Planning
• Educational robots
• High-dimensional
• Dimensional Space
• Multi-agent Systems
• Curse Of Dimensionality
• Configuration Space
• Order Of Expansion
• High-dimensional Systems
• Rapidly-exploring Random Tree
• Individual Robots
• Urban Planning
• Search Space
• Robotic System
• Optimal Path
• Tree Search
• Collision Detection
• Individual Policy
• Single Configuration
• Single Space
• Simulated Robot
• Collision-free Path
• Local Path
• Problem In Robotics
• Robot Configuration
• Nearest Node