Michael Defoort
email: defoort@sum.sd.keio.ac.jp

Annemarie Kokosy

Thierry Floquet

Wilfrid Perruquetti

Decentralized motion planning for cooperative nonholonomic mobile robots ⋆

Keywords: Multi-vehicle formation, Decentralized intelligence, Receding horizon planning, Nonholonomic mobile robot

This paper presents a decentralized motion planner for a formation of autonomous mobile robots evolving in an unknown environment with obstacles. The motion planning scheme consists of decentralized receding horizon planners that reside on each vehicle to achieve coordination among formation agents. The advantage of the proposed algorithm is that each vehicle only requires local knowledge of its neighboring vehicles. The main requirement for designing an optimal conflict-free trajectory in a decentralized way, is that each robot does not deviate too far from its assumed trajectory designed without taking the coupling constraints into account. Finally, a comparative study between the proposed algorithm and other existing algorithms is provided in order to show the advantages especially in terms of computing time.

Introduction

The research effort in multi-agent system relies on the fact that multiple agents have the possibility to solve problems more efficiently than a single agent. Co-operative control of multiple vehicles gives rise to significant theoretical challenges and has various engineering applications including cooperative transportation of a large payload [START_REF] Miyata | Cooperative Transport by Multiple Mobile Robots in Unknown Static Environments Associated With Real-Time Task Assignment[END_REF], formation flying of unmanned aerial vehicles [START_REF] Inalhan | Decentralized optimization, with application to multiple aircraft coordination[END_REF], multi-agent gaming such as robot soccer or robot rescue [START_REF] Clark | A coordination platform for multi-robot systems[END_REF][START_REF] Lawton | A decentralized approach to formation maneuvers[END_REF][START_REF] Sugar | Coordination of multiple mobile manipulators[END_REF].

In this paper, the problem of interest is the navigation of a formation of autonomous mobile robots evolving in environments with obstacles. Here, the vehicles are dynamically decoupled but have common constraints that make them interact. Indeed, each robot has to avoid collision with the other ones. Moreover, some communication links between some vehicles must be maintained during the movement. Since the available power onboard the vehicle is limited, the distance between two vehicles which may exchange information will naturally be constrained. Besides maintaining the communication, the feasibility of the trajectories implies the respect of the dynamic constraints, as well as avoiding obstacles and collisions. In this paper, we will focus solely on these dynamic and geometric aspects and ignore mobile networking factors, such as fading, cross talk, and delay, which can also affect the quality of communication between the vehicles. Motion planning consists in generating a collision-free trajectory from the initial to the final desired positions for each vehicle. Depending on the distance that the robots have to travel, the computation of complete trajectories from start until finish may be computationally expensive. Moreover, the environment is usually partially known and further explored in real time. Therefore, the trajectories have to be computed gradually over time while the mission unfolds. It can be accomplished using an online receding horizon planner [16], in which partial trajectories from an initial state toward the goal are computed by solving an optimal control problem over a limited horizon.

Two strategies for motion planning in multi-agent systems are the centralized and decentralized (distributed) approaches. Although the centralized one has been used in different studies (see [START_REF] Dunbar | Model predictive control of coordinated multivehicle formation[END_REF] for instance), its computation time which scales exponentially with the number of vehicles, its communication requirement and its lack of security make it prohibitive. To overcome these limitations, one can use a distributed strategy which results in a formation behavior similar to what is obtained with a centralized approach.

Recently, some decentralized receding horizon planners have been proposed in [START_REF] Dunbar | Distributed receding for multi-vehicle formation stabilization[END_REF][START_REF] Keviczky | Coordinated autonomous vehicle formations: decentralization, control synthesis and optimization[END_REF][START_REF] Keviczky | Decentralized receding horizon control for large scale dynamically decoupled systems[END_REF][START_REF] Kuwata | Decentralized robust receding horizon control[END_REF]. In [START_REF] Dunbar | Distributed receding for multi-vehicle formation stabilization[END_REF], a solution is provided for unconstrained subsystems (decoupled input constraints only). Therefore, the coupling constraints between robots cannot be taken into account. In [START_REF] Keviczky | Coordinated autonomous vehicle formations: decentralization, control synthesis and optimization[END_REF][START_REF] Keviczky | Decentralized receding horizon control for large scale dynamically decoupled systems[END_REF], a distributed planner is formulated where each robot optimizes locally for itself as well as for every neighbor at each update, resulting in the increase in the computing time and the decrease in the decentralization. Furthermore, in order to ensure collision avoidance, some emergency strategies must be defined. In [START_REF] Kuwata | Decentralized robust receding horizon control[END_REF], the decentralized scheme is based on a leader-follower architecture. Indeed, the vehicles update their trajectory sequentially and the feasibility is guaranteed in spite of the presence of coupling constraints between subsystems. One advantage of the leader-follower approach is that it is easy to implement. However, there is no explicit feedback from the follower to the leader. Another disadvantage is that the leader is a single point of failure. Other decentralized strategies based on potential fields are given in [START_REF] De Gennaro | Formation control for a cooperative multi-agent system using decentralized navigation functions[END_REF][START_REF] Dimarogonas | Formation Control and Collision Avoidance for Multi-Agent Systems and a Connection between Formation Infeasibility and Flocking Behavior[END_REF] but they do not enable to satisfy the nonholonomic constraint imposed by the rolling wheels.

In this paper, a distributed implementation, without assigning any leader, of receding horizon planning is presented. Each robot optimizes only for its own trajectory at each update and exchanges information with neighboring subsystems. It requires the exchange of the assumed trajectory designed without taking the coupling constraints into account between neighboring subsystems prior to each update. Providing that the robot does not deviate too far from the assumed trajectory, a conflict-free trajectory satisfying all the constraints can be found. Contrary to [START_REF] De Gennaro | Formation control for a cooperative multi-agent system using decentralized navigation functions[END_REF][START_REF] Dimarogonas | Formation Control and Collision Avoidance for Multi-Agent Systems and a Connection between Formation Infeasibility and Flocking Behavior[END_REF][START_REF] Dunbar | Distributed receding for multi-vehicle formation stabilization[END_REF][START_REF] Keviczky | Coordinated autonomous vehicle formations: decentralization, control synthesis and optimization[END_REF][START_REF] Keviczky | Decentralized receding horizon control for large scale dynamically decoupled systems[END_REF], the distributed planning algorithm guarantees the feasibility of the vehicle path, which is crucial for real-time implementation.

The outline of this paper is as follows. In Section 2, the problem setup is described. In Section 3, our decentralized algorithm which only uses local information is presented. Finally, in Section 4, a comparative study between the proposed algorithm and other existing algorithms is provided in order to show the advantages especially in terms of computing time.

Problem setup

Modeling of mobile robot

Each mobile robot R n (n ∈ {1, . . . , N }), shown in Fig. 1, is of unicycle-type. The n th robot body is of symmetric shape and the centre of mass is at the geometric centre C n of the body. It has two driving wheels fixed to the axis which passes through C n and one passive centrered orientable wheel. The two fixed wheels separated by 2ρ n , are independently controlled by two actuators (DC motors) and the passive wheel prevents the robot from tipping over as it moves on a plane. In this paper, we assume that the motion of the passive wheel can be ignored in the dynamics of the mobile robot. The centre of mass C n , whose coordinates are (x n , y n ), is located at the intersection of a straight line passing through the middle of the vehicle and the axis of the two driving wheels. The configuration of the robot can be described by:

q n (t) = [x n (t), y n (t), θ n (t)] T ,
where θ n (t) is its orientation in the global frame.

y n x n θ n -→ i -→ j O C n 2ρ n

Fig. 1. Unicycle-type mobile robot

In this paper, the kinematics of wheeled-mobile robot is shown under the nonholonomic constraints (see [START_REF] De | Exponential stabilization of mobile robots with nonholonomic constraints[END_REF] for details). The pure rolling and nonslipping nonholonomic conditions are described by:

A T (q n ) qn = 0 with A T (q n ) = -sin θ n cos θ n 0 .
The kinematic equations can be written as follows:

qn (t) = f (q n (t), u n (t)), (1)
where vector field f : R 3 × R 2 → R 3 and control inputs u n are defined as:

                   f (q n (t), u n (t)) =        cos θ n (t) 0 sin θ n (t) 0 0 1        u n (t), u n (t) = [v n (t), w n (t)] T .
v n (t) and w n (t) are the linear and angular velocities, respectively. The system (1) is constrained to take into account the practical limitations on the vehicle velocities, i.e ∀t ≥ 0,

     |v n (t)| ≤ v n,max , |w n (t)| ≤ w n,max . (2)

Problem setup

The following assumptions are made in this study:

• (i) robots have on-board sensors which can detect surrounding objects and vehicles within a range with a small margin of error, • (ii) robots can reliably communicate with each other, • (iii) the broadcasting range is limited, • (iiii) each robot R n (n ∈ {1, . . . , N }) knows its initial configuration q n (t ini ) (t ini is the initial time instant) and its goal configuration q n (t f in ) = q n,f in (t f in is the final time instant).

Let us consider the following distributed integrated cost for multi-vehicle formation navigation:

L(q, u) = N n=1 L n (q n , u n , q n,f in ), (3)
where L n (q n , u n , q n,f in ) : R 3 ×R 2 ×R 3 -→ R is the integrated cost for one robot stabilization (it is assumed that L n (q n , u n , q n,f in ) = 0 if and only if q n = q n,f in and u n = 0), q = q T 1 , . . . , q T N T and u = u T 1 , . . . , u T N T are the concatened trajectory and control input. To solve the motion planning problem, one can make the following choices without loss of any generality1 :

• The geometric shape of robot R n is represented by a 2-D circle of centre C n = (x n , y n ) and of radius ρ n . Its motion is controlled but nonholonomic and is represented by the velocity vector u n (t). The range of its sensors is also described by a circle centrered at C n . • The i th (i = 1, . . .) obstacle in the environment will be represented by a circle centrered at point O i = (X i , Y i ) and of radius r i , denoted by B i (O i , r i ).

