Mattia Bongini
email: bongini@ma.tum.de

Massimo Fornasier
email: massimo.fornasier@ma.tum.de

Dante Kalise
email: dante.kalise@oeaw.ac.at

(Un)conditional consensus emergence under perturbed and decentralized feedback controls

Keywords: AMS Classification: 34D45, 35B36, 93A14, 93B52, 93D15 Multi-agent systems, Cucker-Smale model, consensus emergence, feedback stabilization, decentralized control

We study the problem of consensus emergence in multi-agent systems via external feedback controllers. We consider a set of agents interacting with dynamics given by a Cucker-Smale type of model, and study its consensus stabilization via centralized and decentralized control configurations. We present a characterization of consensus emergence for systems with different feedback structures, such as leader-based configurations, perturbed information feedback, and feedback based on spatially confined information. We characterize consensus emergence for this latter design as a parameter-dependent transition regime between self-regulation and centralized feedback stabilization. Numerical experiments illustrate the different features of the proposed designs.

Introduction

Over the last years, the study of multi-agent systems has become a topic of increasing interest in mathematics, biology, sociology, and engineering, among many other disciplines. Upon the seminal articles of Reynolds [START_REF] Reynolds | Flocks, herds and schools: A distributed behavioral model[END_REF], Vicsek et al. [START_REF] Vicsek | Novel type of phase transition in a system of self-driven particles[END_REF] and more recently, Cucker and Smale [START_REF] Cucker | Emergent behavior in flocks[END_REF], there has been a substantial amount of mathematical works addressing from both analytical and computational perspectives, different phenomena arising in this class of systems. Multi-agent systems are usually modeled as a large-set of particles interacting under simple binary rules, such as attraction, repulsion, and alignment forces, which can depend either metrically or topologically on the agent configuration; the wide applicability of this setting ranges from modeling the collective behavior of bird flocks [START_REF] Reynolds | Flocks, herds and schools: A distributed behavioral model[END_REF], to the study of data transmission over communication networks [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF], including the description of opinion 1 dynamics in human societies [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF], and the formation control of platoon systems [START_REF] Murray | Recent research in cooperative control of multivehicle systems[END_REF][START_REF] Peters | Leader tracking in homogeneous vehicle platoons with broadcast delays[END_REF]. From a mathematical perspective, at a microscopic level, multi-agent systems are often represented by a large-scale set of differential (or difference) equations; in this context, it is of interest the study of asymptotic behaviors, pattern formation, self-organization phenomena, and its basins of attraction. To make matters concrete, in this article we consider a set of N , d-dimensional agents interacting under a controlled Cucker-Smale model of the form

       ẋi = v i vi = 1 N N j=1 a (r ij ) (v j -v i ) + u i , i = 1, . . . , N (1)
where the pair (x i , v i ) ∈ R 2d represents the position and velocity of every agent, u i is an external controller to be suitably defined later, and a : [0, +∞) → [0, +∞) is a bounded, non increasing, continuous function, whereas r ij stands for the Euclidean distance x i -x j . This kind of model has been introduced by Cucker and Smale in [START_REF] Cucker | Emergent behavior in flocks[END_REF][START_REF] Cucker | On the mathematics of emergence[END_REF], for specific choices of the interaction function a as

a(r ij ) = 1 (1 + r 2 ij ) δ for every δ ∈ [0, +∞), (2)
later greatly generalized to arbitrary positive interaction function in [START_REF] Ha | Emergent behavior of a Cucker-Smale type particle model with nonlinear velocity couplings[END_REF]. Throughout our work we stick to this more general approach; we stress that henceforth, every result we obtain applies for any choice of the interaction kernel a that is a positive, continuous, bounded and non increasing function.

For a group of agents evolving according to (1) , we shall be concerned with studying the asymptotic convergence of the velocity field of to a common vector, a phenomenon often defined as consensus. It is clear that if the group converges to consensus, the consensus velocity coincides with the mean velocity of the group

v ∆ = 1 N N i=1 v i . (3)
Definition 1.1 (Consensus). We say that a solution (x(t), v(t)) of system (1) tends to consensus if the consensus parameter vectors v i tend to the mean v, i.e., lim t→+∞ v i (t) -v(t) = 0 for every i = 1, . . . , N.

To set our work in perspective, let us begin by referring to the available results concerning consensus emergence for the uncontrolled system (1), i.e. when u i ≡ 0. In [START_REF] Cucker | On the mathematics of emergence[END_REF] a first result was presented related to the parameter δ in (2); it asserts that for δ ≤ 1/2, the system will tend asymptotically to consensus, independently of its initial configuration. For δ > 1/2, consensus emergence will depend on the cohesion of the initial setting. A precise characterization of this situation was obtained in [START_REF] Ha | Emergent behavior of a Cucker-Smale type particle model with nonlinear velocity couplings[END_REF]Theorem 3.1], where the authors give a sufficient condition depending on the initial configuration and the parameter δ.

Further results concerning variations of the original system and consensus emergence have been presented in [START_REF] Cucker | Flocking with informed agents[END_REF], where the authors study the effect of adding agents with preferred navigation directions (stubborn agents), and [START_REF] Ha | Asymptotic dynamics for the cucker-smale-type model with the rayleigh friction[END_REF], where a Rayleigh-type of damping is added to the dynamics.

In general, the aforementioned results can be interpreted, in a wider framework, as stability results for nonlinear systems around a consensus manifold. A natural extension is then to consider the case when a controller is included as in [START_REF] Bakule | Decentralized control: An overview[END_REF], and consensus can be achieved not only by internal self-regulation, but also by means of an external action. In [START_REF] Caponigro | Sparse stabilization and control of the Cucker-Smale model[END_REF], the authors consider consensus stabilization for the Cucker-Smale system by means of both feedbackbased controllers and open-loop, sparse optimal control. In particular, in [3, Proposition 2] it is shown that, with a controller of the form

u i = -(v i -v) , (4)
consensus emergence can be guaranteed for any configuration and values of δ. A natural drawback of such a controller relates to the fact that it is always active, and that it requires what we call full information or centralized control, i.e., for a single agent, feedback computation will make use, at every time, of the total velocity field; even if full information is available, it is also possible that some perturbation is present. A much more realistic setting relates to what is known in the literature as decentralized control [START_REF] Bakule | Decentralized control: An overview[END_REF]; in our context, it means a control design where every agent acts based on partial information as for instance, the agents around a certain metrical or topological neighborhood [START_REF] Ballerini | Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study[END_REF][START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF].

The aim of this article is to make a contribution along these directions. Starting from a control of the form (4), we will study different variations of the feedback structure for consensus stabilization, by covering different settings such as feedback under perturbed information, leader-following feedback, and decentralized, local feedback depending on a metrical neighborhood of the agents. In every case, we present results concerning sufficient conditions for consensus emergence. In general, these results represent a transition between consensus emergence conditions for the uncontrolled Cucker-Smale system, and the feedback stabilization result under full information presented in [3, Proposition 2].

The paper is structured as follows. In Section 2, we present some preliminary definitions and results concerning consensus emergence in the Cucker-Smale model. In Section 3 and 4, we introduce consensus stabilization results with feedback controllers based on perturbed information. Section 5 addresses the problem of consensus emergence under local feedback. Finally, in Section 6, numerical experiments are presented, aimed at illustrating the main features of the proposed designs; in particular, we numerically investigate the sharpness of the already existing and new estimates for local feedback stabilization.

Preliminaries

In order to start studying system (1), we introduce the following notation and terminology: given a vector a = (a 1 , . . . , a N ) ∈ (R d ) N , the symbol

a ⊥ i ∆ = a i -a
shall stand for the deviation of the vector a i with respect to the mean a. Note that

N i=1 a ⊥ i = N i=1 a i -N a = N a -N a = 0,
and thus, for any vector c ∈ R d , denoting by •, • the usual scalar product on R d , it holds

N i=1 a ⊥ i , c = N i=1 a ⊥ i , c = 0. (5)
A relevant quantity for the forthcoming analysis is the following bilinear form on (R

d ) N B(u, v) ∆ = 1 2N 2 N i=1 N j=1 u i -u j , v i -v j = 1 N N i=1 u i , v i -u, v . (6)
The introduced notation so far provides two forms in which the quantity B(a, a) can be written,

B(a, a) = 1 2N 2 N i=1 N j=1 a i -a j 2 = 1 N N i=1 a ⊥ i 2 .
The following calculation shall be often exploited: given a N × N matrix ω which is symmetric and with positive entries, i.e., ω ij = ω ji and ω ij > 0, for any a ∈ (R d ) N we have

1 N 2 N i=1 N j=1 ω ij a j -a i , a i = 1 2N 2   N i=1 N j=1 ω ij a j -a i , a i + N j=1 N i=1 ω ji a i -a j , a j   = - 1 2N 2 N j=1 N i=1 ω ij a i -a j 2 ≤ -min i,j ω ij B(a, a). (7)
In order to characterize consensus emergence in terms of the solutions, (x(t), v(t)) of the system (1), we define the following quantities

X(t) ∆ = B(x(t), x(t)) , V (t)
∆ = B(v(t), v(t)) ,
which provide an accurate description of consensus in terms of energy of the system by measuring the spread, both in positions and velocities, of the configuration. A first result establishing a link between consensus in the sense of Definition 1.1 and the above introduced quantities is stated as follows.

Proposition 1. The following are equivalent:

