Analysis of the influence of graph characteristics on MAPFW algorithm performance

Title

Analysis of the influence of graph characteristics on MAPFW algorithm performance

 Author

Bestebreur, Timon (TU Delft Electrical Engineering, Mathematics and Computer Science)

Contributor

Mulderij, J. (mentor)
de Weerdt, M.M. (graduation committee) ORCID 0000-0002-0470-6241

 Degree granting institution

Delft University of Technology

 Programme

Computer Science and Engineering

 Project

CSE3000 Research Project

 Date

2020-06-22

 Abstract

The Multi-Agent Path Finding (MAPF) problem is a problem in which a route must be found for multiple agents such that they do not collide. The Multi-Agent PathFinding with Waypoints problem extends this problem by adding waypoints that the agents must visit before travelling to their end location. This paper compares five algorithms for MAPF that have been extended to incorporate waypoints. It also analyzes which influence map characteristics like corridors, chokepoints, overlapping waypoints and the average degree have on the performance of these algorithms. It concludes that EMLA and WM* perform best overall with some variations per characteristic.

 Subject

Multi-Agent Pathfinding
Waypoints
Graph Characteristics

 To reference this document use:

http://resolver.tudelft.nl/uuid:d602656e-4e27-4e36-8039-90497db5b905

 Part of collection

Student theses

 Document type

bachelor thesis

 Rights

© 2020 Timon Bestebreur
Files
PDF Analysis_of_the_influence ... rmance.pdf 679.61 KB
Close viewer