Definition 1 ∀t k ∈ [t ini , t f in ], ∀R n (n ∈ {1, . . . , N }), the detected obstacle set O n (t k ) is defined as the subset O n (t k ) ⊂ {B 1 (O 1 , r 1 ), B 2 (O 2 , r 2
), . . . , } of M n obstacles in the range of the robot sensors.

Note that the detected obstacle set is time dependent and evolves as long as the robot moves and discovers new obstacles (see Fig. 23). In order to ensure the collision avoidance with obstacles, for all t ≥ 0, the distance between the robot and the detected obstacles (i.e O mn ∈ O n (t)), d(q n (t), O mn ) = (x n (t) -X mn ) 2 + (y n (t) -Y mn ) 2 must satisfy:

d(q n (t), O mn ) ≥ ρ n + r mn . (4)
Here, a cooperative control problem is considered where some constraints couple the dynamic behavior of the robots. Indeed, the trajectory feasibility implies that the topology of the wireless network is kept at any time, i.e some y n (0)

x n (0) -→ i -→ j O Detected obstacle set O n (0)
Range of robot's sensors y n (1s)

x n (1s)

-→ i -→ j O Detected obstacle set O n (1s)
Range of robot's sensors communication links between some vehicles must be maintained during the movement. These coupling constraints can be expressed by the communication graph defined as follows.

Definition 2 A communication graph (R, E, S) is a labeled graph consisting of:

• a set R = {R 1 , . . . , R N } of N nodes representing the robots.

• a set of edges E ⊂ R × R encoding the communication links. Pair R n -R p belongs to E if there is a communication link between robots R n and R p . • a set of edge constraints. Since the available power onboard the vehicle is limited, the distance between two vehicles which may exchange information is constrained. Let us denote the broadcasting range of each R n as

d n,com (> 0). For each pair (R n , R p ) ∈ E, the distance d(q n (t), q p (t)) = (x n (t) -x p (t)) 2 + (y n (t) -y p (t)
) 2 has to be smaller than the shortest range of the two robots, i.e: d(q n (t), q p (t)) ≤ min(d n,com , d p,com ).

(

) 5
Lastly, the robots should remain at a safe distance (i.e. ρ n + ρ p ) from each other to avoid collisions. This coupling constraint can be expressed as follows:

for each pair (R n , R p ) ∈ R × R, n = p, d(q n (t), q p (t)) ≥ ρ n + ρ p . (6)
The objective is to compute the optimal trajectory, for each vehicle, from q n (t ini ) to q n,f in which satisfies requirements (1), ( 2) and ( 4)-( 6) outlined above, in a decentralized cooperative way and according to the performance criteria [START_REF] Cuzzolaa | An improved approach for constrained robust model predictive control[END_REF]. Depending on the distance that robots have to travel, the computation of complete trajectories from start until finish may be computationally too expensive. Moreover, the environment is partially known and further explored in real time. Therefore, the trajectory have to be computed gradually over time while the mission unfolds. It can be accomplished using an on-line receding horizon planner, in which partial trajectories from an initial state toward the goal are computed by solving a constrained finite time optimal control problem over a limited horizon. In the next section, we propose a way to decentralize the receding horizon planning problem in order to reduce the computational complexity and communication requirements.

Decentralized motion planning scheme

In every distributed optimal control problem, the same constant planning horizon T p ∈ R + and constant update period T c ∈ R + (T c < T p ) are used. In practice, T c is typically the time allocated for the resolution of the receding horizon planning problem. At each update, denoted τ k (k ∈ N),

τ k = t ini + kT c , (7)
each robot computes an optimal trajectory satisfying constraints (1), ( 2) and ( 4)-( 6) using local information. One idea is to only include, for each receding horizon planner, the robots that could have direct conflicts (i.e. may produce collision or may lose the communication). It enables a decentralized algorithm based on local information.

Conflict sets

For each vehicle R n , let us define two subsets of robots characterizing conflicts that may occur:

• the inter-robot collision conflict set C n,collision (τ k ) ⊂ R is the subset of all vehicles R p =n for which the separation distance verifies:

d(q n (τ k ), q p (τ k )) ≤ ρ n + ρ p + (v n,max + v p,max )(T p + T c ), (8)
• the communication conflict set C n,com (τ k ) ⊂ R is the subset of all vehicles R p =n such that (R n , R p ) ∈ E and for which the separation distance verifies:

d(q n (τ k ), q p (τ k )) ≥ min(d n,com , d p,com ) -(v n,max + v p,max )(T p + T c ). ( 9
)
Once these two subsets are defined, the conflict set can be expressed as:

C n (τ k ) = C n,collision (τ k ) C n,com (τ k ). Remark 1 For all (R n , R p ) ∈ R × R with R p ∈ C n (τ k )
, the coupling constraints ( 5)-( 6) between robots R n and R p are satisfied during the interval

[τ k , τ k+1 + T p ].

Decentralized motion planning algorithm

In order to avoid a leader-follower approach and to strongly decentralize the algorithm, it is proposed that each vehicle R n only plans its own trajectory using local information.

Let us denote the obstacle detection horizon as

T d ∈ R + (T p < T d ) which
depends on the range of the robot sensors. Over any interval [τ k , τ k + T d ], every vehicle R n must presume some trajectories for robots R p belonging to the conflict set in order to plan its optimal collision-free trajectory. Two difficulties can be stated:

• the definition of a unique presumed trajectory for each robot,

• the coherence between what a vehicle plans to do (the optimal planned trajectory) and what the other robots believe that the vehicle will plan to do (the presumed trajectory).

The proposed solution is to divide each optimal control problem into two steps. First, each robot R n computes its presumed trajectory, denoted q n (t, τ k ), over the prediction horizon (i.e. t ∈ [τ k , τ k + T d ]) and its corresponding control input, denoted u n (t, τ k ). This trajectory is obtained without taking the coupling constraint ( 5)-( 6) into account. Then, each vehicle transmits its presumed trajectory and control inputs to all the robots belonging to its conflict set. Therefore, by design, the presumed trajectory is the same in every distributed optimal control problem in which it occurs, i.e. ∀R p ∈ C n (τ k ), the same trajectory is presumed for R n . Then, using only local information, each robot computes its optimal trajectory, denoted q * n (t, τ k ), which satisfies constraints (1), ( 2) and ( 4)-( 6) and the associated control inputs, denoted u * n (t, τ k ), over the planning horizon (i.e. t ∈ [τ k , τ k + T p ]).

A more formal description follows. Over each interval [τ k-1 , τ k ), let the following optimal control problem P n (τ k ) associated with the n th robot which consists in determining the presumed control input u n (t, τ k ) and the presumed trajectory q n (t, τ k ) which only satisfies constraints (1)-( 4):

Problem P n (τ k ): min qn(t,τ k ), un(t,τ k ) τ k +T d τ k L n ( q n (t, τ k ), u n (t, τ k ), q n,f in )dt, ( 10
)
subject to: ∀t ∈ [τ k , τ k + T d ],                                  ˙ q n (t, τ k ) = f ( q n (t, τ k ), u n (t, τ k )), q n (τ k , τ k ) = q * n (τ k , τ k-1 ), u n (τ k , τ k ) = u * n (τ k , τ k-1 ), | v n (t, τ k )| ≤ v n,max , | w n (t, τ k )| ≤ w n,max , d( q n (t, τ k ), O mn ) ≥ ρ n + r mn , ∀O mn ∈ O n (τ k-1 ). ( 11
)
Remark 2 During the initialization step, that is to say before robots move, we denote:

             τ -1 = t ini q * n (τ 0 , τ -1 ) = q n (t ini ) u * n (τ 0 , τ -1 ) = u n (t ini )
Given the conflict sets C n,collision (τ k-1 ) and C n,com (τ k-1 ), the presumed trajectory q n (t, τ k ) and those of its neighbors, let us define the optimal control problem P * n (τ k ) associated with the n th robot, over each interval [τ k-1 , τ k ), which consists in determining the optimal control input u * n (t, τ k ) and the optimal predicted trajectory q * n (t, τ k ) which satisfies all the constraints (1)-( 6):

Problem P * n (τ k ): min q * n (t,τ k ),u * n (t,τ k ) τ k +Tp τ k L n (q * n (t, τ k ), u * n (t, τ k ), q n,f in )dt, ( 12
)
subject to: ∀t ∈ [τ k , τ k + T p ], q * n (t, τ k ) = f (q * n (t, τ k ), u * n (t, τ k )), ( 13
) q * n (τ k , τ k ) = q * n (τ k , τ k-1 ), ( 14
) u * n (τ k , τ k ) = u * n (τ k , τ k-1 ), ( 15
) |v * n (t, τ k )| ≤ v n,max , (16) |w * n (t, τ k )| ≤ w n,max , (17) d
(q * n (t, τ k ), O mn ) ≥ ρ n + r mn , ∀O mn ∈ O n (τ k-1 ), ( 18
) d(q * n (t, τ k ), q p (t, τ k )) ≥ ρ n + ρ p + ξ, ∀R p ∈ C n,collision (τ k-1 ), ( 19
) d(q * n (t, τ k ), q p ′ (t, τ k )) ≤ min(d n,com , d p ′ ,com ) -ξ, ∀R p ′ ∈ C n,com (τ k-1 ), (20) d(q * n (t, τ k ), q n (t, τ k )) ≤ ξ, (21)
where ξ ∈ R + is a constant. Here, it is assumed that the optimal planned trajectory q * n (t, τ k ) is constrained to be at most at a distance ξ from the presumed trajectory q n (t, τ k ) (see eq. ( 21)). This constraint enforces the degree of correspondence between the optimal trajectory and the presumed trajectory known by the neighbors. Therefore, in order to guarantee the collision avoidance between vehicles and the preservation of the communication links, deformation ξ due to the mismatch between the presumed and the optimal planned trajectories is added (see equations ( 19)-( 20)).

