Guidance Graph Optimization for Lifelong Multi-Agent Path Finding


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.

In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), August 03–09, Jeju, Korea

Optimized Guidance Graphs

All optimized guidance graphs are available in the following table for download and analysis. The guidance graphs are offered in csv format. Each row of the csv file contains information of a vertice with the following entries:

  1. id : id of the vertice.
  2. type : type of the vertice. . for empty space, @ for obstacles, w for workstations, and e for endpoints.
  3. x : x-coordinate of the vertice in the grid map.
  4. y : y-coordinate of the vertice in the grid map.
  5. weight_to_RIGHT : edge weight of the current vertice to the vertice on the right, if valid.
  6. weight_to_UP : edge weight of the current vertice to the vertice upward, if valid.
  7. weight_to_LEFT : edge weight of the current vertice to the vertice on the left, if valid.
  8. weight_to_DOWN : edge weight of the current vertice to the vertice downward, if valid.
  9. weight_for_WAIT : wait cost of the current vertice, if valid.

If an edge/vertice is invalid (e.g. the vertice is an obstacle), the corresponding edge weight/wait cost is inf.

For more information about the maps, please refer to the original paper or MAPF benchmark sets.

Map PreviewMap NameDimension#valid vertices, #valid edgesGuidance Graphs
random-32-32-2032 $\times$ 32819, 2540PIBT + CMA-ES
maze-32-32-432 $\times$ 32790, 2694PIBT + CMA-ES
empty-48-4848 $\times$ 482304, 9024PIBT + CMA-ES
random-64-64-2064 $\times$ 643270, 10298PIBT + CMA-ES
room-64-64-864 $\times$ 643232, 11108PIBT + CMA-ES
den312d64 $\times$ 812445, 8782PIBT + CMA-ES
warehouse 33 $\times$ 3633 $\times$ 36948, 3126PIBT + CMA-ES
warehouse 17 $\times$ 2017 $\times$ 20320, 1158DPP + CMA-ES