Temporal Logic Trees for Model Checking and Control Synthesis of Uncertain Discrete-Time Systems

• 成果类型: Article
• 署名作者: Gao, Yulong; Abate, Alessandro; Jiang, Frank J.; Giacobbe, Mirco; Xie, Lihua; Johansson, Karl Henrik
• 署名单位: Royal Institute of Technology; Nanyang Technological University; University of Oxford; University of Birmingham
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3118335
• 发表日期: 2022
• 页码: 5071-5086
• 关键词: Model checking; reachability analysis; control systems; Automata; Linear systems; uncertainty; trajectory; Control synthesis; linear temporal logic; model checking; temporal logic trees

摘要

We propose algorithms for performing model checking and control synthesis for discrete-time uncertain systems under linear temporal logic (LTL) specifications. We construct temporal logic trees (TLTs) from LTL formulae via reachability analysis. In contrast to automaton-based methods, the construction of the TLT is abstraction-free for infinite systems; that is, we do not construct discrete abstractions of the infinite systems. Moreover, for a given transition system and an LTL formula, we prove that there exist both a universal TLT and an existential TLT via minimal and maximal reachability analysis, respectively. We show that the universal TLT is an underapproximation for the LTL formula and the existential TLT is an overapproximation. We provide sufficient conditions and necessary conditions to verify whether a transition system satisfies an LTL formula by using the TLT approximations. As a major contribution of this work, for a controlled transition system and an LTL formula, we prove that a controlled TLT can be constructed from the LTL formula via a control-dependent reachability analysis. Based on the controlled TLT, we design an online control synthesis algorithm, under which a set of feasible control inputs can be generated at each time step. We also prove that this algorithm is recursively feasible. We illustrate the proposed methods for both finite and infinite systems and highlight the generality and online scalability with two simulated examples.