Global Planning and Local Update for Multi-Size Agents Path Finding

Abstract

In this letter, we study the Multi-Size Agent Path Finding (MSAPF) problem, which is a generalization of the Multi-Agent Path Finding (MAPF) problem and has a wider range of practical applications in intelligent transportation. Compared to the well-known MAPF problem in which each agent only occupies one grid, multi-size agents in MSAPF have different sizes and may occupy multiple grids. Different sizes result in two bottlenecks in finding conflict-free paths. One is that conflicts between the shortest paths of multi-size agents are difficult to resolve, and the other is that numerous new conflicts are likely to occur when resolving one conflict. Existing MAPF algorithms are inefficient in solving MSAPF because they only consider conflicts involving a single grid or between adjacent grids, and few works focus on solving these bottlenecks of MSAPF. To solve MSAPF, we propose a novel and complete algorithm named Global Planning and Local Update (GPLU), which is a two-level algorithm and can efficiently find conflict-free paths for multi-size agents. GPLU is an unbounded sub-optimal algorithm that cannot find the optimal solution. However, we prove that GPLU is complete, which means that GPLU can return solutions for solvable MSAPF instances if such solutions exist. To improve the efficiency of GPLU, we propose two optimization strategies. The former improves efficiency while ensuring completeness, and the latter reduces the time complexity of GPLU to polynomial time. Extensive experiments conducted on a popular benchmark show that our proposed algorithms can support <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$20\%\sim 116.67\%$</tex-math></inline-formula> more multi-size agents than existing MAPF/MSAPF algorithms.