J Lohéac

V S Varma

I C Mor Rescu

Time optimal control for a mobile robot with a communication objective

Keywords: Time optimal control, Pontryagin maximum principle, wireless communication

The paper proposes control design strategies that minimize the time required by a mobile robot to accomplish a certain task (reach a target) while transmitting/receiving a message. The message delivery is done over a wireless network, and we account for path-loss while disregarding any shadowing phenomena, i.e., the transmission rate depends only on the distance to the wireless antenna. We completely analyze the case when the robot dynamics is described by a single integrator. Our minimal-time control design is based on the use of Pontryagin maximum principle. We show how we can use these theoretical results to control more complicated non-holonomic dynamics. Numerical simulations illustrate the eectiveness of the theoretical results.

Introduction

Time optimal control problems under dierent hard constrains (mainly communication based) are ourishing in the eld of mobile robotics (see e.g., [START_REF] Das | An ecient group communication protocol for mobile robots[END_REF]). The objective of the robot's mission is often conicting with the imposed constraints. For instance, minimizing the travel time requires more energy but this resource is limited and in order to increase the robot autonomy we may require to minimize energy. In other context, to minimize the mission time we should follow a straight trajectory but if we want to transmit/receive a message while travelling one may need a higher transmission rate imposing a completely dierent path. Precisely, when an unmanned aerial vehicle or a ground robot has to collect data from a eld of wireless sensors, it typically has to optimize its trajectory to minimize the task time while collecting correctly the data may require longer trajectories (see e.g., [START_REF] Wang | Wireless sensors in agriculture and food industry-Recent development and future perspective[END_REF] and [START_REF] Murray | Recent research in cooperative control of multivehicle systems[END_REF]).

To have an easy interpretation of the mathematical results we propose the following problem formulation. A robot has to move from a starting point to a target point within the shortest possible time. Along its travel it must also ensure the transmission of a certain amount of data to a wireless access point. The access point receives the signal with a signal-to-noise ratio (SNR) which primarily depends on the distance between the mobile and the base. Therefore, the mobile has to choose a trajectory which allows the data to be uploaded successfully (which is made possible by having a suciently large SNR) and to minimize the time taken for reaching its target point.

While an important number of applications can be formalized in the framework of a mobile robot that has to minimize a cost under some communication constraints, most of the proposed solutions are either numerical or heuristic. For instance, the problem under consideration in this work is solved numerically in [START_REF] Bonilla | Trajectory planning for energy-ecient robots with communications constraints[END_REF][START_REF] Licea | Communication-aware energy ecient trajectory planning with limited channel knowledge[END_REF][START_REF] Varma | Energy-ecient time-triggered communication policies for wireless networked control systems[END_REF] and only some analytic insights which provides some conditions for the optimal solution are provided. Mainly heuristic solutions are provided for the minimal energy consumption under communication constraints in [START_REF] Ali | Motion-communication co-optimization with cooperative load transfer in mobile robotics: an optimal control perspective[END_REF][START_REF] Ali | Multiple shooting technique for optimal control problems with application to power aware networks[END_REF][START_REF] Ali | An optimal control approach for communication and motion co-optimization in realistic fading environments[END_REF][START_REF] Jaleel | Minimizing mobility and communication energy in robotic networks: An optimal control approach[END_REF][START_REF] Ooi | Minimal energy path planning for wireless robots[END_REF]. This is due to the fact that the SNR is taken as a random variable.

In contrast with the works cited above, the main contribution of this paper is to analytically provide the optimal solution to our problem of time minimization. This is done through the use of the Pontryagin maximum principle, see e.g., [START_REF] Arutyunov | The maximum principle for optimal control problems with state constraints by R. V. Gamkrelidze: revisited[END_REF][START_REF] Ioe | of Studies in Mathematics and its Applications[END_REF]. To do that, we consider the robot dynamics described by a single integrator. The results obtained in this context are then used to improve the performances of non-holonomic robots that have to accomplish the same tasks.

The rest of the paper is organized as follows. In Section 2 we state the constrained minimization problem in a rather general case. Then, in Section 3, we give some elementary results on the general situation and provide some numerical simulations in this case. The Section 4, deals with the case where the dynamic of the robot is a simple integrator. In particular, in 4.2, we apply the Pontryagin maximum principle and compute the optimal control and the corresponding minimal time. The results of Section 4 section are used for the numerical simulations made in 3.3. The paper ends with some concluding remarks.

2 Problem statement Dynamic of the robot. We consider a quite general dynamic for the robot. More precisely, we assume that the robot is subject to the following ordinary dierential equations.

ẋ = f (x, p, u), (2.1a)
ṗ = g(x, p, u), (2.1b)
where x ∈ R d is the robot position (d ∈ {1, 2, 3}), p ∈ R s (s ∈ N, with the convention R 0 = {0} and g ≡ 0, in the case s = 0), are some auxiliary variables for the dynamic of the robot, and u ∈ R m (m ∈ N * ) are the control variables. In order to avoid some technical diculties, we assume that f and g are of C 1 regularity, and the control u belongs to L ∞ . We also assume that the robot is subject to some constraints. First of all, we assume that the velocity of the robot is bounded and without loss of generality, we assume that it is bounded by 1 (any other bound can be obtained by a trivial time rescaling),

|f (x(t), p(t), u(t))| 1 (t 0),

where | • | is the Euclidean norm of R d . We also assume some other state and control constraints,

(x(t), p(t)) ∈ C s (t 0), (2.2b
)

u(t) ∈ C c (t 0), (2.2c)
where C s is a closed subset of R d × R s and C c is a compact subset of R m . We assume that the system (2.1)(2.2) is controllable, that is to say that for every (x 0 , p 0 ) ∈ C s and every (x 1 , p 1 ) ∈ C s , there exist T > 0 and u ∈ L ∞ (0, T ) m such that the solution (x, p) of (2.1), with initial condition x(0) = x 0 and p(0) = p 0 , and the control u, satises (2.2) together with x(T ) = x 1 and p(T ) = p 1 .

Let us summarize the assumptions made on the dynamic of the robot.

Assumption 1.

(a

) f ∈ C 1 (R d × R s × R m , R d ) and g ∈ C 1 (R d × R s × R m , R s ); (b) C s is a closed and nonempty subset of R d , and C c is a compact and nonempty subset of R m ; (c) 0 ∈ C c , 0 ∈ C s , f (0, 0, 0) = 0 and g(0, 0, 0) = 0; (d) the system (2.1) with constraints (2.2) is controllable; (e) the set f (x, p, u) , g(x, p, u) , u ∈ C c ∈ R d ×R s is convex for almost every (x, p) ∈ C s ; (f) there exist V ∈ C 1 (R d × R s ) and C > 0 such that V 0, lim |x|+|p|→∞ V (x, p) = ∞,
and

∂ x V (x, p), f (x, p, u) + ∂ p V (x, p), g(x, p, u)
CV (x, p) for every (x, p) ∈ C s .

In this set of assumptions, we add some technical ones. Namely, Assumption 1-(c), will be used for the general transmission problem, and the Assumptions 1-(e) and 1-(f) are made in order to ensure the existence of an optimal control.

In this paragraph, we have presented some state variables and control. Let us recall that one task of the robot is to deliver a message over a wireless network. This is represented in the following as the problem of emptying a buer whose size at time t is denoted by b(t). This last state variable b and its dynamic is presented in the next paragraph.

Communication model. Typically in wireless communication, the communication rate is mod- eled as a stochastic function which depends on the distance between the transmitting node and the receiving node. We use R(|x(t)|) to denote the communication rate at time t. In practice, communication is performed over certain intervals over which communication packets are transmitted and received with some probability depending on the channel quality, see [START_REF] Ue | Symbol rate and modulation levelcontrolled adaptive modulation/tdma/tdd system for high-bit-rate wireless data transmission[END_REF]. The duration of a frame is typically of the order of 10ms (see [START_REF] Scheme | Lte: the evolution of mobile broadband[END_REF]) in the LTE communication framework. This implies that if a robot moves suciently slowly (speeds of 2 or 3 m/s), the rate function can be well approximated by its expectation over channel fast fading as shown in [START_REF] Holland | A rate-adaptive mac protocol for multi-hop wireless networks[END_REF]. Therefore, for the rest of this paper, we assume that R satises the following assumption: Assumption 2.

