Frédérique Clément
email: frederique.clement@inria.fr.

Jean-Michel Coron
email: coron@ann.jussieu.fr.

Peipei Shang
email: peipei.shang@inria.fr.

Optimal control of cell mass and maturity in a model of follicular ovulation

Keywords: optimal control, conservation law, biomathematics. 2000 MR Subject Classification: 35L65, 49J20, 92B05

In this paper, we study optimal control problems associated with a scalar hyperbolic conservation law modeling the development of ovarian follicles. Changes in the age and maturity of follicular cells are described by a 2D conservation law, where the control terms act on the velocities. The control problem consists in optimizing the follicular cell resources so that the follicular maturity reaches a maximal value in fixed time. Formulating the optimal control problem within a hybrid framework, we prove necessary optimality conditions in the form of Hybrid Maximum Principle. Then we derive the optimal strategy and show that there exists at least one optimal bang-bang control with one single switching time.

Introduction

This work is motivated by natural control problems arising in reproductive physiology.

The development of ovarian follicles is a crucial process for reproduction in mammals, as its biological meaning is to free fertilizable oocyte(s) at the time of ovulation. During each ovarian cycle, numerous follicles are in competition for their survival. Few follicles reach an ovulatory size, since most of them undergo a degeneration process, known as atresia (see for instance [START_REF] Mcgee | Initial and cyclic recruitment of ovarian follicles[END_REF]). The follicular cell population consists of proliferating, differentiated and apoptotic cells, and the fate of a follicle is determined by the changes occurring in its cell population in response to an hormonal control originating from the pituitary gland.

A mathematical model, using both multiscale modeling and control theory concepts, has been designed to describe the follicle selection process on a cellular basis (see [START_REF] Echenim | Multi-scale modeling of the follicle selection process in the ovary[END_REF]). The cell population dynamics is ruled by a conservation law, which describes the changes in the distribution of cell age and maturity.

Cells are characterized by their position within or outside the cell cycle and by their sensitivity to the follicle stimulating hormone (FSH). This leads one to distinguish 3 cellular phases. Phase 1 and 2 correspond to the proliferation phases and Phase 3 corresponds to the differentiation phase, after the cells have exited the cell cycle.

The cell population in a follicle f is represented by cell density functions ρ f j,k (t, x, y) defined on each cellular phase Q f j,k , where j = 1, 2, 3 denotes Phase 1, Phase 2 and Phase 3, k = 1, 2, • • • denotes the number of the successive cell cycles (see figure 1). The cell density functions satisfy the following conservation laws:

∂ρ f j,k ∂t + ∂(g f (u f )ρ f j,k ) ∂x + ∂(h f (y, u f )ρ f j,k ) ∂y = -λ(y, U )ρ f j,k in Q f j,k , (1)
where

Q f j,k = Ω f j,k × [0, T ], with Ω f 1,k = [(k -1)a 2 , (k -1)a 2 + a 1 ] × [0, y s ], Ω f 2,k = [(k -1)a 2 + a 1 , ka 2 ] × [0, y s ], Ω f 3,k = [(k -1)a 2 , ka 2 ] × [y s , y m ]. E T • • • • • • y s y m y x 0 a 1 a 2 a 2 + a 1 2a 2 (k -1)a 2 (k -1)a 2 + a 1 ka 2 ρ f 1,1 ρ f 2,1 ρ f 3,1 ρ f 1,2 ρ f 2,2 ρ f 3,2 ρ f 1,k ρ f 2,k ρ f 3,k • • • • • • d d d d d d d d E E E E
as the maturity on the follicle scale, and

M (t) := f M f (t) (3)
as the maturity on the ovarian scale.

The velocities of aging g f and maturation h f as well as the loss term λ depends on the mean maturity of the follicle f through a local control u f (t, M f , M ) which represents intrafollicular bioavailable FSH level and the mean maturity of all the follicles through a global control U (t, M ) which can be interpreted as the FSH plasma level. One can refer to [START_REF] Echenim | Multiscale modeling of follicular ovulation as a reachability problem[END_REF][START_REF] Echenim | Multi-scale modeling of the follicle selection process in the ovary[END_REF][START_REF] Shang | Cauchy problem for multiscale conservation laws: Application to structured cell populations[END_REF] for more details on the model.

The aging velocity controls the duration of the cell division cycle. Once the cell age has reached a critical age, the mitosis event is triggered and a mother cell gives birth to two daughter cells. The two daughter cells enter a new cell cycle, which results in a local doubling of the flux. Hence, there are local singularities in the subpart of the domain where y y s , that correspond to the flux doubling due to the successive mitosis events. The maturation velocity controls the time needed to reach a threshold maturity y s , when the cell exits the division cycle definitively. After the exit time, the cell is no more able to contribute to the increase in the follicular cell mass.

Ovulation is triggered when the ovarian maturity reaches a threshold value M s . The stopping time T s is defined as

T s := min {T |M (T ) = M s } , (4)
and corresponds on the biological ground to the triggering of a massive secretion of the hypothalamic gonadotropin releasing hormone (GnRH).

As a whole, system (1)-(3) combined with stopping condition (4) defines a multiscale reachability problem. It can be associated to an optimal control problem that consists in minimizing T s for a given target maturity M s .

Some related control problems have already been investigated on a mathematical ground.

In [START_REF] Echenim | Multiscale modeling of follicular ovulation as a reachability problem[END_REF], the authors studied the characteristics associated with a follicle as an open-loop control problem. They described the sets of microscopic initial conditions compatible with either ovulation or atresia in the framework of backwards reachable set theory. Since these sets were largely overlapping, their results illustrate the prominent impact of cell dynamics control in the model. In [START_REF] Michel | Multiscale modeling of follicular ovulation as a mass and maturity dynamical system[END_REF], the author focused on the issue of the selection process in a game theory approach, where one follicle plays against all the other ones. Whether the follicle becomes atretic (doomed) or ovulatory (saved) depends on the follicular cell mass reached at the time when all cells stop proliferating.

The aim of this paper is to investigate whether there exists an optimal way for a follicle to reach ovulation. On the one hand, the follicle can benefit from a strong and quick enlargement of its cell population. On the other hand, this enlargement occurs at the expense of the maturation of individual cells. This compromise was instanced here as a problem of composition of velocities. A concept central to the understanding of these entangled processes is that of the management of follicular cell resources. There is indeed a finely tuned balance between the production of new cells through proliferation, that increases the whole cell mass, and the maturation of cells, that increases their contribution to hormone secretion.

The controllability of nonlinear hyperbolic equations (or systems) have been widely studied for a long time; for the 1D case, see, for instance [START_REF] Coron | Local controllability of a 1-D tank containing a fluid modeled by the shallow water equations[END_REF][START_REF] Coron | Exact boundary controllability for 1-D quasilinear hyperbolic systems with a vanishing characteristic speed[END_REF][START_REF] Coron | Controllability for a scalar conservation law with nonlocal velocity[END_REF][START_REF] Gugat | Boundary controllability between sub-and supercritical flow[END_REF][START_REF] Gugat | Global boundary controllability of the Saint-Venant system for sloped canals with friction[END_REF][START_REF] Li | Controllability and observability for quasilinear hyperbolic systems[END_REF][START_REF] Li | Exact boundary controllability for quasi-linear hyperbolic systems[END_REF][START_REF] Li | Exact boundary controllability and observability for first order quasilinear hyperbolic systems with a kind of nonlocal boundary conditions[END_REF][START_REF] Wang | Exact controllability for nonautonomous first order quasilinear hyperbolic systems[END_REF] for smooth solutions and [START_REF] Ancona | On the attainable set for scalar nonlinear conservation laws with boundary control[END_REF][START_REF] Bressan | On the boundary control of systems of conservation laws[END_REF][START_REF] Glass | On the controllability of the 1-D isentropic Euler equation[END_REF][START_REF] Thierry Horsin | On the controllability of the Burgers equation[END_REF] for bounded variation entropic solutions. In particular, [START_REF] Coron | Control and nonlinearity[END_REF] provides a comprehensive survey of controllability of partial differential equations including nonlinear hyperbolic systems. As far as optimal control problems for hyperbolic systems are concerned, one can refer to [START_REF] Gugat | Optimal switching boundary control of a string to rest in finite time[END_REF][START_REF] Gugat | Optimal control for traffic flow networks[END_REF][START_REF] Gugat | Flow control in gas networks: exact controllability to a given demand[END_REF][START_REF] Shang | Analysis and control of a scalar conservation law modeling a highly re-entrant manufacturing system[END_REF]. However, most of these monographs study the case where the controls are either applied inside the domain or on the boundary. Our control problem is quite different from the problems already studied in the literature, since the control terms appear in the flux. To solve the problem, we make use both of analytical methods based on Hybrid Maximum Principle (HMP) and numerical computations.

The paper is organized as follows. In section 2, we set the optimal control problem, together with our assumptions, and we enunciate the main result. In section 3, we give necessary optimality conditions from HMP in the case where Dirac masses are used as a rough approximation of the density. An alternative sketch of the proof based on an approximation method is given in appendix. Using the optimality conditions, we show that for finite Dirac masses, every measurable optimal control is a bang-bang control with one single switching time. In addition to the theoretical results, we give some numerical illustrations. In section 4, we go back to the original PDE formulation of the model, and we show that there exists at least one optimal bang-bang control with one single switching time.

2 Problem statement and introductory results

Simplifications with respect to the original model

To make the initial problem tractable, we have made several simplifications on the model dynamics.

S 1 . We consider only one developing follicle, i.e. f = 1; S 2 . There is no loss term anymore, i.e. λ = 0; S 3 . The age velocity is uncontrolled, i.e. g f ≡ 1;

S 4 . The cell division is represented by a new gain term, i.e. c(y) defined by [START_REF] Coron | Local controllability of a 1-D tank containing a fluid modeled by the shallow water equations[END_REF];

S 5 .
The target maturity M s can always be reached in finite time.

(S 1 ) means that, in this problem, we are specially interested in the control of the follicular cell resources for each follicle, in the sense that we ignore the influence of the other growing follicles. The goal is to find the optimal balance between the production of new cells and the maturation of cells.

In (S 2 ), we neglect the cell death, which is quite natural when considering only ovulatory trajectories, while, in (S 3 ), we consider that the cell age evolves as time. Moreover, the cell division process is distributed over ages with (S 4 ), so that there is a new gain term in the model instead of the former mitosis transfer condition.

Even if it is simplified, the problem studied here still captures the essential question of the compromise between proliferation and differentiation that characterizes terminal follicular development. A relatively high aging velocity tends to favor cell mass production, while a relatively high maturation velocity tends to favor an increase in the average cell maturity.

