kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Temporal Logic Trees for Model Checking and Control Synthesis of Uncertain Discrete-time Systems
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control).ORCID iD: 0000-0003-2338-5487
Department of Computer Science, University of Oxford, Oxford, United Kingdom.
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control).
Department of Computer Science, University of Oxford, Oxford, United Kingdom.
Show others and affiliations
2022 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 67, no 10, p. 5071-5086Article in journal (Refereed) Published
Abstract [en]

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 (TLT) 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 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.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE) , 2022. Vol. 67, no 10, p. 5071-5086
Keywords [en]
Automata, Control systems, Linear systems, Model checking, Reachability analysis, Trajectory, Uncertainty, Abstracting, Computer circuits, Control system synthesis, Digital control systems, Discrete time control systems, Forestry, Online systems, Trees (mathematics), Uncertainty analysis, Automaton, Control synthesis, Infinite system, Linear temporal logic, Logic tree, Models checking, Temporal logic formula, Transition system, Temporal logic
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-313272DOI: 10.1109/TAC.2021.3118335ISI: 000861438100007Scopus ID: 2-s2.0-85119608436OAI: oai:DiVA.org:kth-313272DiVA, id: diva2:1662876
Note

QC 20250324

Available from: 2022-06-01 Created: 2022-06-01 Last updated: 2025-03-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Gao, YulongJiang, FrankJohansson, Karl H.

Search in DiVA

By author/editor
Gao, YulongJiang, FrankJohansson, Karl H.
By organisation
Decision and Control Systems (Automatic Control)
In the same journal
IEEE Transactions on Automatic Control
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 43 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf