Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic
<|reference_start|>Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic: 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.<|reference_end|>
@article{phan2024anytime,
    title={Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic},
    author={Thomy Phan, Benran Zhang, Shao-Hung Chan, Sven Koenig},
    journal={arXiv preprint arXiv:2408.02960},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.02960},
    primaryClass={cs.AI}
}