As shown in section 2.4, assumptions (S 2 ) and (S 5 ) allow us to replace a minimal time criterion by a criterion that consists in maximizing the final maturity. Hence, from the initial, minimal time criterion, we have shifted, for sake of technical simplicity, to an equivalent problem where the final time is fixed and the optimality criterion is the follicular maturity at final time. On the biological ground, this means that for any chosen final time t 1 , the resulting maturity at final time M f (t 1 ) can be chosen in turn as a maturity target which would be reached in minimal time at time t 1 . It can be noticed that in the initial problem (4), there might be no optimal solution without assumption (S 5 ), if the target maturity is higher than the maximal asymptotic maturity.

Optimal control problem

Under these assumptions, we arrived to consider the following conservation law on a fixed time horizon:

       ρ t + ρ x + ((a(y) + b(y)u)ρ) y = c(y)ρ, t ∈ (t 0 , t 1 ), x > 0, y > 0, ρ(t, 0, y) = ρ(t, x, 0) = 0, t ∈ (t 0 , t 1 ), x > 0, y > 0, ρ(0, x, y) = ρ 0 (x, y), x > 0, y > 0, (5)
where

a(y) := -y 2 , b(y) := c 1 y + c 2 , (6)
and

c(y) :=    c s , if y ∈ [0, y s ), 0, if y ∈ [y s , ∞), (7)
with y s , c s , c 1 and c 2 being given strictly positive constants. We assume that

y 2 s c 1 y s + c 2 < 1. ( 8
)
Let us denote by w a positive constant such that

w ∈ ( y 2 s c 1 y s + c 2 , 1). ( 9
)
From ( 6) and ( 9), we have

a(y) + b(y)u > 0, ∀y ∈ [0, y s ], ∀u ∈ [w, 1]. ( 10
)
Throughout this paper the control u is assumed to satisfy the constraint

u ∈ [w, 1]. ( 11
)
The left constraint w in [START_REF] Coron | Controllability for a scalar conservation law with nonlocal velocity[END_REF] ensures that the maturation velocity is always positive in the proliferation phase. The right constraint in ( 11) is natural since FSH plasma levels are bounded. The maximal bound can be scaled to 1 for sake of restricting the number of parameters in the model.

By [START_REF] Coron | Controllability for a scalar conservation law with nonlocal velocity[END_REF], there is a maximal asymptotic maturity ȳ on the cell scale, i.e. the positive root y of a(y) + b(y)u = 0 with control u = 1. From ( 6), we have

ȳ = c 1 + c 2 1 + 4c 2 2 . ( 12
) Let u ∈ L ∞ ((t 0 , t 1 ); [w, 1]). Let us define the map Ψ : [t 0 , t 1 ] × [0, y s ] × L ∞ ((t 0 , t 1 ); [w, 1]) → [0, ȳ] (t, y 0 , u) → Ψ(t, y 0 , u) by requiring    ∂Ψ ∂t (t, y 0 , u) = a(Ψ(t, y 0 , u)) + b(Ψ(t, y 0 , u))u(t), Ψ(t 0 , y 0 , u) = y 0 . (13)
Let us now define the exit time t0 as

Ψ( t0 , 0, w) = y s . (14)
Let us point out that, by [START_REF] Coron | Analysis of a conservation law modeling a highly re-entrant manufacturing system[END_REF], there exists one and only one t0 satisfying [START_REF] Echenim | Multi-scale modeling of the follicle selection process in the ovary[END_REF]. Note that it is not guaranteed that the exit time t0 occurs before the final time t 1 , so that we may have t0 > t 1 . When t > t0 , all the cells are in Phase 3, i.e. their maturity is larger than the threshold y s . After time t0 the mass will not increase any more due to [START_REF] Coron | Local controllability of a 1-D tank containing a fluid modeled by the shallow water equations[END_REF]. The maximal cell mass that can be reached at t0 is obtained when applying u = w from the initial time.

For any admissible control u ∈ L ∞ ((t 0 , t 1 ); [w, 1]), we define the cost function

J(u) := - +∞ 0 +∞ 0 y dρ(t 1 , x, y), (15)
and we want to study the following optimal control problem:

minimize J(u) for u ∈ L ∞ ((t 0 , t 1 ); [w, 1]). (16)
A similar minimal time problem was investigated in another ODE framework [START_REF] Clément | Optimal control of the cell dynamics in the granulosa of ovulatory follicles[END_REF], where the proliferating and differentiated cells were respectively pooled in a proliferating and a differentiated compartment. The author proved by Pontryagin Maximum Principle (PMP) that the optimal strategy is a bang-bang control, which consists in applying permanently the minimal apoptosis rate and in switching once the cell cycle exit rate from its minimal bound to its maximal one. In contrast, due to the fact that c is discontinuous, we cannot apply PMP directly here. The idea is to first consider optimal control problems for Dirac masses (see section 3), and then to pass to the limit to get optimal control results for the PDE case (see section 4).

For "discontinuous" optimal control problems of finite dimension, one cannot derive necessary optimality conditions by applying directly the standard apparatus of the theory of extremal problems [START_REF] Bressan | Introduction to the mathematical theory of control, volume 2 of AIMS Series on Applied Mathematics[END_REF][START_REF] Ioffe | Theory of extremal problems[END_REF][START_REF] Pontryagin | The mathematical theory of optimal processes[END_REF]. The first problem where the cost function was an integral functional with discontinuous integrand was dealt in [START_REF] Arutyunov | On necessary optimality conditions in a problem with phase constraints[END_REF]. Later, in [START_REF] Alexey | Necessary optimality conditions for a class of optimal control problems with a discontinuous integrand[END_REF], the author studied the case of a more general functional that includes both the discontinuous characteristic function and continuous terms. There, the author used approximation methods to prove necessary optimality conditions in the form of PMP. One of the difficulties of our problem is that both the integrand of the cost function and the dynamics are discontinuous.

However, our problem can be classified as a hybrid optimal control problem, since the problem has a discontinuous dynamics ruled by a partition of the state space. One of the most important results in the study of such problems is the HMP proved in [START_REF] Garavello | Hybrid necessary principle[END_REF][START_REF] Piccoli | Hybrid systems and optimal control[END_REF][START_REF] Héctor | Hybrid maximum principle[END_REF][START_REF] Héctor | A nonsmooth hybrid maximum principle[END_REF].

There, the authors followed the standard line of the full procedure for the direct proof of PMP, based on the introduction of a special class of control variations, and the computation of the increments of the cost and all constraints. In [START_REF] Dmitruk | The hybrid maximum principle is a consequence of pontryagin maximum principle[END_REF], the authors formulated the hybrid problem as a classical optimal control problem. They then proved the HMP using the classical PMP. Later, in [START_REF] Haberkorn | Convergence results for smooth regularizations of hybrid nonlinear optimal control problems[END_REF], the authors regularized the hybrid problems to standard smooth optimal control problems, to which they can apply the usual PMP. They also derived jump conditions appropriate to our problem.

The main result of this paper is the following theorem.

Theorem 2.1. Let us assume that

t 1 > t0 , (17)
2y s -c 1 > 0 and c s > a(y s ) + b(y s ) y s . ( 18
)
Then, among all admissible controls u ∈ L ∞ ((t 0 , t 1 ); [w, 1]), there exists an optimal control u * for the minimization problem (16) such that

∃ t * ∈ [t 0 , t 1 ] such that u * = w in (t 0 , t * ) and u * = 1 in (t * , t 1 ). ( 19
)
Remark 2.1. From the mathematical viewpoint, assumptions (17) and (18) arise naturally from the computations (see section 3.2.1). Condition [START_REF] Gugat | Boundary controllability between sub-and supercritical flow[END_REF] means that we consider a target time large enough so that all the cells have gone to the differentiation phase. Condition [START_REF] Gugat | Optimal switching boundary control of a string to rest in finite time[END_REF] gives specific relations between the proliferation rate and the parameters of the maturation velocity. Together, these relations are related to the transit time within the proliferation phase.

Remark 2.2. In our case, the dynamics of ρ is essentially one-dimensional, since there is a transport with constant velocity along variable x and we have just to deal with variable y.

Hence our results can be generalized to n-spatial dimensional problem like

ρ t + m • ∇ x ρ + (h(y, u)ρ) y = c(y)ρ, ( 20
)
where m is a constant vector. Generalization to n-spatial dimensional dynamics with both velocities controlled should also be feasible.

Solution to Cauchy problem (5)

In this section, we give the definition of a (weak) solution to Cauchy problem [START_REF] Brezis | Functional analysis, Sobolev spaces and partial differential equations[END_REF].

Let ρ 0 be a Borel measure on R × R such that

ρ 0 0, (21)
and the support of

ρ 0 is included in [0, 1] × [0, y s ]. (22)
Let

K := [0, t 1 -t 0 + 1] × [0, ȳ]. Let M (K)
ρ : [t 0 , t 1 ] → M (K) such that, for every ϕ ∈ C 0 (K), K ϕ(α, β)dρ(t, α, β) = K ϕ(x 0 + t -t 0 , Ψ(t, y 0 , u)) e t t 0
c(Ψ(s,y 0 ,u))ds dρ 0 (x 0 , y 0 ). ( 23)

We take expression [START_REF] Thierry Horsin | On the controllability of the Burgers equation[END_REF] as a definition. This expression is also justified by the fact that if ρ 0 is a L ∞ function, one recovers the usual notion of weak solutions to Cauchy problem [START_REF] Brezis | Functional analysis, Sobolev spaces and partial differential equations[END_REF] studied in [START_REF] Coron | Control and nonlinearity[END_REF][START_REF] Coron | Analysis of a conservation law modeling a highly re-entrant manufacturing system[END_REF][START_REF] Shang | Cauchy problem for multiscale conservation laws: Application to structured cell populations[END_REF][START_REF] Shang | Analysis and control of a scalar conservation law modeling a highly re-entrant manufacturing system[END_REF], as well as by the characteristics method used to solve hyperbolic equations (see figure 2).

Remark 2.3. From (23), if ρ 0 is a positive Borel measure, then solution ρ is also a positive Borel measure. If ρ 0 ∈ C 0 or if ρ 0 is Lipschitz continuous, then ρ ∈ C 0 or ρ is Lipschitz continuous, but if ρ 0 ∈ C 1 ,
it may happen that ρ is not in C 1 due to the fact that c(y) is discontinuous.

Minimal time versus maximal maturity

In this section, we show that the two optimal control problems enunciate either as: "minimize the time to achieve a given maturity" or "achieve a maximal maturity at a given time" are equivalent when S 2 and S 5 hold. The threshold target maturity Ms in S 5 can be computed x,y) is the characteristic curve passing through (t, α, β) that intersects the initial plane t = t 0 at (t 0 , x 0 , y 0 ). from the maximal cell mass combined with the maximal asymptotic maturity ȳ when applying u = w from the initial time until t0 and u = 1 thereafter, so that S 5 can be formulated as:

M s < Ms := ȳ ∞ 0 ∞ 0 dρ( t0 , x, y). (24)
Let ρ 0 be a nonzero Borel measure on R × R satisfying ( 21) and [START_REF] Haberkorn | Convergence results for smooth regularizations of hybrid nonlinear optimal control problems[END_REF]. Let us denote by M u (t) the maturity at time t for the control u ∈ L ∞ ((t 0 , t 1 ); [w, 1]) (and the initial data ρ 0 ).

