Compositional (In)Finite Abstractions for Large-Scale Interconnected Stochastic Systems

• Published in: IEEE transactions on automatic control 2020-12, Vol.65 (12), p.5280-5295
• Main Authors: Lavaei, Abolfazl, Soudjani, Sadegh, Zamani, Majid
• Format: Article
• Language: English
• Subjects: Compositionality; Control systems; Control systems design; Discrete time systems; finite Markov decision processes; formal synthesis; infinite abstractions; interconnected discrete-time stochastic control systems; Interconnected systems; Markov processes; Nonlinear control; Optimal control; Probabilistic logic; Reduced order models; Reduced order systems; small-gain conditions; Stochastic processes; Stochastic systems; Subsystems
• ISSN: 0018-9286; 1558-2523
• DOI: 10.1109/TAC.2020.2975812

This article is concerned with a compositional approach for constructing both infinite (reduced-order models) and finite abstractions [a.k.a. finite Markov decision processes (MDPs)] of large-scale interconnected discrete-time stochastic systems. The proposed framework is based on the notion of stochastic simulation functions enabling us to employ an abstract system as a substitution of the original one in the controller design process with guaranteed error bounds. In the first part of this article, we derive sufficient small-gain-type conditions for the compositional quantification of the probabilistic distance between the interconnection of stochastic control subsystems and that of their infinite abstractions. We then construct infinite abstractions together with their corresponding stochastic simulation functions for a particular class of discrete-time nonlinear stochastic control systems. In the second part of this article, we leverage small-gain-type conditions for the compositional construction of finite abstractions. We propose an approach to construct finite MDPs as finite abstractions of concrete models or their reduced-order versions satisfying an incremental input-to-state stability property. We also show that for the particular class of nonlinear stochastic control systems, the aforementioned property can be readily checked by matrix inequalities. We demonstrate the effectiveness of the proposed results by applying our approaches to a fully interconnected network of 20 nonlinear subsystems (totally 100 dimensions). We construct finite MDPs from their reduced-order versions (together 20 dimensions) with guaranteed error bounds on their output trajectories. We also apply the proposed results to a temperature regulation in a circular building and construct compositionally a finite abstraction of a network containing 1000 rooms. We employ the constructed finite abstractions as substitutes to compositionally synthesize policies regulating the temperature in each room for a bounded time horizon.