Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Online Guidance Graph Optimization 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.
Optimizes a small learned online guidance policy (CNN for PIBT, windowed quadratic for GPIBT) via CMA-ES to dynamically set guidance-graph edge weights, improving lifelong MAPF throughput under static and dynamic task distributions.
Problem
Lifelong multi-agent path finding (LMAPF) throughput is limited by congestion; prior guidance is static (offline) and cannot adapt when task distributions shift.
Approach
Generalize the offline guidance graph into an online guidance policy that maps real-time traffic (edge usage) and current goals to guidance-graph edge weights, and integrate it into PIBT (direct planning on periodically updated heuristic tables) and GPIBT (guide-path planning), with the policy parameters optimized by CMA-ES on LMAPF simulations.
Key results
- Online guidance (on+PIBT) improves throughput over offline guidance (off+PIBT) by up to 30.75% in the abstract's reported comparisons, and over human-designed online guidance by up to 52.42%.
- On the warehouse-33-57 map with 600 agents, on+GPIBT+LNS-type variants substantially outperform off+GPIBT+LNS; on+PIBT achieves 15.515 throughput vs 5.883 for off+PIBT on warehouse static (Table, 400 agents).
- on+PIBT is up to 4x slower than off+PIBT in runtime, but average runtime per timestep stays under 0.026 s.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace no guidance with online guidance | PIBT · warehouse map, 5,000 timesteps, 600 agents | throughput: 3.18 \pm 0.04 -> 8.66 \pm 0.04 | Helped |
| replace static offline guidance with online guidance | PIBT · warehouse map, 5,000 timesteps, 600 agents | throughput: 6.42 \pm 0.09 -> 8.66 \pm 0.04 | Helped |
| use online guidance instead of offline guidance | PIBT and GPIBT · most tested maps and agent counts | throughput | Helped |
| use online guidance instead of offline guidance | PIBT · sortation, static task distribution | throughput | Hurt |
| use online guidance instead of offline guidance | PIBT · static versus dynamic task distributions | throughput | Helped |
| use guide-path information when generating online guidance | GPIBT · tested maps and task distributions | throughput | Helped |
| replace the human-designed guidance policy with optimized online guidance | GPIBT · static task distribution | throughput | Helped |
| replace the human-designed guidance policy with optimized online guidance | GPIBT · dynamic task distribution, most maps | throughput | No clear effect |
| include LNS | on+GPIBT · warehouse map, static and dynamic task distributions | throughput | Helped |
| decrease the guidance update interval m (ablation) | on+PIBT · warehouse map, static and dynamic task distributions | throughput | Helped |
| decrease the guidance update interval m (ablation) | on+PIBT · warehouse map, static and dynamic task distributions | runtime | Hurt |
| constrain the on+GPIBT policy to 48 parameters (ablation) | on+GPIBT · empty and random maps | throughput | No clear effect |
Surprising findings
- On the sortation map with static task distribution, on+PIBT is slightly worse than offline off+PIBT because congestion locations change little over time.
- A constrained 48-parameter guidance policy performs comparably to the human-designed hm+GPIBT on empty and random maps, suggesting the handcrafted equation is near optimal there.
Limitations
- Online updates add computational overhead (up to 4x slower for PIBT and 7x for GPIBT).
- CMA-ES requires many simulator evaluations (10,000 to 50,000), limiting sample efficiency.
- Policy architecture only handles 4-neighbor grid graphs; deadlocks in PIBT are reduced but not eliminated.
Experimental setup
Datasets: sortation-33-57 map warehouse-33-57 map empty-32-32 MAPF map random-32-32 MAPF map warehouse-large-60-100 map game-194-194 MAPF map
Benchmarks: sortation-33-57 warehouse-33-57 empty-32-32 random-32-32 warehouse-large-60-100 game-194-194
Metrics: throughput CPU runtime
Baselines: off+PIBT off+GPIBT hm+GPIBT [p-on]+GPIBT RHCR
Builds on: PIBT GPIBT CMA-ES guidance graph
Closest papers by meaning
- Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities (AAAI 2025 · similarity 0.92)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.91)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.91)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.89)
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.88)
- Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic (AAAI 2025 · similarity 0.88)
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.