Abstract
The hybrid minimum principle (HMP) is established for the optimal control of deterministic hybrid systems with both autonomous and controlled switchings and jumps where state jumps at the switching instants are permitted to be accompanied by changes in the dimension of the state space and where the dynamics, the running and switching costs as well as the switching manifolds and the jump maps are permitted to be time varying. First-order variational analysis is performed via the needle variation methodology and the necessary optimality conditions are established in the form of the HMP. A feature of special interest in this work is the explicit presentations of boundary conditions on the Hamiltonians and the adjoint processes before and after switchings and jumps. Analytic and numerical examples are provided to illustrate the results.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The minimum principle (MP), also called the maximum principle in the pioneering work of Pontryagin et al. [1], is a milestone of systems and control theory that led to the emergence of optimal control as a distinct field of research. This principle states that any optimal control along with the optimal state trajectory must solve a two-point boundary value problem in the form of an extended Hamiltonian canonical system, as well as satisfying an extremization condition of the Hamiltonian function. Whether the extreme value is maximum or minimum depends on the sign convention used for the Hamiltonian definition.
The main objective of this paper is the presentation and proof of the minimum principle for hybrid systems, i.e., the generalization of the MP for control systems with both continuous and discrete states and dynamics. It should be remarked that due to the development of hybrid systems theory in different scientific communities which are motivated by various applications, the domains of definition of hybrid systems do not necessarily intersect in a general class of systems. For instance, in computer science hybrid systems are viewed as finite automata interacting with an analogue environment, and therefore the emphasis is often on the discrete event dynamics [2,3,4,5,6,7,8,9], while in the control systems community, the continuous dynamics is more dominant in the discussion. Even in hybrid systems stability theory (see, e.g., [10,11,12,13,14,15,16,17]) the considered structures for hybrid control inputs are different from the admissible set of input values considered for optimal control purposes. Moreover, the definitions and the underlying assumptions for the class of hybrid optimal control problems in hybrid dynamic programming (HDP) [18,19,20,21,22,23,24,25,26] differ from those of the hybrid minimum principle (HMP) literature.
The formulation of the HMP by Clarke and Vinter [27, 28], referred to by them as “optimal multiprocesses,” provides a minimum principle for hybrid systems of a very general nature in which switching conditions are regarded as constraints in the form of set inclusions and the dynamics of the constituent processes are governed by (possibly nonsmooth) differential inclusions. A similar philosophy is followed by Sussmann [29, 30] where a nonsmooth MP is presented for hybrid systems possessing a general class of switching structures. Due to the generality of the considered structures in [27,28,29,30] degeneracy is not precluded, therefore additional hypotheses (typically of a controllabilty nature) need to be imposed to make the HMP results significantly informative (see, e.g., [31] for more discussion).
An alternative philosophy, followed by Shaikh and Caines [32], Garavello and Piccoli [33], Taringoo and Caines [34], and Pakniyat and Caines [35] is to ensure the validity of the HMP in a non-degenerate form by introducing hypotheses on the dynamics, transitions and switching events. Then by performing first-order variational analysis via the needle variation methodology, the necessary optimality conditions are established in the form of the HMP, with the emphasis of theoretical developments on generalization of the class of hybrid systems and on relaxation of regularity assumptions (see, e.g., [36] for a discussion on regulatory requirements in control theory). Moreover, non-degeneracy provided by this approach is advantageous in the development of numerical algorithms (see, e.g., [37,38,39,40,41,42,43,44,45,46]). Other, prior, versions of the HMP which appeared in its development within hybrid system theory are to be found in the work of Riedinger and Kratz [47], Xu and Antsaklis [48], Azhmyakov, Boltyanski and Poznyak [49], and Dmitruk and Kaganovich [50,51,52].
In past work of the authors (see [35, 53, 54]), a unified general framework for hybrid optimal control problems is presented within which the HMP, HDP, and their mutual relationship are valid. Distinctive aspects in this work are the presence of state dependent switching costs, the consideration of both autonomous and controlled switchings and jumps, and the possibility of state space and control space dimension changes. The latter aspect is of particular importance for systems with hybrid dynamics induced by restrictions of certain degrees of freedom (e.g., single- and double-support modes in legged locomotion [55] and fixed gear modes and transitioning phases in automotive systems [56, 57]). Within this general framework, it is proved that along optimal trajectories of a hybrid system, the adjoint process in the HMP, and the gradient of the value function in HDP are equal almost everywhere (see [53] for a proof method based on variations over optimal trajectories, and [35] for variations over general (i.e., not necessarily optimal) trajectories). Illustrative analytic examples are provided in [58,59,60].
In this paper, we further extend this framework to permit time-varying vector fields, switching manifolds, switching costs and jump transition maps and we present the statement and the proof of the hybrid minimum principle within this general framework. Distinctive aspects of this work are the explicit presentation of the boundary conditions on the Hamiltonians and adjoint processes (in contrast to their implicit expressions in [27,28,29,30, 33]), the relaxation of the regularity requirements (relative to, e.g., [32, 34]) and the presence of both autonomous and controlled switchings and jumps with switching costs and the possibility of state space dimension change (where only subsets of these features have been considered for the presentation of other versions of the HMP). Moreover, the explicit derivation of the boundary conditions in the HMP is presented within the general class of hybrid optimal control problems with time-varying vector fields, running and switching costs, jump transition maps and switching manifolds.
The organization of the paper is as follows: In Sect. 2, a definition of hybrid systems is presented that covers a general class of nonlinear systems on Euclidean spaces with autonomous and controlled switchings and jumps allowed at the switching states and times. Section 3 presents a general class of hybrid optimal control problems with a large range of running, terminal and switching costs. The regularity assumptions in Sects. 2 and 3 are attempted to be minimal, and they are imposed primarily to ensure the existence and uniqueness of solutions as well as continuous dependence on initial conditions. Further generalizations such as the lying of the system’s vector fields in Riemannian spaces [34, 61], nonsmooth assumptions [18, 19, 27,28,29,30], state-dependence of the control value sets [33], and stochastic hybrid systems [62], as well as restrictions to certain subclasses, such as those with regional dynamics [23, 24], and with specified families of jumps [18,19,20,21], become possible through variations and extensions of the framework presented here. The main result which is the statement and the proof of the hybrid minimum principle (HMP) is presented in Sect. 4 where first-order variational analysis is performed via the needle variation methodology and the necessary optimality conditions are established in the form of the HMP. To illustrate the results, four analytic and numerical examples are provided in Sect. 5. Concluding remarks are presented in Sect. 6.
2 Hybrid systems
Definition 1
A (deterministic) hybrid system (structure) \({\mathbb {H}}\) is a septuple
where the symbols in the expression and their governing assumptions are defined as below.
A0 \(H:=\coprod _{q\in Q}{\mathbb {R}}^{n_{q}}\) is called the (hybrid) state space of the hybrid system \({\mathbb {H}}\), where \(\coprod \) denotes disjoint union, i.e., \(\coprod _{q\in Q}{\mathbb {R}}^{n_{q}} = \bigcup _{q\in Q}\big \{ (q,x): x \in {\mathbb {R}}^{n_{q}} \big \}\), where
\(Q=\big \{ 1,2,...,\vert Q\vert \big \} \equiv \big \{ q_{1},q_{2},...,q_{\vert Q\vert }\big \},\vert Q\vert <\infty \), is a finite set of discrete states (components), and
\(\left\{ {\mathbb {R}}^{n_{q}}\right\} _{q\in Q}\) is a family of finite-dimensional continuous valued state spaces, where \(n_{q}\le n<\infty \) for all \(q\in Q\).
\(I:=\Sigma \times U\) is the set of system input values, where
\( \Sigma \) with \( \vert \Sigma \vert < \infty \) is the set of discrete state transition and continuous state jump events extended with the identity element,
\(U=\left\{ U_{q}\right\} _{q\in Q}\) is the set of admissible input control values, where each \(U_q \subset {\mathbb {R}}^{m_q}\) is a compact set in \({\mathbb {R}}^{m_q}\).
The set of admissible (continuous) control inputs \({\mathcal {U}}\left( U\right) :=L_{\infty }\left( \left[ t_{0},T_{*}\right) ,U\right) \), is defined to be the set of all measurable functions that are bounded up to a set of measure zero on \(\left[ t_{0},T_{*}\right) ,T_{*}<\infty \). The boundedness property necessarily holds since admissible inputs take values in the compact set U.
\(\Gamma :H\times \Sigma \rightarrow H\) is a time-dependent (partially defined) discrete state transition map.
\(A:Q\times \Sigma \rightarrow Q\) denotes both a deterministic finite automaton and the automaton’s associated transition function on the state space Q and event set \(\Sigma \), such that for a discrete state \(q\in Q\) only the discrete controlled and uncontrolled transitions into the q-dependent subset \(\left\{ A\left( q,\sigma \right) ,\sigma \in \Sigma \right\} \subset Q\) occur under the projection of \(\Gamma \) on its Q components: \(\Gamma :{\mathbb {R}}\times Q\times {\mathbb {R}}^{n}\times \Sigma \rightarrow H\vert _{Q}\). In other words, \(\Gamma \) can only make a discrete state transition in a hybrid state \(\left( q,x\right) \) if the automaton A can make the corresponding transition in q.
\(\Xi :H\times \Sigma \rightarrow H\) is a time-dependent (partially defined) continuous state jump transition map. For all \(\xi \in \Xi \), the functions \(\xi _{\sigma } \equiv \xi (\cdot , \cdot , \sigma ): [t_{0},t_{f}] \times {\mathbb {R}}^{n_q} \rightarrow {\mathbb {R}}^{n_p}\), \(p\in A\left( q,\sigma \right) \) are assumed to be jointly continuously differentiable in both the time \(t \in [t_{0},t_{f}]\) and the continuous state \(x \in {\mathbb {R}}^{n_q}\).
F is an indexed collection of vector fields \(\left\{ f_{q}\right\} _{q\in Q}\) such that there exist \(k_{f_q}\ge 1\) for which \(f_{q}\in C^{k_{f_q}} \left( [t_{0},t_{f}] \times {\mathbb {R}}^{n_q}\times U_q\rightarrow {\mathbb {R}}^{n_q}\right) \) satisfies a joint uniform Lipschitz condition, i.e., there exists \(L_{f}<\infty \) such that \(\left\| f_{q}\left( t_{1}, x_{1},u_{1}\right) -f_{q}\left( t_{2}, x_{2},u_{2}\right) \right\| \le L_{f}\left( \vert t_{1} - t_{2} \vert + \left\| x_{1}-x_{2}\right\| + \left\| u_{1}-u_{2}\right\| \right) \) for all \(q\in Q\), \(t_{1}, t_{2} \in [t_{0},t_{f}]\), \(x_{1},x_{2}\in {\mathbb {R}}^{n_q}\), \(u_1, u_2\in U_q\).
\({\mathcal {M}}=\left\{ m_{\alpha }:\alpha \in Q\times Q\right\} \) denotes a collection of switching manifolds such that, for any ordered pair \(\alpha \equiv \left( \alpha _1,\alpha _2\right) =\left( q,r\right) \), \(m_{\alpha }\) is a smooth, i.e., \(C^{\infty }\) codimension 1 sub-manifold of \([t_{0},t_{f}] \times {\mathbb {R}}^{n_q}\), described locally by \(m^{t}_{\alpha }=\left\{ x \in {\mathbb {R}}^{n_{\alpha _{1}}}: m_{\alpha }\left( t,x\right) =0 \right\} \), and possibly with boundary \(\partial m^{t}_{\alpha }\). It is assumed that \(m^{t}_{\alpha }\cap m^{t}_{\beta }=\emptyset \), whenever \(\alpha _1 = \beta _1\) but \(\alpha _2 \ne \beta _2\), for all \(\alpha ,\beta \in Q\times Q\), \(t \in [t_{0},t_{f}]\). \(\square \)
We note that the case where \(m^{t}_{\alpha }\) is identified with its reverse ordered version \(m^{t}_{{\bar{\alpha }}}\) giving \(m^{t}_{\alpha }=m^{t}_{{\bar{\alpha }}}\), is not ruled out by this definition, even in the non-trivial case \(m^{t}_{p,p}\) where \(\alpha _1 = \alpha _2 = p\). The former case corresponds to the common situation where the switching of vector fields at the passage of the continuous trajectory in one direction through a switching manifold is reversed if a reverse passage is performed by the continuous trajectory, while the latter case corresponds to the standard example of the bouncing ball.
Switching manifolds will function in such a way that whenever a trajectory governed by the controlled vector field meets the switching manifold transversally there is an autonomous switching to another controlled vector field or there is a jump transition in the continuous state component, or both. A transversal arrival on a switching manifold \(m^{t}_{q,r}\), at state \(x_q \in m^{t}_{q,r}=\left\{ x \in {\mathbb {R}}^{n_{q}}: m_{q,r}\left( t,x\right) =0 \right\} \) occurs whenever
for \(u_q\in U_q\), and \(q,r \in Q\). It is assumed that:
A1 The initial state \(h_{0}:=\left( q_{0},x(t_{0})\right) \in H\) is such that \(m_{q_{0},q_{j}}\left( t_{0}, x_{0}\right) \ne 0\), for all \(q_{j}\in Q\). \(\square \)
Definition 2
A hybrid input process is a pair \(I_{L}\equiv I_{L}^{\left[ t_{0},t_{f}\right) }:= \left( S_L,u\right) \) defined on a half open interval \(\left[ t_{0},t_{f}\right) \), \(t_{f}<\infty \), where \(u\in {{{\mathcal {U}}}}\) and \(S_L = \big (\left( t_{0},\sigma _{0}\right) , \left( t_{1},\sigma _{1}\right) , \cdots ,\) \(\left( t_{L},\sigma _{L}\right) \big )\), \(L<\infty \), is a finite hybrid sequence of switching events consisting of a strictly increasing sequence of times \(\tau _L:= \left\{ t_{0},t_{1},t_{2},\ldots ,t_{L}\right\} \) and a discrete event sequence \(\sigma \) with \(\sigma _0 = id\) and \(\sigma _i \in \Sigma \), \(i \in \left\{ 1,2,\cdots ,L\right\} \). \(\square \)
Definition 3
A hybrid state process (or trajectory) is a triple \(\left( \tau _L,q,x\right) \) consisting of the sequence of switching times \(\tau _L = \left\{ t_{0},t_{1},\ldots ,t_{L}\right\} \), \(L<\infty \), the associated sequence of discrete states \(q=\left\{ q_{0},q_{1},\ldots ,q_{L}\right\} \), and the sequence \(x(\cdot )=\left\{ x_{q_{0}}(\cdot ),x_{q_{1}}(\cdot ),\ldots ,x_{q_{L}}(\cdot )\right\} \) of piece-wise differentiable functions \(x_{q_{i}}(\cdot ):\left[ t_{i},t_{i+1}\right) \rightarrow {\mathbb {R}}^{n}\).\(\square \)
Definition 4
The input-state trajectory for the hybrid system \({\mathbb {H}}\) satisfying A0 and A1 is a hybrid input \(I_L = \left( S_L,u\right) \) together with its corresponding hybrid state trajectory \(\left( \tau _L,q,x\right) \) defined over \(\left[ t_{0},t_{f}\right) ,t_{f}<\infty \), such that it satisfies:
-
(i)
Continuous State Dynamics The continuous state component \(x(\cdot ) =\big \{ x_{q_{0}}(\cdot ), \) \( x_{q_{1}}(\cdot ),\ldots ,x_{q_{L}}(\cdot )\big \}\) is a piecewise continuous function which is almost everywhere differentiable and on each time segment specified by \(\tau _L\) satisfies the dynamics equation
$$\begin{aligned} {{\dot{x}}_{q_{i}}(t) = f_{q_{i}}\big (t,x_{q_{i}}(t),u(t)\big )}, \hspace{1 cm} {a.e.\; t\in \left[ t_{i},t_{i+1}\right) }, \end{aligned}$$(3)with the initial conditions
$$\begin{aligned} x_{q_{0}}(t_{0})&=x_{0} , \end{aligned}$$(4)$$\begin{aligned} x_{q_{i}}(t_{i})&= \xi _{\sigma _{i}}\big (t_{i},x_{q_{i-1}}(t_{i}-)\big ) := \xi _{\sigma _{i}}\bigg (\lim _{t\uparrow t_{i}} t , \lim _{t\uparrow t_{i}}x_{q_{i-1}}(t)\bigg ) , \end{aligned}$$(5)for \(\left( t_{i},\sigma _{i}\right) \in S_L\). In other words, \(x(\cdot )=\left\{ x_{q_{0}}(\cdot ),x_{q_{1}}(\cdot ),\ldots ,x_{q_{L}}(\cdot )\right\} \) is a piecewise continuous function which is almost everywhere differentiable and is such that each \(x_{q_{i}}(\cdot )\) satisfies
$$\begin{aligned} x_{q_{i}}(t)=x_{q_{i}}(t_{i})+\int _{t_{i}}^{t}f_{q_{i}}\left( s,x_{q_{i}}(s),u(s)\right) \textrm{d}s, \end{aligned}$$(6)for \(t \in \left[ t_{i},t_{i+1}\right) \).
-
(ii)
Autonomous Discrete Transition Dynamics An autonomous (uncontrolled) discrete state transition from \(q_{i-1}\) to \(q_i\) together with a continuous state jump \(\xi _{\sigma _i}\) occurs at the autonomous switching time \(t_i\) if \(x_{q_{i-1}}(t_{i}-):=\lim _{t\uparrow t_{i}}x_{q_{i-1}}(t)\) satisfies a switching manifold condition of the form
$$\begin{aligned} m_{q_{i-1}q_i}\left( t_{i}, x_{q_{i-1}}(t_{i}-)\right) = 0, \end{aligned}$$(7)for \(q_i\in Q\), where \(m_{q_{i-1}q_i}\left( t,x\right) = 0\) defines a \(\left( q_{i-1},q_i\right) \) switching manifold and it is not the case that either \(\left( i\right) \) \(x(t_{i}-)\in \partial m_{q_{i-1}q_i}\) or \(\left( ii\right) \) \(f_{q_{i-1}}\left( t_{i}, x(t_{i}-),u(t_{i}-)\right) \perp \nabla m_{q_{i-1}q_i}\left( t_{i}, x(t_{i}-)\right) \), i.e., \(t_i\) is not a manifold termination instant (see [63]). With the assumptions A0 and A1 in force, such a transition is well defined and labels the event \(\sigma _{i} \equiv \sigma _{q_{i-1}q_i} \in \Sigma \), that corresponds to the hybrid state transition
$$\begin{aligned} h(t_{i}) \equiv \left( q_{i},x_{q_{i}}(t_{i})\right) = \left( \Gamma \left( t_{i},q_{i-1}, x_{q_{i-1}}(t_{i}-),\sigma _{i}\right) ,\xi _{\sigma _{i}} \left( t_{i}, x_{q_{i-1}}(t_{i}-)\right) \right) . \end{aligned}$$(8) -
(iii)
Controlled Discrete Transition Dynamics A controlled discrete state transition together with a controlled continuous state jump \(\xi _{\sigma _i}\) occurs at the controlled discrete event time \(t_i\) if \(t_i\) is not an autonomous discrete event time and if there exists a controlled discrete input event \(\sigma _{i} \in \Sigma \) for which
$$\begin{aligned} h(t_{i}) \equiv \left( q_{i},x_{q_{i}}(t_{i})\right) = \left( \Gamma \left( t_{i},q_{i-1}, x_{q_{i-1}}(t_{i}-),\sigma _{i}\right) ,\xi _{\sigma _{i}} \left( t_{i}, x_{q_{i-1}}(t_{i}-)\right) \right) , \end{aligned}$$(9)with \(\left( t_{i},\sigma _{i}\right) \in S_L\) and \(q_{i}\in A\left( q_{i-1}\right) \). \(\square \)
An example hybrid automata with both autonomous (displayed in red arrows) and controlled (displayed in green arrows) switchings (color figure online)
To illustrate the notation, Fig. 1 provides an example hybrid automata with both autonomous and controlled switchings. In this example, the discrete component of the state takes values from \(Q = \{p,q,r\}\), i.e., \(|Q |= 3\) \(|Q |= 3\) within each mode the evolution of the continuous component of the state is governed by a controlled differential equation. Transitions from q to r and from r to p are autonomous (displayed in red arrows) whereas transitions from p to q, from q to p and from q to r are controlled switchings (displayed in green arrows). In this example, there is no direct transition from p to r. The indexed vector fields, the underlying spaces for the state and input values, as well as switching manifold and jump maps are displayed in this figured.
A2 For a specified sequence of discrete states \(\left\{ q_i\right\} _{i=0}^{L}\), the class of input-state trajectories is non-empty. In other words, there exist \(S_L = \big (\left( t_{0},\sigma _{0}\right) , \left( t_{1},\sigma _{1}\right) , \cdots , \left( t_{L},\sigma _{L}\right) \big ) \equiv \big (\left( t_{0},q_{0}\right) , \left( t_{1},q_{1}\right) , \cdots , \left( t_{L},q_{L}\right) \big )\) and \(u_{q_i} \in L_{\infty }\left( \left[ t_{i},t_{i+1}\right) , U_{q_i}\right) \) that together with its corresponding hybrid state process form an input-state trajectory in Definition 4. \(\square \)
Theorem 1
[63] A hybrid system \({\mathbb {H}}\) with an initial hybrid state \(\left( q_{0},x_{0}\right) \) satisfying assumptions A0 and A1 possesses a unique hybrid input-state trajectory on \(\left[ t_{0},T_{**}\right) \), where \(T_{**}\) is the least of
-
(i)
\(T_{*} \le \infty \), where \(\left[ t_{0},T_{*}\right) \) is the temporal domain of the definition of the hybrid system,
-
(ii)
A manifold termination instant \(T_{*}\) of the trajectory \(h(t) = h\left( t,\left( q_0,x_0\right) ,\left( S_L,u\right) \right) \), \(t\ge t_0\), at which either \(x\left( T_{*}-\right) \in \partial m_{q\left( T_*-\right) q\left( T_*\right) }\) or \(f_{q\left( T_*-\right) }\left( x\left( T_*-\right) ,u\left( T_*-\right) \right) \perp \nabla m_{q\left( T_*-\right) q\left( T_*\right) }\left( x\left( T_{*}-\right) \right) \). \(\square \)
We note that Zeno times, i.e., accumulation points of discrete transition times, are ruled out by A2.
Lemma 1
State processes of a hybrid system satisfying Assumptions A0-A2 are continuously dependent on their initial conditions. In other words, for a given \(\left\{ q_i\right\} _{i=0}^{L}\) and an initial continuous state \(x_0 \in {\mathbb {R}}^{n_{q_0}}\), there exist a neighborhood \(N\left( x_0\right) \) and a constant \(0<K<\infty \) such that
for \(s \ge t_0\) and \(x_s \in N\left( x_0\right) \). \(\square \)
Proof
See Appendix A. \(\square \)
3 Hybrid optimal control problems
A3 Let \(\left\{ l_{q}\right\} _{q\in Q},l_{q}\in C^{n_{l}}\left( {\mathbb {R}}^{n}\times U\rightarrow {\mathbb {R}}_{+}\right) ,n_{l}\ge 1\), be a family of cost functions with \(n_l = 2\) unless otherwise stated; \(\left\{ c_{\sigma }\right\} _{\sigma \in \Sigma }\in C^{n_{c}}\left( {\mathbb {R}}^{n}\times \Sigma \rightarrow {\mathbb {R}}_{+}\right) ,n_{c}\ge 1\), be a family of switching cost functions; and \(g\in C^{n_{g}}\left( {\mathbb {R}}^{n}\rightarrow {\mathbb {R}}_{+}\right) ,n_{g}\ge 1\), be a terminal cost function satisfying the following assumptions:
-
(i)
There exists \(K_{l}<\infty \) and \(1\le \gamma _{l}<\infty \) such that \(\vert l_{q}(x,u)\vert \le K_{l}\big ( 1+\Vert x\Vert ^{\gamma _{l}}\big )\) and \(\vert l_{q}(x_{1},u_{1})-l_{q}(x_{2},u_{2}) \vert \le K_{l}\big (\Vert x_{1}-x_{2}\Vert +\Vert u_{1}-u_{2}\Vert \big )\), for all \(x\in {\mathbb {R}}^{n},u\in U,q\in Q\).
-
(ii)
There exists \(K_{c}<\infty \) and \(1\le \gamma _{c}<\infty \) such that \(\vert c_{\sigma }\left( x\right) \vert \le K_{c}\left( 1+\left\| x\right\| ^{\gamma _{c}}\right) \), \(x\in {\mathbb {R}}^{n},\sigma \in \Sigma \).
-
(iii)
There exists \(K_{g}<\infty \) and \(1\le \gamma _{g}<\infty \) such that \(\vert g\left( x\right) \vert \le K_{g}\left( 1+\left\| x\right\| ^{\gamma _{g}}\right) \), \(x\in {\mathbb {R}}^{n}\). \(\square \)
Consider the initial time \(t_{0}\), final time \(t_{f}<\infty \), and initial hybrid state \(h_{0}=\left( q_{0},x_{0}\right) \). With the number of switchings L held fixed, the set of all hybrid input trajectories in Definition 2 with exactly L switchings is denoted by \(\varvec{I_{L}}\), and for all \(I_{L}:=\left( S_{L},u\right) \in \varvec{I_{L}}\) the hybrid switching sequences take the form \(S_{L}= \left\{ \left( t_{0},id\right) ,\left( t_{1},\sigma _{q_{0}q_{1}}\right) , \ldots , \left( t_{L},\sigma _{q_{L-1}q_{L}}\right) \right\} \equiv \left\{ \left( t_{0},q_{0}\right) ,\left( t_{1},q_{1}\right) ,\ldots ,\left( t_{L},q_{L}\right) \right\} \) and the corresponding continuous control inputs are of the form \(u\in {\mathcal {U}} = \bigcup _{i=0}^{L} L_{\infty }\left( \left[ t_i,t_{i+1}\right) ,U\right) \), where \(t_{L+1}=t_f\).
Let \(I_{L}\) be a hybrid input trajectory that by Theorem 1 results in a unique hybrid state process. Then hybrid performance functions for the corresponding hybrid input-state trajectory are defined as
Definition 5
The (Bolza) Hybrid Optimal Control Problem (HOCP) is defined as
that is, the infimization of the hybrid cost (11) over the family of hybrid input trajectories \(\varvec{I_{L}}\). \(\square \)
4 The hybrid minimum principle (HMP)
Theorem 2
Consider the hybrid system \({\mathbb {H}}\) subject to assumptions A0-A3, and the HOCP (12) for the hybrid performance function (11). Define the family of system Hamiltonians by
\(x_q, \lambda _q \in {\mathbb {R}}^{n_{q}}\), \(u_q \in U_{q}\), \(q\in Q\), and let \(\left\{ q_i\right\} _{i=0}^{L}\) be a specified sequence of discrete states with its associated set of switchings. Then for an optimal input \(u^{o}\) and along the corresponding optimal trajectory \(x^{o}\), there exists an adjoint process \(\lambda ^{o}\) such that
for all \(v\in U_{q}\), and at almost every \(t \in [t_{0},t_{f}]\), where \((x^{o},\lambda ^{o})\) satisfy
almost everywhere \(\; t\in \left[ t_{0},t_{f}\right] \), subject to
where \(p_j \in {\mathbb {R}}\) when \(t_{j}\) indicates the time of an autonomous switching, subject to the switching manifold condition \(m_{q_{j-1}q_j}\big (x^o_{q_{j-1}}(t_{j}-)\big ) = 0\), and \(p_j=0\) when \(t_{j}\) indicates the time of a controlled switching. Moreover, the Hamiltonian satisfies
which, with the expansion of the Hamiltonians from (13), is expressed as
\(\square \)
Proof
First, in the first part of the proof (Sect. 4.1), we study a needle variation to the optimal input at the last location \(u^o_{q_L}\) at a Lebesgue instantFootnote 1\(t \in \left( t_L,t_{L+1}\right] \equiv \left( t_L,t_f\right] \) to derive the Hamiltonian canonical equations (15) and (16), the adjoint terminal condition (19), and the Hamiltonian minimization condition (14) in that location. This part of the proof is similar to the proof of the classical Pontryagin minimum principle.
Next, in the second part of the proof in Sect. 4.2, we perform a variation in the penultimate, \(L-1{\text {st}}\), location in order to obtain \(\left( i\right) \) Hamiltonian canonical equations (15) and (16), and \(\left( ii\right) \) the Hamiltonian minimization condition (14) at the location \(q_{L-1}\), as well as \(\left( iii\right) \) the boundary conditions (18) and (20), and \(\left( iv\right) \) the Hamiltonian boundary condition (21) at time \(t_L\).
Then, in the last part of the proof (Sect. 4.3), we extend the analysis for a general switching instant \(t_j\) and prove that \(\left( i\right) \) to \(\left( iv\right) \) above hold for all locations.
In order to provide the simplest derivation of the main result we define
such that \(\theta \) gives the current time and z provide the incurred cost, i.e., at \(t \in [t_{0},t_{f}]\), we have \(\theta (t) = t\) and \(z_{q}(t) = \int _{t_{N_\textrm{sw}(t)}}^{t} l_{q}\left( x_{q}(s),u(s)\right) \textrm{d}s + \sum _{i=0}^{N_\textrm{sw}(t)-1}\int _{t_{i}}^{t_{i+1}}l_{q_{i}}\left( x_{q_{i}}(s),u(s)\right) \textrm{d}s+\sum _{j=1}^{N_\textrm{sw}(t)-1}c_{\sigma _{j}}\left( t_{j},x_{q_{j-1}}(t_{j}-)\right) \) with \(N_\textrm{sw}(t)\) denoting the number of incurred switchings over the interval \([t_{0},t)\). This yields the augmented vector fields as
subject to the initial condition
with the switching manifold
and the extended jump function defined as
This transform the problem into a time invariant, Mayer (without running or switching cost) HOCP in the form of
4.1 The last discrete state location
First, consider a Lebesgue time \(t \in \left( t_L,t_{L+1}\right] \equiv \left( t_L,t_f\right] \) and the evolution of the optimal state \({\tilde{x}}^{o}(\tau )\), \(\tau \in \left[ t_0,t_f\right] \), governed by the set of differential equations
We perform a needle variation at a Lebesgue time t in the form of
This corresponds to a perturbed trajectory \({\tilde{x}}^{\epsilon }\left( \tau \right) , \tau \in \left[ t_0,t_f\right] \) which coincides with the optimal trajectory \({\tilde{x}}^{o}\left( \tau \right) , \tau \in \left[ t_0,t_f\right] \) over the interval \([t_{0},t-\epsilon )\) but differs over \([t-\epsilon ,t_{f}]\). Denoting \(\delta {\tilde{x}}_{q_{L}}^{\epsilon }(\tau ):={\tilde{x}}_{q_{L}}^{\epsilon }(\tau )-{\tilde{x}}_{q_{L}}^{o}(\tau )\), it necessarily satisfies \(\delta {\tilde{x}}_{q_{i}}^{\epsilon }(\tau ) = 0\) for \(\tau \in \left[ t_0,t-\epsilon \right) \), \(0 \le i \le L\), and for \(\tau \in \left[ t-\epsilon ,t_f\right] \) it satisfies
Defining the first-order sensitivity of the (augmented) state as
the dynamics and boundary conditions of the first-order sensitivity are derived as
Denoting the state transition matrix corresponding to (33) by \(\Phi _{q_{L}}\), it is shown by linearization theory (see, e.g., [63, 66]) that
The optimality of \({\tilde{x}}^o\) implies that
which, using (28) and employing first-order Taylor expansion, it is equivalent to
Substitution of (35) into (37) results in
Defining the (augmented) adjoint variable (process) as
for \(t\in \left( t_L,t_f\right] \) and evaluating it at \(t=t_f\) we obtain
where by the definition (28) for \({\tilde{g}}\), this is equivalent to
Also by differentiation of (39) with respect to t we obtain the dynamics of the augmented adjoint process as
which is equivalent to
The zero dynamics (45) and (46) with the terminal conditions (41) and (42) give \(\lambda _{\theta ,q_{L}}^{o}(t) = 0\) and \(\lambda _{z,q_{L}}^{o}(t) = 1\), for all \(t\in \left( t_L,t_f\right) \), and equation (47) is equivalent to
which is valid on \(\left( t_L,t_f\right) \) and where by definition
From the definition of Hamiltonian (49) and through a simple differentiation, the Hamiltonian canonical equation (15) for the state is also verified.
Also from (38) and (49) the Hamiltonian minimization
is obtained for all \(v\in U_{q_{L}}\).
4.2 The penultimate location
Now consider a needle variation at time \(t \in \left( t_{L-1},t_L\right] \) in the form of
where \(\delta ^{\epsilon } \ge 0\) corresponds to the case when the perturbed trajectory arrives on the switching manifold \({\tilde{m}} \left( {\tilde{x}}\right) := m_{q_{L-1}q_L}\left( x\right) = 0\) at an earlier instant. The case with a later arrival time, i.e., \(\delta ^{\epsilon } \le 0\) is handled in a similar fashion, and the case of a controlled switching, i.e., with no switching manifold, can be derived similarly by setting \(\delta ^{\epsilon } = 0\).
For \(\tau \in \left[ t,t_L-\delta ^\epsilon \right) \) we may write
At the last switching time \(t_L\), the state of the optimal trajectory is determined (see also Fig. 2 with the consider of \(n=L\)) by
and the state of the perturbed trajectory is calculated as
Thus (see also Fig. 2),
Now, let us define \(\mu _L:=\epsilon {\rightarrow _0}{\lim }\frac{\delta ^{\epsilon }}{\epsilon }\). If \(t_L\) is the time of a controlled switching then \(\mu _L = 0\) since \(\delta ^{\epsilon } = 0\) for every \(\epsilon \). In order to determine \(\mu _L\) for the case of an autonomous switching, we note that by the switching manifold conditions (7) it must be the case for both \(x^o\) and \(x^{\epsilon }\) that
since \({\tilde{x}}_{q_{L-1}}^{o}\) arrives on the switching manifold at \(t_{L}-\), and \({\tilde{x}}_{q_{L-1}}^{\epsilon }\) arrives at \(t_{L}-\delta ^{\epsilon }-\). Moreover, from the Taylor expansion of \({\tilde{m}}\), we have
which yields
Noting that, by definition, \(y_{q_{L-1}}(t_{L}-)=\lim _{\epsilon \rightarrow 0}\frac{1}{\epsilon }\delta {\tilde{x}}_{q_{L-1}}^{\epsilon }(t_{L}-)\) and that
we obtain a closed-form expression for \(\mu _L\) from (58) in the form of
Hence, by diving both sides of (55) by \(\epsilon \), using a similar Taylor expansion of \({\tilde{\xi }}\) and then taking the limit as \(\epsilon \rightarrow 0\), we obtain the relationship between the values before and after the switching of the first-order sensitivity of the (augmented) state as
where
Similar to part A, the dynamics and boundary conditions of the first-order state sensitivity are derived as
and, hence,
Therefore, the optimality condition (37) is expressed as
with
Defining the (augmented) adjoint process in the interval \(t\in \left( t_{L-1},t_L\right] \) as
and evaluating it at \(t=t_L\) we obtain
By the definition of \({\tilde{\xi }}\) in (27), we have
and since also \(\frac{\partial m}{\partial z} = 0\) we have
Hence, (71) is equivalent to
which, for each of the primary components of the augmented adjoint process, it is written as
Differentiating (70) with respect to t leads to
which is equivalent to
Therefore, \(\lambda _{q_{L-1},0}^{o}(t)=1\) for \(t\in \left( t_{L-1},t_L\right) \) is obtained as before and
holds for \(t\in \left( t_{L-1},t_L\right) \) with the Hamiltonian defined as
Also from (68) the minimization of the Hamiltonian is concluded as
for all \(v\in U_{q_{L-1}}\), a.e. \(t\in \left( t_{L-1},t_L\right) \). It shall be remarked that the Hamiltonian for the time-invariant system with the augmented states (23) includes an additional constant term, i.e.,
but \(\lambda _{q,\theta }\) does not play a role in the adjoint dynamics (82) or in the Hamiltonian minimization (84).
In order to obtain the Hamiltonian boundary condition (21) (equivalently, (22)) at \(t_L\), we evaluate both \(H_{q_{L-1}}\) and \(H_{q_L}\) at \(t_L\) and invoke the previously established relations (as referenced therein) to arrive at
which is equivalent to (21).
The evolution of the original augmented trajectory \({\tilde{x}}^{o}\) arriving on the (augmented) switching manifold at \(t_n^o\) and a perturbed trajectory \({\tilde{x}}^{\epsilon }\) arriving at an earlier time \(t_n^o - \delta _n^{\epsilon }\)
4.3 Other locations
We now consider a needle variation at a general Lebesgue time \(t \in \left( t_{n-1},t_n\right) \) in the form of
As before (see also Fig. 2), the first-order sensitivity of the augmented state before the switching is derived as
and its value after the switching is derived as
Therefore, its propagation until the terminal time is written as
where
and
The optimality condition (37) is expressed as
Defining the augmented adjoint process within the interval \(\left( t_{n-1},t_n\right] \) by
which is, after the implementation of the transpose, equivalent to
we may evaluate (95) at \(t=t_n\) to obtain
or
Having established (71), we take the (backward) induction hypothesis as
and denote the scalar product
Then equation (97) becomes
Since the induction hypothesis (98) is proved to hold as (71) for \(n=L-1\), and since (98) for n implies (100), the boundary condition (20) is deduced from (100) in a similar way as shown in (72) to (77), i.e., (100) is equivalent to
This gives
Differentiating (95) with respect to t leads to
which is equivalent to
Therefore, the constants \(\lambda _{q_{n-1},\theta }^{o}(t)=\sum _{i=n}^{L}\frac{\partial c_{\sigma _{i}}}{\partial t}+\left[ \frac{\partial \xi _{\sigma _{i}}}{\partial t}\right] ^{\top }\lambda _{q_{i}}^{o}(t_{i}+)+p\frac{\partial m_{q_{i-1}q_{i}}}{\partial t}\), and \(\lambda _{q_{n-1},z}^{o}(t)=1\), for \(t\in \left( t_{n-1},t_n\right) \) are obtained as before and
holds for \(t\in \left( t_{n-1},t_n\right) \) with the Hamiltonian defined as
Also from (93) the minimization of the Hamiltonian is concluded, i.e.,
for all \(v\in U_{q_{n-1}}\).
In order to obtain the Hamiltonian boundary condition (21) (equivalently, (22)) at \(t_n\), we evaluate both \(H_{q_{n-1}}\) and \(H_{q_n}\) at \(t_n\) and invoke the previously established relations (as referenced therein) to arrive at
which is equivalent to (21). This completes the proof of the hybrid minimum principle. \(\square \)
5 Analytic examples
5.1 Example 1
Consider a hybrid system with the indexed vector fields:
and the hybrid optimal control problem
subject to the initial condition \(h_{0}=\left( q(t_{0}),x(t_{0})\right) =\left( q_1,x_{0}\right) \) provided at the initial time \(t_{0}=0\). At the controlled switching instant \(t_s\), the boundary condition for the continuous state is provided by the jump map \(x\left( t_{s}\right) =\xi \left( x\left( t_{s}-\right) \right) =-x\left( t_{s}-\right) \).
5.1.1 The HMP formulation
Writing down the hybrid minimum principle results for the above HOCP, the Hamiltonians are formed as
from which the minimizing control input for both Hamiltonian functions is determined as
Therefore, the adjoint process dynamics, determined from (16) and with the substitution of the optimal control input from (118), is written as
which are subject to the terminal and boundary conditions
The substitution of the optimal control input (118) in the continuous state dynamics (15) gives
which are subject to the initial and boundary conditions
The Hamiltonian continuity condition (21) states that
which can be written, using (126), as
The optimal state and adjoint processes, optimal inputs and the Hamiltonians for the system in Example 1 with \(x_{0}=0.5\) and \(t_{f}=4\)
5.1.2 The HMP results
The solution to the set of ODEs (119), (120), (123), (124) together with the initial condition (125) expressed at \(t_0\), the terminal condition (121) determined at \(t_f\) and the boundary conditions (126) and (122) provided at \(t_s\) which is not a priori fixed but determined by the Hamiltonian continuity condition (128), provides the optimal control input and its corresponding optimal trajectory that minimize the cost \(J\left( t_{0},t_{f},h_{0},1;I_1\right) \) over \(\varvec{I_{1}}\), the family of hybrid inputs with one switching. The numerical results for \(x_{0}=0.5\) and \(t_{f}=4\) are illustrated in Fig. 3. Interested readers are referred to [58] for further analytic steps to reduce the above boundary value ODE problem into a set of algebraic equations using the special forms of the differential equations under study.
5.2 Example 2
Consider the hybrid system with the indexed vector fields
and
where autonomous switchings occur on the switching manifold described by
with the continuity of the trajectories at the switching instant. Consider the hybrid optimal control problem defined as the minimization of the total cost functional
5.2.1 The HMP formulation and results
Employing the HMP, the corresponding Hamiltonians are defined as
and
The Hamiltonian minimization with respect to u (Eq. (14)) gives
for both \(q=1\) and \(q=2\).
Therefore the state dynamics (15) and the adjoint process dynamics (16) become
for \(q=1\), and
for \(q=2\). At the initial time \(t=t_0\), the continuous valued states are specified by the initial conditions
At the switching instant \(t=t_s\), the boundary conditions for the states and adjoint processes are determined as
And at the terminal time \(t=t_f\), the adjoint processes are determined by (19) as
Note that unlike \(t_0\) and \(t_f\) which are a priori determined, \(t_s\) is not fixed and needs to be determined by the Hamiltonian continuity condition (21) as
i.e.,
that with the insertion of (149), it becomes
The set of ODEs (136) to (143), together with the initial conditions (144) and (145) expressed at \(t_0\), the boundary conditions (146), (198), (148) and (149) provided at \(t_s\), and the terminal conditions (150) and (151) determined at \(t_f\), with the two unknowns \(t_s\) and p determined by the Hamiltonian continuity condition (154) and the switching manifold condition (131), form an ODE boundary value problem whose solution results in the determination of the optimal control input and its corresponding optimal trajectory that minimize the cost \(J\left( t_{0},t_{f},h_{0},1;I_1\right) \) over \(\varvec{I_{1}}\), the family of hybrid inputs with one switching on the switching manifold (131).
5.2.2 Analytical solution to the HMP
Similar to the previous example, further steps can be taken in order to reduce the above boundary value ODE problem into a set of algebraic equations using the special forms of the differential equations under study. This has been done in detail in [60], and a brief version is provided here.
From (142) and (148) we may write
Therefore, the dynamics of the second component of the adjoint process in \(\left( t_{s},t_{f}\right] \) is determined from (143) as
which from (151) we conclude that
The boundary conditions (148) and (149) on adjoint processes at the switchings instant give
The conditions (158) and (159) serve as terminal conditions for the adjoint processes dynamics (138) and (138) which have a general solution of the form
Therefore, the state dynamics (136) and (137) are written as
for \(t\in \left[ t_{0},t_{s}\right] \), which have a general solution of the form
for \(t\in [t_{0},t_{s} ) = [{0},t_{s}) \), subject to the initial conditions
At the switching time \(t_{s}\) the continuity condition for \(x_{1}\) and \(x_{2}\) are written as
which form the initial conditions for the state dynamics in \(q_2\) and \(t\in \left[ t_{s},t_{f}\right] \), determined from (140) and (141) as
The above equations have the solution
for \(t\in \left[ t_{s},t_{f}\right] \). Since (173) is expressed implicitly in terms of \(x_{2}\left( t_{f}\right) \), we evaluate (173) at \(t_{f}\) to write an explicit form for \(x_{2}\) as
which gives
The optimal trajectory components \(x_{1}^o\) and \(x_{2}^o\), the corresponding adjoint process components \(\lambda _{1}^o\) and \(\lambda _{2}^o\), the optimal control input \(u^{o}\) and the corresponding Hamiltonian \(H \left( x^o, \lambda ^o, u^o\right) \) in Example 2 with \(t_{0}=0\), \(x_{10}=1\), \(x_{20}=-0.5\), \(t_{f}=5\) and \(v_\mathrm{{ref}}=1\)
Substitution of (175) into (172) and (173) results in
for \(t\in \left[ t_{s},t_{f}\right] \). This gives the adjoint boundary conditions (158) and (159) as
The switching manifold condition (169) states that
and the Hamiltonian continuity condition (154) gives
Hence, by solving simultaneously the set of 6 equations (166), (167), (178), (179), (180), and (181) for the given \(t_{0}=0\), \(t_{f}<\infty \), \(x\left( t_{0}\right) \equiv \left[ x_{10},x_{20}\right] ^{T}\) and \(v_\textrm{ref}\) the values of the 6 unknown parameters \(A,\alpha ,B,\beta ,t_{s}\) and p are determined. For the values of \(t_{0}=0\), \(x_{10}=1\), \(x_{20}=-0.5\), \(t_{f}=5\) and \(v_\textrm{ref}=1\) the results are demonstrated in Fig. 4.
5.3 Example 3
Consider the hybrid system with the indexed vector fields
and
where autonomous switchings occur on the switching manifold described by
with the jump map
Consider the hybrid optimal control problem defined as the minimization of the total cost functional
5.3.1 The HMP formulation and results
Employing the HMP, the corresponding Hamiltonians are defined as
The Hamiltonian minimization with respect to u (Eq. (14)) yields
Therefore the state dynamics (15) and the adjoint process dynamics (16) become
for \(q = 1\), and
for \(q =2\).
At the initial time \(t=t_0\), the continuous valued states are specified by the initial condition
At the switching instant \(t=t_s\), the switching manifold condition
must hold, and the boundary conditions for the states and adjoint processes are determined as
And at the terminal time \(t=t_f\), the adjoint processes are determined by (19) as
Note that unlike \(t_0\) and \(t_f\) which are a priori determined, \(t_s\) is not fixed and, together with the unknown parameter p, they need to be determined by the switching manifold condition (196) and the Hamiltonian continuity condition (21) as
The optimal trajectory \(x^o\), the corresponding adjoint process \(\lambda ^o\) and the corresponding Hamiltonian \(H \left( x^o, \lambda ^o, u^o\right) \) in Example 3 over the horizon \([t_{0},t_{f}]=[0,3]\) with \(x_{0}=\left[ \begin{array}{cccc} -2&0&3&-2\end{array}\right] ^{\top }\), an autonomous switching with the switching manifold \(x^{(3)}(t_{s}-) = 0\), and the jump maps \(\left[ \begin{array}{ccc} x^{(1)}(t_{s})&x^{(2)}(t_{s})&x^{(3)}(t_{s})\end{array}\right] ^{\top }=\left[ \begin{array}{ccc} 2x^{(1)}(t_{s}-)&\dfrac{1}{2}x^{(2)}(t_{s}-)&3x^{(4)}(t_{s}-)\end{array}\right] ^{\top }\)
5.3.2 Numerical solution to the HMP
In order to numerically solve the HMP results, we employ the HMP–MAS Conceptual Algorithm presented in [67] and we exploit the analytical availability of trajectory solutions due to the linearity of dynamics before and after switching to expedite the algorithm. More specifically, the algorithm initiation consists of selecting arbitrary switching time \(t_s^0 \in (t_0,t_f)\) and pre-switching state \(x_s^0 \in {\mathbb {R}}^4\) such that the switching manifold condition \(m(x_s^0) = 0\) holds. Then, at each iteration k the hybrid optimal control problem decomposes into two decoupled auxiliary classical (non-hybrid) optimal control problems, one with the dynamics \({\dot{x}} = A_1 x + B_1 u\) with fixed initial and terminal states \(x_0\) at \(t_0\) and \(x_s^k\) at \(t_s^k\) with the cost \(J_1 = \int _{t_0}^{t_s^k} \frac{1}{2} u^2 ds\) and the other with the dynamics \({\dot{x}} = A_2 x + B_2 u\) with a fixed initial state \({\tiny \left[ \begin{array}{cccc} 2 &{} 0 &{} 0 &{} 0\\ 0 &{} {1}/{2} &{} 0 &{} 0\\ 0 &{} 0 &{} 0 &{} 3 \end{array}\right] }x_{s}^{k}\) at \(t_s^k\) and a free terminal state and with the cost \(J_2 = \int _{t_s^k}^{t_f} \frac{1}{2} u^2 \textrm{d}s\). At each iteration, the adjoint process of the first auxiliary problem is determined from \(\lambda _{q_1}^k(t) = \exp (- A_1^\top t) [{\mathcal {G}}(t_0,t_s^k)]^{-1} \big (x_0 - \exp (- A_1 (t_s^k - t_0)) x_s^k\big )\) where \({\mathcal {G}}(t_0,t_s^k) = \int _{t_0}^{t_s^k} \exp (- A_1 \tau ) B_1 B_1^\top \exp (- A_1^\top \tau ) \textrm{d}\tau \) is the controllability Gramian; and the adjoint process of the second auxiliary problem is determined from \(\lambda _{q_2}^k(t) = \Pi _2(t) x(t)\), where \(\Pi _2\) is the solution of the Riccati equation \({\dot{\Pi }}_2 = \Pi _2 B_2 B_2^\top \Pi _2 - A_2^\top \Pi _2 - \Pi _2 A_2\) subject to the terminal condition \(\Pi _2(t_f) = 4 \, I_{3 \times 3}\).
Then the algorithm updates \(t_s^k\) and \(x_s^k\) according to
where \(r_{k} \in (0,1)\) is a set of monotonically non-decreasing sequence of step sizes and
For the initial condition \(x_{0}=\left[ \begin{array}{cccc} -2&0&3&-2\end{array}\right] ^{\top }\), over the time horizon [0, 3] and with the initial guesses \(t_s^0 = 1.5\), \(x_{s}^{0}=\left[ \begin{array}{cccc} 0&2&0&-1\end{array}\right] ^{\top }\), the algorithm converges with \(\epsilon = 0.001\) to \(|H_{2}^{k}(t_{s}^{k}+)-H_{1}^{k}(t_{s}^{k}-)|^{2}+\left\| \lambda _{q_{1}}^{k}(t_{s}^{k})-{\tiny \left[ \begin{array}{ccc} 2 &{} 0 &{} 0\\ 0 &{} \frac{1}{2} &{} 0\\ 0 &{} 0 &{} 0\\ 0 &{} 0 &{} 3 \end{array}\right] }\lambda _{q_{2}}^{k}(t_{s}^{k}+)-\frac{1}{4}x_{s}^{k}\right\| ^{2}+|m(x_{s}^{k})|^{2}\) within the order of \(10^5\) steps and the corresponding results are displayed in Fig. 5.
5.4 Example 4
Consider the hybrid model of an electric vehicle equipped with a dual planetary transmission (presented in detail in [56]) with the set of (active) vector fields F given as
where \(x_{q_1}, x_{q_2}, x_{q_4}, \in {\mathbb {R}}\), \(x_{q_3} \in {\mathbb {R}}^2\) are the continuous components of the hybrid state, with the notation \(x_{q_i}^{(j)}\) used for denoting the \(j^{\text {th}}\) component, and \(u_{q_1}, u_{q_2}, u_{q_4}\in \left[ -1,1\right] \subset {\mathbb {R}}\), \(u_{q_3}\in \left[ -1,1\right] ^3 \subset {\mathbb {R}}^3\) are the continuous components of the hybrid input, with the coefficients on the right hand side of equations assumed to have deterministically known values. In this example, transition from \(q_1\) to \(q_2\) is an autonomous switching, the transition from \(q_2\) to \(q_3\) is a controlled switching accompanied by a dimension change, and transition from \(q_3\) to \(q_4\) is an autonomous switching accompanied by a dimension change. The set of switching manifolds \({{\mathcal {M}}}\) for the autonomous switchings are given by
and the set of jump transition maps \(\Xi \) is provided as
Let the performance measure be given as
where the running costs \(l_{q_i}\)’s are the power consumption rates, determined from the motor efficiency map in [56] as
5.4.1 The HMP results and solution
Optimal state and adjoint processes, optimal input and the corresponding Hamiltonians for the example of vehicle with transmission
Based on the HMP (details of the derivation are presented in [56]), optimal inputs are determined as
where \(\lambda \left( t\right) \equiv \lambda ^o_{q_i}\left( t\right) \) are governed by the set of differential equations
subject to the terminal and boundary conditions:
where the optimal switching instances \(t_{s_1}\), \(t_{s_2}\), \(t_{s_3}\) together with the unknown scalar \(p_1\) and \(p_3\) are determined from switching manifold conditions and Hamiltonian continuity conditions. The associated results are illustrated in Fig. 6. Interested readers are referred to [56] for further details about hybrid systems modeling and the determination of the HMP results for this system.
6 Concluding remarks
The hybrid minimum principle (HMP) presented and proved in this paper exhibits several distinctive characteristics of hybrid systems which are not simultaneously present in other versions of the HMP available in the literature. One of the key aspects of the established HMP is the explicit presentation of the boundary conditions on the Hamiltonians and adjoint processes (in contrast to their implicit expressions in [27,28,29,30, 33] in the form of transversality conditions), the relaxation of the regularity requirements (relative to, e.g., [32, 34]) and the presence of time-varying switching manifolds and jump maps corresponding to both autonomous and controlled, together with time varying switching costs and the possibility of state space dimension change (where only subsets of these features have been considered for the presentation of other versions of the HMP).
It is worth remarking that the statement of the HMP (like other versions of the HMP established in the literature) is along a fixed sequence of discrete states and while the associated switching times are not a priori fixed (and are part of the solution to the HMP), the currently available versions of the HMP are silent about the optimality of a sequence of discrete states. In other words, the adjoint process in the HMP is only in adjoint relationship with variations of the continuous state process while, to the best of our knowledge, the determination of an adjoin-type variable for discrete-valued processes (including especially the discrete component of the state of hybrid systems) is still an open problem. In contrast, one can obtain the optimal switching sequence using hybrid dynamic programming (HDP) (see, e.g., [18, 35]) at the expense of being required to solve multiple partial differential equations and possibly encountering the curse of dimensionality in the associated numerical algorithms. An interesting future line of research would be the development of numerical algorithms based upon the intrinsic relationship between the HMP and HDP [35] where the optimality results of the HMP are combined with HDP in order to also determine the optimal sequence of discrete states.
References
Pontryagin LS, Boltyanskii VG, Gamkrelidze RV, Mishchenko EF (1962) The mathematical theory of optimal processes, vol 4. Wiley Interscience, New York
Puri A, Varaiya P (1994) Verification of hybrid systems using abstractions. In: International Hybrid Systems Workshop. Springer, pp. 359–369
Alur R, Henzinger TA, Lafferriere G, Pappas GJ (2000) Discrete abstractions of hybrid systems. Proc IEEE 88(7):971–984
Alur R, Dang T, Ivančić F (2003) Progress on reachability analysis of hybrid systems using predicate abstraction. In: Proceedings of the 6th international workshop on hybrid systems: computation and control. HSCC, Prague, Czech Republic, p. 4–19
Clarke E, Fehnker A, Han Z, Krogh B, Ouaknine J, Stursberg O et al (2003) Abstraction and counterexample-guided refinement in model checking of hybrid systems. Int J Found Comput Sci 14(04):583–604
Tiwari A, Khanna G (2002) Series of abstractions for hybrid automata. In: Proceedings of the 5th international workshop on hybrid systems: computation and control. HSCC, Stanford, pp. 465–478
Broucke M (1999) A geometric approach to bisimulation and verification of hybrid systems. In: Hybrid systems: computation and control. Springer, pp. 61–75
Helwa MK, Caines PE (2017) In-block controllability of affine systems on polytopes. IEEE Trans Autom Control 62(6):2950–2957
Corona D, Giua A, Seatzu C (2004) Optimal control of hybrid automata: design of a semiactive suspension. Control Eng Pract 12(10):1305–1318 (Analysis and Design of Hybrid Systems)
Goebel R, Sanfelice RG, Teel AR (2012) Hybrid dynamical systems: modeling, stability, and robustness. Princeton University Press, Princeton
Liberzon D (2003) Switching in systems and control, vol 190. Birkhauser, Boston
Liberzon D, Hespanha JP, Morse AS (1999) Stability of switched systems: a lie-algebraic condition. Syst Control Lett 37(3):117–122
Hespanha JP (2004) Uniform stability of switched linear systems: extensions of LaSalle’s invariance principle. IEEE Trans Autom Control 49(4):470–482
Branicky MS (1998) Multiple Lyapunov functions and other analysis tools for switched and hybrid systems. IEEE Trans Autom Control 43(4):475–482
Decarlo RA, Branicky MS, Pettersson S, Lennartson B (2000) Perspectives and results on the stability and stabilizability of hybrid systems. Proc IEEE 88(7):1069–1082
Johansson M, Rantzer A (1998) Computation of piecewise quadratic Lyapunov functions for hybrid systems. IEEE Trans Autom Control 43(4):555–559
Van der Schaft AJ, Schumacher JM (2000) An introduction to hybrid dynamical systems. Lecture notes in control and information sciences, Vol. 251. Springer, London
Bensoussan A, Menaldi JL (1997) Hybrid control and dynamic programming. Dyn Cont Discrete Impuls Syst Ser B Appl Algorithm 3(4):395–442
Dharmatti S, Ramaswamy M (2005) Hybrid control systems and viscosity solutions. SIAM J Control Optim 44(4):1259–1288
Barles G, Dharmatti S, Ramaswamy M (2010) Unbounded viscosity solutions of hybrid control systems. ESAIM Control Optim Calc Var 16(1):176–193
Branicky MS, Borkar VS, Mitter SK (1998) A unified framework for hybrid control: model and optimal control theory. IEEE Trans Autom Control 43(1):31–45
Shaikh MS, Caines PE (2009) A verification theorem for hybrid optimal control problem. In: Proceedings of the IEEE 13th international multitopic conference, INMIC
Caines PE, Egerstedt M, Malhamé R, Schöllig A (2007) A hybrid Bellman equation for bimodal systems. In: Proceedings of the 10th international conference on hybrid systems: computation and control, HSCC, vol. 4416, p. 656–659. LNCS
Schöllig A, Caines PE, Egerstedt M, Malhamé R (2007) A hybrid Bellman equation for systems with regional dynamics. In: Proceedings of the 46th IEEE conference on decision and control, CDC. pp. 3393–3398
Da Silva JE, De Sousa JB, Pereira FL (2012) Dynamic programming based feedback control for systems with switching costs. In: Proceedings of the IEEE international conference on control applications, CCA, pp. 634–639
Hedlund S, Rantzer A (2002) Convex dynamic programming for hybrid systems. IEEE Trans Autom Control 47(9):1536–1540
Clarke FH, Vinter RB (1989) Applications of optimal multiprocesses. SIAM J Control Optim 27(5):1048–1071
Clarke FH, Vinter RB (1989) Optimal multiprocesses. SIAM J Control Optim 27(5):1072–1091
Sussmann HJ (1999) A nonsmooth hybrid maximum principle. In: Aeyels D, Lamnabhi-Lagarrigue F, van der Schaft A (eds) Stability and stabilization of nonlinear systems. London, Springer, pp 325–354
Sussmann HJ (1999) Maximum principle for hybrid optimal control problems. In: Proceedings of the 38th IEEE conference on decision and control, CDC. pp. 425–430
Caines PE, Clarke FH, Liu X, Vinter RB (2006) A maximum principle for hybrid optimal control problems with pathwise state constraints. In: Proceedings of the 45th IEEE conference on decision and control, pp. 4821–4825
Shaikh MS, Caines PE (2007) On the hybrid optimal control problem: theory and algorithms. IEEE Trans Autom Control 52(9):1587–1603
Garavello M, Piccoli B (2005) Hybrid necessary principle. SIAM J Control Optim 43(5):1867–1887
Taringoo F, Caines PE (2013) On the optimal control of impulsive hybrid systems on Riemannian manifolds. SIAM J Control Optim 51(4):3127–3153
Pakniyat A, Caines PE (2017) On the relation between the minimum principle and dynamic programming for classical and hybrid control systems. IEEE Trans Autom Control 62(9):4347–4362
Jafarpour S, Lewis AD (2016) Locally convex topologies and control theory. Math Control Signals Syst 28(4):29
Shaikh MS, Caines PE (2005) Optimality zone algorithms for hybrid systems computation and control: from exponential to linear complexity. In: Proceedings of the 44th IEEE conference on decision and control, and the european control conference, CDC-ECC ’05. vol, 2005, pp. 1403–1408
Taringoo F, Caines PE (2011) Gradient geodesic and Newton geodesic HMP algorithms for the optimization of hybrid systems. Annu Rev Control 35(2):187–198
Axelsson H, Wardi Y, Egerstedt M, Verriest E (2008) Gradient descent approach to optimal mode scheduling in hybrid dynamical systems. J Optim Theory Appl 136(2):167–186
Boccadoro M, Wardi Y, Egerstedt M, Verriest E (2005) Optimal control of switching surfaces in hybrid dynamical systems. Discrete Event Dyn Syst 15(4):433–448
Gonzalez H, Vasudevan R, Kamgarpour M, Sastry SS, Bajcsy R, Tomlin CJ (2010) A descent algorithm for the optimal control of constrained nonlinear switched dynamical systems. In: Proceedings of the 13th ACM international conference on Hybrid systems: computation and control, ACM, pp. 51–60
Zhao P, Mohan S, Vasudevan R (2019) Optimal control of polynomial hybrid systems via convex relaxations. IEEE Trans Autom Control 65(5):2062–2077
Zhu F, Antsaklis PJ (2015) Optimal control of hybrid switched systems: a brief survey. Discret Event Dyn Syst 25(3):345–364
Passenberg B, Leibold M, Stursberg O, Buss M (2011) The minimum principle for time-varying hybrid systems with state switching and jumps. In: Proceedings of the 50th IEEE conference on decision and control and european control conference, CDC-ECC. pp. 6723–6729
Cowlagi RV (2017) Hierarchical trajectory optimization for a class of hybrid dynamical systems. Automatica 77:112–119
Mamakoukas G, MacIver MA, Murphey TD (2018) Feedback synthesis for underactuated systems using sequential second-order needle variations. Int J Robot Res 37(13–14):1826–1853
Riedinger P, Kratz F (2003) An optimal control approach for hybrid systems. Eur J Control 9(5):449–458
Xu X, Antsaklis PJ (2004) Optimal control of switched systems based on parameterization of the switching instants. IEEE Trans Autom Control 49(1):2–16
Azhmyakov V, Boltyanski VG, Poznyak A (2008) Optimal control of impulsive hybrid systems. Nonlinear Anal Hybrid Syst 2(4):1089–1097
Dmitruk AV, Kaganovich AM (2008) The hybrid maximum principle is a consequence of Pontryagin maximum principle. Syst Control Lett 57(11):964–970
Dmitruk AV, Kaganovich AM (2011) Maximum principle for optimal control problems with intermediate constraints. Comput Math Model 22(2):180–215
Dmitruk AV, Kaganovich AM (2011) Quadratic order conditions for an extended weak minimum in optimal control problems with intermediate and mixed constraints. Discr Contin Dyn Syst 29:523–545
Pakniyat A, Caines PE (2014) On the relation between the minimum principle and dynamic programming for hybrid systems. In: Proceedings of the 53rd IEEE conference on decision and control, CDC. pp. 19–24
Pakniyat A, Caines PE (2013) The hybrid minimum principle in the presence of switching costs. In: Proceedings of the 52nd IEEE conference on decision and control, CDC. pp. 3831–3836
Westervelt ER, Chevallereau C, Choi JH, Morris B, Grizzle JW (2007) Feedback control of dynamic bipedal robot locomotion. CRC Press, Boca Raton
Pakniyat A, Caines PE (2017) Hybrid optimal control of an electric vehicle with a dual-planetary transmission. Nonlinear Anal Hybrid Syst 25:263–282
Pakniyat A, Caines PE (2015) Time optimal hybrid minimum principle and the gear changing problem for electric vehicles. In: Proceedings of the 5th IFAC conference on analysis and design of hybrid systems. Atlanta, pp. 187–192
Pakniyat A, Caines PE (2014) On the minimum principle and dynamic programming for hybrid systems. In: Proceedings of the 19th international federation of automatic control world congress, IFAC, p. 9629–9634
Pakniyat A, Caines PE (2015) On the minimum principle and dynamic programming for hybrid systems with low dimensional switching manifolds. In: Proceedings of the 54th IEEE conference on decision and control, Japan. pp. 2567–2573
Pakniyat A, Caines PE (2015) On the relation between the hybrid minimum principle and hybrid dynamic programming: a linear quadratic example. In: Proceedings of the 5th IFAC conference on analysis and design of hybrid systems. pp. 169–174
Taringoo F, Caines PE (2010) Gradient-geodesic HMP algorithms for the optimization of hybrid systems based on the geometry of switching manifolds. In: Proceedings of the 49th IEEE conference on decision and control, CDC. pp. 1534–1539
Pakniyat A, Caines PE (2016) On the stochastic minimum principle for hybrid systems. In: Proceedings of the 55th IEEE conference on decision and control. pp. 1139–1144
Caines PE (2017) Lecture notes on nonlinear and hybrid control systems: dynamics, stabilization and optimal control. Department of Electrical and Computer Engineering (ECE), McGill University
Agrachev AA, Sachkov Y (2013) Control theory from the geometric viewpoint, vol 87. Springer Science & Business Media, Berlin
Rudin W (1987) Real and complex analysis. McGraw-Hill, New York
Sontag ED (1998) Mathematical control theory: deterministic finite dimensional systems. texts in applied mathematics. Springer, New York
Pakniyat A, Caines PE (2020) On the hybrid minimum principle: the Hamiltonian and adjoint boundary conditions. IEEE Trans Autom Control 66(3):1246–1253
Acknowledgements
This work is supported in part by NSERC (Canada) Grant RGPIN-2019-05336, the U.S. ARL and ARO Grant W911NF1910110, and the U.S. AFOSR Grant FA9550-19-1-0138.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript. The authors have no financial or proprietary interests in any material discussed in this article.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix A Proof of Lemma 1
Appendix A Proof of Lemma 1
Proof
Let us define
where \(B_{r}:=\left\{ x \in {\mathbb {R}}^{n_{q}}: \left\| x\right\| ^2 <r^2\right\} \).
we first consider the stage where no remaining switching is available and hence \(t\in \left( t_L,t_{L+1}\right) = \left( t_L,t_{f}\right) \). In this the case that
which gives
where \(L_{f}\) is defined in assumptions A0. By the Gronwall-Bellman inequality this results in
where \(K_{2}=\max \left\{ K_{1},L_{f}K_{1}\left( t_{f}-t_{L}\right) e^{L_{f}\left( t_{f}-t_{L}\right) }\right\} \). Hence, by the semi-group properties of ODE solutions and by use of (A4), for \(s \ge t\) and \(x_s \in N_{r_{x}}\left( x_t\right) \) we have
and therefore, by the Gronwall inequality we have
for some \(K<\infty \) which depends only on \(t_f - t_L\), \(K_1\) and \({\tilde{K}}_f\) and not on the control input.
Now consider \(t,s\in \left( t_j,t_{j+1}\right) \) where \(t_{j+1}\) indicates a time of an autonomous switching for the trajectory \(x\left( \tau ;t,x_{t}\right) \), and consider for definiteness the case where \(x\left( \tau ;s,x_{s}\right) \) arrives on the switching manifold described locally by \(m\left( x\right) = 0\) at a later time \(t_{j+1}+\delta t\) (the case with an earlier arrival time can be handled similarly by considering \(\delta t<0\)). It directly follows by replacing \(f_{q_L}\) and \(t_{f}\) by \(f_{q_j}\) and \(t_{j+1}-\) in the above arguments, that
Now since
and
it is sufficient to show that the upper bound for \(\left| \delta t\right| \) is proportional to \(\big (\left\| x_{t}-x_{s}\right\| ^{2}+\left| s-t\right| ^{2}\big )^{\frac{1}{2}}\). This can be shown to hold by considering the fact that
For \(\left\| \delta x\left( t_{j+1}-\right) \right\| < \epsilon _{j+1}\) sufficiently small,
which is equivalent to
Due to the transversal arrival of the trajectories with respect to the smooth switching manifold, \(\left| \nabla m^{\top } f_{q_j}\right| \) is lower bounded by a strictly positive number \(k_{m,f}\) (see (2)) and hence,
which gives
Hence, for \(t\in \left( t_j,t_{j+1}\right) \) and \(x_t\in B_r\) there exist a neighborhood \(N_{r_x}\left( x_t\right) \) such that for \(s\in \left( t_j,t_{j+1}\right) \) and \(x_s \in \mathcal{N}_{r_x}\left( x_t\right) \) we have \(\left\| \delta x\left( t_{j+1}-\right) \right\| \le K^{\prime }\left( \left\| x_{t}-x_{s}\right\| ^{2}+\left| s-t\right| ^{2}\right) ^{\frac{1}{2}} < \epsilon _{j+1}\) in order to ensure that \(\delta t \le K_{j+1} \epsilon _{j+1}\) and consequently
for K independent of the control. Since \(\xi \) is smooth and time invariant, it is therefore Lipschitz in x uniformly in time. \(\square \)
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Pakniyat, A., Caines, P.E. The minimum principle of hybrid optimal control theory. Math. Control Signals Syst. 36, 21–70 (2024). https://doi.org/10.1007/s00498-023-00374-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00498-023-00374-1