Extending the Multi-Label A* Algorithm for Multi-Agent Pathfinding with Multiple Waypoints

Abstract

Multi-Agent Pathfinding (MAPF) is a problem in which the goal is to plan paths for distinct agents while avoiding collisions between agents. We consider a new variation of MAPF, namely MAPF with multiple waypoints (MAPFW), where agents are required to visit a set of intermediary locations before visiting their end goal. MAPFW may have interesting applications, such as in the field of train scheduling and routing. To solve MAPFW problems we present the new algorithm Extended Multi-Label A* (EMLA*), which is based of the existing MLA* algorithm. Experimental evaluation shows that Heuristic-Based EMLA* (HB-EMLA*) for unordered MAPFW outperforms other algorithms when it comes to the number of agents and waypoints it is able to handle. However, HB-EMLA* struggles to find solutions to instances which are \textit{not well-formed}, as resting agents may block planning agents preventing a valid plan from being found. HB-EMLA* generally outperforms other algorithms when it comes to run time of larger instances. This comes at the cost of solution quality, where the solutions provided by EMLA* are 30\% worse than the best solution of the compared algorithms. Lastly, set benchmarks show that a simple \textit{Nearest Waypoint} heuristic generally outperforms other tested heuristics for HB-EMLA*.