(a) R : R + → R + is an absolutely continuous, non-increasing function;

(b) R(0) > 0; (c) R is decreasing on the set {ρ ∈ R + | R(ρ) > 0}.
In our numerical examples, we will consider a specic rate function similar to the one provided by [START_REF] Tse | Fundamentals of wireless communication[END_REF]. With this assumption, it turns out that we end up with a hybrid control problem in which the robot has rst to apply a control action to approach the antenna (increase the transmission rate) and second, switch the control to a point stabilization one (reach the destination). Formally, the state of the system will be (x, p, b) where dynamics of (x, p) is given in (2.1) and b is solution of ḃ = -R(|x|).

(2.3) Remark 1. The Assumption 2-(b) is used to prove the existence of a time optimal solution. The absolute continuity of R is required to apply the Pontryagin maximum principle. The decreasing properties of R are motivated by the physical nature of the problem.

Objective. We are now ready to formalize the time optimal control problem which is studied in this paper. Given some initial buer b 0 0, some initial position x 0 and target position x 1 in R d , the goal is to move the robot from x 0 to x 1 in minimal time T following a trajectory allowing at emptying the buer b, i.e., b(T ) 0 (in practice, the data is transmitted as soon as b(t) > 0 and the transmission is stopped after the time instant t 0 where b(t 0 ) = 0). In order to tackle the auxiliary variable p, we consider an initial condition p 0 ∈ R s and closed subset P 1 of R s , and add the constraints p(0) = p 0 and p(T ) ∈ P 1 . Obviously, in order that such a path is realizable, one needs to make the following assumption. Assumption 3. We assume that (p 0 , x 0 ) ∈ C s , P 1 is a closed subset of R s , and there exist p 1 ∈ P 1 such that (x 1 , p 1 ) ∈ C s .

In other words, given b 0 0, x 0 , p 0 , x 1 and P 1 , satisfying Assumption 3 we aim to solve the following constrained time optimal control problem: (2.4)

