Multi-Agent Pathfinding with Matching using Enhanced Partial Expansion A*

Bachelor thesis (2021)

Authors

J. de Jong Electrical Engineering, Mathematics and Computer Science

Contributors

J. Mulderij Algorithmics - EEMCS (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 Jaap de Jong
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

For the Multi-Agent Pathfinding (MAPF) problem, a set of non-colliding paths must be found for multiple agents. In Multi-Agent Pathfinding with Matching (MAPFM), this problem is extended: agents and goals are added to a team and each agent has to navigate to a goal that belongs to the same team. In this paper, two extensions of the EPEA* MAPF solver will be discussed that enable it to solve MAPFM problems. The first extension modifies the EPEA* algorithm to directly allow it to solve MAPFM problem instances. The second extension generates all possible goal assignments for each agent and runs EPEA* on these assignments. This last extension is shown to have a superior performance in most cases. The second extension is also compared to extensions of other MAPF algorithms.