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

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

de Jong, Jaap (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Software Technology)

Mulderij, J. (mentor)
de Weerdt, M.M. (mentor)
Zuniga, Marco (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2021-07-01

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.

MAPF
Multi-Agent Pathfinding
epea-star
a-star
MAPFM

http://resolver.tudelft.nl/uuid:1ad692c0-dbda-4448-92ed-e928fc9cd74e

Student theses

bachelor thesis

© 2021 Jaap de Jong