Timing is everything: Analysis and synthesis of traffic patterns in event-triggered control

Abstract

Event-triggered control (ETC) and self-triggered control (STC) are sample-and-hold control paradigms in which sensor data is only updated to the controller when necessary, often aperiodically, in contrast to the well-established periodic sampling paradigm. In ETC, a state-dependent event triggers a transmission, while in STC the controller decides when to request the next sample. The main objective of ETC and STC is to reduce sampling and transmissions when either sampling/transmitting is costly or network resources are scarce. However, despite years of development in the ETC/STC field, little is known about their sampling performances or how to accommodate the generated aperiodic traffic of multiple ETC systems in a shared communication medium. This dissertation presents methods to (i) schedule multiple ETC systems in a shared network, (ii) evaluate ETC systems' sampling performance, and (iii) creating STC strategies that improve ETC systems' sampling performance. In particular, we focus for the most part on ETC applied to linear time-invariant (LTI) systems.

To solve these problems, we first model the timing behavior of ETC/STC systems, obtaining what we call traffic models. The states of a traffic model are the transmitted samples and its output is the elapsed time between consecutive transmissions, the inter-sample time (IST). These models are infinite-state systems that can exhibit very complex—even chaotic—behavior, as we demonstrate. To solve synthesis problems such as scheduling and optimal STC sampling strategies, we augment the models with early-sampling choices, which are guaranteed to preserve control stability and performance. The models are then abstracted into finite-state systems or timed automata, on which many of our problems can be computationally solved. Using these abstractions, the obtained schedulers are always valid for the real systems, and the obtained metrics are always formal bounds to the real system's performance.

Our abstraction method is based on quotient and l-complete systems. That is, we partition the state-space into regions, each region comprising all states whose next IST, or next sequence of l ISTs, is the same. This is made possible by observing that periodic ETC (PETC)—a practical version of ETC where events are checked periodically—has a finite output set, and that each obtained region is described by an intersection of finitely many quadratic cones. The abstraction transitions, which enable predicting how samples and their corresponding ISTs evolve over time, can be computed exactly using nonlinear satisfiability-modulo-theories solvers, or approximately through convex semi-definite relaxations. Infinite periodic IST patterns arising from these abstractions can be verified to exist in the real traffic model via an eigenvector problem, which is central for solving problem (ii) exactly.

Our methodology comprises a comprehensive framework for solving qualitative (scheduling) and quantitative (sampling performance) problems for ETC and STC, as well as a computational machinery that automates these processes, ultimately consolidated in the open-source tool ETCetera. With the developed methods, we can show cases where ETC significantly outperforms periodic sampling in terms of average inter-sample time, and how to increase this performance further using look-ahead. We also manage to solve the ETC scheduling problem efficiently, which is helped by an abstraction minimization algorithm that we propose. In summary, this dissertation provides new tools to understand and manipulate ETC traffic, and ultimately casts new light on the practical relevance of ETC and STC.