Dealing with nondeterminism in symbolic control. (English) Zbl 1143.68488

Egerstedt, Magnus (ed.) et al., Hybrid systems: Computation and control. 11th international workshop, HSCC 2008, St. Louis, MO, USA, April 22–24, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78928-4/pbk). Lecture Notes in Computer Science 4981, 287-300 (2008).
Summary: Abstractions (also called symbolic models) are simple descriptions of continuous and hybrid systems that can be used in analysis and control. They are usually constructed in the form of transition systems with finitely many states. Such abstractions offer a very attractive approach to deal with complexity, while at the same time allowing for rich specification languages. Recent results show that, through the abstraction process, the resulting transition systems can be nondeterministic (i.e., if an input is applied in a state, several next states are possible). However, the problem of controlling a nondeterministic transition system from a rich specification such as a temporal logic formula is not well understood. In this paper, we develop a control strategy for a nondeterministic transition system from a specification given as a Linear Temporal Logic formula with a deterministic Büchi generator. Our solution is inspired by LTL games on graphs, is complete, and scales polynomially with the size of the Büchi automaton. An example of controlling a linear system from a specification given as a temporal logic formula over the regions of its triangulated state space is included for illustration.
For the entire collection see [Zbl 1142.93004].


68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q45 Formal languages and automata
68Q60 Specification and verification (program logics, model checking, etc.)
93B05 Controllability


Full Text: DOI