1. lim t→+∞ v i (t) -v(t) = 0 for every i = 1, . . . , N , 2. lim t→+∞ v ⊥ i = 0 for every i = 1, . . . , N , 3. lim t→+∞ V (t) = 0.
It is thus natural to prove a sufficiently strong decay of the functional V (t) in order to establish that a solution of (1) tends to consensus. On the other hand, it is well known that not every solution of system (1) tends to consensus in the sense of Definition 1.1; in this context, a relevant result will be the characterization of consensus emergence introduced in [9, Theorem 3.1], which we recall in a concise version:

Theorem 2.1. Let (x 0 , v 0 ) ∈ (R d ) N × (R d ) N and set X 0 = B(x 0 , x 0 ) and V 0 = B(v 0 , v 0 ).
If the following inequality is satisfied:

+∞ √ X 0 a( √ 2N r) dr ≥ V 0 , (8)
then the solution of (1) with initial datum (x 0 , v 0 ) tends to consensus.

In general, we can induce consensus into the system, by adding a feedback term measuring the distance from the group velocity, leading to

       ẋi = v i vi = 1 N N j=1 a (r ij ) (v j -v i ) + γ(v -v i ), (9)
where γ is a prescribed nonnegative constant, modeling the strength of the additional alignment term. As (9) can be rewritten as [START_REF] Bakule | Decentralized control: An overview[END_REF] with the function a(r ij ) + γ replacing a(r ij ), by Theorem 2.1 each solution of (9) tends to consensus. As pointed out in [START_REF] Caponigro | Sparse stabilization and control of the Cucker-Smale model[END_REF], the main drawback of this approach, however, is that it requires that each agent has a perfect information at every instant of the whole system, a condition which is seldom met in reallife situations; it is perhaps more realistic to ask that each agent computes an approximated mean velocity vector v i , instead of the true mean velocity of the group v. Therefore, we consider the model

       ẋi = v i vi = 1 N N j=1 a (r ij ) (v j -v i ) + γ(v i -v i ). ( 10
)
In studying under which conditions the solutions of system [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF] tend to consensus, it is often desirable to express the approximated feedback as a combination of a term consisting on a true information feedback, i.e., a feedback based on the real average v, and a perturbation term. We rewrite the system [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF] in the following form:

       ẋi = v i vi = 1 N N j=1 a (r ij ) (v j -v i ) + α(v -v i ) + β∆ i , (11)
where α = α(t) and β = β(t) are two nonnegative, piecewise continuous functions, and ∆ i is a time-dependent not necessarily continuous deviation acting on agent i. System [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF] encompasses all the previously introduced models, as it is readily seen:

• if α = β ≡ γ and ∆ i = v i -v
, or α = β = 0, then we recover system (1),

• the choices α = γ, ∆ i = 0 (or equivalently β = 0) yield system (9),

• if α = β ≡ γ and ∆ i = v i -v we obtain system [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF].

The introduction of the perturbation term in system [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF] may modify deeply the nature of the original model: for instance, an immediate consequence is that the mean velocity of the system is, in general, no longer a conserved quantity (as it is for system (1)).

Proposition 2. For system [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF], with perturbations given by the vector ∆ = (∆ 1 , . . . , ∆ N ), we have

d dt v = β∆.
Proof.

d dt v = 1 N N i=1 d dt v i = 1 N N i=1   1 N N j=1 a (r ij ) (v j -v i ) + α(v -v i ) + β∆ i   = 1 N 2 N i=1 N j=1 a (r ij ) (v j -v i )
=0, by simmetry.

+ α N N i=1 v ⊥ i =0 + β N N i=1 ∆ i = β∆.
Remark 1. As we have already pointed out, it is possible to recover system (1) by setting ∆ i = 0, whereas we can recover system (9) for the choice ∆ i = v i -v. Note that in both cases we have ∆ = 0, and therefore the mean velocity is a conserved quantity both in systems ( 1) and ( 9).

We also highlight the fact that v is not conserved even in the case that for every t ≥ 0, and for every 1

≤ i ≤ N , ∆ i (t) = c
, where c = 0, i.e., the case in which each agent makes the same error in evaluating the mean velocity.

General results for consensus stabilization under perturbed information

As already pointed out in the previous section, the main strategy for studying under which assumptions a solution of system (1) tends to consensus is to obtain an estimate of the decay of the functional V (t). We follow a similar approach in order to study consensus emergence for system [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF]. We begin by proving the following lemma:

Lemma 3.1. Let (x(t), v(t)
) be a solution of system [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF]. For every t ≥ 0, it holds

d dt V (t) ≤ -2a 2N X(t) V (t) -2αV (t) + 2β N N i=1 ∆ i (t), v ⊥ i (t) . (12)
Proof. Differentiating V for every t ≥ 0, we have

d dt V (t) = d dt 1 N N i=1 v ⊥ i (t) 2 = 2 N N i=1 d dt v ⊥ i (t), v ⊥ i (t) = 2 N N i=1 d dt v i (t), v ⊥ i (t) - 2 N N i=1 d dt v(t), v ⊥ i (t) = 2 N 2 N i=1 N j=1 a (r ij ) v j (t) -v i (t), v ⊥ i (t) (i) + + 2α N N i=1 v(t) -v i (t), v ⊥ i (t) + 2β N N i=1 ∆ i (t), v ⊥ i (t) - 2 N N i=1 d dt v(t), v ⊥ i (t) (ii)
.

Since

r ij = x i -x j = x ⊥ i -x ⊥ j ≤ x ⊥ i + x ⊥ j ≤ √ 2 N k=1 x ⊥ k 1 2 ≤ √ 2N X, (14)
the fact that a is non increasing and inequality ( 7) yield

(i) ≤ -2a 2N X(t) V (t). ( 15
)
Using Proposition 2, we can rewrite term (ii) as

(ii) = - 2α N N i=1 v ⊥ i (t) 2 + 2β N N i=1 ∆ i (t), v ⊥ i (t) - 2β N N i=1 ∆(t), v ⊥ i (t) =0 = -2αV (t) + 2β N N i=1 ∆ i (t), v ⊥ i (t) (16)
Applying ( 15) and ( 16) on ( 13) concludes the proof.

As a direct consequence we obtain the following theorem.

Theorem 3.2. Let (x(t), v(t)) be a solution of system [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF], and suppose that there exists a T ≥ 0 such that for every t ≥ T ,

N i=1 ∆ i (t), v ⊥ i (t) ≤ φ(t) N i=1 v ⊥ i (t) 2 (17)
for some function φ : [T, +∞) → [0, ], where < α β . Then (x(t), v(t)) tends to consensus.

Proof. Under the assumption (17), for every t ≥ T the upper bound in [START_REF] Murray | Recent research in cooperative control of multivehicle systems[END_REF] can be simplified to

d dt V (t) ≤ -2αV (t) + 2β N N i=1 ∆ i (t), v ⊥ i (t) ≤ -2αV (t) + 2β N φ(t) N i=1 v ⊥ i (t) 2 = -2αV (t) + 2βφ(t)V (t) ≤ 2β - α β V (t).
Integrating between T and t (where t ≥ T ) we get

V (t) ≤ V (T )e 2β -α β (t-T )
and as the factor -α β is negative, V (t) approaches 0 exponentially fast.

Corollary 1. If there exists T ≥ 0 such that ∆ ⊥ i (t) = 0 for every t ≥ T and for every 1 ≤ i ≤ N , then any solution of system (11) tends to consensus.

Proof. Noting that ∆ ⊥ i = 0 implies ∆ i = ∆, we have, by ( 5)

N i=1 ∆ i (t), v ⊥ i (t) = N i=1 ∆, v ⊥ i (t) = 0.
We apply Theorem 3.2 with φ(t) ≡ 0 for every t ≥ T and obtain the result.

Remark 2. Corollary 1 implies trivially that any solution of system (9) tends to consensus (this was already a consequence of Theorem 2.1), but has moreover a rather nontrivial implication: also any solution of systems subjected to deviated uniform control, i.e., systems like [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF] where ∆ i (t) = ∆(t) for every 1 ≤ i ≤ N and for every t ≥ 0, tend to consensus, because for every 1 ≤ i ≤ N and for every t ≥ 0, we have

∆ ⊥ i (t) = ∆ i (t) - 1 N N j=1 ∆ j (t) = ∆(t) -∆(t) = 0,
and thus Corollary 1 applies. This means that systems of this kind converge to consensus even if the agents have an incorrect knowledge of the mean velocity, provided they all possess the same deviation.

A final consequence of the previously developed results is the following theorem, which provides an upper bound for tolerable perturbations under which consensus emergence can be unconditionally guaranteed.

Theorem 3.3. Let ε i : [0, +∞) → [0, ] for a fixed < α β , for every i = 1, . . . , N . If there exists T ≥ 0 such that ∆ i (t) ≤ ε i (t) v ⊥ i (t)
for every t ≥ T and for every 1 ≤ i ≤ N , then any solution of system (11) tends to consensus. Proof. By using the Cauchy-Schwarz inequality we have

N i=1 ∆ i (t), v ⊥ i (t) ≤ N i=1 ε i (t) v ⊥ i (t) 2 ≤ N i=1 v ⊥ i (t) 2 .
The conclusion follows by taking φ(t) ≡ for t ∈ [T, +∞) in Theorem 3.2.

Remark 3. The result above shows that, provided that the magnitude of the perturbation is smaller than the one of the deviation of the agent velocity from the mean, then convergence to consensus is obtained unconditionally with respect to the initial condition. This is the case of local estimations of the average, as the largest error that an agent can make when estimating the group average upon a subset of agents is precisely its own deviation from the mean, v ⊥ i .

Perturbations as linear combinations of velocity deviations

We begin this section by considering a simple case study, which is nevertheless relevant as it addresses consensus stabilization based on a leader-following feedback.

