Low-Level Planner on Conflict-Based Search Efficiency in Multi-Agent Path Finding

Read full text Summarise with VIRAT
Authors: Marco Ricci, Riccardo Accorsi, Ilaria Battarra, Giacomo Lupi, Riccardo Manzini
Cited by: 0
References: 15

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Research on MAPF has primarily focused on high-level planners and on the comparisons of alternative algorithms in heterogeneous settings, while the role of low-level planners has received little attention. These components are essential for generating agent paths under high-level constraints, and their proper selection can significantly affect performance. This work addresses this gap by comparing four A*-based variants (Uniform Cost Search (UCS), standard A*, Weighted A*, and Adaptive Weighted A*) within the CBS framework. The comparison is carried out through a multi-scenario analysis with varying agent densities and obstacle configurations in grid-based environments. The evaluation includes computational efficiency, conflict resolution capability, and path quality. Results indicate that while weighted planners reduce runtime and node expansions, they generate more conflicts in complex scenarios. Adaptive Weighted A* proves effective overall performance in the empty grid environment, combining high success rates, low computational effort, and moderate conflict levels, even as the number of agents grows. In contrast, in the case of random obstacles, the best performance is achieved by 1.5wA*, although overall planner performances become more comparable, except for UCS, which performs significantly worse. These findings provide actionable insights into the trade-offs involved in low-level planner selection for CBS and pave the way to its application in operational time-based logistic environments.

Fields of Study & Subjects

Robotic Path Planning Algorithms Evacuation and Crowd Dynamics AI-based Problem Solving and Planning

Publication details

Journal / source
Procedia Computer Science
Volume
277
Pages
2125–2134
Publication date
1 January 2026
Language
EN