Print Email Facebook Twitter Solving the Colored Multi-Agent Path Finding with Waypoints Problem using SAT Title Solving the Colored Multi-Agent Path Finding with Waypoints Problem using SAT Author van Dijk, Jeroen (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor de Weerdt, M.M. (mentor) Demirović, E. (mentor) van Essen, J.T. (graduation committee) Degree granting institution Delft University of Technology Date 2022-10-14 Abstract The Multi-Agent Path Finding (MAPF) problem is the problem of planning paths for multiple agents without any collisions. There are also many variants such as the waypoint variant, where each agent also has a set of waypoints it must visit before reaching its goal. The colored variant, in which the agents are grouped into teams and each team has a set of targets that need to be reached. And the colored MAPFW variant is a combination of the two. This paper presents an SAT-solver for the sum-of-costs objective for these variants based on the sum-of-costs SAT solver for MAPF. It also introduces a MaxSAT solver for the makespan objective while also minimizing the sum-of-costs, where instead of having a cardinality constraint on the cost it is minimized. Experimental evaluation showed that these methods perform well on different graph types compared to existing algorithms and that MaxSAT solves more instances than SAT but is only optimal in 90\% of the instances. Subject MAPFSATPathfindingMAPFWMAPFM To reference this document use: http://resolver.tudelft.nl/uuid:6dd249d6-0393-497c-bf51-ea0c0c94daba Part of collection Student theses Document type master thesis Rights © 2022 Jeroen van Dijk Files PDF Thesis_Jeroen_Final.pdf 2.81 MB Close viewer /islandora/object/uuid:6dd249d6-0393-497c-bf51-ea0c0c94daba/datastream/OBJ/view