Remark 3 ¿From the optimal planned trajectory and control inputs associated to the planning horizon T p (i.e q * n (t, τ k ) and u * n (t, τ k )), only the part which corresponds to the update horizon T c is stored (see Fig. 4). The decentralized receding horizon planner is described by the flow chart given in Fig. 5. One can see that during the initialization (i.e. before robots movement), each one only computes its own trajectory using local information and enforcing the correspondence constraint (21). This process is then repeated during the robots movement, over the interval [τ 0 , τ 1 ), and so on until they reach a neighbourhood of their goal q n,f in . As such, new information can be taken into account in the next iteration.

Remark 4 One can note that constraints ( 14)-( 15) which guarantee the continuity of the trajectory and control inputs need the optimal trajectory q * n (τ k , τ k-1 ) and control inputs u * n (τ k , τ k-1 ) computed in the previous step. Therefore, in the proposed strategy, the receding horizon planner is not used in order to reject external disturbances or inherent discrepancies between the model and the real process, as it is usually done (see for instance [START_REF] Cuzzolaa | An improved approach for constrained robust model predictive control[END_REF]). However, it takes the real time constraint into account. Indeed, each mobile robot has a limited time to compute its optimal trajectory. The time allocated to make its decision depends on its perception sensors, its computation delays, etc. and is less than the update period T c (see Fig. 6). The discussed claim for robustness in trajectory tracking can be effectively accomplished by sliding mode control. Robustness properties against various kinds of uncertainties such as parameter perturbations, external disturbances and measurement errors can be guaranteed (see [START_REF] Defoort | Integral sliding mode control for trajectory tracking of a unicycle type mobile robot[END_REF] for instance).

O n (τ 0 ) (q n (τ 0 ), u n (τ 0 )) ( q n (t, τ 0 ), u n (t, τ 0 )) C n,com (τ 0 ) C n,collision (τ 0 ) ( q p (t, τ 0 ), u p (t, τ 0 ))
Resolution of problem P * n (τ 0 ) and storage

Obstacle set update

Resolution of problem P n (τ k )

Computation of conflict sets

Exchange of local information

∀p ∈ C n (τ k-1 ) O n (τ k-1 ) ( q n (t, τ k ), u n (t, τ k )) C n,com (τ k-1 ) C n,collision (τ k-1 ) ( q p (τ k ), u p (τ k )) Resolution of problem (q * n (t, τ 0 ), u * n (t, τ 0 )) P * n (τ k ) and storage (q * n (t, τ k ), u * n (t, τ k )) Reach of a neighborhood ∀t ∈ [τ 0 , τ 0 + T d ] ∀t ∈ [τ 0 , τ 0 + T c ] ∀t ∈ [τ k , τ k + T d ] ∀t ∈ [τ k , τ k + T c ] Stop YES NO ∀t ∈ [τ 0 , τ 0 + T p ] ∀t ∈ [τ k , τ k + T p ]
of q n,f in Fig. 5. Flow chart of distributed motion planner computation time. Indeed, the planning and detection horizon must be sufficiently small in order to have good enough results in terms of computation

τ k q* n (t,τ k-1 )
q* n (t,τ k ) q* n (t,τ k+1 )

Comput. of q* n (t,τ k ) τ k+1

Comput. of q* n (t,τ k+1 )

Fig. 6. Implementation of the receding horizon planner time. However, the planning horizon T p must be higher than the update period T c in order to guarantee reactivity and obstacle avoidance for the next planning problems. Similarly, it must be lower than the detection horizon T d in order to have sufficient authority to avoid collisions between robots and keep the communication links.

Some specific advantages of the proposed decentralized algorithm are enumerated below:

• security (without any supervisor or leader),

• high level of decentralization (each robot only knows its own trajectory, its own desired goal and a presumed trajectory of vehicles for which conflicts may occur), • low computation time,

• real time constraint is not ignored, • quasi-optimal trajectory, • low communication bandwidth (local information) 2

Technique for solving receding horizon planning problems

There are three components for the real time resolution of optimal control problems P n (τ k ) (resp. P * n (τ k )): determination of the flat outputs, B-spline parametrization and constrained feasible sequential quadratic programming.

The key approach is to determine outputs such that equation ( 1) is mapped to a lower dimensional output space. It will imply that the problem becomes computionally more efficient to solve. Using the flatness property of system (1) (see [START_REF] Fliess | Flatness and defect of nonlinear systems: introductory theory and examples[END_REF] for further details about flatness), all system variables can be differentially parameterized by x n , y n as well as a finite number of their time derivatives. Indeed, θ n , v n and w n can be expressed by x n , y n and their first and second time derivatives, i.e.

Once the performance criteria (10) (resp. criteria [START_REF] Keviczky | Decentralized receding horizon control for large scale dynamically decoupled systems[END_REF]) and constraints [START_REF] Keviczky | Coordinated autonomous vehicle formations: decentralization, control synthesis and optimization[END_REF] (resp. constraints ( 13)-( 21)) are mapped into the flat output space, the presumed (resp. optimal) trajectory is planned in this space (see Fig. 7).

State space

Flat space

q n (τ k, τ k ),u n (τ k, τ k ) x n (τ k, τ k ),y n (τ k, τ k ),…,x n (2) (τ k, τ k ),y n (2) (τ k, τ k )

Fig. 7. Flatness and motion planning

Then, in order to transform the optimal trajectory generation problem into a parameter optimization one, a piecewise polynomial function, B-spline, is adopted to specify the trajectory. The B-spline functions are chosen as basis functions due to their flexibility and easiness of enforcing continuity across breakpoints. B-Spline is the function defined by a series of knots called control knots. In our study, the three-order B-spline basis functions are used to parameterize the trajectory. For problem P n (τ k ) (resp.

P * n (τ k )), the time inter- val [τ k , τ k + T d ] (resp. [τ k , τ k + T p ]
) is divided into n knot equal segments with n knot + 4 knots to be control knots:

nod 0 = . . . = nod 3 = τ k < nod 4 < . . . < nod n knot +3 = τ k + T d (resp. T p ) (23)
The trajectories of the flat outputs are written in terms of finite dimensional B-spline curves as:

   x(t, τ k ) y(t, τ k )    = 3+n knot j=1 C j B j,3 (t) ( 24
)
where C j ∈ R 2 are the control points and B j,3 is the B-spline basis function computed recursively as follows:

B j,0 (t) =      1 if nod j ≤ t < nod j+1 0 otherwise ∀d ∈ {1, 2, 3}, (25)
B j,d (t) = t -nod j nod j+d+2 -nod j B j,d-1 (t) + nod j+d+1 -t nod j+d+1 -nod j+1 B j+1,d-1 (t).
Finally, the time domain is truncated into smaller intervals by quadratic laws. The optimal control points C j are numerically found using the constrained feasible sequential quadratic optimization algorithm [START_REF] Lawrance | User's guide for CFSQP Version 2.5[END_REF]. See [17] for a detailed analysis of the efficiency of this approach. To finish, the open-loop control inputs are deduced using equation ( 22).

Simulation results and performance evaluation

In order to highlight the performance of the proposed decentralized strategy, a comparative study with other existing motion planners for a formation of autonomous mobile robots evolving in unknown environments is done. The comparison criteria are: (1) the computation time, (2) the information flow, (3) the easiness of implementation and (4) the optimal traveling time.

Generalities on existing cooperative motion planners

We have implemented and tested the following approaches suitable for our motion planning problem under the same conditions3 :

• a centralized algorithm where the trajectories are computed via a supervisor by typically solving a large-dimension scale optimization problem. • a "weakly" decentralized receding horizon approach [START_REF] Keviczky | Decentralized receding horizon control for large scale dynamically decoupled systems[END_REF] where each robot optimizes locally for itself and every neighbor at each update. In this case, over any interval [τ k-1 , τ k ), only configuration q p (τ k , τ k-1 ) is exchanged pairwise. This fact enables to decrease the information flow. From q p (τ k , τ k-1 )

(∀p ∈ C n (τ k )), robot R n generates its optimal trajectory q n (t, τ k ) and the presumed trajectories q p (t, τ k ). Two problems arise from using such a strategy. On the one hand, the lack of correspondence constraint between the presumed and the optimal planned trajectories implies that the coupling constraint ( 5)-( 6) may not be satisfied. Indeed, the presumed and optimal trajectories can be considerably different.

On the other hand, the computation of each presumed trajectory of robots R p by vehicle R n increases the computation time and decreases the level of decentralization because of the knowledge of desired objectives q p,f inal , ∀p ∈ C n (τ k ). • a leader / follower receding horizon approach [START_REF] Kuwata | Decentralized robust receding horizon control[END_REF] where each robot sequentially computes its optimal trajectory. At first, an order of resolution is determined to establish the level of priority for each robot. So, over any interval [τ k-1 , τ k ), the robot who has the highest priority plans its optimal trajectory without taking the others into account. Once its trajectory is planned, another robot, having the second highest priority, generates its optimal trajectory by taking the already planned trajectories into account.

And, so on. The main advantage of this approach is its easiness of implementation. However, because of the leader / follower architecture, leaders are single points of failure. Finally, when the velocity of the leader is maximal, the manoeuvre margin of the follower is limited.

Simulation results and discussion

The geometrical shape of each robot R n is included in a circle of radius ρ n = 0.2m. The linear and angular velocities are bounded, i.e. |v n | ≤ 0.5m.s -1 and |w n | ≤ 5rad.s -1 . In the simulation examples, (1) represents the kinematics of R n . A pentium IV (192M o of RAM) micro-processor running at 2.4 Ghz operating under linux real time hosts the motion planner written in C.

Scenario 1