Let us use Lemma 3.1 to study the convergence to consensus of a system like [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF], where each agent computes its local mean velocity v i by taking into account themselves and only a single common agent (x 1 , v 1 ), which in turn takes into account only itself by computing v 1 = v 1 . Formally, given two finite conjugate exponents p, q (i.e., two positive real numbers satisfying 1 p + 1 q = 1), we assume that for any i = 1, . . . , N

v i (t) = 1 p v i (t) + 1 q v 1 (t).
We shall prove that any solution of this system tends to consensus, no matter how small the weight 1 q of v 1 in v i is. We start by writing the system under the form [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF], with

α = β = γ and ∆ i (t) = 1 p v ⊥ i (t) + 1 q v ⊥ 1 (t).
Hence, the perturbation term in ( 12) is thus 2γ

N N i=1 ∆ i (t), v ⊥ i (t) = 2γ N N i=1 1 p v ⊥ i (t) + 1 q v ⊥ 1 (t), v ⊥ i (t) = 1 p 2γ N N i=1 v ⊥ i (t) 2 + 1 q 2γ N v ⊥ 1 (t), N i=1 v ⊥ i (t) =0 = 2γ p V (t) ,
and 3.1 let us bound the growth of V (t) as

d dt V (t) ≤ 2γ -1 + 1 p V (t) = - 2γ q V (t) .
This ensures the exponential decay of the functional V (t) for any q > 0.

Motivated by the latter configuration, we turn our attention to the study of systems like [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF] where the perturbation of the mean of the i-th agent has the form

∆ i (t) = N j=1 ω ij (t)v ⊥ j (t). ( 18
)
We shall see that the results obtained in Section 1 help us identify under which assumptions on the coefficients ω ij we can infer unconditional convergence to consensus.

Theorem 4.1. Consider a system of the form [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF], where ∆ i is given as in (18). Then, if for every t ≥ 0 and every i, j = 1, . . . , N we have ω ij (t) = ω ji (t), and we set

I(t) := min i,j ω ij (t) and S(t) := max i N j=1 ω ij (t),
the following estimate holds:

d dt V (t) ≤ -2a 2N X(t) V (t) + 2β S(t) -N I(t) - α β V (t). ( 19
)
Therefore, if there exists a T ≥ 0 such that the quantity S(t) -N I(t) -α β is bounded from above by a constant C < 0 in [T, +∞), then any solution of the system tends to consensus.

Proof. Standard calculations yield

N i=1 ∆ i (t), v ⊥ i (t) = N i=1 N j=1 ω ij (t) v ⊥ j (t), v ⊥ i (t) = N i=1 N j=1 ω ij (t) v ⊥ j (t) -v ⊥ i (t), v ⊥ i (t) + N i=1   N j=1 ω ij (t)   v ⊥ i (t) 2 = N 2   - 1 2N 2 N i=1 N j=1 ω ij (t) v j (t) -v i (t) 2   + N i=1   N j=1 ω ij (t)   v ⊥ i (t) 2 ≤ N (-N I(t) + S(t)) V (t),
having used the equality [START_REF] Cucker | On the mathematics of emergence[END_REF]. Applying this into [START_REF] Murray | Recent research in cooperative control of multivehicle systems[END_REF] and collecting β, we get (19).

In the following results we shall assume N j=1 ω ij (t) = 1, which implies by Proposition 2 that ∆ = 0 and that v is conserved. In particular, for α = β the system can be eventually rewritten as a Cucker-Smale system of the type (1), with a different interaction function a, and the following results can be seen as consequences of Theorem 2.1.

Corollary 2. Let, for any t ≥ 0, ω(t) ∈ [0, +∞) N ×N be a symmetric stochastic matrix, i.e., N j=1 ω ij (t) = 1 for every i = 1, . . . , N . If there exists a ϑ > 0 such that:

I(t) = min i,j ω ij (t) ≥ ϑ > β -α N β ,
then any solution of the system tends to consensus.

Proof. Under the above hypotheses, the quantity S(t) -N I(t) -α β of Theorem 4.1 is bounded from above by 1 -N ϑ -α β , which, by assumption, is negative.

Corollary 3. Suppose that ω ij (t) = φ(r ij (t)) η(t)
where φ : [0, +∞) → (0, 1] is a non increasing, positive, bounded function, and η : [0, +∞) → [0, +∞) is a nonnegative function. Then, given constants α, β ≥ 0 satisfying

1 ≤ N β α ≤ η(t) for every t ∈ [0, +∞), ( 20
)
we have that any solution of system [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF], for ∆ i as in (18) and α and β as above, tends to consensus.

Proof. If we consider the quantity X(t), there are at most two cases: either X(t) is bounded from above by a constant X in [0, +∞), or X(t) remains unbounded.

In the first case, we can bound S(t) from above by N . Since r ij (t) ≤ 2N X(t) ≤ √ 2N X and φ is non increasing, we have that

I(t) = min ij ω ij (t) ≥ φ 2N X ,
and thus, from (20), it follows that

S(t) -N I(t) - α β η(t) ≤ N -N φ 2N X - α β η(t) ≤ -N φ 2N X . ( 21
)
Since φ is positive, the proof is completed by using Theorem 4.1.

Suppose now, instead, that X(t) is unbounded: in this case the term I(t) is bounded from below by a term going to 0 (and hence not helping us) and we have to take advantage of S(t) as shall be shown now. By definition, X(t) is unbounded if and only if there exist two agents with indexes h and k such that r hk (t) is unbounded. By the triangle inequality, it follows that for any index i , there is an index j(i) for which r ij(i) is unbounded. Thus, we fix ρ > 0 and let T > 0 be the maximum time t such that φ(r ij(i) (t)) < 1 -ρ for every i = 1, . . . , N . Then for every t > T we may bound S(t) as

S(t) ≤ 1 η(t) (N -1 + 1 -ρ) ≤ α N β (N -ρ)
and therefore, again from (20),

S(t) -N I(t) - α β η(t) ≤ α N β (N -ρ) - α β η(t) ≤ - α N β ρ + α β -N ≤ - α N β ρ < 0
holds for every t ≥ T , since N β α ≥ 1 by assumption. Theorem 4.1 yields thus the result.

Remark 4. A concrete example of a system for which we can apply Corollary 3 is obtained by considering the functions

φ(r) = 1 (1 + r 2 ) , and
η(t) = max i    N j=1 φ(r ij (t))    .
In this case, can be thought as a parameter tuning the ability of each particle to gather information about the speed of the other agents: indeed, consider a set of agents such that r ij > 0, if i = j. Then, if is 0, v i = v for every i, and each particle communicates at the same rate with near and far away agents, while if goes to +∞ then v i approaches v i , hence each particle is unable to gain knowledge about the speed of the other agents.

The function η serves to the purpose of being a common normalizing factor: naturally one would choose for every agent i the normalizing factor given by

N j=1 φ(r ij (t)), (22)
but that would produce a non symmetric matrix ω, for which the above results are not valid. In this context, the function η is a suitable replacement, being also coherent with the asymptotic behavior of (22) for → 0 and → +∞.

Remark 5. The request of positivity of the function φ cannot be removed from Corollary 3, as the function

φ(r) = χ [0,R] (r) = 1 if r ≤ R 0 if r > R
shows. Indeed, what fails in the argument of the proof is the case in which we suppose that X(t) is bounded by X: if the quantity √ 2N X is not less or equal to R, then φ √ 2N X = 0 in the inequality (21), and we cannot invoke Theorem 4.1 in order to infer consensus.

Perturbations due to local averaging

An interesting case of a system like [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF] is the one where the local mean is calculated as

v i = 1 #Λ R (i) j∈Λ R (i) v j ,
where Λ R (i) = {j ∈ {1, . . . , N } | r ij ≤ R} and #Λ R (i) is its cardinality. In this case, we model the situation in which each agent calculates its local mean counting only those agents inside a ball of radius R centered on him. We want to address the issue of characterizing the behavior of system [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF] with the above choice for v i when the radius R of each ball is either reduced to 0 or set to grow to +∞: we shall see that we can reformulate this decentralized system again as a Cucker-Smale model for a different interaction function for which we can apply Theorem 2.1. We shall show how tuning the radius R affects the convergence to consensus, from the case R ≥ 0 where only conditional convergence is ensured, to the unconditional convergence result given for R = +∞. First of all, by defining χ [0,R] (r) as the characteristic function of a ball of radius R centered at the origin, we can rewrite v i as

v i = 1 N k=1 χ [0,R] (r ik ) N j=1 χ [0,R] (r ij )v j . ( 23
)
As already noted in Remark 4, the normalizing terms N k=1 χ [0,R] (r ik (t)) give rise to a matrix of weights which is not symmetric. Since this will be an issue also in the present section, we take η R (t) to be a function approximating the above normalizing terms and which also preserves its asymptotics for R → 0 and R → +∞, as for instance,

η R (t) = max i N k=1 χ [0,R] (r ik (t)) . ( 24
)
For every t ≥ 0, we replace the vector v i (t) by

1 η R (t) N j=1 χ [0,R] (r ij (t))v j (t) .
Moreover, the vector

v i (t) •   1 η R (t) N j=1 χ [0,R] (r ij (t))  
is also an approximation of v i (t) for R → 0 and R → +∞. This motivates the replacement of the term v i -v i in system [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF] where v i is as in ( 23), with