A. For fixed target time t 1 , suppose that the maximum of the maturity M is achieved with an optimal control u ∈ L ∞ ((t 0 , t 1 ); [w, 1])

M u (t 1 ) = M. (25)
Then we conclude that for this fixed M , the minimal time needed to reach M is t 1 with the same control u. We prove it by contradiction. We assume that there exists another control

ũ ∈ L ∞ ((t 0 , t1 ); [w, 1]) such that M ũ( t1 ) = M, t1 < t 1 . (26)
We extend ũ to [t 0 , t 1 ] by requiring ũ = 1 in ( t1 , t 1 ]. Let us prove that

t ∈ [ t1 , t 1 ] → M ũ(t) is strictly increasing. ( 27
)
Let ρ : [t 0 , t 1 ] → M (K) be the solution to Cauchy problem (5) (see section 2.3). Note that a(y) + b(y) > 0 for every y ∈ [0, ȳ) and that, for every t ∈ [t 0 , t 1 ], the support of ρ(t) is included in [0, t 1 -t 0 + 1] × [0, y s ). Together with [START_REF] Thierry Horsin | On the controllability of the Burgers equation[END_REF] for ρ = ρ and ϕ(α, β) = β, this proves [START_REF] Li | Exact boundary controllability for quasi-linear hyperbolic systems[END_REF]. From [START_REF] Li | Exact boundary controllability for quasi-linear hyperbolic systems[END_REF] it follows that

M ũ(t 1 ) > M ũ( t1 ) = M, (28)
which is a contradiction with the optimality of u.

B. For any fixed target maturity M , suppose that the minimal time needed to reach M is t 1 with control u ∈ L ∞ ((t 0 , t 1 ); [w, 1]). Then we conclude that for this fixed target time t 1 , the maximal maturity at time t 1 is M with the same control u. We prove it again by contradiction. We assume that there exists another control ũ ∈ L ∞ ((t 0 , t 1 ); [w, 1]) such that

M ũ(t 1 ) > M. (29)
Then by the continuity of M ũ(t) with respect to time t, there exists a time t1 < t 1 such that

M ũ( t1 ) = M, (30)
which is a contradiction with the minimal property of t 1 . This concludes the proof of the equivalence between the two optimal control problems.

3 Results on optimal control for finite Dirac masses

In this section, we give results on the optimal control problem ( 16) when the initial data ρ 0 0 is a linear combination of a finite number of Dirac masses. For (α, β) tr ∈ R 2 , we denote by δ α,β the Dirac mass at (α, β) tr . We assume that, for some positive integer N , there exist N elements ((x k0 1 , x k0 2 )) k∈{1,...,N } of [0, 1] × [0, y s ] and N strictly positive real numbers (x k0

3 ) k∈{1,...,N } such that

ρ 0 := N k=1 x k0 3 δ x k0 1 ,x k0 2 . ( 31
)
First, we formulate our problem within a hybrid framework. Let us denote by X α and X β two disjoint and open subsets of R 3 , where

X α := (x 1 , x 2 , x 3 ) ∈ R 3 |x 2 < y s , X β := (x 1 , x 2 , x 3 ) ∈ R 3 |x 2 > y s .
The boundary between the two domains X α (t) and X β (t) can be written as

(x 1 , x 2 , x 3 ) ∈ R 3 |F (x) = 0 ,
where

F (x) := x 2 -y s . (32)
We consider the following Cauchy problem:

   ẋk = f (x k , u), u ∈ L ∞ ((t 0 , t 1 ); [w, 1]), t ∈ [t 0 , t 1 ], x k (t 0 ) = x k0 , (33)
where

f (x k , u) :=    f α (x k , u), x k ∈ X α , f β (x k , u), x k ∈ X β , x k =     x k 1 x k 2 x k 3     , x k0 =     x k0 1 x k0 2 x k0 3     , (34)
with

f α (x k , u) :=     1 a(x k 2 ) + b(x k 2 ) u c s x k 3     , f β (x k , u) :=     1 a(x k 2 ) + b(x k 2 ) u 0     .
It is easy to check that the maximal solution to Cauchy problem ( 33) is defined on [t 0 , t 1 ].

One can also easily check that the solution to Cauchy problem (5), as defined in section 2.3, is

ρ(t) = N k=1 x k 3 (t)δ x k 1 (t),x k 2 (t) . (35)
The cost function J defined in (15) now becomes

J(u) = N k=1 -x k 2 (t 1 ) x k 3 (t 1 ). ( 36
)
We define

f 0 (x k , u) :=    f 0 α (x k , u), x k ∈ X α , f 0 β (x k , u), x k ∈ X β ,
where

f 0 α (x k , u) = -a(x k 2 ) + b(x k 2 )u + c s x k 2 x k 3 , f 0 β (x k , u) = -a(x k 2 ) + b(x k 2 )u)x k 3 .
Hence, to minimize (36) is equivalent to minimize

J(u) = N k=1 t 1 t 0 f 0 (x k , u) dt - N k=1 x k0 2 x k0 3 . (37)
One of the goals of this section is to prove that there exists an optimal control for this optimal control problem and that, if ( 17) and ( 18) hold, every optimal control is bangbang with only one switching time. More precisely, we prove the following Theorem 3.1 and Theorem 3.2.

Using [START_REF] Coron | Analysis of a conservation law modeling a highly re-entrant manufacturing system[END_REF], we can easily check the continuity of the exit time with respect to the weak- * L ∞ topology for the control. From the standard Arzelà-Ascoli theorem, we then get the following theorem (see also [31, Theorem 1])

Theorem 3.1. The optimal control problem (16) has a solution, i.e., there exists u * ∈ L ∞ ((t 0 , t 1 ); [w, 1]) such that

J(u * ) = inf u∈L ∞ ((t 0 ,t 1 );[w,1]) J(u).
Theorem 3.2. Let us assume that (17) and (18) hold. Then, for every optimal control u * for the optimal control problem (16), there exists t * ∈ (t 0 , t 1 ) such that u * = w in (t 0 , t * ) and u * = 1 in (t * , t 1 ). [START_REF] Wang | Exact controllability for nonautonomous first order quasilinear hyperbolic systems[END_REF] This section is organized as follows. In subsection 3.1 we prove a HMP (Theorem 3.3) for our optimal control problem. In subsection 3.2 we show how to deduce Theorem 3.2 from Theorem 3.3.

Hybrid Maximum Principle

Let us define the Hamiltonian

H : (R 3 ) N × R × (R 3 ) N → R (x, u, ψ) = ((x 1 , x 2 , . . . , x N ), u, (ψ 1 , ψ 2 , . . . , ψ N )) → H(x, u, ψ) by H(x, u, ψ) := N k=1 f (x k , u), ψ k - N k=1 f 0 (x k , u). (39)
In (39) and in the following, a, b denotes the usual scalar product of a ∈ R 3 and b ∈ R 3 .

Let us also define the Hamilton-Pontryagin function

H : (R 3 ) N × (R 3 ) N → R by H(x, ψ) := max u∈[w,1] H(x, u, ψ). (40)
It follows from [START_REF] Dmitruk | The hybrid maximum principle is a consequence of pontryagin maximum principle[END_REF][START_REF] Garavello | Hybrid necessary principle[END_REF][START_REF] Haberkorn | Convergence results for smooth regularizations of hybrid nonlinear optimal control problems[END_REF][START_REF] Piccoli | Hybrid systems and optimal control[END_REF][START_REF] Héctor | Hybrid maximum principle[END_REF][START_REF] Héctor | A nonsmooth hybrid maximum principle[END_REF] that we have the following theorem:

Theorem 3.3. Let u * ∈ L ∞ ((t 0 , t 1 ); [w, 1]) be an optimal control for the optimal control problem [START_REF] Glass | On the controllability of the 1-D isentropic Euler equation[END_REF]. Let x k and

ψ k 1 ( tk -0) = ψ k 1 ( tk + 0), (48)
ψ k 3 ( tk -0) = ψ k 3 ( tk + 0), (49)
• if tk < t 1 , ψ k 2 ( tk + 0) -ψ k 2 ( tk -0) ∈ c s x k * 3 ( tk )(y s + ψ k 3 ( tk )) a(y s ) + b(y s ) , c s x k * 3 ( tk )(y s + ψ k 3 ( tk )) a(y s ) + b(y s ) w , (50)
ψ k 2 (t 1 ) = 0, ( 51
)
• if tk = t 1 , -ψ k 2 (t 1 ) ∈ 0, c s x k * 3 (t 1 )y s a(y s ) + b(y s ) w . ( 52
)
Moreover, there exists a constant h such that the following condition holds

H(x k * (t), u * (t), ψ k (t)) = H(x k * (t), ψ k (t)) = h, a.e. t ∈ (t 0 , t 1 ). ( 53
)
Proof of Theorem 3.3. For sake of simplicity, we give the proof only for one Dirac mass (N = 1). To simplify the notations we also delete the k = 1 index. For more than one Dirac mass, the proof is similar.

Applying the HMPs given in [START_REF] Dmitruk | The hybrid maximum principle is a consequence of pontryagin maximum principle[END_REF][START_REF] Garavello | Hybrid necessary principle[END_REF][START_REF] Haberkorn | Convergence results for smooth regularizations of hybrid nonlinear optimal control problems[END_REF][START_REF] Piccoli | Hybrid systems and optimal control[END_REF][START_REF] Héctor | Hybrid maximum principle[END_REF][START_REF] Héctor | A nonsmooth hybrid maximum principle[END_REF], we get the existence of ψ = (ψ 1 , ψ 2 , ψ 3 ) tr ∈ W 1,∞ (((t 0 , t) ∪ ( t, t 1 )) ∩ (t 0 , t 1 )) 3 such that (44) to (49) and, if t < t 1 , (51) hold, together with the existence of h ∈ R such that (53) is satisfied. Let us finally deal with (50) and (52). Let us treat only the case where t < t 1 (the case t = t 1 being similar).

We follow [START_REF] Haberkorn | Convergence results for smooth regularizations of hybrid nonlinear optimal control problems[END_REF]. From (53), there exist v 1 ∈ [w, 1] and v 2 ∈ [w, 1] such that

