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 directed guidance graph as a versatile representation of guidance
for lifelong MAPF, framing Guidance Graph Optimization (GGO) 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 solves GGO by employing CMA-ES, a black-box optimization
algorithm. The second method, PIU, optimizes an update model capable of
generating guidance, demonstrating the ability to transfer optimized guidance
graphs to larger maps with similar layouts. Empirically, we show that (1) our
guidance graphs improve the throughput of three representative lifelong MAPF
algorithms in four benchmark maps, and (2) our update model can generate
guidance graphs for as large as $93 \times 91$ maps and as many as 3000 agents.

我们研究了如何利用引导来提高终身多智能体路径规划（MAPF）的吞吐量。我们提出了两种 GGO 算法来自动生成适用于任意终身 MAPF 算法和地图的引导，并通过实验证明我们的引导图能够提高三个典型终身 MAPF 算法在四个基准地图上的吞吐量。