Safe Multi-Agent Pathfinding with Time Uncertainty

• Published in: The Journal of artificial intelligence research 2021-01, Vol.70, p.923
• Main Authors: Shahar, Tomer, Shekhar, Shashank, Atzmon, Dor, Saffidine, Abdallah, Juba, Brendan, Stern, Roni
• Format: Article
• Language: English
• Subjects: Agents (artificial intelligence); Algorithms; Artificial intelligence; Collisions; Context; Lower bounds; Multiagent systems; Uncertainty
• ISSN: 1076-9757; 1076-9757; 1943-5037
• DOI: 10.1613/jair.1.12397

In many real-world scenarios, the time it takes for a mobile agent, e.g., a robot, to move from one location to another may vary due to exogenous events and be difficult to predict accurately. Planning in such scenarios is challenging, especially in the context of Multi-Agent Pathfinding (MAPF), where the goal is to find paths to multiple agents and temporal coordination is necessary to avoid collisions. In this work, we consider a MAPF problem with this form of time uncertainty, where we are only given upper and lower bounds on the time it takes each agent to move. The objective is to find a safe solution, which is a solution that can be executed by all agents and is guaranteed to avoid collisions. We propose two complete and optimal algorithms for finding safe solutions based on well-known MAPF algorithms, namely, A* with Operator Decomposition (A* + OD) and Conflict-Based Search (CBS). Experimentally, we observe that on several standard MAPF grids the CBS-based algorithm performs better. We also explore the option of online replanning in this context, i.e., modifying the agents' plans during execution, to reduce the overall execution cost. We consider two online settings: (a) when an agent can sense the current time and its current location, and (b) when the agents can also communicate seamlessly during execution. For each setting, we propose a replanning algorithm and analyze its behavior theoretically and empirically. Our experimental evaluation confirms that indeed online replanning in both settings can significantly reduce solution cost.