Solving the Multi-Agent Path Finding with Waypoints Problem Using Subdimensional Expansion

Solving the Multi-Agent Path Finding with Waypoints Problem Using Subdimensional Expansion

van Dijk, Jeroen (TU Delft Electrical Engineering, Mathematics and Computer Science)

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

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2020-06-22

Little to no research has been done on the multi-agent path finding with waypoints problem (MAPFW) even though it has many important real world applications. In this paper we extend an existing algorithm for the multi-agent path finding problem (MAPF) called M* \cite{New}. We do so by ordering the waypoints using a Travelling salesman problem solver before creating a policy for each waypoint and the target. Lastly we extend the underlying A* planner to keep track of the visited waypoints. This results in the new WM* algorithm which will be shown to be performing better than other recently created algorithms with respect to run-time while being optimal in the case of the ordered waypoint variant and near optimal in the unordered variant.

MAPFW
Pathfinding
M*
Subdimensional Expansion
Waypoints

http://resolver.tudelft.nl/uuid:603d2e05-b897-4242-823b-13881abdc670

Student theses

bachelor thesis

© 2020 Jeroen van Dijk