Keywords: Barrières, Systèmes non linéaires, contraintes sur l'état et les entrées, contraintes mixtes, ensemble admissible, points d Barrier, nonlinear systems, state and input constraints, mixed constraints, admissible set, stopping points, potentially safe sets Chapter 2 Barrier, nonlinear systems, state and input constraints, mixed constraints, admissible set, stopping points, potentially safe sets

de la thèse

Cette thèse est consacrée à l'étude de la théorie des barrières pour les systèmes non linéaires sous contraintes d'entrées et d'état. La principale contribution concerne la généralisation au cas de contraintes mixtes, c'est-à-dire dépendant des entrées et de l'état de façon couplée. Ce type de contraintes apparaît souvent dans les applications et dans les systèmes différentiellment plats sous contraintes. On prouve un théorème du type principe du minimum qui permet de construire la barrière et l'ensemble admissible associé. De plus, dans le cas d'intersection de plusieurs trajectoires ainsi construites, on démontre que les points intersections transversaux sont des points d'arrêt de la barrière.

Ces résultats sont utilisés pour calculer l'ensemble admissible d'un pendule avec un câble non-rigide monté sur un chariot, la contrainte correspondant au fait que le câble reste tendu. Ce probléme correspond en fait à la détermination de l'ensemble potentiallement sûr dans le cadre des systèmes hybrides.

Chapter 1 Introduction

Given a constrained nonlinear system the aim of our work is to find its admissible set, which is the set of all initial conditions for which there exists a control such that the constraints are satisfied for all time. It turns out that this set is closed and that its boundary can be divided into two complementary parts, one of which is called the barrier. This is so-called because of a property it possesses called semi-permeability: for an initial state outside the admissible set, no trajectory satisfying the constraints can cross the barrier in the direction of the interior of the admissible set. These terms were originally introduced by Isaacs in the context of pursuit-evasion differential games, see [START_REF] Isaacs | Differential Games[END_REF], and have recently been recognised in [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] to play a key role in the study of constrained nonlinear systems. This semi-permeability property is significant because it allows the barrier's construction via a minimum-like principle.

To explain the ideas let us find the admissible set and the barrier for the following system from [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF]:

ẋ1 = x 2 ẋ2 = -2x 1 -2x 2 + u (1.1)
with constraints

x 2 ≤ 1 |u| ≤ 1. (1.2)
Consider an initial condition x 0 on the barrier, the semi-permeable part of the boundary of the admissible set which is, here, the set of initial conditions x for integral curves of (1.1), denoted by x (u,x) , that satisfy the constraints (1.2) for all time. Then it can be shown that there exists a control ū such that the resulting integral curve x (ū,x 0 ) remains on the barrier until it intersects the set G 0 = {x : x 2 = 1}. In other words, the barrier is made up of integral curves of the differential equation (1.1) with specific inputs. Moreover, it can be shown that the barrier arrives tangentially on G 0 , which allows us to identify these points of intersection. These results are encapsulated in Propositions 2.1.2 and 2.1.3. The next result is that trajectories running along the barrier satisfy a minimum-like principle which we can use to determine the control function ū associated with a barrier trajectory. This result is encapsulated in Theorem 2.1.1.

If we carry out this analysis on the above problem, we identify the final point z = (- 3 2 , 1) ∈ G 0 , along with the control function ū. It turns out that ū(t) = -1 over some interval before arriving at z and that there is a switch from ū(t) = +1 once it crosses the x 1 axis. Now integrating backwards from z using ū, we get the trajectory as in Figure 1.1 which is the barrier for the problem. As will be done throughout the thesis, the admissible Chapter 1. Introduction set is labelled A and the barrier is labelled [∂A] -. Due to the semi-permeability of the barrier, any trajectory initiating in the complement of A is guaranteed to violate the constraints in the future. This emphasises the semi-permeability property.

In this thesis we build on what is known about the admissible set. Our first contribution involves generalising the results from [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] to the case where the constraints imposed on the system depend on both the control and the state. As is done in optimal control we refer to these constraints as mixed, see for example [START_REF] Clarke | Optimal control problems with mixed constraints[END_REF][START_REF] Hestenes | Calculus of Variations and Optimal Control Theory[END_REF].

An example of where these constraints occur is given by the classic pendulum on a cart where the rigid rod has been replaced with a cable that may go slack, see Figure 1.2. The goal is to manoeuvre the cart in such a way that the cable always remains taut. One way to ensure this is to impose the condition that the tension in the cable is always nonnegative, which can be shown to be equivalent to:

u sin(θ) + M g cos(θ) -M l θ2 ≤ 0.
where u is the force applied to the cart and is assumed to be bounded, θ denotes the angle the rope makes with the vertical, M is the mass of the cart, l the length of the cable and g the acceleration due to gravity. In other words, we need to impose a mixed constraint.

Finding the admissible set for this system may be useful to avoid unsafe control of overhead cranes, see for example [START_REF] Kiss | Modelling, flatness and simulation of a class of cranes[END_REF]. A comparable example may be found in [START_REF] Nicotra | Taut cable control of a tethered uav[END_REF], where the authors study tethered unmanned aerial vehicles. Constraints of this type also arise in aerospace problems, see for example [START_REF] Pesch | A practical guide to the solution of real-life optimal control problems[END_REF]. Another motivation for the generalisation to Figure 1.2: Pendulum on a cart with non-rigid cable mixed constraints is provided by flat systems, [START_REF] Sira-Ramirez | Differentially flat systems[END_REF][START_REF] Lévine | Analysis and Control of Nonlinear Systems: A Flatness-Based Approach[END_REF], under constraints: if we express the state and control variables in terms of a flat output y, namely x = ϕ(y, ẏ, . . . , y (α) ) and u = ψ(y, ẏ, . . . , y (α+1) ), where y (k) denotes the kth order time derivative of y for an arbitrary integer k, the constraint γ(u) ≤ 0 is transformed into γ(ψ(y, ẏ, . . . , y (α+1) )) γ(y, ẏ, . . . , y (α) , v) ≤ 0 where v = y (α+1) is the new control variable. It can be seen that γ is mixed.

The presence of mixed constraints makes the study of the admissible set considerably more difficult. This is due to the fact that the evolution of the constraints as a function of time may be discontinuous, that the boundary of the constraint set is not defined a priori as in the purely state constraint setting, and that we require the existence of (regular) perturbed trajectories in some sense that remain on the boundaries of the active constraints. Moreover, it is convenient to use some tools from nonsmooth analysis.

Returning to the example above, we keep the dynamics (1.1) and replace the pure state constraint by the mixed one (1.3):

x 2 -u ≤ 0 |u| ≤ 1 (1.3)
and introduce the notation U = {u : |u| ≤ 1}. The difficulty now is that if we consider an initial condition x 0 on the barrier, then we are not sure of where the trajectory "ends up" because the constraint g(x, u) = x 2 -u can be zero for any (x 1 , x 2 ) ∈ R × [-1 , 1]. We are able to prove, see Proposition 3.3.2, that in the mixed constraint case the barrier may intersect the set G 0 = {x : min u∈U g(x, u) = 0} = {x : min |u|≤1 x 2 -u = 0}. Though in this particular example this set is differentiable, the intersection might occur in a generalised tangential manner, see Proposition 3.3.4. (See Section 3.5.3 for an example of where the barrier does not ultimately reach G 0 .) Moreover, the presence of mixed constraints requires a modification of the minimum-like principle, see Theorem 3.4.1, that allows one to identify the control ū, and along barrier trajectories the constraints may be saturated.

If we apply the generalised results on the example with mixed constraints, we identify the problem's barrier as in Figure 1.3. Note that in this case the barrier arrives at Chapter 1. Introduction z = (- 1 2 , 1), and that the control ū(t) = x 2 (t) over an interval before z and switches from ū(t) = 1 as the trajectory crosses the x 1 axis. In some examples it has been observed that barrier trajectories, found via the minimumlike principle, intersect and that parts of them are in the interior of the admissible set and need to be ignored. A second contribution we make to the study of admissible sets is an explanation of this phenomenon that we call stopping points. The result is a theorem that states that every transversal intersection point of barrier trajectories is a stopping point.

The outline of the thesis is as follows: in Chapter 2 we first present a summary of the paper [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] on which the contributions of this thesis build. The rest of Chapter 2 is dedicated to work that is related to the admissible set. Chapter 3 covers our work on mixed constraints and makes frequent reference to Appendix A, where we cover relevant concepts of compactness of the space of solutions, and Appendix B where we present a needed generalisation of a form of the Pontryagin maximum principle. Chapter 4 covers our work on stopping points. Chapter 5 is dedicated to describing the admissible set for the pendulum on a cart with a non-rigid cable, as introduced above, and requires all the theoretical contributions of the previous chapters. In the final chapter we briefly explore an alternative approach to generalising the theory on barriers from [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] to the mixed constraint case: letting the control be an additional state variable. This study is left unfinished due to unexpected difficulties and is stated here as an open problem. Finally, we provide some perspectives where we point out possible future research.

Introduction

In Section 2.1 we cover, without proofs, the main results on barriers in input and state constrained nonlinear systems as in [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF], where the constraints are not mixed. In Chapter 3 we will generalise the definitions and notations of Section 2.1 as well as the most important results (namely Proposition 2.1.2, Proposition 2.1.3 and Theorem 2.1.1) to the mixed constraint case.

Section 2.2 is dedicated to viability kernels which are closely related to admissible sets. Consequently, we cover the ideas with some depth and compare the method used to construct barriers (via a minimum-like principle) with the methods generally used to construct viability kernels (via iteratively computing approximations of reachable sets).

The remainder of the chapter covers other methods that ensure that systems perform in a way such that constraints are never violated. We briefly cover target avoidance problems and backwards reachable sets that appear in the setting of differential games and which have been applied to the study of "safety sets" in hybrid systems. We also cover barrier certificates and barrier Lyapunov functions.

Chapter 2. A Short Survey of Constrained Systems

Barriers in Constrained Nonlinear System, the Unmixed Case

The material in this section is a summary of the paper [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF]. Consider the constrained nonlinear system: ẋ = f (x, u), (2.1)

x(t 0 ) = x 0 , (2.2) u ∈ U, (2.3
)

g i x(t) ≤ 0 ∀t ∈ [t 0 , ∞), ∀i ∈ {1, . . . , p} (2.4)
where x(t) ∈ R n . U is the set of Lebesgue measurable functions from [t 0 , ∞) to U , where U is a compact convex subset of R m , and not a singleton.

The constraint set is defined by: G {x ∈ R n : g i (x) ≤ 0, i = 1, ..., p}.

Introduce the notation g(x) 0 to indicate that x satisfies g i (x) = 0 for at least one i ∈ {1, ..., p} and g i (x) ≤ 0 for all i ∈ {1, ...p}. g(x) ≺ 0 (resp. g(x) 0) indicates that g i (x) < 0 (resp. g i (x) ≤ 0) for all i ∈ {1, . . . , p}. I(x) denotes the set of all indices i ∈ {1, . . . , p} such that g i (x) = 0.

Also define the sets

G 0 {x ∈ R n : g(x) 0}, G -{x ∈ R n : g(x) ≺ 0}. (2.5)
It can be seen that G = G 0 ∪ G -.

The assumptions made by [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] for the rigorous analysis of the barrier are:

(A1) f is an at least C 2 vector field of R n for every u in an open subset of R m containing U , whose dependence with respect to u is also at least C 2 .

(A2) There exists a constant 0 < C < +∞ such that the following inequality holds true:

sup u∈U |x T f (x, u)| ≤ C(1 + x 2
), for all x (A3) The set f (x, U ), called the vectogram in [START_REF] Isaacs | Differential Games[END_REF], is convex for all x ∈ R n .

(A4)

For each i = 1, . . . , p, g i is an at least C 2 function from R n to R and the set of points given by g i (x) = 0 defines an n -1 dimensional manifold.

In the sequel we will denote by x (u,x 0 ) the solution of the differential equation (2.1) with input u ∈ U and initial condition x 0 , and by x (u,x 0 ) (t) its solution at time t. Sometimes we will use the notation x u and x u (t) without specifying the initial condition.

2.1. Barriers in Constrained Nonlinear System, the Unmixed Case 13

The Admissible Set

The admissible set, as in [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF], is defined as follows:

Definition 1 (Admissible Set). We will say that a state-space point x is admissible if there exists, at least, one input function v ∈ U, such that (2.1)-(2.4) are satisfied for x 0 = x and u = v. The set of all such x is called the admissible set:

A {x ∈ G : ∃u ∈ U, g x (u,x) (t) 0, ∀t ∈ [t 0 , ∞)}. (2.6) Proposition 2.1.1
Assume that (A1)-(A4) are valid. The set A is closed.

The proof of Proposition 2.1.1 uses the result that the space of solutions is compact, see [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF]Appendix A]. In Chapter 3 we prove that the admissible set as defined in the mixed constraint setting is also closed, and the proof also results from the compactness of the space of solutions as generalised in Appendix A.

Denote by ∂A the admissible set's boundary and define the two sets:

[∂A] 0 = ∂A ∩ G 0 , [∂A] -= ∂A ∩ G -. (2.7) It can be seen that ∂A = [∂A] 0 ∪ [∂A] -.

The Barrier

Now consider the subset [∂A] -of the boundary of the admissible set.

Definition 2. The set [∂A]

-is called the barrier of the set A.

Proposition 2.1.2

Assume that (A1) to (A4) hold. The barrier [∂A] -is made of points x ∈ G -for which there exists ū ∈ U and an arc of integral curve x (ū,x) entirely contained in [∂A] - until it intersects G 0 at a point x (ū,x) ( t) for some t ∈ [t 0 , +∞).

Next, the semi-permeability property is stated. It follows as a corollary of Proposition 2.1.2.

Corollary 2.1.1

From any point on the boundary [∂A] -, there cannot exist a trajectory penetrating the interior of A, denoted by int(A), before leaving G -.

In the next proposition is stated the ultimate tangentiality condition, which says that the barrier must intersect the set G 0 tangentialy. It is akin to the transversality condition found in optimal control. By L f h(x, u) Dh(x)f (x, u) is meant the Lie derivative of a smooth function h : R n → R along the vector field f (•, u) at the point x.

Proposition 2.1.3

Consider x ∈ [∂A] -and ū ∈ U as in Proposition 2.1.2, i.e. such that the integral curve x (ū,x) (t) ∈ [∂A] -for all t in some time interval until it reaches G 0 . Then, there exists a point z = x (ū,x) ( t) ∈ cl([∂A] -) ∩ G 0 for some finite time t ≥ t 0 such that

min u∈U max i∈I(z) L f g i (z, u) = 0.
(2.8)

Chapter 2. A Short Survey of Constrained Systems

Next is the theorem that allows one to construct the barrier via the minimum-like principle. Let H(x, λ, u) = λ T f (x, u) denote the Hamiltonian. Theorem 2.1.1

Under the assumptions of Proposition 2.1.2, every integral curve x ū on [∂A] -∩ cl(int(A)) and the corresponding control function ū, as in Proposition 2.1.2, satisfies the following necessary condition.

There exists a (non zero) absolutely continuous maximal solution λ ū to the adjoint equation

λū (t) = - ∂f ∂x (x ū(t), ū(t)) T λ ū(t), λ ū( t) = (Dg i * (z)) T (2.9)
such that the Hamiltonian is minimised:

min u∈U (λ ū(t)) T f (x ū(t), u) = (λ ū(t)) T f (x ū(t), ū(t)) = 0 (2.10)
at every Lebesgue point t of ū (i.e. for almost all t ≤ t). In (2.9), t denotes the time at which z is reached, i.e. x ū( t) = z, with z ∈ G 0 satisfying the ultimate tangentiality condition:

g i (z) = 0, i ∈ I(z), min u∈U max i∈I(z) L f g i (z, u) L f g i * (z, ū( t)) = 0.
(2.11)

Using these results one can construct the barrier for a particular problem by first identifying the ultimate tangentiality points via (2.11), then determining the control function associated with trajectories running along the barrier, via the Hamiltonian minimisation condition (2.10), and then integrating backwards using the problem's dynamics as well as the dynamics of the adjoint. An example will be covered in the next section.

Viability Theory

Viability theory, [START_REF] Aubin | Viability Theory. Systems & Control Foundations[END_REF], is a body of work that is closely related to the study of admissible sets and barriers. It considers the nonlinear system with a constrained control, (2.1) -(2.3), along with a state constraint set K which has nonempty interior. Note that this set plays an analogous role to the set G = {x ∈ R n : g i (x) ≤ 0, i = 1, . . . , p} from the theory on barriers. One of the goals of Viability theory is to find the infinite horizon viability kernel of K, given by:

V iab [0,∞) (K) {x ∈ K : ∃u ∈ U, x (u,x) (t) ∈ K ∀t ∈ [t 0 , ∞)}
or the finite horizon viability kernel, given by:

V iab [0,τ ] (K) {x ∈ K : ∃u ∈ U, x (u,x) (t) ∈ K ∀t ∈ [t 0 , τ ]},
where, as before, x (u,x) (t) is the solution of (2.1) at time t. It can be seen that these sets play an analogous role to the admissible set from the theory on barriers and, in particular, if K = G these two sets are the same.

Estimating the Viability Kernel via Reachable Sets

A common approach in the literature is to estimate the viability kernel (finite or infinite) by iteratively computing approximations of reachable sets. This method is nicely illustrated by the following algorithm from [START_REF] Kaynama | Computing the viability kernel using maximal reachable sets[END_REF] used to approximate the finite horizon viability kernel. To explain the algorithm, let us introduce the following set: Definition 3 (backwards reachable set).

R b t (S) {x 0 ∈ R n : ∃u ∈ U [0,t] s.t. x (u,x 0 ) (t) ∈ S}.
(2.12)

where x 0 = x(0) and U [0,t] is the set of all measurable controls u : [0, t] → U , and U is as before. R b t (S) is the set of states from which S can be reached at exactly time t. Next, introduce a partition P = {t 0 , . . . , t r } of the interval [0, τ ] with t 0 = 0 and t r = τ and let P denote the largest interval in the partition and

|P | = r. If it is assumed that the function f is bounded, i.e. f (x, u) ≤ M , then for any t ∈ [t i , t i+1 ]
x(t) -x(t i ) ≤ M P . Consider the set:

K ↓ (P ) {x ∈ K|d(x, K C ) ≥ M P }
where d(x, S) is the distance from the point x to the set S. It can be seen that K ↓ (P ) is an inner-approximation of K.

The iterative algorithm is then as follows:

K r K ↓ (P ) K n-1 K ↓ (P ) ∩ R tn-t n-1 (K n ), f or n = 1, ..., r (2.13)
and it can be shown, see [START_REF] Kaynama | Computing the viability kernel using maximal reachable sets[END_REF], that for any partition of the interval [0, τ ] the set K 0 is an under-approximation of V iab [0,τ ] (K). Similar ideas also appear in [START_REF] Blanchini | Set-theoretic Methods in Control[END_REF] in the context of "controlled invariance". Another earlier method that uses reachable sets to compute the infinite horizon viability kernel is described in [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF]. Here, the idea is to consider a discrete inclusion:

x n+1 ∈ G(x n )
where x i is the state of the discrete system at index i and G is a set valued mapping.

It can be seen that G(x n ) is the set of all states reachable at index n + 1 from x n . If we now consider the state constraint set K it can be shown, under certain regularity assumptions on G and K, that the following iterative algorithm:

K 0 K K n+1 {x ∈ K n : G(x) ∩ K n = ∅}, n = 1, 2, . . . (2.14)
leads to an estimate of the "discrete viability kernel", labelled V iab(K) (this is the discrete analogue of V iab [0,∞) (K), i.e. the set of all states from where there exists a solution to the discrete inclusion such that every element of this solution is in K). It can be shown that this estimate becomes arbitrarily close as n goes to infinity, i.e. lim n→∞ K n = V iab(K).

If the discrete inclusion is an appropriate approximation of the continuous dynamics, as explained in [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF], one can find a good under-approximation of the infinite horizon viability kernel for the continuous system. Both algorithms require the computation of a reachable set, or its approximation, with each iteration. It is interesting to note that whereas the algorithm (2.13) starts with the constraint set K and recursively looks at sets reachable backwards in time, the algorithm (2.14) starts with K and recursively looks at sets that are reachable in the future.

There is a large literature dedicated to the computation of reachable sets, and the interested reader may consult for example [START_REF] Chutinan | Computing polyhedral approximations to flow pipes for dynamic systems[END_REF], [START_REF] Dang | Verification and Synthesis of Hybrid Systems[END_REF], [START_REF] Kurzhanski | Ellipsoidal techniques for reachability analysis[END_REF], [START_REF] Kurzhanski | Dynamic optimization for reachability problems[END_REF] and [START_REF] Girard | Efficient computation of reachable sets of linear time-invariant systems with inputs[END_REF].

Chapter 2. A Short Survey of Constrained Systems

A Comparative Example

In order to demonstrate the difference between the methods generally taken by viability theory (utilising reachable set computations) and the theory on barriers, let us consider the double integrator example from [START_REF] Kaynama | Computing the viability kernel using maximal reachable sets[END_REF].

The dynamics are given by ẋ1 = x 2 ẋ2 = u and the constraints imposed are |u| ≤ 1 4 and (x 2 1 + x 2 2 ) -1 4 ≤ 0. Using the iterative scheme involving backwards reachable sets mentioned in the previous section, the authors in [START_REF] Kaynama | Computing the viability kernel using maximal reachable sets[END_REF] use ellipsoidal techniques from [START_REF] Kurzhanski | Ellipsoidal techniques for reachability analysis[END_REF] to find successively better approximations of the finite horizon viability kernel V iab [0,1] . See Figure 2.1.

Using the theory on barriers, we identify g(x) = (x 2 1 + x 2 2 ) -1 4 and U = [-1 4 , 1 4 ]. Using Theorem 2.1.1, we identify the points of ultimate tangentiality:

min |u|≤ 1 4 Dg(z)f (z, u) = min |u|≤ 1 4 2z 1 z 2 + 2z 2 u = 2z 1 z 2 -2 1 4 |z 2 | = 0
Thus they are given by (-1 2 , 0); ( 1 2 , 0); ( 1 4 , 3 16 ) and (-1 4 , - 3 16 ). We derive the associated control function from the Hamiltonian minimisation condition (2.10):

ū(t) =        1 4 if λ 2 (t) < 0 -1 4 if λ 2 (t) > 0 arbitrary if λ 2 (t) = 0.
The co-state dynamics are given by:

λ1 = 0 λ2 = -λ 1 with λ( t) T = Dg(z) = (2x 1 ( t), 2x 2 ( t)).
We now need to integrate backwards from each of the ultimate tangentiality points in order to identify the barrier. Doing this from the points (± 1 4 , ± 3 16 ) gives us trajectories that immediately leave the set G, and so we can ignore these curves.

If we consider the point (x 1 ( t), x 2 ( t)) = ( 1 2 , 0) along with the final adjoint (λ 1 ( t), λ 2 ( t)) = (1, 0), we get λ 1 (t) ≡ 1 and λ 2 (t) = -t + t > 0 for all t ∈ (-∞, t], and thus ū(t) ≡ - 1 4 . A similar argument shows that ū(t) ≡ 1 4 for the barrier curve ending at (x 1 ( t), x 2 ( t)) = (-1 2 , 0).

If we now use this information and integrate backwards from ( 1 2 , 0) and (-1 2 , 0) we get the barrier as in Figure 2.2. Note that this is the exact admissible set and, in this example, corresponds to the infinite horizon viability kernel V iab [0,∞) .

