TY - GEN
T1 - Distributed Optimal Control Synthesis for Multi-Robot Systems under Global Temporal Tasks
AU - Kantaros, Yiannis
AU - Zavlanos, Michael M.
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/8/21
Y1 - 2018/8/21
N2 - 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.
AB - 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.
KW - multi robot systems
KW - Optimal control synthesis
KW - temporal logic path planning
UR - https://www.scopus.com/pages/publications/85053503414
U2 - 10.1109/ICCPS.2018.00024
DO - 10.1109/ICCPS.2018.00024
M3 - Conference contribution
AN - SCOPUS:85053503414
SN - 9781538653012
T3 - Proceedings - 9th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2018
SP - 162
EP - 173
BT - Proceedings - 9th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 9th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2018
Y2 - 11 April 2018 through 13 April 2018
ER -