SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2402.01446 · IJCAI · 2024

Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

Yulun Zhang, Stefanos Nikolaidis, Jiaoyang Li, Varun Bhatt, He Jiang

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

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 × 91 maps and as many as 3,000 agents. We include the source code at:

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2402.01446")
get_code_for_paper("2402.01446")
have("2402.01446")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2402.01446.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2402.01446.svg)](https://syntology.ai/paper/2402.01446)

Connect an agent — have() is free.