PS-ECBS: A New Algorithm for Multi-Agent Path Finding with Optimal Task Assignment
Cheng Zhang, Shixin Liu
AI summary
Problem
Traditional multi-agent path finding in warehouses often treats task assignment and path planning separately or assumes fixed positions, causing inefficiencies and collisions in dynamic environments.
Approach
The method iteratively combines Mixed-Integer Linear Programming for dynamic shelf and goal selection with the Enhanced Conflict-Based Search algorithm, adding constraints each cycle to resolve path conflicts until convergence.
Key results
- Introduces PS-ECBS, a novel iterative algorithm combining MILP and ECBS for dynamic MAPF.
- Enables simultaneous picking and returning tasks in large-scale warehouse environments.
- Demonstrates significantly faster runtime and superior joint optimization compared to ECBS-TA.
- Provides a convergence condition and iterative constraint mechanism to bridge ideal distance and actual collision-free path costs.
Why it matters
Critical for warehouse automation and logistics companies seeking to deploy scalable, collision-free robotic fleets with minimal operational latency.
Abstract
Multi-agent path finding (MAPF) problem in warehouse automation consists of optimal task assignment and path planning, where small runtime is necessary. In this paper, we present a new MAPF algorithm related to dynamic start and end positions of the robots, called Position-Selection Enhanced Conflict-Based Search (PS-ECBS). Conflict-Based Search (CBS) is a well-known framework that has been used to find collision-free paths for a given fixed task assignment, while ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS. The mixed integer linear programming (MILP) is introduced to formulate the dynamic model for optimal task assignment, and the successful combination of MILP and ECBS results in PS-ECBS algorithm. The solving process of the PS-ECBS consists of multiple iterations, and in each iteration an additional constraint is added to modify the model. In the computational experiment, the processes of picking up and putting back shelves in the warehouse could occur at the same time by PS-ECBS. We also analyzed the iterative principle of PS-ECBS, and compared its performance with that of ECBS-TA. The computational results demonstrate that PS-ECBS runs significantly faster and has an obvious advantage in jointly optimizing task assignment and path planning for large-scale warehouse.