Jiaqi Tan, Yudong Luo, Jiaoyang Li, Hang Ma

Reevaluation of Large Neighborhood Search for MAPF: Findings and Opportunities

Introduction

Reevaluation of large neighborhood search for mapf: findings and opportunities. Reevaluating Large Neighborhood Search (LNS) for MAPF. We introduce a unified evaluation framework, finding rule-based heuristics outperform current ML methods. Discover new research opportunities.

Abstract

Multi-Agent Path Finding (MAPF) aims to arrange collision-free goal-reaching paths for a group of agents. Anytime MAPF solvers based on large neighborhood search (LNS) have gained prominence recently due to their flexibility and scalability, leading to a surge of methods, especially those leveraging machine learning, to enhance neighborhood selection. However, several pitfalls exist and hinder a comprehensive evaluation of these new methods, which mainly include: 1) Lower than actual or incorrect baseline performance; 2) Lack of a unified evaluation setting and criterion; 3) Lack of a codebase or executable model for supervised learning methods. To address these challenges, we introduce a unified evaluation framework, implement prior methods, and conduct an extensive comparison of prominent methods. Our evaluation reveals that rule-based heuristics serve as strong baselines, while current learning-based methods show no clear advantage on time efficiency or improvement capacity. Our extensive analysis also opens up new research opportunities for improving MAPF-LNS, such as targeting high-delayed agents, applying contextual algorithms, optimizing replan order and neighborhood size, where machine learning can potentially be integrated.

Review

This paper presents a timely and critical reevaluation of Large Neighborhood Search (LNS) approaches for Multi-Agent Path Finding (MAPF). The authors aptly highlight the growing prominence of LNS-based anytime MAPF solvers due to their inherent flexibility and scalability, which has spurred a significant interest, particularly in methods leveraging machine learning for enhanced neighborhood selection. However, the work identifies several crucial pitfalls hindering a comprehensive and fair evaluation of these new techniques. These include inaccurate or understated baseline performance, a lack of standardized evaluation settings and criteria, and the absence of publicly available codebases or executable models for supervised learning methods, collectively making it difficult to assess true progress in the field. To address these significant challenges, the authors introduce a unified evaluation framework, meticulously implement and reproduce prior methods, and conduct an extensive comparative analysis of prominent techniques. The findings are particularly insightful and potentially paradigm-shifting: their rigorous evaluation demonstrates that traditional rule-based heuristics serve as remarkably strong baselines. More surprisingly, the study concludes that current learning-based methods, despite their recent proliferation, do not exhibit a clear advantage in terms of either time efficiency or overall improvement capacity when compared against these robust baselines under a unified evaluation. Beyond critically assessing existing work, the paper proactively opens up new and promising research avenues for enhancing MAPF-LNS. Opportunities include strategies for targeting high-delayed agents, applying contextual algorithms to adapt search behavior, and optimizing crucial parameters such as replan order and neighborhood size. Crucially, the authors suggest that these identified opportunities represent areas where machine learning could be more effectively and strategically integrated to yield genuine performance improvements. This reevaluation provides an invaluable service to the MAPF community by setting a new standard for rigorous benchmarking and offering clear directions for future, impactful research.

Full Text

Comments

You need to be logged in to post a comment.