1 η R N j=1 χ [0,R] (r ij )v j -   1 η R N j=1 χ [0,R] (r ij )   v i = 1 η R N j=1 χ [0,R] (r ij )(v j -v i ) = 1 η R N i=1 (v j -v i ) + 1 η R N j=1 (1 -χ [0,R] (r ij ))(v i -v j ) = N η R (v -v i ) + 1 η R N j=1 (1 -χ [0,R] (r ij ))(v i -v j ). (25)
We can thus rewrite the original system as [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF]:

       ẋi = v i vi = 1 N N j=1 a (r ij ) (v j -v i ) + γ N η ε (v -v i ) + γ∆ ε i , (26)
where the perturbations have the general form

∆ ε i (t) = 1 η ε (t) N j=1 (1 -ψ ε (r ij (t)))(v i (t) -v j (t)). ( 27
)
For ( 27) to be a coherent approximation of our case study, we prescribe that ε is a parameter ranging in a nonempty set Ω satisfying:

(i) ψ ε : [0, +∞) → [0, 1] is a nonincreasing measurable function for every ε ∈ Ω;

(ii) η ε : [0, +∞) → R is an L ∞ -function for every ε ∈ Ω;

(iii) there are two disjoint subsets Ω CS and

Ω U of Ω such that, if ε ∈ Ω CS then ψ ε ≡ χ {0} and η ε ≡ 1, while if ε ∈ Ω U then ψ ε ≡ χ [0,+∞) and η ε ≡ N .
With requirement (iii), we impose that if ε ∈ Ω CS then ∆ ε i = -N ηε (v -v i ), therefore recovering system (1) from ( 26), whereas if ε ∈ Ω U then ∆ ε i = 0, and we obtain a particular instance of system [START_REF] Ha | Emergent behavior of a Cucker-Smale type particle model with nonlinear velocity couplings[END_REF].

In order to study under which conditions on the initial values the solutions of system (26) converge to consensus, we can not use the results of the previous section. This is because, if we compare the following calculations

1 η R N j=1 χ [0,R] (r ij )v j -   1 η R N j=1 χ [0,R] (r ij )   v i =   1 η R N j=1 χ [0,R] (r ij )   (v -v i ) + 1 η R N j=1 χ [0,R] (r ij )v ⊥ j ( 28
)
to (28), we obtain that the system we are considering is precisely the version of system [START_REF] Ignaciuk | Congestion Control in Data Transmission Networks[END_REF] where

α = 1 η R N j=1 χ [0,R] (r ij
) (which is equal to 1 for sufficiently small and large enough R) and ∆ i is of the same kind as the one mentioned in Remark 5.

We present the following result which gives a sufficient condition on the initial data for which the solutions of system (26) converge to consensus. We point out that system (26) can be rewritten into the shape of a Cucker-Smale type of model as follows:

       ẋi = v i vi = 1 N N j=1 a (r ij ) + γ N η ε ψ ε (r ij ) (v -v i ),
and therefore, the following result is obtained as an application of Theorem 2.1.

Theorem 5.1. Fix γ ≥ 0, consider system (26) where

∆ ε i is as in (27) and let (x 0 , v 0 ) ∈ (R d ) N × (R d ) N . Then if X 0 = B(x 0 , x 0 ) and V 0 = B(v 0 , v 0 ) satisfy +∞ √ X 0 a √ 2N r dr + γN η ε ∞ +∞ √ X 0 ψ ε √ 2N r dr ≥ V 0 , (29)
the solution of system (26) with initial datum (x 0 , v 0 ) tends to consensus.

Proof. From requirement (i) we have

1 N N i=1 ∆ i (t), v ⊥ i (t) = 1 N η ε (t) N i=1 N j=1 (1 -ψ ε (r ij (t))) v i (t) -v j (t), v ⊥ i (t) ≤ N η ε (t) 1 -ψ ε 2N X(t) V (t),
and inequality [START_REF] Murray | Recent research in cooperative control of multivehicle systems[END_REF] reads

d dt V (t) ≤ -2 a 2N X(t) + γN η ε (t) ψ ε 2N X(t) V (t).
Moreover, since

d dt V (t) = 1 2 V (t) d dt V (t), from (ii) we have d dt V (t) ≤ -2 a 2N X(t) + γN η ε (t) ψ ε 2N X(t) V (t) ≤ -2 a 2N X(t) + γN η ε ∞ ψ ε 2N X(t) V (t), (30)
and integrating between 0 and t we obtain

V (t) -V (0) ≤ - t 0 a 2N X(t) + γN η ε ∞ ψ ε 2N X(t) V (s) ds. (31)
We now work on changing the variable inside the integral. We can actually claim that

d dt X(t) ≤ V (t), (32)
since, indeed, the following

d dt X(t) = 1 N N i=1 d dt x ⊥ i (t) 2 = 2 N N i=1 x ⊥ i (t), d dt x ⊥ i (t) = 2 N N i=1 x ⊥ i (t), v ⊥ i (t) ≤ 2 N N i=1 x ⊥ i (t) v ⊥ i (t) ≤ 2 N N i=1 x ⊥ i (t) 1 2 N i=1 v ⊥ i (t) 2 1 2 = 2 X(t) V (t),
and d dt X(t) = d dt ( X(t) X(t)) = 2 X(t) d dt X(t)
, together yield (32). Note that we have used

d dt x ⊥ i (t) = d dt   x i (t) - 1 N N j=1 x j (t)   = v i (t) - 1 N N j=1 v j (t) = v ⊥ i (t).
Setting r = X(s), and using (32) we can change variable in (31) as follows:

V (t) -V (0) ≤ - √ X(t) √ X(0) a √ 2N r + γN η ε ∞ ψ ε √ 2N r dr. (33)
Let us suppose that (29) is true, and note that X(0) = X 0 and V (0) = V 0 . If V (0) = 0, then there is nothing to prove since we are already in consensus. If, instead, it is true that

0 < V (0) ≤ +∞ √ X(0) a √ 2N r + γN η ε ∞ ψ ε √ 2N r dr, (34)
then there is a X > X(0) such that

V (0) = √ X √ X(0) a √ 2N r + γN η ε ∞ ψ ε √ 2N r dr
(having used the fact that, from (i), the integrand is a non increasing function). Now, either equality holds in (34), and lim t→+∞ V (t) = 0 follows by passing to the limit in (33), or we have a strict inequality. But in this case X ≥ X(t) must hold for every t ≥ 0, since otherwise there would be a T > 0 for which we have

V (0) ≥ V (T ) + √ X(T ) √ X(0) a √ 2N r + γN η ε ∞ ψ ε √ 2N r dr > √ X √ X(0) a √ 2N r + γN η ε ∞ ψ ε √ 2N r dr = V (0),
which is obviously a contradiction. Thus, we have that the inequality X ≥ X(t) is true for every t ≥ 0, and from (30) we have

d dt V (t) ≤ -2 a 2N X + γN η ε ∞ ψ ε 2N X V (t).
The fact that lim t→+∞ V (t) = 0 follows from the inequality above.

A first example of a family of functions {ψ ε } ε∈Ω is given by

ψ ε (r) = 1 (1 + r 2 ) ε where ε ∈ Ω = [0, ∞],
for which we set ψ ∞ ≡ χ {0} and

η ε (t) = max i N k=1 ψ ε (r ik (t)) .
In this case, Ω CS = {0} and Ω U = {∞}, and (29) is satisfied as soon as

+∞ √ X 0 a √ 2N r dr + γ +∞ √ X 0 ψ ε √ 2N r dr ≥ V 0 is, since η ε ∞ ≤ N .
But the most interesting example of such a family is the one which has introduced this section: we consider Ω = [0, +∞], the set of functions {χ [0,R] } R∈Ω and η R as in (24) (notice that, as before, we have Ω CS = {0} and Ω U = {∞}). Since η ∞ ≤ N , if R is sufficiently large to satisfy √ 2N X 0 ≤ R, condition (29) is satisfied as soon as

+∞ √ X 0 a √ 2N r dr + γ R √ 2N -X 0 ≥ V 0 ,
by means of a trivial integration. If, instead, R is so small that √ 2N X 0 > R, condition (29) is satisfied as soon as

+∞ √ X 0 a √ 2N r dr ≥ V 0 ,
recovering Theorem 2.1.

The above results can be seen as the asymptotic outcome of the following more general approach: consider the set Ω = [0, ∞] × (1, ∞], write ε as the couple of parameter R, θ and set since in both cases we have η ∞ ≤ N , and it holds

ψ R,θ (r) = 1 if r ≤ R, 1 (r-R+1) θ if r > R.
+∞ √ X 0 ψ R,θ √ 2N r dr = R √ 2N √ X 0 dr + +∞ R √ 2N 11 ( √ 2N r -R + 1) θ dr = R √ 2N -X 0 + 1 θ -1 ,
then condition (29) is satisfied as soon as

+∞ √ X 0 a √ 2N r dr + γ R √ 2N -X 0 + 1 θ -1 ≥ V 0 ,
which shows that the consensus region grows linearly with the radius R while it is inversely proportional to the growth of θ.

Otherwise, if R is so small that √ 2N X 0 > R, since +∞ √ X 0 ψ R,θ √ 2N r dr = +∞ √ X 0 1 ( √ 2N r -R + 1) θ dr = 1 (θ -1)( √ 2N X 0 -R + 1) θ-1 ,
we have that condition (29) is true whenever

+∞ √ X 0 a √ 2N r dr + γ θ -1 1 ( √ 2N X 0 -R + 1) θ-1 ≥ V 0 .
In this case, the consensus region is in practice not modified by R, but only by the decay of the far-away interaction θ (the faster the decay, the smaller the consensus region).

In both cases, if θ goes to +∞, we recover the result we obtained for the family of functions

{χ [0,R] } R∈[0,+∞] .

Numerical tests

