[1N1-GS-5] Agents: basic theory

[1N1-GS-5-03] An improved exact algorithm for multi-agent pathfinding problems

〇Koshi Shibata¹, Kei Kimura¹, Taiki Todo¹, Makoto Yokoo¹ (1. Kyushu University)

Keywords:multi-agent system, multi-agent pathfinding

The multi-agent pathfinding (MAPF) problem takes as input a set of agents with different starts and goals, and assigns a path that does not cause conflicts among the agents. There is a powerful exact algorithm called Meta-Agent Conflict Based Search (MA-CBS) for minimizing the sum of the costs for each agent to reach the goal, which is known to be NP-hard. The behavior of MA-CBS varies depending on a condition called the merge policy, but it is known that it requires a huge amount of execution time for some MAPF instances under the conventional static merge policy. In this paper, we propose a new merge policy that dynamically changes the properties of the algorithm, and show by computer experiments that the algorithm that implements the proposed merge policy runs efficiently on more various instances than the conventional one.