An improved exact algorithm for multi-agent pathfinding problems

DOI

Bibliographic Information

Other Title
  • マルチエージェント経路探索のための厳密アルゴリズムの改良
Published
2022
DOI
  • 10.11517/pjsai.jsai2022.0_1n1gs503
Publisher
The Japanese Society for Artificial Intelligence

Description

<p>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.</p>

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top