Extending A* to solve multi-agent pathfinding problems with waypoints

Abstract

In the field of cooperative multi-agent pathfinding (MAPF) the optimal set of non-conflicting paths must be found for a set of agents in a graph. The addition of waypoints to this problem (MAPFW) gives rise to the possibility of more complex applications, such as in vehicle routing, aviation, computer games or robotics. Yet no algorithms have been proposed that can provide optimal solutions efficiently in practice. Starting with an established algorithm for multi-agent pathfinding, A* with operator decomposition and independence detection, this paper provides an extension to find optimal results when waypoints are present that the agents need to visit. This is achieved by altering the heuristic to make use of a solver of an adapted version of the traveling salesperson problem, to calculate the shortest path to visit all the waypoints for each agent individually. It is then empirically shown that this algorithm can solve problem instances of decent sizes, and it is compared to another algorithms that were developed at the same time based by others based on different pre-existing MAPF solvers. While the extension of A* is less performant than alternatives, the difference in performance can be small depending on the type of problem. Together with the relative ease of implementation, this means that A* can be an effective algorithm to optimally solve multi-agent pathfinding problems with waypoints. Additionally, the extension techniques used to adapt A* to MAPFW can also be useful to other algorithms that utilise A* in the context of waypoints.