We present a series of numerical tests illustrating the main results developed throughout this article. We begin by describing the generic setting upon which the initial configurations of agents are determined; we follow similar ideas as those presented in [START_REF] Carrillo | Particle, kinetic, and hydrodynamic models of swarming[END_REF]. We consider a system of N , 2-dimensional agents with a randomly generated initial configuration of positions and velocities ( x, ṽ)

∈ [-1, 1] 2N × [-1, 1] 2N ,
interacting by means of the kernel (2) , with δ = 1. We recall that relevant quantities for the analysis of our results are given by

X[x](t) = 1 2N 2 N i,j,=1 ||x i (t) -x j (t)|| 2 , and V [v](t) = 1 2N 2 N i,j,=1 ||v i (t) -v j (t)|| 2 .
In fact, once a random initial configuration has been generated, it is possible to rescale it to a desired (X 0 , V 0 ) parametric pair, by means of

(x, v) = X 0 X[ x] x, V 0 V [ṽ] ṽ , such that (X[x], V [v]) = (X 0 , V 0 ).
As simulations concerning flock trajectories have been generated by prescribing a value for the pair (X 0 , V 0 ), which is used to rescale randomly generated initial conditions, there are slight variations on the initial positions and velocities in every model run, which can affect the final consensus direction. However our results are stated in terms of X, V , and independently of the specific initial configuration. For simulation purposes the system is integrated in time with the specific feedback controller by means of a Runge-Kutta 4th-order scheme.

Leader-based feedback. The first case that we address is the one presented in Section 4, where the feedback is built upon local information and a single flock leader. In this case, the local feedback is defined as

u i = -(v i -v i ) , with v i = (1 -q)v i + qv 1 , i = 1, . . . , N ,
where for convenience we have selected the first agent as the leader of the flock. Figure 1 shows the behavior of the flock depending on the parameter q, which represents the V(t) V(t) evolution, different leader strength (q) q=0.9 q=0.1 q=0.5 q=0

Figure 2: Leader-based feedback control. Simulations with 100 agents, the value q indicates the strength of the of the leader in the partial average. Evolution of X(t) and V (t) for the simulations in Figure 1.

influence of the leader in the local average. Our result asserts that for 0 < q ≤ 1, the system will converge to consensus independently of the initial configuration, which is illustrated by our numerical experiments, as shown in Figures 1 and2 ; it can be observed that, the weaker the influence of the leader, the longer the flock takes to reach consensus.

Feedback under perturbed information. Next, we deal with the setting presented again in Section 4, by considering a feedback of the form

u i = -α(v i -v) -β∆ i , v = 1 N N i=1 v i ,
where ∆ i = ∆ i (t) represents a structured perturbation written as

∆ i = 1 η i (t) N j=1 ω ij (v j -v) .
In particular, we address the case where the weighting function ω ij corresponds to similar Cucker-Smale kernel as for the dynamics, i.e., 5.1 is consistent in the sense that the theoretical consensus region increases gradually as R grows, eventually covering any initial configuration, which is the case of the total information feedback control, as presented in [3, Proposition 2]. The numerical experiments also confirm this phenomena, as shown in Figure 8 , where contour lines showing the 80% probability of consensus for different radii locate farther from the origin as R increases.

ω ij = 1 (1 + ||x i -x j || 2 ) , η i = 1 N N j=1 ω ij

Concluding remarks and perspectives

We have presented a set of feedback controllers for consensus emergence in nonlinear multiagent systems of Cucker-Smale type. The proposed control designs address different situations concerning leader-following configurations, stabilization under perturbed information, and decentralized, local feedback control. In general, we characterize consensus emergence in every case, providing a coherent extension of the available results in the literature. Furthermore, numerical experiments assess the performance of the controllers in a consistent way. Among possible future directions of research, let us mention that numerical evidence suggest that sharper consensus estimates should be possible to be derived, if the structure of the internal dynamics is more intensively used in the computations. Another natural extension of our work would be to consider the consensus emergence problem, under a decentralized control computed via an optimality-based approach.

  This time we have Ω CS = {(0, ∞)} and Ω U = {∞} × (1, +∞]. If we suppose that R is sufficiently large to satisfy √ 2N X 0 ≤ R and we consider η R,θ to be likeη R,θ (t) = max i N k=1 ψ R,θ (r ik (t)) or η R,θ (t) = min i N k=1ψ R,θ (r ik (t)) ,

2D 10 2D 1 -2D 9 Figure 1 :

 10191 Figure1: Leader-based feedback control. Simulations with 100 agents, the value q indicates the strength of the of the leader in the partial average. It can be how, as the strength of the leader is increased, convergent behavior is improved.

2D2D 6 2D

 6 flock trajectories, controlled under perturbartion, α = 1e -2, β = 10 flock trajectories, controlled under perturbartion, α = 1e -1, β = 10 flock trajectories, controlled under perturbartion, α = 1, β = 10

Figure 3 :

 3 Figure 3: Total feedback control under structured perturbations. For a fixed strong structured perturbation term (β = 10), different energies for the unperturbed control term α generate different consensus behavior; the stronger the correct information term is, the faster consensus is achieved.

Figure 5 :

 5 Figure 5: Local feedback control. Simulations with N = 40 agents, and different control radii R. By increasing the value of R the systems transits from uncontrolled behavior, to partial flocking, up to total, fast flocking.

Figure 8 :

 8 Figure 8: Local feedback control. Empirical contour lines for the 80% probability of consensus with different control radii.

Acknowledgments. The authors acknowledge the support of the ERC-Starting Grant "High-Dimensional Sparse Optimal Control" (HDSPCONTR -306274), the START-award "Sparse Approximation and Optimization in High Dimensions" of the Fonds zur Förderung der wissenschaftlichen Forschung (FWF, Austrian Science Foundation), and the ITN -Marie Curie Grant n. 264735-SADCO.

In this test, we fix a large value of β = 10, representing a strong perturbation of the feedback, and a small value of = 1e-5, related to a disturbance which is distributed among all the agents. In Figures 3 and4 , it is shown how increasing the value of α, representing the energy of the correct information feedback, induces faster consensus emergence.

Figure 4: Total feedback control under structured perturbations. Evolution of X(t) and V (t) for the simulations in Figure 3.

Local feedback control. The last test case studies the results presented in Section 5, where the feedback is computed according to the local average in eq.( 23). Simulations in Figure 5 illustrate the setting. From an uncontrolled system, represented by a local feedback radius R = 0, by increasing this quantity, partial flocking is consistently achieved, until full consensus is observed for large radii mimicking a total information feedback control. From a theoretical perspective, this result is presented in Theorem 5.1, which describes a sufficient consensus region for feedback control based on local averages. This theorem recovers on its asymptotics previous results in [START_REF] Ha | Emergent behavior of a Cucker-Smale type particle model with nonlinear velocity couplings[END_REF], and [START_REF] Caponigro | Sparse stabilization and control of the Cucker-Smale model[END_REF], related to consensus regions for uncontrolled and fully controlled systems under total information feedback, respectively. It has been reported in the literature [START_REF] Carrillo | Particle, kinetic, and hydrodynamic models of swarming[END_REF], that estimates for consensus regions such as the one provided by Theorem 2.1, are not sharp in many situations. In this direction, we proceed to contrast the theoretical consensus estimates with the numerical evidence. For this purpose, for a fixed number of agents, we span a large set of possible initial configurations determined by different values of (X, V ). For every pair (X, V ) we randomly generate a set of 20 initial conditions, and we simulate for a sufficiently large time frame. We measure consensus according to a threshold established on the final value of V ; we consider that consensus has been achieved if the final value of V is lower or equal to 1e -5. We proceed by computing empirical probabilities of consensus for every point of our state space (X, V ); results in this direction are presented in Figures 6 and7. We first consider the simplified case of 2 agents; according to [START_REF] Caponigro | Sparse stabilization and control of the Cucker-Smale model[END_REF], for this particular case, the consensus region estimate provided by Theorem 2.1 is sharp, as illustrated is by the results presented in Figure 6. Furthermore, it is also the case for Theorem 5.1; for R > 0, the consensus region predicted by the theorem coincides with the numerically observed ones.

Figure 7 illustrates the case when a larger number of agents is considered. In a similar way as for Theorem 2.1, the consensus region estimate is conservative if compared with the region where numerical experiments exhibit convergent behavior. Nevertheless, Theorem


France Mentré
email: france.mentre@inserm.fr

Marylore Chenel

Emmanuelle Comets

Joachim Grevel

Andrew C Hooker

Mats O Karlsson

Marc Lavielle

Iva Gueorguieva

Current Use and Developments Needed for Optimal Design in Pharmacometrics: A Study Performed Among DDMoRe's European Federation of Pharmaceutical Industries and Associations Members

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Methods and software tools for optimal design in nonlinear mixed effect models (NLMEM) have been developed and proposed for a decade [START_REF] Mentré | Software for optimal design in population pharmacokinetics and pharmacodynamics: a comparison. Annual Meeting of the Population Approach Group in Europe[END_REF] . They are based on the evaluation and optimisation of the Fisher information matrix, whose inverse is a lower bound of the expected variance of estimation. Since the first optimal design tools for population pharmacokinetics [START_REF] Retout | Development and implementation of the population Fisher information matrix for the evaluation of population pharmacokinetic designs[END_REF] , at least 5 software tools have been developed and new versions [START_REF] Gueorguieva | A program for individual and population optimal design for univariate and multivariate response pharmacokinetic-pharmacodynamic models[END_REF][START_REF] Bazzoli | Design evaluation and optimisation in multiple response nonlinear mixed effect models: PFIM 3.0[END_REF][START_REF] Nyberg | An extended, parallelized, nonlinear mixed effects models optimal design tool[END_REF] with improvements have been made available on a regular basis by several academic groups. They are mainly applied for pharmacokinetic-pharmacodynamic (PKPD) studies.

