  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 \times 91$ maps and as many as 3,000
agents. We include the source code at:
\url{https://github.com/lunjohnzhang/ggo_public}. All optimized guidance graphs
are available online at: \url{https://yulunzhang.net/publication/zhang2024ggo}.
