Olivier Bokanowski

Nicolas Forcadel
email: forcadel@ceremade.dauphine.fr

AND Hasnaa Zidani
email: hasnaa.zidani@ensta.fr

REACHABILITY AND MINIMAL TIMES FOR STATE CONSTRAINED NONLINEAR PROBLEMS WITHOUT ANY CONTROLLABILITY ASSUMPTION

Keywords: Minimal time problem, Hamilton-Jacobi-Bellman equations, Level set method, Reachability set (Attainable set), State constraints, Two-player game AMS subject classifications. 93B03, 49J15, 35A18, 65N15, 49Lxx

We consider a target problem for a nonlinear system under state constraints. We give a new continuous level-set approach for characterizing the optimal times and the backward-reachability sets. This approach leads to a characterization via a Hamilton-Jacobi equation, without assuming any controllability assumption. We also treat the case of time-dependent state constraints, as well as a target problem for a two-player game with state constraints. Our method gives a good framework for numerical approximations, and some numerical illustrations are included in the paper.

1. Introduction. This paper studies a simple way to characterize the reachable sets and the optimal time to reach a target for a controlled non linear system where the state is constrained to stay in a given domain. We are mainly interested in the case where no "controllability" assumption is made.

More precisely, we consider a control system: ẏ(s) = f (y(s), α(s)), for a.e. s ≥ 0, y(0

) = x, (1.1)
where α : (0, +∞) → A is a measurable function, A is a given compact set in R m (set of admissible controls), and the dynamics f : R d × A → R d . In all the sequel, for any initial position x, we denote by y α x the solution of (1.1) associated to the control variable α. Let C ⊂ R d be a closed target and let K ⊂ R d be a closed set of state constraints. For a given time t ≥ 0, we consider the capture basin (backward reachable set) defined by: Cap C (t) := {x ∈ R d | ∃α ∈ L ∞ ((0, t); A), y α x (τ ) ∈ C and y α x (θ) ∈ K, ∀θ ∈ [0, t]}. (1.

2)

It is well known that the set Cap C (τ ) is linked to a control problem. Indeed, consider a Lipschitz continuous function ϑ 0 : R d → R such that

ϑ 0 (x) ≤ 0 ⇐⇒ x ∈ C, (1.3)
and consider the control problem:

u(x, t) := inf{ϑ 0 (y α x (t)) | α ∈ L ∞ ((0, t); A), y α x (θ) ∈ K, ∀θ ∈ [0, t]}.

(1.4)

Then it is not difficult to prove that

