JM
J. Mulderij
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
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.
In the field of cooperative multi-agent pathfinding (MAPF) the optimal set of non-conflicting paths must be found for a set of agents in a graph. The addition of waypoints to this problem (MAPFW) gives rise to the possibility of more complex applications, such as in vehicle routing, aviation, computer games or robotics. Yet no algorithms have been proposed that can provide optimal solutions efficiently in practice. Starting with an established algorithm for multi-agent pathfinding, A* with operator decomposition and independence detection, this paper provides an extension to find optimal results when waypoints are present that the agents need to visit. This is achieved by altering the heuristic to make use of a solver of an adapted version of the traveling salesperson problem, to calculate the shortest path to visit all the waypoints for each agent individually. It is then empirically shown that this algorithm can solve problem instances of decent sizes, and it is compared to another algorithms that were developed at the same time based by others based on different pre-existing MAPF solvers. While the extension of A* is less performant than alternatives, the difference in performance can be small depending on the type of problem. Together with the relative ease of implementation, this means that A* can be an effective algorithm to optimally solve multi-agent pathfinding problems with waypoints. Additionally, the extension techniques used to adapt A* to MAPFW can also be useful to other algorithms that utilise A* in the context of waypoints.
...
In the field of cooperative multi-agent pathfinding (MAPF) the optimal set of non-conflicting paths must be found for a set of agents in a graph. The addition of waypoints to this problem (MAPFW) gives rise to the possibility of more complex applications, such as in vehicle routing, aviation, computer games or robotics. Yet no algorithms have been proposed that can provide optimal solutions efficiently in practice. Starting with an established algorithm for multi-agent pathfinding, A* with operator decomposition and independence detection, this paper provides an extension to find optimal results when waypoints are present that the agents need to visit. This is achieved by altering the heuristic to make use of a solver of an adapted version of the traveling salesperson problem, to calculate the shortest path to visit all the waypoints for each agent individually. It is then empirically shown that this algorithm can solve problem instances of decent sizes, and it is compared to another algorithms that were developed at the same time based by others based on different pre-existing MAPF solvers. While the extension of A* is less performant than alternatives, the difference in performance can be small depending on the type of problem. Together with the relative ease of implementation, this means that A* can be an effective algorithm to optimally solve multi-agent pathfinding problems with waypoints. Additionally, the extension techniques used to adapt A* to MAPFW can also be useful to other algorithms that utilise A* in the context of waypoints.