H( t -0) = max v∈[w,1] H(x( t -0), v, ψ( t -0) = H(x( t -0), v 1 , ψ( t -0)) =< f (x( t -0), v 1 ), ψ( t -0) > -f 0 (x( t -0), v 1 ), (54)
H( t + 0) = max v∈[w,1] H(x( t + 0), v, ψ( t + 0)) = H(x( t + 0), v 2 , ψ( t + 0)) =< f (x( t + 0), v 2 ), ψ( t + 0) > -f 0 (x( t + 0), v 2 ). ( 55
)
From ( 53), ( 54) and (55), we obtain

ψ 2 ( t + 0) -ψ 2 ( t -0) = c s x 3 ( t )(y s + ψ 3 ( t )) + b(y s )(x 3 ( t ) + ψ 2 ( t -0))(v 1 -v 2 ) a(y s ) + b(y s )v 2 , ( 56
)
and

ψ 2 ( t + 0) -ψ 2 ( t -0) = c s x 3 ( t )(y s + ψ 3 ( t )) + b(y s )(x 3 ( t ) + ψ 2 ( t + 0))(v 1 -v 2 ) a(y s ) + b(y s )v 1 . ( 57
)
The Hamiltonian (39) becomes

H(x, u, ψ) =(a(x 2 ) + c(x 2 )x 2 ) x 3 + ψ 1 + a(x 2 )ψ 2 + c(x 2 )x 3 ψ 3 + b(x 2 )(x 3 + ψ 2 ) u, t ∈ [t 0 , t 1 ]. ( 58
)
Let us denote

Φ := x 3 + ψ 2 . ( 59
)
When t = t, from ( 7), ( 43) and ( 45), we obtain

dΦ dt = -(a (x 2 ) + b (x 2 )u) Φ. ( 60
)
Noting that

Φ(t 1 ) > 0. ( 61
)
Combining ( 60) and ( 61), we get

Φ(t) > 0, ∀t ∈ ( t, t 1 ]. ( 62
)
Next, we analyze different cases:

1. When Φ( t -0) > 0 and Φ( t + 0) > 0, we have v 1 = v 2 = 1. From ( 56) or (57), we get

ψ 2 ( t + 0) -ψ 2 ( t -0) = c s x 3 ( t)(y s + ψ 3 ( t)) a(y s ) + b(y s ) . ( 63
)
2. When Φ( t -0) < 0 and Φ( t + 0) > 0, we have v 1 = w and v 2 = 1. From (56), we get

ψ 2 ( t + 0) -ψ 2 ( t -0) = c s x 3 ( t)(y s + ψ 3 ( t)) + b(y s )Φ( t -0)(w -1) a(y s ) + b(y s ) . ( 64
)
Since Φ( t -0) < 0, from (64), we obtain

ψ 2 ( t + 0) -ψ 2 ( t -0) > c s x 3 ( t)(y s + ψ 3 ( t)) a(y s ) + b(y s ) . ( 65
)
From (57), we have

ψ 2 ( t + 0) -ψ 2 ( t -0) = c s x 3 ( t)(y s + ψ 3 ( t)) + b(y s )Φ( t + 0)(w -1) a(y s ) + b(y s )w . ( 66
)
Since Φ( t + 0) > 0, from (66), we obtain

ψ 2 ( t + 0) -ψ 2 ( t -0) < c s x 3 ( t)(y s + ψ 3 ( t)) a(y s ) + b(y s )w . ( 67
)
3. When Φ( t -0) = 0 and Φ( t + 0) > 0, from (56), we obtain

ψ 2 ( t + 0) -ψ 2 ( t -0) = c s x 3 ( t)(y s + ψ 3 ( t)) a(y s ) + b(y s ) . ( 68
)
In the three cases, we have proved that jump condition (50) holds. This concludes the proof of Theorem 3.3.

Using the first inequality of ( 18), ( 51), ( 72) and (77), we get

Φ( t + 0) x 3 (t 1 ). ( 78
)
Noticing that x 3 ( t + 0) = x 3 (t 1 ) and using ( 76) and (78), we get

Φ( t -0) x 3 (t 1 )(1 -c s y s a(y s ) + b(y s ) ). ( 79
)
From the second inequality of ( 18) and ( 79), we get

Φ( t -0) < 0. ( 80
)
which, together with (60), gives us

Φ(t) < 0, t ∈ [t 0 , t ). ( 81
)
Moreover, by (51), we have

Φ(t) = (x 3 + ψ 2 )(t 1 ) = x 3 (t 1 ) > 0,
which together with (60), gives

Φ(t) > 0, t ∈ ( t, t 1 ]. ( 82
)
Taking t * = t and combining (81) and (82), with (69) and (70), we conclude the proof of Theorem 3.2 in the case where N = 1.

Numerical illustration in the case N = 1

For one Dirac mass, the optimal switching time is unique. Assumption ( 18) is not necessary to guarantee that the optimal control is a bang-bang control with only one switching time. It is just used to guarantee that the optimal switching time coincides with the exit time. We give a numerical example to show that when c s is "small", there is no switch at all and the optimal control is constant (u = 1), while when c s is "large", there is a switch occuring at the exit time (see figure 3).

The default parameter values are specified in Table 1 for the numerical studies.

Proof of Theorem 3.2 in the case N > 1

Now, the Hamiltonian (39) becomes in the case of one Dirac mass. When c s is "small", there is no switching time (t = 0) and the optimal control is constant (u = 1), while, when c s is "large", the optimal control strategy consists in switching from u = w to u = 1 at a time coinciding with the exit time. The initial values are specified in the insert.

H(x, u, ψ) = N k=1 (a(x k 2 ) + c(x k 2 )x k 2 )x k 3 + ψ k 1 + a(x k 2 )ψ k 2 + c(x k 2 )x k 3 ψ k 3 + b(x k 2 )(x k 3 + ψ k 2 )u , t ∈ [t 0 , t 1 ]. (83)
Reordering if necessary the x k 's, we may assume, without loss of generality, that

x 10 2 < x 20 2 < . . . < x k0 2 < . . . < x N 0 2 . (84)
Let u be an optimal control for the optimal control problem (16) and let x = (x 1 , . . . , x k , . . . x N ),

with x k = (x k 1 , x k 2 , x k
3 ) tr , be the corresponding trajectory. From (84), we have

tN < tN-1 < . . . tk < . . . < t1 . ( 85
) Let Φ N : [t 0 , t 1 ] → R be defined by Φ N (t) := N k=1 b(x k 2 (t))(x k 3 (t) + ψ k 2 (t)). ( 86
) u = w, if Φ N (t) < 0, (87)
u = 1, if Φ N (t) > 0. (88)
We take the time-derivative of (86) when t = tk , k = 1, • • • , N . From (6), we obtain

ΦN (t) = N k=1 (c 1 (x k 2 ) 2 + 2c 2 x k 2 )(x k 3 + ψ k 2 ). (89)
Similarly to the above proof for one Dirac mass, we can prove that, under assumption (18), we have, for each

k = 1, • • • , N , (x k 3 + ψ k 2 )(t) < 0, when t ∈ (t 0 , tk ), (90)
(x k 3 + ψ k 2 )(t) > 0, when t ∈ ( tk , t 1 ). (91)
By ( 85), ( 86), ( 90) and ( 91), and note that b(x k 2 ) > 0, we get

Φ N (t) < 0, when t ∈ (t 0 , tN ), (92)
Φ N (t) > 0, when t ∈ ( t1 , t 1 ).

The key point now is to study the dynamics of Φ N between different exit times tk . Let k ∈ {1, • • • , N -1} and let us assume that Φ N (t) = 0, for some t ∈ ( tk+1 , tk ).

From ( 86) and (94), we get

x k 3 (t) + ψ k 2 (t) = - i =k b(x i 2 (t)) b(x k 2 (t)) (x i 3 (t) + ψ i 2 (t)). (95)
From ( 90) and (91), for every t ∈ ( tk+1 , tk ),

x i 3 (t) + ψ i 2 (t) < 0, when i k -1, (96)
x i 3 (t) + ψ i 2 (t) > 0, when i k + 1. (97)
From ( 6), ( 89) and (95), we get

ΦN (t) = i k-1 x i 3 + ψ i 2 b(x k 2 ) c 2 1 x i 2 x k 2 + 2c 2 2 + c 1 c 2 (x i 2 + x k 2 ) (x i 2 -x k 2 ) + i k+1 x i 3 + ψ i 2 b(x k 2 ) c 2 1 x i 2 x k 2 + 2c 2 2 + c 1 c 2 (x i 2 + x k 2 ) (x i 2 -x k 2 ). (98)
From (84), we get

x i 2 (t) -x k 2 (t) < 0, when i k -1, (99)
x i 2 (t) -x k 2 (t) > 0, when i k + 1. ( 100
)
Using ( 96) to (100), we get ΦN (t) > 0 whenever Φ N (t) = 0, ∀t ∈ ( tk+1 , tk ). ( 101)

Combining ( 87), ( 88), ( 92), ( 93) and ( 101) together, we get the existence of t * ∈ (t 0 , t 1 ) such that u * = w in (t 0 , t * ) and u * = 1 in (t * , t 1 ).

This concludes the proof of Theorem 3.2.

Numerical illustration in the case N > 1

The optimal control can in some cases be not unique for more than one Dirac mass. Let us consider the case of two Dirac masses as an example. The optimal switching time may happen either at the first exit time or at the second exit time (see figure 4), or between the two exit times (see figure 5).

Optimal control in the PDE case

In this section, we study the optimal control in the PDE case. We give the proof of Theorem 2.1. We first give an explicit expression for the cost function J defined in [START_REF] Garavello | Hybrid necessary principle[END_REF].

Let us define a new map

e : [0, y s ] × L ∞ ((t 0 , t 1 ); [w, 1]) → [t 0 , t 1 ] (y 0 , u) → e(y 0 , u) by requiring Ψ(e(y 0 , u), y 0 , u) = y s , where Ψ is defined by [START_REF] Echenim | Multiscale modeling of follicular ovulation as a reachability problem[END_REF]. Note that, under assumption [START_REF] Gugat | Boundary controllability between sub-and supercritical flow[END_REF], one has, for every y 0 ∈ [0, y s ], the existence of t ∈ [t 0 , t 1 ] such that

Ψ(t, y 0 , u) = y s . (102)
Again, [START_REF] Coron | Analysis of a conservation law modeling a highly re-entrant manufacturing system[END_REF] implies that there exists at most one t ∈ [t 0 , t 1 ] such that (102) holds. This shows that e is well defined. Moreover, we have the following lemma Lemma 4.1. Let (y n 0 ) n∈N be a sequence of elements in [0, y s ] and (u n ) n∈N be a sequence of elements in L ∞ ((t 0 , t 1 ); [w, 1]). Let us assume that, for some y 0 ∈ [0, y s ] and for some u ∈ L ∞ ((t 0 , t 1 ); [w, 1]),

y n 0 → y 0 as n → +∞, u n * u in L ∞ (t 0 , t 1 ) as n → +∞.
From ( 103), ( 105), ( 110) and ( 112) and a classical theorem on the weak topology (see, e.g., [5, (iv) of Proposition 3.13, p. 63]), one has

J(ρ n 0 , u n * ) → J(ρ 0 , u * ) as n → +∞. ( 113
)
Let now u ∈ L ∞ ((t 0 , t 1 ); [w, 1]). From Lemma 4.1, ( 103) and ( 105), one gets

J(ρ n 0 , u) → J(ρ 0 , u) as n → +∞. (114)
Finally, letting n → +∞ in (107) and using (113) together with (114), one has

J(ρ 0 , u * ) J(ρ 0 , u),
which concludes the proof of Theorem 2.1.

Appendix

Sketch of another proof of Theorem 3.3

In this section, we sketch another proof of Theorem 3.3, using approximation arguments inspired from [START_REF] Alexey | Necessary optimality conditions for a class of optimal control problems with a discontinuous integrand[END_REF]. The interest of this approach is that it might be more suitable to prove a maximal principle also in the PDE case. For sake of simplicity, we show the proof only for one Dirac mass. The idea is first to construct a smooth optimal control problem. For the smooth optimal control problem, we can apply PMP. By passing to the limit, we then derive necessary optimality conditions for our discontinuous problem.

Step 1. Let us denote by χ : R → R the characteristic function of (-∞, y s ), i.e.

χ(x 2 ) =    1, ∀x 2 ∈ (-∞, y s ), 0, ∀x 2 ∈ [y s , +∞). ( 115
) Let (w i ) i∈N * be a sequence of elements in C ∞ (R) such that 0 w i , R w i (x) dx = 1, support w i ⊂ [-1/i, 0], ∀i ∈ N * , (116)
and, for some C > 0,

|w i (x)| Ci 2 , ∀x ∈ R, ∀i ∈ N * , (117)
(clearly such a sequence does exist). Then, we define a sequence of functions (χ i ) i∈N * from R into R as follows:

χ i (x) := R χ(y) w i (x -y) dy = ys -∞ w i (x -y) dy = +∞ x-ys w i (z) dz, ∀i ∈ N * , ∀x ∈ R. (118) f i (x, u) :=     1 a(x 2 ) + b(x 2 ) u c s χ i (x 2 ) x 3     , ∀x = (x 1 , x 2 , x 3 ) tr ∈ R 3 , ∀u ∈ R. (119)
Let u * be an optimal control for the optimal control problem ( 16) and let x * be the associated trajectory. Let (z i ) i∈N * be a sequence of uniformly bounded elements of C 1 ([t 0 , t 1 ]) such that

z i → u * in L 2 (t 0 , t 1 ) as i → +∞. ( 120
) Let us then define J i : L ∞ ((t 0 , t 1 ); [w, 1]) → R by J i (u) := - t 1 t 0 a(x 2 ) + b(x 2 )u + c s χ i (x 2 )x 2 x 3 dt + 1 √ i t 1 t 0 |u(t) -z i (t)| 2 dt -x 0 2 x 0 3 , where x : [t 0 , t 1 ] → R 3 is the solution to the Cauchy problem ẋ = f i (x, u), x(t 0 ) = x 0 . (121)
We consider the following optimal control problem minimize J i (u) for u ∈ L ∞ ((t 0 , t 1 ); [w, 1]). (P i )

For any i = 1, 2, • • • , problem (P i ) is a "smooth" optimal control problem. By a classical result in optimal control theory (see, e.g., [25, Corollary 2, p. 262]), there exists an optimal control u i for problem (P i ). Let x i be the optimal trajectory corresponding to the control u i for dynamics (121). We have the following lemma (compare to [START_REF] Alexey | Necessary optimality conditions for a class of optimal control problems with a discontinuous integrand[END_REF]Lemma 4]):

