Paper deep dive
Model Predictive Control of Hybrid Dynamical Systems
Ricardo G. Sanfelice, Berk Altin
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 4/27/2026, 1:36:21 AM
Summary
This paper develops a theoretical framework for Model Predictive Control (MPC) applied to hybrid dynamical systems. Unlike traditional approaches that focus on discrete logic or mixed-integer programming, this work utilizes a set-theoretic formalism to model hybrid plants through continuous-time flows and discrete-time jumps. The authors provide sufficient conditions for the asymptotic stability of a set, establishing properties for the prediction horizon, the forward invariance of the terminal and feasible sets, and the role of the value function as a Lyapunov function. The framework is validated through examples including a bouncing ball control system and a sample-and-hold control mechanism.
Entities (8)
Relation Signals (4)
Ricardo G. Sanfelice → affiliatedwith → University of California, Santa Cruz
confidence 100% · Ricardo G. Sanfelice and B. Altın are with the Department of Electrical and Computer Engineering, University of California, Santa Cruz
Model Predictive Control → appliedto → Hybrid Dynamical Systems
confidence 100% · The problem of controlling hybrid dynamical systems using model predictive control (MPC) is formulated
NSF → funded → Ricardo G. Sanfelice
confidence 100% · Research by R. G. Sanfelice partially supported by NSF Grants
Bouncing Ball Control → isatypeof → Hybrid Dynamical Systems
confidence 90% · Example II.2 (Bouncing Ball Control) Consider the hybrid model of a ball bouncing vertically...
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The problem of controlling hybrid dynamical systems using model predictive control (MPC) is formulated and sufficient conditions for asymptotic stability of a set are provided. Hybrid dynamical systems are modeled in terms of hybrid equations, involving a differential equation and a difference equation with inputs and constraints. The proposed hybrid MPC algorithm uses a suitable prediction and control horizon construction inspired by hybrid time domains. Structural properties of the hybrid optimization problem, its feasible set, and its value function are provided. Checkable conditions to guarantee asymptotic stability of a set are provided. These conditions are given in terms of properties on the stage cost, terminal cost, and the existence of static state-feedback laws, related through a control Lyapunov function condition. Examples illustrate the results throughout the paper.
Tags
Links
- Source: https://arxiv.org/abs/2604.21989v1
- Canonical: https://arxiv.org/abs/2604.21989v1
Trouble viewing inline? Open PDF directly →
Full Text
157,053 characters extracted from source content.
Expand or collapse full text
Model Predictive Control of Hybrid Dynamical Systems Ricardo G. Sanfelice, , and Berk Altın R. G. Sanfelice and B. Altın are with the Department of Electrical and Computer Engineering, University of California, Santa Cruz, CA, 94107 USA e-mail: ricardo@ucsc.edu, berkaltin@ucsc.edu. Research funded in part by Research by R. G. Sanfelice partially supported by NSF Grants no. CNS-2039054 and CNS-2111688, by AFOSR Grants nos. FA9550-23-1-0145, FA9550-23-1-0313, and FA9550-23-1-0678, by AFRL Grant nos. FA8651-22-1-0017 and FA8651-23-1-0004, by ARO Grant no. W911NF-20-1-0253, by DoD Grant no. W911NF-23-1-0158, and by UC Alianza MX Grant no. SRPUCMX24-01. Abstract The problem of controlling hybrid dynamical systems using model predictive control (MPC) is formulated and sufficient conditions for asymptotic stability of a set are provided. Hybrid dynamical systems are modeled in terms of hybrid equations, involving a differential equation and a difference equation with inputs and constraints. The proposed hybrid MPC algorithm uses a suitable prediction and control horizon construction inspired by hybrid time domains. Structural properties of the hybrid optimization problem, its feasible set, and its value function are provided. Checkable conditions to guarantee asymptotic stability of a set are provided. These conditions are given in terms of properties on the stage cost, terminal cost, and the existence of static state-feedback laws, related through a control Lyapunov function condition. Examples illustrate the results throughout the paper. I Introduction I-A Background and Motivation Model Predictive Control (MPC) has established itself as a versatile and powerful feedback strategy for constrained control of dynamic systems, with extensive application across industries. Since its conception as a solution to control problems in emerging industry back in the late 1970s/early 1980s [36, 17], the iterative, optimization-based algorithmic structure of MPC has appealed to practitioners aiming at solving myriad of control problems.111Some of the history of MPC is reported in [28] and [34]. MPC is a receding horizon control scheme that optimizes the selection of the control inputs through the use of a dynamic model of the process to predict the effect of future control actions. Without attempting to survey such a broad literature, MPC schemes for linear and nonlinear systems have undergone substantial development, leading to widespread adoption and rigorous theoretical foundations [35, 11, 21]. Early continuous-time MPC strategies, such as [23, 15], illustrate how continuous-time dynamics can be incorporated into MPC, often through discretization or continuous-time optimization formulations. Within the broader context of MPC, the term “hybrid MPC” typically refers to control of systems that feature both continuous and discrete elements, such as logic-based constraints or mixed-valued states and inputs, or that have a discontinuous right-hand side due to the process dynamics or the control algorithm being nonsmooth [25, 12, 11]. A well-known foundational framework for such systems was developed in [9], where the authors propose mixed logical dynamical (MLD) models and corresponding mixed-integer MPC formulations. These methods address discrete modes and logic rules, and have influenced a large body of work on hybrid MPC [8, 7, 11, 12, 25]. However, following [39], the use of the term “hybrid” in this paper aligns better with the definition introduced in the hybrid systems community [43, 5, 19, 40]. These models capture hybrid behavior beyond discrete logic and variables, including impulsive effects, resets, switching, and asynchronous updates, which arise naturally in applications such as networked systems, robotics, and cyber-physical systems. Several works have addressed model predictive control for classes of systems exhibiting hybrid behaviors, with emphasis on switched and impulsive dynamics. For example, [27] presents a robust MPC formulation for switched systems under uncertain switching schedules, ensuring constraint satisfaction through conservative design techniques. In [41], MPC schemes for linear impulsive systems, addressing the discrete-time occurrence of impulses and demonstrating stability under specific assumptions, are developed. The work in [33] proposes a general optimization-based control framework for impulsive systems, focusing on trajectory generation and feasibility. In [29], the authors investigate switched nonlinear systems and derive conditions under which MPC guarantees stability assuming an average dwell-time condition. Similarly, [16] studies robust MPC for discrete-time switched systems, considering uncertainties and constraints. As a difference to settings based on MLD models, mixed-valued states and inputs, or nonsmooth dynamics, this paper employs the framework for hybrid control systems in [40], in which a hybrid plant is described by the interaction of continuous-time dynamics and discrete-time transitions governed by a unified set-theoretic formalism. Specifically, a hybrid plant is given by ℋ:x˙=f(x,u)(x,u)∈Cx+=g(x,u)(x,u)∈DH: \ aligned x&=f(x,u)&(x,u)&∈ C\\ x^+&=g(x,u)&(x,u)&∈ D aligned . (1) where x is the state, u is the control input, C is the flow set, f is the flow map, D is the jump set, and g is the jump map. This formalism encapsulates numerous models of a hybrid nature already studied in the context of MPC, sample-and-hold control [18, 22], event/self-triggered control [42], and switching systems [26], which, very importantly, as stated in [25, Section 2.2.5], “it is bound to influence further research on hybrid MPC.” The primary objective of this paper is to lay down the theoretical foundations of a MPC framework for hybrid dynamical systems, with the meaning of “hybrid” as clarified above. In contrast to the aforementioned works, the present approach directly incorporates hybrid time domains and trajectory evolution into the prediction and constraint structure, allowing for general, continuous-time hybrid dynamics beyond piecewise-affine, impulsive, or switched-only systems. Although modern MPC developments, such as economic and dissipativity-based MPC, turnpike phenomena, and formulations without terminal ingredients, offer powerful alternatives in continuous settings, their extension to hybrid systems is nontrivial and remains an open research direction. This paper focuses on transferring and formalizing early MPC principles in the hybrid context, providing a foundation for future integration of these newer techniques. I-B Contributions Although the concept of applying MPC to hybrid systems has existed in literature for several decades, an MPC framework for hybrid plants of the form (1) is not yet available. This paper provides a comprehensive presentation of hybrid MPC for such systems, and formally introduces the structural conditions and theoretical tools needed to ensure: 1. Appropriate structure and properties of the hybrid prediction horizon; 2. Forward invariance of the terminal constraint set and of the feasible set (Proposition V.1 and Proposition V.2); 3. That the value function serves as a Lyapunov function via bounds in terms of the terminal and stage costs (Lemma V.3 and Lemma V.5); 4. Positive definiteness of the value function (multiple results in Section V-D and Section V-E); 5. Asymptotic stability of a closed set via hybrid MPC, including special cases when jumps or flows are persistent (Theorem VI.2); 6. Two examples showing in detail how to apply the results. The results are illustrated in two examples throughout the paper, one pertaining to control of a bouncing ball and another one about sample-and-hold control. The overall framework was first outlined in the conference paper [1], which informally presents an initial version of the framework presented here but does not include any mathematical result. The conference paper [2] presents a preliminary version of the basic assumptions. These assumptions are relaxed here; in particular, the set to asymptotically stabilize does no longer need to be compact, expanding the applicability of our results to a broader class of stabilization problems (e.g., consensus, tracking, and estimation), and a condition relating the terminal constraint set and the set to asymptotically stabilize is removed (see (O4) in [2]). A result revealing properties of the value function was stated without proof in [2, Lemma 5.4 and Lemma 5.5], but significantly improved here, under weaker assumptions (cf. Lemma V.3 and Lemma V.5) and allowing the stage costs and the terminal cost to be not be positive definite. The latter results can be found in Section V-D and Section V-E, which further extend the relaxations in the conference paper [3] – in fact, only a version of items 2 and 3 in Theorem V.6 are considered therein, which are further relaxed in those sections. Note that [2] and [3] do not include i) any mathematical proofs, i) the intermediate results required to establish the properties of the value function and asymptotic stability, and i) the many illustrations via examples, given by two examples revisited throughout the paper multiple times. I-C Organization of the Paper Section I introduces notation and basic concepts of hybrid systems. Section I presents an overview of hybrid MPC and its main ingredients: the cost functional, the prediction horizon, the constrained optimal control problem, and the recursive implementation of hybrid MPC. The assumptions required for hybrid MPC to be asymptotically stabilizing are presented in Section IV. Section V reveals the main properties of the constrained optimal control problem associated with hybrid MPC. Section V-D characterizes properties guaranteeing positive definiteness of the value function. Section VI formalizes the asymptotic stabilization properties of hybrid MPC. Section VII presents examples to which the main results are applied. Open problems and future work are discussed in Section VIII. I Background on Hybrid Control Systems Throughout the paper, we use ℝR to represent real numbers and ℝ≥0R_≥ 0 its nonnegative subset. The set of nonnegative integers is denoted ℕN. The notation S1⊂S2S_1⊂ S_2 indicates S1S_1 is a subset of S2S_2, not necessarily proper. The 2-norm is denoted |⋅||·|. The distance of a vector x∈ℝnx ^n to a nonempty set ⊂ℝn A ^n is denoted |x|:=infa∈|x−a| |x |_ A:= _a∈ A|x-a|. We denote by +δ A+ the set of all x∈ℝnx ^n such that |x−a|≤δ|x-a|≤δ for some a∈a∈ A. The interior and closure of a set S⊂ℝnS ^n are denoted intS int S and clS cl S, respectively. We denote by Π:ℝn×ℝm→ℝn :R^n×R^m ^n the standard projection onto ℝnR^n such that Π(x,y)=x (x,y)=x. A strictly increasing continuous function α:ℝ≥0→ℝ≥0α:R_≥ 0→R_≥ 0 with α(0)=0α(0)=0 is said to be a class- K function. An unbounded class- K function is said to be a class-∞ K_∞ function. I-A Hybrid Control Systems This paper focuses on the control of hybrid plants given as ℋH in Section I, where x∈ℝnx ^n is the state and u∈ℝmu ^m is the control input. The data of the hybrid plant ℋH is given by • the flow set C⊂ℝn×ℝmC ^n×R^m; • the flow map f:C→ℝnf:C ^n describes the continuous evolution of x when (x,u)(x,u) belongs to C; • the jump set D⊂ℝn×ℝmD ^n×R^m; • the jump map g:D→ℝng:D ^n describes the discrete evolution of x when (x,u)(x,u) belongs to D. At times, the data of ℋH is explicitly denoted as ℋ=(C,f,D,g)H=(C,f,D,g). Furthermore, when convenient, the input u is partitioned as (uc,ud)(u_c,u_d), where ucu_c collects the components of u that affect the flows and udu_d the components that affect jumps. To simplify the formulation and development of the forthcoming results, the following mild standing assumption on the flow set C is imposed. Assumption I.1 (Standing Assumption) The set C is closed. In particular, as clarified below, assuming C to be closed simplifies the notion of solution pairs. For example, with C closed, solutions are defined so that the state trajectory component of each solution stays in the projection of C onto ℝnR^n over intervals of ordinary time, except potentially at the initial and end times of each such interval. It also simplifies the conditions that the pair needs to satisfy at the initial (hybrid) time. Example I.2 (Bouncing Ball Control) Consider the hybrid model of a ball bouncing vertically on a horizontal flat surface with height x1x_1 and velocity x2x_2. When x1≥0x_1≥ 0, the motion of the (point-mass) ball is represented by the second order differential equation x˙1=x2,x˙2=−γ x_1=x_2, x_2=-γ (2) where γ>0γ>0 is the gravitational constant. Impacts with the surface are assumed to occur instantaneously, namely, the compression of the ball at collisions is neglected and the exchange of kinetic energy between the ball and the ground takes zero time. This behavior is conveniently captured by the difference equation x1+=x1,x2+=−λx2+ux_1^+=x_1, x_2^+=-λ x_2+u (3) where λ∈[0,1]λ∈[0,1] is the coefficient of restitution and u≥0u≥ 0 is a control input that affects the velocity after impacts. Such an instantaneous change occurs when x1=0x_1=0 and x2≤0x_2≤ 0. In the autonomous case with dissipative jumps (i.e., when u=0u=0 and λ∈[0,1)λ∈[0,1)), asymptotic stability of the origin can be certified using the total energy function W(x):=γx1+x222∀x∈ℝ2W(x):=γ x_1+ x_2^22 ∀ x ^2 (4) Although W is constant during flows, it decreases at each impact away from the origin. The dynamics can be represented in the form of (1) by incorporating the constraints therein to (2)-(3). This system can be written as a hybrid plant ℋH in (1), as follows: ℋ:[x˙1x˙2]=f(x,u):=[x2−γ](x,u)∈C[x1+x2+]=g(x,u):=[0−λx2+u](x,u)∈DH: \ aligned bmatrix x_1\\ x_2 bmatrix&=f(x,u):= bmatrixx_2\\ -γ bmatrix&(x,u)&∈ C\\ bmatrixx_1^+\\ x_2^+ bmatrix&=g(x,u):= bmatrix0\\ -λ x_2+u bmatrix&(x,u)&∈ D aligned . with C:=(x,u)∈ℝ2×ℝ≥0:x1≥0C:=\(x,u) ^2×R_≥ 0:x_1≥ 0\ and D:=(x,u)∈ℝ2×ℝ≥0:x1=0,x2≤0,u≥0D:=\(x,u) ^2×R_≥ 0:x_1=0,x_2≤ 0,u≥ 0\. Note that the flow map is defined on C and the jump map is defined on D. △ We refer to an input signal u and the corresponding state trajectory x collectively as a solution pair (x,u)(x,u) to ℋH. A solution pair (x,u)(x,u) is parametrized by (t,j)∈ℝ≥0×ℕ(t,j)∈R_≥ 0×N, where t denotes flow time and j is the number of jumps. The domain of x, denoted domx dom x, is a hybrid time domain. A set S⊂ℝ≥0×ℕS⊂R_≥ 0×N is a compact hybrid time domain if S=⋃j=0J([tj,tj+1]×j)S= _j=0^J ([t_j,t_j+1]×\j\ ) for some J∈ℕJ and for some finite sequence of times tjj=0J+1\t_j\_j=0^J+1 satisfying 0=t0≤t1≤t2≤…≤tJ≤tJ+10=t_0≤ t_1≤ t_2≤…≤ t_J≤ t_J+1, where tjt_j is the ordinary time of the j-th jump. Then, domx⊂ℝ≥0×ℕ dom x⊂R_≥ 0×N is a hybrid time domain if it is the union of a nondecreasing sequence of compact hybrid time domains, namely, domx dom x is the (possibly infinite) union of compact hybrid time domains S0,S1,…,Si,…S_0,S_1,…,S_i,… with the property that the sequence Sii=0i¯\S_i\_i=0 i, i¯∈ℕ∪∞ i ∪\∞\, satisfies S0⊂S1⊂S2⊂…⊂Si⊂…S_0⊂ S_1⊂ S_2⊂…⊂ S_i⊂… . The domain of u is denoted domu dom u in a similar fashion. Since the state and input pair needs to satisfy the dynamics imposed by the hybrid plant at the hybrid times for which they are defined, the domain of the input and of the state are assumed to be the same. Under this assumption, for simplicity, we write dom(x,u) dom (x,u) to denote the hybrid time domain of the pair (x,u)(x,u). Definition I.3 (Solution Pair) Given a pair of functions x:domx→ℝnx: dom x ^n and u:domu→ℝmu: dom u ^m, (x,u)(x,u) is said to be a solution pair to (1) if dom(x,u):=domx=domu dom (x,u):= dom x= dom u is a hybrid time domain and the following hold: (S0) (x(0,0),u(0,0))∈C∪D(x(0,0),u(0,0))∈ C∪ D, (S1) For each j∈ℕj such that Ij:=t:(t,j)∈dom(x,u)I^j:=\t:(t,j)∈ dom (x,u)\ has a nonempty interior, (S1.1) the function t↦x(t,j)t x(t,j) is locally absolutely continuous, (S1.2) the function t↦u(t,j)t u(t,j) is Lebesgue measurable and locally essentially bounded, t∈intIjt∈ int I^j, and (S1.3) for almost all t∈Ijt∈ I^j, (x(t,j),u(t,j)) (x(t,j),u(t,j)) ∈C, ∈ C, (5) x˙(t,j) x(t,j) =f(x(t,j),u(t,j)) =f(x(t,j),u(t,j)) (S2) For each (t,j)∈dom(x,u)(t,j)∈ dom (x,u) such that (t,j+1)∈dom(x,u)(t,j+1)∈ dom (x,u), (x(t,j),u(t,j)) (x(t,j),u(t,j)) ∈D, ∈ D, (6) x(t,j+1) x(t,j+1) =g(x(t,j),u(t,j)) =g(x(t,j),u(t,j)) Remark I.4 The condition in (SO) assures that the initial condition for the state and for the initial value of input can lead to evolution forward in hybrid time. Since C is closed, the condition in (SO) does not involve a closure on C. When C is not closed, it might be possible to have flow when x(0,0)x(0,0) is on the boundary of the projection of C to the state space, as long as u belongs to the interior of the projection of C to the input space after (t,j)=(0,0)(t,j)=(0,0). The condition in (S1.1) guarantees enough regularity of the state trajectory so that a derivative can be calculated during intervals of flow, at least, almost everywhere. A function x that is defined on a hybrid time domain and satisfies (S1.1) is called a hybrid arc. The condition in (S1.2) on the input u further assures integrability during flows. A function u that is defined on a hybrid time domain and satisfies (S1.2) is called a hybrid input. Closedness of C also permits simplifying the two properties in (S1.3), by requiring them to both hold for almost all t, rather than requiring that (x(t,j),u(t,j))∈C(x(t,j),u(t,j))∈ C holds for all t’s in the interior of IjI^j. Note that a solution (x,u)(x,u) might belong to both C and D, in which case either flow or jump might be possible. However, when the input u is given, flow intervals and jump times are determined by its hybrid time domain domu dom u. Throughout the paper, the set of solution pairs to ℋH starting from the set X∘⊂ℝnX_ ^n is denoted ^ℋ(X∘) S _H(X_ ). That is, (x,u)∈^ℋ(X∘)(x,u)∈ S _H(X_ ) implies x(0,0)∈X∘x(0,0)∈ X_ . Given a solution pair (x,u)(x,u), (T,J)∈dom(x,u)(T,J)∈ dom (x,u) is said to be the terminal (hybrid) time of (x,u)(x,u) if T≥tT≥ t and J≥jJ≥ j for all (t,j)∈dom(x,u)(t,j)∈ dom (x,u). A truncation of a solution pair (x,u)(x,u) up to some (T,J)∈dom(x,u)(T,J)∈ dom (x,u) is given by a solution (x′,u′)(x ,u ) that is equal to (x,u)(x,u) with domain dom(x′,u′) dom (x ,u ) given by dom(x,u)∩([0,T]×0,1,…,J)=:⋃i=0J([si,si+1]×i) dom (x,u)∩([0,T]×\0,1,…,J\)=: _i=0^J([s_i,s_i+1]×\i\) (7) for some nondecreasing sequence sii=0J+1\s_i\_i=0^J+1, which is said to be the sequence of generalized jump times associated with the truncation (x′,u′)(x ,u ). Furthermore, a solution pair (x,u)(x,u) is said to be • maximal if it cannot be further extended; • complete if dom(x,u) dom (x,u) is unbounded; and to have a • compact domain if dom(x,u) dom (x,u) is a compact subset of ℝ≥0×ℕR_≥ 0×N with a hybrid time domain structure, namely, with a domain dom(x,u) dom (x,u) equal to ⋃j=0J([tj,tj+1]×j) _j=0^J ([t_j,t_j+1]×\j\ ) for some finite nondecreasing sequence tjj=0J+1\t_j\_j=0^J+1 with t0=0t_0=0 and J∈ℕJ . In addition, a complete solution pair (x,u)(x,u) is said to have • persistent flows if dom(x,u) dom (x,u) is unbounded in the t direction—that is, there exists no T∈ℝ≥0T∈R_≥ 0 such that t≤Tt≤ T for all (t,j)∈dom(x,u)(t,j)∈ dom (x,u); • persistent jumps if dom(x,u) dom (x,u) is unbounded in the j direction—that is, there exists no J∈ℕJ such that j≤Jj≤ J for all (t,j)∈dom(x,u)(t,j)∈ dom (x,u). For simplicity, at times we use (x,u)(x,u) to denote a solution pair or points in ℝn×ℝmR^n×R^m, explicitly making it clear what is meant by saying “solution” or “points” when not clear from context. Example I.5 (Bouncing Ball Control (revisited)) For the bouncing ball with a control input in Example I.2, the amount of ordinary time needed to exhibit an impact (or jump) from any given initial state x=(x1,x2)x=(x_1,x_2) with x1≥0x_1≥ 0 is finite. Hence, every complete solution pair to this hybrid plant has persistent jumps. For a complete characterization of its solutions, see [40, Example 2.32] and [19, Example 2.12]. Due to persistence of jumps, the total energy W in (4) serves as a Lyapunov function for the bouncing ball system in Example I.2 with u≡0u≡ 0 [19, Example 3.15]. Example I.6 (Sample-and-Hold Control) Consider a continuous-time control system with state z∈ℝnzz ^n_z, control input η∈ℝmzη ^m_z, and dynamics z˙=f~(z,η) z= f(z,η), where f~:ℝnz×ℝmz→ℝnz f:R^n_z×R^m_z ^n_z is the right-hand side. When the input η of the plant is updated periodically using a zero-order hold mechanism (e.g., a digital-to-analog converter), the resulting control system can be written as in (1) by treating η as a state component and by introducing a clock variable τs∈ℝ≥0 _s∈R_≥ 0 that updates η every TsT_s seconds. Let x=(z,η,τs)∈ℝnz×ℝmz×ℝ≥0x=(z,η, _s) ^n_z×R^m_z×R_≥ 0 be the state and u the input of the system capturing the dynamics of the system being controlled as well as the sample-and-hold mechanism updating η. In contrast with the continuous-time approach in [18], we capture the dynamics by a hybrid plant ℋH as in (1) with the following data: • the flow map is given by f(x,u):=(f~(z,η),0,1)f(x,u):=( f(z,η),0,1); • the flow set is given by C:=(x,u)∈ℝnz×ℝmz×ℝ≥0×ℝ≥0:τs∈[0,Ts]C:=\(x,u) ^n_z×R^m_z×R_≥ 0×R_≥ 0: _s∈[0,T_s]\, • the jump map is given by g(x,u):=(z,u,0)g(x,u):=(z,u,0); • the jump set is given by D:=(x,u)∈ℝnz×ℝmz×ℝ≥0×ℝ≥0:τs=TsD:=\(x,u) ^n_z×R^m_z×R_≥ 0×R_≥ 0: _s=T_s\. This data accomplishes the following. During flows, the definition of the flow map f is such that the timer τs _s evolves continuously with a constant rate of one, so as to reproduce ordinary time, η remains constant, and z evolves according to the dynamics of the continuous-time system being controlled by the constant input η. When τs _s reaches TsT_s, which is captured by the definition of the jump set D, the definition of the jump map g indicates that τs _s gets reset to zero and η is updated to the value of the input u of the hybrid system at the time of the event. At jumps, the state of the system being controlled remains constant, hence the first component of g is equal to z. Note that the input u to the hybrid system is yet to be assigned. In the forthcoming Section VII, the input u is assigned by the hybrid MPC algorithm presented in the next section. If the input u is given by a continuous-time signal defined for each t∈ℝ≥0t∈R_≥ 0, complete solution pairs (x,u)(x,u) of this system resulting from putting the continuous-time input and the state trajectory on the same hybrid time domain222See [38, 10] for more details. have persistent flows and jumps, as the j-th jump occurs at ordinary time tj=Tsj−τs(0,0)t_j=T_sj- _s(0,0), where τs(0,0) _s(0,0) is the initial condition for the timer τs _s. If the input u is given only at jump times, the same construction is possible by extending the definition of the input over the intervals of flow, for example, as a piecewise constant signal. △ A hybrid system ℋH has solution pairs with unique state trajectories (t,j)↦x(t,j)(t,j) x(t,j) if two inputs that are identical, namely, they are equal during jumps and equal almost everywhere (in time) during flows, lead to the same state trajectory from the same initial condition. To ensure uniqueness for ℋH, we impose the following assumption in our forthcoming result establishing asymptotic stability (Theorem VI.2). Assumption I.7 Given the hybrid plant ℋ=(C,f,D,g)H=(C,f,D,g) in (1), the constrained differential equation x˙=f(x,u)(x,u)∈C x=f(x,u) (x,u)∈ C (8) has unique state trajectories t↦x(t)t x(t); that is, for each x∘x_ , and each pair of inputs t↦u1(t)t u_1(t) and t↦u2(t)t u_2(t) with domu1=domu2 dom u_1= dom u_2 such that u1(t)=u2(t)u_1(t)=u_2(t) for almost all t∈domu1t∈ dom u_1, and (x∘,u1(0))∈C(x_ ,u_1(0))∈ C and (x∘,u2(0))∈C(x_ ,u_2(0))∈ C, the respective solution pairs (x1,u1)(x_1,u_1) and (x2,u2)(x_2,u_2) have identical state trajectories over their common domain of definition. The next result can be obtained using similar steps as in the proof of [19, Proposition 2.11]. Proposition I.8 The hybrid control system ℋH has unique state trajectories if and only if Assumption I.7 holds. Proof: Necessity is obvious. For sufficiency, consider two solution pairs (x,u)(x,u) and (x′,u′)(x ,u ) with the same initial condition and domain, where u and u′u are equivalent. Since jumps of x and x′x occur at the same ordinary time, uniqueness follows from uniqueness during flows (by Assumption I.7) and uniqueness during jumps. ∎ Remark I.9 For hybrid dynamical systems with single-valued flow and jump maps and no inputs (i.e., closed hybrid systems), uniqueness of solutions is guaranteed when flows are not possible on the intersection of the flow and jump sets, and the constrained differential equation (8) has unique solutions [19, Proposition 2.11] and [40, Proposition 2.34]. In contrast, Assumption I.7 states that uniqueness during flows is necessary and sufficient for uniqueness of state trajectories. This property is due to the fact that given any two solution pairs (x,u)(x,u) and (x′,u)(x ,u), their jump times are determined by the domain of the input; hence, by Definition I.3, dom(x,u)=dom(x′,u)=domu dom (x,u)= dom (x ,u)= dom u. I-B Hybrid Control Systems under Static State-Feedback For analysis purposes, we also study the hybrid closed-loop system arising from assigning the input u=(uc,ud)u=(u_c,u_d) to static state-feedback laws κC:ℝn→ℝm _C:R^n ^m and κD:ℝn→ℝm _D:R^n ^m for the hybrid plant ℋH in (1). With this input partition, the resulting hybrid closed-loop system, denoted ℋκH_κ, is given by ℋκ:x˙=fκ(x):=f(x,κC(x))x∈Cκx+=gκ(x):=g(x,κD(x))x∈DκH_κ: \ aligned x&=f_κ(x):=f(x, _C(x))&x&∈ C_κ\\ x^+&=g_κ(x):=g(x, _D(x))&x&∈ D_κ aligned . (9) where Cκ C_κ :=x∈ℝn:(x,κC(x))∈C, =\x ^n:(x, _C(x))∈ C\, Dκ D_κ :=x∈ℝn:(x,κD(x))∈D =\x ^n:(x, _D(x))∈ D\ Similar to ℋH in (1), we define solutions to (9) over hybrid time domains via Definition I.3, as follows: a hybrid arc-input pair (x,u)(x,u) is said to be a solution pair to (9) generated by the feedback κ if there exists a solution pair (x,u)(x,u) to ℋH that satisfies (5) with u(t,j)=κC(x(t,j))u(t,j)= _C(x(t,j)) for all t∈intIjt∈ int I^j and (6) with u(t,j)=κD(x(t,j))u(t,j)= _D(x(t,j)) for all (t,j)∈dom(x,u)(t,j)∈ dom (x,u) such that (t,j+1)∈dom(x,u)(t,j+1)∈ dom (x,u). At times, we say that the x component of such solution pair is a state trajectory of (9). I Hybrid MPC: Key Elements and Algorithm In this section, we introduce the main elements required to formulate an MPC algorithm to asymptotically stabilize the hybrid plant ℋH in (1). I-A Overview In simple words, the algorithm measures the current state of ℋH and finds an optimal solution pair to ℋH over a finite horizon in hybrid time. The optimization problem consists of minimizing a cost functional, subject to constraints on the terminal time and terminal state. The cost functional assesses the cost of the evolution of the state and of the possible inputs to be applied, both over intervals of flows and at time instances at which jumps occur. The cost functional imposes a cost on the terminal state, relative to a desired target set. This optimization is performed over a hybrid prediction horizon, and the terminal hybrid time is allowed to vary within a set rather than being restricted to a point, as done, for instance, in discrete-time MPC where the optimization involves a fixed prediction horizon. This optimization approach is reminiscent of free end-time optimal control. It is instrumental for MPC for hybrid systems as the hybrid time domain of an optimal solution pair is not known a priori. Each time the state is measured, the algorithm finds an optimal control hybrid input that is applied to ℋH until the next measurement, leading to a receding horizon implementation. The initial optimization occurs at the initial time (t,j)=(0,0)(t,j)=(0,0). We refer to this algorithm as hybrid MPC. There are three main differences between conventional continuous-time/discrete-time MPC, in their general formulations, and hybrid MPC: • Since hybrid control systems can have solution pairs from nearby initial conditions with drastically different hybrid time domains, the terminal time has to be allowed to vary within a set. This set is the hybrid prediction horizon introduced above. • To account for the differences in the hybrid time domains of optimal control hybrid inputs, the optimization times are not assumed to be periodic or known a priori. Instead, with the initial optimization being performed at time (0,0)(0,0), each subsequent optimization hybrid time is selected online and the re-optimization occurs before the current hybrid control input is exhausted. • Since hybrid plants typically involve timer states, logic variables, and memory states, as Example I.6 illustrates, the problem that hybrid MPC has to solve may be a set stabilization problem rather than a set-point stabilization problem. In fact, the stabilization problem associated with Example I.6 consists of asymptotic stabilizing the state z to zero, η to some compact set, and τs _s to the range [0,Ts][0,T_s]. It should be noted that the results in this paper do not involve discretization of the differential equation governing the flow of ℋH, since the focus is on theoretical properties of MPC for hybrid systems. A discussion about discretization is in the forthcoming Remark I.8. In the remainder of this section, we detail the formulation of the key elements involved in the formulation of the constrained optimization problem solved by hybrid MPC. I-B Hybrid Prediction Horizon To allow for the prediction of state trajectories that may flow or jump without knowing the behavior a priori, we propose a prediction horizon T that is a subset of ℝ≥0×ℕR_≥ 0×N. This set-based generalization of the usual notion of prediction horizon accounts for hybrid time domains and maximizes the set of initial conditions such that the optimal control problem (OCP) associated to hybrid MPC is feasible. We refer to this construction as the hybrid prediction horizon. To motivate it, we revisit Example I.2. Example I.1 (Bouncing Ball Control (revisited)) For the bouncing ball model in Example I.2 (see also Example I.5), any open-loop hybrid input that steers the state to the origin necessarily leads to trajectories with the time between consecutive jumps converging to zero.333Given a complete solution pair (x,u)(x,u) to (2)-(3), let tj+1t_j+1 be the (j+1)(j+1)th jump time, i.e., (tj+1,j),(tj+1,j+1)∈dom(x,u)(t_j+1,j),(t_j+1,j+1)∈ dom (x,u) for all j∈ℕj . Then, tj+1−tj=(x2(tj,j)+(x2(tj,j))2+2γx1(tj,j))/γt_j+1-t_j= (x_2(t_j,j)+ (x_2(t_j,j))^2+2γ x_1(t_j,j) )/γ for all j∈ℕj [19, Example 2.12], where t0:=0t_0:=0, as the flow map does not depend on the input. Consequently, limj→∞tj+1−tj=0 _j→∞t_j+1-t_j=0 when limj→∞|x(tj,j)|=0 _j→∞|x(t_j,j)|=0. The implication of this property is that it would be impossible to asymptotically stabilize the origin of the bouncing ball by hybrid MPC when the associated OCP is restricted to a fixed prediction horizon of the form (T,J)(T,J), no matter how T∈ℝ≥0T∈R_≥ 0 and J∈ℕJ are chosen. In fact: 1. Since flows are not possible from the origin, given any solution pair (x,u)(x,u) with compact domain and terminal time (T,J)(T,J), since T>0,T>0,there exists (t,j)∈dom(x,u)(t,j)∈ dom (x,u) such that x(t,j)≠(0,0)x(t,j)≠(0,0). As a consequence, prediction horizons of the form (T,J)(T,J) with T>0T>0 are not suitable for asymptotic stabilization of the origin. 2. If the prediction horizon were to be fixed at (0,J)(0,J) for some J∈ℕ>0J _>0 (that is, T=0T=0) the OCP associated to hybrid MPC would only allow jumps and, therefore, be unsolvable from any initial condition with nonzero position or with positive velocity—namely, for every initial condition from the set C D, where C and D are given in Example I.2. Again, this choice of prediction horizon would prohibit asymptotic stabilization of the origin. △ As highlighted in Example I.5, the notion of a prediction horizon given by a singleton (T,J)\(T,J)\ can be overly restrictive and prevent a reasonable formulation of MPC for hybrid systems in the form (1). To maximize feasibility of the OCP, an appropriate selection of the prediction horizon T should ensure that it intersects with unbounded hybrid time domains. To this end, we define the hybrid prediction horizon as a set with a specific geometry that overcomes this issue and maximizes feasibility. Definition I.2 (Hybrid Prediction Horizon) A set ⊂ℝ≥0×ℕ T⊂R_≥ 0×N is a hybrid prediction horizon if there exists a finite nonincreasing sequence tjj=0J+1\t_j\_j=0^J+1 such that t0>0t_0>0, J≥0J≥ 0, tJ+1=0t_J+1=0, and :=⋃j=0J([tj+1,tj]×j) T:= _j=0^J ([t_j+1,t_j]×\j\ ) This prediction structure guarantees that, if a solution pair (x,u)(x,u) “lasts long enough,”444By the ordering induced by the structure of hybrid time domains, the length of elapsed hybrid time (t,j)(t,j) is succinctly captured by t+jt+j. then its hybrid time “reaches” T—meaning that there exists (t,j)∈dom(x,u)(t,j)∈ dom (x,u) such that (t,j)∈(t,j)∈ T. This property is used to prove recursive feasibility in the forthcoming Section V-A. For instance, the choice J=1J=1 with t0=2t_0=2, t1=1t_1=1, and t2=0t_2=0 leads to the hybrid prediction horizon =([0,1]×1)∪([1,2]×0) T=([0,1]×\1\)∪([1,2]×\0\), which assures that predictions have either at least 11 second of flow or one jump. This hybrid prediction horizon is depicted in Figure 1. Figure 1: Hybrid prediction horizon for the case of J=1J=1, t0=2t_0=2, t1=1t_1=1, and t2=0t_2=0. Remark I.3 (On Particular Constructions of T) A natural construction of T is one that independently limits the amount of flow and the number of jumps. Similar to discrete time MPC, the parameter N∈1,2,…N∈\1,2,…\ denotes the maximum number of jumps allowed in the prediction. To limit the amount of flow allowed, let δ>0δ>0 and define δNδ N as the flow time bound for prediction. The construction of T given by :=(T,J)∈ℝ≥0×ℕ:maxT/δ,J=N T:=\(T,J)∈R_≥ 0×N: \T/δ,J\=N\ (10) Note that the set T collects pairs (T,J)(T,J) in ℝ≥0×ℕR_≥ 0×N with T no larger than δNδ N seconds and J no larger than N jumps, in this way, defining more than one possible hybrid time for prediction. Another sample construction is given by :=(T,J)∈ℝ≥0×ℕ:T+J∈[μ,μ+1] T:=\(T,J)∈R_≥ 0×N:T+J∈[μ,μ+1]\ (11) which, by properly choosing the parameter μ>0μ>0, compactly captures prediction horizons allowing for arbitrary (but bounded) amount of flow or number of jumps. In fact, given μ>0μ>0, the construction of T in (11) captures all pairs (T,J)(T,J) satisfying μ≤T+J≤μ+1μ≤ T+J≤μ+1 where T∈ℝ≥0T∈R_≥ 0 and J∈ℕJ . Then, the set T in (11) can be interpreted as the region within ℝ≥0×ℕR_≥ 0×N satisfying the inequalities. For instance, for J=0J=0, the set T collects the points (T,0)(T,0) with T such that μ≤T≤μ+1μ≤ T≤μ+1, and so on. I-C Terminal Constraint Set and Hybrid Cost Functional The terminal constraint set X specifies conditions that the state has to satisfy at the end of the hybrid prediction horizon. The set X is assumed to be a subset of Π(C∪D) (C∪ D), which captures the state values from which flow or jump might be possible. Given a solution pair (x,u)(x,u) of ℋH with compact domain and terminal time (T,J)(T,J), let tjj=0J+1\t_j\_j=0^J+1 be the sequence such that dom(x,u)=⋃j=0J([tj,tj+1]×j) dom (x,u)= _j=0^J([t_j,t_j+1]×\j\) where tJ+1=Tt_J+1=T. If x(T,J)∈Xx(T,J)∈ X, then the cost of the solution pair (x,u)(x,u) is characterized by the hybrid cost functional J defined as (x,u) J(x,u) :=(∑j=0J∫tjtj+1LC(x(t,j),u(t,j))t) = ( _j=0^J _t_j^t_j+1L_C(x(t,j),u(t,j))\,dt ) (12) +(∑j=0J−1LD(x(tj+1,j),u(tj+1,j)))+V(x(T,J)) + ( _j=0^J-1L_D(x(t_j+1,j),u(t_j+1,j)) )+V(x(T,J)) where LC:C→ℝ≥0L_C:C→R_≥ 0 is called the flow cost, LD:D→ℝ≥0L_D:D→R_≥ 0 is called the jump cost, and V:X→ℝ≥0V:X→R_≥ 0 is called the terminal cost. Note that J is a functional as it depends on the solution pair (x,u)(x,u). Example I.4 (Bouncing Ball Control (revisited)) Consider the hybrid model of the bouncing ball with a control input in Example I.2, revisited in Example I.5. Since the input affects only the jumps, the flow cost LCL_C can only depend on the state x. Suppose that the control goal is to asymptotically stabilize the bouncing ball to a given energy level c∗≥0c^*≥ 0, where the total energy is given by W in (4). For this case, the flow cost and the terminal cost can be defined using the energy error captured by W(x)−c∗W(x)-c^*. The jump cost LDL_D can be chosen to depend on both the state and the input. Explicit constructions of these functions are given in Example VII.1 in Section VII. I-D Constrained OCP With the terminal constraint set X and the hybrid prediction horizon T defined, the minimization is performed over solution pairs of ℋH with initial condition x∘x_ , terminal condition belonging to X, and terminal hybrid time belonging to T. Problem I.5 Given an initial condition x∘∈ℝnx_ ^n, minimize(x,u)∈^ℋ(x∘) (x,u)∈ S _H(x_ )minimize (x,u) J(x,u) (13) subject to (T,J)∈ (T,J)∈ T x(T,J)∈X x(T,J)∈ X We say that a solution pair (x,u)(x,u) is feasible if it satisfies the constraints of (13) with x(0,0)=x∘x(0,0)=x_ . A feasible solution may neither be maximal nor complete. If, in addition, (x,u)(x,u) minimizes J, then it is said to be optimal. The feasible set X is the set of all x∘x_ ’s with a feasible (x,u)∈^ℋ(x∘)(x,u)∈ S _H(x_ ). The value function ∗:→ℝ≥0 J^*: X→R_≥ 0 is defined as the infimum over all feasible solution pairs at a given initial condition x∘x_ , i.e., ∗(x∘):=inf(x,u)∈^ℋ(x∘)(T,J)∈x(T,J)∈X(x,u)∀x∘∈ J^*(x_ ):= _ subarrayc(x,u)∈ S _H(x_ )\\ (T,J)∈ T\\ x(T,J)∈ X subarray J(x,u) ∀ x_ ∈ X (14) Recall that (T,J)(T,J) is the terminal time of (x,u)(x,u) and that ^ℋ(x∘) S _H(x_ ) is the set of solution pairs to ℋH in (1) from x∘x_ . Remark I.6 (On Explicit Constraints) Note that while the flow set C and jump set D implicitly define mixed state-input constraints, any additional explicit state and input constraints can be embedded in the problem by modifying C and D of the hybrid plant ℋH. For example, the bouncing ball control system in Example I.2 with a maximum height constraint can be captured by redefining the flow set C therein, namely, (x,u)∈ℝ2×ℝ≥0:x1≥0\(x,u) ^2×R_≥ 0:x_1≥ 0\, as C:=(x,u)∈ℝ2×ℝ≥0:x1≥0∩(x,u):x1≤hmaxC:=\(x,u) ^2×R_≥ 0:x_1≥ 0\∩\(x,u):x_1≤ h_ \ for a given maximum height hmax≥0h_ ≥ 0. In fact, additional constraints to be satisfied by the closed-loop system solutions can be incorporated by intersecting the flow set and jump set by sets capturing the new constraints. Similarly, if state and input constraints on the continuous-time control system in Example I.6 must to be satisfied, namely, z∈Zz∈ Z and η∈Uη∈ U for some sets Z⊂ℝnpZ ^n_p and U⊂ℝmzU ^m_z, then the flow and jump sets given in Example I.6 can be simply intersected by Z×UZ× U, and the resulting hybrid control system should be used in the optimization. In fact, solutions obtained with hybrid MPC, in order to exist, need to satisfy these constraints for all hybrid times—and if they are complete, these constraints are always satisfied and viable. On the other hand, as already introduced, constraints on the terminal time and on the terminal state are specified explicitly, respectively, by a terminal constraint set and a hybrid prediction horizon set. Summarizing, given the hybrid plant data (C,f,D,g)(C,f,D,g), Problem I.5 depends on the following data: • The hybrid prediction horizon T; • The flow cost LCL_C, jump cost LDL_D, and terminal cost V; • The terminal constraint set X. We refer to these as the data of the hybrid MPC problem and denote it as (,LC,LD,V,X)( T,L_C,L_D,V,X). I-E Receding Horizon Implementation We have defined all of the ingredients to formulate a receding horizon implementation of hybrid MPC. At each iteration i∈ℕi , the implementation performs the following operations: Step 1) Measure the current state of the plant ℋH; Step 2) Solve Problem I.5 to obtain an optimal solution pair (xi,ui)(x_i,u_i) from the current state; Step 3) Apply the optimal input uiu_i to the plant ℋH to generate the state trajectory xix_i up to hybrid time (Ti+1,Ji+1)∈dom(xi,ui)(T_i+1,J_i+1)∈ dom (x_i,u_i); Step 4) Go to Step 1. The iteration starts from the initial condition x∘x_ , generating the optimal solution pair (x0,u0)(x_0,u_0), which is applied up to (T1,J1)∈dom(x0,u0)(T_1,J_1)∈ dom (x_0,u_0), and from where a new optimization problem is solved from x0(T1,J1)x_0(T_1,J_1), and so on. Note that the hybrid time instances (Ti,Ji)(T_i,J_i) also indicate when the i-th optimization solving Problem I.5 is performed. A hybrid control horizon, denoted c T_c, with the same structure as the hybrid prediction horizon T can be employed to regulate these time instances, in this way controlling the length of the input applied to the plant, within its domain of definition, which can be controlled by the hybrid prediction horizon. This implementation generates a solution pair, extending the one in Definition I.3. Definition I.7 (Hybrid MPC Solution Pair) A solution pair (x,u)(x,u) is said to be generated by the hybrid MPC algorithm if there exists a sequence (Ti,Ji)i=0∞∈dom(x,u)\(T_i,J_i)\_i=0^∞∈ dom (x,u) with (T0,J0)=(0,0)(T_0,J_0)=(0,0) such that the following hold: • The sequence Ti+Jii=0∞\T_i+J_i\_i=0^∞ is strictly increasing and unbounded. • For every i∈ℕi , there exists an optimal solution pair (xi,ui)(x_i,u_i), in the sense of Definition I.3, such that for every (t,j)∈dom(x,u)(t,j)∈ dom (x,u) satisfying t+j∈[Ti+Ji,Ti+1+Ji+1)t+j∈[T_i+J_i,T_i+1+J_i+1), x(t,j) x(t,j) =xi(t−Ti,j−Ji) =x_i(t-T_i,j-J_i) u(t,j) u(t,j) =ui(t−Ti,j−Ji) =u_i(t-T_i,j-J_i) To illustrate the implementation above, consider the hybrid prediction horizon is given in (10), with parameters N and δ and a hybrid control horizon with the same structure as the hybrid prediction horizon, parametrized by Nc∈1,2,…,NN_c∈\1,2,…,N\ and δc∈(0,δ] _c∈(0,δ]. Algorithm 1 below describes, in concrete steps, the solution pair generated by hybrid MPC, as formalized in Definition I.7, for this particular case.555When the jump set is empty, Algorithm 1 simplifies to the standard periodic implementation of continuous-time MPC. Similar observations can be made when the flow set is empty, with Nc=1N_c=1 recovering the standard “one-step ahead” implementation in discrete-time MPC. Algorithm 1 Hybrid MPC Implementation 1:Set i=0i=0. 2:Set initial optimization time (T0,J0)=(0,0)(T_0,J_0)=(0,0). 3:Set the initial condition of the state of ℋH to x∘x_ . 4:while true do 5: Solve Problem I.5 yielding optimal solution (xi,ui)(x_i,u_i). 6: while maxt−Tiδc,j−Ji≤Nc \ t-T_i _c,j-J_i \≤ N_c do 7: Apply uiu_i to ℋH to generate the trajectory x. 8: end while 9: i=i+1i=i+1. 10: (Ti,Ji)=(t,j)(T_i,J_i)=(t,j), the end time of while in line 6. 11: x∘=x(Ti,Ji)x_ =x(T_i,J_i). 12:end while The receding horizon implementation of hybrid MPC is encoded by the inner while loop (Lines 6-8). The initial optimization occurs at time (0,0)(0,0) from the initial state x∘x_ (Lines 1 to 3 set the initial optimization time and the initial condition), and the initial optimal control input u0u_0 is applied until δcNc _cN_c units of ordinary time elapse or NcN_c jumps occur, whichever happens first (Line 6). Upon any of these conditions, Problem I.5 is solved again to find the new input u1u_1, which is again applied for δcNc _cN_c units of ordinary time or until NcN_c jumps occur. This process continues indefinitely, for each element in the input sequence. For the i-th entry in this sequence, the portion of the state trajectory x from (Ti,Ji)(T_i,J_i) to (Ti+1,Ji+1)(T_i+1,J_i+1) corresponds to the optimal state trajectory xix_i computed at time (Ti,Ji)∈dom(x,u)(T_i,J_i)∈ dom (x,u) using input uiu_i. Note that due to the condition in Line 6, (Ti+1−Ti,Ji+1−Ji)(T_i+1-T_i,J_i+1-J_i) is not necessarily constant as a function of i. A solution to Problem I.5 obtained using the implementation in Algorithm 1 is depicted in Figure 2. The parameters chosen are N=4N=4, δ=1δ=1, Nc=2N_c=2, and δc=1 _c=1. The optimal control input u0u_0 is applied until (T1,J1)=(2,1)(T_1,J_1)=(2,1), which is two seconds after (T0,J0)=(0,0)(T_0,J_0)=(0,0) since the hybrid time domain up to that time includes only one jump. The domain of u0u_0 is shown by the dash-dotted purple line, which extends for four seconds of flow time since N=4N=4 and only two jumps occur up to that time. At (T1,J1)(T_1,J_1), Problem I.5 is solved again to find the new optimal control input u1u_1. The resulting optimal control input u1u_1 has a hybrid time domain that, after being shifted forward in hybrid time by (T1,J1)(T_1,J_1), is indicated by solid blue. Since the hybrid time domain of u1u_1 exhibits two jumps without flow in between, the next “optimization event” occurs at (T2,J2)=(2,3)(T_2,J_2)=(2,3), which is two jumps after the prior optimization time (T1,J1)(T_1,J_1). The resulting optimal control input u2u_2 is then applied until (T3,J3)=(4,4)(T_3,J_3)=(4,4), exactly two seconds after (T2,J2)(T_2,J_2). The domain of u2u_2, shifted by (T2,J2)(T_2,J_2), is depicted in red line in Figure 2. Combining this sequence of optimal control inputs, the hybrid time domain of the resulting optimal state trajectory (t,j)↦x(t,j)(t,j) x(t,j) is shown in Figure 3 from (T0,J0)=(0,0)(T_0,J_0)=(0,0) to (T3,J3)(T_3,J_3). Figure 2: Hybrid time domains associated with the hybrid MPC algorithm for the case of N=4N=4 and Nc=2N_c=2. The hybrid time instances (T1,J1)(T_1,J_1), (T2,J2)(T_2,J_2) and (T3,J3)(T_3,J_3) at which Problem I.5 is solved are circled. Figure 3: Hybrid time domain of the optimal trajectory associated to the hybrid time domains in Figure 2. Under Definition I.7, an appropriate notion of asymptotic stability is given in Section VI. In general, asymptotic stability can be certified by using the value function ∗ J^*, without any assumptions on persistence of jumps or flows [2, Theorem 6.3], provided the cost functions defining J have basic positive definiteness properties. With persistence of jumps or flows, these requirements can be relaxed, as detailed in Section VI. Remark I.8 (About Discretization) Problem I.5 is formulated for the hybrid plant ℋH in (1). Note that the flows of ℋH are not explicitly discretized in the implementation given in Algorithm 1. Such a discretization can be made explicit by choosing a discretization method for x˙=f(x,u) x=f(x,u) and defining solutions to the resulting system on discretized hybrid time domains—indeed, they are defined over hybrid time domains. Discretization for hybrid systems for the purposed of hybrid MPC are presented in [31], along with a method to solve Problem I.5 with discretized flows; see also [30]. Remark I.9 (Computing a Solution to Problem I.5) Computation of an optimal solution to Problem I.5 is a nontrivial task. In certain cases, Problem I.5 can be solved by converting it into a finite-dimensional nonlinear program. The development of general numerical methods to solve Problem I.5 is the current object of research, and can take the form of the maximum principle—see [32] and the references therein. The approaches in [31] and [30] solve Problem I.5 with discretized flows. They algorithms therein use adaptations of off-the-shelf optimization solvers for mixed-integer nonlinear programs, with potentially large computational times. Note that [4] provide conditions under which the optimal cost can be continuously approximated numerically. IV Main Assumptions We list the basic assumptions imposed on Problem I.5 to ensure feasibility and certify asymptotic stability of a given closed set ⊂X A⊂ X of interest. The required assumptions resemble those typically assumed in continuous-time and discrete-time MPC, when generalized to the set stabilization problem.666As mentioned in Section I-A, hybrid systems typically have state variables that do not necessarily converge to equilibria (e.g., timers and logic variables). As such, stability theory for hybrid systems considers sets rather than singletons [19, Ch. 3]. Combined with the hybrid prediction horizon defined in Definition I.2, the forthcoming assumptions guarantee most of the properties required to establish asymptotic stability, with the exception of positive definiteness of the value function, which is studied in depth in the forthcoming Sections V-D and V-E, as it can be achieved in multiple ways. The following assumptions assert basic positive definiteness properties and bounds on the cost functions. These properties are used in establishing positive definiteness of the value function and asymptotic stability of the closed-loop system resulting from using hybrid MPC. Assumption IV.1 Given a hybrid plant ℋ=(C,f,D,g)H=(C,f,D,g), a closed set ⊂ℝn A ^n, flow cost LCL_C, and jump cost LDL_D, (W1) There exists a class-∞K_∞ function αC _C such that LC(x,u)≥αC(|x|)L_C(x,u)≥ _C( |x |_ A) for each (x,u)∈C(x,u)∈ C. (W2) There exists a class-∞K_∞ function αD _D such that LD(x,u)≥αD(|x|)L_D(x,u)≥ _D( |x |_ A) for each (x,u)∈D(x,u)∈ D. Assumption IV.2 Given a closet set ⊂ℝn A ^n, a terminal constraint set X, and a terminal cost function V, there exists ε>0 >0 and a class-K function α such that V(x)≤α(|x|)V(x)≤α( |x |_ A) for each x∈X∩(+ε)x∈ X∩( A+ ). The key stabilizing ingredient of our hybrid MPC algorithm is given by the following familiar CLF-like assumption requiring the existence of a (static) state-feedback pair κ=(κC,κD)κ=( _C, _D). Below, forward pre-invariance of X means that every maximal closed-loop solution with initial state in X is complete and stays in X [14, Definition 3.1], and forward completeness of X means that for every point X there exists a complete solution. A weaker notion of invariance is weak forward invariance, which is used in the next section and simply requires that from each point in X, there exists a maximal and complete solution that stays in X. Assumption IV.3 Given a hybrid plant ℋ=(C,f,D,g)H=(C,f,D,g), a closet set ⊂ℝn A ^n, flow cost LCL_C, jump cost LDL_D, terminal constraint set X, and terminal cost V, there exists a state-feedback law κ=(κC,κD)κ=( _C, _D) such that the terminal constraint set X is forward pre-invariant and forward complete for the hybrid system ℋκH_κ in (9). Moreover, the terminal cost V is differentiable on an open set containing cl(X∩Cκ) cl (X∩ C_κ), and ⟨∇V(x),fκ(x)⟩ ∇ V(x),f_κ(x) ≤−LC(x,κC(x)) ≤-L_C(x, _C(x)) ∀x∈ ∀ x∈ X∩Cκ, X∩ C_κ, (15) V(gκ(x))−V(x) V(g_κ(x))-V(x) ≤−LD(x,κD(x)) ≤-L_D(x, _D(x)) ∀x∈ ∀ x∈ X∩Dκ X∩ D_κ The condition during flow in (15) resembles the one the continuous-time MPC literature. Therefore, it is possible to satisfy this condition, at least locally, using standard techniques relying on linearization in the special case when the flow cost and terminal cost are quadratic. The same is possible for the condition at jumps in (15). When LC∘κCL_C _C (respectively, LD∘κD)L_D _D)) is allowed to be zero, the terminal cost V can be viewed as a Lyapunov function with the feedback κ, provided the trajectories of the hybrid closed-loop system ℋκH_κ have persistent jumps (respectively, flows). Remark IV.4 (About Existence of Solutions) Any MPC-type algorithm would only be able to issue a control input when the optimization problem at the current state has a solution. Existence of a solution to Problem I.5 from a feasible initial condition x∘x_ follows directly from [4] under standard regularity conditions,777Though the results in this paper assume that optimal (hence, feasible) solutions exist, for the integral in the hybrid cost functional J in (12) to exist, the composition LC∘(x,u)L_C (x,u) needs to be (Lebesgue) measurable. or from [20]. In particular, the approach in [4] rewrites the problem into the Mayer form minimizez∈^ℋM z∈ S _H_Mminimize (z) J(z) (16) subject to (z(0,0),(T,J),z(T,J))∈(x∘,0)×(X×ℝ) \!\!\!\!(z(0,0),(T,J),z(T,J))\!∈\!\(x_ ,0)\× T×(X×R) where z=(x,ℓ)z=(x, ) with ℓ representing the running cost and ℋMH_M is an autonomous system arising from the conversion to the Mayer form, and studying its existence of solutions—see [4, Section 6] for examples constructing the Mayer form system ℋMH_M. More precisely, [4, Theorem 8] ensures existence of solutions to Problem I.5 from the feasible set X when J is lower semicontinuous and X is closed. V Properties of the Optimal Control Problem This section presents the properties pertinent to Problem I.5 that are used to show asymptotic stability of A. V-A Forward Invariance of the Feasible Set The initial results are in the same spirit as those in [2], stated in more generality. Proposition V.1 If there exists a state-feedback law κ such that the terminal constraint set X is weakly forward invariant for the hybrid system ℋκH_κ in (9), then X⊂X⊂ X. Proof: Since for each point x∘x_ in X there exists a maximal and complete solution, each trajectory to ℋκH_κ starting from X stays in X. The domain of each such trajectory intersects with the prediction horizon T, due to the structure of the hybrid prediction horizon in Definition I.2. Hence, x∘x_ belongs to X. ∎ Proposition V.2 Suppose that there exists a state-feedback law κ such that the terminal constraint set X is forward pre-invariant and forward complete for the hybrid system ℋκH_κ in (9). Then, each feasible solution pair (x,u)(x,u) to ℋH satisfies x(t,j)∈x(t,j)∈ X for each (t,j)∈dom(x,u)(t,j)∈ dom (x,u). Proof: The proof relies on the extension of the solution pair (x,u)(x,u) from the terminal point by aid of the feedback κ. That is, we take a solution pair (x′,u′)(x ,u ) generated by the feedback κ starting from x(T,J)∈Xx(T,J)∈ X, where (T,J)(T,J) is the terminal time of (x,u)(x,u). That is, we let (z(s,i),v(s,i)):=(x(s,i),u(s,i))(z(s,i),v(s,i)):=(x(s,i),u(s,i)) for all (s,i)(s,i) with s+i<T+Js+i<T+J, and (z(s+T,i+J),v(s+T,i+J)):=(x′(s,i),u′(s,i))(z(s+T,i+J),v(s+T,i+J)):=(x (s,i),u (s,i)), and observe that (z,v)(z,v) is a solution pair to ℋH. Then, we consider the solution pair (z,v)(z,v) from (t,j)∈dom(z,v)(t,j)∈ dom (z,v) onwards, which is itself a solution pair, say (z′,v′)(z ,v ). We notice that from (T−t,J−j)∈dom(z′,v′)(T-t,J-j)∈ dom (z ,v ) onwards, z stays in the terminal constraint set X. Finally, we note that there must exist (s,i)∈dom(z′,v′)(s,i)∈ dom (z ,v ) after time (T−t,J−j)∈dom(z′,v′)(T-t,J-j)∈ dom (z ,v ) that belongs to the prediction horizon T. Hence, the truncation of (z′,v′)(z ,v ) at time (s,i)(s,i) is a feasible solution pair to ℋH, since (s,i)∈(s,i)∈ T and z(s,i)∈Xz(s,i)∈ X. ∎ Proposition V.1 and V.2 show that the terminal constraint set is contained in the feasible set, and recursive feasibility is maintained with the moving horizon implementation, respectively. The conditions in Proposition V.1 and the inequalities in Assumption IV.3 ensure an upper bound on the value function ∗ J^* over the terminal constraint set X, in terms of the terminal cost V. V-B Continuity of the Value Function Combining the property of X established in Proposition V.1 with the bounds obtained in Assumption IV.3 is the first step towards establishing ∗ J^* as a Lyapunov function for the hybrid MPC algorithm. The terminal cost upper bounds not only the value function on the terminal constraint set, but also the cost of feasible solutions generated by κ. To establish this result, we exploit similar techniques to those in the standard MPC literature, see, e.g., [24] and [21, Section 5.3]. Lemma V.3 Suppose that Assumption IV.3 holds. Then, 1. ∗ J^* and V satisfy ∗(x∘)≤V(x∘)∀x∘∈X J^*(x_ )≤ V(x_ ) ∀ x_ ∈ X (17) 2. For each x∘∈Xx_ ∈ X and each feasible solution pair (x,u)(x,u) starting from x∘x_ generated by the state-feedback law κ, ∗ J^* and J satisfy ∗(x∘)≤(x,u)≤V(x∘) J^*(x_ )≤ J(x,u)≤ V(x_ ) (18) Proof: Since Assumption IV.3 holds, Proposition V.1 implies that X⊂X⊂ X. Let (x,u)(x,u) be a feasible solution to Problem I.5 with x∘∈Xx_ ∈ X and, without loss of generality, let (T,J)(T,J) be the terminal time of (x,u)(x,u) and sjj=0J\s_j\_j=0^J be the associated sequence of generalized jump times. Then, using (12), (x,u)=(∑j=0J∫sjsj+1LC(x(t,j),κC(x(t,j)))t)+(∑j=0J−1LD(x(sj+1,j),κD(x(sj+1,j))))+V(x(T,J)) J(x,u)= ( _j=0^J _s_j^s_j+1L_C(x(t,j), _C(x(t,j)))\,dt )\\ + ( _j=0^J-1L_D(x(s_j+1,j), _D(x(s_j+1,j))) )+V(x(T,J)) Since X is forward pre-invariant for ℋκH_κ, x remains in X and, by (15), (x,u)≤−(∑j=0J∫sjsj+1dVdt(x(t,j))dt+∑j=0J−1(V(x(sj+1,j+1))−V(x(sj+1,j))))+V(x(T,J))=−(V(x(T,J))−V(x(0,0)))+V(x(T,J))=V(x(0,0))=V(x∘) J(x,u)≤- ( _j=0^J _s_j^s_j+1 dVdt(x(t,j))\,dt .\\ + . _j=0^J-1 (V(x(s_j+1,j+1))-V(x(s_j+1,j)) ) )+V(x(T,J))\\ =-(V(x(T,J))-V(x(0,0)))+V(x(T,J))\\ =V(x(0,0))=V(x_ ) Item 2 follows from the definition of ∗ J^* in (14) since the value of ∗ J^* is the result of minimizing the cost functional over all such feasible solution pairs. Item 1 follows from the fact that the set X is forward complete and that the cost obtained by any optimal solution cannot be larger than the cost for the solution generated using κ. ∎ The following continuity property of ∗ J^* is a direct consequence of item 1 in Lemma V.3. Proposition V.4 Under Assumption IV.3, for each ϵ>0ε>0, there exists δ>0δ>0 such that ∗(x)≤ϵ J^*(x)≤ε for each x∈x∈ X satisfying |x|≤δ |x |_ A≤δ. V-C Decreasing Properties of the Value Function Next, we show that ∗ J^* is upper bounded by a nonincreasing function along optimal trajectories, which decreases during flows (respectively, at jumps) if LCL_C (respectively, LDL_D) satisfies the lower bound in (W1) (respectively, in (W2)). The proof follows the steps used in the standard MPC literature, see, e.g., [24, Section 3.4] and [21, Lemma 5.4]. Lemma V.5 Suppose Assumption IV.3 holds. Then, for each optimal solution (x,u)(x,u) and each (t,j)∈dom(x,u)(t,j)∈ dom (x,u), ∗(x(t,j))≤∗(x(0,0))−∑i=0j∫sisi+1LC(x(s,i),u(s,i))s−∑i=0j−1LD(x(si+1,i),u(si+1,i)) -10.84006pt J^*(x(t,j))≤ J^*(x(0,0))- _i=0^j _s_i^s_i+1L_C(x(s,i),u(s,i))\,ds\\ - _i=0^j-1L_D(x(s_i+1,i),u(s_i+1,i)) where sii=0j+1\s_i\_i=0^j+1 is the sequence of generalized jump times of the truncation of (x,u)(x,u) up to time (t,j)(t,j). Proof: Given the optimal solution (x,u)(x,u), we recall the feasible solution pair derived in the proof of Lemma V.2 that starts from x(t,j)x(t,j). Call this solution pair (z,v)(z,v), and note that after time (T−t,J−j)∈dom(z,v)(T-t,J-j)∈ dom (z,v), (z,v)(z,v) corresponds to a solution generated by the feedback κ, say (x′,u′)(x ,u ), where (T,J)(T,J) is the terminal time of (x,u)(x,u). Then, observe that ∗(x(t,j))≤(z,v) J^*(x(t,j))≤ J(z,v) as (z,v)(z,v) is not optimal. The following holds: ∗(x(t,j))≤(z,v)=(x,u)−∑i=0j∫sisi+1LC(x(s,i),u(s,i))s−∑i=0j−1LD(x(si+1,i),u(si+1,i))−V(x(t,j))+(x′,u′) J^*(x(t,j))≤ J(z,v)= J(x,u)\\ - _i=0^j _s_i^s_i+1L_C(x(s,i),u(s,i))\,ds\\ - _i=0^j-1L_D(x(s_i+1,i),u(s_i+1,i))\\ -V(x(t,j))+ J(x ,u ) The bound (z,v) J(z,v) follows from the fact that (z,v)(z,v) starts from x(t,j)x(t,j) and that (z,v)(z,v) is not optimal. The equality captures the following fact: the cost of (x,u)(x,u), which is up to (T,J)(T,J), plus the cost of (x′,u′)(x ,u ) is equal to the cost of (x,u)(x,u) up to (t,j)(t,j) plus the cost of (z,v)(z,v). By solving for the cost of (z,v)(z,v) from this relationship we obtain the equality above. Finally, since x(t,j)=x′(0,0)x(t,j)=x (0,0), the term −V(x(t,j))+(x′,u′)-V(x(t,j))+ J(x ,u ) is nonpositive by Lemma V.3, leading to the desired result as (x,u)=∗(x(0,0)) J(x,u)= J^*(x(0,0)) since (x,u)(x,u) is optimal. ∎ V-D Solution-dependent Conditions for Positive Definiteness of the Value Function To ensure that the value function is positive definite and bounded from below by a positive definite function, we start by assuming the existence of a positive definite function α such that an appropriate combination of the following conditions holds for every optimal solution pair (x,u)(x,u): P1) there exist (t,j)(t,j), (t′,j′)∈dom(x,u)(t ,j )∈ dom (x,u) with t+j≤t′+j′t+j≤ t +j such that t′−t+j′−j≥α(|x(0,0)|)t -t+j -j≥α( |x(0,0) |_ A) and |x(s,i)|≥α(|x(0,0)|) |x(s,i) |_ A≥α( |x(0,0) |_ A) for all (s,i)∈dom(x,u)(s,i)∈ dom (x,u) satisfying t+j≤s+i≤t′+j′t+j≤ s+i≤ t +j ; P2) there exist (t,j),(t′,j′)∈dom(x,u)(t,j),(t ,j )∈ dom (x,u) with t+j≤t′+j′t+j≤ t +j such that t′−t≥α(|x(0,0)|)t -t≥α( |x(0,0) |_ A) and |x(s,i)|≥α(|x(0,0)|) |x(s,i) |_ A≥α( |x(0,0) |_ A) for all (s,i)∈dom(x,u)(s,i)∈ dom (x,u) satisfying t+j≤s+i≤t′+j′t+j≤ s+i≤ t +j ; P3) |x(t,j)|≥α(|x(0,0)|) |x(t,j) |_ A≥α( |x(0,0) |_ A) for some (t,j)∈dom(x,u)(t,j)∈ dom (x,u) such that (t,j+1)∈dom(x,u)(t,j+1)∈ dom (x,u); P4) |x(T,J)|≥α(|x(0,0)|) |x(T,J) |_ A≥α( |x(0,0) |_ A), where (T,J)(T,J) is the terminal time of (x,u)(x,u); P5) There exist an open neighborhood U of A and a continuous function σ:ℝ≥0→ℝ≥0σ:R_≥ 0→R_≥ 0 such that |f(x,u)|≤σ(|x|)|f(x,u)|≤σ ( |x |_ A ) for all (x,u)∈C(x,u)∈ C such that x∈x∈ U. Section V-E provides sufficient conditions for these properties. Note that P2) implies P1), and that P3) implies P1). Theorem V.6 (Positive Definiteness of the Value Function) Given a hybrid plant ℋ=(C,f,D,g)H=(C,f,D,g) as in (1), the data (,LC,LD,V,X)( T,L_C,L_D,V,X) defining Problem I.5, and a closed set ⊂ℝn A ^n, if there exists a positive definite function α:ℝ≥0→ℝ≥0α:R_≥ 0→R_≥ 0 such that one of the following conditions holds: 1. Every optimal solution pair (x,u)(x,u) satisfies P1), and LC:C→ℝ≥0L_C:C→R_≥ 0 and LD:D→ℝ≥0L_D:D→R_≥ 0 are positive definite with respect to A; 2. Every optimal solution pair (x,u)(x,u) satisfies P2) and LC:C→ℝ≥0L_C:C→R_≥ 0 is positive definite with respect to A; 3. Every optimal solution pair (x,u)(x,u) satisfies P3) and LD:D→ℝ≥0L_D:D→R_≥ 0 is positive definite with respect to A; 4. Every optimal solution pair (x,u)(x,u) satisfies P4) and V:X→ℝ≥0V:X→R_≥ 0 is positive definite with respect to A; 5. Every optimal solution pair (x,u)(x,u) satisfies P2) or P4), and LC:C→ℝ≥0L_C:C→R_≥ 0 and V:X→ℝ≥0V:X→R_≥ 0 are positive definite with respect to A; 6. Every optimal solution pair (x,u)(x,u) satisfies P3) or P4), and LD:D→ℝ≥0L_D:D→R_≥ 0 and V:X→ℝ≥0V:X→R_≥ 0 are positive definite with respect to A; 7. Every optimal solution pair (x,u)(x,u) satisfies one among P1)-P5), and LC:C→ℝ≥0L_C:C→R_≥ 0, LD:D→ℝ≥0L_D:D→R_≥ 0, and V:X→ℝ≥0V:X→R_≥ 0 are positive definite with respect to A; then there exists a positive definite function α∗:ℝ≥0→ℝ≥0α^*:R_≥ 0→R_≥ 0 such that the value function satisfies ∗(x∘)≥α∗(|x∘|) J^*(x_ )≥α^*( |x_ |_ A) (19) for each x∘∈x_ ∈ X such that an optimal solution pair (x,u)∈^ℋ(x∘)(x,u)∈ S _H(x_ ) exists. Furthermore, the function α∗α^* is class-∞K_∞ if the functions LCL_C and LDL_D satisfy (W1) and (W2), respectively, and α is class-∞K_∞. Proof: Pick x∘∈x_ ∈ X and suppose that there exists an optimal solution pair (x,u)(x,u) starting from x∘x_ . Let sjj=0J+1\s_j\_j=0^J+1 be the sequence of generalized jump times of (x,u)(x,u), namely, it satisfies dom(x,u)=∪j=0J([sj,sj+1]×j) dom (x,u)= _j=0^J([s_j,s_j+1]×\j\). Therefore, we have ∗(x∘)=(x,u)=(∑j=0J∫sjsj+1LC(x(t,j),u(t,j))t)+(∑j=0J−1LD(x(sj+1,j),u(sj+1,j)))+V(x(T,J)) J^*(x_ )= J(x,u)= ( _j=0^J _s_j^s_j+1L_C(x(t,j),u(t,j))\,dt )\\ + ( _j=0^J-1L_D(x(s_j+1,j),u(s_j+1,j)) )+V(x(T,J)) Next, we consider the cases in items 1-7. Now, suppose that item 1 holds. Using the fact that LCL_C and LDL_D are positive definite with respect to A, V takes on nonnegative values, the properties of the solution (x,u)(x,u) for hybrid times between (t,j)(t,j) and (t′,j′)(t ,j ) coming from item 1 with positive definite function α obtained from P1), there exists a positive definite function α~:ℝ≥0→ℝ≥0 α:R_≥ 0→R_≥ 0 such that888We use s instead of t as integration variable to simplify notation. ∗(x∘) J^*(x_ ) ≥∫t′α~(|x(0,0)|)s+∑j′α~(|x(0,0)|) ≥ _t^t α( |x(0,0) |_ A)\,ds+ _j^j α( |x(0,0) |_ A) ≥α(|x∘|)α~(|x∘|)=:α∗(|x∘|) ≥α( |x_ |_ A) α( |x_ |_ A)=:α^*( |x_ |_ A) When item 2 holds, similarly, using the fact that LCL_C is positive definite with respect to A, the properties in item 2, and the fact that V is nonnegative, it follows that there exists a positive definite function α~:ℝ≥0→ℝ≥0 α:R_≥ 0→R_≥ 0 such that ∗(x∘) J^*(x_ ) ≥∫t′α~(|x(0,0)|)s ≥ _t^t α( |x(0,0) |_ A)\,ds ≥(t′−t)α¯(|x∘|)12 ≥(t -t) α( |x_ |_ A) 12 ≥α(|x∘|)α~(|x∘|)=:α∗(|x∘|) ≥α( |x_ |_ A) α( |x_ |_ A)=:α^*( |x_ |_ A) The case when item 3 holds follows similarly. The case when item 4 holds is immediate due to V being positive definite, from where there exists a positive definite function α∗:ℝ≥0→ℝ≥0α^*:R_≥ 0→R_≥ 0 satisfying V(x(T,J))≥α∗(|x(T,J)|)≥α∗(|x∘|)V(x(T,J))≥α^*( |x(T,J) |_ A)≥α^*( |x_ |_ A), which is a lower bound for ∗(x∘) J^*(x_ ). The cases in items 5, 6, and 7 under conditions P1)-P4) follow directly from combinations of the steps above. The case in item 7 under condition P5) is shown next. Let T:=mint∈ℝ≥0:(t,0)∈T:= \t∈R_≥ 0:(t,0)∈ T\, which is positive from the construction in Definition I.2. With U and σ (assumed to be p.d. without loss of generality) coming from P5), fix ϵ>0ε>0 such that |x|≤ϵ |x |_ A≤ε implies x∈x∈ U. Define the function φ:[0,ϵ]→ℝ≥0 :[0,ε]→R_≥ 0 as φ(r):=maxr′∈[r/2,r]σ(r′) (r):= _r ∈[r/2,r]σ(r ) for all r∈[0,ϵ]r∈[0,ε]. Note that φ is continuous. This property can be shown via Berge’s maximum theorem [6, Theorem 1.4.16], similar to the proof of Lemma A.1, by showing that the set-valued mapping associating the interval [r/2,r][r/2,r] with each r∈[0,ϵ]r∈[0,ε] is upper and lower semicontinuous.999A set-valued mapping F:ℝn⇉ℝmF:R^n ^m is upper semicontinuous at a point x∈domFx∈ dom F with F(x)F(x) compact if for any ϵ>0ε>0, there exists δ>0δ>0 such that F(x+δ)⊂F(x)+ϵF(x+ )⊂ F(x)+ [6, Definition 1.4.1]. It is said to be lower semicontinuous at a point x∈domFx∈ dom F if for any y∈F(x)y∈ F(x) and for any sequence xii∈ℕ∈domF\x_i\_i ∈ dom F converging to x, there exists a sequence yii∈ℕ\y_i\_i with yi∈F(xi)y_i∈ F(x_i) for all i∈ℕi , which converges to y [6, Definition 1.4.1]. These notions should not be confused with upper and lower semicontinuity of (extended) real-valued functions. Take any r∈(0,ϵ]r∈(0,ε]. Let (x,u)∈ℋ(x,u)∈ S _H be a feasible solution pair from x∘x_ such that |x∘|=r |x_ |_ A=r. Define the scalar t′(r):=minr/(2φ(r)),T>0t (r):= \r/(2 (r)),T\>0. Observe that for all t<t′(r)t<t (r) satisfying (t,0)∈dom(x,u)(t,0)∈ dom (x,u), we have |x(t,0)|>r/2 |x(t,0) |_ A>r/2; the converse would imply t′(r)φ(r)>r/2t (r) (r)>r/2. Therefore, from the p.d. property of LCL_C, there exists a p.d. function α~C α_C such that ∫0tLC(x(s,0),u(s,0))s≥∫0tα~C(|x(s,0)|)s≥tα~C(r/2)∀(t,0)∈dom(x,u)∩[0,t′(r)]×0, _0^tL_C(x(s,0),u(s,0))\,ds≥ _0^t α_C( |x(s,0) |_ A)\,ds\\ ≥ t α_C(r/2)\\ ∀(t,0)∈ dom (x,u)∩[0,t (r)]×\0\, (20) and, if there exists t≤t′(r)t≤ t (r) so that (t,1)∈dom(x,u)(t,1)∈ dom (x,u), then LD(x(t,0),u(t,0))≥α~D(|x(t,0)|)≥α~D(r/2)L_D(x(t,0),u(t,0))≥ α_D( |x(t,0) |_ A)≥ α_D(r/2) (21) for some p.d. function α~D α_D, from the p.d. property of LDL_D. Suppose there exists no t≤t′(r)t≤ t (r) that satisfies (t,1)∈dom(x,u)(t,1)∈ dom (x,u). Then, because t′(r)≤Tt (r)≤ T, it must be that (t′(r),0)∈dom(x,u)(t (r),0)∈ dom (x,u), and hence by (20), we have from (12) that (x,u)≥t′(r)α~C(r/2) J(x,u)≥ t (r) α_C(r/2). On the other hand, if t≤t′(r)t≤ t (r) exists so (t,1)∈dom(x,u)(t,1)∈ dom (x,u), then (21) implies (x,u)≥α~D(r/2) J(x,u)≥ α_D(r/2). Thus, it follows that (x,u)≥mint′(r)α~C(r/2),α~D(r/2)=:α~(r)>0 J(x,u)≥ \t (r) α_C(r/2), α_D(r/2)\=: α(r)>0 (22) for all feasible (x,u)∈ℋ(x,u)∈ S _H such that |x∘|=r |x_ |_ A=r. Note that α~(r) α(r) depends continuously on r on (0,δ](0,δ] since t′(r)t (r) depends continuously on r on (0,δ](0,δ]. Moreover, limr→0α~(r)=0 _r→ 0 α(r)=0. Now, let (x,u)∈ℋ(x,u)∈ S _H be a feasible solution pair from x∘x_ such that |x∘|≥ϵ |x_ |_ A≥ε. Since x can reach +(ϵ/2) A+(ε/2)B no sooner than (t′(ϵ),0)(t (ε),0) by flowing, a similar analysis shows that (22) holds with ϵε instead of r. Combining these bounds with the fact that α~(r) α(r) depends continuously on r on [0,ϵ][0,ε] and approaches zero as r tends to zero, it follows that (x,u)≥α∗(|x(0,0)|) J(x,u)≥α^*( |x(0,0) |_ A) for every feasible solution pair (x,u)∈ℋ(x,u)∈ S _H, where the function α∗:ℝ≥0→ℝ≥0α^*:R_≥ 0→R_≥ 0 is defined as α∗(ϵ):=0α^*(ε):=0 if ϵ=0ε=0 and α∗(ϵ):=α~(ϵ)α^*(ε):= α(ε) if ϵ>0ε>0. Consequently, ∗(x∘)≥α∗(|x∘|) J^*(x_ )≥α^*( |x_ |_ A) for all x∘∈x_ ∈ X. ∎ Remark V.7 The solution-dependent conditions in Theorem V.6 guarantees required properties to guarantee positive definiteness of the value function. Conditions P1)-P4) therein relax positive definiteness properties of the stage costs and terminal cost, in particular, to allow for the stage cost for flows or jumps to be zero, which permits the user to not associate a cost to flows or jumps, respectively. For instance, for solution pairs with persistent jumps, item 3 relaxes positive definiteness of the flow cost LCL_C and terminal cost V by assuming a property on optimal solution pairs (x,u)(x,u) originating away from A – see condition P3). This property guarantees that x is away from A at a jump time, which ensures that the cost of (x,u)(x,u) is nonzero. A similar relaxation is possible for the jump cost LDL_D, via item 2, through the use of P2). Note that the conditions in item 2 relax those in item 1 by requiring the flow cost to be positive definite when flows are persistent, as captured by P2). A similar comment applies to item 3. Item 7 exploits condition P5) to establish the lower bound, similar to results in the standard MPC literature, at the price of requiring positive definiteness of LCL_C, LDL_D, and V. Note that P5) implies the existence of a uniform upper bound on the magnitude of the velocity of the state trajectories from nearby A, and that is satisfied when f is continuous, A is compact, and C=C′×UC=C × U for some closed set C′⊂ℝnC ^n and some compact set U⊂ℝmU ^m, which corresponds to the typical assumptions on state and input constraints in the MPC literature. Before stating solution-independent sufficient conditions for P1)-P4), we revisit the sample-and-hold control example. Example V.8 (Sample-and-Hold Control (revisited)) Consider the digital control system in Example I.6 and suppose that the function f~ f is linear, i.e., f~(z,η)=Az+Bη f(z,η)=Az+Bη for some matrices A and B. Let =0×0×[0,Ts] A=\0\×\0\×[0,T_s]. Along the first period of flow, a solution pair (x,u)(x,u) is given by τs(t,0)=t+τs(0,0) _s(t,0)=t+ _s(0,0) and [z(t,0)η(t,0)]=exp(A~t)[z(0,0)η(0,0)],A~:=[AB00] bmatrixz(t,0)\\ η(t,0) bmatrix= ( At) bmatrixz(0,0)\\ η(0,0) bmatrix, A:= bmatrixA&B\\ 0&0 bmatrix Note that the function t↦exp(A~t)t ( At) is continuous and exp(A~t) ( At) is nonsingular for each t≥0t≥ 0. Moreover, regardless of the choice of the horizon T, due to the timer dynamics, the sequence tjj=0J+1\t_j\_j=0^J+1 defining dom(x,u) dom (x,u) is such that t1≤Ts−τs(0,0)≤Tst_1≤ T_s- _s(0,0)≤ T_s. Since singular values vary continuously in the matrix entries, there exists c>0c>0 such that |x(t,0)|=|(z(t,0),η(t,0))|≥c|(z(0,0),η(0,0))|=|x(0,0)| |x(t,0) |_ A=|(z(t,0),η(t,0))|\\ ≥ c|(z(0,0),η(0,0))|= |x(0,0) |_ A for all (t,0)∈dom(z,u)(t,0)∈ dom (z,u). Hence, |x(t1,0)|≥c|x(0,0)| |x(t_1,0) |_ A≥ c |x(0,0) |_ A, and P3) holds with α(s):=csα(s):=cs for each s≥0s≥ 0. V-E Sufficient Conditions for P1-P4 P1-P4 can be verified via infinitesimal conditions if the flows of ℋH satisfy a Lyapunov-like inequality that limit the rate of convergence to A and prohibit finite-time convergence, or if appropriate local boundedness conditions hold. Proposition V.9 Given a hybrid plant ℋ=(C,f,D,g)H=(C,f,D,g) as in (1), the data (,LC,LD,V,X)( T,L_C,L_D,V,X) defining Problem I.5, and a closed set ⊂ℝn A ^n, suppose that one of the following conditions holds: 1. Given a function V~:ℝn→ℝ≥0 V:R^n→R_≥ 0 that is continuously differentiable101010This condition could as well be formulated for a locally Lipschitz function V~ V through the use of the generalized Clarke derivative. on an open set containing cl(Π(C)) cl ( (C)), suppose that there exist class- K functions α~1 α_1 and α~2 α_2, and constants λ∈ℝλ and ε>0 >0 such that α~1(|x|)≤V~(x)≤α~2(|x|)∀x∈Π(C):|x|≤ε, α_1( |x |_ A)≤ V(x)≤ α_2( |x |_ A) ∀ x∈ (C): |x |_ A≤ , (23) ⟨∇V~(x),f(x,u)⟩≥λV~(x)∀(x,u)∈C:|x|≤ε ∇ V(x),f(x,u) ≥λ V(x) ∀(x,u)∈ C: |x |_ A≤ (24) 2. Suppose that there exist a continuous function σ:(0,∞)→[0,∞)σ:(0,∞)→[0,∞) and ε>0 >0 satisfying |f(x,u)|≤σ(|x|)∀(x,u)∈C:0<|x|≤ε|f(x,u)|≤σ ( |x |_ A ) ∀(x,u)∈ C:0< |x |_ A≤ (25) Then, there exists a class- K function α such that every feasible solution pair (x,u)(x,u) to ℋH satisfies P2), P3), or P4). Furthermore, if, in addition, a) T is such that i) there exists c>0c>0 s.t. T+J≥cT+J≥ c for all (T,J)∈(T,J)∈ T, then there exists a class- K function α such that every feasible solution pair to ℋH satisfies P1); b) T is such that item a).b)i) holds, i) there exists a positive definite function α~D α_D such that |g(x,u)|≥α~D(|x|)∀(x,u)∈D |g(x,u) |_ A≥ α_D( |x |_ A) ∀(x,u)∈ D (26) and i) there exists ϵ>0ε>0 such that each feasible pair flows for at least ϵε seconds, then P2) or P4) holds for each feasible solution pair to ℋH if α~D(r)≥r α_D(r)≥ r for each r≥0r≥ 0, or there exists J¯∈ℕ J such that J≤J¯J≤ J for each (T,J)∈(T,J)∈ T. The proof of Proposition V.9 uses the following lemmas. These lemmas involve the data (C,f,D,g)(C,f,D,g) of ℋH and the closed set A. Their proofs are in Appendix A. Lemma V.10 Suppose that item 1 in Proposition V.9 holds. Then, there exists a class- K function α such that every solution pair (x,u)(x,u) to ℋH is such that, for each T satisfying (T,0)∈dom(x,u)(T,0)∈ dom (x,u), |x(t,0)|≥α(|x(0,0)|) |x(t,0) |_ A≥α( |x(0,0) |_ A) for all (t,0)∈dom(x,u)∩([0,T]×0)(t,0)∈ dom (x,u)∩([0,T]×\0\). Lemma V.11 Suppose that item 2 in Proposition V.9 holds. Then, there exists a class- K function α such that every solution pair (x,u)(x,u) to ℋH satisfies |x(t,0)|≥α(|x(0,0)|) |x(t,0) |_ A≥α( |x(0,0) |_ A) for all t∈[0,α(|x(0,0)|)]t∈[0,α( |x(0,0) |_ A)] such that (t,0)∈dom(x,u)(t,0)∈ dom (x,u). We are now ready to present the proof of Proposition V.9. Proof: If either item 1 or item 2 holds, an application of Lemma V.10 or Lemma V.11 implies that there exists a class- K function α′α such that every solution pair (x,u)(x,u) to ℋH satisfies the following: for each T such that (T,0)∈dom(x,u)(T,0)∈ dom (x,u), we have |x(t,0)|≥α′(|x(0,0)|) |x(t,0) |_ A≥α ( |x(0,0) |_ A) for all t∈[0,minT,α′(|x(0,0)|)]t∈[0, \T,α ( |x(0,0) |_ A)\] such that (t,0)∈dom(x,u)(t,0)∈ dom (x,u). Take a feasible solution pair (x,u)(x,u). We have the following cases: I) If the solution jumps at (t1,0)(t_1,0) for some t1≤α′(|x(0,0)|)t_1≤α ( |x(0,0) |_ A), then (t1,1)∈dom(x,u)(t_1,1)∈ dom (x,u) and P3) holds with α=α′α=α . I) Otherwise, either (α′(|x(0,0)|),0)∈dom(x,u)(α ( |x(0,0) |_ A),0)∈ dom (x,u), in which case the solution evolves continuously beyond x(t1,0)x(t_1,0) and satisfies P2) with j=j′=0j=j =0, or I) it terminates at time (T,0)(T,0) with T≤α′(|x(0,0)|)T≤α ( |x(0,0) |_ A) and, hence, satisfies P4) with J=0J=0, both with α=α′α=α . In the case of the time horizon T being bounded away from the origin considered in item a).a)i), P1) holds with α=α′α=α since each feasible solution pair (x,u)(x,u) is such that there exists (t′,j′)∈dom(x,u)(t ,j )∈ dom (x,u) such that t′+j′≥c>0t +j ≥ c>0, which, in turn, implies that there exists (t,j)∈dom(x,u)(t,j)∈ dom (x,u) such that t+j≤t′+j′t+j≤ t +j and t′−t+j−j′≥α′(|x(0,0)|)t -t+j-j ≥α ( |x(0,0) |_ A). Finally, P2) or P4) hold under the conditions in b). Without loss of generality, suppose that σ in (25) is such that there exists c>0c>0 such that σ(r)≥cσ(r)≥ c for all r>0r>0. With ε coming from (25), let φ(r):=maxr′∈[r/2,r]σ(r′)∀r∈(0,ε] (r):= _r ∈[r/2,r]σ(r ) ∀ r∈(0, ] (27) which satisfies φ(r)≥c (r)≥ c for all r∈(0,ε]r∈(0, ]. Continuity of φ follows via Berge’s maximum theorem [6, Theorem 1.4.16] by showing upper and lower semicontinuity of the set-valued map mapping each r∈[0,ε]r∈[0, ] to the compact interval [r/2,r][r/2,r]. Indeed, lower semicontinuity of the mapping can be verified directly, while upper semicontinuity follows from the fact that the mapping is outer semicontinuous (since its graph is closed relative to (0,ε]×ℝ(0, ]×R [19, Lemma 5.10]) and locally bounded, due to [19, Lemma 5.15]. Let τ(0):=0τ(0):=0 and τ(r):=r2φ(r)if r∈(0,ε]ε2φ(ε)if r∈(ε,∞)τ(r):= cases r2 (r)&if r∈(0, ]\\ 2 ( )&if r∈( ,∞) cases and similarly, for every r≥0r≥ 0, let ρ(r):=minr,ερ(r):= \r, \. Note that τ is continuous, positive definite, upper bounded by ε2φ(ε) 2 ( ), and lower bounded by zero. Hence, there exists a continuous function τ~:ℝ≥0→ℝ≥0 τ:R_≥ 0→R_≥ 0 that is positive definite, increasing, and such that τ~(r)≤τ(r) τ(r)≤τ(r) for all r≥0r≥ 0. It follows that, for any continuous solution pair (x,u)(x,u) to ℋH with |x(0,0)|>0 |x(0,0) |_ A>0, t<τ~(ρ(|x(0,0)|))t< τ(ρ( |x(0,0) |_ A)) satisfying (t,0)∈dom(x,u)(t,0)∈ dom (x,u) implies |x(t,0)|≥ρ(|x(0,0)|)2 |x(t,0) |_ A≥ ρ( |x(0,0) |_ A)2. To show this implication, first note that, by definition of τ~ τ, τ~(ρ(|x(0,0)|)) τ(ρ( |x(0,0) |_ A)) is upper bounded by τ(ρ(|x(0,0)|))τ(ρ( |x(0,0) |_ A)) and that, since ρ is upper bounded by ε , τ~(ρ(|x(0,0)|))φ(ρ(|x(0,0)|))≤ρ(|x(0,0)|)2 τ(ρ( |x(0,0) |_ A)) (ρ( |x(0,0) |_ A))≤ ρ( |x(0,0) |_ A)2. Using (25) and the construction of φ above, we have |x(t,0)|≥|x(0,0)|−φ(|x(0,0)|)t |x(t,0) |_ A≥ |x(0,0) |_ A- ( |x(0,0) |_ A)t for all (t,0)∈dom(x,u)(t,0)∈ dom (x,u) such that 0<|x(t,0)|≤ε0< |x(t,0) |_ A≤ . Then, the lower bound on |x(t,0)| |x(t,0) |_ A can be obtained by evaluating the latter inequality at t=τ~(ρ(|x(0,0)|))t= τ(ρ( |x(0,0) |_ A)), leading to |x(t,0)|≥ρ(|x(0,0)|)2 |x(t,0) |_ A≥ ρ( |x(0,0) |_ A)2. In other words, τ~∘ρ(r) τ ρ(r) is a lower bound on the ordinary time to reach the (r/2)(r/2)-disc around A from the r-disc around A via flows, for each r≥0r≥ 0. Finally, for every r≥0r≥ 0, let α^D(r):=α~D(ρ(r)/2) α_D(r):= α_D(ρ(r)/2), and note that α^D α_D and ρ are continuous, nondecreasing, and positive definite. Let (x,u)(x,u) be an optimal solution pair and tjj=0J+1\t_j\_j=0^J+1 be a sequence such that dom(x,u)=∪j=0J([tj,tj+1]×j) dom (x,u)= _j=0^J([t_j,t_j+1]×\j\), with |x(0,0)|>0 |x(0,0) |_ A>0. First, suppose α~D(r)≥r α_D(r)≥ r for all r≥0r≥ 0. Then, following the same arguments as before, one can deduce that for any t<τ~(ρ(|x(0,0)|))t< τ(ρ( |x(0,0) |_ A)) and j∈ℕj satisfying (t,j)∈dom(x,u)(t,j)∈ dom (x,u), we have |x(t,j)|≥ρ(|x(0,0)|)2 |x(t,j) |_ A≥ ρ( |x(0,0) |_ A)2, due to the fact that the distance of x to A does not decrease during jumps, in light of (26). Therefore, either there exists (s,i)∈dom(x,u)(s,i)∈ dom (x,u) such that s=τ~(ρ(|x(0,0)|))s= τ(ρ( |x(0,0) |_ A)) and every (t,j)∈domx(t,j)∈ dom x with t+j≤s+it+j≤ s+i satisfies |x(t,j)|≥ρ(|x(0,0)|)2 |x(t,j) |_ A≥ ρ( |x(0,0) |_ A)2, or letting T:=tJ+1T:=t_J+1, x(T,J)≥ρ(|x(0,0)|)2x(T,J)≥ ρ( |x(0,0) |_ A)2. In other words, P2) or P4) holds α=α0α= _0, where α0(r):=minτ~(ρ(r)),ρ(r)2∀r≥0 _0(r):= \ τ(ρ(r)), ρ(r)2 \ ∀ r≥ 0 (28) Next, suppose that there exists Jmax∈ℕJ_ such that for every (T,J)∈(T,J)∈ T, J≤JmaxJ≤ J_ , but α~D(r)≥r α_D(r)≥ r does not necessarily hold for all r≥0r≥ 0. Let T:=tJ+1T:=t_J+1. If there exists j∈0,1,…,Jj∈\0,1,…,J\ such that tj+1−tj≥τ~(ρ(|x(tj,j)|))t_j+1-t_j≥ τ(ρ( |x(t_j,j) |_ A)), let i be the smallest such j, otherwise, let i:=J+1i:=J+1. Then, |x(tj,j)| |x(t_j,j) |_ A ≥α~D(|x(tj,j−1)|) -14.45377pt≥ α_D( |x(t_j,j-1) |_ A) ≥α~D(ρ(|x(tj−1,j−1)|2))=α^D(|x(tj−1,j−1)|) -50.58878pt≥ α_D (ρ ( |x(t_j-1,j-1) |_ A2 ) )= α_D( |x(t_j-1,j-1) |_ A) for all j∈1,2,…,mini,Jj∈\1,2,…, \i,J\\, and consequently, |x(tj,j)|≥α^Dj(|x(0,0)|)∀j∈0,1,…,mini,J |x(t_j,j) |_ A≥ α_D^j( |x(0,0) |_ A) ∀ j∈\0,1,…, \i,J\\ (29) where α^Dj α_D^j denotes the j-times composition of α^D α_D, e.g., α^D0 α_D^0 is the identity function and α^D2=α^D∘α^D α_D^2= α_D α_D. In addition, if i≤Ji≤ J, since ρ is nondecreasing, by (29), |x(t,i)|≥ρ(|x(ti,i)|)2≥ρ(α^Di(|x(0,0)|)2 |x(t,i) |_ A≥ ρ( |x(t_i,i) |_ A)2≥ ρ( α_D^i( |x(0,0) |_ A)2 for all t∈[ti,ti+τ~(ρ(|x(ti,i)|))]t∈[t_i,t_i+ τ(ρ( |x(t_i,i) |_ A))], which, as τ~ τ is increasing, implies that, for all t∈[ti,ti+τ~(ρ(α^Di(|x(0,0)|)))]t∈[t_i,t_i+ τ(ρ( α_D^i( |x(0,0) |_ A)))], |x(t,i)|≥ρ(α^Di(|x(0,0)|)2 |x(t,i) |_ A≥ ρ( α_D^i( |x(0,0) |_ A)2 (30) On the other hand, if i=J+1i=J+1, then again by (29), |x(T,J)|=|x(tJ+1,J)| |x(T,J) |_ A= |x(t_J+1,J) |_ A ≥ ≥ ρ(|x(tJ,J)|)2 ρ( |x(t_J,J) |_ A)2 (31) ≥ ≥ ρ(α^DJ(|x(0,0)|)2 ρ( α_D^J( |x(0,0) |_ A)2 Given r≥0r≥ 0, let α1(r) _1(r) :=minj∈0,1,…,Jmaxρ(α^Dj(r))2, = _j∈\0,1,…,J_ \ ρ( α_D^j(r))2, α2(r) _2(r) :=minj∈0,1,…,Jmaxτ~(ρ(α^Dj(r))) = _j∈\0,1,…,J_ \ τ(ρ( α_D^j(r))) Then, if i≤Ji≤ J, by (30), |x(t,i)|≥α1(|x(0,0)|) |x(t,i) |_ A≥ _1( |x(0,0) |_ A) for every t∈[ti,ti+α2(|x(0,0)|)]t∈[t_i,t_i+ _2( |x(0,0) |_ A)] satisfying (t,i)∈dom(x,u)(t,i)∈ dom (x,u). Otherwise, by (31), |x(T,J)|≥α2(|x(0,0)|) |x(T,J) |_ A≥ _2( |x(0,0) |_ A). Combining this bound with the one in the previous case when α~D(r)≥r α_D(r)≥ r for all r≥0r≥ 0, it follows that P2) or P4) holds with α(r)=mink∈0,1,2αk(r)α(r)= _k∈\0,1,2\ _k(r) for all r≥0r≥ 0, where α0 _0 is defined in (28). ∎ Remark V.12 Condition (26) is to be checked for all points (x,u)(x,u) in D. When the interest is in P2) holding for feasible and complete solution pairs, (26) can be relaxed and only be checked at points (x,u)∈D(x,u)∈ D such that g(x,u)∈cl(Π(C))∪Π(D)g(x,u)∈ cl ( (C))∪ (D). Example V.13 (Bouncing Ball Control (revisited)) Consider the data of the bouncing ball system in Example I.2 and the total energy function W defined in (4). Following the control goal stated in Example I.4, let =x∈ℝ2:x1≥0,W(x)=c∗ A=\x ^2:x_1≥ 0,W(x)=c^*\ (32) with c∗=γhc^*=γ h for some h≥0h≥ 0. This definition of the set A corresponds to the limit cycle of the autonomous bouncing ball starting from x(0,0)=(h,0)x(0,0)=(h,0) when λ=1λ=1. Since A is compact and W is positive definite (on the domain x1≥0x_1≥ 0), the function x↦(W(x)−γh)2=:V~(x)x (W(x)-γ h)^2=: V(x) satisfies (23) for some ε>0 >0 and class-∞ K_∞ functions α~1 α_1 and α~2 α_2, as W is continuous. In fact, these functions can be chosen independently of ε>0 >0, due to radial unboundedness of W. Moreover, ⟨∇V~(x),f(x,u)⟩=0 ∇ V(x),f(x,u) =0 for all (x,u)∈C(x,u)∈ C, so (24) holds with arbitrarily large ε>0 >0. Unlike item 1 in Proposition V.9, (25) does allow for finite-time convergence to A during flows. Existence of a continuous function σ and ε>0 >0 satisfying (25) is guaranteed when C=C′×UC=C × U for a closed set C′⊂ℝnC ^n and compact set U⊂ℝmU ^m, provided A is compact and f is continuous. Example V.14 (Sample-And-Hold Control (revisited)) Given a compact set U⊂ℝmzU ^m_z, we revisit the sample-and-hold control system in Example I.6 with flow and jump sets C C =(x,u):η∈U,τs∈[0,Ts] =\(x,u):η∈ U, _s∈[0,T_s]\ D D =(x,u):η∈U,τs=Ts,u∈U =\(x,u):η∈ U, _s=T_s,u∈ U\ Note that the only difference between these sets and those in Example I.6 is that the state component η and the input u are restricted to the compact set U. Using these sets, we consider the compact set =0×U×[0,Ts] A=\0\× U×[0,T_s], requiring convergence of z and η to zero. Item 2 in Proposition V.9 holds as the flow map f is affine and does not depend on u. We also note that |g(x,u)|=|z|=|x| |g(x,u) |_ A=|z|= |x |_ A for every (x,u)∈D(x,u)∈ D, so item b).b)i) holds with α~D α_D as the identity. Item b).b)i) holds since each solution flows for some nonzero amount of ordinary time. Then, by Proposition V.9, either P2) or P4) hold. Example V.15 (Bouncing Ball Control (revisited)) Given a compact set U⊂ℝU , consider the data C C =(x,u)∈ℝ2×ℝ:x1≥0,u∈U =\(x,u) ^2×R:x_1≥ 0,u∈ U\ (33) f(x,u) f(x,u) =(x2,−γ+u) =(x_2,-γ+u) D D =(x,u)∈ℝ2×ℝ:x1=0,x2≤0 =\(x,u) ^2×R:x_1=0,x_2≤ 0\ g(x,u) g(x,u) =(0,−λx2) =(0,-λ x_2) This data represents a modification of the bouncing ball system in Examples I.2 and V.13, where the input u affects flows instead of jumps. Suppose λ>0λ>0 and, similar to the definition of A in (32) for c∗=γhc^*=γ h, let =x:x1≥0,W(x)=c∗∪(0,−2γh/λ). A=\x:x_1≥ 0,W(x)=c^*\∪ \(0,- 2γ h/λ) \. Item 2 in Proposition V.9 holds by continuity of f and compactness of U, since A is compact. To show that P2) holds, it suffices to note that the jump map g is continuous, and |g(x,u)| |g(x,u) |_ A tends to infinity in D as |x| |x |_ A tends to infinity, and importantly, |g(x,u)|=0 |g(x,u) |_ A=0 if and only if x=(0,−2γh)∈Dx=(0,- 2γ h)∈ D. Note that if the point z=(0,−2γh/λ)∈Dz=(0,- 2γ h/λ)∈ D were to be excluded from A, this condition would not hold since W(g(z,u))=c∗W(g(z,u))=c^*. Hence, item b).b)i) holds and, by Proposition V.9, either P2) or P4) hold. VI Asymptotic Stability In this section, we establish asymptotic stability of the set A for the closed-loop system resulting from controlling the hybrid plant (1) with our hybrid MPC algorithm. Since such a closed-loop system cannot be written as an autonomous system, we introduce the following asymptotic stability notion (cf. [19, 40]). Definition VI.1 The hybrid MPC algorithm is said to render the set A asymptotically stable for ℋH if ℋH has unique state trajectories and the following hold: (E) There exists δ>0δ>0 such that for each x∘∈Π(C∪D)x_ ∈ (C∪ D) satisfying |x∘|≤δ |x_ |_ A≤δ, there exists a solution pair (x,u)(x,u) generated by the hybrid MPC algorithm starting from x∘x_ . (S) For each ε>0 >0, there exists δ>0δ>0 such that for each solution pair (x,u)(x,u) generated by the hybrid MPC algorithm, |x(0,0)|≤δ |x(0,0) |_ A≤δ implies |x(t,j)|≤ε |x(t,j) |_ A≤ for all (t,j)∈dom(x,u)(t,j)∈ dom (x,u). (A) Each maximal solution pair (x,u)(x,u) generated by the hybrid MPC algorithm is complete and satisfies limt+j→∞,(t,j)∈dom(x,u)|x(t,j)|=0 _t+j→∞,(t,j)∈ dom (x,u) |x(t,j) |_ A=0. Item (E) in Definition VI.1 implies that, from a neighborhood of A, either no solution pair exists or, if x∘∈Π(C∪D)x_ ∈ (C∪ D), a solution pair (x,u)(x,u) can be generated by the hybrid MPC algorithm. For this property to hold, it is clear that a solution to Problem I.5 must exist from those points—see Remark IV.4. While not emphasized in Definition VI.1, note that in general, from any initial condition x∘∈x_ ∈ X, there might be infinitely many solution pairs generated by the hybrid MPC algorithm. This is for two reasons. First, the minimizers of the cost functional J might be nonunique; that is, given x∘∈x_ ∈ X, there may be multiple solution pairs achieving the infimum in (14). Second, assuming that the recursive feasibility property stated in Proposition V.2 holds, the optimal control input uiu_i computed at optimization time (Ti,Ji)(T_i,J_i)—see Section I-E— can be updated at any (hybrid) time before the domain of uiu_i ends, that is, at any (Ti+t,Ji+j)(T_i+t,J_i+j), as long as (t,j)∈domui(t,j)∈ dom u_i. Theorem VI.2 Given a hybrid plant ℋ=(C,f,D,g)H=(C,f,D,g) as in (1), the data (,LC,LD,V,X)( T,L_C,L_D,V,X) defining Problem I.5 with T having t0>0t_0>0 and J≥1J≥ 1, and a closed set ⊂ℝn A ^n, suppose that Assumptions I.7, IV.1, IV.2, and IV.3 hold. Furthermore, suppose that there exists a class- K function α∗:ℝ≥0→ℝ≥0α^*:R_≥ 0→R_≥ 0 such that the value function ∗ J^* in (14) satisfies111111Sufficient conditions for (19) to hold are given in Section V-E. (19) for each x∘∈x_ ∈ X and that an optimal solution pair (x,u)∈^ℋ(x∘)(x,u)∈ S _H(x_ ) to Problem I.5 exists.121212Sufficient conditions for such existence are given in [4]; see Remark IV.4. Then, the hybrid MPC algorithm renders the set A asymptotically stable for the hybrid system ℋH if any of the following statements are true: (AS1) LCL_C and LDL_D satisfy (W1) and (W2), respectively; (AS2) Each solution pair generated by the hybrid MPC algorithm has persistent jumps and LDL_D satisfies (W2); (AS3) Each solution pair generated by the hybrid MPC algorithm has persistent flows and LCL_C satisfies (W1). Proof: The proof proceeds as follows. First, a complete optimal solution with initial condition in a (small enough) neighborhood of the set A is constructed by induction. Using properties of J established earlier, we show that J is a Lyapunov function certifying Lyapunov stability of A. Finally, attractivity of A is shown using the assumptions in the different items in the statement. Using Assumption I.7, Proposition I.8 implies that, for any given input, ℋH has unique state trajectories. From Proposition V.1, we have that X⊂X⊂ X. Then, pick δ′>0δ >0 and note that existence of optimal solutions from X implies that, for every ξ∈Π(C∪D)∩Xξ∈ (C∪ D)∩ X satisfying |ξ|≤δ′ |ξ |_ A≤δ , there exists an optimal solution (x0,u0)(x_0,u_0) starting from ξ. Now, the structure of the hybrid prediction horizon in Definition I.2 implies that there exists c>0c>0 such that T^+J^≥c T+ J≥ c for any (T^,J^)∈( T, J)∈ T. Hence, the terminal time (T0,J0)(T_0,J_0) of (x0,u0)(x_0,u_0) satisfies T0+J0≥cT_0+J_0≥ c. In addition, due to the recursive feasibility property stated in Proposition V.2 and existence of optimal solutions, there exists an optimal solution pair (x1,u1)(x_1,u_1) starting from x0(T0,J0)x_0(T_0,J_0), whose terminal time (T1,J1)(T_1,J_1) satisfies T1+J1≥cT_1+J_1≥ c. Then, following Definition I.7, the concatenation of (x0,u0)(x_0,u_0) and (x1,u1)(x_1,u_1) form a solution pair. Specifically, (t,j)↦(x′(t,j),u′(t,j))(t,j) (x (t,j),u (t,j)) defined as follows is a solution pair to ℋH: for every (t,j)∈dom(x0,u0)(t,j)∈ dom (x_0,u_0) such that t+j<T+Jt+j<T+J, (x′(t,j),u′(t,j))=(x0(t,j),u0(t,j))(x (t,j),u (t,j))=(x_0(t,j),u_0(t,j)) and for every (t,j)∈ℝ≥0×ℕ(t,j)∈R_≥ 0×N such that (t−T0,j−J0)∈dom(x1,u1)(t-T_0,j-J_0)∈ dom (x_1,u_1) and (t−T0)+(j−J0)<T1+J1(t-T_0)+(j-J_0)<T_1+J_1, (x′(t,j),u′(t,j))=(x1(t−T0,j−J0),u1(t−T0,j−J0)).(x (t,j),u (t,j))=(x_1(t-T_0,j-J_0),u_1(t-T_0,j-J_0)). Setting (x′(T0+T1,J0+J1),u′(T0+T1,J0+J1))=(x1(T1,J1),u1(T1,J1))(x (T_0+T_1,J_0+J_1),u (T_0+T_1,J_0+J_1))=(x_1(T_1,J_1),u_1(T_1,J_1)), the terminal time (T′,J′)(T ,J ) of (x′,u′)(x ,u ) is such that T′+J′≥2cT +J ≥ 2c. Similarly, (x′,u′)(x ,u ) can be concatenated with an optimal pair (x2,u2)(x_2,u_2) from x1(T1,J1)x_1(T_1,J_1) with terminal (T2,J2)(T_2,J_2) satisfying T2+J2≥cT_2+J_2≥ c. By induction, the resulting solution pair starts from ξ and constitutes a complete optimal solution generated by the hybrid MPC algorithm. Next, we establish that the value function ∗ J^* is a Lyapunov function. Since X⊂X⊂ X from Proposition V.1, by Assumption IV.2, there exists a class-K function, denoted α2 _2, such that ∗(x~)≤α2(|x~|) J^*( x)≤ _2( | x |_ A) for each x~∈ x∈ X satisfying |x~|≤η | x |_ A≤η, for some η>0η>0. By assumption, there exists a class- K function α∗α^* such that ∗(x~)≥α∗(|x~|) J^*( x)≥α^*( | x |_ A) for each x~∈ x∈ X such that an optimal solution pair (x,u)∈^ℋ(x~)(x,u)∈ S _H( x) exists. Hence, ∗ J^* is positive definite with respect to A. Moreover, by Lemma V.5, for each solution pair (x,u)(x,u) generated by hybrid MPC, ∗(x(t,j))≤∗(x(0,0)) J^*(x(t,j))≤ J^*(x(0,0)) for each (t,j)∈dom(x,u)(t,j)∈ dom (x,u). Then, given ε>0 >0 there exists δ∈(0,minδ′,η,α∗−1∘α2(ε)]δ∈(0, \δ ,η,α^*^-1 _2( )\] such that, for each ξ∈Π(C∪D)ξ∈ (C∪ D) satisfying |ξ|≤δ |ξ |_ A≤δ, each (complete) optimal solution pair (x,u)(x,u) constructed as above satisfies α^*(—x(t,j)—_A) ≤J^*(x(t,j))≤J^*(ξ) ≤α_2(—ξ—_A) for each (t,j)∈dom(x,u)(t,j)∈ dom (x,u), from where |x(t,j)|≤ε|x(t,j)|_ A≤ . Hence, A is stable in the sense of item (S) in Definition VI.1. To prove attractivity, using the complete solution pair (x,u)(x,u) generated by hybrid MPC constructed at the beginning of this proof, we show that (t,j)↦∗(x(t,j))(t,j) J^*(x(t,j)) approaches zero as t+jt+j approaches infinity. First, let α~C α_C and α~D α_D be nonnegative and such that LC(x,u)≥α~C(|x|)L_C(x,u)≥ α_C( |x |_ A) for each (x,u)∈C(x,u)∈ C and LD(x,u)≥α~D(|x|)L_D(x,u)≥ α_D( |x |_ A) for each (x,u)∈D(x,u)∈ D, respectively. From the inequality in Lemma V.5, we obtain, for each (t,j)∈dom(x,u)(t,j)∈ dom (x,u), ∗(x(t,j))≤∗(x(0,0))−∑i=0j∫sisi+1LC(x(s,i),u(s,i))s−∑i=0j−1LD(x(si+1,i),u(si+1,i))≤∗(x(0,0))−∑i=0j∫sisi+1α~C(|x(s,i)|))ds−∑i=0j−1α~D(|x(si+1,i)|) J^*(x(t,j))≤ J^*(x(0,0))- _i=0^j _s_i^s_i+1L_C(x(s,i),u(s,i))\,ds\\ - _i=0^j-1L_D(x(s_i+1,i),u(s_i+1,i))\\ ≤ J^*(x(0,0))- _i=0^j _s_i^s_i+1 α_C( |x(s,i) |_ A))\,ds\\ - _i=0^j-1 α_D( |x(s_i+1,i) |_ A) (34) where sii=0j+1\s_i\_i=0^j+1 is the sequence of generalized jump times of the truncation of (x,u)(x,u) up to time (t,j)(t,j)—see (7). Next, we show attractivity when items (AS1)-(AS3) hold, one at a time. First, suppose that item (AS1) holds. Then, (34) holds with α~C=αC α_C= _C and α~D=αD α_D= _D for the class-∞K_∞ functions αC _C and αD _D given in item (AS1), via (W1) and (W2). Let c:=limt+j→∞,(t,j)∈dom(x,u)∗(x(t,j))c:= _t+j→∞,(t,j)∈ dom (x,u) J^*(x(t,j)) (35) As ∗(x∘)≥α∗(|x∘|) J^*(x_ )≥α^*( |x_ |_ A) for all x∘∈x_ ∈ X, since α∗α^* is a class-∞ K_∞ function, c=0c=0 implies limt+j→∞,(t,j)∈dom(x,u)|x(t,j)|=0 _t+j→∞,(t,j)∈ dom (x,u) |x(t,j) |_ A=0. Assuming the opposite, we have ∗(x(t,j))≥c>0 J^*(x(t,j))≥ c>0 for all (t,j)∈dom(x,u)(t,j)∈ dom (x,u). By continuity of ∗ J^* on ∩ A∩ X obtained from Proposition V.4, and the fact that ∗(∩)=0 J^*( A∩ X)=0 since ∗ J^* is positive definite relative to A by assumption, this means that there exists ϵ¯>0 ε>0 so |x(t,j)|≥ϵ¯ |x(t,j) |_ A≥ ε for all (t,j)∈dom(x,u)(t,j)∈ dom (x,u). Let (Tk,Jk)k=0∞\(T_k,J_k)\_k=0^∞ be the sequence of optimization times of (x,u)(x,u). By Lemma V.5, for each k∈ℕk , ∗(x(Tk+1,Jk+1))−∗(x(Tk,Jk))≤−((Tk+1−Tk)αC(ϵ¯)+(Jk+1−Jk)αD(ϵ¯)) J^*(x(T_k+1,J_k+1))- J^*(x(T_k,J_k))\\ ≤- ((T_k+1-T_k) _C( ε)+(J_k+1-J_k) _D( ε) ) Summing over k’s in ℕN and taking limit on each side c=limk→∞∗(x(Tk,Jk))≤∗(x(0,0))−minαC(ϵ¯),αD(ϵ¯)limk→∞(Tk+Jk)c= _k→∞ J^*(x(T_k,J_k))\\ ≤ J^*(x(0,0))- \ _C( ε), _D( ε)\ _k→∞(T_k+J_k) which contradicts c>0c>0 as limk→∞(Tk+Jk)=∞ _k→∞(T_k+J_k)=∞ and ∗(x(0,0)) J^*(x(0,0)) is finite. Therefore, it follows that c=0c=0, and consequently limt+j→∞,(t,j)∈dom(x,u)|x(t,j)|=0 _t+j→∞,(t,j)∈ dom (x,u) |x(t,j) |_ A=0, which completes the proof. Now, suppose item (AS2) is the one that holds. It follows that (34) holds with α~C=0 α_C=0 and α~D=αD α_D= _D for the class-∞K_∞ function αD _D given in item (AS2) via (W2). With c as in (35), we follow the steps of the proof for the case when item (AS1) holds, but in this case, through recursive use of (34), we obtain lim supt+j→∞∗(x(t,j))≤limj→∞∗(x(0,0))−∑j=0∞αD(|x(tj+1,j)|) _t+j→∞ J^*(x(t,j))≤ _j→∞ J^*(x(0,0))- _j=0^∞ _D( |x(t_j+1,j) |_ A) where tjj=1∞\t_j\_j=1^∞ are the jump times of (x,u)(x,u). Proceeding as above and using that αD _D is a class-∞ K_∞ function, assuming c>0c>0 leads to a contradiction showing that c=0c=0. The case when item (AS3) holds follows similarly. In this case, the second term in (34) takes the form of a sum of integrals (for each period of flow) with the integrand αC(|x(t,j)|) _C( |x(t,j) |_ A), where the union of the domains of integration is [0,∞)[0,∞), and similar arguments apply, for which the fact that αC _C is a class-∞ K_∞ function is used. ∎ Remark VI.3 The conditions in Theorem VI.2 involve conditions on the data of the hybrid plant (Assumption I.7), on the data defining Problem I.5 (Assumptions IV.1, IV.2, and IV.3), and on the existence of optimal pairs, which couples both data. The required class- K function α∗α^* can be obtained from the results in Sections V-D and V-E. Note that when the hybrid MPC algorithm generates solution pairs with persistent jumps, we do not insist on the flow cost to be positive definite with respect to the distance of the state x to the set A—similarly when the solution pairs have persistent flows. Persistence of jumps or flows are usually inherited from the open-loop system ℋH. For example, for the bouncing ball in Examples I.2 and V.13, every complete solution pair has persistent jumps (see Section I). Consequently, every solution pair generated by the hybrid MPC algorithm has persistent jumps, regardless of the OCP formulation. VII Examples In this section, we implement the proposed hybrid MPC algorithm in the two examples introduced and revisited throughout the paper. The files used in simulations are available at github.com/HybridSystemsLab/HybridMPC. Example VII.1 We illustrate the implementation of the hybrid MPC algorithm in Algorithm 1 in the bouncing ball control system in Example I.2 with λ∈(0,1]λ∈(0,1] and constraints in u defined by a compact set U⊂ℝU . Using the definition of the total energy W in (4), define the set to stabilize as the constant level of energy c∗=γhc^*=γ h for some h≥0h≥ 0, namely :=x∈Π(C):W(x)=c∗ A:=\x∈ (C):W(x)=c^*\ where Π(C)=x∈ℝ2:x1≥0 (C)=\x ^2:x_1≥ 0\; see Examples I.4 and V.13. Next, we define the data (,LC,LD,V,X)( T,L_C,L_D,V,X) associated with hybrid MPC (see Section I) so as to satisfy the assumptions in Theorem VI.2. The hybrid prediction horizon T is chosen as in (10), with δ>0δ>0 and N∈1,2,…N∈\1,2,…\. This set is such that there exists c>0c>0 such that T+J≥cT+J≥ c for each (T,J)∈(T,J)∈ T, from where it follows that item a.i in Proposition V.9 holds. The terminal set X is chosen as X:=Π(C)X:= (C). Pick θ∈(0,(2/π)(1−λ4)/(1+λ4))θ∈(0,(2/π)(1-λ^4)/(1+λ^4)) We define the terminal cost as V(x):=(1+θarctanx2)V~(x)∀x∈XV(x):=(1+θ x_2) V(x) ∀ x∈ X where V~ V is defined in Example V.13. By the choice of θ, V is positive definite with respect to A. Moreover, Assumption IV.2 holds with α radially unbounded and any ε>0 >0. From Example V.13 and the properties of T, exploiting item 1 and item a in Proposition V.9, we have that P1) holds for each solution to ℋH. We denote the function satisfying P1) as α~ α. To define the hybrid closed-loop system ℋκH_κ in (9), we proceed as follows. Since the bouncing ball control system does not have inputs that affect the flow map, we choose the state-feedback law κC _C as an arbitrary function with its range in UCU_C. The state-feedback law κD _D is defined as κD(x):=maxλx2+2γh,0∀x∈ℝ2 _D(x):= \λ x_2+ 2γ h,0 \ ∀ x ^2 The resulting maps fκf_κ, gκg_κ and the sets DκD_κ, CκC_κ defining the data of (9) are given by Cκ:=Π(C)C_κ:= (C), fκ(x):=(x2,−γ)f_κ(x):=(x_2,-γ) for each x∈Cκx∈ C_κ, Dκ:=x∈ℝ2:x1=0,x2≤0D_κ:=\x ^2:x_1=0,x_2≤ 0\, and gκ(x):=(0,−λx2)if x2≤−2γh/λ(0,2γh)otherwiseg_κ(x):= cases(0,-λ x_2)& if x_2≤- 2γ h/λ\\ (0, 2γ h)& otherwise cases for each x∈Dκx∈ D_κ, respectively. Next, we design the flow cost LCL_C and jump cost LDL_D so that the CLF condition in Assumption IV.3 holds with V and X as designed above. To that end, we define the flow cost as LC(x,u):=θγ(W(x)−γh)21+2W(x)∀(x,u)∈CL_C(x,u):=θγ (W(x)-γ h)^21+2W(x) ∀(x,u)∈ C The jump cost is chosen as follows: LD(x,u)=12(1−θπ2)γh(x2+2γh)2L_D(x,u)= 12 (1- θπ2 )γ h (x_2+ 2γ h )^2 if x2≥−2γh/λx_2≥- 2γ h/λ, and LD(x,u)=min12(1−θπ2)γh(x2+2γh)2,(1−θπ2)(x222−γh)2−(1+θπ2)(λ2x222−γh)2L_D(x,u)= \ 12 (1- θπ2 )γ h (x_2+ 2γ h )^2,\\ (1- θπ2 ) ( x_2^22-γ h )^2- (1+ θπ2 ) ( λ^2x_2^22-γ h )^2 \ otherwise, for all (x,u)∈D(x,u)∈ D. Next, we check that the CLF conditions in (15) hold. For starters, LCL_C satisfies (W1) due to radial unboundedness of W in Π(C) (C), that is, W(x)W(x) approaches infinity as |x| |x |_ A approaches infinity in Π(C) (C). Furthermore, since ⟨∇W(x),fκ(x)⟩=0 ∇ W(x),f_κ(x) =0, it can be shown by direct computation that ⟨∇V(x),fκ(x)⟩≤−LC(x,κC(x)) ∇ V(x),f_κ(x) ≤-L_C(x, _C(x)) for all x∈Cκx∈ C_κ. Now, LDL_D satisfies (W2) due to the choice of θ. More specifically, the condition on θ ensures that the coefficient of the x24x_2^4 term is positive and LDL_D is positive definite, in the sense that, for each (x,u)∈D(x,u)∈ D, LD(x,u)L_D(x,u) is equal to zero if x2=−2γhx_2=- 2γ h and positive otherwise. It can be shown that V(gκ(x))−V(x)≤−LD(x,κD(x))V(g_κ(x))-V(x)≤-L_D(x, _D(x)) for each x∈Dκx∈ D_κ. In particular, since gκ(x)=(0,2γh)∈g_κ(x)=(0, 2γ h)∈ A for each x∈Dκx∈ D_κ satisfying x2≥−2γh/λx_2≥- 2γ h/λ, and V(x)=0V(x)=0 for each x∈x∈ A, V(gκ(x))−V(x)≤−14(1−θπ2)(x2−2γh)2(x2+2γh)2≤−12(1−θπ2)γh(x2+2γh)2≤−LD(x,κD(x))V(g_κ(x))-V(x)\\ ≤- 14 (1- θπ2 ) (x_2- 2γ h )^2 (x_2+ 2γ h )^2\\ ≤- 12 (1- θπ2 )γ h (x_2+ 2γ h )^2≤-L_D(x, _D(x)) for each x∈Dκx∈ D_κ satisfying x2≥−2γh/λx_2≥- 2γ h/λ, where we use the fact that x1=0x_1=0 and x2≤0x_2≤ 0 on DκD_κ. On the other hand, given any x∈Dκx∈ D_κ satisfying x2≤−2γh/λx_2≤- 2γ h/λ, since κD(x)=0 _D(x)=0, we have V(gκ(x))−V(x)=(1+θarctan(−λx2))(λ2x222−γh)2−(1+θarctanx2)(x222−γh)2≤(1+θπ/2)(λ2x222−γh)2−(1−θπ/2)(x222−γh)2≤−LD(x,κD(u))V(g_κ(x))-V(x)\\ =(1+θ (-λ x_2)) ( λ^2x_2^22-γ h )^2\\ -(1+θ x_2) ( x_2^22-γ h )^2\\ ≤(1+θπ/2) ( λ^2x_2^22-γ h )^2-(1-θπ/2) ( x_2^22-γ h )^2\\ ≤-L_D(x, _D(u)) Hence, (15) holds. Note that since LCL_C and LDL_D satisfy Assumption IV.1, and P1) holds for each solution to ℋH, from Theorem V.6 and [4, Section 6.2] we have that there exists a class- K function α∗:ℝ≥0→ℝ≥0α^*:R_≥ 0→R_≥ 0 such that the value function ∗ J^* in (14) satisfies (19) for each x∘∈x_ ∈ X and that an optimal solution pair (x,u)∈^ℋ(x∘)(x,u)∈ S _H(x_ ) exists from each such x∘x_ . Furthermore, one can adapt the steps in [19, Example 2.12] to show that X is forward pre-invariant for ℋκH_κ, leading to =X X=X, which is equal to Π(C)∪Π(D) (C)∪ (D), implying that every maximal solution to the closed-loop system using hybrid MPC is complete. Next, we simulate the bouncing ball controlled by hybrid MPC. The parameters used in the simulation are γ=9.81m/sγ=9.81 m/s, λ=0.9λ=0.9, h=3mh=3\ m, which leads to c∗=1.835m2/sc^*=1.835\ m^2 /s, and a prediction horizon of the form (10) with N=5N=5 and δ=0.5δ=0.5. Problem I.5 is solved in MATLAB using the fmincon function by converting it into a finite-dimensional nonlinear program, for which we exploit the fact that the total energy W—and therefore the flow cost LCL_C—is invariant during flows (namely, W is conserved during flows) and that the state trajectory of the bouncing ball during flows can be written in closed form. The closed-loop system is simulated using the Hybrid Equations Toolbox [37]. After every optimization event, if the predicted state trajectory jumps, the next optimization is triggered at the next jump time; otherwise, the next optimization occurs at the terminal time of the predicted state trajectory. Figure 4 depicts closed-loop state trajectories for the controlled bouncing ball from three initial conditions: 1) x(0,0)=(0,0)x(0,0)=(0,0), shown in blue, 2) x(0,0)=(1,−1)x(0,0)=(1,-1), shown in black, 3) x(0,0)=(3,4)x(0,0)=(3,4), shown in green. Figure 5 shows the total energy associated with these trajectories. The trajectory from x(0,0)=(0,0)x(0,0)=(0,0) exhibits a jump at (t,j)=(0,0)(t,j)=(0,0) since a jump is possible from such initial condition. The hybrid MPC controller injects energy equal to c∗c^* at that jump, and the trajectory converges and stays at the desired level of energy from there on. The trajectory from x(0,0)=(1,−1)x(0,0)=(1,-1) exhibits a similar behavior, but after the first jump at (t1,0)(t_1,0) where t1≈0.36sect_1≈ 0.36 sec. Such “dead beat” convergence property is due to the only constraint on the control input being u≥0u≥ 0. The effect of this constraint is visualized in the trajectory from x(0,0)=(3,4)x(0,0)=(3,4), which has initial energy much larger than c∗c^* and, due to the control input having to be nonnegative, cannot remove energy in one jump. Figure 4: Position and velocity trajectories of the bouncing ball controlled by hybrid MPC projected onto ordinary time t. Figure 5: Evolution of the total energy of the bouncing ball controlled by hybrid MPC projected onto ordinary time t. Example VII.2 (Sample-and-Hold Control (revisited)) We synthesize our hybrid MPC algorithm to control the system in Example I.6 using the sample-and-hold paradigm. With the flow and jump sets given in Example I.6, and the compact set A and linear plant dynamics defined by f~ f in Example V.8, since A is such that both z and η are zero, the control objective for hybrid MPC is to drive the state z and the input η of z˙=Az+Bη z=Az+Bη to zero asymptotically, and render the set A Lyapunov stable. To this end, following the structure of the stage cost used in the linear quadratic regulator, the stage cost for flows is chosen as LC(x,u):=x1⊤QCx1∀(x,u)∈CL_C(x,u):=x_1 Q_Cx_1 ∀(x,u)∈ C where x1:=(z,η)x_1:=(z,η), x2:=τsx_2:= _s, and QCQ_C is a symmetric positive definite matrix that is to be chosen (see below). Assuming that jumps do not accrue cost, the stage cost for jumps is chosen to be the zero function. The terminal cost V is chosen as V(x)=exp(−σx2)(x1⊤exp(Af⊤(Ts−x2))Pexp(Af(Ts−x2))x1)V(x)= (-σ x_2) (x_1 (A_f (T_s-x_2))P (A_f(T_s-x_2))x_1 ), where σ>0σ>0, Af=[AB00]A_f= bmatrixA&B\\ 0&0 bmatrix, and P is a symmetric positive definite matrix, chosen next. The matrices QCQ_C and P are chosen as follows. Given matrices A∈ℝnz×ℝnzA ^n_z×R^n_z and B∈ℝnz×ℝmzB ^n_z×R^m_z, and the compact set U⊂ℝmzU ^m_z, choose a matrix K∈ℝmz×ℝnzK ^m_z×R^n_z, a positive definite symmetric matrix P∈ℝnz×ℝnzP ^n_z×R^n_z, c>0c>0, and Ts>0T_s>0 such that H(K)⊤PH(K)−P<0H(K) PH(K)-P<0 X:=x:x2∈[0,Ts],V(x)≤cX:= \x\ :\ x_2∈[0,T_s],V(x)≤ c\ \ is such that (x1,x2)=(z,η,τs)∈X⇒Kz∈U(x_1,x_2)=(z,η, _s)∈ X\ \ \ \ Kz∈ U and, for each s∈[0,Ts]s∈[0,T_s], QC≤σexp(−σs)⊤exp(Af⊤(Ts−s))Pexp(Af(Ts−s))Q_C≤σ (-σ s) (A_f (T_s-s))P (A_f(T_s-s)) (36) where H(K):=exp(AfTs)Ag(K)H(K):= (A_fT_s)A_g(K) and Ag(K):=[I0K0]A_g(K):= bmatrixI&0\\ K&0 bmatrix. The choice of V stems from the fact that the hybrid closed-loop system resulting from using the state-feedback controller u=κD(x):=Kzu= _D(x):=Kz is such that ⟨∇V(x),fκ(x)⟩≤−σV(x) ∇ V(x),f_κ(x) ≤-σ V(x) on CκC_κ and that V(gκ(x))−V(x)=x1⊤(H(K)⊤PH(K)−exp(−σx2)P)x1V(g_κ(x))-V(x)=x_1 (H(K) PH(K)- (-σ x_2)P)x_1. Then, Assumption IV.3 holds if Lc(x,u)≤σV(x)L_c(x,u)≤σ V(x) on C, which, since f and LCL_C do not depend on u, is guaranteed from (36). Recall that Example V.14 establishes via Proposition V.9 that P2) holds. Then, from item 2 in Theorem V.6, (19) holds.131313Note that Example V.8 establishes that P3) holds with a class-∞ K_∞ function α, but since LDL_D is the zero function, Theorem V.6 cannot be employed to establish that (19) holds. Note that from the construction of the hybrid plant in Example I.6, every complete solution has persistent flows and (AS3) holds. Since the other assumptions in Theorem VI.2 hold, the hybrid MPC algorithm renders A asymptotically stable for ℋH in Example I.6. Example VII.3 (Thermostat Control) The evolution of the temperature of a room controlled by a heater that can either be on or off is given by z˙=−z+zo+zΔq, z=-z+z_o+z_ q, where z∈ℝz is the temperature of the room, zoz_o denotes the effective temperature outside of the room, zΔz_ represents the capacity of the heater, and the logic state q∈0,1q∈\0,1\ represents whether the heater is on or off. When q=1q=1, the heater is on and when q=0q=0, the heater is off. Our goal is to design a control algorithm that steers the temperature to a desired temperature range [zmin,zmax][z_ ,z_ ] where zmin<zmaxz_ <z_ , where zo<zmin<zmax<zo+zΔz_o<z_ <z_ <z_o+z_ . To facilitate the formulation of the optimization problem, we treat q as an additional logic state and incorporate an input, denoted u∈0,1u∈\0,1\, playing the role of the decision variable for the optimization problem. The resulting system is given as in (1), with state x=(q,z)∈0,1×ℝx=(q,z)∈\0,1\×R, input u∈0,1u∈\0,1\, and data (C,f,D,g)(C,f,D,g) given by C C :=0,1×ℝ×0, =\0,1\×R×\0\, f(x,u) f(x,u) :=(0,−z+zo+zΔq)∀(x,u)∈0,1×ℝ×0,1, =(0,-z+z_o+z_ q) ∀(x,u)∈\0,1\×R×\0,1\, D D :=0,1×ℝ×1, =\0,1\×R×\1\, g(x,u) g(x,u) =(1−q,z)∀(x,u)∈0,1×ℝ×0,1. =(1-q,z) ∀(x,u)∈\0,1\×R×\0,1\. With this data, flows of the plant are allowed when u is zero. In this regime, the temperature z evolves according to its continuous-time model and q remains constant as f leads to q˙=0 q=0. At jumps, which are triggered when u is equal to one, the update law 1−q1-q toggles the value of q from 0 to 11 or from 11 to 0. According to the goal stated above, the set to stabilize is given by the range of desired temperature, namely, :=x:z∈[zmin,zmax],q∈0,1 A:= \x\ :\ z∈[z_ ,z_ ],q∈\0,1\\ \ Next, we define the data (,LC,LD,V,X)( T,L_C,L_D,V,X) associated with hybrid MPC (see Section I) so as to satisfy the assumptions in Theorem VI.2. The hybrid prediction horizon T is chosen as in (10), with δ>0δ>0 and N∈1,2,…N∈\1,2,…\. This set is such that there exists c>0c>0 such that T+J≥cT+J≥ c for each (T,J)∈(T,J)∈ T, from where it follows that item a.i in Proposition V.9 holds. The flow cost LCL_C is defined to penalize the cost of flow when the temperature is not in the desired range, as follows: for each (x,u)∈C(x,u)∈ C, LC(x,u):=ahot(z−zmax)+aonq if z≥zmax0 if z∈(zmin,zmax)acold(zmin−z) if z≤zminL_C(x,u):= \ array[]cla_ hot(z-z_ )+a_ onq& if z≥ z_ \\ 0& if z∈(z_ ,z_ )\\ a_ cold(z_ -z)& if z≤ z_ array . where 0<ahot≤zmax−zo0<a_ hot≤ z_ -z_o penalizes the temperature when larger than the desired maximum, 0<acold0<a_ cold penalizes the temperature when smaller than the desired minimum, and 0≤aon0≤ a_ on penalizes the on position of the heater when the temperature is larger than the desired maximum. The jump cost LDL_D also penalizes the temperature when outside the desired range and, in addition, aims at reducing the number of switches of the heater. It is chosen as follows: for each (x,u)∈D(x,u)∈ D, LD(x,u):=bhot(z−zmax)22+bon,hot(1−q) if z≥zmaxbss(zmax−z)(z−zmin)2+bon,s(1−q) if z∈(zmin,zmax)bcold(z−zmin)22 if z≤zminL_D(x,u):= \ array[]l b_ hot (z-z_ )^22+b_ on,hot(1-q)&\\ 101.17755pt if z≥ z_ &\\ b_ s (z_ -z)(z-z_ )2+b_ on,s(1-q)&\\ 101.17755pt if z∈(z_ ,z_ )\\ b_ cold (z-z_ )^22&\\ 101.17755pt if z≤ z_ & array . where 0<bhot≤10<b_ hot≤ 1 penalizes the temperature when larger than the desired maximum, bon,hotb_ on,hot penalizes turning heater on, bssb_ s penalizes temperature variations within the desired range, bon,ssb_ on,s penalizes turning heater on if within the desired range, and bcoldb_ cold penalizes the temperature when smaller than the desired minimum. The terminal constraint set X is defined as X:=C~∪D~X:= C∪ D where the sets C~ C and D~ D are given by C~:=(0×C~0)∪(1×C~1) C:= (\0\× C_0 )∪ (\1\× C_1 ) D~:=(0×D~0)∪(1×D~1) D:= (\0\× D_0 )∪ (\1\× D_1 ) with C~0:=z∈ℝ:z≥zmin,C~1:=z∈ℝ:z≤zmax C_0:= \z \ :\ z≥ z_ \ \,\ C_1:= \z \ :\ z≤ z_ \ \ D~0:=z∈ℝ:z≤zmin,D~1:=z∈ℝ:z≥zmax D_0:= \z \ :\ z≤ z_ \ \,\ D_1:= \z \ :\ z≥ z_ \ \ This construction of X constrains the temperature z and the heater state q to assure stabilizability of the set A. The terminal cost function V is defined as V(x):=(z−zmax)22(1+q) if z≥zmax0 if z∈(zmin,zmax)(z−zmin)22(2−q) if z≤zminV(x):= \ array[]cl (z-z_ )^22(1+q)& if z≥ z_ \\ 0& if z∈(z_ ,z_ )\\ (z-z_ )^22(2-q)& if z≤ z_ array . where the terms (1+q)(1+q) and (2−q)(2-q) penalize being at the “wrong” mode. Picking the feedback κC _C as κC(x)=0 _C(x)=0 if x∈C~x∈ C, and one otherwise, and the feedback κD _D as κD(x)=1 _D(x)=1 if x∈D~x∈ D, and zero otherwise, we obtain the following properties for the variation of V along flows and jumps of the hybrid closed-loop system ℋκH_κ in (9): for every x∈X∩C~(=C~)x∈ X∩ C(= C) we have that ⟨∇V(x),f(x,κC(x))⟩ ∇ V(x),f(x, _C(x)) is given by −(zmax−zo)(z−zmax) if z≥zmax0 if z∈(zmin,zmax)−(zo+zΔ−zmin)(zmin−z) if z≤zmin \ array[]cl-(z_ -z_o)(z-z_ )& if z≥ z_ \\ 0& if z∈(z_ ,z_ )\\ -(z_o+z_ -z_ )(z_ -z)& if z≤ z_ array . and, for every x∈X∩D~(=D~)x∈ X∩ D(= D), V(g(x,κD(x)))−V(x)V(g(x, _D(x)))-V(x) is equal to −(z−zmax)22 if z≥zmax0 if z∈(zmin,zmax)−(z−zmin)22 if z≤zmin \ array[]cl - (z-z_ )^22& if z≥ z_ \\ 0& if z∈(z_ ,z_ )\\ - (z-z_ )^22& if z≤ z_ array . It follows that, with the choices of LCL_C and LDL_D above, Assumption IV.3 holds and that X is forward pre-invariant for ℋκH_κ. From item P5) in Theorem V.6, there exists a class- K function α∗:ℝ≥0→ℝ≥0α^*:R_≥ 0→R_≥ 0 such that the value function ∗ J^* in (14) satisfies (19) for each x∘∈x_ ∈ X. Finally, from [4, Section 6.1], we have that an optimal solution pair (x,u)∈^ℋ(x∘)(x,u)∈ S _H(x_ ) exists from each such x∘x_ . VIII Conclusion This paper formalizes an MPC framework for hybrid dynamical systems. The formulation allows to quantify the cost and predict trajectories over hybrid time domains. Conditions guaranteeing recursive feasibility, positive definiteness of the value function and its decrease along solutions, leading to asymptotic stability of a closed set are proposed. The conditions involve the data of the system and the OCP, leading to checkable design conditions. Future work will focus on the hybrid MPC design to satisfy other dynamical properties of interest, such as safety, temporal logic, and robustness. An add-on to our Hybrid Equations Toolbox (HyEQ) for Matlab/Simulink [37] to compute numerical solutions of Problem I.5 is currently being developed. Employing the results in [13] to relax the conditions for positive definiteness of the value function as suggested by an anonymous reviewer is also part of future work. References [1] B. Altin, P. Ojaghi, and R. G. Sanfelice (2018-08) A model predictive control framework for hybrid systems. In Proceedings of the 6th IFAC Conference on Nonlinear Model Predictive Control (NMPC), Vol. 51, p. 128–133. Cited by: §I-B. [2] B. Altin and R. G. Sanfelice (2019-07) Asymptotically stabilizing model predictive control for hybrid dynamical systems. In Proceedings of the American Control Conference, p. 3630–3635. Cited by: §I-B, §I-E, §V-A. [3] B. Altin and R. G. Sanfelice (2020-07) Model predictive control for hybrid dynamical systems: sufficient conditions for asymptotic stability with persistent flows or jumps. In Proc. Amer. Cont. Conf., p. 1791–1796. Cited by: §I-B. [4] B. Altin and R. G. Sanfelice (2023-03) Regularity of optimal solutions and the optimal cost for hybrid dynamical systems via reachability analysis. Automatica 152. Cited by: Remark I.9, Remark IV.4, Remark IV.4, Example VII.1, Example VII.3, footnote 12. [5] J.-P. Aubin, J. Lygeros, M. Quincampoix, S. S. Sastry, and N. Seube (2002) Impulse differential inclusions: a viability approach to hybrid systems. IEEE Transactions on Automatic Control 47 (1), p. 2–20. Cited by: §I-A. [6] J. Aubin and H. Frankowska (2009) Set-valued analysis. Birkhäuser, Basel. Cited by: §A-C, §V-D, §V-E, footnote 9. [7] A. Bemporad and C. Filippi (2006) Suboptimal explicit receding horizon control with guaranteed stability. Automatica 42 (3), p. 457–462. Cited by: §I-A. [8] A. Bemporad, M. Morari, V. Dua, and E. N. Pistikopoulos (2002) The explicit linear quadratic regulator for constrained systems. Automatica 38 (1), p. 3–20. Cited by: §I-A. [9] A. Bemporad and M. Morari (1999) Control of systems integrating logic, dynamics, and constraints. Automatica 35 (3), p. 407–427. Cited by: §I-A. [10] P. Bernard and R. G. Sanfelice (2019-10) Hybrid dynamical systems with hybrid inputs: definition of solutions and applications to interconnections. International Journal of Robust and Nonlinear Control 30, p. 5892–5916. Cited by: footnote 2. [11] F. Borrelli, A. Bemporad, and M. Morari (2017) Predictive control for linear and hybrid systems. Cambridge University Press. Cited by: §I-A, §I-A. [12] E.F. Camacho, D.R. Ramirez, D. Limon, D. Muñoz de la Peña, and T. Alamo (2010) Model predictive control techniques for hybrid systems. Annual Reviews in Control 34 (1), p. 21–31. External Links: ISSN 1367-5788 Cited by: §I-A. [13] F. Camilli, L. Grüne, and F. Wirth (2008) Control lyapunov functions and zubov’s method. SIAM Journal on Control and Optimization 47 (1), p. 301–326. Cited by: §VIII. [14] J. Chai and R. G. Sanfelice (2019-06) Forward invariance of sets for hybrid dynamical systems (Part I). IEEE Transactions on Automatic Control 64 (6), p. 2426–2441. Cited by: §IV. [15] H. Chen and F. Allgöwer (1998) A quasi-infinite horizon nonlinear model predictive control scheme with guaranteed stability. Automatica 34 (10), p. 1205–1217. Cited by: §I-A. [16] P. Colaneri and R. Scattolini (2007) Robust model predictive control of discrete-time switched systems. IFAC Proceedings Volumes 40 (14), p. 208–212. Cited by: §I-A. [17] C. R. Cutler and B. L. Ramaker (1980) Dynamic matrix control – a computer control algorithm. In Joint Aut. Cont. Conf., p. 72. Cited by: §I-A. [18] R. Findeisen (2006) Nonlinear model predictive control: a sampled-data feedback perspective. Ph.D. Thesis, Stuttgart Univ.. Cited by: §I-A, Example I.6. [19] R. Goebel, R. G. Sanfelice, and A. R. Teel (2012) Hybrid dynamical systems: modeling, stability, and robustness. Princeton University Press, Princeton University Press. External Links: Document Cited by: §A-C, §I-A, §I-A, Example I.5, Remark I.9, §V-E, §VI, Example VII.1, footnote 3, footnote 6. [20] R. Goebel (2019) Existence of optimal controls on hybrid time domains. Nonlinear Analysis: Hybrid Systems 31, p. 153–165. Cited by: Remark IV.4. [21] L. Grüne and J. Pannek (2017) Nonlinear model predictive control. 2nd edition, Springer. Cited by: §I-A, §V-B, §V-C. [22] L. Magni and R. Scattolini (2004-06) Model predictive control of continuous-time nonlinear systems with piecewise constant control. IEEE Transactions on Automatic Control 49 (6), p. 900–906. External Links: Document, ISSN 0018-9286 Cited by: §I-A. [23] D. Q. Mayne and H. Michalska (1990) Receding horizon control of nonlinear systems. IEEE Trans. Aut. Cont. 35 (7), p. 814–824. Cited by: §I-A. [24] D. Q. Mayne, J. B. Rawlings, C. V. Rao, and P. O. Scokaert (2000) Constrained model predictive control: stability and optimality. Automatica 36 (6), p. 789–814. Cited by: §V-B, §V-C. [25] D. Q. Mayne (2014) Model predictive control: recent developments and future promise. Automatica 50 (12), p. 2967–2986. Note: External Links: ISSN 0005-1098 Cited by: §I-A, §I-A. [26] P. Mhaskar, N. H. El-Farra, and P. D. Christofides (2005) Predictive control of switched nonlinear systems with scheduled mode transitions. IEEE Trans. Aut. Cont. 50 (11), p. 1670–1680. Cited by: §I-A. [27] P. Mhaskar, N. H. El-Farra, and P. D. Christofides (2008) Robust predictive control of switched systems: satisfying uncertain schedules subject to state and control constraints. International Journal of Adaptive Control and Signal Processing 22 (2), p. 161–179. Cited by: §I-A. [28] M. Morari and J. H. Lee (1999) Model predictive control: past, present and future. Comp. & Chem. Eng. 23 (4-5), p. 667–682. Cited by: footnote 1. [29] M. A. Müller, P. Martius, and F. Allgöwer (2012) Model predictive control of switched nonlinear systems under average dwell-time. Journal of Process Control 22 (9), p. 1702–1710. Cited by: §I-A. [30] I. Nodozi and R. G. Sanfelice (2025) Solving hybrid model predictive control problems via a mixed-integer approach. In Model Predictive Control, p. 83–109. Cited by: Remark I.8, Remark I.9. [31] P. Ojaghi, B. Altin, and R. G. Sanfelice (2019-12) A model predictive control framework for asymptotic stabilization of discretized hybrid dynamical systems. In Proceedings of the 2019 IEEE Conference on Decision and Control, p. 2356 – 2361. Cited by: Remark I.8, Remark I.9. [32] A. Pakniyat and P. E. Caines (2017-Sept) On the relation between the minimum principle and dynamic programming for classical and hybrid control systems. IEEE Transactions on Automatic Control 62 (9), p. 4347–4362. External Links: ISSN 0018-9286 Cited by: Remark I.9. [33] F. L. Pereira, F. A. C. C. Fontes, A. P. Aguiar, and J. B. de Sousa (2015) An optimization-based framework for impulsive control systems. In Developments in Model-Based Optimization and Control: Distributed Control and Industrial Applications, S. Olaru, A. Grancharova, and F. Lobo Pereira (Eds.), p. 277–300. External Links: ISBN 978-3-319-26687-9 Cited by: §I-A. [34] S. J. Qin and T. A. Badgwell (2003) A survey of industrial model predictive control technology. Control Engineering Practice 11 (7), p. 733–764. Cited by: footnote 1. [35] J. B. Rawlings and D. Q. Mayne (2009) Model predictive control: theory and design. Nob Hill Pub.. Cited by: §I-A. [36] J. Richalet (1976) Algorithmic control of industrial processes. Proc. of the 4th IFAC Sympo. on Identification and System Parameter Estimation, p. 1119–1167. Cited by: §I-A. [37] R. G. Sanfelice, D. A. Copp, and P. Nanez (2013) A toolbox for simulation of hybrid systems in Matlab/Simulink: Hybrid Equations (HyEQ) Toolbox. In Proceedings of Hybrid Systems: Computation and Control Conference, p. 101–106. External Links: Document, Link Cited by: Example VII.1, §VIII. [38] R. G. Sanfelice (2011) Interconnections of hybrid systems: some challenges and recent results. Journal of Nonlinear Systems and Applications 2 (1-2), p. 111–121. External Links: Document Cited by: footnote 2. [39] R. G. Sanfelice (2018-09/2018) Hybrid model predictive control. In Handbook of Model Predictive Control, Birkhäuser, p. 199–220. External Links: ISSN 978-3-319-77489-3, Document Cited by: §I-A. [40] R. G. Sanfelice (2021) Hybrid feedback control. Princeton University Press, Princeton University Press, New Jersey. Cited by: §I-A, §I-A, Example I.5, Remark I.9, §VI. [41] P. Sopasakis, P. Patrinos, H. Sarimveis, and A. Bemporad (2015-08) Model predictive control for linear impulsive systems. IEEE Transactions on Automatic Control 60 (8), p. 2277–2282. External Links: Document, ISSN 0018-9286 Cited by: §I-A. [42] P. Tabuada (2007) Event-triggered real-time scheduling of stabilizing control tasks. IEEE Transactions on Automatic Control 52 (9), p. 1680–1685. Cited by: §I-A. [43] A. van der Schaft and H. Schumacher (2000) An introduction to hybrid dynamical systems. LNCIS, Springer. Cited by: §I-A. Appendix A Proofs A-A Proof of Lemma V.10 Take δ∈(0,ε)δ∈(0, ) such that α~1−1∘α~2(δ)≤ε α_1^-1 α_2(δ)≤ . Let (x,u)(x,u) be a solution pair to ℋH with compact hybrid time domain and terminal time (T,0)(T,0); hence, it is a continuous solution pair with dom(x,u)=[0,T]×0 dom (x,u)=[0,T]×\0\. Suppose |x(0,0)|≤δ|x(0,0)|_ A≤δ. Pick any s≥0s≥ 0 and the largest interval [t1,t2]⊂[0,T][t^1,t^2]⊂[0,T] containing s such that |x(s,0)|≤δ|x(s,0)|_ A≤δ and |x(s,0)|≤|x(0,0)||x(s,0)|_ A≤|x(0,0)|_ A for all t∈[t1,t2]t∈[t^1,t^2]. From differentiability of V~ V, the bounds in (23) and (24) hold on cl(Π(C)) cl ( (C)). Then, since by the choice of δ, |x(s,0)|≤ε|x(s,0)|_ A≤ for all t∈[t1,t2]t∈[t^1,t^2], using (23) and (24), we have α~2(|x(t,0)| α_2(|x(t,0)|_ A ≥V~(x(t,0))≥exp(λ(t−t1))V~(x(t1,0)) ≥ V(x(t,0))≥ (λ(t-t^1)) V(x(t^1,0)) ≥exp(λ(t−t1))α~1(|x(t1,0)|) ≥ (λ(t-t^1)) α_1(|x(t^1,0)|_ A) for all t∈[t1,t2]t∈[t^1,t^2], which implies |x(t,0)| |x(t,0)|_ A ≥α~2−1(exp(λ(t−t1))α~1(|x(t1,0)|)) ≥ α_2^-1( (λ(t-t^1)) α_1(|x(t^1,0)|_ A)) for all t∈[t1,t2]t∈[t^1,t^2]. Since |x(t1,0)|=|x(0,0)||x(t^1,0)|_ A=|x(0,0)|_ A by the very definition of the interval [t1,t2][t^1,t^2], |x(t,0)| |x(t,0)|_ A ≥α~2−1(exp(λ(t−t1))α~1(|x(0,0)|)) ≥ α_2^-1( (λ(t-t^1)) α_1(|x(0,0)|_ A)) ≥α~2−1(exp(λ(t2−t1))α~1(|x(0,0)|)) ≥ α_2^-1( (λ(t^2-t^1)) α_1(|x(0,0)|_ A)) ≥α~2−1(min1,exp(λT)α~1(|x(0,0)|)) ≥ α_2^-1( \1, (λ T)\ α_1(|x(0,0)|_ A)) for all t∈[t1,t2]t∈[t^1,t^2]. Note that this property holds for t’s on any interval such as [t1,t2][t^1,t^2]. At other t’s, |x(t,0)|>δ|x(t,0)|_ A>δ. Then, combining the lower bounds on |x(t,0)||x(t,0)|_ A above and the case when |x(0,0)|>δ|x(0,0)|_ A>δ gives |x(t,0)| |x(t,0)|_ A ≥minα~2−1(min1,exp(λT)α~1(|x(0,0)|)),δ ≥ \ α_2^-1( \1, (λ T)\ α_1(|x(0,0)|_ A)),δ\ for all (t,0)∈dom(x,u)(t,0)∈ dom (x,u). Since α~1 α_1 and α~2 α_2 are class- K functions and δ is positive, there exists class- K function α lower bounding r↦minα~2−1(min1,exp(λT)α~1(r)),δr \ α_2^-1( \1, (λ T)\ α_1(r)),δ\. A-B Proof of Lemma V.11 Without loss of generality, suppose that there exists c>0c>0 such that σ(r)≥cσ(r)≥ c for all r>0r>0. Let φ be given as in (27), which is continuous. Let τ(0):=0τ(0):=0 and τ(r):=r/(2φ(r))τ(r):=r/(2 (r)) for all r∈(0,ε]r∈(0, ], and note that τ is continuous, positive definite, and lower bounds the ordinary time to reach the (r/2)(r/2)-disc around A from the r-disc around A via flows for r≤εr≤ . Let ρ(r):=minr,ερ(r):= \r, \ and τ~(r):=τ(ρ(r)) τ(r):=τ(ρ(r)) for all r≥0r≥ 0. Observing that |x(t,0)|>ρ(|x(0,0)|)/2 |x(t,0) |_ A>ρ( |x(0,0) |_ A)/2 for any continuous solution pair (x,u)(x,u) and t<τ~(|x(0,0)|)t< τ( |x(0,0) |_ A) satisfying (t,0)∈dom(x,u)(t,0)∈ dom (x,u), the proof is completed by picking α to be any class- K function lower bounding both ρ and τ~ τ. A-C Upper Semicontinuous Maps Lemma A.1 Let h:S→ℝh:S be a continuous function, where S⊂ℝnS ^n is closed. Then, given a compact set ⊂ℝn A ^n, there exists r¯≥0 r≥ 0 such that r¯=minr∈ℝ≥0:(+r¯)∩S≠∅. r= \r∈R_≥ 0:( A+ rB)∩ S≠ \.\ (37) Moreover, the function ψ:[r¯,∞)→ℝψ:[ r,∞) given by ψ(r):=maxx∈Γ(r)h(x)∀r∈[r¯,∞),ψ(r):= _x∈ (r)h(x) ∀ r∈[ r,∞), where Γ:ℝ≥0⇉S :R_≥ 0 S is the set-valued mapping defined as Γ(r)=(+r)∩S (r)=( A+rB)∩ S for all r∈ℝ≥0r∈R_≥ 0, is upper semicontinuous. Proof: Take any x∈Sx∈ S and let δ:=|x|δ:= |x |_ A. Since A is compact, there exists a∈a∈ A such that |x−a|=δ|x-a|=δ. Hence, (+δ)∩S( A+ )∩ S is nonempty. Consequently, the infimum of the continuous function x↦|x|x |x |_ A on (+δ)∩S( A+ )∩ S is attained, so (37) holds for some r¯≥0 r≥ 0. Now, let h′:ℝ≥0×S→ℝh :R_≥ 0× S be such that h′(r,x)=h(x)h (r,x)=h(x) for all (r,x)∈ℝ≥0×S(r,x)∈R_≥ 0× S. Then, ψ(r)=maxx∈Γ(r)h′(r,x)∀r∈[r¯,∞).ψ(r)= _x∈ (r)h (r,x) ∀ r∈[ r,∞). Since ℝ≥0×S⊃gphΓR_≥ 0× S⊃ gph , Γ is compact-valued (as A is compact and S is closed), and h′h is continuous, by Berge’s maximum theorem [6, Theorem 1.4.16], ψ is upper semicontinuous if Γ is upper semicontinuous. To show upper semicontinuity of Γ , let Γ′:ℝ≥0⇉ℝn :R_≥ 0 ^n be the set-valued mapping such that Γ′(r)=∅ (r)= for all r<0r<0, and Γ′(r):=(+r) (r):=( A+rB) for all r≥0r≥ 0. Then, since Γ′ is upper semicontinuous and Γ′(r) (r) is closed for all r∈ℝr , by [19, Lemma 5.15], Γ′ is outer semicontinuous. Moreover, [19, Lemma 5.10] implies that gphΓ′ gph is closed, so gphΓ=gphΓ′∩(ℝ≥0×S) gph = gph ∩(R_≥ 0× S) is closed. Therefore, Γ is upper semicontinuous, again as a result of Lemmas 5.10 and 5.15 of [19], and consequently, ψ is upper semicontinuous. ∎ Ricardo G. Sanfelice (SM’01, F’22) received the B.S. degree in Electronics Engineering from the Universidad de Mar del Plata, Buenos Aires, Argentina, in 2001, and the M.S. and Ph.D. degrees in Electrical and Computer Engineering from the University of California, Santa Barbara, in 2004 and 2007, respectively. In 2007 and 2008, he held postdoctoral positions at the Laboratory for Information and Decision Systems at the Massachusetts Institute of Technology and at the Centre Automatique et Systemes at the Ecole de Mines de Paris. In 2009, he joined the faculty of the Department of Aerospace and Mechanical Engineering at the University of Arizona, Tucson, where he was an Assistant Professor. In 2014, he joined the University of California, Santa Cruz, where he is currently Professor and Chair in the Department of Electrical and Computer Engineering. Prof. Sanfelice is the recipient of the 2013 SIAM Control and Systems Theory Prize, the National Science Foundation CAREER award, the Air Force Young Investigator Research Award, the 2010 IEEE Control Systems Magazine Outstanding Paper Award, and the 2020 Test-of-Time Award from the Hybrid Systems: Computation and Control Conference. He is Associate Editor for Automatica, Communicating Editor for the Journal of Nonlinear Science, and a Fellow of the IEEE. His research interests are in modeling, stability, robust control, observer design, and simulation of nonlinear and hybrid systems with applications to power systems, aerospace, and biology. Berk Altın (M’17) received the B.S. degree in mechatronics from Sabanci University, Istanbul, Turkey, in 2011, and the M.S. and Ph.D. degrees in electrical engineering: systems and the M.S. degree in mathematics from the University of Michigan, Ann Arbor, MI, USA, in 2013, 2016, and 2016, respectively. From 2011 to 2016, he was a Fulbright Fellow with the University of Michigan. In 2016, he joined the Hybrid Systems Laboratory, University of California, Santa Cruz, CA, USA, as a Post-Doctoral Researcher. Since 2021, he has been working in the autonomous vehicles industry as a Technical Lead and Planning and Control Software Engineer. His research interests include hybrid systems, model predictive control, iterative learning control, repetitive processes, and multidimensional systems, with applications in cyber-physical systems, power systems, robotics, and additive manufacturing.