Present tools do not yet allow optimization of adaptive designs for these models, although prior information on models and parameter values are needed and adaptive designs are increasingly used and promising in drug development 6, . Before developing this capacity we conducted a study among the 10 drug companies which are members of the Drug Disease Model Resources (DDMoRe) European consortium [START_REF] Harnisch | Annual Meeting of the Population Approach Group in Europe[END_REF] to identify current practices, shortcomings and expectations.

STUDY ON USE OF OPTIMAL DESIGN IN PHARMACOMETRICS

In 2011, the Drug Disease Model Resources (DDMoRe) consortium was approved as one of the Innovative Medicines Initiative (IMI) projects of the European Union with the objective of developing a drug-disease model library and an open-source interoperability framework [START_REF] Harnisch | Annual Meeting of the Population Approach Group in Europe[END_REF] . This project associates 9 academic groups, 6 small and medium sized enterprises, and 10 pharmaceutical companies that are members of the European Federation of Pharmaceutical Industries and Associations (EFPIA). One of the work packages within DDMoRe is responsible for development and integration of new tools, among others also for adaptive optimal designs in PKPD using nonlinear mixed effect models (NLMEM).

The working group members and authors of this article designed a questionnaire for this study. It was sent to each EFPIA representative within DDMoRE in October 2011. Each representative was then in charge to ask one to three scientists within the company to respond to the questionnaire, mostly to those indeed involved in designing PKPD studies.

The detailed questionnaire is available as Supplementary Figure S1. Responders first stated how clinical trials were generally designed, by simulations, heuristic approaches and/or optimal design. The main body of the survey was composed of two parts, part 1: state of the art on the use of optimal design methods in industry, part 2: requests for future developments using adaptive optimal design.

RESULTS

Results were obtained in November 2011 from all the 10 member companies of the DDMoRe consortium (100% response rate): AstraZeneca, GSK, Lilly, Merck Serono, Novartis, Novo Nordisk, Pfizer, Roche, Servier, UCB Pharma.

Current Situation

Part 1 of the study investigated the current situation. The first question showed that optimal design software tools in NLMEM are being used by nearly all companies (9/10), Optimal design approaches are used for a variety of investigations and design complexity (Table 1). Interestingly, optimal design is often used in early clinical phases (I and II), and less in phase III; one responder suggested that there is a lack of models able to handle complex endpoints encountered in later phases. Current limitations were expressed in free text which is available as Supplementary Table S1. The most common limitation was the need to change software when moving from estimation to design, showing a strong need for more integrative/global approaches/tools. Several companies were concerned about the limited models currently implemented in most optimal design software tools and suggested to add more flexibility. Overall, the perceived impact of optimal design was generally considered quite important, with potentially wider applications suggested in the industry.

Adaptive Designs and further developments

Adaptive design in NLMEM is of high priority for most companies with a median of 4, on a scale of 0 to 5, with 4 companies quoting a 5 (very useful). The answers to specific needs were: (i) start from prior information (8/9), (ii) design optimisation after each new cohort (8/9), (iii) use stopping rules (6/9). One company highlighted that adaptive design is not possible in therapeutic areas where endpoints are attained slowly while recruitment is fast.

The importance of new developments in design tools was graded on a scale from 0 to 5.

Results are given in Table 2 and show that the priorities are: (i) handling of continuous covariates, (ii) dealing with data below quantification limit, (iii) robustness across models, and (iv) design for discrete outcome data also in combination with continuous data. Additional expectations were expressed in text (Supplementary Table S1).

CONCLUSION

This study illustrates that optimal design methodology has been quickly adopted within the industry, especially in early phases where PKPD is more important. This is study further highlights expected improvements in interoperability between optimal design and estimation software and in statistical capabilities of the optimal design methodology. A smooth workflow between estimation, model evaluation and design will be facilitated on the DDMoRe platform. It should be noted that we did not perform a comprehensive systematic review of the use of optimal design software tool in NLMEM in drug companies outside of DDMoRe, therefore the presented results may be biased.

Another outcome of the study is the high priority was given to further development of adaptive optimal design (AOD) in NLMEM with optimisation not only of sampling times but of other design variables, e.g. doses (Table 1). Initial work on AOD in population PK demonstrated its feasibility [START_REF] Foo | Adaptive optimal design for bridging studies with an application to population pharmacokinetic studies[END_REF] , but the approach is not yet fully studied nor implemented in any available software. Those developments will only address some of the issues of the complexity of adaptive design in drug development. For instance, adaptive doseranging studies analysed by nonlinear models without random effects, are already being optimised [START_REF] Bornkamp | Innovative approaches for designing and analyzing adaptive dose-ranging trials[END_REF] . Also, as pharmacometrics has increased its scope beyond population PK, design tools for more complex models and for other types of data, especially discrete data, are now needed. Academic groups are actively working on those topics and are sharing their results to translate progress into new software tools, but collaborations with statisticians involved in other aspects of the complex issues in adaptive designs are also increasingly needed. Optimal design enriches clinical trial simulation, and both will work in concert to improve model-based drug development in the pharmaceutical industry.

  mostly during Phase 1 and 2 for Pharmacokinetics (PK)/Pharmacodynamics (PD), sometimes for biopharmaceutical studies later in development in special populations: paediatric patients, patients with renal or hepatic impairment and the elderly. All currently available software tools were used among the respondents. Here a list of the programs and their frequency of usage: PFIM (University Paris Diderot & INSERM, 6/9), POPED (University of Uppsala, 3/9), POPDES (University of Manchester, 3/9), POPT (University of Otago, 3/9).

Acknowledgements. The research leading to these results has received support from the Innovative Medicines Initiative Joint Undertaking under grant agreement n° 115156, resources of which are composed of financial contributions from the European Union's Seventh Framework Programme (FP7/2007-2013) and EFPIA companies' in kind contribution. The DDMoRe project is also financially supported by contributions from Academic and SME partners.

Table 1: Current use of optimal design software tools for the n=9 EFPIA companies, out of the 10 of DDMoRe, presently using this approach.

Yes

Type of investigations

Design evaluation 7

Design optimisation 8

Power evaluation 6

Complexity of designs

Dose/input optimisation 6

Sampling windows in designs 7

Several group of elementary designs 7

Bayesian/robust approaches 5

Complex error models 3

Inter-occasion variability 3

Covariates 5

Multi-response models 4

1


Romain Drouilly

Patrick Rives

Benoit Morisset

Semantic Representation For Navigation In Large-Scale Environments

Mimicking human navigation is a challenging goal for autonomous robots. This requires to explicitly take into account not only geometric representation but also high-level interpretation of the environment. In this paper, we demonstrate the capability to infer a route in a global map by using semantics. Our approach relies on an object-based representation of the world automatically built by robots from spherical images. In addition, we propose a new approach to specify paths in terms of high-level robot actions. This path description provides robots with the ability to interact with humans in an intuitive way. We perform experiments on simulated and real-world data, demonstrating the ability of our approach to deal with complex large-scale outdoor environments whilst dealing with labelling errors.

I. INTRODUCTION

Autonomous navigation in real world environment is one of the key challenges to solve for mobile robots. They have to be able to find the best way from their current position to target position, whilst adhering to constraints and interacting with humans. To date, most of the strategies for route planning rely on metric or topological maps and constraints are expressed in terms of geometry, assuming the shortest path to be the best. While it is obviously useful to minimize the path length, depending on the scenario many other constraints have to be considered. Robots are required to deal with challenges that impose to redefine what "best" means. To name a few, contrarily to static scenes that represent a very small class of real-world environments, dynamic scenes contain moving objects with unpredictable behaviour and are subject to appearance changes. In such cases, an intelligent robot needs to consider those aspects when choosing the best route from one point to another. Other constraints like minimizing the collision risk or maximizing the stability of landmarks along the path are also crucial.

A recent trend in robotic mapping is to augment low-level maps with semantic interpretation of their content, which allows to improve the robot's environmental awareness. In mobile robot navigation, the so-called semantic maps have already been used to improve path planning methods, mainly by providing the robot with the ability to deal with humanunderstandable targets [START_REF] Borkowski | Towards semantic navigation in mobile robotics[END_REF], [START_REF] Posada | Visual semantic robot navigation in indoor environments[END_REF]. However, despite their interesting results, these approaches rely on the "place" concept that is well-defined indoors but difficult to define outdoors.

In this work we propose to use high-level semantic interpretation of the scene both for specifying interesting targets and for choosing optimal path towards a given goal. To do so, 1 Authors are with INRIA Sophia-Antipolis, France romain.drouilly@inria.fr, patrick.rives@inria.fr 2 Authors are with ECA Robotics, bmo@eca.fr we introduce a semantic cost function that takes into account high-level constraints through image annotation. This allows us to select a path according to criteria that capture scene features different from metrical data or topology but that are essential for robot navigation. Additionally, we propose a new semantic path representation that aims to address the problem of semantic path description in outdoor environments. Both this representation and the route planning algorithm rely on the hybrid map structure introduced in our previous work [START_REF] Drouilly | Fast hybrid relocation in large scale metric-topologic-semantic map[END_REF]. It uses only object position in images without the need of 3D scene reconstruction or the use of the ill-defined concept of "place" to describe robot positions.

The main contributions of this paper are twofold: a new framework to select the best route for the robot taking into account semantic content of the scene; and a new approach to describe a path in terms of semantics that easily adapt to both indoor and outdoor environments.