min T T 0, ∃u ∈ L ∞ (0,
3 Preliminary results

Existence of a time optimal control

As detailed in 3.2, under the Assumptions 1 to 3, one can see that there exist a time T > 0, a control u ∈ L ∞ (0, T ) m , and p 1 ∈ R s such that the solution (x, p, b) of (2.1) and (2.3) with x(0) = x 0 , p(0) = p 0 and b(0) = b 0 satises x(T ) = x 1 , p(T ) = p 1 and b(T ) 0. This fact, together with the technical assumptions made in Assumptions 1 to 3, ensure, by application of Filippov Theorem (see e.g., [9, Theorem 9.2.i, and its extention in 9.4]) ensures that the minimal time T given by (2.4) exists.

3.2

Bounds on the minimal time Assumptions 1-(c) and 1-(d), ensures the existence of a time T 0 , a control u 0 ∈ L ∞ (0, T 0 ) m , such that the solution (x, p) of (2.1) with initial conditions x 0 and p 0 , satises x(T 0 ) = 0 and p(T 0 ) = 0. We also have that b, solution of (2.3) with initial condition b 0 satises b(T

0 ) = b 0 - T0 0 R(|x(t)|) dt b 0 .
Let us now set T 1 = b 0 /R(0) (recall that due to Assumption 2, we have R(0) > 0), and consider during the times (T 0 , T 0 + T 1 ) we chose the null control, and we have that the position of the robot is xed to 0 during this time interval (see Assumption 1-(c)), and b(T 0 + T 1 ) 0. Finally, Assumptions 1-(c) and 1-(d), ensures the existence of a time T 2 , a control u 2 ∈ L ∞ (T 0 + T 1 , T 0 + T 1 + T 2 ) m , such that the solution (x, p) of (2.1) with initial conditions x(T 0 + T 1 ) = 0 and p(T 0 + T 1 ) = 0, satises x(T 0 + T 1 + T 2 ) = x 1 and p(T 0 + T 1 + T 2 ) = p 1 , for some p 1 ∈ P 1 such that (x 1 , p 1 ) ∈ C s . Obviously, we also have that b(T 0 + T 1 + T 2 ) 0. It is then clear that the minimal time T given by (2.4) is non-greater that

T 0 + T 1 + T 2 .
It is also possible to provide lower bounds on the minimal time T . Trivially, one has T max{|x 1 -x 0 |, b 0 /R(0)}. Indeed, |x 1 -x 0 | is a lower bound on the minimal time required by the robot to reached x 1 from x 0 , and b 0 /R(0) is a lower bound on the minimal time to empty the buer of the robot (recall that due to Assumption 2-(a), we have R(0) = max ρ 0

R(ρ)).

In addition to these trivial lower bounds, one can be easily convinced that the minimum time T given by (2.4) is non-lower than the minimal time T given by the following minimization problem,

min T T 0, ∃u ∈ L ∞ (0, T ) d , s.t. u L ∞ (0,T ) d
where we have set,

ẋ = u, (3.2a) ḃ = -R(|x|).
(3.2b)

As we will see later in Section 4, we will be able to provide a description of the time optimal controls for the optimal control problem (3.1). In addition, as we will see in 3.3.1, the optimal solution of (3.1) will give a nice initialization for the minimization problem (2.4).

3.3

Numerical experiments

Discretization of the problem

In order to numerically compute a time optimal control and a time optimal path, we use the total discretization strategy, as presented for instance in [20, 9.2.1] (see also [START_REF] Betts | Practical methods for optimal control and estimation using nonlinear programming[END_REF][START_REF] Trélat | Optimal control and applications to aerospace: some results and challenges[END_REF]). This method will be compbined with explicit Euler method. To this end, let us set n t 2, the number of time discretization points. We also set x (i) (respectively p (i) , b (i) and u (i) ) the approximation of x (respectively p, b and u) at time t = iT /n t . So that the discretized version of the time optimal control problem (2.4) becomes Minimize T, (3.3a) subject to T 0 and for every i ∈ {0, . . . , n t }, there exist

x (i) ∈ R d , p (i) ∈ R s , b (i) ∈ R and u (i) ∈ R m ,
such that for all i ∈ {0, . . . , n t -1} we have,

x (i+1) -x (i) = T nt f (x (i) , p (i) , u (i) ), (3.3b
)

p (i+1) -p (i) = T nt g(x (i) , p (i) , u (i) ), (3.3c) b (i+1) -b (i) = -T nt R(|x (i) |), (3.3d)
and for every i ∈ {0, . . . , n t } we have,

u (i) ∈ C c , (x (i) , p (i) ) ∈ C s and |f (x (i) , p (i) , u (i) )| 1, (3.3e)
together with

x (0) = x 0 , p (0) = p 0 , b (0) = b 0 , and x (nt) = x 1 , p (nt) ∈ P 1 , b (nt) 0. (3.3f)
In order to numerically solve this problem, we use the sequential quadratic programming routine of the matlab fmincon function. This iterative routine can be initialized using dierent ways. We proposed the following ones:

(i) use the optimal solution of (3.1);

(ii) initialize all the variables to 0;

(iii) initialize with the robot path formed by the segment [x 0 , x 1 ];

(iv) initialize with the robot path formed by the two segments [x 0 , 0] and [0,

x 1 ].
Let us briey explain how the initialization (i) of the minimization problem (3.3) is made. We explain this in continuous time, the real initialization will be obtained after time discretization, which is not a key point. We set T , x, b and u the optimal solution of the minimization problem (3.1). We then initialize with T = T , x = x, b = b and p and q are adjusted so that u = f (x, p, q) and ṗ = g(x, p, q). Of course, a solution (p, q) of this system might not exist. In this case, one can think to minimize some norm of t ∈ [0, T ] → (u -f (x, p, q), ṗ -g(x, p, q)), but this is case dependent. Similarly, it can happen that multiple solutions exist, in this case, we could choose the one minimizing some distance between (p(0), p(T )) and {p 0 } × P 1 .

As title of illustration, we consider the following dynamic for the robot,

ẋ = v (cos γ, sin γ) , (3.4a) v = a, (3.4b)
γ = ω. (3.4c)
In addition, we will assume that the velocity of the robot v is nonnegative and bounded by 1, the acceleration a of the robot is bounded by some constant a, and the angular velocity ω is also bounded by some constant ω. This leads to the state constraint

0 v(t) 1 (t 0), (3.4d)
and the control constraints,

|a(t)| a and |ω(t)| ω (t 0). (3.4e)
The problem considered in this paragraph is given b

0 ∈ R + , x 0 , x 1 ∈ R 2 , v 0 , v 1 ∈ [0, 1
] and γ 0 ∈ R, nd the minimal time T 0 such that there exist a and ω in L ∞ (0, T ) satisfying (3.4e) such that the solution t ∈ [0, T ] → (x(t), v(t), γ(t)) with initial conditions

x(0) = x 0 , v(0) = v 0 and γ(0) = γ 0 , (3.4f)
satises (3.4d) together with the nal constraints,

x(T ) = x 1 , v(T ) = v 1 and b(T ) 0, (3.4g)
where b is solution of (2.3) with initial condition b 0 , i.e.,

ḃ = -R(|x|), b(0) = b 0 . (3.4h)
Note that when a = ω = +∞, this is exactly the minimization problem considered in 4.3. Note that this system coincide with the one given by (2.1) and (2.2), with

d = s = m = 2, p = (v, γ), u = (a, ω), f (x, p, u) = v(cos γ, sin γ) , g(x, p, u) = u, C s = R 2 × R 2 , C c = [-a, a] × [-ω, ω],
and P 1 = {v 0 } × R. Note also that Assumptions 1 and 3 are clearly satised.

Remark 2. Let us discuss the initialization (i) in the particular situation of (3.4). In addition to the trivial initialization of x and b, we initialize the system with v = |u|, γ = arg(u 1 + iu 2 ), a = v and ω = γ. Note also that for this particular case, γ is dened modulo 2π, we thus look for a continuous realization of

t ∈ [0, T ] → arg(u 1 (t) + iu 2 (t)) such that |γ 0 -arg(u 1 (0) + iu 2 (0))| is minimal.
We also consider the transmission rate R, given by

R(ρ) = p s R 0 log 2 1 + P (δ + ρ) a (ρ 0), (3.5)
with R 0 > 0, P > 0, δ > 0, a 2 and 0 p s 1. In practice, we chose p s = e -c with c 0 (see the next subsection 3.3.2 for more details). This particular choice represent the expected data rate based on information theory results, and is often used in wireless literature as an upper bound on the achievable rate [START_REF] Tse | Fundamentals of wireless communication[END_REF]. Here, p s denotes the probability of packet success caused by wireless channel uncertainty and will play a role in 3.3.2. It is also obvious that the function given in (3.5) satises all the requirements of Assumption 2.

In the numerical simulations below, we chose, The other parameters, used in the numerical simulation, are As we can see on Table 1, the choice of initialization is rather important for the computational time and the convergence of the algorithm. This is expected since the minimization problem (3.3) is a priori non-convex. In addition, on Figure 2, we plot the paths obtained with initializations (i) and (iv) (the results obtained with initializations (iii) and (iv) are almost the same).

R 0 = 1, δ = 1/10, a = 3, P = 1 and c = 1/10, (3.6
x 0 = (4 √ 2, 0) , x 1 = √ 2(1, 1) , (3.7a)
v 0 = v 1 = 0, γ 0 = -π/2, (3.7b
On Table 1, one can see that the best results (in term of minimal value obtained and computational time) are obtained with the initialization strategy (i). In any cases, as it is expected, the minimal time obtained is always greater that the minimal time obtained for the simple integrator robot (see Figure 2).

Case of a noisy transmission rate

In this paragraph, we will only perform some numerical experimentation. To this end, we consider the robot dynamic introduced given in (3.4). In this paragraph, we also assume that the wireless transmission is subject to noise. More precisely, we consider that the signal-to-noise ratio (SNR) at distance ρ from the base station is inversely proportional to (δ + ρ) a where a 2 is the path loss exponent (determined by the environment type) and δ > 0. When transmitting with a bandwidth of R 0 and a spectral rate of R, we assume that the packet success event is a Bernoulli process, i.e., it is received with a probability p s ∈ [0, 1]. Therefore, when a packet is received R 0 R amount of information is communicated, while no bits are communicated when the packet is lost. The expected communication rate is thus given by R = p s R 0 R. Exploiting the results in [START_REF] Ozarow | Information theoretic considerations for cellular mobile radio[END_REF], we know that the probability of successful reception for Rayleigh slow-fading channels can be well-approximated by where c > 0 is a constant associated to the wireless channel. In the numerical simulations below, we set the spectral rate as

p s (R, ρ) = exp -c(2 R -1) (δ + ρ) a P ,
R = R(ρ) = log 2 1 + P (δ + ρ) a (ρ 0). (3.9)
resulting in p s = e -c and an expected rate R given by (3.5).

In order that the robot performed the required task with this noisy transmission rate, we update the control at some given times. Roughly speaking, for a given update time τ > 0, the strategy is the following, (a) we compute the control minimizing (3.3);

(b) we apply this control during time T u = min{τ, T } (where T is the minimal time computed in (3.3)). In particular b(t) is given by

ḃ(t) = -T(t)R(|x(t)|), b(0) = b 0 , (3.10)
where R is given by (3.9), and T ∈ {0, 1} R+ describes the chance of success in the transmission and is a realization of the Bernoulli process. Recall that the probability of success is p s = e -c ;

(c) at time T u , we update the current value of the buer, and we go back to step (a) with new initial condition. We repeat this until the buer is not empty and the robot's position target is not reached.

On Figure 3, we display some realizations of this algorithm. 4 Study of the simple integrator case

Although we develop, in this section, results for a simple dynamics, the reader has to keep in mind that we have shown in Section 3 how these results can be used to control more complex non-holonomic ones. In addition, the choice of a simple integrator dynamics is largely motivated in the literature (see e.g., [START_REF] Bullo | A mathematical approach to motion coordination algorithms[END_REF]). Besides the relevance of this choice for practical applications, we will also see that mathematical analysis of this simple dynamics is not trivial. However, keeping the dynamics simple facilitates the mathematical presentation of the results. Throughout this section, we consider the time optimal control problem (3.1). Before entering the core of this section, let us give a brief summary of the obtained results. See also Figure 8, at the end of this paper, for an example of time optimal controlled path.

• When b 0 is small, the optimal time is given by Proposition 1.

• When b 0 is large, the optimal time is given by Proposition 2.

• When b 0 takes intermediate values and x 0 , x 1 and 0 are aligned, the optimal time is given by Proposition 3.

• When b 0 takes intermediate values and x 0 , x 1 and 0 are not aligned, the optimal time is given by Theorem 1.

This section is organized as follows. Based on some geometrical facts, in 4.1, we reduce the above minimization problem to a simpler one. Precisely, we show that it is sucient to consider that the robot evolves in the two-dimensional plane. Moreover, if the size of the message to transmit is small or large enough the solution can be easily found. In 4.2, we apply the Pontryagin maximum principle and compute the optimal control and the corresponding minimal time. Finally, in 3.3, we illustrate the result with some numerical simulations.

Preliminary observations

As for the discussion made in 3.1, Filippov theorem and its extension can also be applied in the context of the minimal time control problem (3.1) (under Assumption 2-(b)). Using some simple geometric facts we reduce the general d-dimensional problem (3.1) to the same problem but with d = 2. Furthermore, we will show that there exist an optimal path x such that x(t) belongs to the convex hull of {x 0 , 0, x 1 } for every time t ∈ [0, T ]. Finally, we will give the closed form of the control signal and of the minimal time in some particular situations. Precisely, the analytic solution is provided when b 0 is small or large enough, as well as when the initial position (x 0 ), the position of the antenna (0) and the nal position (x 1 ) are aligned.

Reduction to a planar motion

Let us rst emphasize an invariance property with respect to the change of the basis used to express the vectors x ∈ R d .

Remark 3. It is straightforward to show that for every orthogonal matrix Q ∈ R d×d , if (T , u) is an optimal solution of the constrained minimization problem (3.1), then (T , Qu) is also an optimal solution of (3.1) with x 0 replaced by Qx 0 and x 1 replaced by Qx 1 .

Secondly, we can show that there exist a time-optimal solution for which the motion of the robot is performed in a 2D space, namely Span{x 0 , x 1 }. Lemma 1. Given x 0 , x 1 ∈ R d and b 0 ∈ R + , then there exists a solution (T , u) of (3.1) such that the trajectory x of (3.2a) associated with u, satises x(t) ∈ Span x 0 , x 1 for every t ∈ [0, T ]. Proof. Let us dene P ∈ R d×d the orthonormal projector from R d to Span x 0 , x 1 ⊂ R d . Let (T , u) be an optimal solution, and set (x, b) the corresponding time-optimal trajectory. We set ũ = P u and x = P x, and we obtain ẋ = ũ, x(0) = x 0 , x(T ) = In conclusion we have found a control in time T which is admissible (i.e., is of L ∞ -norm lower than 1 for which we have x(T ) = x 1 and b(T ) 0) such that the trajectory of the robot belongs to Span x 0 , x 1 .

From Remark 3 and Lemma 1, we can assume without loss of generality that d = 2. The next result shows that, there always exists a time-optimal solution such that the trajectory x belongs to the following convex and bounded set co 0, x 0 , x 1 , where co A denotes the convex hull of the set A.

Lemma 2. Given x 0 , x 1 ∈ R d and b 0 ∈ R + , there exist a solution (T , u) of (2.4) such that the trajectory x of (3.2a) associated with u satises,

x(t) ∈ co {0, x(t 0 ), x(t 1 )} (t ∈ (t 0 , t 1 )), (4.1)
for every t 0 , t 1 such that 0 t 0 t 1 T . Proof. Assume that (T , u) is optimal and let x be the corresponding path. Since x is continuous, if this property is not satised, there exist two times t 0 and t 1 such that 0 t 0 < t 1 T and x(t) / ∈ co {0, x(t 0 ), x(t 1 )} for every t ∈ (t 0 , t 1 ). Then, for every t ∈ (t 0 , t 1 ), we dene x(t) ∈ co{0, x(t 0 ), x(t 1 )} such that x(t) minimizes y → |x(t) -y| under the constraint y ∈ co {0, x(t 0 ), x(t 1 )}, and for t ∈ [0, T ] \ (t 0 , t 1 ), we simply set x(t) = x(t). It is easy to see that x is almost everywhere dierentiable on (t 0 , t 1 ) and | ẋ| 1. We thus have build an admissible path x satisfying |x(t)| |x(t)| for every t ∈ [0, T ], and since R is non-increasing, we have

t1 t0 R(|x(t)|) dt t1 t0 R(|x(t)|) dt.
Remark 4. The result of Lemma 2 ensures that there always exists a time optimal control u such that the solution x of (3.2a) satises (4.1). However, it can be possible that some other time optimal trajectories do not satisfy the property (4.1). This is, in particular, the case when R is constant on a ball centered on 0. However, when b 0 is large enough and when the Assumption 2-(c) is used, we will see in Lemma 4 that the time optimal trajectory of the robot necessarily satises (4.1).

Minimal time for small or large enough initial buer

For every x 0 , x 1 ∈ R d , let us dene

B(x 0 , x 1 ) = x 1 -x 0 1 0 R |x 0 + s(x 1 -x 0 )| ds, (4.2)
representing the quantity of buer transmitted when going on a straight line from x 0 to x 1 with velocity one.

In the next proposition, we give the optimal time and the optimal control when b 0 is small. Proposition 1. Given

x 0 , x 1 ∈ R d and b 0 ∈ R + . If B(x 0 , x 1 ) b 0 , then the minimal time is |x 1 -x 0 | and the optimal control is u(t) = (x 1 -x 0 )/|x 1 -x 0 |.
In other words, the optimal path of the robot is to go straight to the target.

Proof. Indeed, when the buer to transmit is smaller than the quantity of information that can be transmitted while going from x 0 to x 1 with the maximum speed, it is optimal to apply a control that achieves this straight line motion. It is clear that, with this control, we get b(T ) 0.

The next result considers the other extreme case (b 0 large) in which going straight to antenna (where the transmission rate is maximal) and then going to the target provides a time which is not sucient to empty the buer. Therefore, we basically show that the optimal strategy is to go to the antenna, stay there for a certain period, and then go straight to the target. Proposition 2. Given x 0 , x 1 ∈ R d and b 0 ∈ R + . If B(x 0 , 0) + B(0, x 1 ) b 0 , then the optimal time is

T = |x 0 | + |x 1 | + b 0 -B(x 0 , 0) -B(0, x 1 ) /R(0) (4.3a)
and an optimal control is

u(t) =      -x 0 /|x 0 | if 0 < t < |x 0 |, 0 if |x 0 | < t < T -|x 1 |, x 1 /|x 1 | if T -|x 1 | < t < T . (4.3b)
Proof. It is easy to see that the maximal amount of buer that can be transmitted during the time interval [0, |x 0 |] is B(x 0 , 0), and the maximal amount of buer that can be transmitted during the time interval

[T -|x 1 |, T ] is B(0, |x 1 |),
and nally, the maximal amount of buer that can be transmitted during the time interval

[|x 0 |, T -|x 1 |] is R(0) T -|x 1 | -|x 0 | .
Consequently, the minimal time cannot be lower than T given by (4.3a). We conclude the proof by noticing that the control u given by (4.3b) allows to reach the target in this time T , hence is optimal.

4.1.3 Minimal time when x 0 , x 1 and 0 are aligned From the convexity result Lemma 2, we know that an optimal trajectory belongs to the triangle formed by x 0 , x 1 and 0. Furthermore, if b 0 B(x 0 , x 1 ) or b 0 B(x 0 , 0) + B(0, x 1 ), an optimal trajectory has been obtained in Propositions 1 and 2 respectively. Note that these cases include the case where 0 is included in the segment [x 0 , x 1 ]. Let us state the result for the other cases. Proposition 3. Let x 0 , x 1 ∈ R d and b 0 ∈ R + and assume that x 0 , x 1 and 0 are aligned and that B(x 0 , x 1 ) < b 0 < B(x 0 , 0) + B(0, x 1 ), then there exist λ ∈ (0, 1) such that λ|x 0 | < |x 1 | and b 0 = B(x 0 , λx 0 ) + B(λx 0 , x 1 ). Furthermore, the minimal time is given by

T = |x 0 | + |x 1 | -2λ|x 0 |
and an optimal control is

u(t) = -x 0 /|x 0 | if 0 < t < (1 -λ)|x 0 |, x 0 /|x 0 | if (1 -λ)|x 0 | < t < T .
The proof of this result is a direct application of Lemma 2 and is not detailed here.

A priori conditions when b 0 takes intermediate values

To conclude this paragraph, we consider the last case, i.e., the case where x 0 , x 1 and b 0 satisfy the following assumptions: Assumption 4.

(a) dim Span{x 0 , x 1 } = 2 (i.e., x 0 , x 1 and 0 are not aligned); (b) B(x 0 , x 1 ) < b 0 < B(x 0 , 0) + B(0, x 1 ).

In the following lemma, we give some preliminary observations on the optimal solution when Assumption 4 is satised. Lemma 3. Let x 0 , x 1 ∈ R d and b 0 ∈ R + satisfying the Assumption 4, let (T , u) be a minimizer of (3.1) and let (x, b) be the corresponding optimal state trajectory. Then we have:

(i) |x 1 -x 0 | < T < |x 0 | + |x 1 |; (ii) min t∈[0,T ] |x(t)| > 0; (iii) b(T ) = 0.
Proof. The rst item is trivial. In fact, the rst inequality says that the optimal time T is larger than the time required to go from x 0 to x 1 on a straight line, and the second inequality says that the optimal time T is smaller than the time required to go from x 0 to 0 and then to x 1 following two straight lines.

The second item can be proven by contradiction. If there exist a time t ∈ [0, T ] such that x(t) = 0, we necessarily have T |x 0 | + |x 1 |, which contradicts the rst item.

For the last item, assume by contradiction that b(T ) < 0. For every τ ∈ [0, T ], let us dene the path x τ by

x τ (t) =    x(t) if 0 t τ, x(τ ) + t -τ T τ -τ (x 1 -x(τ )) if τ < t T τ , with T τ = τ + |x 1 -x(τ )|. Note that we have by construction x τ (0) = x 0 , x τ (T τ ) = x
(T τ ) = b(τ ) -B(x(τ ), x 1 ). Note that τ → b τ (T τ ) is continuous, b 0 (T 0 ) = b 0 -B(x 0 , x 1 ) > 0 and b T (T T ) = b(T ) < 0.
Consequently, there exist τ * ∈ (0, T ) such that b τ * (T τ * ) = 0. Note now that we have T τ * < T . In fact if T τ * = T then we have x = x τ * on [0, T ], and hence b τ * = b, which is impossible (because b(T ) < 0). This leads to a contradiction with the optimality of T . Remark 5. Note that the item (iii) is valid with the only assumption being b 0 > B(x 0 , x 1 ). This last result, together with a more careful use of Assumption 2, leads to a rened version of Lemma 2. Lemma 4. Let x 0 , x 1 ∈ R d and b 0 ∈ R + satisfying the Assumption 4, let (T , u) be a minimizer of (3.1) and let (x, b) be the corresponding optimal state trajectory. Then for every t 0 , t 1 ∈ [0, T ], with t 0 t 1 , the convex property (4.1) is fullled. Proof. We reproduce here the proof of Lemma 2. If this property is not satised, there exist two time t 0 and t 1 such that 0 t 0 t 1 T and x(t) / ∈ co {0, x(t 0 ), x(t 1 )} for every t ∈ (t 0 , t 1 ). For every t ∈ [t 0 , t 1 ], we then dene x(t) ∈ co {0, x(t 0 ), x(t 1 )} such that x(t) minimizes y → |x(t) -y| under the constraint y ∈ co {0, x(t 0 ), x(t 1 )}. Thus, we have built an admissible path x on [t 0 , t 1 ] satisfying |x(t)| |x(t)| for every t ∈ [t 0 , t 1 ], and since R is non-increasing, we have

t1 t0 R(|x(t)|) dt t1 t0 R(|x(t)|) dt. Two situations can happen: either we have R(|x(t)|) = 0 for every t ∈ [t 0 , t 1 ], or there exist a time t ∈ [t 0 , t 1 ] such that R(|x(t)|) > 0.
1. In the rst case (R(|x|) = 0 on [t 0 , t 1 ]) no buer is transmitted and obviously the optimal path to steer x(t 0 ) to x(t 1 ) is a straight line. This contradicts the fact that x was optimal and x(t) / ∈ co{0, x(t 0 ), x(t 1 )} for every t ∈ (t 0 , t 1 ).

In the second case (

∃ t ∈ [t 0 , t 1 ] | R(|x(t)|) > 0)
, the continuity of R and x, ensure the existence of a time t ∈ (t 0 , t 1 ) such that R(|x(t)|) > 0. Since, by assumption, we have x(t) / ∈ co{0, x 0 , x 1 }, we can conclude that |x(t)| < |x(t)|. This means (using the strict monotonicity of R, see Assumption 2), that R(|x(t)|) < R(|x(t)|), and hence, from the continuity of x and R, we conclude that

t1 t0 R(|x(t)|) dt < t1 t0 R(|x(t)|) dt.
In conclusion, we have built an admissible path, for which the corresponding buer size satises b(T ) < 0. This leads to a contradiction with the item (iii) of Lemma 3.

In the next paragraph, we give some more precise results when Assumption 4 is satised. These result will be derived from the Pontryagin maximum principle.

4.2

Pontryagin maximum principle

In this section, we are going to apply the well-known Pontryagin maximum principle to solve the problem (3.1). We rst write the Pontryagin maximum principle in the general case d ∈ N * . Next, based on the results in 4.1, we reduce the analysis without loss of generality to the particular case d = 2. Finally, the results obtained are summarized in Theorem 1. In addition, since the optimal controls and times have already been obtained for x 0 , x 1 and 0 aligned and for b 0 small or large (see Propositions 1 to 3), we will assume in this section that x 0 , x 1 and b 0 satisfy the Assumption 4.

General case d ∈ N *

Let us recall that we assume that R is an absolutely continuous function.

The Hamiltonian associated to the optimal control problem (3.1) is dened by

H(x, b, u, ξ, β, s 0 ) = -s 0 + ξ, u -βR(|x|), for (x, b, u, ξ, β, s 0
) ∈ R d × R × R d × R d × R × R + .
The Pontryagin maximum principle (see e.g., [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF]Chapter 12] or [START_REF] Jurdjevic | Geometric control theory[END_REF]Chapter 11]) ensures that if (T , x, b, u) is an optimal solution, then, for almost every t ∈ [0, T ], we have,

0 = max υ∈D H(x(t), b(t), υ, ξ(t), β(t), s 0 ) = H(x(t), b(t), u(t), ξ(t), β(t), s 0 ), (4.4)
where D is the closed unit ball of R d . We note that in (4.4), ξ and β (the adjoint states) are solutions of

ξ = - ∂H(x, b, u, ξ, β, s 0 ) ∂x = βR (|x|) x |x| , (4.5a)
β = - ∂H(x, b, u, ξ, β, s 0 ) ∂b = 0, (4.5b)
with R ∈ L ∞ loc (R + ) is the derivative of R. Recall that if x 0 , x 1 and b 0 satisfy the Assumption 4 then the optimal path of the robot do not pass through 0 (see item (i) of Lemma 3). This ensures the validity of the relation (4.5a). The relation (4.5b) trivially ensures that β is constant.

Note also that the relation (4.4), ensures that

u(t) = ξ(t) |ξ(t)| (t ∈ [0, T ] s.t. ξ(t) = 0). (4.6)
Using (4.4) together with the expression of u, we deduce that

s 0 + βR(|x|) = |ξ| (t ∈ [0, T ]). (4.7)
The next proposition summarize the above discussion.

Proposition 4. Let x 0 , x 1 ∈ R d and b 0 ∈ R + satisfying the Assumption 4, let (T , u) be a minimizer of (3.1) and let (x, b) be the corresponding optimal state trajectory. Then there exist s 0 0, β ∈ R and an absolutely continuous function ξ : [0, T ] → R d , such that (s 0 , β, ξ) is not trivial and satises (4.5a) together with (4.7). Furthermore, u is given by (4.6) for every t ∈ [0, T ] such that ξ(t) = 0.

In addition to this initial result, we can give some more properties on s 0 and β.

Lemma 5. With the notations and assumptions introduced in Proposition 4, we have in addition β < 0 and s 0 > 0.

Proof. The fact that β 0 follows from transversality conditions (see e.g., [START_REF] Arutyunov | The maximum principle for optimal control problems with state constraints by R. V. Gamkrelidze: revisited[END_REF]). Consequently, we only have to prove that β = 0 and s 0 = 0. Let us assume by contradiction that β = 0, which yields, from (4.5a), ξ is constant. Since (s 0 , β, ξ) shall not be trivial, we necessarily have (using (4.7)) ξ = 0. Consequently, using (4.6), u is a constant vector of the unit sphere of R d . In order to reach the target x 1 , we necessarily have u = (x 1 -x 0 )/|x 1 -x 0 | and T = |x 1 -x 0 |. But with this path, the transmitted information will be B(x 0 , x 1 ) which is strictly smaller than b 0 . Consequently, one has b(T ) > 0 which is a contradiction with item (iii) of Lemma 3. This proves that β < 0.

Since b 0 > 0, there exist a time τ ∈ [0, T ] such that R(|x(τ )|) > 0. Consequently, from (4.7) (together with β < 0), we deduce that s 0 |β|R(|x(τ )|) > 0.

As a consequence of this result, we assume without loss of generality that β = -1 (recall that s 0 , ξ and β are dened up to a multiplicative constant).

Let us now show that the adjoint state ξ vanishes at most one time.

Lemma 6. With the notations and assumptions of Proposition 4, the adjoint state ξ vanishes at most one time. Proof. Assume there exist two times t 0 and t 1 such that 0 t 0 < t 1 T and ξ(t 0 ) = ξ(t 1 ) = 0.

Using (4.7) this yields that R(|x(t 0 )|) = R(|x(t 1 )|) = s 0 . By Assumption 2-(c), we have that R is injective on R -1 (R * + ). In addition, since s 0 > 0 (see Lemma 5), we conclude that R -1 ({s 0 }) is a single point and |x(t 0 )| = |x(t 1 )|. Using (4.7), once again, we have for every t Remark 6. This last result ensures that any time optimal control u is given by (4.6) for almost every time t ∈ [0, T ].

∈ [t 0 , t 1 ], R(|x(t)|) = s 0 -|ξ(t)| s 0 = R(|x(t 0 )|) = R(|x(

Case d = 2

Let us now particularise the consequences of the Pontryagin maximum principle to the particular case d = 2. Recall that the study of the case d = 2 is not a restriction, see Remark 3 and Lemma 1. In order to integrate the Pontryagin maximum principle, we identify R 2 with C. Consequently, we set x(t) = ρ(t)e iθ(t) and ξ(t) = σ(t)e iγ(t) , with ρ and σ non-negative. Recall also that due to the item (ii) of Lemma 3, if x is a time optimal path, then ρ(t) is positive for every time t. From (4.5), we deduce that σ and γ satisfy (recall that we have chosen, without loss of generality, β = -1):

σ = -R (ρ) cos(θ -γ), (4.8a
)

σ γ = -R (ρ) sin(θ -γ) (4.8b)
and we have from (4.7), σ = s 0 -R(ρ). (4.9)

According to Remark 6, the optimal control u is given by u(t) = e iγ(t) for almost every t ∈ [0, T ]. Thus, from (3.2), we deduce that ρ, θ and b satisfy:

ρ = cos(θ -γ), (4.10a)
ρ θ = -sin(θ -γ), (4.10b) ḃ = -R(ρ).

(4.10c)

In addition, from Remark 3 (with Assumption 4-(a)), we can assume without loss of generality that the initial and nal state constraints are

ρ(0) = ρ 0 > 0, ρ(T ) = ρ 1 > 0 and θ(T ) = -θ(0) = Θ ∈ (0, π/2).
By eventually performing the change of variables t → T -t and using again Remark 3, it can also be assumed that ρ 0 ρ 1 . Hence, in the rest of this paragraph, we assume that

ρ 0 ρ 1 > 0 and Θ ∈ (0, π/2). (4.11)
Let us nally dene α = γ -θ. We are now ready to state the following lemma.

Lemma 7. Let x 0 = ρ 0 e -iΘ and x 1 = ρ 1 e iΘ , with ρ 0 , ρ 1 and Θ satisfying the assumptions (4.11), and let b 0 ∈ R + satisfying the Assumption 4-(b). Given any minimizer (T , u) of (3.1), we set x = ρe iθ and b the corresponding optimal state trajectory. Then there exist three constants ρ ∈ [0, ρ 1 ] and s 0 > R(ρ), and an absolutely continuous function ξ = σe iγ such that ρ, θ, b, σ, γ and s 0 satisfy (4.8), (4.9) and (4.10), and in addition,

σ(t) = 0 (t ∈ [0, T ]) (4.12)
and α = γ -θ satises:

sin α(t) = ρ (s 0 -R(ρ)) ρ(t) (s 0 -R(ρ(t))) (t ∈ [0, T ]), (4.13)
together with α(0) ∈ (π/2, π] (modulo 2π), and α is non-increasing. Finally, the time optimal control is given by u = e iγ everywhere on [0, T ].

Proof. Most of the results of this lemma are direct consequences of the previous results introduced in this paper. In fact, it remains to prove (4.12), the existence of ρ, that s 0 > R(ρ) and the claimed properties on α.

Using the notation α = γ -θ, (4.8) and (4.10), become:

ρ = cos α, ρ θ = sin α, σ = -R (ρ) cos α, σ γ = R (ρ) sin α.
and, for every t ∈ [0, T ] such that σ(t) = 0, we have

α = -1 ρ + R (ρ) σ sin α. (4.14)
Let us denote by T a connected component of [0, T ] \ σ -1 ({0}) (recall that according to Lemma 6, σ -1 ({0}) is either the empty set or a singleton). Note that, if α(t) is given for some t ∈ T , then α solution of (4.14), is uniquely determined in T . Consequently, we have either α(t) = 0, or α(t) = 0 (modulo π) for every t ∈ T .

1. In the rst situation (α = 0 (modulo π) on T ), by continuity of α on T , we conclude that α is constant equal to 0 (modulo π) on T .

2. In the second situation (α(t) = 0 (modulo π) for every t ∈ T ), we have,

cos α sin α α = - ρ ρ - σ σ (on T ).
From which we obtain,

sin α = c ρσ = c ρ (s 0 -R(ρ)) (on T ), (4.15)
with c a constant depending only on of the connected component T of [0, T ] \ σ -1 ({0}). Note that if σ -1 ({0}) = t is not empty, we have

lim t→t ρ(t) (s 0 -R(ρ(t))) = 0.
Hence, this ensures that if σ -1 ({0}) is not empty, we have c = 0.

In both cases, if σ -1 ({0}) is not empty or if there exist t ∈ [0, T ] \ σ -1 ({0}) such that α(t) = 0 (modulo π), then α is constant equal to 0 (modulo π) on each connected component of [0, T ] \ σ -1 ({0}). Thus, using the expression of θ and γ, we deduce that θ and γ are constant on each component of [0, T ] \ σ -1 ({0}). Note that θ is also continuous on each connected component of [0, T ] \ σ -1 ({0}), and the only point of discontinuity of θ can be when ρ = 0. But, since θ(T ) = -θ(0) = Θ ∈ (0, π/2), θ necessarily have a discontinuity point, meaning that there exist a time t such that ρ(t) = 0. This leads to a contradiction with the item (ii) of Lemma 3. In conclusion, we have σ(t) = 0 for every t ∈ [0, T ] and there exist a constant c = 0 such that (4.15) holds on [0, T ]. In particular, this ensures that ρ, σ, θ, γ and α are continuous on [0, T ]. Note that this also ensure that u = e iγ everywhere on [0, T ]. Due to the assumption ρ 0 ρ 1 and due to the convexity result (Lemma 4), one has γ(0) ∈ (-Θ + π/2, -Θ + π] (modulo 2π), and hence α(0) ∈ (π/2, π] (modulo 2π) (see Figure 4). This, in particular, ensures that c > 0, and hence α(t) ∈ (0, π) (modulo 2π) for every t ∈ [0, T ]. From the above result, and using (4.14), we can now state that α is a non-increasing function.

0 x 1 2Θ ρ 0 ρ 1 ρ 0 x 0 u(0) -Θ + π/2 x(t) -Θ + π γ(0)
(0) = γ(0) -θ(0) = γ(0) + Θ ∈ (π/2, π] (modulo 2π).

Let us nally prove the existence of ρ

such that c = R(ρ). Note that ρ → ρ(s 0 -R(ρ)) is increasing on [ρ m , ∞) with ρ m = 0 if s 0 R(0), and ρ m ∈ R + is such that s 0 = R(ρ m ) otherwise. In any cases, we have 0 = ρ m (s 0 -R(ρ m )) c ρ 1 (s 0 -R(ρ 1
)) (the second inequality follows from the fact that (4.15) holds on the full interval [0, T ]). Consequently, there exist ρ ∈ (ρ m , ρ 1 ] such that c = ρ(s 0 -R(ρ)) yielding that s 0 > R(ρ).

Remark 7. Let us mention that once s 0 and ρ are found, the control law is purely a feed-back control law. More precisely, the optimal control is given by u = e iγ with γ given by the ordinary dierential equation:

γ = ρR (ρ)(s 0 -R(ρ)) ρ(s 0 -R(ρ)) 2 , (4.16a)
with the initial condition:

γ(0) = -Θ + π -arcsin ρ(s 0 -R(ρ)) ρ 0 (s 0 -R(ρ 0 )) . (4.16b)
In what follows we distinguish two possible situations α(T ) < π/2 and α(T ) π/2 (modulo 2π). Let us rst set

f s0,ρ (ρ) = ρ(s 0 -R(ρ)) ρ(s 0 -R(ρ)) (ρ 1 ρ 0, s 0 > R(ρ), ρ ρ). (4.17)
• Case α(T ) π/2 (modulo 2π): In this case, there exist t ∈ [0, T ] such that sin α(t) = 1, we then have ρ = ρ(t). Note that according to (4.10a), we have ρ = min [0,T ] ρ. Using the monotonicity properties of ρ, we can see that

t ∈ [0, t] → ρ(t) ∈ [ρ, ρ 0 ] and t ∈ [t, T ] → ρ(t) ∈ [ρ, ρ 1 ]
are two dieomorphisms. Thus, using (4.10a)(4.10c) and the expression (4.13), we deduce that s 0 and ρ shall, in addition to s 0 > R(ρ), satisfy

2Θ = ρ 0 ρ f s0,ρ (ρ) ρ 1 -f s0,ρ (ρ) 2 dρ + ρ 1 ρ f s0,ρ (ρ) ρ 1 -f s0,ρ (ρ) 2 dρ (4.18a) and b 0 = ρ 0 ρ R(ρ) 1 -f s0,ρ (ρ) 2 dρ + ρ 1 ρ R(ρ) 1 -f s0,ρ (ρ) 2 dρ. (4.18b)
The corresponding minimal time is given by

T = ρ 0 ρ dρ 1 -f s0,ρ (ρ) 2 + ρ 1 ρ dρ 1 -f s0,ρ (ρ) 2 . ( 4

.18c)

Note that the above integrals are well-dened as soon as s 0 > R(ρ).

• Case α(T ) > π/2 (modulo 2π): In this case, ρ is strictly decreasing and t ∈ [0, T ] → ρ(t) ∈ [ρ 1 , ρ 0 ] is a dieomorphism. Using (4.10a)(4.10c) and the expression (4.13), we deduce that s 0 and ρ shall, in addition to s 0 > R(ρ), satisfy

2Θ = ρ 0 ρ 1 f s0,ρ (ρ) ρ 1 -f s0,ρ (ρ) 2 dρ (4.19a) and b 0 = ρ 0 ρ 1 R(ρ) 1 -f s0,ρ (ρ) 2 dρ. (4.19b)
The corresponding minimal time is given by 1. We can have α(T ) > π/2 only if Θ < π/4 and ρ 0 > ρ 1 / cos(2Θ).

T = ρ 0 ρ 1 dρ 1 -f s0,ρ (ρ) 2 . ( 4
If α(T ) > π/2, then we have min [0,T ] ρ = ρ 1 and ρ (T ) = 0. This together with the convexity result Lemma 4 leads to the claim of the remark. To clarify the reasoning, we refer to Figure 5. 2. If α(T ) π/2, then ρ > ρ m , with

ρ m = min λ∈R |x 0 + λ(x 1 -x 0 )| = |x 0 | 2 -x 1 -x 0 |x 1 -x 0 | , x 0 2 .
If ρ = ρ 1 , the fact that ρ > ρ m is obvious. If ρ < ρ 1 , then for every τ > 0, the optimal trajectory can be continued on [T , T + τ ], to create a new optimal path for some other initial buer b 0 τ > b 0 . Knowing that at time T , ρ(T ) = ρ 1 , this result can be proved using the convexity result Lemma 4 for t 1 < T and t 2 > T . This is illustrated on Figure 6. 3. In any cases, if (s 0 , ρ) is a solution to the equation (4.18b) or (4.19b), with b 0 > 0, we necessarily have ρ > 0. Remark 9. In both situations, the time t, the angle θ and the buer size b can be recovered in term of ρ, for instance, in the situation α(T ) < π/2, we set,

0 x 1 x 0 2Θ π/2 ρ 1 ρ 1 / c o s( 2 Θ ) (a) Case Θ < π/4. 0 x 1 x 0 2Θ (b) Case Θ π/4.
t = ρ 0 ρ dr 1 -f s0,ρ (r) 2
and for t t, we have,

t = t(ρ) = ρ 0 ρ dr 1 -f s0,ρ (r) 2
and for t t, we have, t = t(ρ) = t + ρ ρ dr 1 -f s0,ρ (r) 2 . In addition, once ∈ {-1, 1} and the parameters s 0 and ρ minimizing J T on E are found, the control u = e iγ can be recovered from (4.16), and the state trajectories can be recovered by using the process described in Remark 9.

Recall that according to Remark 8, we already know that E -1 = ∅ for Θ π/4, or for Θ < π/4 and ρ 0 ρ 1 / cos(2Θ). The problem is now to minimize J T on the set E . We conjecture that the set E is the empty set or a singleton. Proving such a fact does not seem to be an easy task. However, we can make the next remark ensuring that s 0 is uniquely determined by ρ.

Remark 10. Let ρ ∈ (0, ρ 1 ], then when (4.11) holds, for every ∈ {-1, 1}, there exists at most one s 0 = s 0 (ρ) such that (s 0 , ρ) ∈ E .

Let us rst recall that according to the 3 rd claim of Remark 8, we necessarily have R(ρ) > 0. To prove the claim of the remark, we rst dene, (Explicit values of ρ 0 , ρ 1 and Θ are given in the introduction of 3.3.)

I ρ Θ (s 0 , ρ) =

Conclusions

In this paper, we design a time-optimal control strategy allowing a mobile robot to reach a target while transmitting a message in minimum time. Analytical results have been obtained in one of the simplest situations in which there is only one antenna, there are no shadowing eects (the transmission rate only depend on the distance to the antenna) and the dynamics of the robot is described by a single integrator. In this framework, we give both a theoretical description of the optimal control and a strategy for its numerical implementation. We also show how this theoretical result could be useful for the numerical computation of optimal trajectories with robots having non-holonomic dynamics and in the case where the transmission debit is subject to noise. Further works should consider the presence of multiple antennas and noises.

  T ) m and p 1 ∈ P 1 s.t. (x, p, u) satises (2.2), together with x(T ) = x 1 , p(T ) = p 1 and b(T ) 0, where (x, p, b) is solution of (2.1) and (2.3), with x(0) = x 0 , p(0) = p 0 and b(0) = b 0 .

1

 1 and (x, b) satises x(T ) = x 1 and b(T ) 0, where x is solution of (3.2a) with x(0) = x 0 , and b is solution of (3.2b) with b(0) = b 0 ,

Figure 1 :

 1 Figure 1: Illustration of the expected transmission rate function R given by (3.5), with parameters given in (3.6).

) b 0 3

 3

  2π)%1 v γ * /(2π)%1 v *(a) Time optimal values computed for v and γ. Time optimal buer discharge computed.

Figure 2 :

 2 Figure 2: Time optimal state trajectories computed for initializations (i) (named γ * , v * , x * and b * ) and (iv) (named γ, v, x and b). The state trajectory used for initialization (i) is also displayed (named γ, v, x and b) (The displayed result has been obtained with n t = 200).

  2π)%1 realizations v realizations γ * /(2π)%1 v * (a) Values computed for v and γ. (b) Path computed for the robot position. Buer discharge computed.

