# Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

arXiv: https://arxiv.org/abs/2402.01446 · HTML: https://mlsanity.com/paper/2402.01446/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 2 Feb 2024.

## Builds on (most cited first, 16 of 16)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [pyribs: A Bare-Bones Python Library for Quality Diversity Optimization](https://mlsanity.com/paper/2303.00191/) (2023)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Multi-Robot Coordination and Layout Design for Automated Warehousing](https://mlsanity.com/paper/2305.06436/) (2023)
- [Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2308.11234/) (2023)
- [Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers](https://mlsanity.com/paper/1912.00253/) (2019)
- [Arbitrarily Scalable Environment Generators via Neural Cellular Automata](https://mlsanity.com/paper/2310.18622/) (2023)
- [Optimizing Space Utilization for More Effective Multi-Robot Path Planning](https://mlsanity.com/paper/2109.04677/) (2021)
- [The Study of Highway for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2304.04217/) (2023)

## Built on by (most cited first, 13 of 13)

- [Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities](https://mlsanity.com/paper/2404.16162/) (2024)
- [Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large Scale Imitation Learning for MAPF](https://mlsanity.com/paper/2409.14491/) (2024)
- [Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2410.21415/) (2024)
- [RAILGUN: A Unified Convolutional Policy for Multi-Agent Path Finding Across Different Environments and Tasks](https://mlsanity.com/paper/2503.02992/) (2025)
- [DeepFleet: Multi-Agent Foundation Models for Mobile Robots](https://mlsanity.com/paper/2508.08574/) (2025)
- [Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems](https://mlsanity.com/paper/2510.03472/) (2025)
- [Caching-Augmented Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2403.13421/) (2024)
- [Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2602.23468/) (2026)
- [Enhancing Lifelong Multi-Agent Path Finding with Cache Mechanism](https://mlsanity.com/paper/2501.02803/) (2025)
- [A Lightweight Traffic Map for Efficient Anytime LaCAM*](https://mlsanity.com/paper/2603.07891/) (2026)
- [Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF](https://mlsanity.com/paper/2608.06702/) (2026)
- [Belief-Aware Multi-Agent Path Finding under Map Uncertainty](https://mlsanity.com/paper/2609.40269/) (2026)
- [Reinforcement Learning for Large-Scale Lifelong Multi-Agent Path Finding with Shared Spatial Fields](https://mlsanity.com/paper/2610.18186/) (2026)

## Abstract (arXiv)

We study how to use guidance to improve the throughput of lifelong Multi-Agent Path Finding (MAPF). Previous studies have demonstrated that, while incorporating guidance, such as highways, can accelerate MAPF algorithms, this often results in a trade-off with solution quality. In addition, how to generate good guidance automatically remains largely unexplored, with current methods falling short of surpassing manually designed ones. In this work, we introduce the guidance graph as a versatile representation of guidance for lifelong MAPF, framing Guidance Graph Optimization as the task of optimizing its edge weights. We present two GGO algorithms to automatically generate guidance for arbitrary lifelong MAPF algorithms and maps. The first method directly optimizes edge weights, while the second method optimizes an update model capable of generating edge weights. Empirically, we show that (1) our guidance graphs improve the throughput of three representative lifelong MAPF algorithms in eight benchmark maps, and (2) our update model can generate guidance graphs for as large as 93 × 91 maps and as many as 3,000 agents. We include the source code at: urlhttps://github.com/lunjohnzhang/ggopublic. All optimized guidance graphs are available online at: urlhttps://yulunzhang.net/publication/zhang2024ggo.