Solving the Colored Multi-Agent Path Finding with Waypoints Problem using SAT
J. van Dijk (TU Delft - Electrical Engineering, Mathematics and Computer Science)
M.M. de Weerdt – Mentor (TU Delft - Algorithmics)
E. Demirović – Mentor (TU Delft - Algorithmics)
J.T. van Essen – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.