Exact Computation of Maximal Invariant Sets for Safe Markov Chains-Lattice Theoretic Approach

• 成果类型: Article
• 署名作者: Janak, Dylan; Garoche, Pierre-Loic; Acikmese, Behcet
• 署名单位: University of Washington; University of Washington Seattle; Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Ecole Nationale de l'Aviation Civile (ENAC)
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3211959
• 发表日期: 2022
• 页码: 6980-6986
• 关键词: Control system synthesis; decentralized control; dynamical systems; Directed graphs; Eigenvalues and eigenfunctions; Limit-cycles; Linear matrix inequalities; Linear systems

摘要

Set theoretic analysis plays a crucial part in understanding safety requirements for control systems. We apply the lattice theoretic insights of fixed point theorems to construct the maximal invariant set and verify safety constraint satisfaction. We present a Kleene iteration-based algorithm with a novel initialization-based on omega-limit sets-for exactly computing the maximal invariant set under a general safety constraint, and we analyze this algorithm for the special case of Markov chains under polyhedral safety constraints. We also establish sufficient conditions for finite termination of the for a general discrete-time system, which is applicable to Markov chains. In addition to proving that the new initialization of the Kleene iteration algorithm requires no more iterations than the previously considered initialization, we present an example where our method computes the exact maximal invariant set in finitely many iterations and the previous method does not.