After a concise review of related work in section II, we present the Semantic Map structure in section III while our Semantic Route Planning framework and our Path Description methodology are introduced in section IV and V respectively. Then two series of experiments are presented on both simulated and real-world data in section VI, demonstrating the effectiveness of our algorithm.

II. RELATED WORK

Semantics have been shown to be useful in inferring new information about the scene and to improve planning efficiency [START_REF] Galindo | Robot task planning using semantic maps[END_REF]. It is useful when the search space is large, translating the problem in a new space of smaller dimension.

In the specific domain of mobile robot navigation, semantics has been used mainly for place modelling, allowing to specify high-level goals for robot navigation and description of trajectories. In [START_REF] Borkowski | Towards semantic navigation in mobile robotics[END_REF] semantics is used to represent the environment as a graph of places. The robot reasons about space with this graph-based representation of places where semantics is embedded in the nodes while edges correspond to accessibility. A navigation framework based on high-level understanding of the world is proposed in [START_REF] Posada | Visual semantic robot navigation in indoor environments[END_REF]. As in the previous work, semantics are used both to define places and robot's actions related to navigation. Spherical images are labelled with Random Forest and a place recognition module is used that is based on SVM. The navigation behaviour is then described as a sequence of low-level behaviours organised in a hierarchical way. Similarly in [START_REF] Klaus | From structure to actions: Semantic navigation planning in office environments[END_REF] semantic regions and positions are defined to allow the robot to plan its path at a high-level. Each node of the graph is connected to others through edges encoding reachability of a place from another. Planning is done using metric constraints like the euclidean distance of two nodes.

The related problem of interpreting route from description has also received significant attention. For example a framework combining automatic semantic place labelling and human route description interpretation is presented in [START_REF] Landsiedel | Route description interpretation on automatically labeled robot maps[END_REF]. To handle the possible ambiguity that occurs due to perception errors, a probability distribution over the possible paths is built, and the best path is chosen computing the MAP of the distribution. In [START_REF] Matuszek | Following directions using statistical machine translation[END_REF], a machine translation technique from natural language input is used to infer a most likely path within a Voronoi graph where the nodes of the graph correspond to different places like room, hall or doorways.

All these works offer high-level description for path planning. They model space as a set of semantic places connected topologically through robot's actions or metric constraints. However, all these works rely on the attribution of a label to each place to localize the robot. This is not feasible in outdoor environments where there is no clear separation between different places which is an issue that we specifically address in the proposed framework.

III. SEMANTIC MAP FOR NAVIGATION

In this paper we address two problems: finding the best route according to high-level criteria and describing it using surrounding objects all along the trajectory. To address these problems, we rely on the map structure illustrated in fig 1 and a localization scheme described in our previous work [START_REF] Drouilly | Fast hybrid relocation in large scale metric-topologic-semantic map[END_REF]. For the sake of completeness we briefly review them in the following paragraph.

A. Hybrid Metric-Topologic-Semantic Map

Our map consists of a set of local submaps connected to each other in a graph whose edges are pairwise pose estimates. Those submaps are built from data captured by our multicamera stereovision system, described in [START_REF] Meilland | A spherical robot-centered representation for urban navigation[END_REF]. It allows to capture ego-centered spherical views of the scene augmented with depth data. From the sequence of images acquired, we keep only reference keyframes as detailed in [START_REF] Meilland | Dense visual mapping of large scale environments for real-time localisationtime localisation[END_REF]. That comprises the RGB-D level of submaps. Atop of this layer lies the label layer which is the result of the automatic annotation of the spherical views [START_REF] Drouilly | Fast hybrid relocation in large scale metric-topologic-semantic map[END_REF]. The scene parsing process occurs in two steps: first Random Forests are used to estimate the probability distribution over classes for each pixel. Then a Fully Connected Conditional Random Field corrects results taking into account neighbourhoods. Given a labelled image, a set of contiguous pixels with the same label is called a semantic area, denoted as A i . It can contain several instances of each class depending of the perspective viewpoint. The contiguous semantic areas are connected to each other through edges E i j encoding their relative position in image, constituting a semantic graph G = {A, E}. This representation, is powerful as it encodes in a very compact way both the structure and the semantic content of the scene.

B. Semantic Content-based Localization

Following a route needs to solve the robot localization issue. An efficient algorithm for localization in our map has been developed in [START_REF] Drouilly | Fast hybrid relocation in large scale metric-topologic-semantic map[END_REF], where localization is formulated as a content request problem and allows to localize an image or a set of objects. The semantic graph is first extracted from the current annotated image. Then, the localization consists in comparing it with those of the submaps to estimate similarities. The comparison is done with an interpretation tree [START_REF] Grimson | Object Recognition by Computer: The Role of Geometric Constraints[END_REF] matching one by one the nodes of the current semantic graph to those of the reference semantic graph using nodes properties and context. The similarity score σ between two semantic graphs G 1 and G 2 is measured as follows:

σ (G 1 , G 2 ) = exp 1-N Nm (1)
where N m is the number of nodes matched between the two graphs denoted as A 12 = A G1 A G 2 and N the total number of nodes in the current semantic graph. The submap with the highest score σ corresponds to the most probable location.

IV. SEMANTIC-BASED ROUTE PLANNING

A route is defined by a set of adjacent local submaps in the global graph. Once submaps corresponding to the current and the target positions of the robot are found, the route planning problem consists in finding the best path in the graph to go from one to the other. We want to optimize this path with respect to semantic criteria, therefore we need to use semantics to weight edges between nodes. To do this, we define a heuristic cost function that computes the weight of an edge depending on the semantic scene content. Two adjacent submaps share objects that are visible from the two viewpoints. The cost function relies on these objects. The highest is the weight, the more penalized will be the path. Several scene features are used to build the cost function, listed as follows:

a) Number of shared objects: To navigate within our map, the robot needs landmarks all along the way. If the environment changes considerably between two submaps, the risk for the robot to be lost is higher as it may not be able to localize itself. Therefore the higher is the number of objects shared between two submaps the more it should be preferred. However this number strongly depends on the number of objects visible in a given scene. Therefore we compute the number of objects shared relatively to the total number of objects visible in the current scene. The Shared Objects Score S is:

S(G 1 , G 2 ) = 1 -σ (G 1 , G 2 ) (2)
b) Object class: objects can be more or less helpful landmarks for navigation depending on their class. Cars are dynamic objects and therefore not well suited to characterize a place while buildings are stable landmarks. We give a weight to all classes according to their expected usefulness for purpose of navigation. The lowest is the penalizing weight, the more useful is the object. For an edge between two adjacent submaps, we compute the Class Score C as the average of the class weight of each shared object:

C(G 1 , G 2 ) = 1 N m ∑ i∈A 12 w(c i ) (3)
where N m is the number of objects as stated before, w i the weight of the object i that is a function of the class c i .

Averaging over all objects allows to mesure the dynamics of the scene, that is what we want to penalize. c) Object observability: Another important feature is the length of the path along which an object is visible. It is preferred that they remain observable on a long range so that the robot can use them as landmarks. Each object is indexed in a table with the number of submaps where it is observable. Taking the maximum of this table as o max for normalization, we compute the Observability Score O of an edge as follows:

O(G 1 , G 2 ) = 1 N m ∑ i∈A 12 (1 -exp(1 - o max o i )) (4)
where o i is the individual observability of each object. d) Object Spatial Repartition: It is important to observe objects in all directions in the spherical image in order to constrain the pose, all ideally by finding the same amount of objects in all directions. We model this ideal repartition by a uniform probability distribution of finding objects with respect to the direction of observation, denoted as P. Then the image is cut in four parts corresponding to front, right, left and back. We count the number of objects in each direction and divide by the total, building the actual repartition function, denoted as Q. The penalty of using the actual repartition instead of the ideal repartition is computed using the Kullback-Leibler divergence of Q with respect to P:

