Failure-Robust Multi-Robot Tasks Planning under Linear Temporal Logic Specifications

摘要

In this work, we investigate the problem of multi-robot planning for tasks specified by linear temporal logic (LTL) formulas. The objective is to synthesize a reactive plan for the team of robots such that a global LTL task is fulfilled while minimizing the satisfaction time. We consider the scenario where some robots may fail during the execution so that they cannot contribute to the satisfaction of the task. Specifically, we assume that there are at most k robot that may fail. An effective task planning algorithm is presented that guarantees the robust satisfaction of the task under the upper-bounded number of failure robots. Our approach is based on constructing a team transition system that can capture both asynchronous motion of robots and possible robot failures. Then by utilizing value-iteration algorithm over the product of the task automata and the team transition system, a reactive and optimal strategy is computed. We illustrate the proposed algorithm by multi-robot coordination in grid-world.