Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding
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 congestion-aware guide paths, computed via traffic-assignment-style iterative flow updates with focal search, to guide PIBT (lifelong MAPF) and LaCAM* (one-shot MAPF) and reduce congestion.
Problem
Multi-agent path finding scales poorly because free-flow shortest-path heuristics (as in PIBT) create congestion, hurting solution quality in one-shot MAPF and throughput in lifelong MAPF with thousands of agents.
Approach
Compute time-independent congestion-aware guide paths by iteratively updating edge costs from traffic flows (two-part vertex and contraflow congestion cost, in the style of traffic assignment user-equilibrium), then use the guide paths as heuristics for PIBT and LaCAM*, with online refinement and lazy initialisation.
Key results
- On the sortation map with 1000 agents, GP-R100-Re10-F2 achieves throughput 10.2 versus 3.5 for RHCR-PBS and RHCR-ECBS while using about 0.013 s response time per timestep.
- Guided LaCAM* with focal bound 2 achieves relative SIC of 0.954 on 10000-agent Warehouse versus LaCAM* baseline and solves all 24 instances at 10000 agents where F1.2 also does.
- GP-R100-Re10-F2 improves throughput on every map and agent count, shifting the congestion peak by 2000 agents on Warehouse and Game and 200 on Sortation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use two-part congestion-aware guide paths instead of PIBT's free-flow distances | PIBT · Warehouse (8000 agents) | throughput: 19.3±5.0 -> 23.6±5.8 | Helped |
| Use two-part congestion-aware guide paths instead of PIBT's free-flow distances | PIBT · Sortation (600 agents) | throughput: 6.2±2.6 -> 10.9±3.5 | Helped |
| Use two-part congestion-aware guide paths instead of PIBT's free-flow distances | PIBT · Game (8000 agents) | throughput: 41.9±7.7 -> 45.7±8.6 | Helped |
| Use two-part congestion-aware guide paths instead of PIBT's free-flow distances | PIBT · Room (1000 agents) | throughput: 2.8±1.7 -> 2.2±1.5 | Hurt |
| Add online refinement and Focal Search bound 2 to guided PIBT (ablation) | Guided PIBT · Sortation (600–1000 agents) | throughput: 6.5±0.6 -> 11.4±0.3; 5.2±0.5 -> 11.5±0.6; 3.5±0.3 -> 10.2±0.7 | Helped |
| Add Focal Search bound 2 (ablation) | GP-R100 · Room (1000 agents) | throughput: 2.2±1.5 -> 3.1±1.8 | Helped |
| Add Focal Search bound 2 (ablation) | GP-R100 · Warehouse (8000 agents) | throughput: 23.6±5.8 -> 22.3±5.6 | Hurt |
| Ignore contraflow congestion and use vertex congestion only (ablation) | GP-R100 · Warehouse (8000 agents) | throughput: 23.6±5.8 -> 14.9±4.2 | Hurt |
| Use summed congestion costs 1 + c_e + p_v instead of the two-part cost (ablation) | GP-R100 · Sortation (600 agents) | throughput: 10.9±3.5 -> 11.8±3.8 | Helped |
| Use SU-I congestion cost only as a tie-breaker on optimal-length paths (ablation) | GP-R100 · Warehouse (8000 agents) | throughput: 23.6±5.8 -> 20.0±5.2 | Hurt |
| Allow SU-I guide paths up to C* × 2 (ablation) | GP_sui-R100 · Warehouse (8000 agents) | throughput: 20.0±5.2 -> 21.9±5.5 | Helped |
| Use congestion-aware guide paths for LaCAM* | LaCAM* · Warehouse (8000 agents) | relative SIC: 0.852 | Helped |
Surprising findings
- Vertex-congestion-only guide paths (GP_v) perform substantially worse than the two-part contraflow-aware formulation, showing contraflow costs are necessary.
- Traffic cost heuristics (TH_v) time out on large maps despite being similar in throughput on small maps.
Limitations
- Guide path initialisation is costly (7 ms per agent) and requires lazy initialisation to avoid startup delays.
- Guided LaCAM* sacrifices time for search, reducing scalability under tight runtime limits.
- Relies on focal search suboptimality bound to balance detour and congestion, with no principled objective for guide path computation.
Experimental setup
Datasets: warehouse map (synthetic) sortation centre map (synthetic) ost003d game map room-64-64-8
Benchmarks: lifelong MAPF warehouse, sortation, game and room maps one-shot MAPF warehouse, sortation, game and room maps
Metrics: throughput response time sum of individual costs (relative) solved instances
Baselines: PIBT LaCAM* RHCR-PBS RHCR-ECBS TH_v SU-I cost-to-come guide paths
Builds on: PIBT LaCAM* FOCAL Search Traffic Assignment Problem Adaptive LNS
Closest papers by meaning
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.92)
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.91)
- Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities (AAAI 2025 · similarity 0.90)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.90)
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.90)
- 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.