Matching in Multi-Agent Pathfinding using M*

Title

Matching in Multi-Agent Pathfinding using M*

 Author

Dönszelmann, Jonathan (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Intelligent Systems)

Contributor

Mulderij, J. (mentor)
de Weerdt, M.M. (mentor) ORCID 0000-0002-0470-6241
Zuniga, Marco (graduation committee) ORCID 0000-0003-3544-9169

 Degree granting institution

Delft University of Technology

 Programme

Computer Science and Engineering

 Project

CSE3000 Research Project

 Date

2021-07-01

 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.

 Subject

MAPF
MAPFM
Pathfinding
Algorithm
M*
matching

 To reference this document use:

http://resolver.tudelft.nl/uuid:a98cc32e-9d10-41a3-8fc3-c840f1a8654d

 Part of collection

Student theses

 Document type

bachelor thesis

 Rights

© 2021 Jonathan Dönszelmann
Files
PDF Research_Project_CSE3000.pdf 693.07 KB
Close viewer