TL;DR
This paper introduces Loosely Synchronized Rule-based Planning (LSRP), a novel algorithm for Multi-Agent Path Finding (MAPF) that handles asynchronous actions (agents moving at different speeds or taking different amounts of time for actions). LSRP scales to thousands of agents, significantly outperforming existing methods in terms of scalability while maintaining reasonable solution quality.
What Problem Does This Paper Address?
Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents in a shared environment, typically aiming to minimize total travel time or path cost. Many existing MAPF algorithms make a simplifying assumption: all agents take actions in discrete, synchronized time steps. This assumption breaks down in real-world scenarios where agents have different speeds or can vary their movement speed. While some algorithms handle asynchronous actions, they often struggle with scalability, only managing a few dozen agents within practical time limits. This paper addresses the challenge of developing MAPF algorithms that can efficiently handle asynchronous actions for a large number of agents, trading off perfect optimality for significant scalability gains.
Methods
The core of this work is the Loosely Synchronized Rule-based Planning (LSRP) algorithm. LSRP combines two key ideas:
- Loosely Synchronized Search (LSS): This approach extends traditional search algorithms by incorporating action timestamps into the state definition. It allows for asynchronous actions by planning for agents based on their earliest upcoming action time, rather than strictly synchronized steps.
- Priority Inheritance with Backtracking (PIBT): This is a rule-based planning method known for its scalability in synchronous MAPF. LSRP adapts PIBT to the LSS state space, using agent priorities to resolve conflicts.
A crucial component of LSRP is its cache mechanism (represented by the dictionary Φ and list I in the paper) that stores planned future actions. This allows the algorithm to "look ahead" and manage the interactions between agents with different action durations. When conflicts arise, LSRP uses a recursive ASY-PUSH procedure to attempt to resolve them by having higher-priority agents move, potentially "pushing" lower-priority agents out of the way.
An extension, LSRP-SWAP, is also introduced to address potential non-termination issues in certain scenarios by incorporating a swap operation, inspired by similar techniques in synchronous MAPF.
Datasets
The experiments were conducted using three standard MAPF benchmark maps: "Empty-16", "Den520d", and "Warehouse". The paper does not introduce new datasets.
Key Insights and Ideas
- Scalability vs. Optimality Trade-off: The paper demonstrates that by embracing asynchronous actions and using rule-based planning with priority inheritance, significant gains in scalability can be achieved, even for thousands of agents, at the expense of optimal solutions.
- The Importance of Asynchronous Action Modeling: Ignoring asynchronous actions (by forcing uniform durations) can lead to solutions that are significantly more expensive (30-75% higher cost) than those that properly account for varying agent speeds.
- Caching Future Actions is Key: The mechanism for caching planned future actions is essential for LSRP to manage the complex interactions and dependencies introduced by asynchronous movement durations.
- Pushing as a Scalable Conflict Resolution: The ASY-PUSH mechanism, which allows higher-priority agents to push lower-priority agents, proves to be an effective and scalable way to resolve conflicts in asynchronous MAPF.
Key Results
- Scalability: LSRP and LSRP-SWAP can handle up to 1000 agents within a 30-second runtime limit, an order of magnitude more than baselines like CCBS and SIPP. LSRP-SWAP was particularly fast.
- Runtime: LSRP-SWAP was the fastest algorithm tested, outperforming LSRP and baselines.
- Solution Quality: LSRP and LSRP-SWAP achieved solutions with a median Sum of Costs (SoC) that was approximately 4x higher than baselines, and a makespan that was about 1.25x higher. This confirms the trade-off for scalability.
- Impact of Asynchronicity: Considering asynchronous actions resulted in solutions that were 30-75% cheaper than when these actions were ignored.
Limitations and Future Work
- Completeness: LSRP only guarantees "weak termination" (all agents reach their goals at least once) under specific graph conditions (c-graphs). For general graphs, LSRP-SWAP is introduced to mitigate potential non-termination issues, but the paper acknowledges that LSRP itself might not terminate in all solvable instances.
- Solution Quality: The primary limitation is the sub-optimal nature of the solutions, which is a direct consequence of prioritizing scalability.
- Future Work: The authors suggest extending LSRP into an "anytime" planner, similar to LaCAM over PIBT, to iteratively improve solution quality within the runtime limit. This would allow for a more flexible approach that can provide better solutions as more time becomes available.
Summary updated