Lemma 4.2. The following holds as i → +∞ u i → u * in L 2 (t 0 , t 1 ), (122)

x i → x * in C 0 ([t 0 , t 1 ]; R 3 ), (123)
χ i (x i2 ) → χ(x * 2 ) in L 1 (t 0 , t 1 ). ( 124
)
Step 2. We now deduce necessary optimality conditions for the optimal control problem [START_REF] Glass | On the controllability of the 1-D isentropic Euler equation[END_REF]

) ψi2 = -(a (x i2 ) + b (x i2 ) u i ) ψ i2 -c s χ i (x i2 ) x i3 ψ i3 -(a (x i2 ) + b (x i2 ) u i ) x i3 -c s χ i (x i2 ) x i3 -c s x i2 χ i (x i2 ) x i3 , 130
= -c s χ i (x i2 ) ψ i3 -(a(x i2 ) + b(x i2 )u i ) -c s x i2 χ i (x i2 ), (131) ψi3
ψ i1 (t 1 ) = ψ i2 (t 1 ) = ψ i3 (t 1 ) = 0. ( (132)
) 133
We can prove that

ψ i1 (t) = ψ 1 (t) = 0, ∀t ∈ [t 0 , t 1 ], (134)
and

ψ i3 → ψ 3 in C 0 ([t 0 , t 1 ]) as i → +∞. ( 135
)
As far as ψ i2 is concerned, Theorem 3.3 in the case where x * 2 (t 0 ) = x 0 2 = y s or x * 2 (t 1 ) < y s follows directly from the standard PMP. Hence, we may assume that x * 2 (t 0 ) < y s x * 2 (t 1 ).

(136)

Let us treat the case where

x * 2 (t 0 ) < y s < x * 2 (t 1 ), (137) (the case x * 2 (t 1 ) = y s being similar). By [START_REF] Coron | Analysis of a conservation law modeling a highly re-entrant manufacturing system[END_REF], there exists one and only one t ∈ (t 0 , t 1 ) such that x * 2 ( t ) = y s .

Using ( 123) and (138), one also gets that, at least if i is large enough, which, from now on, will always be assumed, there exists one and only one ti ∈ (t 0 , t 1 ) and one and only one ti ∈ (t 0 , t 1 ) such that

x i2 ( ti ) = y s , x i2 ( ti ) = y s -(1/i). ( 139
)
Using ( 122) and (123), we can prove ti → t and ti → t as i → +∞.

(140)

It is easy to check that

ψ i2 → ψ 2 in C 0 ([t 0 , t -ε] ∪ [ t + ε, t 1 ]), ∀ε > 0. ( 141
)
We now prove jump condition (50) when t < t 1 , the proof of (52) when t = t 1 being similar.

Let us integrate (131) from ti to ti , we get Letting i → +∞ in (129), we get the existence of h such that (53) holds. This concludes the proof of Theorem 3.3.

ψ i2 ( ti ) -ψ i2 ( ti ) = A(i) + B(i), (142)

Figure 1 :

 1 Figure 1: Cellular phases on the age-maturity plane for each follicle f . The domain consists of the sequence of k = 1, 2, • • • cell cycles. Variable x denotes the age of the cell and variable y denotes its maturity. Number y s is the threshold value at which cell cycle exit occurs and y m is the maximal maturity. The top of the domain corresponds to the differentiation phase and the bottom to the proliferation phase.

  be the set of Borel measures on K, i.e. the set of continuous linear maps from C 0 (K) into R. The solution to Cauchy problem (5) is the function

Figure 2 :

 2 Figure 2: Construction of a weak solution by backward tracking of the characteristics. Variables x and y respectively denote the age and maturity, y s is the threshold maturity and ȳ is the maximal asymptotic maturity. The initial mass concentrates in the shaded area [0, 1] × [0, y s ]. The curve ξ = (x, y) is the characteristic curve passing through (t, α, β) that

c 1 Figure 3 :

 13 Figure 3: Value of the cost function J with respect to the switching time (t) and c s parameter

Figure 4 :

 4 Figure 4: Value of the cost function J with respect to the switching time (t) in the case of two Dirac masses and a "large" value of c s (c s = 1.0). In the left panel, the three-part curve represents the value of the cost function obtained after switching from u = w to u = 1 at time t. Blue dashed curve: switching time occurring before the first exit time; green solid curve: switching time occurring in between the two exit times; red dashed curve: switching time occurring after the second exit time. The initial values are specified in the insert. The right panel is a zoom on the green solid curve displayed on the left panel. There are two optimal switching times which coincide with the two exit times.

Figure 5 :

 5 Figure 5: Value of the cost function J with respect to the switching time (t) in the case of two Dirac masses and a "large" value of c s (c s = 0.8). In the left panel, the three-part curve represents the value of the cost function obtained after switching from u = w to u = 1 at time t. Blue dashed curve: switching time occurring before the first exit time; green solid curve: switching time occurring in between the two exit times; red dashed curve: switching time occurring after the second exit time. The initial values are specified in the insert. The right panel is a zoom on the green solid curve displayed on the left panel. There is one single optimal switching time, which occurs in between the two exit times.

From Lemma 4 .

 4 1 and (111), one gets e(•, u n * ) → e(•, u * ) in C 0 ([0, y s ]) as n → +∞.

  x i2 ) + b (x i2 ) u i ) (ψ i2 + x i3 ) + c s χ i (x i2 ) x i3 ) dt,(143)B(i) := -ti ti c s x i3 (x i2 + ψ i3 ) χ i (x i2 ) dt. (144)It is easy to obtain thatA(i) → 0 as i → +∞. (145)For B(i), we perform the change of variable τ = x i2 (t). By (139) and (144), we getB(i) = -ys ys-(1/i) c s x i3 (x -1 i2 (τ )) (τ + ψ i3 (x -1 i2 (τ ))) a(τ ) + b(τ )u(x -1 i2 (τ )) χ i (τ ) dτ.(146)Let us point out that, from (116) and (118), one hasys ys-(1/i) χ i (τ ) dτ = -1, χ i 0. (147)From (10), (123), (135), (146), (147), one gets thatc s x * 3 ( t )(y s + ψ 3 ( t )) a(y s ) + b(y s ) lim inf i→+∞ B(i) lim sup i→+∞ B(i) c s x * 3 ( t )(y s + ψ 3 ( t )) a(y s ) + b(y s )w ,which, together with (140), (141), (142) and (145), gives (50).

  in the form of PMP. The Hamiltonian and the Hamilton-Pontryagin function for problem (P i ) are respectivelyH i (x, u, ψ) = f i (x, u), ψ + (a(x 2 ) + b(x 2 )u + c s χ i (x 2 )x 2 )x 3 -and there exist constants h i such thatH i (x i (t), u i (t), ψ i (t)) = H i (x i (t), ψ i (t)) = h i , a.e. t ∈ (t 0 , t 1 ). (129)Let us denote ψ i = (ψ i1 , ψ i2 , ψ i3 ) tr . From (119), (127) and (128), we have

	ψi1 = 0,			(
		1 √ i	|u -z i (t)| 2 ,	(125)
	H i (x, ψ) = max u∈[w,1]	H i (x, u, ψ).		(126)

By the PMP -see, e.g.,

[START_REF] Bruce | Foundations of optimal control theory[END_REF] Theorem 2, p. 319

] or [4, Section 6.5]-, there exists an absolutely continuous function

ψ i : [t 0 , t 1 ] → R 3 such that ψi a.e. = -∂f i ∂x (x i , u i ) tr ψ i -∂ ∂x (a(x i2 ) + b(x i2 )u i + c s χ i (x i2 )x i2 )x i3 ,

(127)

ψ i (t 1 ) = 0,

(128)

Acknowledgements

We thank Emmanuel Trélat for useful discussions on the Hybrid Maximum Principle.

