Print Email Facebook Twitter Solving Multi-Agent Pathfinding with Matching using A*+ID+OD Title Solving Multi-Agent Pathfinding with Matching using A*+ID+OD Author de Bruin, Ivar (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Software Technology) Contributor Mulderij, J. (mentor) de Weerdt, M.M. (mentor) Zuniga, Marco (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science and Engineering Project CSE3000 Research Project Date 2021-07-01 Abstract This paper extends the Multi-Agent Pathfinding (MAPF) algorithm, A*+ID+OD, to be able to solve problems with matching. This extension still keeps the optimal and completeness properties of the original algorithm. Matching is added to the algorithm in both an exhaustive and heuristic manner. Exhaustive matching is further improved by adding a new layer of Independence Detection (ID) to reduce the number of matchings. Besides this, the pruning efficiency is increased by sorting the matchings based on the initial heuristic. The exhaustive matching method has been found to perform better than the heuristic matching method. The exhaustive version of A*+ID+OD is finally compared to other extended MAPF algorithms which shows that on small maps, Conflict Based Min-Cost Flow (CBM) performs best as it is the only algorithm that does not use exhaustive matching. A*+ID+OD and Enhanced Partial Expansion A* (EPEA*) also perform well on open maps with multiple teams when compared to other exhaustive matching algorithms due to the addition of matching ID. Subject MAPFMAPFMMulti-Agent PathfindingMatchinga-star To reference this document use: http://resolver.tudelft.nl/uuid:8da2b89a-7bed-4459-b468-917b1003e136 Part of collection Student theses Document type bachelor thesis Rights © 2021 Ivar de Bruin Files PDF Solving_Multi_Agent_Pathf ... _ID_OD.pdf 561.59 KB Close viewer /islandora/object/uuid:8da2b89a-7bed-4459-b468-917b1003e136/datastream/OBJ/view