Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding

Yulun Zhang; Varun Bhatt; Matthew C. Fontaine; Stefanos Nikolaidis; Jiaoyang Li

cs.MAFeb 26, 2026

Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding

Authors: Yulun Zhang, Varun Bhatt, Matthew C. Fontaine, Stefanos Nikolaidis, Jiaoyang Li

Organizations: Robotics Institute, Carnegie Mellon University · Thomas Lord Department of Computer Science, University of Southern California · Lila Sciences

Abstract

Multi-Agent Path Finding (MAPF) aims to move agents from their start to goal vertices on a graph. Lifelong MAPF (LMAPF) continuously assigns new goals to agents as they complete current ones. To guide agents' movement in LMAPF, prior works have proposed Guidance Graph Optimization (GGO) methods to optimize a guidance graph, which is a bidirected weighted graph whose directed edges represent moving and waiting actions with edge weights being action costs. Higher edge weights represent higher action costs. However, edge weights only provide soft guidance. An edge with a high weight only discourages agents from using it, instead of prohibiting agents from traversing it. In this paper, we explore the need to incorporate edge directions optimization into GGO, providing strict guidance. We generalize GGO to Mixed Guidance Graph Optimization (MGGO), presenting two MGGO methods capable of optimizing both edge weights and directions. The first optimizes edge directions and edge weights in two phases separately. The second applies Quality Diversity algorithms to optimize a neural network capable of generating edge directions and weights. We also incorporate traffic patterns relevant to edge directions into a GGO method, making it capable of generating edge-direction-aware guidance graphs.

Figures & tables

Figure 1: A guidance graph and a mixed guidance graph defined for a grid graph. Edge weights are all 1 for simplicity.

Figure 2: Optimize edge directions in phase one of MGGO-DS.

Setup	MAPF	Map	$\|E_{mg\_max}\|$	$\|X\|$	$N_{a}$
1	RHCR	random-32-32-20	3,359	1,258	200
2		warehouse-33-36	4,074	1,563	220
3		empty-48-48	11,328	4,512	800
4	PIBT	random-32-32-20	3,359	1,258	400
5		warehouse-33-36	4,074	1,563	400
6		empty-48-48	11,328	4,512	1,000

Table 1: Summary of the experiment setup.

|E_{mg\_max}|

is the maximum number of edges the mixed guidance graphs can have, respectively.

|X|

is the number of decision variables in phase-one of two-phase MGGO-DS.

N_{a}

is the number of agents.

Panel of Figure 5 — Figure 5: Throughput, wait action ratio, and rotation action ratio with different numbers of agents for RHCR in setups 1 to 3.

Panel of Figure 6 — Figure 6: Throughput, wait action ratio, and rotation action ratio with different numbers of agents for PIBT in setups 4 to 8.

MGGO	Throughput	CPU Runtime
QD + Joint MGGO-PU	$\textbf{4.42}\pm\textbf{0.02}$	$2.76\pm 0.03$
CMA-ES + Joint MGGO-PU	$4.26\pm 0.01$	$3.35\pm 0.01$
QD + Joint MGGO-PU (Indept Edge-Dir Rep)	$4.18\pm 0.01$	$\textbf{2.57}\pm\textbf{0.01}$
MGGO-DS (Phase 1)	$\textbf{4.07}\pm\textbf{0.01}$	$\textbf{2.40}\pm\textbf{0.02}$
MGGO-DS (Phase 1, Bi-Dir)	$3.93\pm 0.01$	$3.03\pm 0.02$
MGGO-DS (Phase 1, k-node Only)	$3.86\pm 0.01$	$3.01\pm 0.02$

Table 2: Numerical results of ablation experiments. We run each graph for 50 times and report the results in the format of

x\pm y

, where

x

and

y

are the average and standard error, respectively.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: ERS vs. MILP.

Panel of Figure 8 — Figure 8: Comparison of different agent priority strategies of PIBT before and after GGO.

Setup	MAPF + (M)GGO	SR	Throughput	CPU Runtime
1	CMA-ES + Edge-Dir-Aware GGO-PU	94%	$\textbf{4.93}\pm\textbf{0.03}$	$29.47\pm 0.81$
	CMA-ES + GGO-DS	92%	$4.69\pm 0.04$	$33.77\pm 0.85$
	Directed Crisscross	0%	N/A	N/A
	No Guidance	0%	N/A	N/A
	QD + Joint MGGO-PU	92%	$4.08\pm 0.03$	$32.59\pm 0.94$
	Two-Phase MGGO-DS	100%	$4.20\pm 0.00$	$\textbf{18.63}\pm\textbf{0.08}$

Appendix

Table 3: Success rates ( SR ), throughput, and CPU runtimes of the simulations on different mixed guidance graphs. For RHCR, the success rate is the percentage of simulations that end without congestion. For PIBT, it is the percentage of simulations that end without timeout. We measure the throughput and CPU runtime over only successful simulations.

Panel of Figure 9 — Figure 9: Throughput, wait action ratio, and rotation action ratio of Joint MGGO-PU ablations experiments.

Panel of Figure 10 — Figure 10: Throughput, wait action ratio, and rotation action ratio of $(1+\lambda)$ EA ablations experiments.

Panel of Figure 11 — Figure 11: Example optimized mixed guidance graphs. The arrows indicate edge directions and the color indicates edge weights.

Multi-Agent Path Finding

Multi-agent path finding (MAPF) plans collision-free routes for multiple agents sharing an environment.

See all 93 papers

A Lightweight Traffic Map for Efficient Anytime LaCAM*
Mar 9, 2026Bojie Shen, Yue Zhang, Zhe Chen +1Multi-Agent Path Finding
Monash University, Faculty of Information Technology
The Cost of Classical Multi-Agent Path Finding
Oct 7, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianMulti-Agent Path Finding Graph-Based Planning
Chalmers University of Technology Gothenburg, Sweden
Map-Distribution Mixture-of-Experts for Multi-Agent Pathfinding
Oct 19, 2026Fumimaro Suzuki, Keisuke OkumuraMulti-Agent Path Finding Mixture-of-Experts Models
University of Tsukuba, Tsukuba, Japan · National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan

Mar 9, 2026J/K move · Enter open · S save

A Lightweight Traffic Map for Efficient Anytime LaCAM*

Bojie Shen, Yue Zhang, Zhe Chen, Daniel Harabor

Monash University, Faculty of Information Technology

Multi-Agent Path Finding

Open paper AskPDF arXiv

Multi-Agent Path Finding (MAPF) aims to compute collision-free paths for multiple agents and has a wide range of practical applications. LaCAM*, an anytime configuration-based solver, currently represents the state of the art. Recent work has explored the use of guidance paths to steer LaCAM* toward configurations that avoid traffic congestion, thereby improving solution quality. However, existing approaches rely on Frank-Wolfe-style optimization that repeatedly invokes single-agent search before executing LaCAM*, resulting in substantial computational overhead for large-scale problems. Moreover, the guidance path is static and primarily beneficial for finding the first solution in LaCAM*. To address these limitations, we propose a new approach that leverages LaCAM*'s ability to construct a dynamic, lightweight traffic map during its search. Experimental results demonstrate that our method achieves higher solution quality than state-of-the-art guidance-path approaches across two MAPF variants.

Abstract

Multi-Agent Path Finding

Explore similar work

A Lightweight Traffic Map for Efficient Anytime LaCAM*

The Cost of Classical Multi-Agent Path Finding

Map-Distribution Mixture-of-Experts for Multi-Agent Pathfinding