Print Email Facebook Twitter Extending the Multi-Label A* Algorithm for Multi-Agent Pathfinding with Multiple Waypoints Title Extending the Multi-Label A* Algorithm for Multi-Agent Pathfinding with Multiple Waypoints Author Ferwerda, Arjen (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Mulderij, J. (mentor) de Weerdt, M.M. (mentor) Degree granting institution Delft University of Technology Programme Computer Science and Engineering Project CSE3000 Research Project Date 2020-06-21 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*. Subject MAPFMAPFWMulti-Agent Pathfindingwaypoints To reference this document use: http://resolver.tudelft.nl/uuid:d744eab0-1884-424e-978a-15a08cbaeff8 Part of collection Student theses Document type bachelor thesis Rights © 2020 Arjen Ferwerda Files PDF Extending_MLA.pdf 959.67 KB Close viewer /islandora/object/uuid:d744eab0-1884-424e-978a-15a08cbaeff8/datastream/OBJ/view