Probabilistic Control of Heterogeneous Swarms Subject to Graph Temporal Logic Specifications: A Decentralized and Scalable Approach

DOI10.1109/TAC.2022.3176797MaRDI QIDQ6053263zbMATH OpenOpenAlexFDO

Authors Zhe Xu, Murat Cubuktepe, Ufuk Topcu

Publication date 26 September 2023

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.15729

zbMATH Keywords

formal languageMarkov processoptimization methodsswarm robotics

Mathematics Subject Classification ID

Systems theory; control (93-XX)

Abstract: We develop a probabilistic control algorithm, $extttGTLProCo$, for swarms of agents with heterogeneous dynamics and objectives, subject to high-level task specifications. The resulting algorithm not only achieves decentralized control of the swarm but also significantly improves scalability over state-of-the-art existing algorithms. Specifically, we study a setting in which the agents move along the nodes of a graph, and the high-level task specifications for the swarm are expressed in a recently-proposed language called graph temporal logic (GTL). By constraining the distribution of the swarm over the nodes of the graph, GTL can specify a wide range of properties, including safety, progress, and response. $extttGTLProCo$, agnostic to the number of agents comprising the swarm, controls the density distribution of the swarm in a decentralized and probabilistic manner. To this end, it synthesizes a time-varying Markov chain modeling the time evolution of the density distribution under the GTL constraints. We first identify a subset of GTL, namely reach-avoid specifications, for which we can reduce the synthesis of such a Markov chain to either linear or semi-definite programs. Then, in the general case, we formulate the synthesis of the Markov chain as a mixed-integer nonlinear program (MINLP). We exploit the structure of the problem to provide an efficient sequential mixed-integer linear programming scheme with trust regions to solve the MINLP. We empirically demonstrate that our sequential scheme is at least three orders of magnitude faster than off-the-shelf MINLP solvers and illustrate the effectiveness of $extttGTLProCo$ in several swarm scenarios.

Recommendations

• Decentralized control of multi-agent systems for swarming with a given geometric pattern
• Consensus problems of high-order swarm systems over random topologies with time-varying probability
• Decentralized coordination of autonomous swarms using parallel Gibbs sampling
• Distributed control for spatial self-organization of multi-agent swarms
• Swarming movement of dynamical multi-agent systems with sampling control and time delays
• Markov chain approach to probabilistic guidance for swarms of autonomous agents
• A swarm-based approach to dynamic coverage control of multi-agent systems

Cited in

(2)

• Safe Metropolis-Hastings algorithm and its application to swarm control
• Markov chain approach to probabilistic guidance for swarms of autonomous agents

This page was built for publication: Probabilistic Control of Heterogeneous Swarms Subject to Graph Temporal Logic Specifications: A Decentralized and Scalable Approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6053263)