Multi-Agent Pathfinding with Matching using Increasing Cost Tree Search
T.B. van der Woude (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Jesse Mulderij – Mentor (TU Delft - Algorithmics)
Mathijs M. de de Weerdt – Mentor (TU Delft - Algorithmics)
M Zuñiga Zamalloa – Graduation committee member (TU Delft - Embedded Systems)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Both the assignment problem and the multi-agent pathfinding problem are common problems in the fields of robotics and transportation. The joint problem of multi-agent pathfinding extended with the assignment of goals to agents, matching, is something that has not been studied much; few methods exist today that solve it. In this work, two types of algorithms based on the Increasing Cost Tree Search (ICTS) algorithm for multi-agent pathfinding are presented that can optimally solve this joint problem: exhaustive algorithms that reduce the problem to solving many multi-agent pathfinding problems using regular ICTS, and algorithms that search a generalized increasing cost tree. These are compared to each other experimentally on a set of grid maps, and it is shown that exhaustive methods typically outperform the generalized ICTS. Lastly, an exhaustive ICTS algorithm is compared to alternative algorithms based on other multi-agent pathfinding approaches to put its performance into the broader context of algorithms for multi-agent pathfinding with matching.