Optimizing Node Selection in Search Based Multi-Agent Path Finding

Abstract A Multi-Agent Path Finding (MAPF) problem involves the task of finding paths for multiple agents who want to reach their destinations without obstructing other agents. Although MAPF is essential for numerous real-world applications, finding an optimal solution to this problem is NP-hard. Many approaches have been proposed in the literature, offering sub-optimal solutions to this problem to improve runtime efficiency. Lazy Constraints Addition search for MAPF (LaCAM) is a state-of-the-art sub-optimal MAPF algorithm that employs tree-based lazy successor generation to minimize planning effort. However, the success of the algorithm heavily relies on the effective selection of nodes for expansion. LaCAM employs a fixed heuristic throughout the entire search process, disregarding the agents' preferences or the characteristics of the underlying environment. Nevertheless, experiments with various heuristics indicate that no single heuristic consistently outperforms others across all scenarios. Consequently, in diverse environments, as the number of agents increases, reliance on a single, general heuristic leads to diminished runtime performance. Against this backdrop, with the intent to further speed up the runtime, we propose a novel approach, called eLaCAM, that adaptively selects nodes during the search process considering the current scenario of the environment and agents preferences. We introduce two distinct methods within this approach. The first, eLaCAM-stat, statistically analyses previous results of using different heuristics and selects nodes accordingly. The second method, eLaCAM-ML, employs a Machine Learning (ML) framework to assist in node selection. Our extensive empirical results depict a notable improvement in runtime and a reduction in the search space compared to state-of-the-art MAPF algorithms.