Control of stochastic discrete event systems modeled by probabilistic languages

From MaRDI portal





A special case of ``probabilistic supervision, previously studied by \textit{P. J. Ramadge} and \textit{W. M. Wonham} [SIAM J. Control Optimization 25, 206--230 (1987; Zbl 0618.93033)], of discrete-event systems is considered. It uses the formalism of probabilistic languages introduced by \textit{V. K. Garg}, \textit{R. Kumar} and \textit{S. I. Marcus} [IEEE Trans. Autom. Control 44, No. 2, 280--293 (1999; Zbl 0957.68055)]. Let \(\Sigma\), \(\Sigma^*\) denote the universe of events and the set of all finite-length traces of events, respectively. A probabilistic language (\(p\)-language) assigns to every trace \(s \in \Sigma^*\) a probability \(L(s)\) that satisfies the following conditions: i) \(0 \leq L(s) \leq 1\), ii) \(\sum_{\sigma \in \Sigma} L(\sigma) \leq 1\), and iii) \(\sum_{\sigma \in \Sigma} L(s\sigma) \leq L(s)\), where \(s\sigma\) is a concatenation of the trace \(s\) and the event \(\sigma\). Accordingly, a nonprobabilistic language (\(np\)-language) can be described by the condition \(L(s):L(s) \to \{0,1\}\) or equivalently by a set of legal traces \(\{s:L(s)=1\}\). For two \(p\)-languages \(K\), \(L\) the partial order \(K \preceq L\) is defined by the condition \(K(s) \leq L(s)\), \(\forall s \in \Sigma^*\). In the problem, a plant described by a \(p\)-language \(L\) is given. A supervisor \(S\) observes traces of \(L\) and dynamically disables certain controllable events. The goal of the supervision is to provide a restriction \(K \preceq L^S \preceq D\) where \(L^S\) is the \(p\)-language of the controlled plant, \(D\) is the \(np\)-language of legal traces, and \(K\) is a \(p\)-language describing desirable minimal probabilities of legal traces. The supervisor is proved to exist if and only if the infimal controllable superlanguage of \(K\) [see \textit{S. Lafortune} and \textit{E. Chen}, IEEE Trans. Autom. Control 35, No. 4, 398--405 (1990; Zbl 0709.68028)] is bounded above by the supremal controllable sublanguage of \(D\) [see \textit{P. J. Ramadge} and \textit{W. M. Wonham}, Proceedings of the IEEE 77, 81--98 (1989)]. If \(L\), \(K\), \(D\) allow finite-state automata representations, i.e. \(L\), \(K\), \(D\) are regular languages, then an effective algorithm checking the condition \(K \preceq L^S \preceq D\) is given. Its complexity is \(O(n^3)\), where \(n\) is the product of the number of states in the automata representations of \(K\), \(D\). At last, a solution to the problem of minimally permissive and maximally permissive supervisors in the considered setting is given.











This page was built for publication: Control of stochastic discrete event systems modeled by probabilistic languages

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