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

arXiv: https://arxiv.org/abs/2602.23468 · HTML: https://mlsanity.com/paper/2602.23468/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 45 references that are in the map.
- First posted on arXiv 26 Feb 2026.

## Builds on (most cited first, 24 of 24)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network](https://mlsanity.com/paper/2007.05674/) (2020)
- [Deep Surrogate Assisted Generation of Environments](https://mlsanity.com/paper/2206.04199/) (2022)
- [Mapping Hearthstone Deck Spaces through MAP-Elites with Sliding Boundaries](https://mlsanity.com/paper/1904.10656/) (2019)
- [pyribs: A Bare-Bones Python Library for Quality Diversity Optimization](https://mlsanity.com/paper/2303.00191/) (2023)
- [Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding](https://mlsanity.com/paper/2112.03534/) (2021)
- [Covariance Matrix Adaptation MAP-Annealing](https://mlsanity.com/paper/2205.10752/) (2022)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2308.11234/) (2023)
- [Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers](https://mlsanity.com/paper/1912.00253/) (2019)
- [Guidance Graph Optimization for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2402.01446/) (2024)
- [Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities](https://mlsanity.com/paper/2404.16162/) (2024)
- [Arbitrarily Scalable Environment Generators via Neural Cellular Automata](https://mlsanity.com/paper/2310.18622/) (2023)
- [Quality-Diversity Algorithms Can Provably Be Helpful for Optimization](https://mlsanity.com/paper/2401.10539/) (2024)
- [Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search](https://mlsanity.com/paper/2412.13359/) (2024)
- [Optimizing Space Utilization for More Effective Multi-Robot Path Planning](https://mlsanity.com/paper/2109.04677/) (2021)
- [Enhancing PIBT via Multi-Action Operations](https://mlsanity.com/paper/2511.09193/) (2025)
- [Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems](https://mlsanity.com/paper/2510.03472/) (2025)
- [The Study of Highway for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2304.04217/) (2023)

## Built on by (most cited first, 1 of 1)

- [Planning over MAPF Agent Dependencies via Multi-Dependency PIBT](https://mlsanity.com/paper/2603.23405/) (2026)

## Abstract (arXiv)

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.