Authors:
Jiří Švancara
1
;
David Zahrádka
2
;
3
;
Mrinalini Subramanian
1
;
Roman Barták
1
and
Miroslav Kulich
3
Affiliations:
1
Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
;
2
Dept. of Cybernetics, Faculty of Electrical Engineering, Czech Technical University in Prague, Prague, Czech Republic
;
3
Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Prague, Czech Republic
Keyword(s):
Multi-Agent Path Finding, Temporal Uncertainty, Policy, SAT.
Abstract:
Multi-Agent path finding (MAPF) deals with the problem of finding collision-free paths for a group of mobile agents moving in a shared environment. In practice, the duration of individual move actions may not be exact but rather spans in a given range. Such extension of the MAPF problem is called MAPF with Temporal Uncertainty (MAPF-TU). In this paper, we propose a compilation-based approach to generate safe agents’ policies solving the MAPF-TU problem. The policy guarantees that each agent reaches its destination without collision with other agents provided that all agents move within their predefined temporal uncertainty range. We show both theoretically and empirically that using policies rather than plans is guaranteed to solve more types of instances and find a better solution.
