Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search

Authors

  • Thomy Phan University of Southern California
  • Taoan Huang University of Southern California
  • Bistra Dilkina University of Southern California
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/aaai.v38i16.29701

Keywords:

MAS: Multiagent Planning, ROB: Motion and Path Planning, MAS: Coordination and Collaboration, SO: Heuristic Search

Abstract

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 performance 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.

Published

2024-03-24

How to Cite

Phan, T., Huang, T., Dilkina, B., & Koenig, S. (2024). Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search. Proceedings of the AAAI Conference on Artificial Intelligence, 38(16), 17514-17522. https://doi.org/10.1609/aaai.v38i16.29701

Issue

Section

AAAI Technical Track on Multiagent Systems