Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Loosely Synchronized Rule-based Planning (LSRP, with a swap variant LSRP-SWAP) that combines PIBT with loosely synchronized search to scale MAPF with asynchronous actions to about 1000 agents at the cost of solution quality.
Problem
Multi-agent path finding where agents have asynchronous, variable-duration actions (MAPF-AA); existing solvers either are optimal/bounded-suboptimal with limited scalability (≤100 agents) or assume synchronized unit-time actions.
Approach
Extends PIBT's recursive push to continuous timestamps: plans agents whose arrival times coincide, caches future wait-and-move actions in a dictionary, and adds a swap operation (LSRP-SWAP) to resolve deadlocks under duration conflicts.
Key results
- LSRP and LSRP-SWAP handle up to an order of magnitude more agents than CCBS and SIPP within a 30-second runtime limit; LSRP-SWAP handles up to 1000 agents.
- Median solution ratios are about 4x in SoC and 1.25x in makespan relative to baselines, i.e. about 25% longer makespan.
- Considering asynchronous actions yields solutions usually 30% and sometimes up to 75% cheaper than ignoring them.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LSRP or LSRP-SWAP instead of the baseline planners | MAPF-AA planning · MAPF benchmark maps | agents handled within the runtime limit: an order of magnitude | Helped |
| Use LSRP-SWAP instead of LSRP without swap | MAPF-AA planning · Warehouse | scalability and runtime | Helped |
| Consider asynchronous actions during planning rather than ignoring them | LSRP and LSRP-SWAP · MAPF benchmark instances | solution cost: 30\% and sometimes up to 75\% cheaper | Helped |
| Use LSRP or LSRP-SWAP instead of CCBS or SIPP | MAPF-AA planning · Successfully solved shared instances | makespan: 1.25x | Hurt |
| Use LSRP or LSRP-SWAP instead of CCBS or SIPP | MAPF-AA planning · Successfully solved shared instances | SoC: 4x | Hurt |
| Add the swap operation to LSRP (ablation) | LSRP · Warehouse | scalability and runtime | Helped |
Surprising findings
- Plain asynchronous PIBT-style push can loop forever on solvable instances, requiring the swap operation for completeness on those cases.
Limitations
- Solution quality is much worse than optimal planners (about 4x SoC median).
- Weak termination only guaranteed on c-graphs; may not terminate on some solvable instances without swap.
- No anytime improvement of solutions.
Experimental setup
Datasets: MAPF benchmark maps (Empty-16, Den520d, Warehouse)
Benchmarks: Empty-16 Den520d Warehouse
Metrics: success rate runtime sum of costs ratio makespan ratio
Baselines: CCBS SIPP-based prioritized planning
Builds on: PIBT Loosely Synchronized Search Conflict-Based Search Safe Interval Path Planning Causal PIBT
Closest papers by meaning
- Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI 2024 · similarity 0.91)
- Speedup Techniques for Switchable Temporal Plan Graph Optimization (AAAI 2025 · similarity 0.91)
- Windowed MAPF with Completeness Guarantees (AAAI 2025 · similarity 0.91)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.90)
- Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities (AAAI 2025 · similarity 0.90)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.