KL(Q||P) = 4 ∑ i=1 (P(i).log( P(i) Q(i) ) (5)
where the sum is performed on the four parts of the image. Finally the Repartition Score R is computed as: Finally the cost of a path p, made of N edges e i is defined as follows:

R = 1 -exp(-KL(Q||P)) (6)
F s (p) = N ∑ i=1 S(e i ) +C(e i ) + O(e i ) + R(e i ) (7)
Summing over all edges allows to implicitely take into account the length of the path. With all the weights in the global graph having been computed, the best path, from the semantic perspective, is found using the well-known Dijkstra's algorithm.

V. SEMANTIC ROUTE DESCRIPTION

Once the best route is selected within the graph, it can be useful to automatically describe it for human-robot interaction. Many works have addressed the problem of describing the route in terms of high-level behaviour of the robot and semantic places sequence (see section II). Despite slight differences between them, all these works rely on the concept of place that is straightforward indoors, but difficult to define outdoors. In this part, we propose another approach to describe the route at a high level without using places so that our work can easily adapt to any diverse environment. Additionally, our approach naturally alleviates labelling errors by preferring stable objects for which label confidence is higher.

A. Route Description Language

A route is given as an ordered sequence of local submaps S = {s i }. As previously stated, semantic edges connecting submaps encode the object set shared by the two corresponding submaps and they can be described in terms of objects features.

To describe the path at a high level, the transition t i→i+1 between s i and s i+1 is decomposed in two elements:

• The movement type: turn or move forward/backward • Its amplitude: do movement until Each image is cut in four quarters Q i corresponding to front, back, right and left. The front is set in the center of the spherical image, corresponding to the image of the first camera on the camera ring of our sensor. A given orientation is described semantically by giving the quarter where each object center belongs to. This results in a set of Orientation

B. Description Compression

Many objects are visible along the path but they are not all equally important in describing the route. Some objects are visible for a very short time and are not useful to navigate. Additionally, the constraints sets can be similar for successive poses on a long range if the same objects are observed and the movement is constant. Then we may compress the route description using only objects visible on a long range and keeping the same set of constraints. It is worth noting that using only objects with good observability increases the robustness of our approach. In fact, errors in the labelling process produce objects with very small observability and these objects are filtered by this selection process. As each object is tracked along the path, it is easy to know how long a given object will be visible. To choose the best constraint we refer to the index used to compute the observability score (see fig 3). For a given set of constraints, we keep only those referring to objects with the best observability. Instead of computing new constraints at each step, the existing constraints are checked. While they are valid no new constraint is added to the set.

VI. EXPERIMENTS

We propose two separate series of experiments to evaluate our semantic route planning and our automatic description framework. For both, we first use a simulated world in which a virtual multi-camera sensor captures 360 o views of the environment. We use simulated data as it is more convenient to generate specific cases to highlight the performance and the particular aspects of our algorithm. Then, we show that our algorithm is fully functional in a real-world environment using a challenging dataset where images are automatically labelled with our previous approach presented in [START_REF] Drouilly | Fast hybrid relocation in large scale metric-topologic-semantic map[END_REF].

A. Semantic-based route planning in a virtual world

Our first set of tests is performed on a dataset acquired with a virtual multi camera sensor. Our aim is to evaluate the behaviour of our algorithm depending on environmental features such as the number and class of objects.Our virtual world corresponds to an urban environment with buildings, roads, side-walks, trees, cars, sign panels and ground signs. In our first experiment, the robot is placed at a position from where four paths are possible to reach the target position (see fig 4). Along the first path, the robot encounters many objects, mainly cars, so that it could understand that the scene is highly dynamic. Along the second path, the robot can see a lot of objects with several cars and a few sign panels. The third path is characterized by a high number of sign panels and only a few cars. By this way there is a lot of objects and their mean class value is high. Finally the fourth path offers only a few objects to see, mainly sign panels. To be coherent with an urban scenario, the number of buildings and trees are more or less the same along each path.

Results of the first experiment are shown in the table I. The sum of the four scores for all the edges along each path are reported together with the relative score of each. The preferred path is the third one, as this path offers the best compromise between number of objects and dynamic of the scene. There is a large number of objects and most of them are static so the robot can progress safely. In contrast, the first path contains more objects but a significant part of them are cars and the robot strongly penalizes it. Additionally objects are seen on a short period of time producing a high Observability score. However, as this path contains the bigger number of objects its Repartition Score is the best. Although a small number of objects are visible, the last path has a low score as there are no dynamic objects and the linear sections are long enough to provide a small Observability score. The experiment shows that robot prefers paths with low dynamic, longer straight sections and more objects. However, the number of objects could conflict with the requirement for a minimum number of dynamic objects. In fact the Repartition Score(penality) decreases with the number of objects but the Class Score increases. It comes from the fact that areas with large number of objects contain more dynamic objects. Then the choice of the best path is a question of tradeoff between different scores. The tuning of the parameters w i allows us to adapt the robot's behaviour to different environments. This result is very close to what it is expected from human behaviour.

B. Semantic-based route planning in the real-world

Our second set of experiments is performed with a challenging real-world images dataset acquired on the INRIA campus. The environment is semi-urban, with a lot of trees and buildings, cars, side-walk, sign panels and ground signs on the road. Due to the configuration of the campus it is not possible to choose between multiple paths to go from one point to another. Consequently our test consists in evaluating the path weight given different starting positions in order to reach the same target. We also reporte the lenght of each path, computed as the sum of distances between each consecutive submaps. The path 1 and 2 are illustrated in fig 5 by blue and red lines respectively. The first one is a quasistraight line from the starting to the target position. They are two sections with a cars parked in front of building on one or two sides of the road. Along the second path the robot moves in a constantly changing environment with several turns, alternating places with trees, buildings and cars parked in several places. Places with cars are highlighted in fig 5 by dotted circles.

Results are presented in table II. The best path according to semantic criteria is the first one, even if it is slightly longer. This could be understood looking at the repartition of objects along the path. In the path 1 there are a lot of cars but they are concentrated in a two places. That way, they appear as a few semantic areas and the robot considers the dynamics of path 1 lower than dynamics of path 2, where cars are spread all along the trajectory and are identified individually. Furthermore, the first path is a straight line and it is possible to track objects on a long range. It results in a considerably better observability than in path 2. These results validate our approach in real outdoor environments, showing its ability to discriminate between the two routes in a human-friendly way. It shows that path length is not the best choice for navigation as the most dynamic path would have been chosen with classical approaches.

C. Automatic Route Description

We have evaluated the performances of our automatic route description framework through two parameters: the correctness of the produced descriptions and their compactness. Obviously, it is not possible to report the full description of a long path, so for the sake of simplicity, the correctness has been evaluated on a small simulated scene. Then the compactness, defined as the number of constraints sets used for a given number of keyframes, has been evaluated on a subset of the INRIA dataset, representing two very different paths, each composed of 200 keyframes.

1) Correctness of the description: The path consists of a straight line represented at fig 6. The dataset consists of 100 reference images. Along the path the robot generates three sets of constraints at the positions illustrated by the three numbers. The doted lines highlight objects used by robot.

The generated constraints are:

• Orientation: building (1) left, sign (2) right, sign (3) right Move forward until: end As expected, the path is described with a few constraints and is understandable by human. Despite the simplicity of the example, the result shows the ability to produce humanlike description of a path, which is our goal. results can be explained by the presence of many occlusions in the second case, that prevent from tracking objects on long range and then actualise constraints sets regularly. However, even if the compactness is lower than in the previous case, the number of constraints is still low. These results show that despite imperfect images annotations, it is possible to produce compact human-like descriptions of trajectories selected according to high-level criteria, in real-world scenes.

VII. CONCLUSION AND FUTURE WORK

A new approach to automatically select the best route has been presented. The use of semantic content of the scene to choose among several possible paths has been shown to be useful in complex environments where many factors influence robot behaviour. Both simulated and real-world dataset have been used to show the utility of the system. Furthermore a convenient approach for high-level route description has been introduced based on semantic graphs. Both contributions extend the state-of-the-art methods to outdoor environments and open new perspectives towards intelligent navigation and human-robot interaction.

1 http://youtu.be/JtuGG LS1Jg Extensions of our work can be sought in several directions. Objects are tracked locally in successive images and occlusions can temporally hide an object. Tracking objects not only in successive images but in several neighbours can overpass this problem. Path description and planning would benefit from these improvements. Finally, taking into account the long-term evolution of the environment by monitoring changes can improve path planning process providing the robot with more information about dynamic aspects of the scene.

Fig. 1 .

 1 Fig. 1. Building Process of local submaps. Ego-centered spherical images are automatically labelled with Random Forest and CRF. Then a Semantic Graph is extracted from the labelled image.

Fig. 2 .

 2 Fig. 2. Illustration of the path description for two consecutive images in the case of translation (a) and composed movement (b). The spherical image is illustrated by a blue circle with a cross highlighting the four quarters. Each object appearing in a different quarter allows to describe the movement of the robot. In example (a), the generated constraints are: move forward until green object ∈ Q le f t and orange ∈ Q right

Fig. 3 .

 3 Fig. 3. Index of the objects present for each submap. Observability correspond to the length of arrows. Object 1 and 4 are interesting as they are observed many times while object 3 and 5 are not.

Fig. 4 .

 4 Fig. 4. Map of the simulated world. The four paths are highlighted by the four dashed lines. The black line is the path 1 along which robot meets lots of cars and objects. Following path 2, the blue line, the robot meets lots of objects among which cars and a few sign panels. The third path, materialised in orange, allows the robot to see several sign panels and a few cars. Along the last path, in green, robot sees only a few objects, mainly sign panels. The light blue point is the starting position and the red dot the target one.

Fig. 5 .

 5 Fig. 5. Example images of the real paths. The blue line (bottom) correspond to path 1 and the red line (top) to path 2. Cars are localized by dotted circles.

Fig. 6 .

 6 Fig. 6. Top: spherical view of the scene taken from position 2. Bottom: schematic view of the environment. Path 1 in simulated data. Robot is materialized by a crossed circle with an arrow, cars are red, trees green, building brown, panels blue. The robot uses 3 sets of constraints to describe the path at the position highlighted the figures.

2 )

 2 Compactness of the Description: To evaluate the compactness of the descritpion, two different paths have been chosen in INRIA dataset. For each, constraints sets have been generated according to environment features. The results are best viewed in the video 1 . For the first route, a quasi-straight line visible at fig 7 left, the robot has generated 7 constraints sets for 200 reference images. For the second path, visible at fig 7 right, the robot has generated 17 constraints sets for 200 reference images. The compactness are respectively 7/200 and 17/200. The large difference between those two

Fig. 7 .

 7 Fig. 7. The two paths used to test automatic route description. At the top is the path 1, below is the path 2.

TABLE I RESULTS

 I FOR SIMULATED WORLD.

	Score	S	C	O	R	Relative total score
	Path 1	19	102	93	148	100
	Path 2	21	85	91	153	98
	Path 3	18	81	88	149	92
	Path 4	19	81	90	158	95

TABLE II RESULTS

 II FOR REAL WORLD.

	Score	S	C	O	R	Relative score	Relative length
	Path 1	49	53	58	91	92	100
	Path 2	49	65	65	93	100	97

ACKNOWLEDGMENT

The work presented in this paper was supported by the French Fundation of technological Research under the grant CIFRE N2012/0067.