In this scenario, the group consists of two robots (N = 2) starting at q 1 (0) = [0, 0, 0] T and q 2 (0) = [0, 5.1, 0] T , respectively, with velocities equal to zero. These robots must cross each other in order to reach their desired configuration q 1,f in = [5, 5, 0] T and q 2,f in = [5, 0, 0] T , respectively as fast as possible.

Since the environment is partially known and further explored in real time (i.e. the range of sensors of each robot is of radius 1.5m), a receding horizon strategy, whose parameters are given in Table 1, is used. 1 Parameters of the receding horizon planners Here, we do not consider coupling constraint (5) on maximum separation distance (i.e. d 1,com = d 2,com = +∞). Thus, only the collision avoidance [START_REF] Dimarogonas | Formation Control and Collision Avoidance for Multi-Agent Systems and a Connection between Formation Infeasibility and Flocking Behavior[END_REF] between robots is taken into account as a coupling constraint. For robots R n (n = 1, 2), the goal is to determine over each interval [τ k-1 , τ k ), the optimal collision-free trajectory. One can note that, due to the symmetry of this problem, some properties of the studied algorithms can be highlighted4 .

T p 2s T c 0.5s T d 2s ξ 0.25 n knot 3 Table

Centralized and "weakly" decentralized approach [12]

For the centralized strategy, a supervisor is used. At the initial time instance, the two robots send their initial configuration and their objective. Then, the supervisor solves, over any interval [τ k-1 , τ k ), an optimization problem of dimension scale 2N (3 + n knot ). The time needed to find the optimal solution when robots cross over is 172ms. The simulation results are given in Fig. 8. The linear velocities, shown in Fig. 8(b), are less than 0.5m/s. In Fig. 8(a)-(b), one can see that robots avoid collision by modifying their trajectory and their velocity. During the crossing, robots slow down and adapt their trajectory. Figure 8(c) shows the evolution of the distance between robots. Since it is higher than 0.4m, the collision avoidance is guaranteed. The time to reach the desired objective is 15.8s for robot R 1 and 16.2s for robot R 2 .

For the "weakly" decentralized approach [START_REF] Keviczky | Decentralized receding horizon control for large scale dynamically decoupled systems[END_REF], a supervisor is not needed. Each robot plans its own trajectory by solving an optimization problem of dimension scale 2(3 + n knot ) as long as no collision may occur during the planning horizon. Then, when a collision may occur, each robot exchanges its last planned configuration and computes its trajectory and the one of its neighbor (optimization problem of size 2N (3 + n knot )). Therefore, the results obtained are the same as the results using a centralized strategy for this scenario. 5.1.2 Leader / Follower approach [START_REF] Kuwata | Decentralized robust receding horizon control[END_REF] First, an order of resolution is determined (robot R 1 , then robot R 2 ). Contrary to previous algorithms, leader R 1 does not try to avoid follower R 2 . It plans its optimal trajectory by solving an optimization problem of dimension scale 2(3 + n knot ) without taking the coupling constraints into account. Once its optimal trajectory is computed, it transmits it to robot R 2 . Then, robot R 2 generates its optimal collision-free trajectory in order to avoid leader R 1 . The time needed to solve the problem when robots cross over is small (about 40ms). The simulation results are given in Fig. 9. The linear velocities, shown in Fig. 9(b), are less than 0.5m/s. In Fig. 9(a)-(b), one can see that only robot R 2 modifies its trajectory and its velocity (i.e. deceleration) in order to avoid collision. Therefore the time to reach the desired objective is 15.7s for robot R 1 and 16.4s for robot R 2 . Figure 9(c) shows the evolution of the distance between robots. Since it is higher than 0.4m, the collision avoidance is guaranteed.

Proposed decentralized approach

Contrary to the leader / follower algorithm, there is no order of resolution. The motion planning problem is solved in two steps. First, each robot computes a presumed trajectory. Then, they exchange their presumed trajectory if a collision may occur. Using the local information exchanged, they compute their optimal collision-free trajectory. The time needed to solve the problem when robots cross over is 94ms. The simulation results are given in Fig. 10. The linear velocities, shown in Fig. 10(b), are less than 0.5m/s. In Fig. 10(a)-(b), one can see that each robot modifies its trajectory and its velocity in order to avoid collision. The time to reach the desired objective is 16.0s for robot R 1 and 16.3s for robot R 2 . Figure 10(c) depicts the evolution of the distance between robots. Since it is higher than 0.4m, the collision avoidance is guaranteed.

Remark 6 Contrary to the "weakly" decentralized approach [START_REF] Keviczky | Decentralized receding horizon control for large scale dynamically decoupled systems[END_REF], constraint (21) is added in order to enforce the degree of correspondence between the optimal and the presumed trajectory known by the neighbors. Thus, the collision avoidance between robots is guaranteed. The comparison in terms of computation time and optimal traveling time for the group using the above algorithms is summarized in Tab. 2.

Approach

Scenario 2

In this scenario, the group consists of five robots (N = 5) starting at initial configurations given in Tab. 3, with velocities equal to zero. These robots must reach the desired configuration given in Tab. 4 as fast as possible. One can note that the geometrical shape of the group will be reconfigured (from "linear" to "triangular" shape). All along the way, they need to maintain the connectivity, i.e there are communication links between the pairs (R 1 , R 2 ), (R 2 , R 3 ), (R 2 , R 4 ) and (R 3 , R 5 ) (see the communication graph given in Fig. 11). The five robots make decisions in order to avoid collision with other robots and obstacles, initially unknown, and to maintain the communication links. The broadcast range of each R n is d n,com = 2.5m. 3 Initial configurations ("linear" shape). 4 Desired configurations ("triangular" shape). Since the environment is partially known (i.e. the range of sensors of each robot is of radius 1.5m), a receding horizon strategy, whose parameters are given in Table 5, is used. One can note that, due to the number of potential 5 Parameters of the receding horizon planners conflicts during crossings, the advantages and limitations of the algorithms studied can be highlighted.

Robot x-position (m) x-position (m) θ-position (rad) R 1 0 0 0 R 2 0 2 0 R 3 0 -2 0 R 4 0 4 0 R 5 0 -4 0 Table
T p 2s T c 0.5s T d 2.5s ξ 0.25 n knot 3 Table
The simulation results are given in Fig. 12. One can see that each robot modifies its trajectory and its velocity in order to satisfy all the constraints (i.e. nonholonomic constraints, limitations on velocities, obstacle avoidance5 , collision avoidance between robots and constraints on communication links). The coordination is done by mutual adjustments (i.e. there is no leader). The time to reach the desired objective is 36.5s for the group. Figure 12(b) shows the evolution of the distances between robots which must maintain a communication link. One can see that these distances are higher than 0.4m and lower than 2.5m. The other relative distances are given in Fig. 12(c), showing the collision avoidance between robots.

Finally, in order to show the advantages of the proposed decentralized algorithm, the same five vehicle scenario is tested using other algorithms. The comparison in terms of maximum computation time for the design of the optimal trajectory during one planning horizon, optimal traveling time, communication bandwidth and feasibility (i.e. guarantee of collision avoidance and maintenance of communication links) using the algorithms studied is summarized in Tab. 6.

The centralized algorithm provides the best results in terms of optimal traveling time. However, since the maximum computation time for the design of the optimal trajectory during one planning horizon is higher than update horizon T c , this algorithm cannot be applied online. The same conclusion arises from the "weakly" decentralized algorithm due to the high dimension scale of optimization problems during conflicts. Here, only, the proposed decentralized and the leader / follower algorithms can be applied in real time. However, using the leader / follower approach, the optimality is damaged because of the lack of information from the follower to the leader. This lack of cooperation implies a more difficult motion planning for robots with low priority. Therefore, we can conclude that the proposed decentralized algorithm provides the best compromise between optimality and computation time for this scenario.

Conclusion

A decentralized algorithm, based on a receding horizon strategy, is proposed in order to solve the motion planning problem for a formation of autonomous mobile robots which is subject to constraints : control bounds, collision avoidance and bounded distances between robots. The main idea is to divide in two steps the generation of the optimal trajectory which satisfies the set of all constraints for each robot. In the first step, an intuitive trajectory is computed which respects just the constraints. In the second step, each robot elaborates its optimal trajectory by taking the notions of intention and engagement of robots into account. Simulations on a formation of five mobile robots highlighted the advantages of the proposed strategy in terms of computation time, optimal traveling time, communication bandwidth and feasibility, compared to the best decentralized algorithms of the literature [START_REF] Kuwata | Decentralized robust receding horizon control[END_REF], [START_REF] Keviczky | Decentralized receding horizon control for large scale dynamically decoupled systems[END_REF]. The most important advantages of the proposed algorithms are the real time implementation, especially when the formation contains more than two robots, and the reduction of the information exchanged between the robots. In fact, each robots requires only local knowledge of its neighbors.

Fig. 2 .

 2 Fig. 2. Detected obstacle set at time t k = 0s.

Fig. 3 .

 3 Fig. 3. Detected obstacle set at time t k = 1s.

Fig. 4 .

 4 Fig. 4. Planning and update horizons

Remark 5 A

 5 compromise must be done between reactivity, optimality and Initialization Computation step (before robots move) over [τ k-1 , τ k-1 + T c ) Determination of initial parameters Resolution of problem P n (τ 0 ) Computation of conflict sets Exchange of local information ∀p ∈ C n (τ 0 )

Fig. 8 .

 8 Fig. 8. Scenario 1: centralized and weakly decentralized approaches.

Fig. 9 .

 9 Fig. 9. Scenario 1: leader / follower approach.

Fig. 10 .

 10 Fig. 10. Scenario 1: proposed decentralized approach.

  Robot x-position (m) x-position (m) θ-position (rad)

Fig. 11 .

 11 Fig. 11. Communication graph.

