切替可能な時間的計画グラフ最適化の高速化手法
Speedup Techniques for Switchable Temporal Plan Graph Optimization
マルチエージェント経路計画の遅延に強い切替可能時間的計画グラフ最適化を、4つの高速化技術で改良し、成功率と速度を大幅に向上させた。
著者: He Jiang, Muhan Lin, Jiaoyang Li
分類: cs.MA, cs.AI, cs.RO
原文アブストラクト
Multi-Agent Path Finding (MAPF) focuses on planning collision-free paths for multiple agents. However, during the execution of a MAPF plan, agents may encounter unexpected delays, which can lead to inefficiencies, deadlocks, or even collisions. To address these issues, the Switchable Temporal Plan Graph provides a framework for finding an acyclic Temporal Plan Graph with the minimum execution cost under delays, ensuring deadlock- and collision-free execution. Unfortunately, existing optimal algorithms, such as Mixed Integer Linear Programming and Graph-Based Switchable Edge Search (GSES), are often too slow for practical use. This paper introduces Improved GSES, which significantly accelerates GSES through four speedup techniques: stronger admissible heuristics, edge grouping, prioritized branching, and incremental implementation. Experiments conducted on four different map types with varying numbers of agents demonstrate that Improved GSES consistently achieves over twice the success rate of GSES and delivers up to a 30-fold speedup on instances where both methods successfully find solutions.
