Recent technological innovations have caused a considerable interest in the study of dynamical processes of a mixed continuous and discrete nature, denoted as hybrid systems. In their most general form hybrid systems are characterized by the interaction of continuous-time models (governed by differential or difference equations), and of logic rules and discrete event systems (described, for example, by temporal logic, finite state machines, if-then-else rules) and discrete components (on/off switches or valves, gears or speed selectors, etc.). Such systems can switch between many operating modes where each mode is governed by its own characteristic dynamical laws. Mode transitions are triggered by variables crossing specific thresholds (state events), by the lapse of certain time periods (time events), or by external inputs (input events) (Antsaklis, 2000). A detailed discussion of different modeling frameworks for hybrid systems that appeared in the literature goes beyond the scope of this paper; the main concepts can be found in Antsaklis (2000), Branicky, Borkar, and Mitter (1998), Bemporad and Morari (1999), Lygeros, Tomlin, and Sastry (1999).
Different methods for the analysis and design of controllers for hybrid systems have emerged over the last few years (Sontag, 1981, Lygeros et al., 1999 and Bemporad and Morari, 1999). Among them, the class of optimal controllers is one of the most studied. The approaches differ greatly in the hybrid models adopted, in the formulation of the optimal control problem and in the method used to solve it.
In this paper we focus on discrete-time linear hybrid models. In our hybrid modeling framework we allow (i) the system to be discontinuous, (ii) both states and inputs to assume continuous and discrete values, (iii) events to be both internal, i.e., caused by the state reaching a particular boundary, and exogenous, i.e., forced by a switch to some other operating mode, and (iv) states and inputs to fulfill linear constraints. We will focus on discrete-time piecewise affine (PWA) models. Discrete-time PWA models can describe a large number of processes, such as discrete-time linear systems with static piecewise-linearities; discrete-time linear systems with discrete states and inputs; switching systems where the dynamic behavior is described by a finite number of discrete-time linear models together with a set of logic rules for switching among these models; approximation of nonlinear discrete-time dynamics, e.g., via multiple linearizations at different operating points.
In discrete-time hybrid systems an event can occur only at instants that are multiples of the sampling time, and many interesting mathematical phenomena occurring in continuous-time hybrid systems such as Zeno behaviors do not exist. However, the solution to optimal control problems is still complex: the solution to the HJB equation can be discontinuous and the number of possible switches grows exponentially with the length of the horizon of the optimal control problem. Nevertheless, we will show that for the class of linear discrete-time hybrid systems we can characterize and compute the optimal control law exactly without gridding the state space.
The solution to optimal control problems for discrete-time hybrid systems was first outlined by Sontag (1981). In his plenary presentation (Mayne, 2001) at the 2001 European Control Conference, Mayne presented an intuitively appealing characterization of the state-feedback solution to optimal control problems for linear hybrid systems with performance criteria based on quadratic and linear norms. The detailed exposition presented in the initial part of this paper follows a similar line of argumentation and shows that the state-feedback solution to the finite time optimal control problem is a time-varying PWA feedback control law, possibly defined over non-convex regions. Moreover, we give insight into the structure of the optimal state-feedback solution and of the value function.
In the second part of the paper we describe how the optimal control law can be efficiently computed by means of multiparametric programming. In particular, we propose a novel algorithm that solves the Hamilton–Jacobi–Bellman equation by using a simple multiparametric solver. In collaboration with different companies and institutes, the results described in this paper have been applied to a wide range of problems (Baotic, Vasak, Morari, & Peric, 2003; Bemporad, Borodani, & Mannelli, 2003; Bemporad, Giorgetti, Kolmanovsky, & Hrovat, 2002; Bemporad & Morari, 1999; Borrelli, Bemporad, Fodor, & Hrovat, 2001; Ferrari-Trecate et al., 2002 and Mignone, 2002; Möbus, Baotic, & Morari, 2003; Torrisi & Bemporad, 2004). Simple examples that highlight the main features of the hybrid system approach presented in this paper can be found in Borrelli, Baotic, Bemporad, and Morari (2003).
Before formulating optimal control problems for hybrid systems we will give a short overview on multiparametric programming and on discrete-time linear hybrid systems.
For discrete-time linear hybrid systems, we have described an off-line procedure to synthesize optimal control laws based on the minimization of quadratic and linear performance indices subject to linear constraints on inputs and states. The procedure is based on a combination of dynamic programming and multiparametric quadratic programming. In collaboration with different companies and institutes, the results described in this paper have been applied to a wide range of problems (Baotic et al., 2003, Bemporad et al., 2002, Bemporad et al., 2003, Bemporad and Morari, 1999, Borrelli et al., 2001, Ferrari-Trecate et al., 2002, Möbus et al., 2003 and Torrisi and Bemporad, 2004). Simple examples that highlight the main features of the hybrid system approach presented in this paper can be found in Borrelli et al. (2003).
