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

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.

Introduction

In large-scale automated systems, such as robotic warehouses, Lifelong Multi-Agent Path Finding (LMAPF) is essential for maintaining a continuous flow of agents toward ever-changing goals. A primary challenge in these environments is congestion and gridlock, which significantly degrade system throughput. Previous research introduced Guidance Graph Optimization (GGO) to mitigate these issues by assigning weights to graph edges. These weights act as "soft guidance," nudging agents toward preferred paths. However, soft guidance is often insufficient in high-density scenarios or realistic rotational motion models, where head-on collisions require expensive 180-degree turns. This paper proposes Mixed Guidance Graph Optimization (MGGO), which supplements edge weights with "strict guidance" by optimizing edge directions, effectively creating one-way streets to streamline traffic.

The Transition to Mixed Guidance

The core innovation of MGGO is the transition from a purely weighted graph to a mixed guidance graph that incorporates both weights and explicit directions. While weights discourage certain paths, directions can strictly prohibit them, preventing head-on conflicts before they occur.

Comparison of the Original Graph, a standard Guidance Graph (weights only), and the proposed Mixed Guidance Graph (weights and directions).

Proposed Methodology

Optimizing edge directions introduces a significant constraint: strong connectivity. If too many edges are restricted to a single direction, certain areas of the map may become unreachable. To address this, the authors developed the Edge Reversal Search (ERS) algorithm, a greedy repair tool that identifies and flips edge directions to ensure every vertex remains reachable from every other vertex.

Building on this foundation, the paper presents two primary optimization strategies:

  1. Two-Phase MGGO-DS: This approach decouples the optimization. It first utilizes an Evolutionary Algorithm (EA) to establish an optimal layout of one-way directions. Once the topology is fixed, a black-box optimizer (CMA-ES) fine-tunes the edge weights.
  2. Joint MGGO-PU: This more advanced method uses Quality Diversity (QD) algorithms, specifically CMA-MAE, to train a neural network. This network generates both edge directions and weights simultaneously based on observed traffic patterns.

Joint Optimization with Quality Diversity

The Joint MGGO-PU method is particularly effective because it is traffic-aware. By analyzing where agents frequently wait or rotate, the model learns to place one-way restrictions where they provide the most benefit to flow.

The workflow of the QD-based Joint MGGO-PU method, which integrates traffic pattern analysis and Quality Diversity algorithms to evolve guidance graphs.

Experimental Results and Insights

The authors evaluated MGGO across various benchmarks, including warehouse layouts and game maps, with agent counts reaching up to 3,000. Key findings include:

  • Throughput Improvements: MGGO consistently outperformed weight-only GGO in high-density warehouse maps, achieving higher goals-per-timestep.
  • Efficiency in Motion: In rotational motion models, MGGO significantly reduced the "Rotate Ratio." By eliminating head-on encounters, robots spent less time spinning in place and more time moving toward their targets.
  • Scalability and Robustness: The ERS repair algorithm maintained 100% connectivity success rates on maps with over 3,000 vertices, a scale where traditional Mixed-Integer Linear Programming (MILP) solvers typically fail.
  • Planner Compatibility: Rule-based planners like PIBT showed the most significant gains from strict edge directions, as they benefit from the simplified decision-making space provided by one-way streets.

Conclusion

By integrating edge directions into the optimization process, MGGO provides a robust framework for managing high-density multi-agent traffic. The shift from soft to strict guidance, supported by connectivity-aware algorithms and traffic-informed neural networks, offers a scalable solution for modern automated logistics. Future work will explore the use of surrogate models to improve sample efficiency and the integration of long-horizon pathfinders with these optimized guidance graphs.

Summary updated

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.
BibTeX
@misc{zhang2026optimization,
  author = {Yulun Zhang and Varun Bhatt and Matthew C. Fontaine and Stefanos Nikolaidis and Jiaoyang Li},
  title = {{Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding}},
  year = {2026},
  eprint = {2602.23468},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.23468},
}
Figure