M*: A complete multirobot path planning algorithm with performance bounds

Multirobot path planning is difficult because the full configuration space of the system grows exponentially with the number of robots. Planning in the joint configuration space of a set of robots is only necessary if they are strongly coupled, which is often not true if the robots are well separated in the workspace. Therefore, we initially plan for each robot separately, and only couple sets of robots after they have been found to interact, thus minimizing the dimensionality of the search space. We present a general strategy called subdimensional expansion, which dynamically generates low dimensional search spaces embedded in the full configuration space. We also present an implementation of subdimensional expansion for robot configuration spaces that can be represented as a graph, called M*, and show that M* is complete and finds minimal cost paths.

Authors

• Glenn Wagner
• Howie Choset

Keywords

• Collision avoidance
• Robot kinematics
• Path planning
• Search problems
• Planning
• Cost function
• Pathfinding
• Planning Algorithm
• Dimensional Space
• Search Space
• Low-dimensional Space
• Configuration Space
• Cost Path
• Set Of Robots
• Finite Time
• Robotic System
• Heuristic Algorithm
• Coordination Of Activities
• Multi-agent Systems
• Optimal Path
• Position Of The Robot
• Optimistic View
• Voter Preferences
• Robot Path
• Collision-free Path
• Individual Robots