Figure 3 :

 3 Figure 3: Realization of the process described in 3.3.2, items (a)(c), with τ = 1/2. Update points are marked with circles and the state path (γ * , v * , x * , b * ) is the optimal solution of (3.3). (Parameters used for this simulation are given in (3.6), (3.7) and (3.8).)

  x 1 and |ũ(t)| |u(t)| 1. Let us also dene b(t) = b 0 -t 0 R(|x(τ )|) dτ . Since |x(t)| |x(t)| and since R is a decreasing function, we have b(t) b(t) for every t ∈ [0, T ] and in particular, b(T ) 0.

  1 and | ẋτ (t)| 1 for almost every t ∈ [0, T τ ]. Note also that T τ T for every τ ∈ [0, T ]. Let us also dene b τ the buer size associated with the path x τ . We then have b τ

Figure 4 :

 4 Figure 4: Graphical illustration of the fact that γ(0) ∈ (-Θ + π/2, -Θ + π] (modulo 2π), and α(0) = γ(0) -θ(0) = γ(0) + Θ ∈ (π/2, π] (modulo 2π).

Figure 5 :

 5 Figure 5: Illustration of the 1 st claim of Remark 8.

Figure 6 : 1 ρ dρ 1 - 1 ρ 2 (E

 61112 Figure 6: Illustration of the 2 nd claim of Remark 8.

f

  s0,ρ (ρ) ρ 1 -f s0,ρ (ρ) 2 dρ (ρ ∈ R * + , (s 0 , ρ) ∈ D(ρ)), Value of s0 = s0(ρ; ). ρm was introduced in the 3 rd claim of Remark 8. Value of C b (s0, ρ), with s0 = s0(ρ; ) given in Figure 7a. Value of J T (s0, ρ), with s0 = s0(ρ; ) given in Figure 7a. Tmin = |x 1 -x 0 | and Tmax = |x 0 | + |x 1 |.

Figure 7 :

 7 Figure 7: Computation of s 0 such that C Θ (s 0 , ρ) = 2Θ and associated values of C b and J T .(Explicit values of ρ 0 , ρ 1 and Θ are given in the introduction of3.3.)

  Time optimal buer discharge (Tmin= |x 1x 0 | and Tmax = |x 0 | + |x 1 |).

  Color-map for the dierent values of b 0 .

Figure 8 :

 8 Figure 8: Time optimal state trajectories for dierent values of b 0 . (Explicit values of x 0 and x 1 are given in (3.7a).)

Table 1 :

 1 n t Initialization Number of iterations CPU time (sec.) Minimal time obtained

		(i)	32	0.43	7.877915
	10	(ii) (iii)	450 61	7.65 0.97	13.624892 8.736611
		(iv)	306	3.43	8.736611
		(i)	61	0.99	7.719635
	20	(ii) (iii)	218 147	6.57 4.44	8.923896 8.662189
		(iv)	226	4.15	8.662189
		(i)	140	11.22	7.692913
	50	(ii) (iii)	5 202	25.91 32.73	did not converge 8.667430
		(iv)	423	28.92	8.667430
		(i)	208	22.75	7.687747
	75	(ii) (iii)	6 266	130.77 129.87	did not converge 10.058427
		(iv)	330	61.79	8.667643
		(i)	261	52.41	7.688806
	100	(ii) (iii)	8 356	538.80 349.71	did not converge 8.666217
		(iv)	317	89.24	8.666217
		(i)	358	190.15	7.686823
	150	(ii) (iii)	5 573	1584.41 2113.11	did not converge 8.665094
		(iv)	421	293.25	8.665094
		(i)	450	563.15	7.685786
	200	(ii) (iii)	7 690	5439.79 4330.84	did not converge 8.664531
		(iv)	509	860.40	8.664531

Results obtained for the minimization problem (3.3) with dierent parameters n t and initializations proposed in (i)(iv).

  t 1 )|). By Assumption 2 (R is nonincreasing), we deduce that 0 |x(t 0 )| = |x(t 1 )| |x(t)| for every t ∈ [t 0 , t 1 ]. Obviously, this situation is impossible due to the convexity result of Lemma 4 and the fact that |x(t)| > 0 for every t ∈ [0, T ] (see item (iii) of Lemma 3).

