Discrete hybrid automata

Why yet another framework for hybrid systems?

We are going to introduce yet another framework for modeling hybrid systems – mixed logical dynamical (MLD) description. A question must inevitably pop up: “why yet another framework?”

The answer is, that we would like to have a model of a hybrid system that is suitable for model predictive control (MPC). Recall that the role of the model in MPC is that the model is used to define some constraints (equations and inequalities) in the numerical optimization problem. The frameworks that we considered so far did not offer it.

In particular, with the state variable and control input vectors composed of continuous and discrete variables \bm x = \begin{bmatrix}\bm x_c\\\bm x_d\end{bmatrix}, \quad \bm u = \begin{bmatrix}\bm u_c\\\bm u_d\end{bmatrix}, where \bm x_c\in\mathbb R^{n_c},\;\bm x_d\in\mathbb N^{n_d},\; \bm u_c\in\mathbb R^{m_c} and \bm u_d\in\mathbb N^{m_d}, we would like to formulate the model in the form of state equations, say \begin{aligned} \begin{bmatrix}\bm x_c(k+1) \\ \bm x_d(k+1)\end{bmatrix} &= \begin{bmatrix} \mathbf f_c(\bm x(k), \bm u(k)) \\ \mathbf f_d(\bm x(k), \bm u(k)) \end{bmatrix}. \end{aligned}

Is it possible?

Unfortunately no. At least not exactly in this form. But something close to it is achievable instead.

But first we need to set the terminology and notation used to define a discrete(-time) hybrid automaton.

Discrete hybrid automaton

Since the new modelling framework is expected to be useful for prediction of a system response within model predictive control, it must model a hybrid system in discrete time. This is a major difference from what we did in our course so far.

In particular, we are going to model a hybrid system as a discrete(-time) hybrid automaton (DHA), which means that

  • the continuous-value dynamics (often corresponding to the physical part of the system) evolves in discrete time,
  • the events and their processing by the logical part of the system are synchronized to the same periodic clock.

We are already well familiar with the concept of a hybrid automaton, and the restriction to discrete time does not seem to warrant reopening the definition (modes/locations, guards, invariants/domains, reset maps, …). However, it turns out that reformulating/restructuring the hybrid automaton will be useful for our ultimate goal of developing an MPC-friendly modelling framework. In particular, we consider four components of a DHA:

  • switched affine system (SAS),
  • mode selector (MS),
  • event generator (EG),
  • finite state machine (FSM).

Their interconnection is shown in the following figure.

[TBD] #TODO: Add a figure

Let’s discuss the individual components (and while doing that, you can think about the equivalent concept in the classical definition of a hybrid automaton such as mode, invariant, guard, …).

Switched affine systems (SAS)

This is a model of the continuous-value dynamics parameterized by the index i that evolves in (discrete) time \begin{aligned} x_c(k+1) &= A_{i(k)} x_c(k) + B_{i(k)} u_c(k) + f_{i(k)},\\ y_c(k) &= C_{i(k)} x_c(k) + D_{i(k)} u_c(k) + g_{i(k)}. \end{aligned}

In principle there is no need to restrict the right hand sides to affine functions as we did, but the fact is that the methods and tools are currently only available for this restricted class of systems.

Event generator (EG)

We consider partitioning of the state space or possibly state-control space into polyhedral regions. The system is then in the ith region of the state-input space, if the continuous-value state x_c(k) and the continuous-value control input u_c satisfy H_i x_c(k) + J_i u_c(k) + K_i \leq 0.

The event indicated by the (vector) binary variable \delta_e(k) = h(x_c(k), u_c(k)) \in \{0,1\}^m, where h_i(x_c(k), u_c(k)) = \begin{cases}1 & H_i x_c(k) + J_i u_c(k) + K_i \leq 0,\\ 0 & \text{otherwise}. \end{cases}

Finite state machine (FSM)

x_d(k+1) = f_d(x_d(k),u_d(k),\delta_e(k)).

Mode selector (MS)

i(k) \in \{1, 2, \ldots, s\}

i(k) = \mu(x_d(k), u_d(k), \delta_e(k)).

Trajectory of a DHA

\begin{aligned} \delta_e(k) &= h(x_c(k), u_c(k))\\ i(k) &= \mu(x_d(k), u_d(k), \delta_e(k))\\ y_c(k) &= C_{i(k)} x_c(k) + D_{i(k)} u_c(k) + g_{i(k)}\\ y_d(k) &= g_d(x_d(k), u_d(k), \delta_e(k))\\ x_c(k+1) &= A_{i(k)} x_c(k) + B_{i(k)} u_c(k) + f_{i(k)}\\ x_d(k+1) &= f_d(x_d(k),u_d(k),\delta_e(k)) \end{aligned}

Obviously, in order to compute the trajectory, besides the standard arithmetics, some IF-THEN conditions are also present in the model. They prevent us from using this model as constraints within a mathematical program (numerical optimization problem). Can we get rid of them?

Back to top