The above example suggests that finding the admissible set using the theory of barriers is much simpler than the methods from viability theory: compare the best approximation from [START_REF] Kaynama | Computing the viability kernel using maximal reachable sets[END_REF] that uses 377 iterations, computing an estimate of a reachable set at each iteration, versus integrating a differential equation twice using the barrier approach. However, it is fair to say that the barrier approach needs some "art" in solving the problem. In other words, experience is needed to quickly arrive at the solution, similar to solving optimal control problems via the maximum principle. This "art" is especially needed in solving problems of higher dimension, (see the three dimensional problem of the Dubins' car in the section on stopping points, Section 4).

Other Approaches for Ensuring Constraint Satisfaction

Backwards Reachable Sets and Target Avoidance in Differential Games

Sets that are similar to admissible sets and viability kernels are of interest in the field of differential games. Following [START_REF] Mitchell | A time-dependent hamilton-jacobi formulation of reachable sets for continuous dynamic games[END_REF], and keeping their notations, consider a differential equation with two inputs:

ẋ = f (x, a, b) (2.15)
where x is the state, a is the input for player E (the "evader") and b is the input for the player P (the "pursuer"). It is assumed that a ∈ A t and b ∈ B t , where A t is the set of measurable functions from [t, 0] to A ⊂ R ma ; and B t is the set of measurable functions from [t, 0] to B ⊂ R m b with A and B compact, and t ∈ [-t 1 , 0], t 1 > 0. The function f : R n × A × B → R n is assumed to be uniformly continuous, bounded and Lipschitz in x for fixed a and b, which guarantees that there exists a unique solution of (2.15) for fixed a and b. We denote by x (a,b,x 0 ) (s) the solution of (2.15) at time s ∈ [t, 0] initiating from x 0 at time t with inputs a and b.

Having an additional input allows one to analyse and design a system's behaviour in a robust sense: for example, the second input b may represent disturbances or model uncertainties and one can then design the control a in order that it takes account of b. This is sometimes referred to as a "game against nature", see for example [START_REF] Başar | H ∞ -Optimal Control and Related Minimax Design Problems. A Dynamic Game Approach[END_REF], and [START_REF] Başar | Dynamic Noncooperative Game Theory[END_REF] for the relationship between differential games and robust control. Another example of where considering this second input (or multiple inputs) is useful is in collision avoidance problems, which occur, for example, in air traffic control, see [START_REF] Tomlin | A game theoretic approach to controller design for hybrid systems[END_REF].

Given a target set

G 0 = {x ∈ R n : g(x) ≤ 0}
where g is a bounded Lipschitz continuous function, player P wants to steer the state such that it intersects G 0 and player E wants the state to evade G 0 . The information that the players have of each other's inputs affects the solution of the game and a common assumption to make is that one of the players uses nonanticipative strategies. In other words, the pursuer's input is based on the current input of the evader, and it does not have access to the evader's input in the future. It should be mentioned that if the pursuer knows the initial condition of the game as well as the history of the evader's input for all r ∈ [t, s], then by the uniqueness of solutions it also knows the current state of the game. A nonanticipative strategy is therefore a state feedback with additional information of the other player's input.

Depending on the application the nonanticipative strategy may be given to the pursuer or the evader or both. By only giving it to the pursuer in the above definition we give this player an advantage over the evader and we can investigate reachability problems in a worst case context. For more information on strategies and solutions to differential games see the paper [START_REF] Varaiya | On the existence of solutions to a differential game[END_REF].

Given a target set G 0 , the goal is to find the set G t as defined next:

Definition 5 (Differential Games Backwards Reachable Set).

G t {x 0 ∈ R n : ∃γ ∈ Γ t s.t. ∀a ∈ A t ∃s ∈ [t, 0] s.t. x (a,γ,x 0 ) (s) ∈ G 0 } (2.16)
As can be seen, G t is the set of all initial conditions for which there exists an input for player P such that the state reaches G 0 regardless of the input for Player E. The idea is to never let the state venture inside the set G t as a way of ensuring that the constraints are always satisfied. Note that if G 0 is a subset of the state space where the constraints are violated in the theory on barriers, then (G t ) c is similar to the finite horizon admissible set, and can in fact be seen as a robust analogue:

(G t ) c = {x 0 ∈ R n : ∀γ ∈ Γ t , ∃a ∈ A t , s.t. x (a,γ,x 0 ) (s) / ∈ G 0 , ∀s ∈ [t, 0]}
The majority of the literature on target avoidance via backwards reachable sets deals with the problem by taking an optimisation approach involving Hamilton-Jacobi-Isaacs (HJI) partial differential equations. If we define the value of the game to be v(x, t) = min γ∈Γt max a∈At g(x (a,γ,x) (0)) then it can be shown, see [START_REF] Mitchell | A time-dependent hamilton-jacobi formulation of reachable sets for continuous dynamic games[END_REF], that v(x, t) is the viscocity solution of an HJI equation, and consequently G t is given by its zero sublevel set: Let v : R n × [-t 1 , 0] → R be the viscosity solution of the terminal value HJI PDE:

D t v(x, t) + min[0, H(x, D x v(x, t))] = 0
(2.17)

with v(x, 0) = g(x)
, where H(x, p) = max a∈A min b∈B p T f (x, a, b). Then, the zero sublevel set of v describes G t :

G t = {x ∈ R n : v(x, t) ≤ 0}.
Isaacs originally investigated these ideas in [START_REF] Isaacs | Differential Games[END_REF] using state feedback strategies which are of the form a(x) and b(x), along with a value given by:

v(x) = min b∈Bt max a∈At τ (G 0 )
where τ (G 0 ) inf{s ≥ t : x (a,b,x 0 ) (s) ∈ G 0 }. This is also where he introduced the concepts of capturability, barriers, the usable part and semi-permeability. However, it is well-known that this value function may be discontinuous, which creates problems when trying to compute/approximate it. The viscosity solution to (2.17) is continuous which allows its approximation via effective level-set methods, see for example [START_REF] Mitchell | Application of level set methods to control and reachability problems in continuous and hybrid systems[END_REF] and [START_REF] Chen | Exact and efficient hamilton-jacobi reachability for decoupled systems[END_REF].

Further references that study backwards reachable sets for differential games via an optimisation approach include [START_REF] Gao Yan | On the reachability problem for uncertain hybrid systems[END_REF], [START_REF] Lygeros | Controllers for reachability specifications for hybrid systems[END_REF] and [START_REF] Tomlin | Computational techniques for the verification of hybrid systems[END_REF]. These references also apply the results to computing "safety sets" in hybrid systems.

Similar ideas that use Hamilton Jacobi type equations to find backwards reachable sets have also been explored in a control systems context, i.e. with no second input. See for example [START_REF] Kurzhanski | Dynamic optimization for reachability problems[END_REF], [START_REF] Kurzhanski | The hamilton-jacobi type equations for nonlinear target control and their approximation[END_REF] [32], [START_REF] Oishi | Computing viable sets and reachable sets to design feedback linearizing control laws under saturation[END_REF] and [START_REF] Lygeros | On reachability and minimum cost optimal control[END_REF].

Barrier Certificates

Consider a time-varying nonlinear system ẋ(t) = f (x, t) (2.18) where x ∈ R n is the state, t ∈ R is time and it is assumed that f is continuous with respect to x and t. Also specified is a set X ⊂ R n ; an initial subset of the state space, labelled X 0 ; a forbidden/unsafe subset, labelled X u ; and a time interval [t 0 , t 1 ], t 0 ≤ t 1 .

Definition 6. The system (2.18) with sets X, X 0 , X u , and time interval [t 0 , t 1 ] is said to be safe if x x 0 (t 1 ) / ∈ X u for all x 0 ∈ X 0 .

Safety is then established via Lyapunov-like sufficient conditions as in the next theorem.

Theorem 2.3.2

Suppose that there exists a real-valued function B(x, t) that is continuously differentiable w.r.t. x and t, such that

B(x(t 1 ), t 1 ) > 0, ∀x(t 1 ) ∈ X u B(x(t 0 ), t 0 ) ≤ 0, ∀x(t 0 ) ∈ X 0 2.3. Other Approaches for Ensuring Constraint Satisfaction 21 ∂B ∂x (x, t)f (x, t) + ∂B ∂t (x, t) ≤ 0, ∀x ∈ X, ∀t ∈ [t 0 , t 1 ].
Then the system is safe.

The function B is called a barrier function or certificate because its zero level set specifies a "barrier" between the initial states and the unsafe states that system trajectories cannot cross. The attractiveness of the approach comes from the fact that if f is polynomial, and the sets X 0 and X u are described by polynomial inequalities, then polynomial barrier functions can be obtained via convex programming. However, note that this approach verifies whether a given set X 0 is safe and differs from the theory on barriers and viability theory where "safe" sets are computed. Note that there is no control in the right hand side of (2.18), and so in a control systems setting Theorem 2.3.2 would at best be applicable for verifying safety given a candidate control function. However, in [START_REF] Prajna | Barrier certificates for nonlinear model validation[END_REF] an extension of the theorem is stated that involves multiple barrier functions for control functions that are piecewise constant.

Another point to make is that the approach only considers finite horizons, and so asymptotic behaviour of system trajectories cannot be investigated. To clarify, consider the example from [START_REF] Wisniewski | Converse barrier certificate theorem[END_REF] of a linear system ẋ = Ax with A a Hurwitz matrix, and let X u = {0}, with X 0 = R \ {0}. Then this system is safe for any t 1 < ∞, even though all trajectories approach X u as t approaches ∞. These issues are further addressed in the same paper.

For more information on barrier certificates see the references [START_REF] Prajna | Barrier certificates for nonlinear model validation[END_REF], [START_REF] Prajna | Convex programs for temporal verification of nonlinear dynamical systems[END_REF] and [START_REF] Prajna | Safety verification of hybrid systems using barrier certificates[END_REF] from where Definition 6 and Theorem 2.3.2 have been adapted.

Barrier Lyapunov Functions in Backstepping

Given a nonlinear control system in strict feedback form with state constraints, the literature on barrier Lyapunov functions aims to design/find controllers in order to track a desired output without violating the constraints for a given initial state. Therefore, it differs from previously mentioned methods where a type of "safety set" is sought that consists of initial conditions for which there exist admissible controls. Nevertheless, we summarise the method and begin by briefly covering the method of backstepping.

Backstepping is a well-known method for constructing stabilizing controllers for nonlinear systems in strict feedback form, see for example [START_REF] Khalil | Nonlinear Systems[END_REF]Ch. 14] and [START_REF] Krstic | Nonlinear and Adaptive Control Design[END_REF]. Following [START_REF] Khalil | Nonlinear Systems[END_REF], a strict feedback system is given by

                           ẋ = f 0 (x) + g 0 (x)z 1 ż1 = f 1 (x, z 1 ) + g 1 (x, z 1 )z 2 ż2 = f 2 (x, z 1 , z 2 ) + g 2 (x, z 1 , z 2 )z 3 . . . żk-1 = f k-1 (x, z 1 , . . . , z k-1 ) + g k-1 (x, z 1 , . . . , z k-1 )z k żk = f k (x, z 1 , . . . , z k ) + g k (x, z 1 , . . . , z k )u (2.19)
where x ∈ R n , z i ∈ R, i = 1, . . . , k, with initial conditions x(0) = x 0 , z i (0) = z 0 i and u ∈ R is the input. It is assumed that the functions f 0 : D → R n and g 0 : D → R n , are smooth in a domain D ⊂ R n that contains x = 0. Furthermore, it is assumed that f i (0) = 0 for i = 0, . . . , k and g i (x, z 1 , . . . , z i ) = 0 i = 1, . . . , k over some domain of interest. The goal is to design a state feedback such that the origin (x, z i , . . . , z k ) = (0, . . . , 0) is stable.

Chapter 2. A Short Survey of Constrained Systems

Backstepping constructs the stabilizing controller recursively. To explain the method, consider the system:

η = f (η) + g(η)ξ (2.20) ξ = f j (η, ξ) + g j (η, ξ)u (2.21)
where η ∈ R n , ξ ∈ R, and the assumptions imposed on the functions f and g are the same as those imposed on f 0 and g 0 above. The functions f j and g j have the same assumption imposed on them as f i and g i for i = 1, . .

∂V ∂η [f (η) + g(η)φ(η)] ≤ -W (η) ∀η ∈ D (2.22)
where W (η) is positive definite. Then, the control function:

u = 1 g j ∂φ ∂η [f (η) + g(η)ξ] - ∂V ∂η g(η) -k [ξ -φ(η)] -f j (η, ξ)
for some k > 0 stabilises the origin of (2.20) -(2.21) with

V (η) + [ξ -φ(η)] 2 2 (2.23)
as a Lyapunov function.

Now considering the system

ẋ = f 0 (x) + g 0 (x)z 1 (2.24) ż1 = f 1 (x, z 1 ) + g 1 (x, z 1 )z 2 (2.25)
we assume that z 1 = φ 0 (x) is a stabilizing feedback for equation (2.24) (which we have obtained or designed somehow) with φ 0 (0) = 0 and V 0 (x) is a smooth Lyapunov function that satisfies (2.22). In (2.20) -(2.21) we let:

η = x, ξ = z 1 , f = f 0 , g = g 0 , f j = f 1 , g j = g 1 , u = z 2
and from Lemma 2.3.1 we arrive at the function:

z 2 = φ 1 (x, z 1 ) = 1 g 1 ∂φ 0 ∂x [f 0 (x) + g 0 (x)z 1 ] - ∂V 0 ∂x g 0 (x) -k 1 [z 1 -φ 0 ] -f 1 (x, z 1 )
with k 1 > 0, which stabilises the origin of (2.24) -(2.25), with the smooth Lyapunov function

V 1 (x, z 1 ) = V 0 (x) + [z 1 -φ 0 (x)] 2 2 .
Now we consider the system

ẋ = f 0 (x) + g 0 (x)z 1 ż1 = f 1 (x, z 1 ) + g 1 (x, z 1 )z 2 ż2 = f 2 (x, z 1 , z 2 ) + g 2 (x, z 1 , z 2 )z 3 let η = x z 1 , ξ = z 2 , f = f 0 + g 0 z 1 f 1 , g = 0 g 1 , f j = f 2 , g j = g 2 , u = z 3
and use Lemma 2.3.1 to arrive, after some simplification, at

z 3 = φ 2 (x, z 1 , z 2 ) = 1 g 2 ∂φ 1 ∂x [f 0 (x) + g 0 (x)z 1 ] + ∂φ 1 ∂z 1 [f 1 (x) + g 1 (x)z 2 ] - ∂V 1 ∂z 1 g 1 -k 2 [z 2 -φ 1 ] -f 2
with k 2 > 0, and a smooth Lyapunov function

V 2 (x, z 1 , z 2 ) = V 0 (x) + [z 1 -φ 0 (x)] 2 2 + [z 2 -φ 1 (x)] 2 2
We carry on in this way k times to arrive at the final stabilizing control function, u = φ k (x, z 1 , . . . , z k ), along with a smooth Lyapunov function:

V k (x, z 1 , . . . , z k ) = V 0 (x) + k j=1 [z j -φ j-1 (x)] 2 2 .
(2.26)

The Lyapunov function V k (x, z 1 , . . . , z k )'s sublevel sets are invariant sets. However, if there are state constraints imposed on the system, then there is no guarantee that the state will always satisfy these constraints.

A barrier Lyapunov function replaces the function (2.26) and is designed in such a way that the state will remain admissible. The idea is to choose the Lyapunov function so that it becomes unbounded as the state approaches the boundary of some subset of the state space. These functions have been used in output tracking problems for systems in strict feedback, and we briefly summarise the method as given in [START_REF] Peng Tee | Barrier lyapunov functions for the control of output-constrained nonlinear systems[END_REF].

Definition 7. [55]

A barrier Lyapunov function is a scalar function V (x), defined with respect to the system ẋ = f (x) on an open region D containing the origin, that is continuous, positive definite, has continuous first-order partial derivatives at every point of D, has the property V (x) → ∞ as x approaches the boundary [of the closure] of D, and satisfies V (x(t)) ≤ b, for all t ≥ 0 along the solution of ẋ = f (x) for x(0) ∈ D and some positive constant b. We consider the system (2.19), with x ∈ R, f 0 : D → R, g 0 : D → R, D ⊂ R, and with a single output y = x. We also impose constraints on the state:

   |x| ≤ k c 0 |z i | ≤ k c i , i = 1, . . . , k (2.27)
where k c 0 , and k c i for each i are positive constants and let

G = {(x, z 1 , . . . , z k ) : |x| ≤ k c 0 , |z i | ≤ k c i , i = 1, . . . ,
t∈[0,∞) |y d (t)| ≤ A 0 ,
A 0 > 0, while satisfying the constraints (2.27) . In the spirit of Lemma 2.3.1, we do this by recursively constructing a control law along with a barrier Lyapunov function that guarantees that the state remains in some subset of the state space. Consider the candidate barrier Lyapunov function:

V k (x, z 1 , . . . , z k ) = 1 2 ln k 2 b 0 k 2 b 0 -x 2 + k i=1 1 2 ln k 2 b i k 2 b i -z 2 i , i = 1 . . . , k.
where k b 0 = k c 0 -A 0 and the k b i 's are positive constants to be chosen. Let w 0 x -y d , and w i z i -α i-1 for i = 1, . . . , k, where the α i 's are stabilizing functions that are given by

α i = 1 g i -f i + αi-1 -(k 2 b i -w 2 i )κ i w i - k 2 b i -w 2 i k 2 b i-1 -w 2 i-1 g i-1 w i-1 , i = 1, . . . , k and α 0 = 1 g 0 -f 0 -(k 2 b 0 -w 2 0 )κ 0 w 0 + ẏd
where κ 0 and κ i for i = 1, . . . , k are also positive constants to be chosen. The control is then given by u = α k . Now considering the system ẇ = h(w)

with initial condition w(0) ∈ R k+1 that satisfies |w i (0)| < k b i for i = 0, . . . , k, it can be shown that Vk (w 0 , . . . , w k ) = - k i=0 κ i w i
and that the solution of the system satisfies |w i (t)| ≤ k b i , i = 0, . . . , k, for all t ≥ 0. Under some assumptions placed on y d as well as the functions g i , it may then be possible to find design parameters (k b 1 , . . . , k b k , κ 1 , . . . , κ k ) that guarantee that the output asymptotically tracks y d and that the state (x, z 1 , . . . , z k ) remains in a subset of G. However, finding these parameters involves solving a nonlinear program for each initial condition that is of interest.

For more information on barrier Lyapunov functions consult the references [START_REF] Peng | Control of nonlinear systems with full state constraint using a barrier lyapunov function[END_REF] [44], [START_REF] Peng | Control of state-constrained nonlinear systems using integral barrier lyapunov functionals[END_REF], [START_REF] Ngo | Integrator backstepping using barrier functions for systems with multiple state constraints[END_REF].

Introduction

In this chapter we extend the results on barriers in constrained nonlinear systems from [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF], which has been summarised in Section 2.1, to the case where the constraints are mixed. Recall that these are constraints that explicitly depend on the control as well as the state.

In the exposition of the generalisation we follow similar steps as in Section 2.1. Important contributions include:

• The admissible set as defined in the mixed constraint case is shown to still be closed and we study a subset of its boundary, that we still call the barrier, which also exhibits a semi-permeability property.

• Trajectories that run along the barrier may intersect the set G 0 = {x : min u∈U max i=1,...,p g i (x, u) = 0}, see Proposition 3.3.2. (Note that we have redefined the set G 0 as it occurred in Section 2.1). In this case, the intersection of the barrier with the set G 0 occurs tangentially in a generalised manner, see Proposition 3.3.4, and is characterised using tools from nonsmooth analysis.

• Trajectories that run along the barrier still satisfy a minimum-like principle, see Theorem 3.4.1, though containing significant modifications as compared with Theorem 2.1.1. To prove Theorem 3.4.1 we use a duality-like argument similar to the one from [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF]: the boundary of the constrained reachable set at some time t, issued from any point of the barrier, is tangent to the barrier, and the respective normals of both boundaries are opposed. To characterise the extremum trajectories whose Chapter 3. Barriers for Mixed Constraints endpoints lie on the boundary of the reachable set we needed to generalise a form of the Pontyagin maximum principle, as is covered in Appendix B. This required the introduction of assumption (A3.4) in order to construct the suitable needle perturbations that satisfy the constraints in order to generate the perturbation cone, which is a key construct used in proving Theorem B.2.1.

• The characterisation of the intersection of the barrier with the set G 0 , when this occurs, allows us to identify points on the barrier, along with the adjoint, that serve as endpoints from where the barrier can be constructed via the modified minimum-like principle. However, when the barrier does not intersect G 0 it remains in G -for all time and in this case no conditions have yet been obtained in order to identify points on the barrier that can be used in its construction. We illustrate this phenomenon with an example at the end of Section 3.5 for which we are able to provide a full solution.

In Section 3.5 we further demonstrate the results by finding the barrier for two examples that involve mixed constraints where the barrier reaches G 0 . Some of the work in this chapter can be found in [START_REF] Esterhuizen | Barriers in nonlinear control systems with mixed constraints[END_REF].

Dynamical Control Systems with Mixed Constraints

We consider the following nonlinear system with mixed constraints:

ẋ = f (x, u), (3.1) x(t 0 ) = x 0 , (3.2) u ∈ U, (3.3
)

g i x(t), u(t) ≤ 0 for a.e. t ∈ [t 0 , ∞) i = 1, ..., p (3.4)
where x(t) ∈ R n . We denote by U a given compact convex subset of R m , expressible as

U {u ∈ R m : γ j (u) ≤ 0, j = 1, . . . , r} (3.5)
with r ≥ m, where the functions γ j are convex and of class C 2 . Note that this definition of U differs from the one in Section 2.1; it is needed in this form to prove the generalisation of the maximum principle in Theorem B.2.1. Further assumptions on the functions {γ j , j = 1, . . . , r} and {g i , i = 1, . . . , p}, associated to the constraints, are imposed in (A3.4)-(A3.5) (see below). The input function u is assumed to belong to the set U of Lebesgue measurable functions from [t 0 , ∞) to U , i.e. u is a measurable function such that u(t) ∈ U for almost all t ∈ [t 0 , ∞).

As before, x u (t) or x (u,x 0 ) (t) denotes the solution of the differential equation (3.1) at t with input u ∈ U and initial condition (3.2).

The constraints (3.4), called mixed constraints [START_REF] Hestenes | Calculus of Variations and Optimal Control Theory[END_REF][START_REF] Clarke | Optimal control problems with mixed constraints[END_REF], explicitly depend both on the state and the control. We denote by g(x, u) the vector-valued function whose i-th component is g i (x, u). By g(x, u) ≺ 0 (resp. g(x, u) 0) we mean g i (x, u) < 0 (resp. g i (x, u) ≤ 0) for all i. By g(x, u) 0, we mean g i (x, u) = 0 for at least one i. Note that the mapping t → g(x(t), u(t)) may be discontinuous. We impose the condition that the mixed constraints are satisfied almost everywhere in order to arrive at the result that the space of solutions is compact, see Appendix A.

Dynamical Control Systems with Mixed Constraints

27

We now (re)define the following sets:

G u∈U {x ∈ R n : g(x, u) 0} (3.6) G 0 {x ∈ G : min u∈U max i∈{1,...,p} g i (x, u) = 0} (3.7) G - u∈U {x ∈ R n : g(x, u) ≺ 0} (3.8)
Because the constraints are now mixed, we also need to introduce the following set:

U (x) {u ∈ U : g(x, u) 0} ∀x ∈ G.
Given a pair (x, u) ∈ R n × U , we denote by I(x, u) the set of indices, possibly empty, corresponding to the "active" mixed constraints, namely:

I(x, u) = {i 1 , . . . , i s 1 } {i ∈ {1, . . . , p} : g i (x, u) = 0}
and by J(u) the set of indices, possibly empty, corresponding to the "active" input constraints:

J(u) = {j 1 , . . . , j s 2 } {j ∈ {1, . . . r} : γ j (u) = 0}. The integer s 1 #(I(x, u)) ≤ p (resp. s 2 #(J(u)) ≤ r)
is the number of elements of I(x, u) (resp. of J(u)). Thus, s 1 + s 2 represents the number of "active" constraints, among the p + r constraints, at (x, u).

As in [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF] a Lebesgue point, which we will denote by L-point, for a given control u ∈ U is a time t ∈ [t 0 , ∞) such that u is continuous at t in the sense that there exists a bounded (possibly empty) subset I 0 ⊂ [t 0 , ∞), of zero Lebesgue measure, which does not contain t, such that u(t) = lim s→t,s ∈I 0 u(s). By Lusin's theorem, the Lebesgue measure of the complement in [t 0 , T ], for all finite T , of the set of Lebesgue points is equal to 0.

If u 1 ∈ U and u 2 ∈ U, and if τ ≥ t 0 is given, the concatenated input v, defined by

v(t) = u 1 (t) if t ∈ [t 0 , τ [ u 2 (t) if t ≥ τ satisfies v ∈ U. The concatenation operator relative to τ is denoted by τ , i.e. v = u 1 τ u 2 .
We further assume:

(A3.1) f is an at least C 2 vector field of R n for every u in an open subset U 1 of R m
containing U , whose dependence with respect to u is also at least C2 .

(A3.2)

There exists a constant 0 < C < +∞ such that the following inequality holds true: sup

u∈U |x T f (x, u)| ≤ C(1 + x 2 ), for all x (A3.
3) The set f (x, U ), called the vectogram in [START_REF] Isaacs | Differential Games[END_REF], is convex for all x ∈ R n .

(A3.4) g is at least C 2 from R n × U 1 to R p . Moreover, the vectors ∂g i ∂u (x, u), ∂γ j ∂u (u) : i ∈ I(x, u), j ∈ J(u) (3.9)
are linearly independent at every (x, u) ∈ R n × U for which I(x, u) or J(u) is non empty. 1 We say, in this case, that the point x is regular with respect to u (see e.g. [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF][START_REF] Hestenes | Calculus of Variations and Optimal Control Theory[END_REF]).

Chapter 3. Barriers for Mixed Constraints (A3.5) For all i = 1, . . . , p, the mapping u → g i (x, u) is convex for all x ∈ R n .

Given u ∈ U, we will say that an integral curve x u of equation (3.1) defined on [t 0 , T ] is regular if, and only if, at each L-point t of u, x u (t) is regular in the afore mentioned sense w.r.t. u(t), and if t is a point of discontinuity of u, x u (t) is regular in the afore mentioned sense w.r.t. u(t -) and u(t + ), with u(t -) lim τ t,t / ∈I 0 u(τ ) and u(t + ) lim τ t,t / ∈I 0 u(τ ), I 0 being a suitable zero-measure set of R.

Since system (3.1) is time-invariant, the initial time t 0 may be taken as 0. When clear from the context, "∀t" or "for a.e t" will mean "∀t ∈ [0, ∞)" or "for a.e. t ∈ [0, ∞)". Note that throughout the thesis a.e. is understood with respect to the Lebesgue measure.

The Admissible Set: Topological Properties

We now introduce the admissible set in the mixed constraint case.

Definition 8 (Admissible States

). We will say that a state-space point x is admissible if there exists, at least, one input function v ∈ U, such that (3.1)-(3.4) are satisfied for x 0 = x and u = v:

A {x ∈ G : ∃u ∈ U, g x (u,x) (t), u(t)
0, for a.e. t}.

(3.10)

According to the Markovian property of the system, any point of the integral curve,

x (v,x) (t ), t ∈ [0, ∞), is also an admissible point.
The complement of A in G, namely A C G \ A, is thus given by:

A C {x ∈ G : ∀u ∈ U, ∃i ∈ {1, ..., p}, ∃ t < +∞, L -point, s.t. g i x (u,x) ( t), u( t) > 0}.
(3.11) We assume that both A and A C contain at least one element to discard the trivial cases A = ∅ and A C = ∅.

We use the notations int(S) (resp. cl(S)) (resp.co(S)) for the interior (resp. the closure) (resp. the closed and convex hull) of a set S.

We also consider the family of sets A T , called finite horizon admissible sets, defined for all finite 0 ≤ T < +∞ by

A T {x ∈ G : ∃u ∈ U, g x (u,x) (t), u(t)
0, for a.e. t ≤ T } as well as its complement A C T in G is given by:

A C T {x ∈ G : ∀u ∈ U, ∃i ∈ {1, ..., p}, ∃ t ≤ T, L -point s.t. g i x (u,x) ( t), u( t) > 0}.
Clearly, since A ⊂ A T for all finite T , we have A T = ∅.

Proposition 3.2.1

Assume that (A3.1)-(A3.5) are valid. The set of finite horizon admissible states, A T , is closed for all finite T .

Proof :

The proof is a direct consequence of Lemma A.0.2 and follows the same lines as Proposition 4.1 of [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF], up to small changes.

Consider a sequence of initial states {x k } k∈N in A T converging to x as k tends to infinity. By definition of A T , for every k ∈ N, there exists u k ∈ U such that the corresponding integral curve x (u k ,x k ) satisfies g(x (u k ,x k ) (t), u k (t)) 0 for a.e. t ∈ [0, T ]. According to Lemma A.0.2, there exists a uniformly converging subsequence, still denoted by x (u k ,x k ) , to the absolutely continuous integral curve x (ū,x) for some ū ∈ U. Moreover, we have g(x (ū,x)) (t), ū(t)) 0 for almost every t ∈ [0, T ], hence x ∈ A T , and the proposition is proven.

Corollary 3.2.1

Under the assumptions of Proposition 3.2.1, the set A is closed.

Proof : This proof follows the same lines as Corollary 4.1 of [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF], and we give it for completeness.

For all 0 ≤ T 1 ≤ T 2 < ∞, we have

A = A ∞ ⊂ A T 2 ⊂ A T 1 ⊂ A 0 = G.
Therefore, A = ∩ T ≥0 A T and the result follows from the fact that the intersection of a family of closed sets is closed.

Boundary of the Admissible Set

A Characterisation of A, its Complement and its Boundary

Denoting by ∂A T (resp. ∂A) the boundary of A T (resp. A), we know from Proposition 3.2.1 and Corollary 3.2.1 that ∂A T ⊂ A T (resp. ∂A ⊂ A). As in [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF], we focus on the characterisation of these boundaries and derive the generalisation of Proposition 5.1 from [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] to the mixed constraint case. Note that in this generalisation we need to consider the L ∞ (0, ∞)-norm of a measurable function h : [0, ∞) → R. Proposition 3.3.1

Assume that (A3.1)-(A3.5) hold. We have the following equivalences:

(i) x ∈ A is equivalent to min u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≤ 0 (3.12) (ii) x ∈ A C is equivalent to min u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) > 0 (3.13) (iii) x ∈ ∂A is equivalent to min u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) = 0. ( 3
g i (x (u k ,x) (t), u k (t)) = inf u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)). (3.16)
According to Lemma A.0.2 in Appendix A, with x k = x for every k ∈ N, one can extract a uniformly convergent subsequence on every compact interval [0, T ] with T ≥ 0, still denoted by x (u k ,x) , whose limit is x (ū,x) for some ū ∈ U. Moreover, one can build another subsequence, made of convex combinations of the {g(x x) , u j ), where the α k i,j 's are all non negative real numbers such that k j=1 α k i,j = 1 for all i = 1, . . . , p and k ≥ 1, that pointwise converges to g(x (ū,x) , ū) a.e. t ∈ [0, T ] for all T ≥ 0.

