Print Email Facebook Twitter Multi-agent pathfinding with waypoints using Branch-Price-and-Cut Title Multi-agent pathfinding with waypoints using Branch-Price-and-Cut Author Michels, Andor (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-22 Abstract In the multi-agent pathfinding (MAPF) problem, agents have to traverse a graph to a goal location without running into each other. Currently, the Branch-and-Cut-and-Price-MAPF (BCP-MAPF) algorithm is the state-of-the-art algorithm for solving MAPF problems, which uses Branch-Price-and-Cut (BPC) to solve a linear minimization problem. The multi-agent pathfinding with waypoints (MAPFW) problem is a variation on the classical MAPF problem. MAPFW can be useful for e.g. navigating warehouses and scheduling trains. However, little to no research exists on MAPFW. This research proposes two extensions to the BCP-MAPF algorithm to incorporate waypoints and reviews their performance. Subject Multi-Agent PathfindingBranch-Price-and-CutInteger Linear Programming To reference this document use: http://resolver.tudelft.nl/uuid:d3deaccc-db8b-4fe0-8328-faaf4fa6b598 Part of collection Student theses Document type bachelor thesis Rights © 2020 Andor Michels Files PDF Andor_BCP_MAPFW_paper.pdf 295.04 KB Close viewer /islandora/object/uuid:d3deaccc-db8b-4fe0-8328-faaf4fa6b598/datastream/OBJ/view