Rapid Randomized Restarts for Multi-Agent Path Finding Solvers
Multi-Agent Path Finding (MAPF) is an NP-hard problem well studied in artificial intelligence and robotics. It has many real-world applications for which existing MAPF solvers use various heuristics. However, these solvers are deterministic and perform poorly on "hard" instances typically characterized by many agents interfering with each other in a small region. In this paper, we enhance MAPF solvers with randomization and observe that they exhibit heavy-tailed distributions of runtimes on hard instances. This leads us to develop simple rapid randomized restart (RRR) strategies with the intuition that, given a hard instance, multiple short runs have a better chance of solving it compared to one long run. We validate this intuition through experiments and show that our RRR strategies indeed boost the performance of state-of-the-art MAPF solvers such as iECBS and M*.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Agent Path FindingSimilar Papers 제목 키워드 기반
Efficient Restarts in Non-Stationary Model-Free Reinforcement Learning
In this work, we propose three efficient restart paradigms for model-free non-stationary reinforcement learning (RL). We identify two core issues with the restart design of Mao et al. (2022)'s RestartQ-UCB algorithm: (1)…
Reinforcement LearningA Generic Bet-and-run Strategy for Speeding Up Traveling Salesperson and Minimum Vertex Cover
A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been develope…
Combinatorial OptimizationTwo Techniques That Enhance the Performance of Multi-robot Prioritized Path Planning
We introduce and empirically evaluate two techniques aimed at enhancing the performance of multi-robot prioritized path planning. The first technique is the deterministic procedure for re-scheduling (as opposed to well-k…
SchedulingFail-Fast, Restart-Smart: Early Failure Prediction and Restart for SWE Agentic Tasks
Software engineering (SWE) agents resolve repository-level issues through long trajectories that grow increasingly expensive as context accumulates. Failed runs tend to be longer and exhibit redundant exploration or loop…
Avoiding Redundant Restarts in Multimodal Global Optimization
Na\"ive restarts of global optimization solvers when operating on multimodal search landscapes may resemble the Coupon's Collector Problem, with a potential to waste significant function evaluations budget on revisiting …
global-optimization