Solving the Multi-Agent Path Finding with Waypoints Problem Using Subdimensional Expansion
J. van Dijk (TU Delft - Electrical Engineering, Mathematics and Computer Science)
M.M. Weerdt (TU Delft - Algorithmics)
More Info
expand_more
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.
Abstract
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.