Guidance Graph Optimization for Lifelong Multi-Agent Path Finding

• URL: http://arxiv.org/abs/2402.01446v2
• Date: Thu, 9 May 2024 19:14:12 GMT
• Title: Guidance Graph Optimization for Lifelong Multi-Agent Path Finding
• Authors: Yulun Zhang, He Jiang, Varun Bhatt, Stefanos Nikolaidis, Jiaoyang Li,
• Abstract summary: 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.
• Score: 47.51678151084153
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study how to use guidance to improve the throughput of lifelong Multi-Agent Path Finding (MAPF). Previous studies have demonstrated that, while incorporating guidance, such as highways, can accelerate MAPF algorithms, this often results in a trade-off with solution quality. In addition, how to generate good guidance automatically remains largely unexplored, with current methods falling short of surpassing manually designed ones. In this work, we introduce the guidance graph as a versatile representation of guidance for lifelong MAPF, framing Guidance Graph Optimization as the task of optimizing its edge weights. We present two GGO algorithms to automatically generate guidance for arbitrary lifelong MAPF algorithms and maps. The first method directly optimizes edge weights, while the second method optimizes an update model capable of generating edge weights. Empirically, we show that (1) our guidance graphs improve the throughput of three representative lifelong MAPF algorithms in eight benchmark maps, and (2) our update model can generate guidance graphs for as large as $93 \times 91$ maps and as many as 3,000 agents. We include the source code at: \url{https://github.com/lunjohnzhang/ggo_public}. All optimized guidance graphs are available online at: \url{https://yulunzhang.net/publication/zhang2024ggo}.

Related papers

• Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
  Multi-agent path finding (MAPF) is the problem of finding paths for multiple agents such that they do not collide. Finding optimal solutions to MAPF is NP-Hard, yet modern optimal solvers can scale to hundreds of agents and even thousands in some cases. We show how this encoding can be effectively joined with existing encodings, resulting in a novel AS method we call MAPF Algorithm selection via Graph embedding.
  arXiv  Detail & Related papers  (2024-06-16T07:41:58Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  We present SimTeG, a frustratingly Simple approach for Textual Graph learning. We first perform supervised parameter-efficient fine-tuning (PEFT) on a pre-trained LM on the downstream task. We then generate node embeddings using the last hidden states of finetuned LM.
  arXiv  Detail & Related papers  (2023-08-03T07:00:04Z)
• RNGDet++: Road Network Graph Detection by Transformer with Instance Segmentation and Multi-scale Features Enhancement [19.263691277963368]
  The graph structure of road networks is critical for downstream tasks of autonomous driving systems, such as global planning, motion prediction and control. In the past, the road network graph is usually manually annotated by human experts, which is time-consuming and labor-intensive. Previous works either post-process semantic segmentation maps or propose graph-based algorithms to directly predict the road network graph. Previous works suffer from hard-coded processing algorithms and inferior final performance. Since the new proposed approach is improved from RNGDet, it is named RNGDet++.
  arXiv  Detail & Related papers  (2022-09-21T07:06:46Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Transferable Graph Optimizers for ML Compilers [18.353830282858834]
  We propose an end-to-end, transferable deep reinforcement learning method for computational graph optimization (GO) GO generates decisions on the entire graph rather than on each individual node autoregressively, drastically speeding up the search compared to prior methods. GO achieves 21% improvement over human experts and 18% improvement over the prior state of the art with 15x faster convergence.
  arXiv  Detail & Related papers  (2020-10-21T20:28:33Z)
• Adaptive Graph Encoder for Attributed Graph Embedding [36.06427854846497]
  Attributed graph embedding learns vector representations from graph topology and node features. We propose Adaptive Graph (AGE), a novel attributed graph embedding framework. We conduct experiments using four public benchmark datasets to validate AGE on node clustering and link prediction tasks.
  arXiv  Detail & Related papers  (2020-07-03T10:20:34Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  We propose a novel pre-processing technique, namely ELectoral COllege (ELCO), which automatically expands new nodes and edges to refine the label similarity within a dense subgraph. In all setups tested, our method boosts the average score of base models by a large margin of 4.7 points, as well as consistently outperforms the state-of-the-art.
  arXiv  Detail & Related papers  (2020-06-10T14:48:48Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin.
  arXiv  Detail & Related papers  (2020-04-16T16:20:53Z)
• 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.