Fig. 12 .

 12 Fig. 12. Scenario 2: proposed decentralized approach.

  Comparison of the proposed decentralized algorithm with other centralized and decentralized algorithms for the scenario 2

	Approach	Centralized Leader	"Weakly"	Proposed
			Follower decentralized decentralized
			[13]	[12]
	Maximum
	computation	2050ms	313ms	703ms	121ms
	time
	Information	global	local	local	local
	Flow
	Feasibility	YES	YES	NO	YES
	Optimal
	traveling	35s	39s	36s	36.5s
	time
	Table 6

It is trivial to allow the envelope of either the robot or an obstacle to be represented by union/intersection of several circles. The envelopes could also be polygonal. Mathematically, circular envelopes can be represented by second order inequalities while polygonal envelopes can be described by first order linear inequalities.

Since each trajectory and control inputs are approximated using B-spline functions, only control knots and optimal control points are exchanged pairwise (see next part for further details).

One can note that the existing strategies have been proposed in order to solve the motion planning problem for linear systems. Nevertheless, using techniques given in Section 3.3 (i.e flat outputs, B-spline parametrization and constrained feasible sequential quadratic programming), these algorithms can easily be extended to nonlinear systems.

For comparison purpose, every optimal control problem is solved using the technique given in Section 3.3. The parameters of the receding horizon planner are the same for each algorithm studied.

In order to take the size of robots into account, the radius of obstacles is increased by 0.2m (dotted lines around obstacles).

⋆ This work was partially supported by the JSPS Postdoctoral Fellowship and the FEDER (European Funds of Regional Development) under the ARCIR Robocoop and the AUTORIS-TAT T31 projects.


Benoit Scherrer

Dojat Michel

Florence Forbes

MRF Agent Based Segmentation: Application to MRI Brain Scans

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

MRI Brain Scan Segmentation is a challenging task and has been widely addressed in the last 15 years. Difficulties arise from various sources including the size of the data, the high level of noise with strong field images (3T or higher), the intensity nonuniformity or the low contrast between tissues. The Markov Random Field (MRF) probabilistic framework is classically used to introduce spatial dependencies between voxels, providing a labeling regularization and a robust to noise segmentation [START_REF] Van Leemput | Automated modelbased tissue classification of MR images of the brain[END_REF], [START_REF] Zhang | Segmentation of brain MR images through a hidden Markov random field model and the expectation-maximisation algorithm[END_REF]. In addition to noise, the intensity nonuniformity is a critical issue. Most approaches estimate global tissue intensity models through the entire volume and require the estimation of an explicit "bias field" model to account for the intensity nonuniformity [START_REF] Wells | Adaptative segmentation of MRI data[END_REF], [START_REF] Ashburner | Unified segmentation[END_REF]. These models are based on underlying assumptions that are not always valid and requires additional computational burden for their estimation. Local segmentation approaches are attractive alternatives [START_REF] Shattuck | Magnetic resonance image tissue classification using a partial volume model[END_REF], [START_REF] Richard | Automated segmentation of human brain MR images using a multi-agent approach[END_REF], [START_REF] Zhu | Multicontextual fuzzy clustering for separation of brain tissues in magnetic resonance images[END_REF]. The principle is to locally compute the tissue intensity models in various volume partitions. These models fit better to local image properties. In particular local segmentation intrinsically handles the intensity nonuniformity without any bias field modelization. Existing approaches either use local estimation as a preprocessing step to estimate a bias field model [START_REF] Shattuck | Magnetic resonance image tissue classification using a partial volume model[END_REF], or use redondant information to ensure consistency and smoothnesss between local estimated models [START_REF] Zhu | Multicontextual fuzzy clustering for separation of brain tissues in magnetic resonance images[END_REF], greedily increasing computation. We consider that these approaches do not fully take advantage of locality. We propose to immerse a local MRF segmentation approach into a distributed and cooperative framework based on the multiagent (MA) paradigm. This paradigm provides convenient mechanisms of cooperation and coordination, allowing to ensure consistency of local models in an elegant way. In addition, we achieve segmentation of tissues and structures in a unified and cooperative way. We show how to design a MRF agent-based segmentation approach and report some experiments on MRI brain scans that exhibit the properties of the system. These efforts extend a first tentative of agent based region growing tissue segmentation [START_REF] Richard | Automated segmentation of human brain MR images using a multi-agent approach[END_REF] to a unified MRF tissue and structure segmentation. This paper is organized as follows. We present in Section 2 how MRF processes are turned into cooperating agent entities. Section 3 reports evaluation results and presents several experiments to exhibit some interesting properties of such a local approach. Section 4 is devoted to the discussion and the conclusion.

MRF Agent Based Segmentation

MRF Framework

We consider a finite set of N voxels V = {1, ...N } on a regular three-dimensional (3-D) grid. Our aim is to assign each voxel i to one of K classes considering the observed greylevel intensity y i at voxel i. Both observed intensities and unknown classes are considered to be random fields denoted respectively by Y = {Y 1 , ..., Y N } and Z = {Z 1 , ..., Z N }. Each random variable Z i takes its value in {e 1 , ..., e K } where e k is a K-dimensional binary vector corresponding to class k. Only the k th component of this vector is non zero and is set to 1. In a traditionnal Markov model based segmentation framework, it is assumed that the conditional field Z given Y = y is a Markov random field, ie.

p (z |Y = y, Φ ) = W -1 y,Φ exp (-H (z |y, Φ ))
where H (z |y, Φ ) is an energy function depending on some parameters Φ = (Φ y , Φ z ) and given by:

H (z |y, Φ ) = H (z |Φ z ) - i∈V log p (y i |z i , Φ y ). ( 1
)
This energy is a combination of two terms: the first term in (1) is a regularization term that accounts for spatial dependencies between voxels. Denoting by N (i) the neighbors of voxel i, we will consider a Potts model with external field:

H(z |Φ z ) = i∈V   t z i v i - β 2 j∈N (i) t z i z j   . (2)
The second summation above tends to favor neighbors that are in the same class when parameter β is positive. This β parameter accounts for the strengh of spatial interaction. Other parameters are the v i ´s that are K-dimensional vectors defining the so-called external field. In this case Φ z = {v 1 , . Φ ). This requires the evaluation of an intractable normalizing constant W y,Φ and the estimation of the unknown parameters Φ. A standard approach is to use the ICM algorithm that alternates between parameter estimation and segmentation but results in biased estimates. EM-based algorithms and variants proposed by [START_REF] Celeux | EM procedures using mean field-like approximations for model-based image segmentation[END_REF] can be rather considered. They are based on Mean-field like approximations which make the MRF models case tractable. In all these approaches, MRF estimation is performed globally through the entire volume.

Local Approach of Tissue Segmentation

We agentify the global MRF process by distributing in the volume several local MRF processes in a MA paradigm. We consider a decentralized and memory shared MA framework based on the classical Agent/Group/Behaviour conceptual model. At the system starting point, a global tissue agent A T G is responsible for partitioning the volume into C nonoverlapping territories {T T c , c = 1...C} and instantiating one situated tissue agent A T c per territory. We consider K = 3 tissue classes: CSF (Cephalo-Spinal Fluid), GM (Grey Matter) and W M (White Matter). The hidden tissue classes t i 's take their values in {e 1 , e 2 , e 3 } respectively for classes {e CSF , e GM , e W M }. The tissue agent A T c segments its territory with the MRF model defined by the energy (see Equations ( 1) and ( 2)):

H c (t |y, Φ c ) = i∈T T c   t t i λ c i - β c 2 j∈N (i) t t i t j -log p y i t i , Φ c y   , (3)
where the parameters

Φ c = Φ c t ,
c i,k ,σ c i,k , i ∈ T T c , k ∈ {e CSF , e GM ,
e W M }} per voxel. There are two benefits from interpolating models. First, this ensures smooth model variation between neighboring agents. Second, this intrinsically handles nonuniformity of intensity inside each agent. Coordination between tissue agents: Each agent enter in idle mode after its initialization. The global tissue agent A T G then computes a global tissue intensity model using the FCM algorithm and wakes up the 20 percents agents whose local model is nearest from the global model. Once each A T c has finished its local model estimation, it wakes up its neighbors. First, it allows them to perform estimation in turn. Second, it allows already stabilized agent to perform model checking, restarting their estimation if needed to take into account updated models of A T c in their model correction and model interpolation.

Cooperative Approach of Tissue and Structure Segmentation

Automatic structures segmentation can not rely only on radiometry information because intensity distributions of grey nucleus are largely overlapping. A priori knowledge should be introduced. Classical approaches rely on an a priori known atlas describing anatomical structures. Atlas warping methods are however time consuming and limited due to inter-subject variability. A recent different way to introduce a priori anatomical knowledge is to describe brain anatomy with generic fuzzy spatial relations [START_REF] Barra | Automatic segmentation of subcortical brain structures in MR images using information fusion[END_REF], [START_REF] Colliot | Description of brain internal structures by means of spatial relations for MR image segmentation[END_REF]. We generally consider three kind of spatial relations: distance, symmetry and orientation relations. They are expressed as 3D fuzzy maps to take into account the general nature of the provided knowledge. We describe each subcortical structure by a set of generic fuzzy spatial relations provided by a brain anatomist. Fusion operators between fuzzy sets then permits to combine the knowledge provided by each spatial relation and provides a Fuzzy Localization Map (FLM) of the structure in the volume.

We define one structure agent A S l per structure and currently consider L = 9 subcortical structures: the ventricular System, the two Frontal Horns, the two Caudate Nucleus, the two Thalamus, and the two Putamens. Each structure agent segments its territory with a MRF model of K = 2 classes referred as structure and background. The FLM f l of structure l is used in two ways: first it dynamically provides the structure territory T S l containing the structure l by a simple thresholding. Second we propose to integrate it as an a priori anatomical knowledge in the MRF framework. Denoting by s = {s i , i ∈ T S l } the hidden classes, the energy function of the MRF model of A S l is given by:

