Presentation information

General Session

General Session » GS-5 Agents

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

Tue. Jun 14, 2022 10:00 AM - 11:40 AM Room N (Room 501)

座長:高野 諒(立命館大学)[遠隔]

10:40 AM - 11:00 AM

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

〇Koshi Shibata1, Kei Kimura1, Taiki Todo1, Makoto Yokoo1 (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.

Authentication for paper PDF access

A password is required to view paper PDFs. If you are a registered participant, please log on the site from Participant Log In.
You could view the PDF with entering the PDF viewing password bellow.