Université de Lorraine, CNRS, CRAN, F-54000 Nancy, France (e-mail addresses:jerome.loheac@univ-lorraine.fr, vineeth.satheeskumar-varma@univ-lorraine.fr, constantin.morarescu@univ-lorraine.fr).

where D(ρ) = {(s 0 , ρ) ∈ R + × (0, ρ) | s 0 > R(ρ) > 0}, and where f s0,ρ is given by (4.17). Note that we have: C Θ (s 0 , ρ) = I ρ 0 Θ (s 0 , ρ) + I ρ 1 Θ (s 0 , ρ).

Note also that the above functions are continuously dierentiable on D(ρ) for every ρ > 0, and, after some computations, we obtain,

with,

Using the monotonicity of R, we obtain (recall that R(ρ) > 0) that

This in particular ensures that given ρ, there exist at most one s 0 = s 0 (ρ) such that

Furthermore, if such an s 0 exist, then, using the implicit function Theorem, ρ → s 0 (ρ) is absolutely continuous.

Numerical illustration

We illustrate the results obtained Section 4, with the transmission rate given by (3.5), with parameters given in (3.6). We place ourselves in the case d = 2, and we consider the initial and nal condition x 0 and x 1 given by (3.7a). Up to a rotation, this leads, with the notation of 4.2, to Θ = π/8, ρ 1 = 2 and ρ 0 = 2ρ 1 / cos(2Θ). This choice has been made in order to allow the existence of a minimizer of J T -1 on the set E -1 (see Remark 8). Let us dene b 0 0 = B(x 0 , x 1 ) and b 0 10 = B(x 0 , 0) + B(0, x 1 ) (note that the initial buer chosen in 3. In order to show the optimal trajectory in the situations given by Propositions 1 and 2, we will also consider initial conditions b 0 < b 0 0 and b 0 > b 0 10 . In order to obtain the optimal solution for the given initial condition b 0 , we chose to use the property claimed in Remark 10, that is to say that for every ρ ∈ [0, ρ 1 ], and every ∈ {-1, +1} we try to compute an s 0 R(ρ) such that C Θ (s 0 , ρ) = 2Θ.

The results of these computations are given on Figure 7a, and the computation has been done with the fsolve function of matlab. Once s 0 is known in term of and ρ, we draw the corresponding buer and time, see Figures 7b and7c. Let us also mention that in order to numerically compute the integrals given in (4.18) and (4.19), we use the midpoint rule, which is known to be convergent for improper integrals. For the computation presented here, we have used 10 5 discretization points. On Figure 7b, we observe that given b 0 ∈ (b 0 0 , b 0 10 ), there exist one and only one corresponding value for ρ and , leading to the time optimal solution. Finally, on Figure 8, we display the optimal state trajectories associated to b 0 0 , . . . , b 0 10 .


• The Azé 1 Cave functionned essentially during the median and upper Middle Pleistocene, before its complete filling with sediments and before the obstruction of its entrances by slope deposits;

• Two closed parallel galleries (Galerie Touristique and Galerie des Aiglons) and two total stalagmitic blockages, well dated, determining three separated sections (1, 2, 3), enable a chronological approach;

• All the bears found in these galleries are too old to be dated by 14C-AMS (beyond the limit of the method, about 50 ka);

• The study of the complete bear N°2 from the Connection Gallery (Argant et al., 2019), between the Galerie Touristique and the Galerie des Aiglons, enables us now a knowledge of the more recent bears of Azé 1 (probably OIS 5);

• The comparison of the bears of Azé 1 is possible only on P4/, M1/ and M2/, the only teeth visible on the bear N°2 from Azé 1-6. The comparison presented here is based only on the morphology of the M2/.

CONCLUSIONS:

The Azé 1 Cave enables to follow the evolution of bears over a long period and it establishes the direct and continuous link in the evolutionary stages and in the dynamics of the populations of bears in the course of time, from the form U. deningeri at the end of median Middle Pleistocene (since OIS.11), then U. spelaeus deningeroides during the recent Middle Pleistocene (OIS.6) in Azé 1-2 (Argant, 1991). Ursus spelaeus ladinicus form occurred probably during OIS. 5.

(1) Is it only a biochronological evolution at the local scale over a long time or (2) was there, in the Mâconnais, a dynamics of populations of bears moving from refuge areas occupied during the major climatic deteriorations, to the previous abandoned sites?

The succession U. deningeri -U. spelaeus deningeroides probably corresponds to the first hypothesis (1) according to the morphological similarity of the M2/. The second hypothesis (2) seems to be more suitable for U. spelaeus ladinicus because of clear morphological differences of its P4/, M1/ and M2/ with the more ancient forms. Of course, this second hypothesis remains to be confirmed with more data.

Anyway, the bear N°2 from Azé 1-6, U. spelaeus ladinicus, seems to be different from the more ancient bears (U. deningeri, U. s. deningeroides) and the three cheek teeth that we could remove from concretion, have characteristics which don't appear on the ancient forms.

References : Well developed talon, with important relief.

Argant A.,
Long cingulum on lingual edge, strongly developed.

Steep gradient on lingual edge.

Long, flat occlusal surface with parallel and relatively narrow edges.

Very long talon, sole like shape, slightly granular.

Small and long cingulum on lingual edge.

Gentle gradient on lingual edge.

Wide and flat, small,.

Small talon.

No visible cingulum (wear).

Medium gradient on lingual edge.

  Aix-Marseille Université, LAMPEA, UMR 7269 CNRS, 5 rue du Château de l'Horloge, F-13094 AIX-EN-PROVENCE cedex 2. (2) ARPA, Université Claude Bernard LYON 1, Bâtiment Géode R.1, 2 rue Raphaël Dubois, F-69622 VILLEURBANNE cedex. (3) Université de Savoie, EDYTEM, UMR 5204, Bâtiment « Pôle Montagne », 5 Bd de la mer Caspienne, F-73376 LE BOURGET-DU-LAC cedex. (4) Association Culturelle du site d'Azé, Rizerolles, F-71260 AZE. like shape talon, smooth ornamentation External lingual cingulum not very developed, Steep gradient on lingual edge More triangular, elongated, flat, big.

  Château (Saône-et-Loire, France) Blanot 2 (Saône-et-Loire, France)

15,67 x 10,76 x4,29