(u k ,x) , u k )}, namely k j=1 α k i,j g i (x (u j ,
According to Egorov's theorem [START_REF] Yosida | Functional Analysis[END_REF], the pointwise convergence implies that, for almost every t ∈ [0, T ], all T ≥ 0 and ε > 0, there exists k 0 (t, T, ε) ∈ N such that, for every k ≥ k 0 (t, T, ε),

g i (x (ū,x) (t), ū(t)) ≤ k j=1 α k i,j g i (x (u j ,x) (t), u j (t)) + ε.
Taking the maximum with respect to i ∈ {1, . . . , p} and the essential supremum w.r.t. t ∈ [0, ∞) on the right hand side, we get

g i (x (ū,x) (t), ū(t)) ≤ k j=1 α k i,j ess. sup s∈[0,∞) max i=1,...,p g i (x (u j ,x) (s), u j (s)) + ε ∀t ∈ [0, T ].
On the other hand, by the definition of the limit in (3.16), for every ε > 0 there exists k 1 (ε) ∈ N such that for all j ≥ k 1 (ε), we have ess. sup

t∈[0,∞) max i=1,...,p g i (x (u j ,x) (t), u j (t)) ≤ inf u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) + ε and thus g i (x (ū,x) (t), ū(t)) ≤ k j=1 α k i,j inf u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) + 2ε ∀t ∈ [0, T ].
Hence, using the fact that k j=1 α k i,j = 1, for all k ≥ max(k 0 (t, T, ε), k 1 (ε)), we get

g i (x (ū,x) (t), ū(t)) ≤ inf u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t))+2ε a.e. t ∈ [0, T ], ∀i = 1, . . . , p.
However, since the latter inequality is valid for any t and T ≥ 0 and it does not depend on k anymore, and since its right-hand side is independent of i, t and T , we have that the inequality holds if we maximize the left-hand side with respect to i ∈ {1, . . . , p} and take its essential supremum with respect to t ∈ [0, ∞). Thus, using the definition of the infimum w.r.t. u, we obtain that, for every ε > 0 ess. sup

t∈[0,∞) max i=1,...,p g i (x (ū,x) (t), ū(t)) ≤ inf u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) + 2ε ≤ ess. sup t∈[0,∞) max i=1,...,p g i (x (ū,x) (t), ū(t)) + 2ε,
or, using also (3.15), that ess. sup

t∈[0,∞) max i=1,...,p g i (x (ū,x) (t), ū(t)) = inf u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≤ 0,
which proves (3.12).

Conversely, if (3.12) holds, there exists an input u ∈ U such that ess. sup

t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≤ 0,
which in turn implies that g(x (u,x) (t), u(t)) 0 for almost all t ≥ 0, or, in other words, x ∈ A, which achieves the proof of (i).

To prove (ii), we now assume that x ∈ A C and prove (3.13). By definition of A C , for all u ∈ U, we have ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t)) > 0 and thus

inf u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≥ 0.
The same minimising sequence argument as in the proof of (i) shows that the minimum over u ∈ U is achieved by some ū ∈ U and that

min u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≥ 0.
But the inequality has to be strict since, if min

u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) = 0, it
would imply, according to (i), that x ∈ A which contradicts the assumption. Therefore, we have proven (3.13).

Conversely, if (3.13) holds, it is immediately seen that x is such that ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) > 0 for all u ∈ U. The essential supremum with respect to t must be reached at some t(u) < +∞ since t(u) = +∞ would imply that max i=1,...,p g i (x (u,x) (t), u(t)) ≤ 0 for almost all t < +∞, and thus ess. sup

t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≤ 0. A fortiori, min u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≤ 0,
which contradicts (3.13). Thus, for all u ∈ U, there exists t(u) < +∞ such that max i=1,...,p g i (x (u,x) ( t(u)), u( t(u))) > 0, and hence x ∈ A C , which proves (ii).

To prove (iii), since A is closed, x ∈ ∂A is equivalent to x ∈ A and x ∈ cl(A C ), the closure of A C , which, by (i) and (ii), is equivalent to (3.12) and (3.13) (the latter with a "≥" symbol as a consequence of x ∈ cl(A C )), which in turn is equivalent to (3.14).

Remark 1. The same formulas hold true for A T , A C

T and ∂A T if one replaces the infinite time interval [0, ∞) by [0, T ].

Geometric Description of the Barrier

As a consequence of (3.14), the boundary ∂A is made of points x such that there exists a ū ∈ U for which at least one of the constraints is saturated for some L-point t, i.e. g(x (ū,x) ( t), ū( t)) 0. We now (re)define the barrier for the mixed constraint setting:

[∂A] -= ∂A ∩ G - Definition 9.
The set [∂A] -is called the barrier of the set A (see Proposition 3.3.3).

We now present the mixed constraint analogue of Proposition 2.1.2. Assume (A3.1) to (A3.5) hold. The barrier [∂A] -is made of points x ∈ G -for which there exists ū ∈ U and an integral curve x (ū,x) entirely contained in [∂A] - either until it intersects G 0 , i.e. at a point z = x (ū,x) ( t), for some t, such that min u∈U max i=1,...,p g i (z, u) = 0, or which never intersects G 0 .

Proof : Let x ∈ [∂A] -, therefore satisfying (3.14). In particular, there exists ū ∈ U and t > 0 such that

min u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x u,x (t), u(t)) = ess. sup t∈[0,∞) max i=1,...,p g i (x ū,x (t), ū(t)) = max i=1,...,p g i (x (ū,x) ( t), ū( t)) = 0
where ū has been possibly modified on a 0-measure set to satisfy the right-hand side equality. Then, choose t as the first time for which max i=1,...,p g i (x (ū,x) ( t), ū( t)) = 0 and an arbitrary t 0 ∈ [0, t[. Setting ν(t) = ū(t 0 + t), since t 0 < t, the point ξ = x (ū,x) (t 0 ) satisfies max i=1,...,p g i (ξ, ν(0)) = max i=1,...,p g i (x (ū,x) (t 0 ), ū(t 0 )) < 0, i.e. ξ ∈ G -, and by a standard dynamic programming argument (since

x (ν,ξ) (t) = x (ū,x) (t 0 + t) for all t ≥ 0), min u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,ξ) (t), u(t 0 + t)) = 0. It follows that ξ ∈ [∂A]
-and, therefore, the arc of integral curve between 0 and t starting from

x ∈ [∂A] -is entirely contained in [∂A] -. Since [∂A] -⊂ G -, taking the closure on both sides, we get cl([∂A] -) ⊂ cl(G -) = G -∪ cl(G -) ∩ G C -. Thus either cl([∂A] -) ⊂ G -in which case the integral curves in [∂A] -remain in G -forever, or cl([∂A] -) ⊂ cl(G -) ∩ G C -. Let us prove that cl(G -) ∩ G C -= G 0 . According to (3.8) we have that x ∈ G -is equivalent to min u∈U max i=1,...,p g i (x, u) < 0 and x ∈ G C -is equivalent to max i=1,...,p g i (x, u) ≥ 0, ∀u ∈ U. Thus, x ∈ cl(G -) ∩ G C -is equivalent to min u∈U max i=1,...,p g i (x, u) = 0
and our assertion is proven.

Therefore, the integral curves in [∂A] -can intersect G 0 .

We now prove the semi-permeability property of x (ū,x+εh) (σ), we indeed have ξ ε,h ∈ G -. Assume, by contradiction, that there exists ũ ∈ U such that max i=1,...,p g i (x (ũ,ξ ε,h ) (t), ũ(t)) < 0 for all t ∈ [σ, σ + τ [ for some sufficiently small τ > 0 and ζ x (ũ,ξ ε,h ) (σ + τ ) ∈ int(A), which indeed implies that x (ũ,ξ ε,h ) (t) ∈ G -for all t ∈ [σ, σ + τ [. As a consequence of (3.12) and (3.14), there exists v ∈ U such that ess. sup

t∈[0,∞) max i=1,...,p g i (x (v,ζ) (τ + σ + t), v(τ + σ + t)) < 0.
Setting ṽ = ū τ ũ τ +σ v, we easily verify that ess. sup t∈[0,∞) max i=1,...,p g i (x (ṽ,x+εh) (t), ṽ(t)) < 0, which implies, again by (3.12) and (3.14), that x+εh ∈ int(A), the whole integral curve x (ṽ,x+εh) remaining in G -, hence contradicting the fact that x + εh ∈ A C . We thus conclude that no integral curve starting in A C can penetrate the interior of A before leaving G -. Finally, taking the limit as ε → 0 we conclude that no integral curve initiating on [∂A] - can penetrate the interior of A before leaving G -.

Ultimate Tangentiality

In this section we generalise the ultimate tangentialiy condition as given by Proposition 2.1.3. We define g(x) min u∈U max i∈{1,...,p}

g i (x, u). ( 3.17)
It can be seen that G 0 is the set of points x ∈ G such that g(x) = 0. We prove that g is locally Lipschitz, a simplified version of a result of J. Danskin [START_REF] Danskin | The Theory of Max-Min[END_REF]:

Lemma 3.3.1
The function g is locally Lipschitz, and thus absolutely continuous and almost everywhere differentiable, on every open and bounded subset of R n .

Proof : Consider the family of subsets of i=1,...,p cl(g -1 i (] -∞, 0])) defined by

O j {(x, u) ∈ i=1,...,p cl(g -1 i (] -∞, 0])) : max i=1,...,p g i (x, u) = g j (x, u)}, j = 1, . . . , p.
It is clear that j=1,...,p O j = i=1,...,p cl(g -1 i (]-∞, 0])) and that we can extract a minimal subfamily of {O j } still covering i=1,...,p cl(g -1

i (] -∞, 0])), where every O j has nonempty interior. In the sequel we only consider this subfamily. Given x 1 and x 2 in G - arbitrarily close, there exists i

1 such that (x 1 , u 1 ) ∈ O i 1 with u 1 such that g i 1 (x 1 , u 1 ) = min u∈U g i 1 (x 1 , u), and such that (x 2 , u 1 ) ∈ O i 1 . Thus, we get g(x 2 ) -g(x 1 ) = min u∈U max i∈{1,...,p} g i (x 2 , u) -min u∈U max i∈{1,...,p} g i (x 1 , u) ≤ max i∈{1,...,p} g i (x 2 , u 1 ) -max i∈{1,...,p} g i (x 1 , u 1 ) ≤ max i∈{1,...,p} g i (x 2 , u 1 ) -g i 1 (x 1 , u 1 ) ≤ g i 1 (x 2 , u 1 ) -g i 1 (x 1 , u 1 ) (3.18)
Thus, since g is continuously differentiable in x for all u, there exists a point ξ 1 such that g i 1 (x 2 , u 1 ) -

g i 1 (x 1 , u 1 ) = D x g i 1 (ξ 1 , u 1 ) (x 2 -x 1 ).
Similarly, there exists i 2 such that (

x 2 , u 2 ) ∈ O i 2 with g i 2 (x 2 , u 2 ) = min u∈U g i 2 (x 2 , u) and (x 1 , u 2 ) ∈ O i 2 . We get g i 2 (x 2 , u 2 ) -g i 2 (x 1 , u 2 ) ≤ g(x 2 ) -g(x 1 ) (3.19)
Again, there exists a point ξ 2 such that g

i 2 (x 2 , u 2 ) -g i 2 (x 1 , u 2 ) = D x g i 2 (ξ 2 , u 2 ) (x 2 -x 1 ). Combining (3.18) and (3.19) yields |g(x 2 ) -g(x 1 )| ≤ C x 2 -x 1 with C = sup( D x g i 1 (ξ 1 , u 1 ) , D x g i 2 (ξ 2 , u 2 ) ).
It results that g is locally Lipschitz. The absolute continuity and almost everywhere differentiability follow from Rademacher's theorem (see e.g. [START_REF] Heinonen | Lectures on Lipschitz analysis[END_REF]Theorem 3.1]. See also [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF][START_REF] Clarke | Nonsmooth Analysis and Control Theory[END_REF]), which achieves to prove the lemma.

Now that we have established that the barrier may intersect the set {x ∈ G : g(x) = 0}, we will show that this intersection occurs in a generalised tangential manner. To do this we will need a few concepts from nonsmooth analysis, see for example [START_REF] Clarke | Nonsmooth Analysis and Control Theory[END_REF].

Consider h : X → R, where X is a finite dimensional vector space, and h is Lipschitz with Lipschitz constant K near a given point x ∈ X. The generalised directional derivative of h at x in the direction v is defined as follows:

h 0 (x; v) lim sup y→x,t→0 + h(y + tv) -h(y) t (3.20)
We also need to introduce the generalised gradient of h at x, labeled ∂h(x). In our setting, where we consider a Lipschitz function h : R n → R, the generalised gradient is the compact and convex set:

∂h(x) = co{ lim i→∞ Dh T (x i ) : x i → x, x i / ∈ Ω 1 ∪ Ω 2 } (3.21)
where Dh T (x) denotes the transpose of the row vector Dh(x) at x, Ω 1 is a zero measure set where h is nondifferentiable (recall that h is differentiable almost everywhere), Ω 2 is any zero-measure set and recall that co(S) denotes the closed and convex hull of an arbitrary set S.

The relationship between the generalised directional derivative and the generalised gradient is given by: -for all t in some time interval until it reaches G 0 at some finite time t ≥ 0. Then, the point

