Jv
J. van Dijk
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
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.
...
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.
Little to no research has been done on the multi-agent path finding with waypoints problem (MAPFW) even though it has many important real world applications. In this paper we extend an existing algorithm for the multi-agent path finding problem (MAPF) called M* \cite{New}. We do so by ordering the waypoints using a Travelling salesman problem solver before creating a policy for each waypoint and the target. Lastly we extend the underlying A* planner to keep track of the visited waypoints. This results in the new WM* algorithm which will be shown to be performing better than other recently created algorithms with respect to run-time while being optimal in the case of the ordered waypoint variant and near optimal in the unordered variant.
...
Little to no research has been done on the multi-agent path finding with waypoints problem (MAPFW) even though it has many important real world applications. In this paper we extend an existing algorithm for the multi-agent path finding problem (MAPF) called M* \cite{New}. We do so by ordering the waypoints using a Travelling salesman problem solver before creating a policy for each waypoint and the target. Lastly we extend the underlying A* planner to keep track of the visited waypoints. This results in the new WM* algorithm which will be shown to be performing better than other recently created algorithms with respect to run-time while being optimal in the case of the ordered waypoint variant and near optimal in the unordered variant.