Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

Abstract

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.

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 Preview	Map Name	Dimension	#valid vertices, #valid edges	Guidance Graphs
	random-32-32-20	32 $\times$ 32	819, 2540	PIBT + CMA-ES PIBT + PIU
	maze-32-32-4	32 $\times$ 32	790, 2694	PIBT + CMA-ES PIBT + PIU
	empty-48-48	48 $\times$ 48	2304, 9024	PIBT + CMA-ES PIBT + PIU
	random-64-64-20	64 $\times$ 64	3270, 10298	PIBT + CMA-ES PIBT + PIU
	room-64-64-8	64 $\times$ 64	3232, 11108	PIBT + CMA-ES PIBT + PIU
	den312d	64 $\times$ 81	2445, 8782	PIBT + CMA-ES PIBT + PIU
	warehouse 33 $\times$ 36	33 $\times$ 36	948, 3126	PIBT + CMA-ES PIBT + PIU RHCR + CMA-ES
	warehouse 17 $\times$ 20	17 $\times$ 20	320, 1158	DPP + CMA-ES