Distributed Optimal Control Synthesis for Multi-Robot Systems under Global Temporal Tasks

Abstract

This paper proposes a distributed sampling-based algorithm for optimal multi-robot control synthesis under global Linear Temporal Logic (LTL) formulas. Existing planning approaches under global temporal goals rely on graph search techniques applied to a synchronous product automaton constructed among the robots. In our previous work, we have proposed a more tractable centralized sampling-based algorithm that builds incrementally trees that approximate the state-space and transitions of the synchronous product automaton and does not require sophisticated graph search techniques. In this work, we provide a distributed implementation of this sampling-based algorithm, whereby the robots collaborate to build subtrees that decreases the computational time significantly. We provide theoretical guarantees showing that the distributed algorithm preserves the probabilistic completeness and asymptotic optimality of its centralized counterpart. To the best of our knowledge, this is the first distributed, computationally efficient, probabilistically complete, and asymptotically optimal control synthesis algorithm for multi-robot systems under global temporal tasks.