Speedup Techniques for Switchable Temporal Plan Graph Optimization
This work addresses inefficiencies and delays in multi-agent path execution, offering a practical improvement for robotics and logistics applications, though it is incremental as it builds on an existing method.
The paper tackles the problem of slow optimal algorithms for Switchable Temporal Plan Graph optimization in Multi-Agent Path Finding by introducing Improved GSES, which achieves over twice the success rate and up to a 30-fold speedup compared to the existing Graph-Based Switchable Edge Search method.
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.