  Anytime multi-agent path finding (MAPF) is a promising approach to scalable
path optimization in large-scale multi-agent systems. State-of-the-art anytime
MAPF is based on Large Neighborhood Search (LNS), where a fast initial solution
is iteratively optimized by destroying and repairing a fixed number of parts,
i.e., the neighborhood, of the solution, using randomized destroy heuristics
and prioritized planning. Despite their recent success in various MAPF
instances, current LNS-based approaches lack exploration and flexibility due to
greedy optimization with a fixed neighborhood size which can lead to low
quality solutions in general. So far, these limitations have been addressed
with extensive prior effort in tuning or offline machine learning beyond actual
planning. In this paper, we focus on online learning in LNS and propose
Bandit-based Adaptive LArge Neighborhood search Combined with Exploration
(BALANCE). BALANCE uses a bi-level multi-armed bandit scheme to adapt the
selection of destroy heuristics and neighborhood sizes on the fly during
search. We evaluate BALANCE on multiple maps from the MAPF benchmark set and
empirically demonstrate cost improvements of at least 50% compared to
state-of-the-art anytime MAPF in large-scale scenarios. We find that Thompson
Sampling performs particularly well compared to alternative multi-armed bandit
algorithms.
