Matching in Multi-Agent Pathfinding using M*
J.B. Dönszelmann (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J. Mulderij – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
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
Multi-agent pathfinding (MAPF) is the process of finding collision-free paths for multiple agents. MAPF can be extended by grouping agents into teams. In a team, agents need to be assigned (or matched) to one of the team's goals such that the sum of individual cost} is minimised. This extension is called MAPF with matching (MAPFM). M* is a complete and optimal algorithm to solve MAPF problems. In this paper, two strategies are proposed which allow M* to solve MAPFM problems. These strategies are called inmatching and prematching. It is shown that prematching is generally preferable to inmatching, the benefits of different optimisations for M* are compared, and it is shown that the performance of M* performs very comparably to other A*-derived algorithms.