Authors: Rishi Veerapaneni, Muhammad Suhail Saleem, Jiaoyang Li, Maxim Likhachev
Abstract: Traditional multi-agent path finding (MAPF) methods try to compute entire
start-goal paths which are collision free. However, computing an entire path
can take too long for MAPF systems where agents need to replan fast. Methods
that address this typically employ a “windowed” approach and only try to find
collision free paths for a small windowed timestep horizon. This adaptation
comes at the cost of incompleteness; all current windowed approaches can become
stuck in deadlock or livelock. Our main contribution is to introduce our
framework, WinC-MAPF, for Windowed MAPF that enables completeness. Our
framework uses heuristic update insights from single-agent real-time heuristic
search algorithms as well as agent independence ideas from MAPF algorithms. We
also develop Single-Step CBS (SS-CBS), an instantiation of this framework using
a novel modification to CBS. We show how SS-CBS, which only plans a single step
and updates heuristics, can effectively solve tough scenarios where existing
windowed approaches fail.
Source: http://arxiv.org/abs/2410.01798v1
