Optimizing Space Utilization for More Effective Multi-Robot Path Planning

We perform a systematic exploration of the principle of Space Utilization Optimization (SUO) as a heuristic for planning better individual paths in a decoupled multi-robot path planner, with applications to both one-shot and life-long multi-robot path planning problems. We show that the heuristic set, SU - I, preserves single path optimality and significantly reduces congestion that naturally happens when many paths are planned without coordination. Integration of SU - I into complete planners brings dramatic reductions in computation time due to the significantly reduced number of conflicts and leads to sizable solution optimality gains in diverse evaluation scenarios over medium and large maps, for both one-shot and life-long problem settings.

Authors

• Shuai D. Han
• Jingjin Yu

Keywords

• Uncertainty
• Systematics
• Robot kinematics
• Pipelines
• Robot sensing systems
• Path planning
• Planning
• Space Utilization
• Multi-robot Path
• Heuristic
• Computation Time
• Reduce Computation Time
• Single Path
• Individual Paths
• Horizon
• Time Step
• Free Space
• Undirected
• Shortest Path
• Temporal Information
• Multi-agent Systems
• Planning Phase
• Edge Information
• Single Robot
• Robot Path