We present the Windowed Anytime Multiagent Planning Framework (WAMPF), a framework that can make any optimal MAPF solver anytime by exploiting domain sparsity. Real-world domains are often sparse, i.e. agent-agent collisions tend to involve a small subset of agents in a single local region; this allows WAMPF to break down a large MAPF problem into small repair windows that can be efficiently searched to quickly generate a valid path. As time permits, WAMPF repair windows are grown and further repaired to improve the global repair quality. WAMPF provides online path suboptimality upperbounds, provably converges to a known optimal path given sufficient runtime, and provides infrastructure for information reuse to speed up window repair searches if supported by the underlying MAPF planner.
We present two A*-based implementations of WAMPF: 1) Naive Windowing A* (NWA*), a naive implementation that does not leverage information reuse, and 2) Expanding A* (X*), an efficient implementation that employs a novel A* search tree transformation to perform search reuse.
Experimentally, we demonstrate that in sparse domains: 1) X* outperforms state-of-the-art anytime or optimal MAPF solvers in time to valid path, 2) X* is competitive with state-of-the-art anytime or optimal MAPF solvers in time to optimal path, 3) X* quickly converges to tight suboptimality bounds, and 4) X* is competitive with state-of-the-art suboptimal MAPF solvers in time to valid path for small numbers of agents while providing much higher quality paths.
Two minute teaser video [slides]
Fifteen minute overview video [slides]