提升多智能体路径规划的实时性，解决执行延迟导致的拥堵与冲突。
Speedup Techniques for Switchable Temporal Plan Graph Optimization
- 通过更强启发式、边分组、优先分支和增量实现加速搜索
- 在四种地图上成功率超GSES两倍，最快提速30倍
- 适合需要快速响应的智能体协同场景，如机器人调度
多智能体路径规划（MAPF）旨在为多个智能体规划无碰撞路径。然而，在执行过程中，智能体可能遭遇意外延迟，导致效率下降、死锁甚至碰撞。为此，可切换时间计划图（Switchable Temporal Plan Graph）提供了一种框架，可在延迟下找到无环且执行成本最低的时间计划图，确保无死锁、无碰撞的执行。然而，现有最优算法如混合整数线性规划和基于图的可切换边搜索（GSES）通常过于缓慢，难以实用。本文提出改进GSES，通过四项加速技术：更强的可容许启发式、边分组、优先分支和增量实现，显著提升了搜索效率。在四种不同地图类型、多种智能体数量的实验中，改进版GSES始终比GSES成功率高出两倍以上，对成功求解实例的运行速度最高提升30倍。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。