Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Windowed MAPF with Completeness Guarantees
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 WinC-MAPF, a framework that makes windowed MAPF solvers complete by combining real-time heuristic updates with grouped heuristic penalties, and instantiates it as Single-Step CBS (SS-CBS) with heuristic conflicts.
Problem
Windowed multi-agent path finding (MAPF) planners compute only partial collision-free paths over a short horizon, which makes them incomplete and prone to deadlock and livelock in congestion.
Approach
Views windowed MAPF in the joint configuration space and applies real-time search heuristic updates (penalties) to disjoint groups of coupled agents rather than the full joint configuration; SS-CBS adds a "heuristic conflict" constraint so CBS can find the optimal single-step action given penalties.
Key results
- On tough congested scenarios, SS-CBS achieves success rates of 1 on Tunnel (3,4), Loopchain (6), and Connector (5,6), while wCBS (W=1-16) fails completely and CBS+ and EECBS (w=1.5) solve few or none of the harder instances.
- On standard benchmark maps, SS-CBS (single-step planning) consistently outperforms windowed CBS with windows 1 to 16 in success rate, with solution cost about 2-8% higher than wCBS.
- SS-CBS's failures on benchmarks were attributed to a few congested iterations taking over 10 seconds each.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SS-CBS with single-step planning and grouped heuristic penalties instead of full-horizon CBS+ | MAPF · High-congestion small maps | success: Tunnel (3): 0.9 -> 1; Tunnel (4): 0 -> 1; Loopchain (6): 0 -> 1; Loopchain (7): 0 -> 0.95; Connector (5): 0 -> 1; Connec | Helped |
| Use SS-CBS with single-step planning instead of EECBS w_so=1.5 | MAPF · High-congestion small maps | success: Tunnel (3): 0.80 -> 1; Tunnel (4): 0 -> 1; Loopchain (6): 0 -> 1; Loopchain (7): 0 -> 0.95; Connector (5): 0.95 -> 1; Co | Mixed |
| Use SS-CBS rather than windowed CBS | MAPF benchmark scenarios · random-32-32-20, ht_chantry, den520d, warehouse-10-20-10-2-1 | solution cost: 2-8% higher | Hurt |
| Increase high-level suboptimality above 1 (ablation) | SS-CBS · Standard benchmark maps | scalability | Mixed |
| Use distance-based priority tie-breaking instead of no tie-breaking (ablation) | SS-CBS · Standard benchmark maps | scalability | Helped |
| Use random-initialized priority tie-breaking instead of no tie-breaking (ablation) | SS-CBS · Standard benchmark maps | scalability | Helped |
| Increase high-level suboptimality in congested scenarios (ablation) | SS-CBS · random-32-32-20 and warehouse | iterations to reach goal | Hurt |
| Increase high-level suboptimality from 1 to 1.05 (ablation) | SS-CBS · Three of four benchmark maps | scalability | Helped |
| Increase high-level suboptimality beyond 1.05 (ablation) | SS-CBS · Benchmark maps | scalability | No clear effect |
| Increase windowed ECBS suboptimality (ablation) | Windowed ECBS · Benchmark maps | scalability | Mixed |
Surprising findings
- A single-step (W=1) planner with heuristic penalties outperforms windowed CBS with larger windows and even full-horizon CBS+ on congested instances.
- Higher high-level suboptimality (w>1) helped scalability for windowed ECBS but not for SS-CBS beyond 1.05.
Limitations
- Completeness proven only for optimal action generators; suboptimal variants untested theoretically.
- Requires perfect backward Dijkstra single-agent heuristics.
- Solution costs are very high on tough congested scenarios (e.g., about 7500 to 11000), and some iterations take tens of seconds.
Experimental setup
Datasets: random-32-32-20 ht_chantry den520d warehouse-10-20-10-2-1 tough congested small maps (Tunnel, Loopchain, Connector)
Benchmarks: random-32-32-20 ht_chantry den520d warehouse-10-20-10-2-1 Tunnel Loopchain Connector
Metrics: success rate runtime solution cost makespan number of heuristic penalties
Baselines: windowed CBS (wCBS) CBS+ EECBS RHCR Windowed ECBS
Builds on: LRTA* Conflict-Based Search Enhanced CBS RHCR Independence Detection
Closest papers by meaning
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.91)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.90)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.90)
- Speedup Techniques for Switchable Temporal Plan Graph Optimization (AAAI 2025 · similarity 0.89)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.89)
- Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic (AAAI 2025 · similarity 0.89)
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.