Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding
This work is an incremental improvement for researchers and practitioners working on multi-agent pathfinding, specifically in lifelong scenarios, by introducing stricter guidance mechanisms.
This paper addresses Lifelong Multi-Agent Path Finding (LMAPF) by introducing Mixed Guidance Graph Optimization (MGGO), which optimizes both edge weights and directions in guidance graphs. This provides stricter guidance compared to prior methods that only optimized edge weights. The authors propose two MGGO methods: a two-phase optimization and a Quality Diversity algorithm for neural network generation of directions and weights.
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.