Cap C (t) = {x ∈ R d , u(x, t) ≤ 0}.
For the unconstrained case, several works have been devoted to the characterization of the value function u as a continuous viscosity solution of a Hamilton-Jacobi equation [START_REF] Falcone | Level sets of viscosity solutions : some applications to fronts and rendez-vous problems[END_REF][START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi[END_REF][START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF]. In presence of state constraints, the continuity of this value function is no longer satisfied, unless the dynamics satisfy a special controllability assumption on the boundary of the state constraints. This assumption called "inward pointing qualification condition (IQ)" was first introduced by Soner in [START_REF] Soner | Optimal control with state-space constraint[END_REF]. It asks that at each point of K there exists a field of the system pointing inward K. Clearly this condition ensures the viability of K (from any initial condition in K, there exists an admissible trajectory which could stay for ever in K). Under this assumption, the value function u is the unique continuous constrained viscosity solution of a HJB equation with a suitable new boundary condition [START_REF] Soner | Optimal control with state-space constraint[END_REF][START_REF] Soner | Optimal control with state-space constraint[END_REF][START_REF] Ishii | A new formulation of state constraint problems for first-order PDEs[END_REF][START_REF] Capuzzo-Dolcetta | Hamilton-Jacobi equations with state constraints[END_REF][START_REF] Motta | On nonlinear optimal control problems with state constraints[END_REF].

Unfortunately, in many control problems, the condition (IQ) is not satisfied and the value function u could be discontinuous. In this framework, Frankowska introduced in [START_REF] Frankowska | Semicontinuous solutions of Hamilton-Jacobi-Bellman equations with degenerate state constraints[END_REF] another controllability assumption, called "outward pointing condition (OQ)". Under this assumption it is still possible to characterize the value function as the unique lower semicontinuous (for short lsc) solution of an HJB equation.

In absence of any assumption of controllability, the function u is discontinuous and its characterization becomes more complicate, see for instance [START_REF] Barles | Exit time problems in optimal control and vanishing viscosity method[END_REF][START_REF] Soravia | Optimality principles and representation formulas for viscosity solutions of Hamilton-Jacobi equations.ii. equations of control problems with state constraints[END_REF][START_REF] Bokanowski | Value function characterisations for some deterministic state constraint optimal control problems without controllability assumptions[END_REF] and the references therein. In [START_REF] Cardaliaguet | Optimal times for constrained nonlinear control problems without local controllability[END_REF], the authors proved that the minimal time function for a state constrained control problem, without any controllability assumption, is the smallest non-negative lsc supersolution of an HJB equation. This characterization leads to a numerical algorithm based on the viability approach [START_REF] Cardaliaguet | Numerical schemes for discontinuous value function of optimal control[END_REF][START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF].

In this paper, we are interested in the case where no controllability assumption is assumed. We show that it is possible to characterize the capture basin Cap C by means of a control problem whose value function is continuous (even Lipschitz continuous). For that, we consider a continuous function g : [R d × 0, +∞[→ R such that1 g(x) ≤ 0 ⇐⇒ x ∈ K.

(

Then we consider the new control problem: ϑ(x, t) := inf{max(ϑ 0 (y α x (t)), max θ∈[0,t] g(y α x (θ))) | α ∈ L ∞ ((0, t); A)}.

(1.6)

We prove that the value function ϑ is the unique continuous viscosity solution of the equation: min ∂ t ϑ(x, t) + H(x, D x ϑ(x, t)), ϑ(x, t)g(x)) = 0 for t

∈ [0, +∞[, x ∈ R d , (1.7a) ϑ(x, 0) = max(ϑ 0 (x), g(x)). (1.7b)
Moreover, the capture basin is given by Cap C (t) = {x ∈ R d | ϑ(x, t) ≤ 0}, and the minimal time for a given x ∈ R d to reach the target while remaining in the set of state constraints is obtained by: T (x) = inf{t ∈ [0, +∞[ | ϑ(x, t) ≤ 0}. This continuous setting opens a large class of numerical schemes to be used for such problems (such as Semi-Lagrangian or finite differences schemes).

A similar idea of introducing a control problem in the form of (1.6) is also introduced in [START_REF] Kurzhanski | A time-dependent Hamiliton-Jacobi formulation of reachable sets for continuous dynamic games[END_REF]. However, in that paper, the analysis is a little bit more complicated and did not lead to a simple PDE for characterizing ϑ (the obstacle function is also assumed convex in [START_REF] Mitchell | A time-dependent Hamiliton-Jacobi formulation of reachable sets for continuous dynamic games[END_REF]). Also, control problems with maximum cost have already studied by Barron and coauthors.

The main feature of our paper is the use of (1.6) to deal easily with minimal time problems with state constraints, and to determine the corresponding capture basins. This idea generalizes in some sense the known level-set approach usually used for unconstrained problems.

The paper is organised as follows. In Section 2, we introduce the problem and give the main results. In this section we precise also the assumptions and fix the notations that will be used in the sequel. The proof of the main results are given in Section 3. We then give some extensions of the previous results. In Section 4, we shall discuss the case of time-dependent state constraints of the form

y α x (θ) ∈ K θ , ∀θ ∈ [0, t],
where the sets (K θ ) θ≥0 can evolve in time (assuming some regularity of the map θ K θ ). The case of two-player games with state constraints will be also discussed in the appendix. Numerical approximation is studied in Section 5, and an error estimate is derived. Finally, we give some numerical illustrations in Section 6.

Main results . Let

A be a nonempty compact set in R m , for m ≥ 1. We consider function f ∈ C(R d × A; R d ) satisfying the following assumptions: (throughout the paper | • | is a given norm on R d ) (H1) there exists L f > 0, such that for every (x, x ′ , a) ∈ R d × R d × A, |f (x, a) -f (x ′ , a)| ≤ L f |x -x ′ |, |f (x, a)| ≤ L f . (H2) For every y ∈ R d , f (y, A) is a convex set of R d .
Assumption (H2) is made just to simplify the presentation of the main ideas. All the results of the paper can be extended to the case when (H2) does not hold. Also the boundedness of f can be weakened, and only a linear growth property

"|f (x, a)| ≤ L f (1 + |x|)" is needed.
Let C be a nonempty closed set of R d (the "target"), and let also K be a nonempty closed set (of "state constraints"). Now, for t ≥ 0, we define the capture basin as the set of all initial points x from which starts a trajectory y α x (•) solution of (1.1), associated to an admissible control α ∈ L ∞ ((0, t); A), and such that y α x (t) ∈ C while y α x (θ) belongs to the set of constraints K, for every θ ∈ [0, t]:

Cap C (t) := x ∈ R d , ∃α ∈ L ∞ ((0, t); A), y α x (t) ∈ C and y α x (θ) ∈ K, ∀θ ∈ [0, t] ,
In this problem, the trajectory should belongs to the (fixed) set of state-constraints K. In all the sequel, we will use the following definition of admissible trajectory: Definition 2.1. Let t be a fixed positive time. We will say that a solution of (1.1) y α

x is admissible on [0, t], if it is associated to an admissible control α ∈ L ∞ ((0, ∞); A) and y α

x (θ) belongs to K for every θ ∈ [0, t]. Remark 1. For every t ≥ 0, the set Cap C (t) contains the initial positions which can be steered to the target (exactly) at time t. Of course, we can also define the "backward reachable set", which is the set of points from which one can reach the target C before time t:

R([0, t]) := x ∈ R d , ∃τ ∈ [0, t], ∃α ∈ L ∞ ((0, τ ); A), y α x (τ ) ∈ C and y α x (θ) ∈ K, ∀θ ∈ [0, τ ] . (R([0, t])) t≥0 is a family of increasing closed sets, with R([0, 0]) = C. If we consider the new dynamics F : R d × Ã → R d by F (x, (α, β)) := βf (x, α) for (α, β) ∈ Ã = A × [0, 1]
. Then, we can remark that R([0, t]) is exactly the capture basin associated to the dynamics F (see for instance [START_REF] Mitchell | A time-dependent Hamiliton-Jacobi formulation of reachable sets for continuous dynamic games[END_REF]).

In this paper, we propose to use the level set approach in order to characterize Cap C (t) as the negative region of a continuous function ϑ, i.e., we look for a continuous function such that Cap C (t) = {x, ϑ(x, t) ≤ 0} .

To do so, we first consider a Lipschitz continuous function ϑ 0 : R d → R such that

ϑ 0 (x) ≤ 0 ⇔ x ∈ C. (2.1)
For instance we may choose ϑ 0 (x) := d C (x) (where for any closed set K ⊂ R d , d K (x) denotes the signed distance function to K, i.e., with d K (x) := d(x, K) > 0 for x / ∈ K, and

d K (x) := -d(x, R d \K) < 0 for x ∈ • K)
, then ϑ 0 is Lipschitz continuous (see for instance [START_REF] Delfour | Shape analysis via oriented distance functions[END_REF]). In particular, we have Cap

C (0) = C = {x, ϑ 0 (x) ≤ 0}.
Consider the value function u associated to the Mayer problem with final cost ϑ 0 :

u(x, t) := inf{ϑ 0 (y α x (t)), α ∈ L ∞ ((0, t); A), y α x (θ) ∈ K, ∀θ ∈ [0, t]}. (2.2)
It is well known that the capture basin is characterized by

Cap C (t) = {x, u(x, t) ≤ 0}.
However, function u is a value function of a state-constrained problem, and we are still faced to the problem of characterizing this value function if no controllability assumption is made.

To overcome this difficulty, we consider another Lipschitz continuous function g :

R d → R such that g(x) ≤ 0 ⇔ x ∈ K. (2.3)
Note that such a function always exists since we can choose g(x) := d K (x).

We then consider the control problem: ϑ(x, t) := inf max ϑ 0 (y α x (t)), max θ∈[0,t] g(y α x (θ)) , α ∈ L ∞ ((0, t); A) .

(2.4) Problem (2.4) has no "explicit" state constraint. In fact, in this new setting, the term max θ∈[0,t] g(y α x (θ)) plays a role of a penalization that a trajectory y α x would pay if it violates the state-constraints. We will see in Theorem 2, that the advantage of considering (2.4) is that ϑ can be now characterized as the unique continuous solution of an HJB equation.

The central idea of the paper is that the function ϑ(•, t) and u(•, t) have same negative regions and so we have the following characterisation of the capture basin:

Theorem 1 (Characterization of the capture basin). Assume (H1)-(H2). Let ϑ 0 and g be Lipschitz continuous functions defined respectively by (2.1) and (2.3). Let u and ϑ the value functions defined respectively by (2.2) and (2.4). Then, for every t ≥ 0, we have:

(i) the capture basin is given by

Cap C (t) = {x, u(x, t) ≤ 0} = {x, ϑ(x, t) ≤ 0}.
(ii) if ϑ(x, t) < 0 and

• K= {x, g(x) < 0}, then u(x, t) < 0, and there exists, on [0, t], an admissible trajectory y α that does never touch the boundary ∂K.

Remark 2. Let us point out that the zero level sets of u and ϑ may not coincide. In particular, when there is an optimal trajectory y α that touches the boundary ∂K, we can have u(x, t) < 0 and ϑ(x, t) = 0 (hence the converse of Theorem 1(ii) is false). This is illustrated in Example 1.

Let us also point out that this theorem allows us to characterize the minimal time function to reach the target from a point x ∈ R d with an admissible trajectory y α x solution of (1.1) and satisfying y α x (θ) ∈ K:

T (x) := inf{t ≥ 0, ∃α ∈ L ∞ ((0, t); A), y α x (t) ∈ C and y α x (θ) ∈ K, ∀θ ∈ [0, t]}. (2.5)
Many works have been devoted to the regularity of the minimum time function T . When K ≡ R d , and under some local metric properties around the target, the function T is the unique continuous viscosity solution of an HJB equation [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF].

Here, without assuming any controllability assumption at the boundary of the target, neither at the boundary of K, the function T may be discontinuous. Indeed, if, for x ∈ R d , no trajectory y α

x reaches the target C or if any trajectory leaves K before reaching the target, we set T (x) = +∞. Nevertheless, the next proposition states that T is lower semicontinuous and characterizes it by using the knowledge of the function ϑ.

Proposition 1. Assume (H1)-(H2). The minimal time function T : R d -→ R + ∪ +∞ is lsc. Moreover, we have:

T (x) = inf{t ≥ 0, x ∈ Cap C (t)} = inf{t, ϑ(x, t) ≤ 0},
with ϑ the value function defined in (2.4), where ϑ 0 and g are any Lipschitz functions satisfying respectively (2.1) and (2.3).

Remark 3. The idea of using an auxiliary value function to define the minimal time function is not new by itself. For instance, we refer to [START_REF] Barron | Viscosity solutions and analysis in L ∞[END_REF] when the minimal time function for an unconstrained control problem is obtained by using a new function G(x, t) which gives the minimum distance that an optimal trajectory, starting from x, comes to the target over the time interval [0, t]. On the other hand, the use of a level-set approach is a standard way to determine the minimal time function of unconstrained control problems [START_REF] Falcone | Level sets of viscosity solutions : some applications to fronts and rendez-vous problems[END_REF].

In our work, we generalize this point of view to the case when the time control problem is in presence of state constraints. Our formulation allows also to obtain the capture basins.

As mentioned before, the function ϑ can be characterized as the unique solution of a Hamilton-Jacobi equation. More precisely, considering the Hamiltonian

H(x, p) := max α∈A -f (x, α) • p , (2.6)
we have Theorem 2. Assume (H1)-(H2), and that ϑ 0 and g are Lipschitz continuous. Then ϑ is the unique continuous viscosity solution (see Definition 1) of the variational inequation (obstacle problem)

min(∂ t ϑ + H(x, ∇ϑ), ϑ -g(x)) = 0, t ≥ 0, x ∈ R d , (2.7a) ϑ(x, 0) = max(ϑ 0 (x), g(x)), x ∈ R d . (2.7b) Remark 4.
As function ϑ is associated to a control problem without state constraints, the statement of the above theorem remains true if assumption (H2) is not satisfied. Here, we assume this assumption just to simplify the proof we give in Section 3. Also, it is known that when (H2) does not hold, lower semicontinuity of T is no-longer true. In this case, the result of Proposition 1 is satisfied by the lower semicontinuous envelope T * (see [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF]).

Remark 5. In practice, the target C is a subset of K and in this case, it is always possible to choose ϑ 0 and g in such a way that ϑ 0 ≥ g.

Inequalities such (2.7) appear also in the framework of exit time problems where the obstacle g represent the exit cost that should be paid for exit. Here, g is a "fictitious cost" that a target would pay if it leaves K.

Remark 6. From a theoretical point of view, the choice of g is not important, and g can be any Lipschitz function satisfying (2.3). Of course, the value function ϑ is dependent on g, while the set {x ∈ R d , ϑ(x, t) ≤ 0} does not depend on g.

Let us also point out that the obstacle term in (2.7) comes from the presence of the sup-norm max θ∈[0,t] g(y α

x (θ)) in the cost function which defined ϑ (see (2.4)). We refer to the works of Barron and Ishii [START_REF] Barron | The Bellman equation for minimizing the maximum cost[END_REF] and the references therein for optimal control problems with sup-norm cost functions.

Proofs of the main results.

Proof of Theorem 1.

(i) Assume that u(x, t) ≤ 0. Then by definition of u, there exists an admissible trajectory y α x such that ϑ 0 (y α x (t)) ≤ 0, and

y α x (θ) ∈ K for every θ ∈ [0, t].
Hence, max θ∈[0,t] g(y α x (θ)) ≤ 0, and we have:

ϑ(x, t) ≤ max(ϑ 0 (y α x (t)), max θ∈[0,t] g(y α x (θ))) ≤ 0.
Conversely, assume that ϑ(x, t) ≤ 0. Then there exists a trajectory y α x such that

0 ≥ ϑ(x, t) = max(ϑ 0 (y α x (t)), max θ∈[0,t] g(y α x (θ))).
Thus, for all θ ∈ [0, t], g(y α x (θ)) ≤ 0, i.e. y α x (θ) ∈ K, and so y α x is an admissible trajectory. Moreover, we have ϑ 0 (y α x (t)) ≤ 0, hence u(x, t) ≤ ϑ 0 (y α x (t)) ≤ 0.

(ii) The proof uses similar arguments as in (i).

The following example show that the converse of Theorem 1 (ii) is false in general, i.e. we can have ϑ(x, t) = 0 and u(x, t) < 0.

Example 1.

Consider f = (1, 1) T , the target C = [1, 2] 2 , the constraint set K := R 2 \(] -1, 0[×]0, 1[),
and x := (-1, -1). We assume that ϑ 0 < 0 on the interior • C of C. In this example, we do not have any control variable and the only possible trajectory starting from x is the one defined by: y

x (t) = x + 1 1 t. At time t = 2.5 we have y x (t) = (1.5, 1.5) T ∈ • C and then u(x, t) = ϑ 0 (y x (t)) < 0.
On the other hand, since y x (1) = (0, 0) ∈ ∂K, we have max θ∈[0,t] g(y x (θ)) = 0, thus ϑ(x, t) = 0 (see Fig. 3.1).

We now give, for seek of completeness, the proof for Proposition 1.

Proof of Proposition 1. The lower semicontinuity of T has been already proved in [START_REF] Cardaliaguet | Optimal times for constrained nonlinear control problems without local controllability[END_REF]. Let T (x) := inf{t ≥ 0, x ∈ Cap C (t)}. The fact that T (x) = inf{t, ϑ(x, t) ≤ 0} = inf{t, u(x, t) ≤ 0} is a consequence of Theorem 1(i) and of the definition of Cap C (t). It remains just to prove that T (x) = T (x). Let t := T (x). Since t is the minimal time, by using compacity arguments as in [START_REF] Saint-Pierre | Approximation of the viability kernel[END_REF], there exists an admissible trajectory y α

x , such that y α x (t) ∈ C. Hence ϑ(x, t) ≤ ϑ 0 (y α x (t)) ≤ 0, and thus T (x) ≤ t = T (x).

On the other hand, let t := T (x). For any n ≥ 1, there exists some t n ∈ [ t, t + 1 n ] such that ϑ(x, t n ) ≤ 0. We can consider an associated optimal trajectory y n := y αn x such that y αn

x is admissible and y αn x (t n ) ∈ C. By using again a compacity argument, and since K and C are closed subsets, we can extract a convergent subsequence and an admissible trajectory y, such that y n → y uniformly on [0, t], and y( t) ∈ C. Hence T (x) ≤ t, which concludes the proof.

Before giving the proof of Theorem 2, we need the following dynamic programming principle (DPP) for ϑ Lemma 1 (Dynamic Programming Principle). The function ϑ is characterized by (i) for all t ≥ 0 and τ ≥ 0, for all x ∈ R d ,

ϑ(x, t + τ ) = inf max ϑ(y α x (τ ), t), max θ∈[0,τ ] g(y α x (θ)) , α ∈ L ∞ ((0, τ ); A) , (ii) ϑ(x, 0) = max(ϑ 0 (x), g(x)).
Proof. One can refer for instance to Barron and Ishii [START_REF] Barron | The Bellman equation for minimizing the maximum cost[END_REF]Proposition 3.1].

The first consequence of the above lemma is the Lipschitz continuity of the value function ϑ:

Proposition 2. Assume (H1)-(H2). Let ϑ 0 and g are Lipschitz continuous functions satisfying (2.1) and (2.3). Let ϑ the value function defined as in (2.4). For every

T > 0, ϑ is Lipschitz continuous on R d × [0, T ].
Proof. Let T > 0 and let x, x ′ ∈ R d and t ∈ [0, +∞[. By using the definition of ϑ and the simple inequalities:

max(A, B)-max(C, D) ≤ max(A-C, B-D), and inf A α -inf B α ≤ sup(A α -B α ) (3.1)
we get:

|ϑ(x, t) -ϑ(x ′ , t)| ≤ sup α(•)∈A max ϑ 0 (y α x (t)) -ϑ 0 (y α x ′ (t)) , max θ∈[0,t] g(y α x (θ)) -g(y α x ′ (θ)) , ≤ sup α(•)∈A L 0 y α x (t) -y α x ′ (t) , L g max θ∈[0,t] y α x (θ) -y α x ′ (θ)
where L 0 and L g denotes respectively the Lipschitz constant of ϑ 0 and g. By assumption (H1), we know that

|y α x (θ) -y α x ′ (θ)| ≤ e L f θ |x -x ′ |.
Then we conclude that:

|ϑ(x, t) -ϑ(x ′ , t)| ≤ max(L 0 , L g )e L f T |x -x ′ |, (3.2)
for any x, x ′ ∈ R d and any t ∈ [0, T ] for T ≥ 0. Now, let x ∈ R d , and t, h ≥ 0. Remarking that ϑ(x, t) ≥ g(x), we deduce from Lemma 1 that

|ϑ(x, t + h) -ϑ(x, t)| = inf α max ϑ(y α x (h), t), max θ∈[0,h] g(y α x (θ)) -max ϑ(x, t), g(x) ≤ sup α max ϑ(y α x (h), t) -ϑ(x, t) , max θ∈[0,h] g(y α x (θ)) -g(x) ≤ L f max(max(L 0 , L g )e L f T , L g )h
where we have used (3.2) and assumption (H1). This completes the proof. Now, we recall the definition of viscosity solution for (2.7). Let us first recall the definition of the upper semi-continuous (usc for short) envelope and the lower semi-continuous (lsc for short) envelope of a locally bounded function u: Definition 1 (Viscosity solution). An upper semi-continuous (resp. lower semicontinuous) function ϑ : R d × R + → R is a viscosity subsolution (resp. supersolution) of (2.7) if ϑ(x, 0) ≤ ϑ 0 (x) in R d (resp. ϑ(x, 0) ≥ ϑ 0 (x)) and for any (x, t) ∈ R d × (0, ∞) and any test function φ ∈ C 1 (R d × R + ) such that ϑφ attains a maximum (resp. a minimum) at the point (x, t) ∈ R d × (0, +∞), then we have

min(∂ t φ + H(x, ∇φ), ϑ -g(t, x)) ≤ 0 (resp. min(∂ t φ + H(x, ∇φ), ϑ -g(t, x)) ≥ 0) .
A continuous function ϑ is a viscosity solution of (2.7) if ϑ is a viscosity subsolution and a viscosity supersolution of (2.7).

We now give the proof of Theorem 2:

Proof of Theorem 2. The proof can be deduced from [START_REF] Barron | The Bellman equation for minimizing the maximum cost[END_REF]Proposition 2.6]. Here, we give the main lines of a direct proof for completeness. We first show that ϑ is a solution of (2.7). The fact that ϑ satisfies the initial condition is a direct consequence of Lemma 1(ii).

Let us check the supersolution property of ϑ. By Lemma 1(i), we get that for any τ ≥ 0

ϑ(x, t + τ ) ≥ inf α ϑ(y α x (τ ), t).
Hence, with classical arguments, we can obtain

∂ t ϑ + H(x, ∇ϑ) ≥ 0
in the viscosity sense. Moreover, by definition of ϑ, for every (x, t) ∈ R d × R + , we have

ϑ(x, t) ≥ inf α max θ∈[0,t] g(y α x (θ)) ≥ g(x).
Combining this two inequalities, we get min(∂ t ϑ + H(x, ∇ϑ), ϑ(x, t)g(x)) ≥ 0 in the viscosity sense, i.e., ϑ is a supersolution of (2.7).

Let us now prove that ϑ is a subsolution. Let x ∈ R d and t > 0. If ϑ(x, t) ≤ g(x), it is obvious that ϑ satisfies:

min(∂ t ϑ + H(x, ∇ϑ), ϑ(x, t) -g(x)) ≤ 0.
Now, assume that ϑ(x, t) > g(x). By continuity of g and ϑ, there exists some τ > 0 such that ϑ(y α x (θ), t) > g(y α x (θ)) for all θ ∈ [0, τ ] (since y α x (θ) will stay in a neighbourhood of x which is controlled uniformly with respect to α). Hence, by using Lemma 1(i), we get that

ϑ(x, t + h) = inf α ϑ(y α x (h), t), for any 0 ≤ h ≤ τ.
We then deduce by classical arguments [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF] that ∂ t ϑ(x, t)+H(x, ∇ϑ(x, t)) ≤ 0 in the viscosity sense. Therefore, ϑ is a viscosity subsolution of (2.7).

The fact that ϑ is the unique solution of (2.7) follows from the comparison principle for (2.7) (which is classical, see for instance [START_REF] Barles | Solutions de viscosité des équations de Hamilton-Jacobi[END_REF]), and the fact that the Hamiltonian function H satisfies

|H(x 2 , p) -H(x 1 , p)| ≤ C(1 + |p|) |x 2 -x 1 |, (3.3a) |H(x, p 2 ) -H(x, p 1 )| ≤ C|p 2 -p 1 |, (3.3b)
for some constant C ≥ 0 and for all x i , p i , x and p in R d .

4. Time-dependant state constraints. Let (K θ ) θ≥0 be a family of closed subsets of R d . We assume that:

(H3) the set-valued application θ K θ is Lipschitz continuous2 on [0, +∞[. For x ∈ K 0 , we consider the trajectories solution of (1.1) and satisfying the timedependant constraints:

y α x (θ) ∈ K θ , ∀θ ∈ [0, t]. (4.1)
An example of such a situation, is the case where we want to avoid a mobile obstacle located at every θ ≥ 0 at the open subset O θ , while remaining in a given closed set K ⊂ R d . In this case, we should set

K θ := K \ O θ .
Now, let us define the minimal time function :

T ♯ (x) = min{t ≥ 0 | ∃α ∈ L ∞ (0, t; A), y α x (t) ∈ C and y α x (θ) ∈ K θ for θ ∈ [0, t]}.
In this setting, the function T ♯ can not be characterized by an HJB equation. The reason for that comes from the time-dependency of the state-constraints. Actually, function T ♯ even does not satisfy the dynamic programming principle (this is also the case of the minimal time function of non-autonomous systems, see [START_REF] Bokanowski | Minimum time control problems for non autonomous differential equations[END_REF]). Also, here we cannot use the ideas developed in the previous sections to determine the capture basins. Nevertheless, we shall see that a problem similar to (2.4) can be used to determine the reachable sets.

Let D be a given nonempty closed set of R d (D can be a singleton). For t ≥ 0, we consider the attainable set (or, reachability region) starting from D , defined as the set of points that can be reached at time t by a trajectory starting from D and satisfying the time-dependant state constraint (4.1), i.e.

Att D (t) := y α x (t) ∈ R d , x ∈ D, ∃α ∈ L ∞ ((0, t); A), y α x (θ) ∈ K θ , ∀θ ∈ [0, t] .
As in Section 2, we consider a Lipschitz continuous function g ♯ : [0, +∞[×R d such that, ∀θ ≥ 0,

g ♯ (x, θ) ≤ 0 ⇔ x ∈ K θ . (4.2)
Such a function always exists since we can choose g ♯ (x, θ) := d K θ (x) (note that by assumption (H3), the sign distance function to K θ is also Lipschitz continuous in both variables (x, θ)).

We also consider ϑ ♯ 0 : R d → R such that

ϑ ♯ 0 (x) ≤ 0 ⇐⇒ x ∈ D. (4.3)
We then consider the following control problem:

ϑ ♯ (x, t) := inf max ϑ ♯ 0 (y α x (t)), max θ∈[0,t] g ♯ (y α x (θ), θ) , α ∈ L ∞ ((0, t); A) . (4.4)
Similar arguments, as in Section 2, lead to: Theorem 3. Let t ≥ 0. The attainable set is characterized by

Att D (t) = x, ϑ ♯ (x, t) ≤ 0 , ∀t ≥ 0.
Theorem 4. We assume (H1)-(H3). Let ϑ ♯ 0 and g ♯ be Lipschitz continuous functions satisfying respectively (4.3) and (4.2). Let H ♯ be defined by H ♯ (x, p) := max α∈A f (x, α) • p. Then ϑ ♯ is the unique continuous viscosity solution of

min(∂ t ϑ + H ♯ (x, ∇ϑ), ϑ -g ♯ (x, t)) = 0, t ≥ 0, x ∈ R d , (4.5a) ϑ(x, 0) = max(ϑ ♯ 0 (x), g ♯ (x, 0)), x ∈ R d . (4.5b) Remark 7.
It is worth to remark that the HJB inequality (4.5) (with a time-dependant obstacle function g ♯ ) allows to determine the reachable sets and not the capture basins.

Remark 8. For x ∈ K 0 , if we want to know the minimal time needed to reach the target C, starting from x and satisfying the state-constraints (4.1), we should consider D = {x} and set ϑ ♯ 0 (y) := d(x, y) (this is the signed distance to the set D := {x}). Then let ϑ ♯ be the solution of (4.5) and where g ♯ represents the time-dependent state constraints. In that case, the set of points that can be reached at time t and starting from x is Att {x} (t) := {x, ϑ ♯ (x, t) ≤ 0} (which also identical to {x, ϑ ♯ (x, t) = 0} in this specific case). Finally we can recover the minimal time to reach C as T (x) := inf t ≥ 0, Att {x} (t) ∩ C = ∅ . 5. Numerical scheme and error estimates. In this section we propose a finite difference scheme to approximate the solution u of (2.7) or (4.5). In this section H : R d × R d → R is only assumed to be a given continuous function satisfying (3.3).

For given mesh sizes ∆x > 0, ∆t > 0, we define

G := {I∆x, I ∈ Z d }
where N T is the integer part of T /∆t. The discrete running point is (x I , t n ) with x I = I∆x, t n = n∆t. The approximation of the solution ϑ at the node (x I , t n ) is written indifferently as v(x I , t n ) or v n I according to whether we view it as a function defined on the lattice or as a sequence. Now, given a numerical Hamiltonian H : R d × R d × R d → R (which will be a consistent approximation of the Hamiltonian H), we consider the following scheme

       min v n+1 I -v n I ∆t + H(x I , D + v n (x I ), D -v n (x I )), v n+1 I -g(x I , t n+1 ) = 0 v 0 I = ũ0 (x I ) (5.1)
where ũ0 is an approximation of ϑ 0 and

D + v n (x I ) = (D + x1 v n (x I ), . . . , D + x d v n (x I )), D -v n (x I ) = (D - x1 v n (x I ), . . . , D - x d v n (x I ))
are the discrete space gradient of the function v n at point x I defined for a general function w by

D ± xi w(x I ) = ± w(x I i,± ) -w(x I ) ∆x , (5.2)
with the notation I k,± = (i 1 , . . . , i k-1 , i k ± 1, i k+1 , . . . , i d ).

We make the following assumptions on the numerical Hamiltonian H: (H4) There exists C 1 > 0 such that for all x I ∈ G, (P In the next section we will give some examples of numerical schemes satisfying (H4) -(H7).

+ , P -) ∈ R d × R d , |H(x I , P + , P -)| ≤ C 1 (|P + | ∞ + |P -| ∞ ) (H5) There exists C 2 > 0 such that for all x I ∈ G, P + , P -, Q + , Q -∈ R d , |H(x I , P + , P -) -H(x I , Q + , Q -)| ≤ C 2 (|P + -Q + | + |P --Q -|).
Remark 9. It is well known that the monotony assumption (H6), together with the following CFL condition:

∆t ∆x d i=1 ∂H ∂P - i (x, P + , P -) + ∂H ∂P + i (x, P + , P -) ≤ 1, a.e. (x, P + , P -) ∈ R d × R d × R d , (5.3
)

ensures that the scheme      v n+1 I -v n I ∆t + H(x I , D + v n (x I ), D -v n (x I )) = 0 v 0 I = ũ0 (x I ) (5.4)
is monotone (i.e, if v is a subsolution of (5.4) and if w is a supersolution of (5.4) and such that v n ≤ w n , then v n+1 ≤ w n+1 ). Furthermore by (H5), we have

| ∂H ∂P ± i | ≤ C 2 and
thus the CFL condition is satisfied as soon as ∆t ∆x ≤ 1/(2dC 2 ). Remark 10. Equation (5.1) implies also that

v n+1 I = max v n I -∆tH(x I , D + v n (x I ), D -v n (x I )), g(x I , t n+1 ) .
We deduce, assuming (H6) and the CFL condition (5.3), that the scheme (5.1) is monotone.

We then have the following error estimate: Theorem 5. (Discrete-continuous error estimate) Assume (H4)-(H7) and that ϑ 0 and g are Lipschitz continuous and bounded. Let T > 0. There exists a constant K > 0 (depending only on

d, C 1 , C 2 , C 3 Dϑ 0 ∞ , Dg ∞ , ϑ 0 ∞ , g ∞ and ∂H
∂p ∞ ) such that if we choose ∆x and ∆t sufficiently small, such that the CFL condition (5.3) holds and

√ T (∆x + ∆t) 1/2 + sup G |ϑ 0 -ũ0 | ≤ 1 K ,
then the error between the solution ϑ of (2.7) (with a Hamiltonian satisfying (3.3)) and the discrete solution v of the finite difference scheme (5.1) satisfies

sup 0≤n≤NT sup G |ϑ n -v n | ≤ K max(T, √ T ) (∆x + ∆t) 1/2 + sup G |ϑ 0 -ũ0 | .
Remark 11. The fact that ϑ 0 and g are bounded is not a restriction since we can truncate them and this will not change the set {x, ϑ(x, t) ≤ 0}.

Proof. The proof is an adaptation of the one of Crandall and Lions [START_REF] Crandall | Two approximations of solutions of Hamilton Jacobi equations[END_REF], revisited by Alvarez et al. [START_REF] Alvarez | A convergent scheme for a non local Hamilton Jacobi equation modelling dislocation dynamics[END_REF]. Nevertheless, for the reader's convenience, we give the main steps to show how to take into account the obstacle. The main idea of the proof is the same as the one of comparison principles, i.e. to consider the maximum of uv, to duplicate the variable and to use the viscosity inequalities to get the result. We consider the case when T ≤ 1 and assume also that ∆x + ∆t ≤ 1.

We first assume that ϑ 0 (x I ) ≥ ũ0 (x I ), for all I ∈ Z d .

(5.5)

and we set

µ 0 := sup G (ϑ 0 -ũ0 ) ≥ 0. (5.6)
We denote throughout by K various constant depending only on d, C 1 , C 2 , C 3 Dϑ 0 ∞ , Dg ∞ , ϑ 0 ∞ , g ∞ and ∂H ∂p ∞ . Since ϑ 0 and g are bounded, we deduce that ϑ is bounded.

The proof is splitted in three steps.

Step 1: Estimate on v. We have the following estimate for the discrete solution

-Kt n -µ 0 ≤ v(x I , t n ) -ϑ 0 (x I ) ≤ Kt n + µ 0 . (5.7)
To show this, it suffice to consider w ± (x I , t n ) = ϑ 0 (x I )±Kt n ±µ 0 and to show that w -(resp. w + ) is a subsolution (resp. a supersolution) of the scheme for K large enough. The result will then follow by the monotonicity of the scheme. Let us prove that w + is a supersolution. In one way, we have

w +,n+1 I -w +,n I ∆t + H(x I , D + w +,n (x I ), D -w +,n (x I )) = K + H(x I , D + ϑ 0 (x I ), D -ϑ 0 (x I )) ≥ K -2C 1 Dϑ 0 ∞ ≥ 0 for K ≥ 2C 1 Dϑ 0 ∞
and where we have used assumption (H4) for the second line.

In the other way, we also have

w + (x I , t n+1 ) -g(x I , t n+1 ) = ϑ 0 (x I ) + Kt n+1 + µ 0 -g(x I , t n+1 ) ≥ ϑ 0 (x I ) -g(x I , 0) + Kt n+1 + g(0, x I ) -g(x I , t n+1 ) ≥ t n+1 (K -Dg ∞ ) ≥ 0 for K ≥ Dg ∞ .
From the two previous inequalities, we deduce that w + is a supersolution of the scheme. Remarking moreover that w(x I , 0) = ϑ 0 + µ 0 ≥ v 0 (x I ) we conclude using the monotonicity of the scheme that

v n I ≤ w n I for all (I, n) ∈ Z d × {0, . . . , N T } i.e. v(x I , t n ) ≤ ϑ 0 (x I ) + Kt n + µ 0 .
To obtain the reverse inequality, we show in a similar way that w -,n+1

I -w -,n I ∆t + H(x I , D -w -,n (x I ), D -w -,n (x I )) ≤ 0, O. Bokanowski, N. Forcadel, H. Zidani
which implies that w -is a subsolution of the scheme, and obtain the desired result.

Before continuing the proof, we need a few notations. We put

µ := sup G (ϑ -v).
We want to bound from above µ by µ 0 plus a constant. We assume that µ > 0 (otherwise the estimate is trivial). For every 0 < α ≤ 1, 0 < ε ≤ 1 and 0 < η ≤ 1, we set

M α,ε η := sup R N ×G×(0,T )×{0,...,tN T } Ψ α,ε η (x, x I , t, t n ) with Ψ α,ε η (x, x I , t, t n ) := ϑ(x, t) -v(x I , t n ) - |x -x I | 2 2ε - |t -t n | 2 2ε -ηt -α(|x| 2 + |x I | 2 ).
We shall drop the superscripts and subscripts on Ψ if there is no ambiguity. We remark that for η and α small enough, we have M α,ε η ≥ µ 2 . Since ϑ and v are bounded (using Step 1 for v), we then deduce that Ψ achieves its maximum at some point that we denote by (x, x I , t, t n ).

Step 2: Estimates for the maximum point of Ψ. Here we show that there exists a constant K > 0 such that the following estimates hold: (5.9)

α(|x| 2 + |x I | 2 ) ≤ K (5.8)
To prove (5.8), it suffices to use the inequality Ψ(x, x I , t, t n ) ≥ Ψ(0, 0, 0, 0) ≥ 0. Indeed, this implies

α(|x| 2 + |x I | 2 ) ≤ ϑ(x, t) -v(x I , t n ) ≤ K.
To prove the first estimate of (5.9), we use the inequality Ψ(x,

x I , t, t n ) ≥ Ψ(x I , x I , t, t n ) to get |x -x I | 2 2ε ≤ ϑ(x I , t) -ϑ(x, t) + α(|x I | 2 -|x| 2 ) ≤ |x -x I |(α(|x I | + |x|) + K) ≤ K|x -x I |
which implies the result. The last inequality is obtained in the same way by using the inequality Ψ(x, x I , t, t n ) ≥ Ψ(x, x I , t n , t n ).

Step 3 : Upper bound of µ. First, we claim that for η large enough, we have either t = 0, or t n = 0 or

µ ≤ K √ T √ ∆x + ∆t.
We argue by contradiction. We suppose that the function (y, s) → Ψ(y, x I , s, t n ) achieves its maximum at a point (x, t) of R N × (0, T ). Then, using the fact that ϑ is a subsolution of (2.7), we deduce that min (p t + H(x, p x + 2αx), ϑ(x, t)g(x, t)) ≤ 0 where

p t = t -t n ε and p x = x -x I ε .
We now distinguish two cases.

Case 1: ϑ(x, t) ≤ g(x, t). Since v is a solution of the scheme, we also have

v(x I , t n ) ≥ g(x I , t n ).
We then deduce that

µ 2 ≤ ϑ(x, t) -v(x I , t n ) ≤ K(|x -x I | + |t -t n |) ≤ Kε.
Choosing ε ≤ √ T √ ∆x + ∆t, we get a contradiction.

Case 2: p t + H(x, p x + 2αx) ≤ 0. In this case, using the fact that

v n+1 I -v n I ∆t + H(x I , D + v n (x I ), D -v n (x I )) ≥ 0,
we deduce using the classical arguments of the proof of Crandall and Lions that

p t + ∆t 2ε ≥ -H x I , p x - ∆x 2ε -α(2x I + ∆x), p x + ∆x 2ε -α(2x I -∆x) . ( 5
≤ K ∆x + ∆t 2ε + K √ α + C 3 |x I -x| ≤ K ∆x + ∆t 2ε + K √ α + Kε
where we have used the Lipschitz continuity of H in p, assumption (H5) for the second line, assumption (H7) and (5.8) for the third one and (5.9) for the last one.

We then deduce that for 1 ≥ η ≥ η * := K ∆x+∆t 2ε + K √ α + Kε, we have either t = 0 or t n = 0. If t = 0, then we have

M α,ε η = Ψ(x, x I , 0, t n ) ≤ ϑ 0 (x) -v(x I , t n ) ≤ Kt n + µ 0 + K|x -x I | ≤ Kε + µ 0 ,
where we have used Step 1, the Lipschitz continuity of ϑ and (5.9). In the same way, if t n = 0, we get

M α,ε η = Ψ(x, x I , t, 0) ≤ ϑ(x, t) -v(0, x I ) ≤ K(|x -x I | + |t|) + µ 0 ≤ Kε + µ 0 .
We obtain that for all (s n , y I ) ∈ {0, . . . , N T ∆t} × G, we have

ϑ(s n , y I ) -v(s n , y I ) -K ∆x + ∆t 2ε + √ α + ε T -2α|y I | 2 ≤ M α,ε η ≤ Kε + µ 0 .
Sending α to 0, taking the supremum over (y In order to conclude the proof in the case T ≥ 1, we remark that since Dϑ ∞ and ϑ ∞ do not depend on time, we can iterate the process and get a linear estimate in T , i.e

I , s n ) ∈ G ×
sup GT |ϑ -v| ≤ K T (∆x + ∆t) 1/2 + sup G |ϑ 0 -ũ0 | .
This ends the proof of Theorem 5.

6. Numerical Simulations. We keep the notations of the previous Section. We now apply finite difference schemes for solving equation (2.7). We consider here the case of dimension d = 2, and the Hamiltonian defined by (2.6). We denote f = (f 1 , f 2 ) the two components of the dynamics f .

In order to ensure convergence of the scheme in the viscosity framework, we need monotony properties (assumption (H6)). A basic standard finite difference scheme is obtained with H(x, P + , P -) := max α∈A max(0, f 1 (x, α))P - 1 + min(0, f 1 (x, α))P + 1 + max(0, f 2 (x, α))P - 2 + min(0, f 2 (x, α))P + 2 .

Then the following scheme

v n+1 I = max v n I -∆tH(x j , D + v n (x I ), D -v n (x I )), g(x I ) , (6.1)
is consistent with (2.7) and satisfies assumptions (H4)-(H7). The CFL condition, which ensures the monotony of the scheme, is then given by ∆t ∆x max

x max α |f 1 (x, α)| + |f 2 (x, α)| ≤ 1.
An other standard scheme is obtained by

v n+1 I = max v n I -∆tH LF (x j , D + v n (x I ), D -v n (x I )), g(x I ) . (6.2)
where H LF is the Lax-Friedrich (LF) Hamiltonian:

H LF (x, P + , P -) := H(x, P

+ + P - 2 ) - C 1 (x) 2 (P + 1 -P - 1 ) - C 2 (x) 2 (P + 2 -P - 2 )
and where C i (x) are chosen such that max P | ∂H ∂Pi (x, P )| ≤ C i (x). Then, under the CFL condition ∆t ∆x max x (C 1 (x) + C 2 (x)) ≤ 1, the scheme is monotone and satisfies (H4)-(H7). Although monotone schemes ensure convergence properties as well as error estimates, they are at most of first order [START_REF] Godlewski | Hyperbolic Systems of Conservation Laws[END_REF]. This can lead to numerical diffusion problems as time increases. One way to diminish this diffusion problem is to use higher order ENO schemes as proposed by Osher and Shu [START_REF] Osher | High essentially nonoscillatory schemes for Hamilton-Jacobi equations[END_REF]. Instead of (6.2), the scheme can be formulated as follows:

v n+1 I = max v n I -∆tH LF (x j , Dv + n (x I ), Dv - n (x I )), g(x I ) , (6.3)
where Dv ± n (x I ) correspond to higher order numerical approximations of the derivatives ∂v ∂x i (this can also be coupled with a Runge-Kutta time discretization scheme). The scheme (6.3) is not necessarily monotone, and its convergence is not proved. Its relevance is proved in many numerical experiments (see [START_REF] Osher | High essentially nonoscillatory schemes for Hamilton-Jacobi equations[END_REF] and Example 1 below).

In our illustrations, except otherwise precised, we shall use a second order ENO scheme [START_REF] Osher | High essentially nonoscillatory schemes for Hamilton-Jacobi equations[END_REF], denoted "ENO2".

Example 1: (Backward reachable set with obstacle.) In this example we compute the backward reachable set for the target C which is the ball centered at (1, 1) of radius 0.5, and with a rotation-type dynamics: f (x, y) = 2π(-y, x). We also consider an obstacle which is the square centered in (-0.5, 0) and of length 0.8.

In Fig. 6.1, we use the first-order LF scheme, and the number of mesh points (M x × M y ) is either 100 2 or 200 2 We observe a numerical convergence towards the exact front, but at a slow rate. In Fig. 6.2, we use the second-order ENO2 scheme, with 100 2 mesh points. We see that the result is greatly improved. Remark 12. From a numerical point of view, it is also possible to consider that the dynamics vanishes on the obstacle, thus replacing the dynamics f by f 1 K and solving the equation In Fig 6 .3, we have compared this approach, using the dynamics f 1 K instead of f , with our approach on Example 1 and with the second order ENO2 scheme. The obstacle is now the square centered in (-0.5, 0.3) and of length 1.0. We observe that when the backward reachable region becomes narrow, the numerical results based on (6.4) are less accurate than the ones obtained by solving (2.7). The problem comes from the fact that setting f = 0 on the obstacles creates discontinuities in the corresponding solution u, and the scheme may not behave very well in this case. Example 2: In this second example we consider a simplified Zermelo problem: a swimmer wants to reach the target C := B(0, r) which is the ball centered at the origin and of radius r = 0.25. The dynamics, depending on a control α ∈ [0, 2π], is given by f (x, y, α) = (c + cos(α), sin(α)), where c := 2 is the speed of the current, the speed of the swimmer is 1 and he can move in any direction α. We consider two fixed obstacles as represented in Fig. 6.4. Also, in order to get the set of points that can reach the target up to time t, the Hamiltonian function considered here is

u t + max α (-f (x, α)1 K (x) • ∇u) = 0. ( 6
H(x, ∇v) := max λ∈[0,1] max α∈[0,2π] λ (-c∂ x1 v -cos α∂ x1 v -sin α∂ x2 v) ≡ max 0, -c ∂ x1 v + ∇v .
(Note that the set of points that can reach the target at time t exactly would be obtained by using simply H(x, ∇v) := -c ∂ x v + ∇v .)

Results are given in Fig. 6.4. We have used the ENO2 scheme with 100 2 grid points. Computations are done up to time t = 2 and on the domain [-2, 2] 2 . For a given x = (x 1 , x 2 ), the obstacle function is defined by

g(x) := max g min , C 1 r a -x -a ∞ , C 1 r b -max(|x 1 -b 1 |, 1 3 |x 2 -b 2 | (6.5)
where r a = 0.4, a = (0, 0.8) and r b = 0.2, b = (-1, -0.8), C 1 := 20, and g min := -0.2. The initial data is defined by ϑ 0 (x) := C 1 min(r 0 , xr 0 ) where r 0 = 0.25. Remark 13. As said in Remark 6, the theoretical results hold for any choice of ϑ 0 and g such satisfying (2.3) and (2.1). However, the choice of ϑ 0 and g seems important for numerical purposes. Indeed when we consider ϑ 0 (x) := min(r 0 , xr 0 ) and

g(x) := max r a -x -a ∞ , r b -max(|x 1 -b 1 |, 1 3 |x 2 -b 2 |) (6.6)
instead of (6.5), then the numerical results are less accurate. Appendix A. Two-player games with state constraints. We present a generalization of the previous approach to the case of two-player deterministic games with state constraints, without assuming any controllability assumption. We refer to [START_REF] Varaiya | On the existence of solutions to a differential game[END_REF][START_REF] Elliott | The existence of value in differential games[END_REF][START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF][START_REF] Soravia | Pursuit-evasion problems and viscosity solutions of Isaacs equations[END_REF] and references therein for an introduction and some results for deterministic two-player games with infinite horizon.

In the literature, a controllability assumption or continuity of the value function is general supposed [START_REF] Bardi | Pursuit-evasion games with state constraints: dynamic programming and discrete-time approximations[END_REF] in order to deal with state-constrained problems. Note that in the work of Cardaliaguet, Quincampoix and Saint-Pierre [START_REF] Cardaliaguet | Pursuit differential games with state constraints[END_REF], no controllability assumption is assumed, and a characterization is obtained involving non-smooth analysis. Let A and B be two nonempty compact subset of R m and R p respectively. For t ≥ 0, let A t := L ∞ ((0, t); A) and B t := L ∞ ((0, t); B). We consider a continuous dynamics f : R d × A × B → R d , and, for every x ∈ R d and (α, β) ∈ A t × B t , its associated trajectory y = y α,β x solution of ẏ(s) = f (y(s), α(s), β(s)), for a.e. s ∈ [0, t], y(0) = x.

(A.1)

We consider a game involving two players. The first player wants to steer the system (initially at point x) to the target C in minimal time, by staying in K (and using her input α), while the second player tries to steer the system away from C or from K (with her input β). We define the set of non-anticipative strategies for the first player, as follows: This gives again a characterization of the capture basin with state constraints by using a continuous viscosity approach. The corresponding minimal time function can then be recovered as in Proposition 1.

Fig. 3 . 1 .

 31 Fig. 3.1. The target C, the state-constraints set K, and the trajectory yx.

u

  * (x, t) = lim sup s→t,y→x u(y, s) and u * (x, t) = lim inf s→t,y→x u(y, s).

(

  H6) H = H(x I , P + 1 , . . . , P + d , P - 1 , . . . , P - d ) satisfies the following monotonicity condition, a.e. (x, P +, P -) ∈ R d × R d × R d∂H ∂P + i (x, P + , P -) ≤ 0 and ∂H ∂P - i (x, P + , P -) ≥ 0. (H7) (consistency) There exists C 3 > 0 such that for all x I ∈ G, x ∈ R d and P ∈ R d , |H(x I , P, P ) -H(x, P )| ≤ C 3 |x I -x|.

  and |xx I | ≤ Kε and |tt n | ≤ Kε.

  {0, . . . , N T ∆t} and choosing ε = √ T √ ∆x + ∆t, we finally get sup G×{0,...,NT ∆t}ϑ(s n , y I )v(s n , y I ) = µ ≤ K √ T √ ∆x + ∆t + µ 0 provided that ∆x+∆t ≤ 1 K 2 , T ≤ 1 and 0 ≤ µ 0 ≤ 1.Using the same arguments as in Alvarez et al.[START_REF] Alvarez | A convergent scheme for a non local Hamilton Jacobi equation modelling dislocation dynamics[END_REF] Theorem 2], we easily deduce the result in the general case when -1 ≤ µ 0 ≤ 1.

Fig. 6 . 1 .

 61 Scheme:LF Exact obstacle target

Fig. 6 . 2 .

 62 Scheme:ENO2 Exact obstacle target -2 -1 0 1 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

Fig. 6 . 3 .

 63 Scheme:ENO2 Exact obstacle target -2 -1 0 1 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

Fig. 6 . 4 .

 64 Scheme:ENO2 Exact (at t=2) obstacle target

Fig. 6 . 5 .

 65 Fig. 6.5. (Example 2) Isovalues of the minimal time function, and corresponding 3d view.

Γ 2 )

 2 t := a : B t → A t , ∀(β, β) ∈ B t , and ∀s ∈ [0, t], β(θ) = β(θ). a.e. θ ∈ [0, s] ⇒ a[β](θ) = a[ β](θ), a.e. on [0, s] .Then we are interested to characterize the following capture basin for the first player:Cap C (t) := x, ∃a ∈ Γ t , ∀β ∈ B t , y a[β],β x (t) ∈ C, and y a[β],β x (θ) ∈ K, ∀θ ∈ [0, t]Now we consider a function g satisfying (2.3), and we define the following value function for the first player:ϑ(x, t) := inf a∈Γt max β∈Bt max ϑ 0 (y a[β]By using similar arguments as before, we have: Theorem 6. (i) For any t ≥ 0, the capture basin for the first player is characterized byCap C (t) = {x, ϑ(x, t) ≤ 0}.(ii) If g and ϑ 0 are Lipschitz continuous, ϑ is the unique continuous viscosity solution of:min(∂ t ϑ + H(x, ∇ϑ), ϑg(x)) = 0, t ≥ 0, x ∈ R d , (A.3a) ϑ(x, 0) = max(ϑ 0 (x), g(x)) x ∈ R d . (A.3b)where H(x, p) := max α∈A min β∈B -f (x, α, β) • p.

By using the continuity of g we will also have g(x) = 0 if x ∈ ∂K.

That is, ∃C ≥ 0, ∀θ, θ ′ ∈ [0, +∞[ d H (K θ , K θ ′ ) ≤ C|θθ ′ |, where d H is the Hausdorff distance.