H l s y, Ψ l = i∈T S l   t s i α l i - β l 2 j∈N (i) t s i s j -log p y i s i , Ψ l y   , (4)
with Ψ l = Ψ l s , Ψ l y and s i ∈ {e 1 , e 2 } = {e B , e S } for a voxel of the background or a voxel belonging to structure l. The external field denoted by {α i , i ∈ T S l }, where α l i is a 2-dimensional vector, allows to incorporate the a priori knowledge contained in the FLM. We denote by f l i the value of f l at voxel i and propose to introduce the prior fuzzy knowledge of the FLM as relative prior weights for each voxel i, by setting:

α l i = γ -log 1 -f l i -log f l i , (5)
where γ adjusts the influence of the external field. When f l i ≈ 0, the voxel i is unlikely to belong to the structure. If γ was null, the segmentation would be performed only from the intensity models. Else, according to (5), α l i (1) < α l i (2) which favores in (4) the class background. When f l i ≈ 1, the voxel i is likely to belong to the structure. In that case α l i (1) > α l i (2) and the class structure is favored. Each structure owns four behaviours: 1) Struct Init that initializes the structure agent, 2) Struct ComputeFuzzyMap that computes or updates the FLM from fuzzy spatial relations, 3) Struct EM that computes MRF model parameters and 4) Struct Stabilized when the agent is in the idle state. As we define a neighborhood group for each tissue agent, we define the group G T →S A S l of tissue agents cooperating with a structure agent A S l , the group G S→T A T c of structure agents cooperating with a tissue agent A T c , and the group G S→S A S l of structure agents using A S l as a reference in a spatial relation. These groups allow to detail cooperation and coordination mechanisms between agents. Updating structure models via tissue models: each structure being composed of a single tissue T l ∈ {e CSF , e GM , e W M }, we do not estimate intensity model Ψ l y of class structure and class background. We rather compute them from tissue intensity models of G T →S A S l estimated by tissue agents, by setting:

p y i s i = e S , Ψ l y = p y i t i = T l , Ψ y p y i s i = e B , Ψ l y = max t∈{e CSF ,e GM ,e W M } p (y i |t i = t, Ψ y ) ,
so that improvements in tissue intensity models estimation will be dynamically taken into account by structure agents.

Feedback of Structure Segmentation on Tissue Segmentation: conversely, results from structure agents are integrated in the tissue segmentation model via the external field λ c of tissue agents. We express it as the disjunctive fusion of a posteriori probabilities p s y, Ψ l coming from structures of G S→T A T c . It follows that structure segmentation is not reduced to a second step but is combined with tissue segmentation to improve its performance. Update Fuzzy Maps: when the segmentation of structure l is updated the structure models of G S→S A S l take it into account by re-computing their spatial relations with respect to l, making the knowledge gradually more accurate.

Evaluation

The evaluation was performed using both phantoms and real 3T brain scans. We first evaluated the tissue segmentation performances provided by tissue agents only. We quantitatively compared our approach to two well known ap- proaches, FSL [START_REF] Zhang | Segmentation of brain MR images through a hidden Markov random field model and the expectation-maximisation algorithm[END_REF] and SPM5 [START_REF] Ashburner | Unified segmentation[END_REF], with the Jaccard similarity4 on the BrainWeb5 [START_REF] Collins | Design and construction of a realistic digital brain phantom[END_REF] database (see Figure 2). It shows comparable results and particularly more robustness to noise than SPM5, whereas the computational time was approximately 4min with our approach and respectively 8min and 14min with FSL and SPM5 on a 4Ghz Pentium, 1Go RAM. The Figure 3 shows visual evaluation on a very high bias field brain scan 6 . SPM5, which uses an a priori atlas, failed in the segmentation while FSL did not estimate a correct bias field. Our local approach clearly appears to be more robust to very high intensity inhomogeneities. Figure 4 shows results of cooperative tissue and structure segmentation. In addition to these competitive performances, our platform allows to exhibit some interesting properties of this local approach. Figure 5 shows that large territory sizes result in poor performance. Smaller territory sizes allow to better model local intensity distributions, but need to be large enough to correctly estimate models. In practice we use territory size of 20x20x20 voxels. Figure 6 illustrates the activity of a tissue agent immersed in the system. It allows to understand the behaviour of an agent that would have poor estimated models without cooperation mechanisms.

Discussion and Conclusion

We propose an original MRF agent based approach for MRI brain scan segmentation. Markovian segmentation is an efficient probabilistic framework which introduces a local regularization via spatial dependancies between voxels. It makes it robust to local pertubations such as data noise. In addition, accurate segmentation of MRI brain scan requires to handle the intensity nonuniformity. These global perturbations require to spatially adapt models over the volume. Instead of estimating a spatial bias field model or using non-tractable non-stationnary MRFs, we propose an original agent based approach: we integrate the local level of regularization via Markov models and the global level via distributed and cooperative agents which estimate local models. Coordination mechanisms are introduced (1) to ensure the spreading of knowledge between neighbouring agents and (2) to prevent agents from starting with poor knowledge. The main advantage over other existing local approaches [START_REF] Shattuck | Magnetic resonance image tissue classification using a partial volume model[END_REF], [START_REF] Richard | Automated segmentation of human brain MR images using a multi-agent approach[END_REF], [START_REF] Zhu | Multicontextual fuzzy clustering for separation of brain tissues in magnetic resonance images[END_REF] is that using this appropriate framework we are able to make full use of local estimation. In addition, it allows to integrate a priori information in an elegant way. Indeed, we can consider two levels of knowledge as regards MRI brain scans: the tissue knowledge at a local level and the brain structure knowledge at a global level. In general these two levels are processed independantly [START_REF] Barra | Automatic segmentation of subcortical brain structures in MR images using information fusion[END_REF], [START_REF] Colliot | Description of brain internal structures by means of spatial relations for MR image segmentation[END_REF]. We rather consider that they are linked and must be used in a common setting. We show how to introduce a priori anatomical knowledge expressed by fuzzy spatial relations in the MRF framework to segment several subcortical structures. We also show how to combine the MRF models of tissues and structures. Models are mutually constrained in their convergence, making both models gradually more accurate and providing optimal results for both levels. We thus show how the Markovian approach can be extended by introducing mechanisms (1) to handle multiple levels of regularizations (multi-scale regularization) and (2) to consider conjointly multiple level of heterogeneous knowledge (multi-scale knowledge processing).

Our implementation provides interesting visualization tools which allow to track specific agents and explore local knowledge such as local segmentation errors or local intensity models. The evaluation shows competitive results compared to other algorithms with lower computational time. Indeed, local easy-to-segment territories converge quickly, allowing the system to focus on other areas. In addition, it appears to be robust to the intensity nonuniformity without any bias field assumption and estimation. Note that we currently consider a regular cubic partitioning for tissue segmentation but should in future work evaluate the contribution of more particular partitionning, like adaptive or spherical partitionings. The locality may allow to integrate brain extraction as an additional level of knowledge in our processing. We also plan to extend our model to new structures to study specific pathologies. Finally, MRF agent based computing appears as an interesting and modular tool for complex image segmentation.

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Synthetic view of our agent based approach.

Fig. 4 .

 4 Fig. 4. Cooperative tissue and structure segmentation: structure segmentation (a) with 3D rendering (b) shows good results with computational time less than 15 minutes. Image (d) shows visual improvement in tissue segmentation compared to the segmentation produced by tissue agents only (c) (see putamens).

Fig. 5 .

 5 Fig. 5. Influence of tissue agent territory size on the robustness to intensity nonuniformity, using the BrainWeb phantom with 3% of noise and 100% of nonuniformity.

