Adaptive Neighborhood Selection for MAPF via Non-Stationary Bandits

Abstract

Adaptive Large Neighborhood Search (ALNS) is a meta-heuristic framework widely used to solve large-scale MAPF problems. It uses selection mechanisms such as the Roulette Wheel or Multi-Armed Bandit (MAB) policies, which adaptively learn to identify the most effective neighborhood (heuristic) at each iteration. A key assumption of these policies is that each heuristic’s reward distribution (effectiveness) is stationary. However, the best heuristic can change during the search process. In this work, we address the inherent non-stationarity of neighborhood selection in ALNS-based MAPF solvers, where the reward distribution of the heuristic changes over time. We introduce DyMAB (Dynamic multi-armed bandit for neighborhood selection), a novel anytime algorithm that integrates a non-stationary multi-armed bandit (MAB) framework into ALNS. DyMAB leverages a windowed queue to track recent rewards, allowing for dynamic adaptation of neighborhood selection at each iteration. This ensures that the most effective heuristic is prioritized, improving overall search efficiency. We present a theoretical analysis showing that DyMAB achieves sub-linear regret under standard non-stationary bandit assumptions, offering formal performance guarantees. We benchmark DyMAB against a range of state-of-the-art anytime solvers across diverse MAPF scenarios, demonstrating that our method significantly enhances solution quality and scalability. In most cases, DyMAB achieves up to a 50% reduction in AUC and up to a 30% decrease in the Sum of Delays, highlighting its superiority in optimizing large-scale MAPF instances.