Matching in Multi-Agent Pathfinding using M*

Bachelor thesis (2021)

Authors

J.B. Dönszelmann Electrical Engineering, Mathematics and Computer Science

Contributors

J. Mulderij Electrical Engineering, Mathematics and Computer Science (mentor)
M.M. de Weerdt Algorithmics - EEMCS (mentor)
Marco Zuniga Embedded Systems - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2021 Jonathan Dönszelmann
More Info
expand_more

Published Date

01-07-2021

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

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.