  Anytime multi-agent path finding (MAPF) is a promising approach to scalable
path optimization in multi-agent systems. MAPF-LNS, based on Large Neighborhood
Search (LNS), is the current state-of-the-art approach where a fast initial
solution is iteratively optimized by destroying and repairing selected paths of
the solution. Current MAPF-LNS variants commonly use an adaptive selection
mechanism to choose among multiple destroy heuristics. However, to determine
promising destroy heuristics, MAPF-LNS requires a considerable amount of
exploration time. As common destroy heuristics are non-adaptive, any
performance bottleneck caused by these heuristics cannot be overcome via
adaptive heuristic selection alone, thus limiting the overall effectiveness of
MAPF-LNS in terms of solution cost. In this paper, we propose Adaptive
Delay-based Destroy-and-Repair Enhanced with Success-based Self-Learning
(ADDRESS) as a single-destroy-heuristic variant of MAPF-LNS. ADDRESS applies
restricted Thompson Sampling to the top-K set of the most delayed agents to
select a seed agent for adaptive LNS neighborhood generation. We evaluate
ADDRESS in multiple maps from the MAPF benchmark set and demonstrate cost
improvements by at least 50% in large-scale scenarios with up to a thousand
agents, compared with the original MAPF-LNS and other state-of-the-art methods.