h 0 (x; v) = max ξ∈∂h(x) ξ T v. ( 3
z = x (ū,x) ( t) ∈ cl([∂A] -) ∩ G 0 , satisfies 0 = max ξ∈∂g(z) ξ T f (z, ū( t)) = min v∈U (z) max ξ∈∂g(z) ξ T f (z, v) = max ξ∈∂g(z) min v∈U (z) ξ T f (z, v). (3.23)
Moreover, if the function g is differentiable at the point z, then condition (3.23) reduces to the smooth counterpart:

0 = L f g(z, ū( t)) = min u∈U (z) L f g(z, u) (3.24)
where L f g(x, u) Dg(x)f (x, u) is the Lie derivative of g along the vector field f at (x, u).

Proof : Let x 0 ∈ [∂A] -, then there exists a ū ∈ U such that g(x (ū,x 0 ) (t)) < 0 until x (ū,x 0 ) intersects G 0 at some t. As in the proof of Proposition 3.3.2, we consider an open set O ⊂ R n such that x 0 + εh ∈ A C for all h ∈ O and h ≤ H, with H arbitrarily small, and all ε sufficiently small.

Introduce a needle perturbation of ū, labeled u κ,ε , at some Lebesgue point τ of ū before x (ū,x 0 ) intersects G 0 , in the spirit of [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF], i.e. a variation u κ,ε of ū, parameterized by the vector

κ (v, τ, l) ∈ U (x (ū,x 0 +εh) (τ -lε)) × [0, T ] × [0, L]
with bounded T, L, of the form

u κ,ε ū (τ -lε) v τ ū = v on [τ -lε, τ [ ū elsewhere on [0, T ] (3.25)
where v stands for the constant control equal to v ∈ U (x (ū,x 0 ) (τ )) for all t ∈ [τ -lε, τ [. Remark that, by definition of G -and U (x), since x (ū,x 0 ) (t) ∈ G -for all t < t, we have ū(t) ∈ U (x (ū,x 0 ) (t)) for all t < t and thus U (x (ū,x 0 ) (t)) = ∅ for all t < t.

Because

x 0 + εh ∈ A C , ∃t ε,κ,h < ∞ at which x (uκ,ε,x 0 +εh) (t ε,κ,h ) crosses G 0 , see Proposition 3.3.3.
As a result of the uniform convergence of x (uκ,ε,x 0 +εh) to x (ū,x 0 ) , there exists a t ≥ t, s.t. x (uκ,ε,x 0 +εh) (t ε,κ,h ) → x (ū,x 0 ) ( t) as ε → 0 and, according to the continuity of g, we have

lim ε→0 g(x (uκ,ε,x 0 +εh) (t ε,κ,h )) = 0 = g(x (ū,x 0 ) ( t)).
Because g(x (uκ,ε,x 0 +εh) (t ε,κ,h )) = 0 and g(x (ū,x 0 ) (t ε,κ,h )) ≤ 0 (recall that g(x (ū,x 0 ) (t ε,κ,h )) ≤ g(x (ū,x 0 ) (t ε,κ,h ), ū(t ε,κ,h )) ≤ 0 since the pair (x (ū,x 0 ) (t), ū(t)) satisfies the constraints for all t), we have that g(x (uκ,ε,x 0 +εh) (t ε,κ,h )) -g(x (ū,x 0 ) (t ε,κ,h )) ≥ 0.

Recall from [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF] as well as [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] that

x (uκ,ε,x 0 +εh) (t ε,κ,h ) = x (ū,x 0 ) (t ε,κ,h ) + εw(t ε,κ,h , κ, h) + O(ε 2 )
where

w(t, κ, h) Φ ū(t, 0)h + lΦ ū(t, τ ) f (x (ū,x 0 ) (τ ), v) -f (x (ū,x 0 ) (τ ), ū(τ )) , Φ ū(t,
ε k-r = lim ε→0 O(ε r ) = 0 for all 0 ≤ r ≤ k -1, k, r ∈ N.
Since g is almost everywhere differentiable, we have:

g(x (uκ,ε,x 0 +εh) (t ε,κ,h )) -g(x (ū,x 0 ) (t ε,κ,h )) ε = Dg(x (ū,x 0 ) (t ε,κ,h )).w(t ε,κ,h , κ, h)) + O(ε) ≥ 0
(3.26) for every v ∈ U (x (ū,x 0 ) (τ )) and almost every ε and h.

If we take any accumulation point of the right-hand side of (3.26) as ε and h tend to zero, according to (3.20) and (3.22), we get, after division by l:

ξ T Φ ū( t, τ ) f (x (ū,x 0 ) (τ ), v) -f (x (ū,x 0 ) (τ ), ū(τ )) ≥ 0 ∀ξ ∈ ∂g(x (ū,x 0 ) ( t)) (3.27)
Chapter 3. Barriers for Mixed Constraints

Assume for a moment that we can replace v in (3.27) by a continuous family v τ with respect to τ such that lim τ → t v τ = v. This result is proven in Lemma 3.3.2 below. Thus, taking the limit as τ tends to t in (3.27), we get

ξ T f (z, v) -f (z, ū( t) ≥ 0, ∀ξ ∈ ∂g(z), ∀v ∈ U (z) (3.28)
where z = x (ū,x 0 ) ( t). Therefore,

max ξ∈∂g(z) ξ T f (z, ū( t)) = min v∈U (z) max ξ∈∂g(z) ξ T f (z, v). (3.29)
Since the mapping ξ → ξ T f (z, v) is linear on the compact and convex set ∂g(z) and the mapping v → ξ T f (z, v) is convex and continuous on the compact set U (z) which is convex by (A3.5), it results from the minimax theorem of Von Neumann (see e.g. [START_REF] Berge | Topological Spaces[END_REF]) that min

v∈U (z) max ξ∈∂g(z) ξ T f (z, v) = max ξ∈∂g(z) min v∈U (z) ξ T f (z, v). (3. 30
)
If t is not an L-point, it suffices to modify ū on the 0-measure set { t} by replacing ū( t) by its left limit ū( t-) in the latter expression.

We will now show that this expression is equal to 0. On the one hand, because g is locally Lipschitz, Dg exists almost everywhere and the mapping t → g(x (ū,x 0 ) (t)) is nondecreasing on some small interval ( t -η, t] with η > 0 sufficiently small, and we have Dg(x (ū,x 0 ) (t)).f (x (ū,x 0 ) (t), ū( t)) ≥ 0 where Dg exists. Therefore we conclude that g0 (z; f (z, ū( t-))) ≥ 0.

(

On the other hand, by definition, we have:

0 = g(x (uκ,ε,x 0 +εh) (t ε,κ,h )) -g(x (ū,x 0 ) ( t)) ε = g(x (uκ,ε,x 0 +εh) (t ε,κ,h )) -g(x (ū,x 0 ) (t ε,κ,h )) ε + g(x (ū,x 0 ) (t ε,κ,h )) -g(x (ū,x 0 ) ( t)) ε
Thus, since the first bracketed term of the right-hand side has been proven to be ≥ 0, we immediately get lim sup

ε→0 + g(x (ū,x 0 ) ( t)) -g(x (ū,x 0 ) (t ε,κ,h )) ε = lim sup ε→0 + g(x (uκ,ε,x 0 +εh) (t ε,κ,h )) -g(x (ū,x 0 ) (t ε,κ,h )) ε ≥ 0 But, since lim sup ε→0 + g(x (ū,x 0 ) ( t)) -g(x (ū,x 0 ) (t ε,κ,h )) ε = -g 0 (z; f (z, ū( t-)))
we conclude that -g 0 (z; f (z, ū( t-))) ≥ 0. Comparing to (3.31), we get g0 (z; f (z, ū( t-))) = 0, or according to (3.22): 0 = max

ξ∈∂g(z) ξ T f (z, ū( t))
which, together with (3.29) and (3.30), proves (3.23).

If g is differentiable at z, we can apply exactly the same argument as before up until equation (3.26). Thus, letting h → 0 and dividing by l, we get:

Dg(x (ū,x 0 ) (t ε,κ,h )). Φ ū(t ε,κ,h , τ ) f (x (ū,x) (τ ), v) -f (x (ū,x) (τ ), ū(τ )) + O(ε) ≥ 0.
If ε now tends to zero we get

Dg(z)Φ ū( t, τ )f (x (ū,x) (τ ), v) ≥ Dg(z)Φ ū( t, τ )f (x (ū,x) (τ ), ū(τ )), ∀v ∈ U (x (ū,x) (τ )).
We again assume that t is an L-point for the control ū, and construct the same continuous mapping τ → v τ as before, such that lim τ → t v τ = v, for an arbitrary v ∈ U (z) to get:

Dg(z)f (z, v) ≥ Dg(z)f (z, ū( t)), ∀v ∈ U (z)
or, using the Lie derivative notation:

L f g(z, ū( t)) = min v∈U (z) L f g(z, v).
Interpreting L f g(z, ū( t)) as the time derivative of t → g(x (ū,x 0 ) (t)) and remarking that the latter mapping is non decreasing on an interval ] t -η, t], for some η > 0 small enough, we indeed deduce that L f g(z, ū( t)) ≥ 0. The same mapping being non increasing on the interval [ t, t + η [, we have L f g(z, ū( t)) ≤ 0, which finally proves that L f g(z, ū( t)) = 0. If t is not an L-point of ū, the same modification of ū at t, as in the nonsmooth case, may be applied, which achieves to prove the proposition.

Lemma 3.3.2

Under the assumptions of Proposition 3.3.4, for all v ∈ U (z) with z = x (ū,x 0 ) ( t), there exists a continuous mapping

τ → v τ from [ t -η, t[ to U , with η > 0 small enough, such that v τ ∈ U (x (ū,x 0 ) (τ )) for all τ ∈ [ t -η, t[ and lim τ t v τ = v. Proof : Recall that the condition v τ ∈ U (x (ū,x 0 ) (τ )) is equivalent to g(x (ū,x 0 ) (τ ), v τ ) 0 for all τ ∈ [ t -η, t[ and, since z = x (ū,x 0 ) ( t) ∈ G 0 , v ∈ U (z) is such that g(z, v) 0.
We construct such a v τ as follows.

Since, by assumption, #I(z, ū( t-)) = s 1 and #J(ū( t-)) = s 2 , with max(s 1 , s 2 ) > 0, consider the equation

Γ(x, u) =          g i 1 (x, u) . . . g is 1 (x, u) γ j 1 (u) . . . γ js 2 (u)          = 0.
According to assumption (A3.4) and the implicit function theorem, there exists a continuously differentiable mapping: û (û 1 , . . . , ûs 1 +s 2 ) : R n × R m-(s 1 +s 2 ) → R s 1 +s 2 defined in a neighbourhood of the point (z, v s 1 +s 2 +1 , . . . , v m ), labelled N , such that (û(x, v s 1 +s 2 +1 , . . . , u m ), v s 1 +s 2 +1 , . . . , v m ) = v and Γ(x, û(x, u s 1 +s 2 +1 , . . . , u m ), u s 1 +s 2 +1 , . . . , u m ) = 0 ∀(x, u s 1 +s 2 +1 , . . . , u m ) ∈ N .

Then we define

v τ ũ(x (ū,x 0 ) (τ ), v s 1 +s 2 +1 , . . . , v m ) ∀τ ∈ [ t -η, t[
with η small enough such that (x (ū,x 0 ) (τ ), v s 1 +s 2 +1 , . . . , v m ) remains in N in the whole interval [ t -η, t[. Therefore, we have Γ(x (ū,x 0 ) (τ ), v τ ) = 0 for all τ ∈ [ t -η, t[. Moreover, since v τ so defined is clearly a continuous function of τ , and since, by assumption (A.4), η may be possibly decreased in order that

g i (x (ū,x 0 ) (τ ), v τ , v s 1 +s 2 +1 , . . . , v m ) < 0 ∀τ ∈ [ t -η, t[, ∀i ∈ I(z, ū( t-)) and γ j (x (ū,x 0 ) (τ ), v τ , v s 1 +s 2 +1 , . . . , v m ) < 0 ∀τ ∈ [ t -η, t[, ∀j ∈ J(ū( t-))
we have, as required, v τ ∈ U (x (ū,x 0 ) (τ )) and lim τ t v τ = v.

The Barrier Equation

We next present the main result of this section, Theorem 3.4.1, which gives necessary conditions satisfied by an integral curve running along the barrier. This theorem is the mixed constraint analogue of Theorem 2.1.1 and the main differences include:

• The existence of Karush-Kuhn-Tucker multipliers, µ i , i = 1, . . . , p, associated with the mixed constraints that appear in the adjoint dynamics.

• As a result of Proposition 3.3.2, given x 0 ∈ [∂A] -the resulting barrier trajectory may ultimately intersect the set G 0 . In this case, the final condition of the adjoint at the time of this intersection is now given by (3.35).

• The Hamiltonian is now minimised almost everywhere over the set U (x ū(t)), as opposed to being minimised over the set U , as in Theorem 2.1.1.

Theorem 3.4.1

Under the assumptions of Proposition 3.3.2, consider an integral curve x ū on [∂A] -∩ cl(int(A)) and assume that the control function ū is piecewise continuous. Then ū and x ū satisfy the following necessary conditions. There exists a non-zero absolutely continuous adjoint λ ū and piecewise continuous multipliers µ ū i ≥ 0, i = 1, . . . , p, such that:

λū (t) = - ∂f ∂x (x ū(t), ū(t)) T λ ū(t) - p i=1 µ ū i (t) ∂g i ∂x (x ū(t), ū(t)) (3.32)
with the "complementary slackness condition"

µ ū i (t)g i (x ū(t), ū(t)) = 0, i = 1, . . . , p. (3.33)
Moreover, at almost every t, the Hamiltonian, denoted by H(x ū(t), u, λ ū(t)) = (λ ū(t)) T f (x ū(t), u), is minimised over the set U (x ū(t)) and equal to zero:

min u∈U (x ū(t)) λ ū(t) T f (x ū(t), u) = min u∈U λ ū(t) T f (x ū(t), u) + p i=1 µ ū i (t)g i (x ū(t), u) = λ ū(t) T f (x ū(t), ū(t)) = 0 (3.34)
with the following boundary conditions:

3.4. The Barrier Equation 39• If the barrier ultimately intersects G 0 , then at this point the adjoint satisfies

λ ū( t) T ∈ arg max ξ∈∂g(z) ξ.f (z, ū( t)) (3.35)
where z = x ū( t) with t such that z ∈ G 0 , i.e. min u∈U max i=1,...,p g i (z, u) = 0, ∂g(z) being the generalised gradient of g defined by (3.17) at z.

• If the barrier integral curve remains in G -forever the adjoint satisfies the following:

if ∃z ∈ G 0 such that min u∈U (z) max ξ∈∂g(z) ξ.f (z, u) < 0 with t such that z = x ū(t) then min u∈U (z) λ ū(t) T f (z, u) = 0. (3.36)
Remark 2. To compute (3.32) the following necessary conditions are useful:

                   H(x ū(t), ū(t), λ ū(t)) = 0 ∂H ∂u (x ū(t), ū(t), λ ū(t)) + p i=1 µ ū i (t) ∂g i ∂u (x ū(t), ū(t)) + r j=1 ν ū j (t) ∂γ j ∂u (ū(t)) = 0 µ ū i (t)g i (x ū(t), ū(t)) = 0, µ ū i (t) ≥ 0 i = 1, . . . , p ν ū j (t)γ j (ū(t)) = 0, ν ū j (t) ≥ 0 j = 1, . . . , r. (3.37)
Before proving Theorem 3.4.1 we need to introduce the following definition:

Definition 10. The constrained reachable set at time t from initial condition x is given by:

R t (x) {x ∈ R n : ∃u ∈ U s.t. x = x (u,x) (t), g(x (u,x) (s), u(s)) 0 for a.e. s ≤ t} Lemma 3.4.1 Let x ∈ [∂A] -∩ cl(int(A)
) and ū ∈ U as in Proposition 3.3.2, i.e. such that x (ū,x) (t) ∈

[∂A] -for all t ∈ [0, t[ where t is the time such that g(x (ū,x) ( t)) = 0. Then, x (ū,x) (t) ∈ ∂R t (x) for all 0 ≤ t < t.

Proof : We first prove that R t (x) ⊂ cl(A C ) for all 0 ≤ t < t. Assume by contradiction that for some 0 ≤ t < t we have R t (x) ∩ int(A) = ∅. Then ∃u ∈ U such that x (u,x) (t) ∈ int(A) for some 0 ≤ t < t, which contradicts the fact that x ∈

[∂A] -, hence R t (x) ⊂ cl(A C ).
By complementarity int(A) ⊂ R t (x) C , and thus cl(int(A)) ⊂ cl(R t (x) C ). Thus, assume that x ∈ [∂A] -∩cl(int(A)) and that there exists ū ∈ U as in Proposition 3.3.2. Then it can be shown as in the proof of Corollary 3.3.3 that there exists a sequence {x k } k∈N , with x k ∈ int(A), and a sequence {u k } k∈N , u k ∈ U, such that every integral curve x (u k ,x k ) lies in int(A) and the sequence {x (u k ,x k ) } k converges uniformly to x (ū,x) on every compact interval [0, T ]. We therefore immediately deduce that x (ū,x) (t) ∈ [∂A] -∩ cl(int(A)) for all t < t and hence that x (ū,x) (t) ∈ cl(R t (x) C ). But because x (ū,x) (t) ∈ R t (x), and since

∂R t (x) = R t (x) ∩ cl(R t (x) C ), we conclude that x (ū,x) (t) ∈ ∂R t (x).
Proof of Theorem 3.4.1 : By Lemma 3.4.1 we know that x (ū,x) (t) ∈ ∂R t (x) for all 0 ≤ t < t. Therefore, according to Theorem B.2.1, we know that ū must satisfy (B.13). Then, setting λ ū = -η ū we get (3.32) with (3.33) and that the resulting dualised Hamiltonian H(x, u, λ, µ) H(x, u, -η, µ), defined by (B.12), now must be minimised.

If x (ū,x) ultimately intersects G 0 , taking the final conditions for λ ū as in Proposition 3.3.4, namely (3.23), we immediately deduce that at time t the minimised Hamiltonian must be zero, and thus the constant of (B.13) is equal to zero. Let us look at the case where there exists a point z = x x(t) ∈ G 0 such that min u∈U (z) max ξ∈∂g(z) ξ.f (z, u) < 0 but where x (ū,x) remains in G -for all t > t. We have that x (ū,x) (t) ∈ ∂R t (z) and that R t (z) is tangent to the barrier for all t > t. We can conclude that λ(t) = -η(t), where η is as defined in Appendix B, is the inner normal to a separating hyperplane that contains the elementary perturbation cone K t , as defined in Appendix B, such that min

u∈U (x (ū,x) (t))
λ ū(t) T f (x (ū,x) (t)) = 0 for all t ≥ t. We can thus conclude (3.36).

Finally, according to the complementary slackness condition, (B.11), the minimisation of H becomes equivalent to (3.34) which achieves the proof of the theorem.

Examples

Constrained Spring 1

Consider the following constrained mass-spring-damper model:

ẋ1 ẋ2 = 0 1 -2 -2 x 1 x 2 + 0 1 u, |u| ≤ 1, x 2 -u ≤ 0
where x 1 is the mass's displacement. The spring stiffness is here equal to 2 for a mass equal to 1 and the friction coefficient is equal to 2. u is the force applied to the mass. We identify g(x, u) = x 2 -u, U = [-1, 1] and g(x) = x 2 -1. We also identify the following sets:

G = {x ∈ R 2 : x 2 ≤ 1}, G 0 = {x ∈ G : x 2 = 1} and U (x) = {u ∈ U : x 2 ≤ u ≤ 1}. Note that if z (z 1 , z 2 ) ∈ G 0 , i.e. z 2 = 1, then U (z) is the singleton U (z) = {1}.
We have ∂g(z) = {(0, 1) T } = Dg(z) T (which means that g is differentiable everywhere) and the ultimate tangentiality condition reads:

min u∈U (z) Dg(z) T f (z, u) = 0 which gives min u∈U (z) -2z 1 -2z 2 + u = -2z 1 -2 + 1 = 0
Thus z = (-1 2 , 1). Let us now compute λ( t). From (3.35), which here reduces to (3.24), we get that λ( t) = Dg(z) = (0, 1).

We now construct the barrier by integrating backwards from z and λ( t). From the minimisation of the Hamiltonian, H(x, λ, u) = λ 1 x 2 +λ 2 (-2x 1 -2x 2 +u), condition (3.34), we find that the control ū associated with the barrier is given by min

x 2 ≤u≤1 λ 1 x 2 + λ 2 (-2x 1 -2x 2 + u) = 0 which gives: if λ 2 (t) < 0 ū(t) = 1 if λ 2 (t) > 0 ū(t) = x 2 if x 2 ∈] -1, 1] -1 if x 2 ∈] -∞, -1] if λ 2 (t) = 0 ū(t) = arbitrary
We note from condition (3.32) that if the constraint is active (i.e. g(x, u) = 0), the adjoint differential equation is given by λū = -∂f ∂x

T λ ū -µ ū ∂g ∂x = 0 2 -1 2 λ ū -µ ū 0 1
and is otherwise (when g(x, u) < 0) given by λū = -∂f ∂x

T λ ū = 0 2 -1 2 λ ū. (3.38)
Recall that λ 2 ( t) > 0 and x 2 ( t) > 0. Therefore, because λ and x are continuous, ū(t) = x 2 (t) over an interval before t. We can show that ū(t) = 1 over this interval: if x 2 = 1 and u = 1 over an interval before t, then we get ẋ2 = -2x 1 -2 + 1 = 0 or x 1 = -1 2 which implies ẋ1 = 0 for all t ∈] t -η, t], η > 0. However, we would also have ẋ1 = 1 over t ∈] t -η, t], which contradicts the fact that ẋ1 = 0 over this interval.

Therefore, only the constraint g is active over an interval before t, and by (3.37), we obtain µ over this interval:

∂H ∂u + µ ∂g ∂u = λ 2 -µ = 0
and thus λ 2 = µ. In addition the adjoint satisfies:

λ = 0 2 -1 1 λ, ∀t ∈] t -η, t] (3.39)
At some point in time before t, let us label this point t, we have λ 2 ( t) = 0 and it can be verified that, at this time, x 2 ( t) = 0 and λ 1 ( t) < 0. Let us prove that λ 2 is negative on the interval [0, t]. If λ 2 vanishes at some point in time, since we have λ2 = 2λ 1 = 0 then λ ≡ 0 which contradicts our assertion. We conclude that over [0, t], λ 2 is either everywhere positive or everywhere negative.

If over this interval before t λ 2 > 0, then the co-state dynamics are as before, and λ2 < 0 which is equivalent to -λ 1 + λ 2 < 0, but this contradicts the fact that λ 1 ( t) < 0. We can conclude that λ 2 is negative before t, and that ū = 1 over this period. The adjoint dynamics are then given by (3.38). The sign of λ 2 then remains negative until the trajectory intersects G 0 again. The barrier is shown in Figure 3.2.

Note that Assumption (A3.4) does not hold true at the final point z since there are two active constraints for only one control. However, we can argue by the continuity of the set-valued mapping x → U (x) at the point z that condition (3.35) still holds.

To elaborate, note that lim x→z U (x) = U (z), this limit being taken over the set {x : x 2 < 1}. We can thus conclude that there exists a continuous mapping τ → v τ , as specified in Lemma 3.3.2, which is required to arrive at the conclusions of Proposition 3.3.4. See Figure 3.3 for further clarification.

Constrained Spring 2

Consider the same mass-spring-damper system with the same constants as in the previous example, but with a richer constraint: We identify g(x) = x 2 2 -|x 2 |, and G 0 = {x : x 2 = 0 ∪ x 2 = ±1}. g is differentiable for x 2 = 0 and from (3.34) and (3.35) we identify, in same manner as in the previous example, two points of ultimate tangentiality, namely z = (-1 2 , 1) along with λ( t) = (0, 1), and z = ( 12 , -1) along with λ( t) = (0, -1). We defer the treatment of the x 1 axis, which is also in G 0 , to the discussion below.

ẋ1 ẋ2 = 0 1 -2 -2 x 1 x 2 + 0 1 u, |u| ≤ 1, x 2 (x 2 -u) ≤ 0 (3.40)
From the minimisation of the Hamiltonian, which is the same as in the previous example, we find the control ū:

if λ 2 (t) < 0 ū(t) = 1 if x 2 ∈]0, 1] x 2 if x 2 ∈] -1, 0[ if λ 2 (t) > 0 ū(t) = x 2 if x 2 ∈]0, 1] -1 if x 2 ∈] -1, 0[ if λ 2 (t) = 0 ū(t) = arbitrary
If we now integrate backwards from the points (-1 2 , 1) and ( 12 , -1) with the control ū(t) we obtain the barrier as in Figure 3.4. It turns out that along both curves ū(t) = x 2 (t).

Let us now turn to the x 1 axis, where g = x 2 2 -|x 2 | is non differentiable. For any z on the x 1 axis, we have

U (z) = [-1, 1] and ∂g(z) = co (0, -1) T , (0, 1) T = {0} × [-1, 1]
max ξ∈∂g(z) ξ.f (z, u) = 0 = min u∈[-1,1] max ξ 2 ∈[-1,1] ξ 2 (-2x 1 + u) (3.41)
For each -1 2 ≤ z 1 ≤ 1 2 equation (3.41) has a solution given by ξ = (0, sign(-2z 1 + u)) from which we deduce that ū = 2z 1 . However, one can directly verify that the integral curves of (3.40) with endpoints in the set [-1 2 , 1 2 ] × {0} with the control u = x 2 all correspond to admissible curves (integrated backwards) and therefore do not belong to the barrier, but that they make the constraint g(x (ū,x) (t), ū(t)) equal to 0 for ū = x 2 for all x ∈ [-1 2 , 1 2 ] × {0} and for all t. This attests that our conditions are only necessary and far from being sufficient.

Remark 5. Note that, as in Example 3.5.1, Assumption (A3.4) does not hold true at the final points z ∈ G 0 since there are two active constraints for only one control. Again, we conclude by continuity that condition (3.35) still holds.

Example Where Barrier Does Not Intersect G 0 Tangentially

The first two examples demonstrated the construction of barriers that intersect the set G 0 tangentially. We next cover an example of where this does not occur, i.e. the barrier remains in G -for all time. Note that this phenomenon can not exist in the case of pure state constraints; due to the mixed constraints the set U (x) depends on x and can be empty in some part of the state space. Consider the double integrator: Dg(z).f (z, u) = z 2 = 0, which gives z (z 1 , z 2 ) = (1, 0). We derive the control associated with the barrier from:

ẋ1 = x 2 ẋ2 = u (3.42)
min u∈U (x) λ 1 x 2 + λ 2 u = 0, a.e. t which gives: if λ 2 (t) < 0 ū(t) = 1 if x 1 ∈]∞, 1] if λ 2 (t) > 0 ū(t) = x 1 if x 1 ∈ [-1, 1] -1 if x 1 ∈] -∞, -1[ if λ 2 (t) = 0 ū(t) = arbitrary.
The adjoint equations are given by: λ = 0 0 -1 0 λ with λ( t) = Dg(z) = (1, 0) T . From here we deduce that λ 2 (t) = -t + t for all t ∈ (-∞, t], and thus λ 2 (t) > 0 for all t ∈ (-∞, t]. If we integrate backwards from the point z = (1, 0) we find that the integral curve immediately leaves the constrained state space, and so this curve cannot be part of the barrier. However, let us show that the barrier does indeed exist and that it remains in G -for all time.

We will frequently refer to the following analytic solution of (3.42) given by the control û(t) = x 1 (t) initiating at t = 0 from x 0 = x(0) (x 1 (0), x 2 (0)):

x (û,x 0 ) 1 (t) = x 1 (0) + x 2 (0) 2 e t + x 1 (0) -x 2 (0) 2 e -t x (û,x 0 ) 2 (t) = x 1 (0) + x 2 (0) 2 e t + x 2 (0) -x 1 (0) 2 e -t .
With this control the origin is a saddle point. Proposition 3.5.1

The set B = {(x 1 , x 2 ) :

x 2 > -x 1 , x 1 ≤ 1} is a subset of A c .
Proof : From the mixed constraint we have that u(t) ≥ x 1 (t), which implies t 0 u(σ) ≥ t 0 x 1 (σ). Thus:

x (u,x 0 ) 1 (t) = x 1 (0) + x 2 (0)t + t 0 t 0 u(σ)dσdτ, ∀t ∈ [0, ∞) (3.43) ≥ x 1 (0) + x 2 (0)t + t 0 t 0 x 1 (σ)dσdτ, ∀t ∈ [0, ∞) (3.44) But x 1 (0) + x 2 (0)t + t 0 t 0 x 1 (σ)dσdτ = x 1 (0)+x 2 (0) 2 e t + x 1 (0)-x 2 (0)
2 e -t . Thus, for any admissible u,

x (u,x 0 ) 1 (t) ≥ x 1 (0) + x 2 (0) 2 e t + x 1 (0) -x 2 (0) 2 e -t , ∀t ∈ [0, ∞).
If we consider the limit as t → ∞, we see that x (u,x 0 ) 1 (t) → ∞. Therefore, if the system initiates in the set B then for any admissible u there exists t u,x 0 ≥ 0 such that x (u,x 0 ) 1 (t u,x 0 ) > 1. Therefore, for any x 0 ∈ B, we have min u∈U ess. sup t∈[0,∞) g(x (u,x 0 ) , u(t)) > 0, which by Proposition 3.3.1 implies x 0 ∈ A C , which completes the proof.

Proposition 3.5.2

The set L = {(x 1 , x 2 ) :

x 2 = -x 1 , x 1 ≤ 1, x 1 ≥ -1} is a subset of [∂A] -. Proof : For any x 0 ∈ L employing û(t) = x 1 (t) gives x (û,x 0 ) 1 (t) = x 1 (0)e -t and x (û,x 0 ) 2 (t) = -x 1 (0)e -t
. Thus the solution remains on L and asymptotically approaches the origin. Moreover, g(x (û,x 0 ) (t), û(t)) = 0 for all t. Let l(x) {x : x 2 + x 1 = 0}. Recalling from the mixed constraint that u(t) ≥ x 1 (t), if we thus employ any other control specified by:

u(t) = x 1 (t) t / ∈]t 1 , t 1 + ε[ v > x 1 (t) t ∈]t 1 , t 1 + ε[ we get: Dl(x (u,x 0 ) (t)).f (x (u,x 0 ) (t), u(t)) = x (u,x 0 ) 2 (t) + u(t) > -x (u,x 0 ) 1 (t) + x (u,x 0 ) 1 (t) = 0.
Therefore, any other control results in the state leaving L and entering B ⊂ A c . Therefore, for any x 0 ∈ L, min u∈U ess. sup t∈[0,∞) g(x (u,x 0 ) , u(t)) = 0, which again by Proposition 3.3.1 implies that x 0 ∈ ∂A. Since L ⊂ G -, L ⊂ [∂A] -which completes the proof.

We now prove that the barrier extends as in Figure 3.5 from the point (x 1 , x 2 ) = (-1, 1), being constructed backwards by the control ū(t) ≡ -1 for all t ∈] -∞, t], where x ū is the backward extension of the barrier and x ū( t) = (-1, 1). By Lemma 3.4.1 we can say that any trajectory running along the barrier still satisfies the Pontryagin maximum principle and in particular that the Hamiltonian is minimised and constant for almost all time.

Starting from L we have proven that employing û we remain on L. The reachable set from any point of L is tangent to L according to Lemma 3.4.1 and its adjoint η ū is normal to L. Hence,

λ ū = -η ū satisfies min u∈U (x ū(t)) λ ū(t) T f (x ū(t), u) = 0, a.e. t.
We have that the point (-1, 1) ∈ [∂A] -and so in order to further construct the barrier we need only identify the adjoint at this point. Seeing as though at this point the vector field given by the control û, associated with the barrier, is f (x û( t), û( t)) = (1, -1), we can deduce that λ( t) = k(1, 1), k a positive constant. Recall that the adjoint equations are given by:

λ = 0 0 -1 0 λ, λ( t) = k(1, 1)
from which we deduce that λ

1 (t) ≡ k and λ 2 (t) = -k(t -t) + k, t ∈ (-∞, t].
The Hamiltonian minimisation almost everywhere gives:

ū(t) = -sign(λ 2 (t)) ≡ -1.
Using this information we can extend the barrier further backwards as in Figure 3.5. We have also included a few of the vectograms along the extension of the barrier in order to emphasise that this is indeed an "extremal" trajectory and that as we approach the point (-1, 1), the vectogram points towards the set B, which we have shown to be a subset of A C .

Introduction

The previous sections have provided us with necessary conditions that are satisfied by a trajectory that runs along the barrier for problems with pure state or mixed constraints. We have already seen examples of where a trajectory obtained via backward integration leaves the constrained state-space, and it is clear that the barrier "stops": further prolongation of the curve is outside G (as defined in either the pure state or mixed constraint setting) and so it cannot be part of the barrier.

There are also examples of where these trajectories, obtained via backward integration, intersect with each other and where their further prolongations are in the interior of A. At these points the barrier also "stops". Interestingly, Isaacs observed an analogous phenomenon in the context of differential games [START_REF] Isaacs | Differential Games[END_REF], and noted, without explanation, that it is "possible for a semipermeable surface to come to an abrupt end". He then demonstrated this on a number of examples.

In our context of constrained nonlinear systems we call these points stopping points, and in this chapter we present a theorem that states that every transversal intersection point of trajectories that run along the barrier is a stopping point. The work in this section has been published in [START_REF] Esterhuizen | A preliminary study of barrier stopping points in constrained nonlinear systems[END_REF].

Motivating Example: Nonholonomic Vehicle

Let us consider the system: ẋ = cos θ ẏ = sin θ θ = u |u| ≤ 1 with constraint g(x, y, θ) = x -1. This is a simple model of a nonholonomic vehicle of unit length moving at constant unit speed where the front wheels can instantaneously change their angle. The pair (x, y) denotes the coordinates of the middle of the rear axle and θ is the angle the car makes with the x-axis, [START_REF] Dubins | On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents[END_REF], see Figure 4.1. The constraint may be interpreted as a wall located at x = 1 to be avoided.

Let us find the barrier: the co-state at tangential arrival is given by (2.9): λ( t) = [g x , g y , g θ ] T = [1, 0, 0] T . The Hamiltonian minimisation for almost all t ≤ t gives:

min |u|≤1 {λ 1 cos θ + λ 2 sin θ + λ 3 u} = 0 (4.1) i.e. ū(t) =        1 -1 arbitrary λ 3 (t) < 0 λ 3 (t) > 0 λ 3 (t) = 0
The co-state is given by: For any initial condition (x 0 , y 0 , θ 0 ) with x 0 < 0 (the initial orientation has been indicated with an arrow on the car) there exists a control such that the solution traces out a unit circle in the (x, y) space that is completely contained in {(x, y, θ) : x < 1} i.e. λ 1 (t) ≡ 1; λ 2 (t) ≡ 0 and therefore, λ3 (t) = sin θ(t).

λ =    0 0 0 0 0 0 sin θ -cos θ 0    λ
From equation (4.1) at the final time t, θ( t) = ± π 2 , and we also have x( t) = 1 and y( t) is free. To show that λ 3 only vanishes at isolated points in time before t, suppose that λ 3 (t) = 0 over some interval before t. Then θ(t) = 0 ± kπ, k an integer, over this same interval, but θ( t) = ± π 2 and we thus have arrived at a contradiction. If θ( t) = π 2 and λ 3 (t) > 0 over ] t -η, t] with η > 0 and sufficiently small, then over this interval λ3 (t) < 0 which implies that sin θ(t) < 0. This in turn implies that θ(t) / ∈] π 2 -ν, π 2 + ν[ for ν > 0 and sufficiently small, which leads to a contradiction because θ( t) = π 2 and θ is continuous. We thus conclude that over an interval before arriving tangentially with θ( t) = π 2 , we have ū(t) = 1. Similarly, we conclude that ū(t) = -1 over an interval before arriving with θ( t) = -π 2 . For the interval [ t -π, t] we can easily compute the analytic solutions: for a curve ending at [x( t),

y( t), θ( t)] T = [1, y 1 , -π 2 ] T , we get x(t) = cos(t -t); y(t) = -sin(t -t) + y 1 ; θ(t) = -(t -t) -π
2 and for a curve ending at [x( t),

y( t), θ( t)] T = [1, y 1 , π 2 ] T , we get x(t) = cos(t -t); y(t) = sin(t -t) + y 2 ; θ(t) = t -t + π
2 . These curves are helices in the (x, y, θ) space and intersect when t = tπ 2 (i.e. when x(t) = 0) and y 2 -y 1 = 2. Because y( t) is free, we can see that any point on the y-axis is the intersection point of two trajectories that run along the barrier.

In fact, we can argue that any initial condition (x 0 , y 0 , θ 0 ) with x 0 < 0 is in the interior of A: note that with u ≡ 1 or u ≡ -1 we get, from the analytic solutions above, that the car would trace out unit circles in the (x, y) plane with centre (x 0 ± sin(θ 0 ), y 0 ∓ cos(θ 0 )). At least one of these circles is contained in the set {(x, y, θ) : x < 1}, see Figure 4.2, and we can conclude that for any initial condition with x 0 < 0 there exists a solution such that the constraints are satisfied for all time.

Returning to finding the barrier via backward integration, we can see that once we reach the y-axis we need to stop: any further prolongation is inside A. In the next section Chapter 4. Stopping Points we provide a rigorous treatment of the stopping point phenomenon.

Rigorous Treatment

We assume in the remainder of this chapter that |I(z)| = 1 for all z ∈ G 0 , where |A| denotes the cardinality of a set A. Thus the mapping z → I(z) is piecewise constant on G 0 and it may be seen that the barrier [∂A] -is a piecewise (n -1) dimensional manifold which is the envelope of backward integrated trajectories given by Theorem 2.1.1 or Theorem 3.4.1. Several cases of stopping points are possible, among which are:

• the barrier is made of maximal integral curves obtained from Theorem 2.1.1 or Theorem 3.4.1 by backward integration, that stop in finite time 1 . In this case we call the corresponding end-point a barrier stopping point.

• two or more distinct integral curves obtained as before intersect at a point, some arcs of these curves not forming part of the barrier. Such a point corresponds to a barrier stopping point by intersection. See the Definition 11.

• an integral curve obtained as before may intersect with itself at a later time, some arcs of this curve not forming part of the barrier. This corresponds to a barrier stopping point by self-intersection. If t1 and t2 are the distinct times at which this integral curve passes through the point ξ, then this case is possible if f (ξ, ū( t1 )) = f (ξ, ū( t2 )), where ū satisfies the Hamiltonian minimisation conditions (2.10) or (3.34).

We now give precise definitions of these stopping point phenomena.

Definition 11 (Stopping Point).

(i) Consider two distinct integral curves x (u 1 ,z 1 ) and x (u2 ,z 2 ) obtained from Theorem 2.1.1 or Theorem 3.4.1 by backward integration, running along the barrier [∂A] -from two distinct points z 1 , z 2 ∈ G 0 at t1 and t2 respectively, i.e.

x (u i ,z i ) ( ti ) = z i , i = 1, 2,
where u i is the corresponding control function that satisfies condition (2.10) or (3.34) for almost all t ≤ ti , i = 1, 2. Assume that there exists a point of transversal 2 intersection ξ of these two curves at some time labeled t. ξ is said to be a barrier stopping point by intersection either if the two maximal integral curves stop at ξ,

or if x (u i ,z i ) (t) ∈ int(A), i = 1, 2, for all t < t, whereas x (u i ,z i ) (t) ∈ [∂A] -for all t ∈ [ t, ti ], i = 1, 2.
(ii) Consider an integral curve x (u,z) obtained from Theorem 2.1.1 or Theorem 3.4.1 by backward integration, running along the barrier [∂A] -from a point z ∈ G 0 at t, i.e. x (u,z) ( t) = z, where u is the corresponding control function that satisfies condition (2.10) or (3.34) for almost all t ≤ t. Assume that there exist times t1 and t2 , with t1 < t2 , such that ξ = x (u,z) ( t1 ) = x (u,z) ( t2 ) with f (ξ, u( t1 )) and f (ξ, u( t2 )) independent. ξ is said to be a barrier stopping point by self-intersection if x (u,z) (t) ∈ int(A), for all t < t2 , whereas

x (u,z) (t) ∈ [∂A] -for all t ∈ [ t2 , t].
The next theorem states that all points where integral curves intersect with one another or with themselves are stopping points. The adjoint dynamics are given by:

λ1 = 0 λ2 = 2x 2 λ 1 (4.3)
According to the Hamiltonian minimisation condition we must have

min u∈[-1,1] {λ 1 (1 -x 2 2 ) + λ 2 u} = 0, which gives u(t) = -sign(λ 2 ).
In [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] it was shown that integral curves ending at (3, 1) and (-1, -1) have the associated control ū(t) ≡ 1 and that integral curves ending at (3, -1) and (-1, 1) have the associated control ū(t) ≡ -1, see Figure 4.5. Moreover, the curves ending at (3, 1) and (3, -1) intersect at the point ξ (2 + 1 3 , 0) and by Theorem 4.2.1 we can conclude that it is a stopping point by intersection.

Back to Nonholonomic Vehicle

Let us again consider the nonholonomic vehicle problem from section 4, where we have shown that the trajectories on the barrier are helices in the (x, y, θ) space. These backwards integrated trajectories, each of which initiates from a different y coordinate, run along two manifolds that intersect on the y-axis, which we denote by S, see Figure 4.6. By Theorem 4.2.1 we can conclude that all points ξ ∈ S are stopping points by intersection.

We can interpret the result as follows: the car is allowed to do what it pleases, unless it comes too close to the wall (x > 0). If x > 0 and the car is not oriented appropriately, then it is guaranteed to hit the wall regardless of control chosen. This corresponds to being in the set A c .

For a certain distance close to the wall (0 < x < 1) there are two orientations of the car along with appropriate controls (u = ±1) that guarantee that it will arrive tangentially to the wall, and any other control will result in collision. This corresponds to being on the barrier, [∂A] -.

The line S of stopping points are special points on the barrier. From here, the car can choose between two different controls that will guarantee tangential arrival to the wall. Notre but dans ce chapitre est d'obtenir l'ensemble des conditions initiales pour lesquelles il est possible d'employer un contrôle tel que le câble reste tendu. Bien que les conditions pour la construction de la barriére ne soient pas réunies, on utilise une méthode de convergence pour obtenir cette dernière ce qui permet de déduire l'ensemble admissible. Puis, on montre qu'on peut interpréter ces résultats en termes de système hybride et d'ensemble potentiellement sûr.

Introduction

In this chapter we study a pendulum on a cart with a non-rigid cable. Our goal is to find the set of initial conditions for which it is possible to employ a control such that the cable never goes slack. In the first section we do the complete analysis and then carry out a brief discussion in Section 5.2 where we show that this system can be modelled as a hybrid system and that the obtained admissible set may be interpreted as a potentially safe set.

Admissible set for the Pendulum on a Cart with

Non-Rigid Cable

Modelling of the System

We consider the classic pendulum on a cart, see Figure 5.1, but replace the rigid rod with a massless cable that may go slack. The control, u, assumed to be bounded, is the force applied to the cart of mass M kg, θ denotes the angle in radians the cable makes with the vertical, m is the mass in kg at the end of the cable, l is the length in meters of Chapter 5. An Application to Potentially Safe Sets in Hybrid Systems: Pendulum on a Cart with Non-Rigid Cable - Without loss of generality we will only carry out the analysis on G 0 for θ 1 ∈ [-arctan(M g), arctan(M g)].

Invoking the ultimate tangentiality condition on G 0 for θ 1 ∈ [-arctan(M g), 0[, we obtain:

min u∈U (θ) D h(θ).f (θ, u) = min u∈{1} (cos θ 1 -M g sin θ 1 , -2M lθ 2 ).( θ1 , θ2 ) T = 0 (5.9)
where we note that U (θ) = {1} for θ 1 in this range. The expression becomes

(cos θ 1 -M g sin θ 1 ) θ 2 -2M lθ 2 cos θ 1 -(M + m)gsinθ 1 + mlθ 2 2 cos θ 1 sin θ 1 -l (M + m sin 2 (θ 1 )) = 0
from where we immediately identify the point (-arctan(M g), 0) as a point of ultimate tangentiality. Let us show that (5.9) does not have another solution for any θ 1 ∈ [-arctan(M g), 0[. Indeed, we must investigate:

(cos θ 1 -M g sin θ 1 ) -2M l cos θ 1 -(M + m)gsinθ 1 + ml sin θ 1 +M g cos θ 1 M l cos θ 1 sin θ 1 -l (M + m sin 2 (θ 1 )) = 0
where we have substituted θ 2 2 using h(θ) = 0. Multiplying by -l (M + m sin 2 (θ 1 )), after some algebra we get: Noting that m cos 3 θ 1 -m cos θ 1 = -m cos θ 1 sin 2 θ 1 , the above expression becomes:

-3M cos θ 1 -3M mg sin θ 1 cos 2 θ 1 + 3M 2 g sin θ 1 + 3M mg sin θ 1 +m cos 3 θ 1 -m cos θ 1 -2m sin 2 θ 1 cos θ 1 = 0.
-M cos θ 1 -M mg sin θ 1 cos 2 θ 1 + M 2 g sin θ 1 + M mg sin θ 1 -sin 2 θ 1 (m cos θ 1 ) = 0
and after grouping terms we get:

-cos θ 1 M + m sin 2 θ 1 + M g sin θ 1 M + m sin 2 θ 1 = 0.
The expression (M + m sin 2 θ 1 ) > 0, thus we get θ 1 = arctan( 1 M g ) / ∈ [-arctan(M g), 0[, and so there is not another solution for θ 1 ∈ [-arctan(M g), 0[. Along the same lines we deduce that (arctan(M g), 0) is the only point of ultimate tangentiality on G 0 for all θ 1 ∈]0, arctan( 1 M g )]. By constructing the barrier from (± arctan(M g) + 2πk, 0) we will show that these points cannot be the only points of ultimate tangentiality. This fact will motivate a close inspection of the points (0, ± g l + 2πk) where h is not differentiable. We concentrate on the point θ ( θ1 , θ2 ) = (-arctan(M g), 0); the analysis will carry over to the points (± arctan(M g) + 2kπ, 0) in a similar way. The Hamiltonian is given by:

H(θ, x, u, λ) = λ 1 θ 2 +λ 2 u cos(θ 1 ) -(M + m)g sin(θ 1 ) + mlθ 2 2 cos(θ 1 ) sin(θ 1 ) -l (M + m sin 2 (θ 1 )) +λ 3 ẋ1 +λ 4 ẋ2
and the adjoint equations are given by:

λ(t) =       0 -∂f 2 ∂θ 1 0 -∂f 4 ∂θ 1 -1 -∂f 2 ∂θ 2 0 -∂f 4 ∂θ 2 0 0 0 0 0 0 1 0       λ(t) -µ(t)      u cos θ 1 -M g sin θ 1 -2M lθ 2 0 0      . ( 5.10)
From (3.37) we have that µ satisfies:

∂H ∂u + µ ∂h ∂u = 0
which is equivalent to:

λ 2 cos θ 1 -l (M + m sin 2 (θ 1 )) + µ sin θ 1 = 0
and so:

µ(t) =    λ 2 (t) cot θ 1 (t) l(M +m sin 2 (θ 1 )) if h(θ(t), u(t)) = 0 0 if h(θ(t), u(t)) < 0.
The final conditions of the adjoint are given by

λ( t) = D h( θ) T = (cos θ1 -M g sin θ1 , -2M l θ2 , 0, 0) T
and from here we deduce that λ 4 (t) = λ 3 (t) ≡ 0. The Hamiltonian minimisation condition gives:

min u∈U (θ) λ 1 θ 2 + λ 2 u cos(θ 1 ) -(M + m)g sin(θ 1 ) + mlθ 2 2 cos(θ 1 ) sin(θ 1 ) -l (M + m sin 2 (θ 1 )) = 0 62
Chapter 5. An Application to Potentially Safe Sets in Hybrid Systems: Pendulum on a Cart with Non-Rigid Cable and so, because -l (M + m sin 2 (θ 1 )) < 0, the control is given by:

if λ 2 (t) cos θ 1 (t) > 0 ū(t) =    1 if sin θ 1 (t) ≤ 0 min M lθ 2 2 (t)-M g cos θ 1 (t) sin θ 1 (t) , 1 if sin θ 1 (t) > 0 if λ 2 (t) cos θ 1 (t) < 0 ū(t) =    -1 if sin θ 1 (t) ≥ 0 max M lθ 2 2 (t)-M g cos θ 1 (t) sin θ 1 (t) , -1 if sin θ 1 (t) < 0 if λ 2 (t) cos θ 1 (t) = 0 ū(t) = arbitrary.
If we use the information and integrate backwards from the points (± arctan(M g) + 2πk, 0) we get the trajectories as in Figure 5.3. Looking at the integral curve arriving at (-arctan(M g), 0) we see that A C must be to the right of the obtained curve and the interior of A must be to its left, as indicated in the figure. However, further backwards along the curve it becomes clear that the part to the right of this curve is also to the left of the curve terminating at (-arctan(M g) + 2π, 0). Clearly there is a contradiction with regards to the orientation of the obtained barrier, and parts of it must be missing. We conclude that if there is another barrier trajectory ultimately intersecting G 0 , then it must intersect the points (0, ± g l + 2kπ), where h is not differentiable. Turning our attention to the point (0, g l ) (the analysis carries over to all the points (0, ± g l + 2kπ) in a similar way), we see that h((0, g l ), u) = 0 for all u ∈ [-1, 1] and the regularity assumption (A3.4) does not hold true. Therefore, we cannot deduce the existence of the continuous mapping as described in Lemma 3.3.2 which is required to prove the ultimate tangentiality condition, Proposition 3.3.4. Moreover, the analysis is made considerably more complicated by the fact that the set-valued mapping x → U (x) is not continuous at these points, as illustrated in Figure 5.4, and so we cannot use arguments similar to those in Examples 3.5.1 and 3.5.2 to deduce that the point (0, g l ) is still an ultimate tangentiality point. Nonetheless, we will show that this point is still on the barrier by considering the limit of the set U (θ(t)) along specific directions.

Consider a barrier trajectory θ (ū,θ 0 ) with θ (ū,θ 0 ) (0) = θ 0 ∈ [∂A] -and assume that it intersects the point (0, g l ) at some future time, i.e. θ (ū,θ 0 ) ( t) = (0, g l ), t > 0. Referring to the partition of the state space as in Figure 5.4, define the sets:

D - θ : θ 1 < 0, M lθ 2 2 -M g cos θ 1 sin θ 1 ≥ -1, h(θ) ≤ 0 D + θ : θ 1 > 0, M lθ 2 2 -M g cos θ 1 sin θ 1 ≤ 1, h(θ) ≤ 0 C - θ : θ 1 < 0, M lθ 2 2 -M g cos θ 1 sin θ 1 < -1, h(θ) ≤ 0 C + θ : θ 1 > 0, M lθ 2 2 -M g cos θ 1 sin θ 1 > 1, h(θ) ≤ 0
we will show that a barrier trajectory intersecting the point (0, g l ) must arrive from the set labelled D -. The admissible set for the pendulum on a cart with a slack rope, equations (5.6), with the constraint that the tension in the cable is always nonnegative. The constants in this case are: g = 10m/s 2 , l = 1 metre, M = 0.1 kg, m = 0.1 kg. Note that the obtained barrier trajectories intersect at stopping points.

Discussion

The physical interpretation of the results is clear: if θ is such that h(θ) ≥ 0 then the angular velocity of the mass is too small to ensure positive tension in the cable, and the mass enters free-fall. If θ ∈ A C then no admissible control function can prevent a loss of tension in the future. At the ultimate tangentiality points θ = (± arctan(M g) + 2kπ, 0), k an integer, the angular velocity of the mass is zero and because h( θ) = 0 the tension in the cable is zero and the mass is in free-fall. However, employing the only admissible control at this point (i.e. u = ±1 depending on the point) results in the state immediately entering the admissible set and the tension can be made positive again. As is intuitively expected, for the same bound on the input force the final angle θ1 = ± arctan(M g) + 2kπ increases with an increase in the mass of the cart.

At the singular points (2kπ, ± g l ), k an integer, the control acts perpendicularly to the cable and so does not have any effect on the tension. This is why the set of admissible controls at these points is {u : u ∈ [-1, 1]} and why the analysis is so difficult. The barrier trajectory that passes through the points (2kπ, ± g l ) is quite interesting. Along the entire part of the trajectory for which ū = M lθ 2 2 -M g cos θ 1 sin θ 1 the mass is in fact in free-fall: recall that equation (5.16) is equivalent to d 2 dt 2 (l cos θ) = z = -g, and the solution is only defined on the interval t -2 l g , t + 2 l g because |z| ≤ l. As remarked earlier, studying the system (5.6) with constraint (5.7) can be interpreted as studying a pendulum on a cart with a rigid bar and requiring the tension to never be strictly negative. We are thus assured that along the barrier trajectory where ū = M lθ 2 2 -M g cos θ 1 sin θ 1 the cable does not go slack. Upon the barrier's arrival at the points (0, ± g l ) it is again possible to employ a control such the state enters the admissible set and the tension in the cable can be made positive.

It is interesting to note how the admissible set is dependent on the problem's constants. For those as specified in Figure 5.5, the admissible set consists of a periodic sequence of disjoint connected components. This has the interesting interpretation that if the system is initiated in the bounded connected component of the admissible set (i.e. the part at low angular speeds) then it is impossible to increase the angular velocity beyond a certain bound without leaving the admissible set. However, if the system is initiated with a high enough angular speed one can "spin" the mass through the full range of angles, i.e. through all θ ∈ R, always maintaining a taut cable. In fact, if one initiates with these high velocities one would always need to manoeuvre the mass in this way as it is impossible for the state to pass into the bounded part of the admissible set. Moreover, one can most certainly not change the sense of this "spinning" manoeuvre.

The admissible set obtained in Figure 5.6 permits more freedom with the manoeuvring of the mass. Indeed, because the admissible set is connected, one can for example start with a slow velocity, manoeuvre the mass into a clockwise spinning motion, slow it down and then manoeuvre it into an anticlockwise spinning motion, all the while maintaining a taut cable.

Hybrid Systems and Safety Sets

We now briefly discuss how the pendulum system from the previous section can be modelled as a hybrid system and how the obtained admissible set can be viewed as a type of Chapter 5. An Application to Potentially Safe Sets in Hybrid Systems:

Pendulum on a Cart with Non-Rigid Cable "safety set". Hybrid systems incorporate both continuous and discrete dynamics and can be used to model many systems found in engineering. There exist different frameworks in the literature, see for example [START_REF] Goebel | Hybrid Dynamical Systems: Modeling, Stability, and Robustness[END_REF] and [START_REF] Liberzon | Switching in systems and control. Systems & Control : foundations & applications[END_REF], but we will follow the hybrid automaton approach as expounded in [START_REF] Van Der Schaft | An Introduction to Hybrid Dynamical Systems[END_REF]. We have made small changes to this framework that allows the "guards" and "invariants" to be state and control dependent, and we have enforced the assumption that the dynamics describing the evolution of the continuous state at each location satisfies assumptions (A3.1)-(A3.3).

Definition 12 (Hybrid Automaton)

. A hybrid automaton is described by a tuple (L, X, A, U, E, Inv, Act) where each of the symbols have the following meanings:

• L is called the locations. It is a finite set and forms the vertices of the automaton.

• X ⊂ R n is the continuous state space.

• A is a finite set of symbols that label the edges of the automaton.

• U ⊂ R m is the space in which the continuous control variables u take their values.

• E is called the set of edges. Every element of E is defined by a tuple (l, a, Guard l,l , Jump l,l , l ) where l, l ∈ L, a ∈ A, Guard l,l ⊂ X × U and Jump l,l is a relation defined on a subset of X × X. The meanings of these two last sets will be made clear shortly.

• Inv is a mapping from L to the set of subsets of X × U . If the system is at location l i the continuous state x must satisfy x ∈ Inv(l i ). The subset Inv(l i ) is referred to as the location invariant for location l i .

• Act assigns to each l ∈ L an ordinary differential equation ẋ = f l (x, u), where f l satisfies the assumptions (A3.1)-(A3.3), the solution of which is referred to as the activities of location l.

A continuous trajectory associated with a location l i is specified by the tuple (l i , δ i , x i , u i ), where δ i ∈ R is nonnegative (called the duration of the continuous trajectory), u i is a piecewise continuous function from the interval [0, δ i ] to U and x i is a piecewise differentiable function from [0, δ i ] to X, such that:

• x i (t) ∈ Inv(l i ) for all t ∈]0, δ i [ • x i (t) and u i (t) satisfy ẋi (t) = f l (x i (t), u i (t)) a.e. t ∈]0, δ i [.
A trajectory of the hybrid automaton is an (infinite) sequence of continuous trajectories: .22) such that at the event times

(l 0 , δ 0 , x 0 , u 0 ) a 0 -→ (l 1 , δ 1 , x 1 , u 1 ) a 1 -→ (l 2 , δ 2 , x 2 , u 2 ) a 2 -→ . . . ( 5
t 0 = δ 0 , t 1 = δ 0 + δ 1 , t 2 = δ 0 + δ 1 + δ 2 , . . .
the following holds for all i = 1, 2, . . . :

• (x i (t i ), u i (t i )) ∈ Guard l i ,l i+1 • (x i (t i ), x i+1 (t i )) ∈ Jump l i ,l i+1 .
The behaviour of a hybrid automaton is determined by the events which occur at event times. Initiating at a location l 0 , the continuous state evolves according to the differential equation at that location. When an event occurs the location l 0 transitions to a new location l 1 and the continuous state x jumps instantaneously to a new state x , with (x, x ) ∈ Jump l 0 ,l 1 , and then evolves according to the differential equation at location l 1 . This process continues for all event times. An event may be externally induced or internally induced. An externally induced event comprises the specification of the event time and a symbol a ∈ A. An internally induced event occurs when (x, u) / ∈ Inv(l), i.e. an event must take place when (x, u) / ∈ Inv(l). An event may take place if and only if (x, u) ∈ Guard l,l . Thus, it can be seen that the invariants provide enforcing of switching whereas the guards provide enabling of switching.

Given a hybrid automaton it may be necessary to ensure that the state, described by the pair (l, x) ∈ L × X, never ventures into some known set of undesirable/bad states. Solving this problem usually involves finding a set of initial conditions, in the literature usually referred to as a "safety set", from where it is guaranteed that it is never possible for the state to reach the undesirable states.

The references [START_REF] Lygeros | Controllers for reachability specifications for hybrid systems[END_REF] [63], and [START_REF] Tomlin | Computational techniques for the verification of hybrid systems[END_REF] (already mentioned in Section 2.3.1) apply backwards reachable sets for differential games to the study of safety sets in hybrid systems. Further references on the subject include [START_REF] Dang | Verification and Synthesis of Hybrid Systems[END_REF], [START_REF] Girard | Efficient computation of reachable sets of linear time-invariant systems with inputs[END_REF], [START_REF] Chutinan | Computational techniques for hybrid system verification[END_REF] and [START_REF] Lygeros | Verified hybrid controllers for automated vehicles[END_REF].

We will now demonstrate that our work from previous chapters may find future application to the study of safety in hybrid systems. Moreover, because we have results on barriers for systems with mixed constraints, our work may be applicable to problems where undesirable sets are subsets of the state space and control space.

As an early application, we are interested in the following problem: given a hybrid automaton for which no externally induced events are possible with initial condition (l 0 , x 0 ) and an undesirable subset of L × X × U given by: B = (L -{l 0 }) × ((X × U ) -Inv(l 0 )) find the potentially safe set: Definition 13 (Potentially Safe Set). Given an undersirable set B ⊂ L × X × U , a statespace point ( l, x) ∈ L × X is said to be potentially safe if there exists, at least, one control ū ∈ U such that (l ( l,x,ū) (t), x ( l,x,ū) (t), ū(t)) / ∈ B for all t ≥ 0. The potentially safe set, S is the set of all such points, i.e.:

S = {( l, x) ∈ L × X : ∃ū ∈ U s.t. (l ( l,x,ū) (t), x ( l,x,ū) (t), ū(t)) / ∈ B, ∀t}.
In other words, we are interested in the special case where it is desirable that the system never transitions out of the initial location. We call this set potentially safe to emphasise that our notion of safety in hybrid systems is not the one usually found in the literature: we only require that there exists a control such that B is not reached.

We can recast the pendulum on a cart system as a hybrid automaton. If we examine the system we see that it is quite difficult to specify a complete hybrid model: if the tension in the cable is positive the dynamics are given by (5.6) and if the cable goes slack and the mass is in free-fall the dynamics are also easy to specify. However, there is a "bouncing phenomenon" that occurs: if the mass is in free-fall there is a finite time at which the cable goes taut, an impact occurs and the mass is in free-fall again. Modelling Chapter 6. Unsolved Problem: Augmenting the State and we deduce λ ū 1 (t) ≡ 1 and λ ū 2 (t) = -t + t > 0 for all t ∈ (-∞, t]. We find that the control is given by: ū(t) = -sign(λ 2 (t)) ≡ -1.

Integrating backwards from z utilising ū gives the barrier in Figure 6.1.

-0.

= x 2 ẋ2 = u u = v (6.3) with |v| ≤ v max , 0 < v max < ∞, x 1 -1 ≤ 0, u -1 ≤ 0 and -u -1 ≤ 0 and let us label g 1 (x, u) = x 1 -1, g 2 (x, u) = u -1 and g 3 (x, u) = -u -1.
The adjoint equations are given by:

λ =    0 0 0 -1 0 0 0 -1 0    λ, λ v( t) =    λ 1 ( t) λ 2 ( t) λ 3 ( t)    which gives λ v 1 (t) ≡ λ v 1 ( t), λ v 2 (t) = -(t -t)λ v 1 ( t) + λ v 2 ( t) and λ v 3 (t) = 1 2 λ v 1 ( t)(t -t) 2 - λ v 2 ( t)(t -t) + λ v 3 ( t) for t ∈ (-∞, t]
where v is the control associated with the barrier, given by: v(t) = -v max sign(λ v 3 (t)). We now show that the only points of tangential arrival are given by {(x 1 , x 2 , u) :

x 1 = 1, x 2 = 0, -1 ≤ u ≤ 0}.
The state cannot arrive tangentially only with the planes given by {(x 1 , x 2 , u) : g 2 (x, u) = 0} or {(x 1 , x 2 , u) : g 3 (x, u) = 0}, because the ultimate tangentiality condition would give: min |v|≤vmax ±v = 0 which is impossible because v max > 0. Let us look at the plane given by {(x 1 , x 2 , u) :

g 1 (x, u) = 0} for u ∈] -1, 1[.
Ultimate tangentiality gives:

min |v|≤vmax Dg(z).f (z, v) = z 2 = 0 where z (z 1 , z 2 , z 3 ) = (x v 1 ( t), x v 2 ( t), u v( t)
). We deduce that the barrier may arrive tangentially with the set given by B = {(x 1 , x 2 , u) : x 1 = 1, x 2 = 0, |u| < 1}, along with the final adjoint λ v( t) = (1, 0, 0). Therefore, from the exact solution of the adjoint we get that for a trajectory arriving on B, v(t) ≡ -v max . If we integrate backwards from any point on B such that u v( t) ≥ 0 we see that these trajectories immediately leave the constrained state space because

x v 1 (t) = -1 6 (t -t) 3 + u v( t)(t -t) 2 + x v 1 ( t) > 0 for all t ∈] -∞, t]
and all ūv ( t) ≥ 0.

Considering the intersection of the planes given by {(x 1 , x 2 , u) : g 1 (x, u) = 0} and {(x 1 , x 2 , u) : g 3 (x, u) = 0}, we invoke conditions (2.11):

min |v|≤vmax max{Dg 1 (z).f (z, v), Dg 3 (z).f (z, v)} = min |v|≤vmax max{z 2 , -v} = 0 (6.4)
For any |z 2 | > v max (6.4) becomes:

min |v|≤vmax max{z 2 , -v} = z 2 > 0. For any |z 2 | ≤ v max min |v|≤vmax max{z 2 , -v} = z 2 ,
and so the point (1, 0, -1) is a point of ultimate tangentiality, along with the final adjoint λ v( t) = (1, 0, 0). For all identified ultimate tangentiality points, that is the set {(x 1 , x 2 , u) :

x 1 = 1, x 2 = 0, -1 ≤ u ≤ 0}, we see that λ v 3 (t) > 0 for all t < t and so v(t) ≡ -v max . The surface made up of backwards integrated barrier trajectories for v max = 1 is shown in Figure 6.2. For decreasing t, u v(t) increases until the trajectory reaches the plane given by {(x 1 , x 2 , u) : u = 1} at which point we need to stop.

Peculiarities of the obtained result include the fact that there is no interior of the admissible set, and as we let v max tend to infinity, the surface disappears. We conjecture that switching of the control must take place for trajectories ending at the identified ultimate tangentiality points in order to construct a sensible admissible set. However, this switching is clearly not provided by the obtained adjoint, and the solution to the problem is an open question.

The first contribution of this thesis is the extension of the work on admissible sets and barriers introduced in [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] to the case of mixed constraints. It was shown that the barrier as well as the concept of semi-permeability extends to this setting; that the barrier may intersect the set G 0 and if so, that it satisfies a generalised ultimate tangentiality condition; and that the barrier can be constructed via a modified minimum-like principle, the proof of which required the Pontryagin maximum principle stated in terms of reachable sets for systems with mixed constraints, as covered in Appendix B. However, the result in this form is available only for control functions that are assumed to be piecewise continuous. The possibility of relaxing this assumption to merely measurable controls is an open question, and can be the subject of future work.

The treatment of the maximum principle as in Appendix B required the introduction of the regularity assumption (A3.4) in order to construct the suitable needle perturbations. We also used this regularity assumption to prove the ultimate tangentiality condition. However, as discussed at the end of Example 3.5.1 and demonstrated in the application to the pendulum on a cart problem of Chapter 5, this assumption may be too strict, especially on the set G 0 , where we may be able to find points of ultimate tangentiality by considering the continuity of the mapping x → U (x). Relaxing the assumption (A3.4) could be addressed in future research.

A trajectory running along the barrier may reach the set G 0 tangentially, in which case we can characterise this intersection and identify points from where the barrier can be constructed. However, as displayed in Example 3.5.3, it is possible that the barrier, still a semi-permeable surface satisfying a minimum-like principle, does not necessarily reach G 0 tangentially but remains in G -for all time. As yet, general conditions that may be used for the identification of points on a barrier of this type, along with the adjoint, have not been derived and this could form the focus of future research.

The thesis's second contribution is a preliminary investigation of stopping points that occur in the construction of barriers: we have presented a theorem that states that every intersection point of barrier trajectories is a stopping point.

It has been observed in optimal control that problems with state constraints often have singularities of the value function, see for example [START_REF] Vinter | Optimal Control[END_REF]. Note that the barrier, which is an (n -1) dimensional manifold, is nondifferentiable at the stopping point in Example 4.3.1 and at every point on the "stopping line" in Example 4.3.2. It may be that stopping points in barriers play an analogous role to singularities found in optimal control.

The minimum-like principle allows us to find a collection of (n-1) dimensional oriented manifolds that intersect. Deducing what parts of these manifolds are in the interior of the admissible set is a question of determining the orientation of these manifolds in a neighbourhood of the intersection. Future research could investigate the use of tools from differential topology, such as the Brouwer degree, to describe this change of orientation.

Finally, we applied the theoretical contributions of the thesis to find the admissible set for the problem involving the pendulum on a cart with a non-rigid cable, as in Chapter 5. This problem involved mixed constraints and stopping points, and we had to provide an ad hoc proof that the barrier intersected specific points on G 0 which again highlighted the strictness of the regularity assumption (A3.4).

F i g(x (u i ,x i ) , u i )
constructed by selecting a subsequence of indices i j such that, given

ε > 0, sup t∈[0,T ] f (x (u i j ,x i j ) (t), u i j (t)) -f (ξ(t), u i j (t)) + g(x (u i j ,x i j ) (t), u i j (t)) -g(ξ(t), u i j (t)) ) < ε2 -j
for each j, which is indeed possible thanks to the uniform convergence of x (u k ,x k ) to ξ and the continuity of f and g. Note also that the limit F ḡ remains the same (for convenience of notation, we keep the same symbols for the α k j 's, but we remark that these coefficients have to be adapted relative to the new subsequence). By Minkowski's inequality, we have:

  T 0 k j=1 α k j f (ξ(t), u i j (t)) -F (t) 2 dt   1 2 ≤   T 0 k j=1 α k j f (ξ(t), u i j (t)) -f (x (u i j ,x i j ) (t), u i j (t)) 2 dt   1 2 +   T 0 k j=1 α k j f (x (u i j ,x i j ) (t), u i j (t)) -F (t) 2 dt   1 2 . (A.6)
We now prove that the limits of the two terms on the right-hand side of expression (A.6), as k tends to infinity, exist and are equal to 0. The convergence of the second limit to 0 is clearly an immediate consequence of the strong convergence of k j=1 α k j F i j to F . For the first term on the right-hand side of (A.6), according to the construction of the above subsequence, and using the fact that α k j ∈ [0, 1] for every j, we have

k j=1 α k j f (ξ(t), u i j (t)) -f (x (u i j ,x i j ) (t), u i j (t)) ≤ k j=1 α k j f (ξ(t), u i j (t)) -f (x (u i j ,x i j ) (t), u i j (t)) < ε k j=1 α k j 2 -j ≤ ε max 1≤j≤k α k j k j=1 2 -j ≤ ε(1 -2 -k ). (A.7) Thus   T 0 k j=1 α k j f (ξ(t), u i j (t)) -f (x (u i j ,x i j ) (t), u i j (t)) 2 dt   1 2 < T ε(1 -2 -k ) 2 1 2 < ε √ T , (A.8)
hence, since ε can be chosen arbitrarily small, the left-hand term in (A.8) converges to 0 as k tends to infinity.

Therefore, the same holds for the left-hand side of (A.6), which proves that F (t) belongs almost everywhere to the closed convex hull of {f (ξ(t), u i j (t))} j∈N which is contained in f (ξ(t), U ) according to (A3.3).

and consider the solution ûI

1,1 of Γ I 1,1 (x, u) = 0, defined from a neighbourhood N I 1,1 of R n × R m-(s 1 +s 2 ) to R s 1 +s 2 . Thus, Γ I 1,1 (x, ûI 1,1 (x, u s 1 +s 2 +1 , . . . , u m ), u s 1 +s 2 +1 , . . . , u m ) = 0 ∀(x, u s 1 +s 2 +1 , . . . , u m ) ∈ N I 1,1
and we can define the integral curve x I 1,1 by: ẋ = f (x, ûI 1,1 (x, ūs 1 +s 2 +1 , . . . , ūm ), ūs 1 +s 2 +1 , . . . , ūm ) (B.2) starting from ξ I 1 at time τ 1 and assume that the interval [σ 1 1 , σ 1 2 [ is small enough such that its solution remains in N I 1,1 .

We iteratively apply the same construction for all q = 2, . . . , d 1 and thus obtain the perturbed x I 1,q and ūI 1,q in each interval [σ 1 q , σ 1 q+1 [, q = 1, . . . , d k -1, satisfying the constraints.

B.1. Control perturbations 93

Then finally, for k > 1, assuming that x I k,d k -1 and ūI k,d k -1 have been obtained, we construct x I k+1,d k+1 -1 and ūI k+1,d k+1 -1 by replacing τ 1 in the above algorithm by τ k to finally get the complete perturbed trajectory.

According to [47, Chapter VI, §34] we introduce the following notations: the perturbation parameters denoted by π belong to the convex cone co{(τ k , l k , v k , ε) : k = 1, . . . , K} and we note x π (t) = x I k,q (t) previously defined with the vector of perturbation parameters π if t ∈ [σ k q , σ k q+1 [. Then, for a given vector of perturbation parameters π {τ 1 , . . . , τ K , α 1 l 1 , . . . , α K l K , v 1 , . . . , v K }, with α k ≥ 0 and K k=1 α k = 1, we have

x π (t) = x (ū,x 0 ) (t) + εδx(t) + O(ε 2 ) (B.3) with δx(t) = K k=1 α k Φ ū(t, τ k ) f (x (ū,x 0 ) (τ k ), v k ) -f (x (ū,x 0 ) (τ k ), ū(τ k )) l k (B.4)
and Φ ū the transition matrix of the variational equation: d dt (Φ ū(t, τ )) = ∂f ∂x (x (ū,x 0 ) (t), ū(t)) + Λ ū(t) ∂g ∂x (x (ū,x 0 ) (t), ū(t)) Φ ū(t, τ ), Φ ū(τ, τ ) = I (B.5) for all 0 ≤ τ ≤ t where the function Λ ū : [0, t 1 ] → R n × R p is a matrix with piecewise continuous entries which we recursively construct over [0, t 1 ] as follows.

Consider the interval [τ 1 -εl 1 , τ 1 ] and assume that s 1 = #I(x (ū,x 0 ) (τ 1 ), ū(τ 1 )) = 0 and s 2 = #J(ū(τ 1 )) = 0 (again, we will not carry over the indexing of s 1 and s 2 to subsequent intervals to lighten the notation). Then we let Λ ū(t) = 0 for t ∈ [τ 1 -εl 1 , τ 1 ], i.e. a matrix of zeros.

Otherwise max(s 1 , s 2 ) > 0 and we define Λ ū I 1 (t), an n × s 1 matrix, along with L ū I 1 (t), an n × s 2 matrix, as the solution to the following linear equation for t ∈ [τ 1 -εl 1 , τ 1 ]: ∂f 1,...,n (x (ū,x 0 ) (t), ū(t)) ∂u 1 , . In other words, we augment the matrix Λ ū I 1 (t) by adding columns of zeros that correspond to the inactive g i 's over the interval [τ 1 -εl 1 , τ 1 ]. Recall that we have divided the interval [0, t 1 ] into a number of disjoint subintervals as follows:

0 < τ 1 -εl 1 < τ 1 = σ 1 1 < σ 1 2 < • • • < σ 1 d 1 = τ 2 -εl 2 < τ 2 = σ 2 1 < σ 2 2 < • • • < σ K d K = t 1
We recursively construct Λ ū(t) over each of these subintervals using the same algorithm to arrive at Λ ū(t) defined over the whole interval [0, t 1 ]. Now introducing η ū(t) = (Φ ū) -1 (t, 0)η 0 = Φ ū(0, t)η 0 for an arbitrary η 0 = 0 and setting The variational equation (B.5) may be interpreted as describing the parallel displacement of tangent vectors v π k f (x (ū,x 0 ) (τ k ), v k ) -f (x (ū,x 0 ) (τ k ), ū(τ k )) l k , referred to as elementary perturbation vectors, along x (ū,x 0 ) from τ k to t, and the adjoint equation (B.8) may be interpreted as describing the parallel displacement of hyperplanes along x (ū,x 0 ) . It can be shown that for any elementary perturbation vector v π k . Denote by K t the tangent perturbation cone:

µ
K t = {x : x = x (ū,x 0 ) (t) + δx(t)}.

In other words, K t consists of the convex combination of all elementary perturbation vectors that have been transported to time t.

B.2 The maximum principle

The following theorem is an adaptation of [47, Theorem 23, Chapter VI, §35], in the spirit of [START_REF] Lee | Foundations of Optimal Control Theory[END_REF], using the perturbation cone constructed in the previous section. We present a sketch of the proof for completeness.

Theorem B.2.1 (Maximum principle)

Consider the constrained system (3.1), (3.2), (3.3) (3.4). Let x (ū,x 0 ) be a regular trajectory associated with the piecewise continuous control ū ∈ U such that x (ū,x 0 ) (t 1 ) ∈ ∂R t 1 (x 0 ) for some t 1 > 0. Then, there exists a non zero absolutely continuous η ū and piecewise continuous multipliers µ ū i ≥ 0, i = 1, . . Proof : Following the proof of Theorem 3 from [34, Chapter IV], the fact that x (ū,x 0 ) (t 1 ) ∈ ∂R t 1 (x 0 ) implies that there exists a sequence of points {P n }, with P n outside R t 1 (x 0 ) for each n, such that P n → x (ū,x 0 ) (t 1 ), and the unit vectors in the direction P n -x (ū,x 0 ) (t 1 ) approach a vector labelled w(t 1 ).

It can be shown that w(t 1 ) can not be interior to the set K t 1 , and thus we can conclude that there exists a hyperplane Π(t 1 ) at x (ū,x 0 ) (t 1 ) that separates the vector w(t 1 ) from K t 1 . Let η(t 1 ) be the exterior normal of the hyperplane Π(t 1 ), then its parallel transport along x (ū,x 0 ) is given by the solution of (B.10) and we get η(t) T v(t) = η(t 1 ) T v(t 1 ) ≤ 0, ∀t ∈ [0, t 1 ] (B.14) from (B.9) where v(t) is any perturbation vector in K t . We now prove the Hamiltonian maximisation condition by contradiction. Denote by H(x, u, η) = η T f (x, u) the Hamiltonian (not dualised) and suppose that H(x (ū,x 0 ) (t), u(t), η ū(t)) > H(x (ū,x 0 ) (t), ū(t), η ū(t))

over some interval ]t -η, t + η[, η > 0 on [0, t 1 ] with u(t) ∈ U (x (ū,x 0 ) (t)) for all t ∈ ]t -η, t + η[ where t ∈ [0, t 1 ] is a point of continuity of ū. We thus get η(t ) T f (x (ū,x 0 ) (t ), u ) > η(t ) T f (x (ū,x 0 ) (t ), ū(t ))

where u u(t ). If we consider the elementary perturbation vector denoted by v π = f (x (ū,x 0 ) (t ), u ) -f (x (ū,x 0 ) (t ), ū(t ) , which corresponds to the data π = {t , 1, u }, then we get η(t ) T v π (t ) > 0 which contradicts (B.14). We thus conclude that max u∈U (x (ū,x 0 ) (t))

H(x (ū,x 0 ) (t), u, η ū(t)) = H(x (ū,x 0 ) (t), ū(t), η ū(t)), a.e. t ≤ t 1 .

By the Karush-Kuhn-Tucker necessary conditions we conclude that there exists p piecewise continuous multipliers μū i , i = 1, . . . , p and r piecewise continuous multipliers ν ) by η T it can be shown that μi = µ i , i = 1, . . . , p and from here we also get (B.11).

Finally, we need to show that H(x (ū,x 0 ) (t), ū(t), η ū(t), µ ū(t)) = constant a.e. t ≤ t 1 . To this end, we introduce m(η, x) max u∈U (x)

H(x, u, η) = max u∈U H(x, u, η) -p i=1 µ i g i (x, u) M (t) m(η ū(t), x (ū,x 0 ) (t)) = H(x (ū,x 0 ) (t), ū(t), η ū(t)) -p i=1 µ ū i (t)g i (x (ū,x 0 ) (t), ū(t))

and show that the mapping m is locally Lipschitz and thus continuous. From this we will deduce that the mapping t → M (t) is also locally Lipschitz, since it is the composition of m with the piecewise differentiable mappings t → x (ū,x 0 ) (t) and t → η ū(t).

Let m(x 1 , η 1 ) = H(η 1 , x 1 , u 1 ) and m(x 2 , η 2 ) = H(η 2 , x 2 , u 2 ). For the point x 1 , since we have U (x 1 ) = ∅ equivalent to g(x 1 ) ≤ 0 and since g is continuous by Lemma 3.3.1, there exists a neighbourhood of x 1 , N (x 1 ), such that U (x 1 ) ∩ U (ξ) = ∅ for all ξ ∈ N (x 1 ). Therefore, there exists a point x 2 in this neighbourhood such that U (x 1 ) ∩ U (x 2 ) = ∅ and consequently since u 1 ∈ U (x 1 ) there exists x 2 ∈ N (x 1 ) such that u 1 ∈ U (x 2 ). Then we have m(x 1 , η 1 ) -m(x 2 , η 2 ) = max u∈U (x 1 )

H(η 1 , x 1 , u) -max u∈U (x 2 ) H(η 2 , x 2 , u) ≤ H(η 1 , x 1 , u 1 ) -H(η 2 , x 2 , u 1 ) ≤ K 1 x 1 η 1 - x 2 η 2
where the last inequality follows from the fact that H is continuously differentiable w.r.t.

x and η and the constant K 1 is determined from the mean value theorem. A similar analysis gives

m(x 2 , η 2 ) -m(x 1 , η 1 ) ≤ K 2 x 2 η 2 - x 1 η 1
and thus:

|m(x 1 , η 1 ) -m(x 2 , η 2 )| ≤ max(K 1 , K 2 ) x 2 η 2 - x 1 η 1
which shows that m(x, η) is locally Lipschitz.

Let τ ∈ [0, t 1 ], then for an arbitrary τ > τ with τ ∈ [0, t 1 ], since M is locally Lipschitz and therefore has bounded variation, we have the following classical integral formula: For those components where the constraints are not active we have ν j = 0. Otherwise, if ν j = 0 we have γ j (ū(t + ε)) = γ j (ū(t)) = 0 for ε small enough if t is a Lebesgue point. Therefore, ν ū j (t) ∂γ j ∂u (x (ū,x 0 ) (t), ū(t))dū(t) = 0. If t is not a Lebesgue point, again since ν = 0 we have γ j (ū(t + )) -γ j (ū(t -)) = 0 which yields ∂γ j ∂u (x (ū,x 0 ) (t), ū(t))dū(t) = 0, therefore (B.20) is proven. Multiplying (B.18) by dū(t) yields (B.17).

M (τ ) -M (τ ) = τ τ dM (t)
Finally, the proof that p i=1 g i (x (ū,x 0 ) (t), ū(t))dµ ū i (t) = 0 follows the same lines as the proof of (B.20) according to the complementary slackness property. It results that dM (t) = 0 which means that M is constant on every interval of time which achieves the proof of the theorem.

Figure 1 . 1 :

 11 Figure 1.1: Admissible set for (1.1) with a pure state constraint. An integral curve is shown that initiates in A C , utilising the control u = +1 for x 2 ≤ 0, u = -1 for x 2 > 0. This emphasises the semi-permeability property.

Figure 1 . 3 :

 13 Figure 1.3: The admissible set, labelled A, for (1.1) with a mixed constraint, shown along with the admissible set with a pure state constraint

Figure 2 . 1 :Figure 2 . 2 :

 2122 Figure 2.1: Image taken from [25]. Red: constrained set, black: boundary of V iab [0,1] , green: approximation of V iab [0,1] . From top left to bottom right the partition of the interval [0, 1] gets finer.

20 Chapter 2

 202

Chapter 3 .

 3 Barriers for Mixed Constraints Proposition 3.3.2

. 22 ) 3 . 3 . 4

 22334 Proposition Assume (A3.1) to (A3.5) hold. Consider x ∈ [∂A] -and ū ∈ U as in Proposition 3.3.2, i.e. such that the integral curve x (ū,x) (t) ∈ [∂A]

  s) being the solution to the variational equation at time t starting from time s (see equation (B.5) in Appendix B), τ being any Lebesgue point of the control ū, with v ∈ U (x (ū,x 0 ) (τ )) and where we have denoted by O(ε k ) a continuous function of ε k defined in a small open interval containing 0 and such that lim ε→0 O(ε k )

Figure 3 . 1 :Remark 3 .Remark 4 .

 3134 Figure 3.1: A trajectory running along the barrier is on the boundary of the constrained reachable set for every t ≤ t, and if it intersects G 0 it does so tangentially in a generalised sense.

2 Figure 3 . 2 :

 232 Figure 3.2: Admissible set of the constrained spring from Example 3.5.1

Figure 3 . 3 :

 33 Figure 3.3: Figure emphasising the continuity of the mapping x → U (x)

Figure 3 . 4 :

 34 Figure 3.4: Admissible set of the constrained spring from Example 3.5.2

Figure 3 . 5 :

 35 Figure 3.5: Figure showing some of the sets referred to in Example 3.5.3, along with a curve obtained by backward integration from the point (-1, 1) which we have shown to be the backward extension of the barrier.

Chapter 4 .

 4 Stopping Points

Figure 4 . 1 :

 41 Figure 4.1: Problem from section 4.1: wall avoidance for the Dubins car

4. 1 . 51 Figure 4

 1514 Figure 4.2:For any initial condition (x 0 , y 0 , θ 0 ) with x 0 < 0 (the initial orientation has been indicated with an arrow on the car) there exists a control such that the solution traces out a unit circle in the (x, y) space that is completely contained in {(x, y, θ) : x < 1}

Figure 4 . 3 :Figure 4 . 4 :

 4344 Figure 4.3: Example of a stopping point by intersection occurring in a two dimensional system. The two separating hyperplanes at t are marked in red andf (ξ, U ) ⊂ Π + 1 ( t)∩Π + 2 ( t)

Figure 4 . 5 :

 45 Figure 4.5: Admissible set for Example 4.3.1, from[START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF]

Figure 4 . 6 :

 46 Figure 4.6: The barrier for the nonholonomic vehicle, showing the intersection of the two surfaces in a line

5 .

 5 Une application aux ensembles potentiellement sûrs pour systèmes hybrides: le pendule avec un câble non-rigide monté sur un chariot.

Figure 5 . 2 :

 52 Figure 5.2: The set G 0 = {θ : -| sin θ 1 | + M g cos θ 1 -M lθ 2 2 = 0} for M = 0.1, m = 0.1, l = 1 and g = 10, along with some important points.

5. 1 .

 1 Admissible set for the Pendulum on a Cart with Non-Rigid Cable 61

5. 1 .Figure 5 . 3 :Figure 5 . 5 : 5 . 1 .Figure 5 . 6 :

 153555156 Figure 5.3: Result of obtaining barrier trajectories that end at the points (± arctan(M g)+ 2kπ, 0). There is a contradiction with regards to the orientation of the barrier, and we conclude that parts of the barrier are missing.

  Denoting by M (t) a,b the entry in the a'th row and b'th column of the time-varying matrix M , we now specify:Λ ū(t) a,b = λ b a (t), ∀a ∈ {1, . . . , n}, if b ∈ I(x (ū,x 0 ) (τ 1 ), ū(τ 1 )) 0 ∀a ∈ {1, . . . , n}, if b / ∈ I(x (ū,x 0 ) (τ 1 ), ū(τ 1 ))94 Appendix B. Maximum principle for problems with mixed constraints

  d dt Φ ū(t, τ k )v π k T η ū(t) = 0 ∀t ∀η 0 = 0 (B.9)

  Chapter 3. Barriers for Mixed ConstraintsLet us prove next that the infimum with respect to u is achieved by some ū ∈ U in order to get(3.12). To this aim, let us consider a minimising sequence u k ∈ U, k ∈ N, i.e. such that

	lim k→∞	ess. sup t∈[0,∞)	max i=1,...,p

.14)

Proof : We first prove (i). If x ∈ A, by definition, there exists u ∈ U such that g(x (u,x) (t), u(t))

0 for almost all t ≥ 0, and thus such that ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≤ 0. We immediately get inf u∈U ess. sup t∈[0,∞) max i=1,...,p g i (x (u,x) (t), u(t)) ≤ 0. (3.15)

  [∂A] -to justify the name of barrier in Definition 9.Assume (A3.1) to (A3.5) hold. Then from any point on the boundary [∂A] -, there cannot exist a trajectory penetrating the interior of A before leaving G -.

	Proposition 3.3.3

Proof : Since x ∈ [∂A] -, there exists an open set O ⊂ R n such that x + εh ∈ A C for all h ∈ O and h ≤ H, with H arbitrarily small, and all ε sufficiently small. Therefore, there exists t ε,h such that max i=1,...,p g i (x (ū,x+εh) (t), ū(t)) < 0 for all t < t ε,h and max i=1,...,p g i (x (ū,x+εh) (t ε,h ), ū(t ε,h )) ≥ 0. Taking an arbitrary σ ∈]0, t ε,h [ and setting ξ ε,h

  . . , ∂u s 1 +s 2 = Λ ū I 1 (t) ∂g i 1 ,...,is 1 (x (ū,x 0 ) (t), ū(t)) ∂u 1 , . . . , ∂u s 1 +s 2 + L ū I 1 (t) ∂γ j 1 ,...,js 2 (x (ū,x 0 ) (t), ū(t)) ∂u 1 , . . . , ∂u s 1 +s 2 (B.6) where ∂g i 1 ,...,is 1 ∂u 1 , . . . , ∂u s 1 +s 2 = and ∂f 1,...,n ∂u 1 ,...,∂u s 1 +s 2 and ∂γ j 1 ,...,js 2 ∂u 1 ,...,∂u s 1 +s 2 are similarly defined. The solution to this equation exists due to assumption (A3.4).

			     	∂g i 1 ∂u 1 . . . ∂g is 1 ∂u 1	. . . . . . . . .	∂g i 1 ∂us 1+s 2 . . . ∂u s 1 +s 2 ∂g is 1	     
	Let		λ i 1 1 (t) λ i 2 1 (t) . . . λ is 1 1 (t)
	Λ ū I 1 (t) =	     	λ i 1 2 (t) . . . . . . λ i 1		λ is 1 2 (t)

n (t) . . . λ is 1 n (t)

  ū(t) -Λ ū(t) T η ū(t)

						(B.7)
	we get the adjoint equation
	ηū (t) = -	∂f ∂x	(x (ū,x 0 ) (t), ū(t))	p i=1	µ ū i (t)	∂g i ∂x

T η ū(t) + T (x (ū,x 0 ) (t), ū(t)). (B.8)

  . , p satisfying, for almost all t ≤ t 1 : B.2. The maximum principle 95 such that, if we define the dualised Hamiltonian H(x, u, η, µ) η T f (x, u) -(ū,x 0 ) (t), u, η ū(t), µ ū(t)) = H(x (ū,x 0 ) (t), ū(t), η ū(t), µ ū(t)) = constant a.e. t≤ t 1 (B.13)

			p
			µ i g i (x, u),	(B.12)
			i=1
	it satisfies
	max u∈U	H(x
		p i=1	µ ū i (t)	∂g i ∂x

ηū (t) = -∂f ∂x (x (ū,x 0 ) (t), ū(t)) T η ū(t) + T (x (ū,x 0 ) (t), ū(t)) (B.10) µ ū i (t)g i (x (ū,x 0 ) (t), ū(t)) = 0 ∀i ∈ {1, . . . , p} (B.11)

  96 Appendix B. Maximum principle for problems with mixed constraints Noting that ∂H ∂u = η T ∂f ∂u , if we now multiply equation (B.6

										ū j ,
	j = 1, . . . , r such that
	∂H ∂u	(x ū(t), ū(t), λ ū(t)) -	p i=1	μū i (t)	∂g i ∂u	(x ū(t), ū(t)) -	r j=1	ν j (t) ū	∂γ j ∂u	(ū(t)) = 0, a.e. t ≤ t 1
	along with the complementary slackness conditions:

   μū i (t)g i (x ū(t), ū(t)) = 0, μū i (t) ≥ 0 i = 1, . . . , p ν ū j (t)γ j (ū(t)) = 0, ν ū j (t) ≥ 0 j = 1, . . . ,

r . (B.15)

  where dM is a bounded measure on[τ, τ ]. By a straightforward identification we have(ū,x 0 ) (t), ū(t), η ū(t)) --L ū(t) T η ū(t) (B.19)with L ū(t) suitably augmented with zeros for coordinates which do not correspond to active constraints, as was done for Λ ū. Let us prove that

	B.2. The maximum principle		97
	Using (B.10) we immediately deduce that
			∂H ∂x	(x p i=1	µ ū i (t)	∂g i ∂x	(x (ū,x 0 ) (t), ū(t)) ẋ(t)
										+	∂H ∂η	(x (ū,x 0 ) (t), ū(t), η ū(t)) η(t) = 0
	Let us now prove that
		∂H ∂u	(x (ū,x 0 ) (t), ū(t), η ū(t)) -	p i=1	µ ū i (t)	∂g i ∂u	(x (ū,x 0 ) (t), ū(t)) dū(t) = 0.	(B.17)
	From (B.6) left multiplying η ū(t) T we get:
	∂H ∂u	(x (ū,x 0 ) (t), ū(t), η ū(t))-	p i=1	µ ū i (t)	∂g i ∂u	(x (ū,x 0 ) (t), ū(t))-j=1 r	ν ū j (t)	∂γ j ∂u	(x (ū,x 0 ) (t), ū(t)) = 0
										(B.18)
	where
						ν ū(t)   r ν ū j (t) ∂γ
						j=1
		dM (t) =	∂H ∂x	(x (ū,x 0 ) (t), ū(t), η ū(t)) ẋ(t)dt +	∂H ∂η	(x (ū,x 0 ) (t), ū(t), η ū(t)) η(t)dt
			+	∂H ∂u	(x (ū,x (B.16)

0 ) (t), ū(t), η ū(t))dū(t) -p i=1 g i (x (ū,x 0 ) (t), ū(t))dµ ū i (t) -p i=1 µ ū i (t) ∂g i ∂x (x (ū,x 0 ) (t), ū(t)) ẋ(t)dtp i=1 µ ū i (t) ∂g i ∂u (x (ū,x 0 ) (t), ū(t))dū(t). j ∂u (x (ū,x 0 ) (t), ū(t))   dū(t) = 0. (B.

[START_REF] Goebel | Hybrid Dynamical Systems: Modeling, Stability, and Robustness[END_REF]

boulevard Saint-Michel, 75006 Paris

Note that this implies that s 1 + s

≤ m, with s 1 = #(I(x, u)) and s 2 = #(J(u))

we discard cases of blow-up in finite time

in other words with f (ξ, u 1 ( t)) and f (ξ, u 2 ( t)) independent

Remark 6. By condition (2.10) and condition (3.34) we have that at each t (λ ū(t)) T f (x ū(t), u) ≥ 0 for all u ∈ U , which intuitively means that the vectogram f (x, U ) points in the direction of cl(A C ) for all x ∈ [∂A] -. Theorem 4.2.1 (i) Consider two distinct integral curves x (u 1 ,z 1 ) and x (u 2 ,z 2 ) as in Definition 11. If there exists an intersection point ξ of these two curves at some time 3 t, i.e.

x (u 1 ,z 1 ) ( t) = x (u 2 ,z 2 ) ( t) = ξ, then ξ is a barrier stopping point by intersection.

(ii) Consider an integral curve x (u,z) as in Definition 11. If x (u,z) is self-intersecting at ξ, then ξ is a barrier stopping point by self-intersection.

Proof : (i) We denote by λ u 1 and λ u 2 the two corresponding adjoint integral curves satisfying λ u j ( tj ) = Dg i * j (z j ) T , j = 1, 2, with i * j ∈ I(z j ) for the case with pure state constraints, or λ u j ( tj ) ∈ arg max ξ∈∂g(z j ) ξ.f (z j , ū( tj )), j = 1, 2 for the case with mixed constraints. For each t ∈ [ t, tj ] the adjoint λ u j (t) is the normal to the (n -1) dimensional separating hyperplane Π j (t) tangent to the curve x (u j ,z j ) at the point x (u j ,z j ) (t), the vectogram given by f (x (u j ,z j ) (t), U ) being included in the closed half space Π + j (t) containing λ u j (t), j = 1, 2, since we have (λ u j (t)) T f (x (u j ,z j ) (t), v) ≥ 0 for all v ∈ U by condition (2.10) and condition (3.34). Moreover, according to Remark 6, f (x (u j ,z j ) (t), v) points into cl(A C ) for all v ∈ U and all t such that x (u j ,z j ) (t) ∈ [∂A] -, j = 1, 2. Thus f (ξ, U ) ⊂ Π + 1 ( t) ∩ Π + 2 ( t), see Figures 4.3 and 4.4. Therefore, going backwards with -f (x (u i ,x i ) (t), u i (t)), i = 1, 2 impies that x (u i ,x i ) (t) ∈ int(A) for all t < t and thus cannot belong to the barrier. Hence ξ is a stopping point.

(ii) Let λ u denote the adjoint associated with the integral curve x (u,z) with λ u ( t) = Dg i * (z) T , and let Π + (t) denote the closed half space containing λ u (t) at time t. The proof of (i) may be adapted to a self-intersecting curve by replacing the two closed half spaces Π + 1 ( t) and Π + 2 ( t) by Π + ( t1 ) and Π + ( t2 ) respectively. The proof then follows the same lines.

Remark 7. Theorem 4.2.1 is applicable to points where more than two distinct integral curves obtained from Theorem 2.1.1 or Theorem 3.4.1 intersect. In this case, Theorem 4.2.1 can be applied to pairs of integral curves.

Examples

Two Dimensional Nonlinear Example

We consider the problem from section 8.3 of [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF]. A system is specified with dynamics:

with |u| ≤ 1. The state is constrained to lie in the region -1 ≤ x 1 ≤ 3. From the ultimate tangentiality condition we easily identify four points: (-1, -1), (-1, 1), (3, -1) and (3, 1).

Chapter 5. An Application to Potentially Safe Sets in Hybrid Systems: Pendulum on a Cart with Non-Rigid Cable the cable and g the acceleration due to gravity. The cart's position is given by x, and the coordinates of the mass m are given by (y, z). We also note that y = x + l sin θ and z = l cos θ. It is desirable to manoeuvre the cart in such a way that the cable always remains taut.

The study of this system may serve as an initial step in the investigation of safely controlling overhead cranes where slackness of the cable would result in free-fall of the working mass, which is very dangerous and can damage the system. See for example [START_REF] Kiss | Planification de trajectoires et commande d'une classe de systèmes mécaniques plats et Liouvilliens[END_REF], [START_REF] Kiss | Modelling, flatness and simulation of a class of cranes[END_REF] and [START_REF] Kiss | Modelling and motion planning for a class of weight handling equipment[END_REF] for studies on weight handling equipment. A similar problem appears in [START_REF] Nicotra | Taut cable control of a tethered uav[END_REF] where the authors study tethered unmanned aerial vehicles.

One way of keeping the cable taut is to impose the condition that the cable's tension, T , is always nonnegative. Under this assumption the dynamics of the system are given by the well-known equations of the pendulum on a cart system, given by: θ1 = θ 2 (5.1)

where x 1 = x, and θ 1 = θ. These equations of motion are easily derived via the Euler-Lagrange equations. Let us show that imposing the condition that the tension in the cable remains nonnegative is equivalent to imposing a mixed constraint on the system. Considering the balance of forces on the mass m, we get that mz = -T cos θ 1 -mg where z = -l θ 2 2 cos θ 1 + θ2 sin θ 1 . Thus T ≥ 0 is equivalent to:

Admissible set for the Pendulum on a Cart with Non-Rigid Cable 59 and so

After multiplying by -l (M + m sin 2 (θ 1 )) (an expression that is always negative), gathering terms and simplifying we obtain:

This last inequality then simplifies to:

Note that (5.5) is independent of x 1 and x 2 which also do not appear on the right hand sides of (5.1) or (5.2). Therefore, we can analyse the system while ignoring the dynamics of the cart and our problem reduces to finding the admissible set of the following constrained system:

(5.7)

Because our theory has been developed for constraints of the form (3.4), we will consider the problem with a non-strict inequality as in (5.7). Although it would be correct to observe that zero tension in the cable results in the mass being in free-fall, we can in fact guarantee that the cable remains taut when this occurs as long as the state remains in the obtained admissible set. The reason for this is that we can interpret (5.6) and (5.7) as studying a pendulum on a cart with a rigid bar and requiring the tension to be nonnegative. Clearly then, any trajectory of this system such that the tension never goes negative will be a trajectory for the pendulum on a cart with a non-rigid cable such that the cable never goes slack.

Constructing the Admissible Set

We label the mixed constraint h(θ, u) = u sin θ 1 + M g cos θ 1 -M lθ 2 2 and let h

Let us assume that barrier trajectories reach the set G 0 = {(θ 1 , θ 2 ) : h(θ) = 0}, which is shown in Figure 5.2 for the constants M = 0.1, m = 0.1, l = 1 and g = 10. Note that the equation h(θ) = 0 only has a solution for θ 1 ∈ [-arctan(M g) + 2kπ, arctan(M g) + 2kπ], k an integer, and that h(θ) is not differentiable if θ 1 = 2kπ. Also,

if sin θ 1 = 0.

(5.8) If the trajectory approaches the point (0, g l ) from D + or D -and we consider the left limit of the set U (θ (ū,θ 0 (t)) as t t then, due to the continuity of the mapping

, we can see that for all v ∈ U (θ (ū,θ 0 ( t-)) there exists a continuous mapping τ → v τ from [ t -η, t[ to U , with η > 0 small enough, such that v τ ∈ U (θ (ū,θ 0 ) (τ )) for all τ ∈ [ t -η, t[ and lim τ → t v τ = v. This mapping τ → v τ also exists if the barrier approaches the point (0, g l ) from C + or C -because in this case U (θ (ū,θ 0 (t)) = [-1, 1] for all t in an arbitrarily small interval before t.

We now construct a needle perturbation as in (3.25):

and carry out the analysis as in Proposition 3.3.4 to arrive at:

for every v ∈ U (θ (ū,θ 0 ) (τ )) and almost every ε and h as in equation (3.26). In particular, recall:

Replacing v in the above expression with the continuous family v τ , letting h and ε tend to zero and then dividing by l, we see that as τ tends to t equation (5.11) becomes:

where as before, u(t -) lim τ t,t / ∈I 0 u(τ ), I 0 being a suitable zero-measure set of R and θ(t -) lim τ t θ(τ ). Because h(θ (ū,θ 0 ) (t)) is clearly increasing over an arbitrarily small interval before t we have min

(5.12)

Let us assume that θ (ū,θ 0 ) approaches the point (0, g l ) from

The inequality (5.12) becomes:

where we have dropped the superscripts to lighten the notation. This simplifies to:

We have that ū( t-) = -1 and sog l + 2 g l ū( t-) = -g l + 2 g l (-1) < 0 which is impossible. Therefore, a barrier trajectory cannot approach the point (0, g l ) from C + .

Chapter 5. An Application to Potentially Safe Sets in Hybrid Systems: Pendulum on a Cart with Non-Rigid Cable

Let us assume that θ (ū,θ 0 ) approaches the point (0, g l ) from

is the same as before andg l + 2 g l ū( t-) = -g l + 2 g l (-1) < 0 which is impossible. Therefore, a barrier trajectory cannot approach the point (0, g l ) from D + . Let us assume that θ (ū,θ 0 ) approaches the point (0, g l ) from C -. Then U (θ (ū,θ 0 ) ( t-)) = [-1, 1] and D h(θ (ū,θ 0 ) ( t-)) = cos θ 1 ( t-) -M g sin θ 1 ( t-), -2M lθ 2 ( t-) . The inequality (5.12) becomes:

and again we have ū( t-) = -1 which means g l + 2 g l ū( t-) = g l + 2 g l (-1) < 0 which is impossible.

Finally, if θ (ū,θ 0 ) approaches the point (0

, 1] and D h(θ (ū,θ 0 ) ( t-)) is as before. The inequality (5.12) becomes:

Therefore, it is only possible for θ (ū,θ 0 ) to intersect the point (0, g l ) from the set D -. Recall from Appendix B that for any elementary perturbation vector ν(t) f (θ (ū,θ 0 ) (t), v) -f (θ (ū,θ 0 ) (t), ū(t)) , v ∈ U (θ (ū,θ 0 ) (t)) we have that:

where η(t) is the normal of a hyperplane containing the elementary perturbation cone K t . Therefore, from equation (5.12) we have that D h(θ (ū,θ 0 ) ( t-))ν( t-) ≥ 0 which means that -D h(θ (ū,θ 0 ) ( t-)) is the normal to the referred to separating hyperplane. We can thus conclude that the final conditions of the adjoint at (0, g l ) are given by

From here we deduce that λ 4 (t) = λ 3 (t) ≡ 0 and we derive the same control law as before.

Because λ 2 ( t-) < 0 and cos(θ 1 ( t-)) > 0 we conclude, from the continuity of θ and λ, that:

over some interval of time before t. This fits in well with our previous argument that the barrier trajectory must approach (0, g l ) from D -. We now have all the information we need in order to construct the barrier from the point (0, g l ). However, note that equation (5.14) is singular for θ 1 = 0 which presents a problem if we want to numerically integrate backwards from (0, g l ). Luckily, we can in fact find the exact solution to the pendulum equations with control (5.14) and boundary condition (0, g l ).

5.1. Admissible set for the Pendulum on a Cart with Non-Rigid Cable 67

Employing the control (5.14), the system (5.6) becomes: θ1 -θ 2 = 0 (5.15) θ2 (-l sin θ 1 ) -lθ 2 2 cos θ 1 + g = 0.

(5.16)

The adjoint equations (5.10) reduce to

which are the same equations one derives from the much simpler system (5.15) -(5.16).

(We momentarily drop the superscripts to lighten the notation.) Equation ( 5. [START_REF] Dubins | On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents[END_REF]) is equivalent to: d 2 dt 2 l cos θ 1 = -g and from the boundary condition θ 1 ( t) = 0 we get:

and cos(θ

(5.20)

Due to the symmetry of cosine, we see that there are two possible solutions:

defined on the interval [ t -2 l g , t + 2 l g ]. However, from the condition θ 2 ( t) = g l we deduce that the correct solution is given by: over this same interval. The adjoint equations (5.17) -(5.18) are also singular for θ 1 = 0. We work around this problem by integrating the system equations (5.6) and the adjoint equations (5.10) backwards from the point θ (ū,x 0 ) ( t -η), η > 0, along with λ (ū,x 0 ) ( t -η) = (1, -2M l g l ), where θ (ū,x 0 ) ( t -η) is the exact solution to (5.15) -(5.16) at t -η. As η tends to zero the resulting integral curve uniformly converges to the barrier trajectory.

The resulting admissible sets are shown in Figures 5.5 and 5.6 for two different sets of constants. It is interesting to note that for the same bound on the input force, if the cart's mass compared with the mass at the end of the cable is small enough then the two barrier trajectories intersect and we get a stopping point as shown in Figure 5.6. Figure 5.7 shows the control function associated with the barrier trajectories. where the control switches. The crosses labelled "+" correspond to the points where the controls associated with the barrier trajectories arriving at (0, ± g l ) switch to

Chapter 5. An Application to Potentially Safe Sets in Hybrid Systems: Pendulum on a Cart with Non-Rigid Cable this phenomenon would be very difficult as it depends on the properties of the cable, the state of the mass at impact and the state of the cart. This "bouncing" carries on until enough energy has been lost, at which point the system returns to being governed by (5.6). Luckily in order to solve our problem, we can ignore this aspect of the system and study the following incomplete model.

) is given by (5.6) and the remainder of the model is left unspecified, as it unnecessarily complicates the problem. See Figure 5.8. The potentially safe set is now just the admissible set as obtained from the previous section. Dans ce chapitre on considère les contraintes mixtes comme des contraintes d'état pures sur l'état étendu où l'entrée est considérée comme un état supplémentaire, dans un but de simplification. Cependant, on obtient des résultats qui ne permettent pas de conclure, le problème demeurant non-résolu. This section briefly explores the idea of letting the control u be an additional state of the system with dynamics given by u = v, where v is a new fictional bounded measurable input function. The motivation for this is that a system subjected to mixed constraints would be transformed into the framework of the pure state constraint setting with the hope that many of the difficulties associated with mixed constraint barriers would be averted. Intuitively, as we let the bound on the fictional input v tend to infinity we should get that the admissible set obtained for the augmented system, projected onto the x space, approaches the admissible set obtain for the original problem where u was considered an input. However, carrying out this analysis on a simple example, that we present in this chapter, gives some very surprising and nonintuitive results even for a problem subjected to pure state constraints.

Let us consider the double integrator subjected to a pure state constraint:

with |u| ≤ 1 and x 1 -1 ≤ 0. The ultimate tangentiality condition gives:

and so an ultimate tangentiality point is given by z (z 1 , z 2 ) = (x ū 1 ( t), x ū 2 ( t)) = (1, 0), where t indicates the time of tangential arrival with G 0 and ū denotes the control associated with the barrier trajectory. The adjoint satisfies:

Appendix A

Compactness of solutions

We slightly extend the compactness results proven in [15, Appendix A] to the mixed constraint context. We first recall the following lemma and its corollary from [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF] along with the proofs for completeness.

Lemma A.0.1

If assumptions (A3.1) and (A3.2) of Section 3.1 hold true, equation (3.1) admits a unique absolutely continuous integral curve over [t 0 , +∞) for every u ∈ U and every bounded initial condition x 0 , which remains bounded for all finite t ≥ t 0 ,

K(t). (A.1)

Moreover, we have

for all t, s ∈ [t 0 , T ] and all T > t 0 , where

C sup

x ≤K(T ),u∈U f (x, u) < +∞. (A.3)

Proof : Multiplying both sides of (3.1) by x(t) T , we get

or, in integral representation, and taking absolute values,

By Grönwall's Lemma, we get

which readily yields (A.1).

To prove Inequality (A.2), let us recall that, for every pair t, s ∈ [t 0 , T ] and all T > t 0 , x(t) -x(s) = t s f (x(τ ), u(τ ))dτ . The continuity of f implies that C < +∞ with C defined by (A.3). We immediately deduce (A.2).

Corollary A.0.1

Let us denote by X (x 0 ) the set of integral curves issued from an arbitrary x 0 , x 0 < ∞, and satisfying (3.1), (3.2), (3.3).

If assumptions (A3.1) and (A3.2) of Section 3.1 hold true, X (x 0 ) is a subset of C 0 ([0, ∞), R n ), the space of continuous functions from [0, ∞) to R n , and is relatively compact with respect to the topology of uniform convergence on C 0 ([0, T ], R n ) for all finite T ≥ 0. In other words, from any sequence of integral curves in X (x 0 ), one can extract a subsequence whose convergence is uniform on every interval [0, T ], with T ≥ 0 and finite, and whose limit belongs to C 0 ([0, ∞), R n ).

Proof : In Lemma A.0.1, inequality (A.1) means that the restriction of the integral curves of X (x 0 ) to any finite interval [0, T ] is equibounded, and (A.2) shows that the same restriction to any finite interval [0, T ] of the integral curves of X (x 0 ) is an equicontinuous set with respect to the topology of uniform convergence on C 0 ([0, T ], R n ), for all T ≥ 0. The relative compactness results from Ascoli-Arzelà's theorem (see e.g. [64, Chap. III, §3, p. 85]).

We now adapt the proof of [15, Lemma A.2, Appendix A]. Lemma A.0.2

Assume that (A3.1), (A3.2) and (A3.3) of Section 3.1 hold. Given a compact set X 0 of R n , the set X x 0 ∈X 0 X (x 0 ) is compact with respect to the topology of uniform convergence on C 0 ([0, T ], R n ) for all T ≥ 0, namely from every sequence {x (u k ,x k ) } k∈N ⊂ X one can extract a uniformly convergent subsequence on every finite interval [0, T ], whose limit ξ is an absolutely continuous integral curve on [0, ∞), belonging to X . In other words, there exists x ∈ X 0 and ū ∈ U such that ξ(t) = x (ū,x) (t) for almost all t ≥ 0.

Moreover, if the sequence {(x

0 for all k and almost all t, then the limit also does: g(x (ū,x) (t), ū(t)) 0 for almost all t.

Proof : Since X 0 is compact, it is immediate to extend inequalities (A.1) and (A.2) to integral curves with arbitrary x 0 ∈ X 0 by taking, in the right-hand side of (A.1), the supremum over all x 0 ∈ X 0 . Thus, by the same argument as in the proof of Corollary A.0.1, using Ascoli-Arzelà's theorem, we conclude that X is relatively compact with respect to the topology of uniform convergence on C 0 ([0, T ], R n ), for all T ≥ 0. The proof that from every sequence {x (u k ,x k ) } k∈N ⊂ X one can extract a uniformly convergent subsequence on every finite interval [0, T ] whose limit ξ belongs to X is the same as in [START_REF] De Dona | On barriers in state and input constrained nonlinear systems[END_REF], which we now present along with the new result that the sequence of functions {t → g(x (u k ,x k ) (t), u k (t)} converges to a limit such that g(x (ū,x) (t), ū(t)) 0 almost everywhere.

We first remark that, from the fact that X is relatively compact we have that the limit, ξ, is a continuous function on [0, T ] for all T ≥ 0, and that, for every finite T and every t ∈ [0, T ],

where the limit is taken over a subsequence and with the notations x = lim k→∞ x k and

We denote by < v, w >= n i=1 v i w i the scalar product of the vectors v and w in R n . Since, for every k, the integral curve x (u k ,x k ) satisfies ẋ(u k ,x k ) (t) = F k (t) for almost every t, taking the scalar product of both sides by a function ϕ ∈ C ∞ ([0, ∞), R n ) and integrating from 0 to T , yields

or, after integration by parts:

Taking the limits of both sides, according to the uniform boundedness of the integrals, we get, with ξ defined as a distribution on [0, T ]:

In other words, ξ = lim k→∞ F k in the sense of distributions. Moreover, for every T > 0, restricting ϕ to C ∞ K ([0, T ], R n ) (the set of infinitely differentiable functions from [0, T ] to R n with compact support, which is indeed contained in C ∞ ([0, ∞), R n )) and using the density of

R n ) (see e.g. [START_REF] Schwartz | Théorie des Distributions[END_REF]), equation (A.5) also implies that the sequence F k is weakly convergent in L 2 ([0, T ], R n ). Let us denote by FT its weak limit in L 2 ([0, T ], R n ). We have therefore constructed a collection { FT } T >0 of weak limits, which uniquely defines a function F almost everywhere on the whole interval [0, ∞), whose restriction to any interval [0, T ] coincides a.e. with FT , i.e. F [0,T ] = FT a.e.. Indeed, taking any pair of intervals [0, T 1 ] and [0, T 2 ] with T 1 ≤ T 2 , by the uniqueness of the limits FT 1 and FT 2 , the restriction of FT 2 to the interval [0, T 1 ] coincides almost everywhere with FT 1 and it is readily seen that non uniqueness of F would contradict the uniqueness of every FT .

Accordingly, the sequence of functions {t → g(x

R n ) for every finite T , which implies that this sequence contains at least a weakly convergent subsequence (still denoted by g(x (u k ,x k ) , u k )). We denote by ḡ its weak limit, independent of T as above. By Mazur's Theorem (see e.g. [64, Chapter V, §1, Theorem 2, p. 120]), for every k, there exists a sequence {α k 1 , . . . , α k k } of non negative real numbers, with k i=1 α k i = 1, such that the sequence Fk gk

R n ) for all finite T . Note that this property a fortiori holds true if we replace the sequence F i by any subsequence

The proof that ḡ(t) ∈ g(ξ(t), U ) for almost all t follows the same lines. We immediately conclude that if g(x (u k ,x k ) (t), u k (t)) 0 for all k and almost every t, it is the same for any convex combination and therefore ḡ(t) 0 for almost all t.

Finally, again according to (A3.3) and (A3.5), there exists, by the measurable selection theorem [START_REF] Castaing | Convex Analysis and Measurable Multifunctions[END_REF], ū ∈ U such that

Thus, we conclude that ξ satisfies ξ = f (ξ, ū) almost everywhere, with ξ(0) = x ∈ X 0 . By the uniqueness of integral curves of (3.1), we conclude that ξ(t) = x (ū,x) (t) almost everywhere and, thus, that ξ ∈ X . Accordingly, we indeed have ḡ(t) = g(ξ(t), ū(t)) = g(x (ū,x) (t), ū(t)) 0 a.e. t ∈ [0, ∞), which achieves to prove the lemma.

Appendix B

Maximum principle for problems with mixed constraints

In this appendix we sketch a version of the maximum principle for problems with mixed constraints that describes the extremal curves as those whose endpoints at each time t belong to the boundary of the reachable set at the same instant of time. This form of the principle is needed to prove Theorem 3.4.1. The proof draws content from [START_REF] Lee | Foundations of Optimal Control Theory[END_REF], where the principle is proved in the particular case of constraints on the control, and [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF], where the principle is proved in the context of optimising a cost function for systems with both constraints on the control and the state, but which are not mixed, though a remark indicating the possibility of its extension to mixed constraints is given in [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF]Chapter VI,[START_REF] Lévine | Analysis and Control of Nonlinear Systems: A Flatness-Based Approach[END_REF]. See also [START_REF] Hestenes | Calculus of Variations and Optimal Control Theory[END_REF]Chapter 7] for a proof in the framework of the Calculus of Variations. For a survey on the maximum principles with state constraints, the reader may refer to [START_REF] Hartl | A survey of the maximal principles for optimal control problems with state constraints[END_REF].

In our treatment we will introduce the suitable perturbations to regular trajectories, similar to [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF], that are needed to generate the so-called perturbation cone, the latter being crucial to obtain the necessary conditions of the maximum principle. Throughout the analysis we assume that the extremal control is piecewise continuous as in the above cited references.

The contents of this appendix are to appear in [START_REF] Esterhuizen | Barriers in nonlinear control systems with mixed constraints[END_REF].

B.1 Control perturbations

Consider an integral curve x (ū,x 0 ) associated with the piecewise continuous control ū, initiating from the point x 0 . Let τ k , k = 0, . . . , K, with τ 0 = 0, be a collection of points of continuity of ū such that τ k -εl k is also a point of continuity with l k ≥ 0 for all ε small enough. Assume that g(x (ū,x 0 ) (t), ū(t)) 0 for a.e. t ∈ [τ k-1 , τ k [. We will perturb the control over the interval I k = [τ k -εl k , τ k [ and extend both the control and the integral curve between τ k and τ k+1 -εl k+1 in order to satisfy the constraints. This will be done by first making a subdivision σ k q , q = 1, . . . , d k , namely

, assumed to contain all discontinuities of ū on the interval [τ k , τ k+1 -εl k+1 [ and adapting ū and its corresponding integral curve on each subinterval [σ k q , σ k q+1 [, q = 1, . . . , d k -1, using the implicit function theorem. At k = 1, if s 1 = #I(x (ū,x 0 ) (τ 1 ), ū(τ 1 )) = 0 and s 2 = #J(ū(τ 1 )) = 0 (we do not pass on 92 Appendix B. Maximum principle for problems with mixed constraints the indexing of s 1 and s 2 with respect to k and q to avoid too cumbersome notations), we introduce the classical needle perturbation: ūI 1 ū τ 1 -εl 1 v I 1 , defined on the interval [0, τ 1 [, with v I 1 arbitrarily chosen in U (x (ū,x 0 ) (τ 1 -εl 1 )) and constant over [τ 1 -εl 1 , τ 1 [. We denote by ξ I 1 = x (ū I 1 ,x 0 ) (τ 1 ).

Otherwise, by remarking that s 1 and s 2 are such that max(s 1 , s 2 ) > 0, according to (A3.4), define the function

Sur les barrières des systèmes non linéaires sous contraintes avec une application aux systèmes hybrides

Résumé de la thèse: Cette thèse est consacrée à l'étude de la théorie des barrières pour les systèmes non linéaires sous contraintes d'entrées et d'état. La principale contribution concerne la généralisation au cas de contraintes mixtes, c'est-à-dire dépendant des entrées et de l'état de façon couplée. Ce type de contraintes apparaît souvent dans les applications et dans les systèmes différentiellment plats sous contraintes. On prouve un théorème du type principe du minimum qui permet de construire la barrière et l'ensemble admissible associé. De plus, dans le cas d'intersection de plusieurs trajectoires ainsi construites, on démontre que les points intersections transversaux sont des points d'arrêt de la barrière.

Ces résultats sont utilisés pour calculer l'ensemble admissible d'un pendule avec un câble non-rigide monté sur un chariot, la contrainte correspondant au fait que le câble reste tendu. Ce probléme correspond en fait à la détermination de l'ensemble potentiallement sûr dans le cadre des systèmes hybrides.

Mots clés

Barrières, Systèmes non linéaires, contraintes sur l'état et les entrées, contraintes mixtes, ensemble admissible, points d'arrêt, ensemble potentiellement sûr On Barriers in Constrained Nonlinear Systems with an Application to Hybrid Systems.

Abstract: This thesis deals with the theory of barriers in input and state constrained nonlinear systems. Our main contribution is a generalisation to the case where the constraints are mixed, that is they depend on both the input and the state in a coupled way. Constraints of this type often appear in applications, as well as in constrained flat systems. We prove a minimumlike principle that allows the construction of the barrier and the associated admissible set. Moreover, in case of intersection of some of the trajectories involved in this principle, we prove that such transversal intersection points are stopping points of the barrier. We demonstrate the utility of all the theoretical contributions by finding the admissible set for the pendulum on a cart with a non-rigid cable, the constraint being that the cable remains taut. Note that this problem corresponds to the determination of potentially safe sets in hybrid systems.