Multi-Agent Path Execution with Uncertainty

In real-world multi-agent applications, unexpected conditions can break the assumptions made in path planning and degrade the effectiveness of path execution. This paper studies robust and effective execution of multi-agent path plans under uncertainty. To guarantee conflict-freeness and deadlock-freeness, we define a feasibility problem to check whether the remaining portion of a path plan can be successfully executed. We prove that the problem is NP-complete and propose a feasibility test algorithm. We further develop algorithms to coordinate the agents online and have as many of them as possible moving concurrently to maximize the effectiveness of execution.