Contingent Planning for Robust Multi-Agent Path Finding

Authors

  • Michal Nekvinda Charles University, Faculty of Mathematics and Physics
  • Roman Barták Charles University, Faculty of Mathematics and Physics
  • Meir Kalech Ben-Gurion University of the Negev

Keywords:

Problem Solving Using Search, Search In Robotics, Real-life Applications

Abstract

A classical approach to Multi-agent Path Finding assumes an offline construction of collision-free paths that the agents blindly follow during execution. k-robust plans can be executed without collisions even if an agent is delayed for at most k steps. In the paper, we propose a novel concept of robustness that uses alternative paths to which the agents are diverted in case of delay. Such plans can be found with much higher chances than k-robust plans.

Downloads

Published

2021-07-21