Logo Logo
Help
Contact
Switch language to German
Formal synthesis of partially-observable cyber-physical systems
Formal synthesis of partially-observable cyber-physical systems
This dissertation is motivated by the challenges arising in the synthesis of controllers for partially-observable cyber-physical systems (PO-CPSs). In the past decade, CPSs have become ubiquitous and an integral part of our daily lives. Examples of such systems range from autonomous vehicles, drones, and aircraft to robots and advanced manufacturing. In many applications, these systems are expected to do complex logic tasks. Such tasks can usually be expressed using temporal logic formulae or as (in)finite strings over finite automata. In the past few years, abstraction-based techniques have been very promising for the formal synthesis of controllers. Since these techniques are based on the discretization of state and input sets, when dealing with large-scale systems, unfortunately, they suffer severely from the curse of dimensionality (i.e., the computational complexity grows exponentially with the dimension of the state set). In order to overcome the large computa- tional burden, a discretization-free approach based on control barrier functions has shown great potential to solve formal synthesis problems. In this thesis, we provide a systematic approach to synthesize a hybrid control policy for partially-observable (stochastic) control systems without discretizing the state sets. In many real-life applications, full-state information is not always available (due to the cost of sensing or the unavailability of the measurements). Therefore, in this thesis, we consider partially-observable (stochastic) control systems. Given proper state estimators, our goal is to utilize a notion of control barrier functions to synthesize control policies that provide (and potentially maximize) a lower bound on the probability that the trajectories of the partially-observable (stochastic) control system satisfy complex logic specifications such as safety and those that can be expressed as deterministic finite automata (DFA). Two main approaches are presented in this thesis to construct control barrier functions. In the first approach, no prior knowledge of estimation accuracy is needed. The second approach utilizes a (probability) bound on the estimation accuracy. Though the synthesis procedure for lower-dimensional systems is challenging itself, the task is much more computationally expensive (if not impossible) for large-scale interconnected systems. To overcome the challenges encountered with large-scale systems, we develop approaches to reduce the computational complexity. In particular, by considering a large-scale partially-observable control system as an interconnection of lower-dimensional subsystems, we compute so-called local control barrier functions for subsystems along with the corresponding local controllers. By assuming some small-gain type conditions, we then utilize local control barrier functions of subsystems to compositionally construct an overall control barrier function for the interconnected system. Finally, since closed-form mathematical models of many physical systems are either unavailable or too complicated to be of any use, we also extend our work to the synthesis of safety controllers for partially-observable systems with unknown dynamics. To tackle this problem, we utilize a data-driven approach and construct control barrier functions and their corresponding controllers via sets of data collected from the output trajectories of the systems and the trajectories of the estimators. To demonstrate the effectiveness of the proposed results in the thesis, we consider various case studies, such as a DC motor, an adaptive cruise control (ACC) system consisting of vehicles in a platoon, and a Moore-Greitzer jet engine model.
Formal synthesis, Stochastic systems, Interconnected systems, Partially observable systems
Jahanshahi, Niloofar
2023
English
Universitätsbibliothek der Ludwig-Maximilians-Universität München
Jahanshahi, Niloofar (2023): Formal synthesis of partially-observable cyber-physical systems. Dissertation, LMU München: Faculty of Mathematics, Computer Science and Statistics
[thumbnail of Jahanshahi_Niloofar.pdf]
Preview
PDF
Jahanshahi_Niloofar.pdf

6MB

Abstract

This dissertation is motivated by the challenges arising in the synthesis of controllers for partially-observable cyber-physical systems (PO-CPSs). In the past decade, CPSs have become ubiquitous and an integral part of our daily lives. Examples of such systems range from autonomous vehicles, drones, and aircraft to robots and advanced manufacturing. In many applications, these systems are expected to do complex logic tasks. Such tasks can usually be expressed using temporal logic formulae or as (in)finite strings over finite automata. In the past few years, abstraction-based techniques have been very promising for the formal synthesis of controllers. Since these techniques are based on the discretization of state and input sets, when dealing with large-scale systems, unfortunately, they suffer severely from the curse of dimensionality (i.e., the computational complexity grows exponentially with the dimension of the state set). In order to overcome the large computa- tional burden, a discretization-free approach based on control barrier functions has shown great potential to solve formal synthesis problems. In this thesis, we provide a systematic approach to synthesize a hybrid control policy for partially-observable (stochastic) control systems without discretizing the state sets. In many real-life applications, full-state information is not always available (due to the cost of sensing or the unavailability of the measurements). Therefore, in this thesis, we consider partially-observable (stochastic) control systems. Given proper state estimators, our goal is to utilize a notion of control barrier functions to synthesize control policies that provide (and potentially maximize) a lower bound on the probability that the trajectories of the partially-observable (stochastic) control system satisfy complex logic specifications such as safety and those that can be expressed as deterministic finite automata (DFA). Two main approaches are presented in this thesis to construct control barrier functions. In the first approach, no prior knowledge of estimation accuracy is needed. The second approach utilizes a (probability) bound on the estimation accuracy. Though the synthesis procedure for lower-dimensional systems is challenging itself, the task is much more computationally expensive (if not impossible) for large-scale interconnected systems. To overcome the challenges encountered with large-scale systems, we develop approaches to reduce the computational complexity. In particular, by considering a large-scale partially-observable control system as an interconnection of lower-dimensional subsystems, we compute so-called local control barrier functions for subsystems along with the corresponding local controllers. By assuming some small-gain type conditions, we then utilize local control barrier functions of subsystems to compositionally construct an overall control barrier function for the interconnected system. Finally, since closed-form mathematical models of many physical systems are either unavailable or too complicated to be of any use, we also extend our work to the synthesis of safety controllers for partially-observable systems with unknown dynamics. To tackle this problem, we utilize a data-driven approach and construct control barrier functions and their corresponding controllers via sets of data collected from the output trajectories of the systems and the trajectories of the estimators. To demonstrate the effectiveness of the proposed results in the thesis, we consider various case studies, such as a DC motor, an adaptive cruise control (ACC) system consisting of vehicles in a platoon, and a Moore-Greitzer jet engine model.