Fig. 6 .

 6 Fig. 6. Evaluation of tissue segmentation (b) on a real 3T brain scan (a). Our implementation allows to observe the activity of each agent: (c) shows the local histogram of the red-outlined agent in (b). All tissue classes are not represented, leading to bad models estimation without cooperation. Figure (d) shows the agent behaviour: after initialization it waits for the neighbouring agents to wake it up. Then it performs model corrections in its EM behaviour. After convergence (Stabilized behaviour), model checking restarts the estimation twice. Then, the agent stay in idle mode.

  .., v N , β}. The v i 's can be related to a priori weights accounting for the relative importance of the K classes at site i. The introduction of these extra parameters in the standard Potts model enables us to integrate a priori knowledge on classes. The second term in (1) is a data-driven term based on intensities. For MRI we generally consider a Gaussian probability density function for the observed intensity y i when the tissue class is z i . It follows that p (yi |z i = e k , Φ y ) = g µ k ,σ k (y i ) with Φ y = {µ k , σ k , k = 1...K}.Segmentation is then performed according to the Maximum A Posteriori principle (MAP) by maximizing over z the probability p (z |y,

  Φ c y have to be estimated. The external field denoted by {λ c i , i ∈ T T c } is not estimated but used to incorporate information coming from structure segmentation agents (see Section 2.3). Each tissue agent owns three behaviours to segment its territory: 1) Tissue Init which initializes the EM algorithm by computing initial intensity models via a Fuzzy-C Mean algorithm (FCM), 2) Tissue EM which computes the MRF model parameters in cooperation with neighbouring agents and 3) Tissue Stabilized when the agent is in the idle state. Cooperation between tissue agents: The agent A T c cooperates with its neighbors group denoted by G N (A T c ) to ensure a global consistency of the local estimated model. It performs: Model Checking: for each tissue class k we compute a local mean model from the models of G N (A T c ). The KullBack-Leibler distance D c k provides a measure of dissimilarity between intensity models of each class that allows to apply model correction if required. Model Correction: we compute the corrected mean and variance of class k from a linear combination of estimated and mean models according to D c k . Model Interpolation: we use cubic splines interpolation between corrected models of A T c and of G N (A T c ) to compute one intensity model {g µ

The Jaccard similarity between two sets is defined by the size of their intersection divided by the size of their union. A value of 1.0 represents a complete agreement.

BrainWeb provides MR volumes whose the segmentation is known (semi-manually segmented by experts) and to which different values of noise and nonuniformity can be added.

This image was acquired with a surface coil which provides a high sensitivity in a small region (here the occipital lobe) and is useful for functional imaging.


Laurent Mamy

Vincent Letouzey

Jean-Philippe Lavigne

Xavier Garric

Jean Gondry

Pierre Mares

Renaud De Tayrac
email: renaud.detayrac@chu-nimes.fr

Correlation between shrinkage and infection of implanted synthetic meshes using an animal model of mesh infection

Keywords: Infection, Mesh, Poly (lactic acid), Polypropylene, Shrinkage

Introduction and hypothesis

The aim of this study was to evaluate a link between mesh infection and shrinkage. Methods Twenty-eight Wistar rats were implanted with synthetic meshes that were either non-absorbable (polypropylene (PP), n=14) or absorbable (poly (D,L-lactic acid) (PLA94), n=14). A validated animal incisionnal abdominal hernia model of mesh infection was used. Fourteen meshes (n=7 PLA94 and n=7 PP meshes) were infected intraoperatively with 10e6 CFU Escherichia coli, and compared with 14 non-infected meshes (n=7 PLA94 and n=7 PP meshes) (control groups). Explantations were performed on day 30. Shrinkage was evaluated by a reproducible numerical analysis of mesh area. Infection and histological study were evaluated on day 30.

Results Non-infected meshes were less shrunk than infected meshes for both non-absorbable (5.0±1.7% versus 21.6±6.1%, p<0.05) and absorbable meshes (2.4±0.9% versus 11.0±2.5%, p<0.05). Conclusion This study highlights a link between infection and shrinkage in the model used.

Introduction

The surgical treatment of genital prolapse using synthetic mesh is restricted by complications such as erosion, infection and shrinkage. Vaginal erosions are well known and may affect more than 10% of patients [START_REF] Collinet | Transvaginal mesh technique for pelvic organ prolapse repair: mesh exposure management and risk factors[END_REF]. They usually require local excision. However, recent publications have reported lower erosion rates (0% to 6.9%), which are therefore close to those observed after laparoscopic or open sacrocolpopexy (3% to 5%) [START_REF] Ridder | Should we use meshes in the management of vaginal prolapse?[END_REF].

The biological response of tissues to foreign bodies largely depends on the material and conformation of the mesh [START_REF] Bellon | Integration of biomaterials implanted into abdominal wall: process of scar formation and macrophage response[END_REF]. The current literature supports the notion that monofilament polypropylene with a large-pore size induces fewer complications [START_REF] Birch | The role of synthetic and biological prostheses in reconstructive pelvic floor surgery[END_REF]. However, data are not consistently compelling, making it difficult to choose the ideal material [START_REF] Cosson | Risk of infection and prostheses: time out or a red flag?[END_REF]. Furthermore, infection is thought to be responsible for erosion, shrinkage, migration of prosthetic devices, and pain [START_REF] Dougherty | Pathobiology of infection in prosthetic devices[END_REF]. Microorganisms can interfere with the integration process through adhesion to mesh surfaces, and such adhesion is an important stage in the infection [START_REF] An | Concise review of mechanisms of bacterial adhesion to biomaterial surfaces[END_REF]. The first stage of adhesion is physical and reversible. The second stage is molecular and irreversible [START_REF] Marshall | Mechanisms of bacterial adhesions at solid-water interfaces[END_REF]. A subclinical mesh infection, acquired during the initial implantation, could result in wound separation with subsequent mesh exposure [START_REF] Huang | Management of polypropylene mesh erosion after intravaginal midurethral sling operation for female stress urinary incontinence[END_REF]. Both infection and shrinkage are current problems concerning the treatment of genital prolapse using synthetic meshes.

The aim of this study was to evaluate the link between mesh infection and shrinkage in a validated animal model of mesh infection.

Materials and methods

Shrinkage was studied in relation to the infected or noninfected character of the meshes used. A referent mesh, light-weight PP (Parietene®, Sofradim-Covidien, Trévoux, France), weighting 38 g/m 2 , was compared with a new mesh called PLA 94 . PLA is a long-lasting absorbable polymer that has been used for many years in not only orthopedic and vascular surgery, due to its biocompatibility, but also in preclinic study of our team [START_REF] De Tayrac | Long-lasting bioresorbable poly(lactic acid) 94 mesh: a new approach for soft tissue reinforcement based on an experimental pilot study[END_REF][START_REF] De Tayrac | In vitro degradation and in vivo biocompatibility of poly(lactic acid) 94 mesh for soft tissue reinforcement in vaginal surgery[END_REF]. We used a thread composed of PLA with 94% L-lactic acid and 6% Dlactic acid (PLA 94 ), which had previously been treated by extraction to remove the surface additive and any agents present in the fibers. A large-pore monofilament mesh composed only of PLA 94 was used. Time to resorption depends on the level of "L" form containing in the polymer. The resorption time of PLA 94 is done in 1.5 years; nonetheless, after 8 months, the mesh has no mechanical property anymore. The technical characteristics of the two meshes are outlined in Table 1. Meshes were pre-cut into 30×30-mm patches. Eight 3/0 polypropylene sutures were placed around each implant to facilitate surface area measurements. All meshes used for the study were then sterilized by ethylene oxide, which does not affect their mechanical properties [START_REF] De Tayrac | In vitro degradation and in vivo biocompatibility of poly(lactic acid) 94 mesh for soft tissue reinforcement in vaginal surgery[END_REF].

Ethical committee approval was obtained for the animal study (Ethical Committee Approval number CE-LR-0804).

Rats were housed in an animal facility and treated in accordance with current national guidelines on animal welfare. Twenty-eight Wistar rats (weight range 250 to 300 g) were implanted with synthetic meshes that were either non-absorbable (polypropylene (PP), n = 14) or absorbable (poly (D,L-lactic acid) (PLA 94 ), n=14). Fourteen meshes (n=7 PLA 94 meshes and n=7 PP meshes) were infected intraoperatively with 10e6 CFU Escherichia coli and compared with 14 non-infected meshes (n=7 PLA 94 meshes and n=7 PP meshes) (control groups).

The animals were anesthetized by a mixture of halotane 2.5% and oxygen (0.5 l/min) administered via an inhalation mask, and by an intraperitoneal injection of ketamine (50 mg/kg). The experiments were performed according to the validated incisional hernia rat model described by Alponat et al. [START_REF] Alponat | Prevention of adhesions by Seprefilm, an absorbable adhesion barrier: an incisional hernia model in rats[END_REF] and used by Zheng et al. [START_REF] Zheng | Host response after reconstruction of abdominal wall defects with porcine dermal collagen in a rat model[END_REF]. The abdomen was shaved, disinfected with betadine, and draped to ensure sterile conditions. A vertical midline incision was made through the skin, and skin flaps were raised. A 15×25-mm longitudinal full-thickness defect was created. The defects were repaired with the meshes positioned under the skin but above fascia and muscles. Typically, a mesh was extended 5 mm beyond the cranial and caudal borders and 15 mm laterally. The mesh was laid over the defect with a slight overlap and was sutured without tension to the abdominal wall using interrupted resorbable 2/0 PGA sutures (Vicryl®, Ethicon) at the fourth corners. The peritoneum was left unclosed under the mesh. The meshes were then photographed in vivo using a digital reflex camera (Canon EOS 400D digital), and the area of the mesh was evaluated numerically by ImageJ freeware available on the internet (results in pixels) (Fig. 1). The distance between the camera and the mesh was noted such that the photograph at explantation on day 30 was taken with the same distance between mesh and camera (average 40 cm). The subcutaneous tissues and skin incision were closed with interrupted resorbable 2/0 PGA sutures (Vicryl®). Bacterial inoculation was performed at the end of the surgical procedure according to a validated model of mesh infection previously developed by our team [START_REF] Mathé | Comparison of different biomaterials for vaginal surgery using an in vivo model of meshes infection in rats[END_REF], using a small quantity of E. coli (10e6 CFU) in order to mimic a subclinical mesh infection.

The animals were checked daily for local or systemic complications throughout the entire 30-day observation period. Explantations were performed on day 30. The meshes were photographed in vivo using the same reflex digital camera previously used, and mesh area was again evaluated numerically by the software (Fig. 2). The initial implants, with their neighboring host tissues, were resected. On retrieval, the meshes were cut into two strips for both histological and bacteriological study.

An uropathogenic E. coli (UPEC) strain previously isolated from a patient with UTI (NECS19923) and harboring the main virulence factors (e.g., toxins, adhesins, siderophores, and capsules) registered in UPEC was used. The bacteriologist was blinded with regard to mesh identity. Strips samples were placed in 2 ml Muller-Hinton broth, crushed with a sterile scalpel, and incubated at 37°C for 18 h. Colonies were counted after serial dilution. Different standard agar plates were used to identify and isolate the bacteria that grew around the meshes. Genus and species were determined biochemically using the API identification card (bioMérieux, Marcy l'etoile, France). Post-infection E. coli strains were identified by genetically comparing randomly collected colonies with NECS19923 on the basis of their virulence profile.

The investigator for the histopathological examination was blinded to the mesh. For each histology strip sample (one per mesh explanted), three slides were stained with Masson's trichrome, and three slides with hematoxylin and eosin (H&E). The microscopic evaluation quantified the presence of polynuclear, mononuclear, and giant cells; newly formed vessels in H&E-stained sections; and collagen (organization, composition, and amount). Five fields per slide were counted at ×400 magnification (Olympus AX70 Provis, Japan). The scale used was similar to that described by Zheng et al. [START_REF] Zheng | Host response after reconstruction of abdominal wall defects with porcine dermal collagen in a rat model[END_REF].

Data were summarized by frequency and percentage for categorical variables and by mean, standard deviation, median, and range for continuous variables. To investigate the association between categorical variables, univariate statistical analyze were performed using Pearson's chi-2 test or Fisher's exact test if the sample size was small and using Wilcoxon's test or Student's t test for continuous variables. In order to account for the number of tests performed, the alpha risk was corrected using the Bonferroni method. All statistical tests were two-tailed, and a p value of less than 0.05 was considered statistically significant. All statistical tests were performed using SAS v.9 statistical software (SAS Institute, Cary, NC, USA).

Results

Four animals died during the experimental period (14.3%): one in the PLA 94 -infected group, two in the PP-infected group, and one in the PP non-infected group. One died after anesthesia and three because of postoperative evisceration. None died because of infection. Tests conducted on day 30 showed that no E. coli were present on the mesh in noninfected animals. In the opposite group, the NECS19923 strain was found in all infected animals and there was at least 10e5 CFU. Contamination with Staphylococcus epidermidis was possible, but always less than 10e5 CFU, and did not correlate with mesh shrinkage.

Non-infected meshes were less contracted (2.4±0.9% for PLA 94 and 5.0±1.7% for PP) than infected meshes (11.0± 2.5% for PLA 94 and 21.6±6.1% for PP) after 1 month of implantation (p < 0.05). Moreover, absorbable PLA 94 meshes contracted less than non-absorbable PP meshes when infected (11.0 ± 2.5% versus 21.6± 6.1, p< 0.05) (Table 2). Histological results are shown in Table 3.

Discussion

Three recent randomized controlled trials have showed that mesh repair was superior to anterior colporrhaphy in pelvic floor reconstructive surgery [START_REF] Hiltunen | Low weight polypropylene mesh for anterior vaginal wall prolapse: a randomized controlled trial[END_REF][START_REF] Nguyen | Outcome after anterior vaginal prolapse repair: a randomized controlled trial[END_REF][START_REF] Sivaslioglu | A randomized comparison of polypropylene mesh surgery with site specific surgery in the treatment of cystocele[END_REF]. Low-weight polypropylene meshes were used by Hiltunen et al. [START_REF] Hiltunen | Low weight polypropylene mesh for anterior vaginal wall prolapse: a randomized controlled trial[END_REF], and the rate of recurrence was better with it than with colporrhaphy repair. Nguyen and Burchette [START_REF] Nguyen | Outcome after anterior vaginal prolapse repair: a randomized controlled trial[END_REF] also found less recurrence of prolapsed using polypropylene than without. Sivaslioglu et al. [START_REF] Sivaslioglu | A randomized comparison of polypropylene mesh surgery with site specific surgery in the treatment of cystocele[END_REF] concluded in their study that surgery with light polypropylene mesh (Sofradim, Parietene) is superior in terms of anatomical results to the site-specific surgery in the treatment of cystocoeles. Local complica-Fig. 1 Mesh contraction was evaluated by measuring mesh area pre-and postoperatively using a standardized protocol of in vivo mesh photography. Pictures of anesthetized rats at a distance of 40 cm were taken, before skin closure preoperatively and after skin incision on day 30 tions, such as erosion, shrinkage, pain, dyspareunia, and infection, are still important limitations, particularly in young and sexually active women.

Whereas the pathophysiology and management of vaginal erosion are now well known, little information is available on mesh shrinkage. Although this phenomenon is poorly defined, its incidence poorly reported, and its pathophysiology and risk factors unclear, it may be responsible for major local complications such as pain and dyspareunia, and also recurrences, with subsequent difficult reinterventions.

Hypotheses explaining mesh shrinkage include an inflammatory reaction around the mesh, itself correlated with weight and pore size, and an immunological reaction, which we have not found in our study, probably due to a lack of power. In the present study, we put forward the hypothesis that infection of the mesh caused by bacterial contamination during the implantation phase is an independent risk factor for shrinkage. When working with two different meshes, we observed a significant correlation between infection and shrinkage.

Tissue ingrowth around synthetic implants is a complex phenomenon, indissociable from the inflammatory reaction. An immunochemical analysis of infected implanted mesh would be of great interest, with a particular focus on TGF-beta1 which is a determinant of foreign body reaction to alloplastic materials in rat fibroblast cultures [START_REF] Weyhe | The role of TGF-beta1 as a determinant of foreign body reaction to alloplastic materials in rat fibroblast cultures: comparison of different commercially available polypropylene meshes for hernia repair[END_REF]. This type of study should be able to differentiate between the respective responsibilities of bacterial contamination and non-infectious foreign body reactions in mesh shrinkage.

Fig. 2 Examples of mesh contraction measurements using Image J software However, intraoperative bacterial contamination of synthetic implants is rather uncommon in clinical practice; although clinical infection such as abscess is rare, subclinical chronic infection may explain several local complications. This has already been observed in mesh exposure after wound separation due to infection [START_REF] Huang | Management of polypropylene mesh erosion after intravaginal midurethral sling operation for female stress urinary incontinence[END_REF]. Further studies are necessary to confirm our hypothesis using more animals, animal models for vaginal surgery, and longerterm experiments. Should the hypothesis be confirmed, the use of antibacterial products on synthetic implants would be greatly beneficial in women.

Mesh shrinkage has been reported to occur early after tissue implantation, within the first 14 days of tissue healing in response to the acute inflammatory reaction [START_REF] Sergent | Experimental biomechanical evaluation of polypropylene prostheses used in pelvic organ prolapse surgery[END_REF]. After this early phase, mesh shrinkage defined as surface loss measured in millimeters and expressed as a percentage of initial surface area, and which occurs in 72% of all implants, was stable over a 180-day period in a rabbit abdominal model where it correspond to 3-20% of the initial surface area [START_REF] Sergent | Experimental biomechanical evaluation of polypropylene prostheses used in pelvic organ prolapse surgery[END_REF].

E. coli isolate was used because this strain is common in vaginal infections [START_REF] Judlin | Infections in gynecology[END_REF] and is the most frequent in infected biomaterial [START_REF] Gristina | Biomaterial-centered infection: microbial adhesion versus tissue integration[END_REF]. Prosthesis infection often springs from the transformation of a usually non-pathogenic colonizing bacterium into virulent colonies that adhere to the material [START_REF] Gristina | Biomaterial-centered infection: microbial adhesion versus tissue integration[END_REF]. A low infection level (10e6 UFC) was injected intraoperatively on the mesh in order to mimic a subclinical bacterial contamination of the mesh.

As previously shown [START_REF] De Tayrac | Long-lasting bioresorbable poly(lactic acid) 94 mesh: a new approach for soft tissue reinforcement based on an experimental pilot study[END_REF], mesh was better tolerated in the PLA 94 than in the PPL groups, and PLA 94 is also less likely to be infected than PPL, which could contribute to improving biocompatibility, but our results are not significant probably due to a lack of power. Anyway, PLA 94 did shrink less than PPL. A better tolerance and a lower degree of infection with a better integration of the mesh could explain the difference; physical reasons may explain the difference, including different hydrophilic surface properties, which could influence bacteria colonization [START_REF] Klinge | Do multifilament alloplastic meshes increase the infection rate? Analysis of the polymeric surface, the bacteria adherence, and the in vivo consequences in a rat model[END_REF]. Furthermore, research with more power would be interesting in order to find out a link between shrinkage, infection, and integration of meshes.

In conclusion, shrinkage, which is a complex phenomenon occurring during tissue healing around synthetic biomaterial, may be significantly influenced by both the polymer used for the implant and intraoperative bacterial contamination around the mesh. To explain the mechanism of shrinkage with infection, more powerful studies are needed. Are the meshes less integrated when infected? Mechanical strength tests and histological studies with more effective power would be

Table 1

 1 Comparative technical characteristics of the implanted meshes

	Name	Type of textile	Filament	Structure	Coating	Pore size (mm)	Amid classification	Weight (g/m 2 )
	None	PLA 94	Mono	Knitted	No	Macroporous (3.5×1.7)	I	100
	Parietene light	PP light	Mono	Knitted	No	Macroporous (1.5×1.7)	I	38

Table 2

 2 Results for infection and contractionPLA 94 poly (lactic acid) mesh, PP polypropylene mesh a The difference between infected PLA meshes and non-infected PLA meshes is significant in term of shrinkage (p<0.05): The infected one are more shrunk b The difference between infected PPL meshes and non-infected PPL meshes is significant in term of shrinkage (p<0.05): The infected one are more shrunk

	Meshes	Samples	Death	Infection on day30 (mean CFU)	Contraction (%±SD)	p
	Non-infected PLA 94	7	0	0	2.4±0.9	-
	Infected PLA 94 (E. coli 10e6 CFU)	7	1	7 (5×10e5)	5±1.7	<0.05 a
	Non-infected PP	7	1	0	11±2.5	-
	Infected PP (E. coli 10e6 CFU)	7	2	7 (2×10e6)	21.6±6.1	<0.05 b

Table 3

 3 Histological results (scores from 0 to 3) PLA 94 poly (lactic acid) mesh, PP polypropylene mesh Statistical comparison between the 14 non-infected meshes and the 14 infected meshes interesting. These observations are critical if the local complications of synthetic mesh placement by the vaginal route are to be reduced.

	Meshes	Mononuclear	Polynuclear	Foreign body	Vascularity	Collagen	Collagen	Collagen
		cells	cells	giant cells		organization	composition	amount
	PLA 94 , n=7	1.43 a	0.71	0.29	2.86	2.71	2.43	2.71
	Infected PLA 94 , n=6	2	0.83	0.33	2.5	2.5	2.67	2.8
	PP, n=6	2.5	1.33	1	2.17	2	1.83	2
	Infected PP, n=5	2.8	1.4	0.8	1.6	1.86	2	2
	p b	0.43	1.0	1.0	0.18	0.84	0.68	1.0

a Results: average score of the parameters b

Conflicts of interest This study represents a master thesis funded by Covidien. Renaud de Tayrac is a consultant for Covidien. The other co-authors have no conflict of interest.