JMC was partially supported by the ERC advanced grant 266907 (CPDENL) of the 7th Research Framework Programme (FP7). PS was supported by the INRIA initiative action REGATE (REgulation of the GonAdoTropE axis). * = (x k *

Proof of Theorem 3.2

In this section, we use the necessary optimality conditions given in Theorem 3.3 to prove Theorem 3.2. From now on, we assume that the target time t 1 satisfies t 1 > t0 so that all the cells will exit from Phase 1 into Phase 3 before time t 1 . We give a proof of Theorem 3.2 in the case where N = 1 in section 3.2.1. In section 3.2.3, we study the case where N > 1; in this case we need additionally to analyze the dynamics between different exit times tk , k = 1, 2, • • • , N , to obtain that there exists one and only one switching time and that the optimal switching direction is from u = w to u = 1. In both cases N = 1 or N > 1, we give some numerical illustrations, respectively in section 3.2.2 and section 3.2.4.

Proof of Theorem 3.2 in the case N = 1

Let u be an optimal control for the optimal control problem ( 16) and let x = (x 1 , x 2 , x 3 ) tr be the corresponding trajectory. Note that, by ( 6), b(x 2 ) > 0. Then, by ( 40), ( 53), ( 58) and ( 59), one has, for almost every t ∈ (t 0 , t 1 ),

Let us recall that, under assumption (17) of Theorem 3.2, there exists one and only one t ∈ [t 0 , t 1 ) such that

Then

We study the case where t > t 0 , the case t = t 0 being obvious. Thanks to (50), we get

By ( 42) and (46), we get

and then, using also [START_REF] Coron | Local controllability of a 1-D tank containing a fluid modeled by the shallow water equations[END_REF], (47), (71), ( 72) and (74), we obtain

Combining ( 73) with (75), we get

By ( 6) and (60), we obtain

Then e(y n 0 , u n ) → e(y 0 , u) as n → +∞.

Let now ρ 0 be a Borel measure on R × R such that ( 21) and ( 22) hold. Using ( 23), [START_REF] Garavello | Hybrid necessary principle[END_REF] becomes

Ψ(t 1 , y 0 , u) e cse(y 0 ,u) dρ 0 (x 0 , y 0 ). ( 103)

In order to emphasize the dependence of J on the initial data ρ 0 , from now on we write J(ρ 0 , u) for J(u).

It is well known that there exists a sequence ((x i,n 0 , y i,n 0 , λ i,n 0 ))

From Theorem 3.1 and Theorem 3.


Ben Faten
email: faten.benhmida@ensi.rnu.tnwided.chaari@ensi.rnu.tn

Wided Lejouad Hmida

Chaari

Rémy Dupas
email: remy.dupas@u-bordeaux1.fr

Anne Seguy
email: anne.seguy@u-bordeaux1.fr

"Performance, interoperability and safety for sustainable development" GRAPH-BASED EVALUATION OF ORGANIZATION IN MULTAGENT SYSTEMS

Keywords: MultiAgent Systems, Evaluation, Organization, Graph Theory, Measure, Modelling, Observation

This paper deals with the evaluation of multiagent systems. The related works in this issue are most often interested in evaluation of agent design methodologies or agent tools and platforms but do not address sufficiently evaluation of multiagent applications from a general point of view, the used evaluation criteria remain either specific to a special topic or application dependent. In this work we present an evaluation approach to measure general characteristics of multiagent systems. The proposed method follows a three step process: observation, modelling and measure. The modelling technique is based on graph theory which is used to define and estimate metrics for the evaluation of structural properties of multiagent systems. In this paper, we focus especially in organization as evaluation criterion as it is a very interesting characteristic transposing the social dimension of multiagent systems. Therefore, specific metrics based on graph theory are proposed to analyse agent organizational structures. The tests and experimentations are carried out on a multiagent application for the simulation of production planning and control in supply chains.

INTRODUCTION

In the last decades, multiagent technology has become widely used in various fields and the number of developed multiagent applications is currently increasing considerably. Despite the great interest that the scientific community bears to this growing research area, there are still open issues particularly regarding standardization and definition of consensus on key concepts. One of the most critical issues in this domain is the question of performance evaluation which was addressed from different points of view. In this perspective, evaluating design methodologies and development platforms and tools is undeniably of great interest but remains insufficient to make a full coverage of multiagent systems evaluation. It becomes more and more necessary and urgent to provide means for evaluating and comparing multiagent applications. That is what we address through our research works which focus on agent-oriented applications evaluation based on specific characteristics especially structural ones. In previous works, we focused on one of the most important characteristics of multiagent systems which is communication. In this paper we are interested in organization and we propose several metrics to evaluate it based on graph theory. The paper is organized as follows: in section 2 a literature review of multiagent systems evaluation is presented. The proposed evaluation approach is then described in section 3. Section 4 presents an overview on organization in multiagent systems and the used metrics to evaluate it. The application on which tests and experimentations were carried out is described in section 5 with the obtained results and their interpretations. A conclusion and a look at future work are presented in section 6.

EVALUATION OF MULTIAGENT SYSTEMS: STATE OF THE ART

The several studies related to multiagent systems evaluation do not address the evaluation issue from the same point of view. In the following paragraphs we classify the presented works into four categories according to the evaluation objective in order to position our contribution.

Agent technology

The early works in this domain were interested in evaluating the multiagent technology as a new software engineering technique and tried to compare it to other existing ones namely the object-oriented one, as it was considered the leading technology at that time. For instance in [START_REF] Wooldridge | Agentoriented software engineering: the state of the art[END_REF], [START_REF] Tveit | A survey of agent-oriented software engineering[END_REF] and (Lind, 2001), agents and objects are compared with reference to some key criteria such as autonomy, self behaviour control, flexibility, parallelism and ability to represent mental components. All of these researches concluded that agent-oriented paradigm brought to software engineering many interesting novel concepts and that it allows dealing with complex problems and addressing dynamic environments more effectively.

MOSIM'12 -June 06-08, 2012 -Bordeaux -France

Agent design methodologies

Evaluation of agent-oriented methodologies aims to provide common frameworks for comparing the wide range of existing design approaches. [START_REF] Cernuzzi | On the evaluation of agent oriented modeling methods[END_REF] defines qualitative evaluation criteria organized as an attribute tree. Evaluation criteria are classified into three generic categories which are: internal agents' attributes, interaction attributes and process. [START_REF] Sturm | A framework for evaluating agent-oriented methodologies[END_REF] examine criteria encompassed within the methodology definition; these criteria cover four major aspects namely concepts and properties, notation and modelling techniques, process, and pragmatics. The proposed framework was used to evaluate and compare three methodologies: GAIA, Tropos and MaSE [START_REF] Sturm | A comparative evaluation of agent oriented methodologies[END_REF]. In [START_REF] Dam | Comparing agentoriented methodologies[END_REF] almost the same decomposition of criteria is used to compare MaSE, Prometheus and Tropos. Another work [START_REF] Akbari | Evaluation Framework for Agent-Oriented Methodologies[END_REF] attempts to identify strengths and weaknesses of agent-oriented methodologies by defining an evaluation framework that addresses six major areas: concepts, notation, process, pragmatics, support for software engineering and marketability. [START_REF] Sudeikat | Evaluation of agent-oriented software methodologies -examination of the gap between modeling and platform[END_REF] claims that "a complete evaluation of methodologies cannot be done without considering target platforms". This type of evaluation aims to help developers choosing the agent-oriented development tool that is most suited to their expectations. In this perspective, [START_REF] Boissier | Un essai de définition de critères pour l'étude comparative de plates-formes multi-agents[END_REF] defines criteria to evaluate and compare agent-oriented tools. The evaluation criteria were grouped into five categories that cover the whole life cycle of multiagent systems, namely: general characteristics, multiagent models, physical characteristics, development environment and execution environment. In [START_REF] Nguyen | Agent platform evaluation and comparison[END_REF], another set of evaluation criteria is proposed which are: standard compatibilities, communication, agent mobility, security, availability, usability, development issues. In both researches, no quantification methods were presented to estimate the proposed criteria. In [START_REF] Leszczyna | Evaluation of agent platforms[END_REF], the study focuses only on FIPA compliant agent platforms which were evaluated according to general criteria such as documentation, update, popularity, accessibility, etc. These criteria are not specific to agent-oriented environments; that's why the study remains too general. At the opposite, very specific criteria are proposed in [START_REF] Shakshuky | Multi-agent development toolkits: an evaluation[END_REF] to evaluate agent platforms. The work focuses especially on the Message Transport System.

Agent tools and platforms

Agent applications

This kind of evaluation in which we are specifically interested addresses implemented multiagent systems and deals especially with the multiagent application's performance regardless of the used design methodology and development tool.

Although there is little interest on this issue, we retrieved some related works from the literature. We classify those works into two subcategories: internal and external performance evaluation.

Internal performance evaluation

Internal evaluation refers to the process by which the multiagent system itself measures its performance. This is done most of the time by calculating a global utility function. A utility function expresses the functional adequacy of the multiagent system, i.e. how well it realizes the objective for which it was designed; it is defined a priori and depends on the problem to solve [START_REF] Thomas | Construction de systèmes multi-agents par apprentissage collectif à base d'interactions[END_REF]. In [START_REF] Gnanasambandam | An autonomous performance control framework for distributed multi-agent systems: a queueing theory based approach[END_REF], the authors propose a methodology to control the performance of a distributed agents' network. The multiagent system is equipped with a self-evaluating capability, so that it is up to the system itself to predict its performance by computing its overall utility which depends on metrics such as end-to-end delay and latency. The main problem with such evaluation method is that it could not be generalized. In fact, there is no general definition of a utility function, it is system dependent and is strongly linked to the problem which the multiagent system is supposed to solve.

External performance evaluation

External performance evaluation, unlike internal one, means that the evaluation is done by an entity outside the system. Although there is a great need for developing multiagent systems evaluation tools, few studies have addressed this issue from a general point of view. In fact, most of the works found in the literature propose evaluation solutions which are either system dependant or specific to a given topic. For instance, in [START_REF] O'malley | Comparing performance of static versus mobile multiagent system's[END_REF] a comparison between mobile and static multiagent systems is done. For this purpose, the performances of two distributed text search systems were evaluated using a single performance metric which is search execution time. In [START_REF] Helsinger | Tools and techniques for performance measurement of large distributed multiagent systems[END_REF], a performance measurement tool for large scale multiagent systems built into the Cougaar agent is presented. [START_REF] Hu | From local behaviours to global performance in a multi-agent system[END_REF] examines how local behaviours of agents can affect the global multiagent system's performance of Ro-boNBA which is a basketball game platform for autonomous robots. Local behaviours studied in this work are very specific to the target system. They include, for instance, strategies to pass the ball, strategies to defend or to attack, etc. So it is for global performance indicators which are ball control time, pass accuracy, etc. [START_REF] Babczy1ski | Performance comparison of multiagent systems[END_REF] presents a performance analysis and comparison of two information retrieval multiagent systems. The first is composed of only stationary agent while the second contains a mobile agent. Performance evaluation is carried out through simulation and the considered performance metrics include probability and mean time of receiving the good response which are very specific metrics.

MOSIM'12 -June 06-08, 2012 -Bordeaux -France

PROPOSED APPROACH FOR MULTIAGENT SYSTEMS EVALUATION

Through the previous study of the literature we showed that existing works on evaluation in multiagent domain are essentially oriented toward design methodologies and development platforms. The originality of our contribution is that we are interested in performance evaluation of MAS from a general point of view and regardless of its used methodology or platform.

In our research works, MAS are evaluated by measuring their functional characteristics. In fact, MAS have very interesting properties that may impact their global performances. These characteristics are identified and explained in [START_REF] Boissier | Caractéristiques des systèmes et des applications[END_REF]. Some of them can be presented as follows:

Autonomy: It consists in three important points: the agent's independent existence, its viability out of external control and its decision according only to perceptions and knowledge.

Distribution and Decentralization: Distribution means that knowledge, processing, tasks and resources are distributed among agents in order to achieve a common goal. While distribution concerns tasks and resources, decentralization means control distribution. In a multiagent system there is no global controller but the several agents participate to the control of the whole application.

Communication and Interaction:

The communication between agents provides coherence to the multiagent system in spite of decentralization. It could be performed directly by exchanging messages or indirectly by acting on the common environment. Agents interact in the environment in which they progress. Interactions between agents are point to point and include cooperation, collaboration, competition, negotiation, and delegation politics.

Organization: Organizations allow formalizing relationships between agents and offer a mean to specify and design a multiagent system structure that defines agents' roles and relations between these roles.

Openness and Adaptation: Openness is the functional evolution of the multiagent system. This evolution corresponds to the dynamic add, modification or removal of entities of the system. Adaptation is the ability of the multiagent system to modify its behaviour in order to evolve in a dynamic environment which is subject to many constraints.

In our research works we are especially interested in structural properties of MAS, which are evaluated following a specific process. The proposed evaluation method includes three major steps which are observation, modelling and measure, as shown in figure 1. In the following paragraphs, the several steps of the evaluation process are detailed.

Observation

Observation consists in collecting information related to the execution of a given system. It includes essentially detection of significant events in the system's execution and generation of traces [START_REF] Jain | The art of computer systems performance analysis[END_REF]. In our evaluation approach, observation is performed through software probes [START_REF] Ben Hmida | Aspect-Based MultiAgent Systems Observation for Performance Evaluation[END_REF]. The observation probes' design and implementation are based on Aspect Oriented Programming (AOP) which is a very promising software engineering technology [START_REF] Kiczales | Aspect-Oriented Programming[END_REF].

Figure 2 shows the proposed observation architecture. The probes are activated each time a significant event occurs in the MAS. For instance, each time an agent interacts with another agent, the event is detected and processed by a probe. So that all the agents' interactions are captured and saved in a traces file. The information contained in this file is used to generate the interaction graph of the MAS and compute the metrics.

Modelling

To evaluate properly the structural aspect of a MAS, we need to develop its formal representation. Using graphs to model such systems constitutes a very appropriate issue. In fact, graphs are commonly used to represent and study various types of computer networks and offer a strong abstraction and modelling tool for the real entities composing those networks. The study of graphs and their properties is done according to graph theory. Thus, the evaluated MAS is modelled by an oriented graph where the nodes represent the agents and the arcs represent the communication links between agents.

MOSIM'12 -June 06-08, 2012 -Bordeaux -France

According to [START_REF] Gondran | Graphes et algorithmes[END_REF] an oriented graph G = [X, U] is defined by: a set X of nodes, where |X| = N a set U of oriented pairs of nodes, where |U| = M There are several possible representations of a graph.

Here, the adjacency matrix is used.

( ) 1.. 1.. ij i N j N A A = = = (1)
In an adjacency matrix, each line (respect. column) corresponds to a node in the graph.

( ) ( )

1 if and only if , 0 otherwise ij ij A i j U A = ∈ = (2)
Thus, the proposed solution consists, first in modelling the interaction network of the MAS through an oriented graph, and then identifying the properties of this graph to evaluate it.

Measure

In this step, the generated graph representing the evaluated MAS is analysed according to specific criteria. To each criterion are associated measures which are then estimated. In previous works, we focused on communication as it is a very important property of multiagent systems [START_REF] Ben Hmida | Evaluation of communication in industrial multiagent systems[END_REF]. It is measured according to three main aspects which are: structural, syntactical and statistical aspects. Some of the used metrics are presented below:

solicitation / participation degrees of each agent complexity and connectivity of the MAS communication network average amount traffic per agent load of the network messages typology and complexity Communication is a central aspect, at the basis of the agents' interaction, and essential to realise the social attribute of the MAS. Besides, communication level in the MAS is one of the most important factors likely to affect its performance. However, it is not the only criterion according to which MAS could be evaluated. In fact, in [START_REF] Ben Hmida | Evaluation of communication in industrial multiagent systems[END_REF] interpretations of the obtained measures related to communication led us to evaluate other properties such as autonomy and organization. Thus, based on our previous works, our longterm goal is to propose an evaluation system allowing measuring several multiagent characteristics, and testing it on real world applications. This will greatly help promoting application of MAS especially in industry.

EVALUATION OF ORGANIZATION

At this stage of our research we are interested in the evaluation of the organizational aspect of multiagent systems.

Organization in multiagent systems

A multiagent system is a society of agents in a situation of mutual interaction sharing tasks, resources and/or knowledge. There is a large panel of possible interactions between agents which encompasses for example coordination, collaboration and negotiation politics [START_REF] Ferber | Les systèmes multi-agents, vers une intelligence collective[END_REF]. The several interaction patterns in a multiagent system engender complex organizational structures and interrelated acquaintances networks. Organizations can be formed in two ways. They can be defined a priori by the system's designer, in this case we talk about predefined organizations; or a posteriori as a result of the agents' social behaviours and interactions; and in this case we talk about emergent organizations [START_REF] Ferber | Les systèmes multi-agents, vers une intelligence collective[END_REF]. In the literature, many types of organizational structures are defined in multiagent systems. Generally speaking, these structures are groups of agents cooperating to realize their objectives. However, we can distinguish two categories of groups, namely teams and coalitions. In teams the agents are assembled together from the beginning in a way that their competences are complementary in order to realize the common objective of the team but not necessarily individual objectives. In coalitions the agents can come together promptly and collaborate to realize their individual interests in the absence of a common global objective [START_REF] Legras | Organisation dynamique d'équipes d'engins autonomes par écoute flottante[END_REF], [START_REF] Boussebough | Les systèmes multi-agents dynamiquement adaptables[END_REF].

In multiagent systems, there are also subordination relationships between agents concerning control and decision making. These relationships can be egalitarian where the agents are considered at the same level and participate evenly to the decision making process. In an egalitarian organizational structure, an agent can ask any other agent to accomplish a given task, but the latter may refuse to do it. On the other hand, there are hierarchical organizational structures where relationships between agents are authoritarian. Thus, organization is a very important characteristics and a basic concept of multiagent systems as it transposes the social dimension of such systems. The evaluation of organization is a very interesting issue; it allows developing an understanding of the multiagent system and its structure. [START_REF] Ferber | Les systèmes multi-agents, vers une intelligence collective[END_REF] defines the possible ways of analysing organizations in multiagent systems. From one hand there is functional analysis which aims to identify and describe the functions that the several entities of an organization are supposed to realize. From this prospect, organization is viewed as a set of roles and relations between those roles. From the other hand there is structural analysis which focuses on the interactions between agents trying to make sense to their complex interrelations and explain the resulting organizational structures.

In this work, great importance is accorded to the structural aspect of organizations, that's why the chosen representative model rely on graphs which expressively shapes the multiagent structure by drawing its entities MOSIM'12 -June 06-08, 2012 -Bordeaux -France and their relationships. A similar representation is used in [START_REF] Campagne | Systèmes Multi-agents et Morphologie[END_REF]. In this work, the author tries to develop a method to control massive multiagent systems organizations using morphology. For this purpose, graphs are used to describe the system's state. But in this representation, the nodes correspond to roles or groups' roles and the links correspond to mutual preferences between those roles. The analysis consists in states graphs comparison in order to make the system auto-adaptive [START_REF] Cardon | La complexité organisée. Systèmes adaptatifs et champ organisationnel[END_REF]. In our work, graph modelling is used for an evaluation purpose; we do not address control issue. Besides, in our case, the nodes correspond to agents and the links correspond to interactions between those agents, which is a different representation. Based on this model, the evaluation of organization is done thanks to specific metrics of graph theory which are presented in the following paragraph.

Measures for the evaluation of organization

The presented following measures are in the majority based on node degrees.

Degree distribution

In graph theory, the degree of a node is the number of connections it has to other nodes. Here we designate by Ki the degree of a node i. In a graph, the several nodes may have different degrees. The degree distribution P(K) is then defined to be the fraction of nodes in the graph with degree K:

( ) K N P K N = (3)
with N K the number of nodes having a degree K and N the total number of nodes.

The degree distribution is very important in studying graphs structures and helps understanding their topological features. The different types of networks have different characteristic degree distributions P(K). Thus, the shape of the degree distribution function allows distinguishing two main classes of networks (see figure 3). Homogeneous networks are characterized by a degree distribution that is concentrated around the degree mean value < K > given by: = ( )

K K P K < > × 1 (4)
In such networks, there are no highly connected nodes. On the contrary, heterogeneous networks are characterized by a degree distribution that generally follows a power law which is the case of most networks in the real world. This means that, in such networks, there is a large majority of nodes having low degree but a small number having high degree that greatly exceeds the average. Those nodes are thought to be special and having a specific function in their networks.

Assortativity

Assortativity is a characteristic of graphs which reflects the tendency of a graph's nodes to be connected to nodes having similar (or different) degrees. Assortativity is often examined in terms of correlation between nodes degrees. A simple characterization of the correlations between degrees of neighbour nodes is determined by the neighbourhood degree K nn,i which expresses the average neighbours degree of a given node i.

,

1 nn i j j i K K K = 1 (5)
Based on this measure, degree correlation is given by the mean neighbourhood degree of nodes with K degree. , / 1 ( )

i nn nn i i K K K K K K N = = 1 (6)
The behaviour of K nn (K) defines two main classes of networks. We talk about assortative network when K nn (K) increases with K. This is the case of social networks when high degree nodes are preferentially associated with other high degree nodes. And we talk about disassortative network K nn (K) decreases with K, which is the case of hierarchic networks where high degree nodes are connected to many nodes with low degree.

Centrality

Centrality is a characteristic expressing the position of a node in the graph. It determines the importance of a node within the network and how much it is influent. This concept is inspired from the analysis of social networks. Many terms are used to measure centrality; here the degree centrality is used. Cd(i) is the degree centrality of a node i.

( ) ( -1)

Ki Cd i N = ( 7
)
Where Ki is the degree of the node i and N is the number of nodes in the network.

MOSIM'12 -June 06-08, 2012 -Bordeaux -France

Hierarchy

We talk about hierarchy in organizations if relations between the organization entities are determined by authority. In oriented graphs, hierarchy is defined as follows:

1 V Hierarchy MaxV

2 3 = -4 5 6 7 (8)
With V the number of unordered pairs of nodes symmetrically connected, meaning that both of the nodes can reach each other, and MaxV is the total number of unordered pairs of nodes [START_REF] Krackhardt | Graph Theoretical Dimensions of Informal Organizations[END_REF]. This measure is interesting to express structural hierarchy of the network but does not reflect hierarchy degree in multiagent systems as it does not consider semantic meaning of a link. In fact, hierarchy degree in multiagent systems should reflect the existence of dominant agents.

For this reason, we propose to examine the nature of the several links between agents to determine whether there is any power relationship. The better way to do that is to pick up the nature of the message, and to deduce the existence of power relationship if the message is an order. Thus, the proposed measure for hierarchy is:

OrdV Hierarchy MaxV = ( 8
)
Where OrdV is the number of unordered pairs related by power relationship (message subject is order).

Leadership

As explained in section 4.1, in a multiagent system several agents can come together into organization structures called groups which may be teams or coalitions. In both cases, there can be an agent having the special capability of coordinating the actions of the other agents. This agent is called "leader" [START_REF] Legras | Organisation dynamique d'équipes d'engins autonomes par écoute flottante[END_REF]. While in a team the leader represents a decision authority, in a coalition the leader does not have a real decisional power but is rather a point of information centralization. To pick up such agents using graph formalism, a group is assimilated to a star sub-graph, with the leader as a central node surrounded by the other group agents [START_REF] Legras | Organisation dynamique d'équipes d'engins autonomes par écoute flottante[END_REF]. A star graph Sn of order n, sometimes simply known as an n-Star, is a graph on n nodes with one node having the degree n-1 and the other nodes having the degree 1 [START_REF] Harary | Graph Theory[END_REF]. Figure 4 illustrates such graphs.

Figure 4: Illustration of a star structure Thus, to recognize the leaders in a multiagent system, we have to identify the star sub-graphs in the whole representative graph.

EXPERIMENTATION AND RESULTS

The proposed evaluation system is tested on three versions of a supply chain control multiagent application.

Agent-based test application

The tested multiagent application is the implementation of a test-case considered in [START_REF] François | Planification des chaînes logistiques: modélisation du système décisionnel et performances[END_REF]. As shown in Figure 5, it is a multi-products supply chain network in the domain of furniture manufacturing. Two families of products are manufactured: tables and shelves. In a first step, wood trunks, delivered by the wood suppliers, are transformed by the sawmills into wood furniture components (trays, legs and boards). In a second step, shelves and tables are assembled by the assembly factory. Shelves are delivered to final customers, and tables are passed to the painting factory to be painted in a third and final step before being delivered to final customers. Distributer: this agent is responsible for the reception and the management of the customers' orders. It is also responsible for managing the products' stocks and deliveries.

Producer: this agent manages the material flow and ensures the effective production process; it transforms the received material into products according to composition rules defined by the nomenclature.

Provider: this agent is responsible for contacting suppliers and making orders whenever some components are required.

Decider: this agent synchronises the other agents' actions. It also realises the production and the material requirement planning. The distribution of the decider agents over the supply chain defines the control architec-MOSIM'12 -June 06-08, 2012 -Bordeaux -France ture. In the case of a distributed control architecture, each decider agent is responsible for the decision making process in its enterprise; whether in a centralized or mixed control architecture, the enterprise's decider agents rely on a common decider of a higher level.

Customer: this agent represents a final customer which is wishing to buy some finished product.

Supplier: this agent represents a supplier putting on sale some raw material.

The development of procurement, production and delivery plans requires the implementation of a decisionmaking system defining the organization of the decision units through which the supply chain is controlled. The decisional pattern of the production planning and control activity can be organized according to different architectures which are distributed, centralised and mixed one.

In the distributed control there is a single decision making level. In such control architecture, each enterprise of the supply chains network is totally independent and manages locally its own resources. In each enterprise, control is done through a decision making center.

To overcome the lack of global visibility of information induced by the distributed control, an alternative is to make information accessible to all the actors of the supply chains network and to centralize its processing. In fact, in centralized control architecture, there is a supplementary higher decision making level with a single decision center which is responsible for production planning and resources management of the overall supply chains network. The different decision centers of the lower level are reduced to entities relaying information to the central decision making entity.

To find a balance between local autonomy induced by distributed control and global optimisation induced by centralized control, a third control strategy is proposed in [START_REF] François | Planification des chaînes logistiques: modélisation du système décisionnel et performances[END_REF]. Such mixed control architecture is based on many decision making centers of a higher level instead of a single one. In fact, to each supply chain of the network is associated a decision center which centralizes information and processing within that supply chain. In this case, the information exchange between decision centers of the higher and the lower levels are the same as in centralized control.

Results and interpretations

The experimentations carried out on the three versions of the described multiagent application pointed out the following results.

Figure 6 shows the generated graph corresponding to the distributed control architecture. Each one of the decision centers S1.dec, S2.dec, S3.dec, ASS.dec and PNT.dec carries out locally the production planning and resources management of the enterprise to which it belongs.

Figure 6: Distributed agent-based control architecture

Figure 7 shows the generated graph corresponding to the centralized control architecture. In this case there is a higher level decision center DEC which carries out all the production plans for the entire supply chain network. Figure 8 shows the generated graph corresponding to the mixed control architecture. In this case, there is a higher level decision center for each supply chain: DEC1 and DEC2. The following figure expresses the several agents degrees Ki related to the three used control architectures.

Figure 9: Agents degrees

We distinguish two catogories of agents :

-those whose degree has not changed such as clients, suppliers and operating agents (production, distribution and procurement)

-those whose degree has increased with the centralization, especially in mixed control architecture. Degree increase concerns only decision centers as the centralization strategy is about the decision making system.

Besides, we notice that high degree agents are either decision centers (S1.dec, S2.dec, S3.dec, ASS.dec, PNT.dec) or operating interfaces agents in relation with many enterprises (ASS.dist and ASS.prov). By interface agent we mean distributer or provider as those agents are in relation with other enterprises agents.

Figure 10 below illustrates the aspects of distribution degree functions related to the several control architectures.

Figure 10: Degree distribution All of the three generated graphs correspond to heterogeneous networks since there is no significant degree mean value around which the distribution degree is concentrated. In the three cases there is a majority of nodes having low degree but a small number having high degree that exceeds the average. But what we can notice here is that the degree distributions of centralized and mixed architectures are very similar and notably different from distributed one.

This is also what we notice through the following figure 11 which draws the degree correlation for the three control architectures.

Figure 11: Degree correlation (Assortativity)

Degree correlation expresses the Assortativity of the system. The three control architectures are disassortative. Disassortativity is a characteristic of hierarchical systems where high degree agents tend to be linked to lesser degree agents. This can be explained by the existence of dominant agents. Here also we notice that assortativity of the distributed architecture is different from the centralized and mixed architectures which are very similar.

In the two latter cases disassortativity is reinforced by the addition of a higher decisional level of agents. In fact dominance relation is accentuated through the centralization of control.

The following figure 12 shows the centrality degrees of the several agents using the three control architectures.

Figure 12: Centrality degree

We notice that for all agents except decision centers centrality decreases when passing from a distributed architecture to centralized or mixed one. This is naturally due to the add of agents to the system which are not linked to those agents. In the contrary all of the decision centers centrality is higher in centralized and mixed cases than in distributed one. Here again, this is due to the addition of a supplamentary higher decision level whose agents are directly and only linked to decision centers.

MOSIM '12 -June 06-08, 2012 -Bordeaux -France Table 1 below presents the measured hierarchy degrees for the different studied agent architectures.

Table 1: Hierarchy degree Hierarchy degree can vary from 0 to 1. In the three cases, its value is superior to the mean value 0.5 which indicates that the different studied agent applications are characterized by hierarchical tendency which is more marked when it comes to centralization that concerns both centralized and mixed architectures. This is also due to the addition of decider agents which have control over the other agents.

All the previous results indicate the presence of leadership in the studied multiagent applications. This is also confirmed by the analysis of their representative graphs which points out the existence of star structures. Star sub-graphs were identified. The highest order star structures corresponds either to decision centers or to high connected operating interfaces agents.

Significance of the measures

In conclusion, the obtained results help understanding the organizational structures and identifying different categories of agents present in the several analysed multiagent applications. In fact, in the case of distributed control architecture, agents characterized by high degree are either decision centers or operating agents connected to great number of enterprises. High degree agent which is also decider is necessarily a leader, and high degree agent which is operating agent are in situation of dependency with other agents, especially resources dependency. On the contrary agents characterized by low degree cannot be deciders, they are necessarily operating agents having certain autonomy of action and somehow isolated, and this is the case of all the production agents.

In centralized and mixed control, high degree decider agents are of two categories: the greatest degree agents are leaders of a higher decision level and the others are leaders of a lower decision level. The other high degree agents are operating agents with great connectivity. Whereas low degree agents are operating ones as it is the case in distributed control architecture.

CONCLUSION

In this paper we presented an evaluation approach to measure organization in multiagent systems. The proposed method follows a three step process: observation, modelling and measure. The modelling technique is based on graph theory which is used to define and estimate metrics for the evaluation of structural properties of multiagent systems. In this paper, we focused especially in organization as evaluation criterion as it is a very interesting characteristic transposing the social dimension of multiagent systems. Therefore, specific metrics based on graph theory were proposed to analyse agent organizational structures. The tests and experimentations were carried out on a multiagent application for the simulation of production planning and control in supply chains. The evaluation allows the practitioners to have a clear idea on the organizational structures of the different control architectures. It pointed out that centralized and mixed controls have almost the same organizational properties. The advantage of the evaluation presented through this work is that it's done on a real world application rather than a case study. It allows providing practitioners a clear vision about the global manufacturing organization which can help analysing and eventually improving the enterprises strategies. Our future works includes two points. The first consists in extending the test application in order to move to a larger scale and thus reconsider the evaluation results. The second point is to focus on the evaluated system's dynamics and the evolution of the proposed measures over time.

Figure 1 :

 1 Figure 1: the evaluation system architecture

Figure 2 :

 2 Figure 2: the aspect-based observation architecture

Figure 3 :

 3 Figure 3: Homogeneous vs. Heterogeneous networks degree distributions

Figure 5 :

 5 Figure 5: Test-case supply chain network Each enterprise of the supply chain includes four services: distribution, production, procurement, and decision making which are represented by the following agents:

Figure 7 :

 7 Figure 7: Centralized agent-based control architecture

Figure 8 :

 8 Figure 8: Mixed agent-based control architecture

ACKNOWLEDGEMENTS

The authors would like to thank Asma Ben Rouha a student at the National School of Computer Studies (ENSI), Tunisia, for her participation in the implementation of some parts of the test-case application.