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

• URL: http://arxiv.org/abs/2602.23468v2
• Date: Mon, 02 Mar 2026 05:47:08 GMT
• Title: 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,
• Abstract summary: We present two methods capable of optimizing both edge weights and directions in a guidance graph.<n>We also incorporate traffic patterns relevant to edge directions into a GGO method, making it capable of generating edge-direction-aware guidance graphs.
• Score: 37.533959881191485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• DOGE: Differentiable Bezier Graph Optimization for Road Network Extraction [21.196497150995356]
  We introduce the Bézier Graph, a differentiable parametric curve-based representation.<n>Our framework, DOGE, operationalizes this paradigm by learning a parametric Bézier Graph directly from segmentation masks.<n>Our method sets a new state-of-the-art on the large-scale SpaceNet and CityScale benchmarks.
  arXiv  Detail & Related papers  (2025-11-25T02:28:53Z)
• ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
  Graph Neural Networks (GNNs) have exhibited the powerful ability to gather graph-structured information from neighborhood nodes. The performance of GNNs is limited by poor generalization and fragile robustness caused by noisy and redundant graph data. We propose a novel adversarial edge-dropping method (ADEdgeDrop) that leverages an adversarial edge predictor guiding the removal of edges.
  arXiv  Detail & Related papers  (2024-03-14T08:31:39Z)
• GSINA: Improving Subgraph Extraction for Graph Invariant Learning via Graph Sinkhorn Attention [52.67633391931959]
  Graph invariant learning (GIL) has been an effective approach to discovering the invariant relationships between graph data and its labels. We propose a novel graph attention mechanism called Graph Sinkhorn Attention (GSINA) GSINA is able to obtain meaningful, differentiable invariant subgraphs with controllable sparsity and softness.
  arXiv  Detail & Related papers  (2024-02-11T12:57:16Z)
• Guidance Graph Optimization for Lifelong Multi-Agent Path Finding [47.51678151084153]
  We study how to use guidance to improve the throughput of lifelong Multi-Agent Path Finding (MAPF) We introduce the guidance graph as a versatile representation of guidance for lifelong MAPF. We present two GGO algorithms to automatically generate guidance for arbitrary lifelong MAPF algorithms and maps.
  arXiv  Detail & Related papers  (2024-02-02T14:38:04Z)
• Adaptive Spatio-temporal Estimation on the Graph Edges via Line Graph Transformation [3.6448362316632115]
  Leveraging the Line Graph transform, the Line Graph Least Mean Square (LGLMS) algorithm is proposed to conduct adaptive estimation of time-varying edge signals. LGLMS is an adaptive algorithm analogous to the classical LMS algorithm but applied to graph edges.
  arXiv  Detail & Related papers  (2023-11-01T17:02:41Z)
• Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selection [57.34881616131377]
  We introduce a Personalized Subgraph Selector (PS2) as a plug-and-play framework to automatically, personally, and inductively identify optimal subgraphs for different edges. PS2 is instantiated as a bi-level optimization problem that can be efficiently solved differently. We suggest a brand-new angle towards GNNLP training: by first identifying the optimal subgraphs for edges; and then focusing on training the inference model by using the sampled subgraphs.
  arXiv  Detail & Related papers  (2022-12-23T17:30:19Z)
• GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
  We propose an efficient shared encoding for all agents and the map without sacrificing accuracy or generalization. We leverage pair-wise relative positional encodings to represent geometric relationships between the agents and the map elements in a heterogeneous spatial graph. Our decoder is also viewpoint agnostic, predicting agent goals on the lane graph to enable diverse and context-aware multimodal prediction.
  arXiv  Detail & Related papers  (2022-11-04T16:10:50Z)
• CSGO: Constrained-Softassign Gradient Optimization For Large Graph Matching [0.7456521449098222]
  This paper integrates several well-known graph matching algorithms into a framework: the constrained gradient method.<n>In attributed graph matching tasks, CSGO achieves an over 10X increase in speed compared to current constrained gradient algorithms.
  arXiv  Detail & Related papers  (2022-08-17T11:25:03Z)
• Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent [33.31762612175859]
  We present a novel approach called Optimized Directed Roadmap Graph (ODRM) ODRM is a method to build a directed roadmap graph that allows for collision avoidance in multi-robot navigation. Our experiments show that with ODRM even a simple centralized planner can solve problems with high numbers of agents that other multi-agent planners can not solve.
  arXiv  Detail & Related papers  (2020-03-29T02:18:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.