José Miguel Vilca

Lounis Adouane

Youcef Mezouar

Robust On-line Obstacle Detection using Range Data for Reactive Navigation

Keywords: Mobile robots navigation, Obstacle detection and avoidance, Telemetry, Parameter identification, Extend Kalman Filter

. The main contribution proposed here is to perform this navigation in a completely reactive way while using only uncertain range data. Each obstacle, in this obstacle avoidance strategy, is surrounded by an ellipse and its parameters are obtained online while using the sequence of uncertain range data. This method uses the fusion between heuristic approach and Extended Kalman Filter (EKF) techniques to improve the computed ellipse parameters. A large number of simulations and experiments show the efficiency of the proposed on-line navigation in cluttered environment.

INTRODUCTION

An important issue for successful mobile robot navigation is obstacle avoidance. This function permits to prevent robot collision and insure thus robot safety. One area of research in obstacle avoidance is concentrated on reactive methods, where only local sensors information is used rather than a prior knowledge of the environment [START_REF] Toibero | Switching control of mobile robots for autonomous navigation in unknown environments[END_REF], [START_REF] Adouane | Hybrid and safe control architecture for mobile robot navigation[END_REF]. In [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF], the author proposes a real-time obstacle avoidance approach based on the principle of artificial potential fields. In this work, it is assumed that the robot actions are guided by the sum of attractive and repulsive fields.

Many other approaches can be found in the literature, such as the obstacle avoidance algorithm based on orbital trajectories. It is described by circular limit-cycle differential equations [START_REF] Kim | A real-time limitcycle navigation method for fast mobile robots and its application to robot soccer[END_REF], [START_REF] Jie | Real time obstacle avoidance for mobile robot using limit-cycle and vector field method[END_REF] or [START_REF] Adouane | Orbital obstacle avoidance algorithm for reliable and on-line mobile robot navigation[END_REF]. This work uses elliptical trajectories that was presented in [START_REF] Adouane | Mobile robot navigation in cluttered environment using reactive elliptic trajectories[END_REF]. Therefore, more generic and efficient obstacle avoidance is performed and this even with different obstacle shapes, for instance long walls. In fact, an ellipse fit better this kind of obstacles than a circle. At this aim, different approaches have been proposed in the literature to enclose the data with an ellipse [START_REF] Welzl | Smallest enclosing disks (balls and ellipsoids)[END_REF] and [START_REF] Zhang | Parameter estimation techniques: A tutorial with application to conic fitting[END_REF]. In [START_REF] Welzl | Smallest enclosing disks (balls and ellipsoids)[END_REF], the author proposed a technique to obtain the smallest enclosing ellipse by a set of data using primitive operation with linear increasing time with regards to data dimension. In [START_REF] Zhang | Parameter estimation techniques: A tutorial with application to conic fitting[END_REF], the author presents a summary of the methods to fit a set of data with an ellipse. The presented methods are the least square fitting based on algebraic and Supported by the French National Research Agency (ANR) through the Safeplatoon and R-Discover projects.

Euclidean distance, Kalman filtering method and robust estimation.

The Extended Kalman Filter has important application in different fields, such as parameters estimation, data fusion and signal processing [START_REF] Xiong | Robust kalman filtering for discrete-time nonlinear systems with parameter uncertainties[END_REF] and [START_REF] Fouque | Enhancement of global vehicle localization using navigable road maps and dead-reckoning[END_REF]. In robotics field, the main applications is found in localization, data fusion of the sensor and mapping [START_REF] Rigatos | Extended kalman and particle filtering for sensor fusion in motion control of mobile robots[END_REF] and [START_REF] Levinson | Robust vehicle localization in urban environments using probabilistic maps[END_REF]. In this work, we use the EKF to enhance the ellipse parameters obtained from uncertain data.

The rest of the paper is organized as follows: in the next section, the task of navigation using elliptic trajectories is presented. In section 3, the details of the control architecture are introduced and obstacle avoidance algorithm is given. Section 4 presents the method for enclosing the uncertain range data with an ellipse. Simulation and experimental results are given in section 5. Finally, conclusion and some future works are given in section 6.

NAVIGATION IN CLUTTERED ENVIRONMENT

First, let us assume that the obstacle O can be surrounded by an elliptical box (cf. Fig. 1). The elliptical shape is represented by its Cartesian form:

(x -h) 2 a 2 + (y -k) 2 b 2 = 1 (1)
where (h, k) ∈ 2 are the ellipse center coordinates and a, b ∈ + are the semi-axes with a ≥ b.

The choice of ellipse box rather than circle as used in [START_REF] Adouane | Mobile robot navigation in cluttered environment using reactive elliptic trajectories[END_REF] is to have one more generic and flexible mean to surround and fit accurately different kind of obstacles shapes (longitudinal shapes). In section 4, it will be shown how the ellipse parameters can be efficiently computed from range data. Let us also represent the robot and the target by circles C R and C T of radius R R and R T respectively (cf. Fig. 1). One can define:

(1) D RO as the minimal distance between the robot and the obstacle "O". (2) Ellipse of influence (E f ) as an ellipse that has the same center (h, k) and tilt angle Ω as the ellipse which surround the obstacle (1) while its major and minor semi-axes, a lc and b lc , are defined as follows

a lc = a + R R + Margin b lc = b + R R + Margin
where Margin represents safety tolerances encapsuling: perception uncertainties, control reliability and accuracy. (3) "l" as the line passing through the center of C R and C T . As we will see in the sequel, our method only needs to know if it exists intersection points between l and E f (cf. Fig. 1).

Fig. 1. The obstacle and robot modeling.

The objective of the navigation task in cluttered environment is to lead a mobile robot towards a specific target in an unstructured environment. This task must be achieved while avoiding static and dynamic obstacles O which can have different shapes.

CONTROL ARCHITECTURE

The used control structure is based on Benzerrouk et al.

(2010) (cf. Fig. 2). It aims to manage the interactions between elementary controllers while guaranteeing the stability of the overall control as proposed in [START_REF] Adouane | Hybrid and safe control architecture for mobile robot navigation[END_REF]. Its objective is also to insure safe, smooth and fast robot navigation. The specific blocks composing the global control are detailed below. This control architecture uses a hierarchical action selection mechanism to manage the switches between the controllers, according to environment perception. The mechanism activates the obstacle avoidance controller as soon as it exists at least one obstacle which can obstruct the future robot movement toward its target [START_REF] Adouane | Orbital obstacle avoidance algorithm for reliable and on-line mobile robot navigation[END_REF]. This allows to anticipate the activation of obstacle avoidance controller unlike what is proposed in [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF] or [START_REF] Adouane | Behavioral and distributed control architecture of control for minimalist mobile robots[END_REF], which wait until the robot is in the immediate vicinity of the obstacle (i.e. D RO ≤ R "a certain radius value").

Fig. 3. Robot configuration in a Cartesian reference frame.

Before describing each elementary controller, let us briefly recall the kinematic model of an unicycle robot (cf. Fig. 3)

  ẋ ẏ θ   = cos(θ) 0 sin(θ) 0 0 1 v ω (2)
where x, y, θ are configuration state of the unicycle at the point O m , v and ω are respectively, the linear and the angular velocity of the robot at the point O m .

Attraction to target controller

This controller guides the robot toward the target which is represented by a circle C T of center (x T , y T ) and radius R T (cf. Fig. 3). This controller is based on the position control of the robot to the target, represents by d and θ d in Fig. 3, more details are given in [START_REF] Benzerrouk | Lyapunov global stability for a reactive mobile robot navigation in presence of obstacles[END_REF]. As we consider a circular target with radius R T , therefore, to guarantee that the center of robot axes reaches the target with asymptotical convergence, d must be ≤ R T .

(cf. Fig. 3). The position errors are:

e x = x -x T = d cos(θ d ) e y = y -y T = d sin(θ d ) ( 3
)
where d is the distance of the robot to the target and θ d is the orientation of the line passing through the robot and the target. θ ∈ [-π, π] is the orientation error, such that θ = θ d -θ (4)

Its derivative θ is then θ = θd -ω (5)
From the previous equation and the kinematic model (2), we obtain θd

= ω r = v sin( θ)/d ( 6
)
where v is the linear velocity of the robot and d > 0.

Obstacle avoidance controller

To perform the obstacle avoidance behavior, the robot needs to follow accurately limit-cycle trajectories as detailed in [START_REF] Kim | A real-time limitcycle navigation method for fast mobile robots and its application to robot soccer[END_REF] or [START_REF] Adouane | Orbital obstacle avoidance algorithm for reliable and on-line mobile robot navigation[END_REF]. In these works, the authors use a circular limit-cycle characterized by a circle of influence of radius R I . In [START_REF] Adouane | Mobile robot navigation in cluttered environment using reactive elliptic trajectories[END_REF], it is proposed to extend this methodology for more flexible limit-cycle shape (an ellipse). The main ideas of this controller are detailed below.

The differential equations giving elliptic limit-cycles are: 8) with m = ±1 according to the direction of avoidance (clockwise or counter-clockwise, cf. Fig. 4). (x s , y s ) corresponds to the position of the robot according to the center of the ellipse; a lc and b lc characterize respectively the major and minor elliptic semi-axes (cf. Fig. 1); c if = 0 gives the Ω ellipse angle. Fig. 4. Clockwise and counter-clockwise shape for the used elliptic limit-cycles.

ẋs = my s + x s (1 -x 2 s /a lc 2 -y 2 s /b lc 2 -cx s y s ) (7) ẏs = -mx s + y s (1 -x 2 s /a lc 2 -y 2 s /b lc 2 -cx s y s ) (
The algorithm for obstacle avoidance is summarized by following main steps:

• The nearest hindering obstacle is detected,

• The direction of avoidance is chosen according to the position of the robot with regards to the position of the obstacle and the target, • The robot avoids the obstacle while following an elliptic limit cycle trajectory which has the semi-axes a lc and b lc , with a lc ≥ b lc .

Refer to [START_REF] Adouane | Mobile robot navigation in cluttered environment using reactive elliptic trajectories[END_REF] for details. The desired robot orientation is thus given by the differential equation of the limit-cycle ( 7) and (8) as:

θ d = arctg ( ẏs / ẋs ) (9)
and the error by: θ = θ d -θ (10)

Control law

The used control law is expressed as follows [START_REF] Benzerrouk | Lyapunov global stability for a reactive mobile robot navigation in presence of obstacles[END_REF]:

v = v max e -1/d cos( θ) (11) ω = ω r + K p θ (12
) where v max is the maximum linear velocity, K p is a constant such that K p > 0 and d is the distance between the robot and the target when the attraction to the target controller is activated, and d is equal to D RO if the obstacle avoidance is activated (cf. Fig. 1). The robot reaches the target when 0 < d ≤ R T .

It is interesting to notice that only one control law is applied to the robot even if the control architecture contains two different controllers. Only the set points change according to the applied controller, [START_REF] Benzerrouk | Lyapunov global stability for a reactive mobile robot navigation in presence of obstacles[END_REF].

ENCLOSING UNCERTAIN RANGE DATA WITH AN ELLIPSE

During the robot movement, it is important to detect online and to avoid the hinder obstacle. At this aim, the observed noisy range data are surrounded with the closest ellipse to apply elliptic limit-cycle approach.

For this purpose, let us consider a set of n points in 2 with coordinates P i (x i , y i ) (cf. Fig. 5). These points are computed from the data range of the robot, and the outliers are erased while using the Mahalanobis distance De [START_REF] De Maesschalck | The mahalanobis distance[END_REF]. In this section, it will be shown how to compute the ellipse that encloses all points. An important condition in this work is that the methods need to start at least with three different points.

start at least with three different points.

Range sensor model

The position of the obstacle with respect to the range sensor in 2 can be denoted by the polar coordinates (D Li , β i ), where D Li is the distance between the center of the robot and the impact point of the sensor and β i is the orientation with respect to the mobile reference frame (cf. Fig 5).

The sensor specifications and the real behavior of the sensor has significant differences [START_REF] Burguera | Sonar sensor models and their application to mobile robot localization[END_REF].

In this work, we focus on the accuracy of the range sensor, because we have observed that short range readings are more accurate than the long range ones. In [START_REF] Burguera | Sonar sensor models and their application to mobile robot localization[END_REF] it is observed how the mean and the standard deviation of the errors between the real and the measured range tend to increase with distance.

The reading range data provided by the range sensor at each time step is modeled by the Normal distribution

D t Li = N ( Dt Li , P t Li )
, where Dt Li is the mean vector and P t

Li is the covariance that is defined as the model of the range and angular uncertainties. The angular uncertainty is related to the sonar opening α and the range uncertainty is given according to the accuracy of the range sensor (cf. Fig. 5) [START_REF] Burguera | Sonar sensor models and their application to mobile robot localization[END_REF].

The following sub-sections will present the proposed methods to enclose the data with an ellipse. Sub-section 4.2 permits to address the problem of enclosing ellipse and the sub-section 4.3 is the extension of the proposed method to deal with uncertainty data and to enhance the identification of the ellipse parameters to get round the obstacle.

Heuristic approach

The proposed heuristic approach uses the distance between the points to obtain one of the axes. This method computes the distance between all the points d ij = p i -p j with i, j = 1, . . . , n; and select the maximum distance d max . We have thus, d ij ≤ d max . This d max is not decreasing if more data points are added. While connecting the points with the maximum distance, one of the ellipses axes is obtained. The ellipse center C O is the middle point between the points with maximum distances and the first semi-axis is a 1 = d max /2 (cf. Fig 6). Now, we work in the new coordinates system X Y to obtain the second ellipse semi-axis a 2 . We transform the n points to new coordinates system using (13).

P i = cos(Ω) sin(Ω) -sin(Ω) cos(Ω) (P i -C O ) ( 13
)
Where Ω is the orientation of the line between the two points that have the maximum distance. P i (x i , y i ) is the coordinate in the new system, P i (x i , y i ) is the coordinate in the initial system and C O is the coordinate of the ellipse center in the initial system.

If the value of |y i | of the points is greater than a threshold > 0, the distance of P i to the origin O is computed, i.e., if |y i | > ⇒ d i = P i is computed. This threshold is used to eliminate the points that are colinear with the two points that have the maximum distance (first axis) and the points in the perpendicular line to first axis (which could produce a large axis).

We know that all points inside the ellipse have the distance d i < max {a 1 , a 2 }. As we do not know the spatial distribution of the set of points and to ensure that all the points are inside the ellipse, we choose that a 2 = max {b i }, where b i is the computed semi-axis using P i in (1). In other words, b i ≤ a 2 ≤ max {a 1 , a 2 } ⇒ P i ∈ Ellipse. Hence, the ellipse encloses all points without regard of the obstacle shape. Finally, we obtain the semi-axes of the ellipse (1), cf. Fig 6, such as:

a = max {a 1 , a 2 } b = min {a 1 , a 2 } (14)
The orientation of the ellipse is Ω E = Ω + Π/2 if a 2 is the major axis, otherwise Ω E = Ω. The heuristic approach is an efficient method to enclose data with an ellipse, however, this method does not consider neither uncertain data nor the sequentiality of obtained data which characterize the real experiments. The following subsection deal with this issue.

Optimal parameters identification using EKF

Kalman filter is likely to have applications in many fields as a general method for integrating noisy measurements [START_REF] Rigatos | Extended kalman and particle filtering for sensor fusion in motion control of mobile robots[END_REF] and [START_REF] Levinson | Robust vehicle localization in urban environments using probabilistic maps[END_REF]. This approach uses the general conic equation which is given by: f (x, y) = Ax 2 + 2Bxy + Cy 2 + 2Dx + 2Ey + F = 0 (15)

According to the real constants A, B, C, D, E anf F , we obtain the analytic equation of the different kind of conics (parabola, ellipse and hyperbole). An ellipse is defined if the conic parameters ( 15) satisfy the following condition

B 2 -AC < 0.
The problem is to fit a conic section ( 15) with a set of n

points {p i } = {(x i , y i )} | i = 1, . . . , n.
This set of points are selected using ( 15) with the ellipse parameters from the heuristic method. These points satisfy the following condition |f (x i , y i )| < δ, and 0 < δ << 1, i.e., these points are close to the boundary of the obtained ellipse, other points are not consider for this method. As the data are noisy, it is unlikely to find a set of parameters (A, B, C, D, E, F ) (except for the trivial solution

A = B = C = D = E = F = 0) such that f (x i , y i ) = 0.
We applied this method to the conic fitting. The state vector is defined by the conic parameters as x = [A, B, C, D, E, F ] T and the measurement vector by the point as z i = [x i , y i ] T , a linear dynamic system (in discrete-time form) can be described by

x i+1 = F i x i + w i (16)
z i = H i x i + v i (17)
where i = 0, 1, . . .. The matrix state F i is the identity matrix of order 6 (I 6 ), w i is the vector of random disturbance of the state and is usually modeled as white noise: 17) is nonlinear and it is described by the observation function:

E[w i ] = 0, E[w i w T i ] = Q i The measurement equation (
f i (z i , x i ) = x 2 i A + 2x i y i B + y 2 i C + 2x i D + 2y i E + F (18)
where z i is the ideal measurement. The real measurement z i is assumed to be corrupted by additive noise v i , i.e. z i = z i + v i . We expand f i (z i , x i ) into a Taylor series about (z i , xi|i-1 ):

f i (z i , x i ) = f i (z i , xi|i-1 ) + ∂f i (z i , xi|i-1 ) ∂z i (z i -z i ) + ∂f i (z i , xi|i-1 ) ∂x i (x i -xi|i-1 ) + O((z i -z i ) 2 ) + O((x i -xi|i-1 ) 2 ) (19)
By ignoring the second order terms, we get a linearized measurement equation:

y i = M i x i + ξ i (20)
where y i is the new measurement vector, ξ i is the noise vector of the new measurement, and M i is the linearized transformation matrix. They are given by

M i = ∂f i (z i , xi|i-1 ) ∂x i y i = -f i (z i , xi|i-1 ) + ∂f i (z i , xi|i-1 ) ∂x i xi|i-1 ξ i = ∂f i (z i , xi|i-1 ) ∂z i (z i -z i )
Clearly, we have E[ξ i ] = 0, and E[ξ i ξ T i ] = R ξi . We consider then there is no correlation between the noise process of the system and that of the observation. The derivative of f i (z i , x) with respect to x and that with respect to z i , are given by

∂f i (z i , x) ∂x = [x 2 i , 2x i y i , y 2 i , 2x i , 2y i , 1] (21) ∂f i (z i , x) ∂z i = 2[x i A + y i B + D, y i C + x i B + E] (22)
The extended Kalman Filter (EKF) is then described by the well known following steps:

• Initialization: Π 0|0 = Π 0 , x0|0 = E[x 0 ] • Prediction of states: xi|i-1 = F i-1 xi-1 • Prediction of the state covariance matrix: Π i|i-1 = F i-1 Π i-1 F T i-1 + Q i-1 • Kalman gain matrix: K i = Π i|i-1 H T i-1 H i-1 Π i|i-1 H T i-1 + R v -1
• Update of the state estimation: xi = xi|i-1 + K i (z i -H i xi|i-1 ) • Update of the covariance matrix of states:

Π i = (I -K i H i )Π i|i-1
Note that the Kalman filtering technique is usually applied to a temporal sequence. Here, it is applied to a spatio-temporal sequence. This spatio-temporal sequence is composed of data from each sensor at each time. Due to its recursive nature, it is more suitable to problems where the measurements are available in a serial manner.

Otherwise, if all measurements are available or could be made available (with no serious overhead) at the same time, it is advantageous to applied the Kalman filter in a single joint evaluation (all the spatial sequence at the same time). This is because the Kalman filtering technique is equivalent to the least-squares technique only if the system is linear. For nonlinear problems, the EKF will yield different results depending on the order of processing the measurements one after the other, and may run the risk of being trapped into a local minimum [START_REF] Zhang | Parameter estimation techniques: A tutorial with application to conic fitting[END_REF].

SIMULATIONS RESULTS

To demonstrate the efficiency of the proposed approach to enclose the obstacle with an ellipse and to avoid it, a statistical survey was made. We consider a mobile robot with a radius of R R = 0.065 m and six infrared range sensors with the maximum detected range equal to D L max = 0.30 m (cf. Fig. 5). These sensors are in the front of the robot, with 30 • between each pairs of sensor (cf. Fig. 7). The accuracy of the used sensors based on the datasheet is around 10% of D L max. In the simulation, we consider uncertainty range with maximum value of 20% of D L max ensuring to take the worst range value. The maximum velocity of the robot is 0.4 m/s and the sample time is 0.01 s. For each simulation the robot starts at the same configuration and reach the same final configuration. We do not start to use any method until we have enough range data (n data ≥ 3).

This survey is used to make a focus around the proposed heuristic method and Kalman filter which gives satisfactory results and this while making an on-line navigation in cluttered environment (cf. Fig. 7).

Fig. 7 shows the trajectory of the robot in the environment with three obstacles. Moreover, the red points represent the range data from the sensor along all the trajectory. The range data buffer used to compute the ellipse parameters is delete to each new obstacle. We observe that the robot avoid the obstacles with a smooth trajectory. This trajectory was obtained while using the on-line obstacle avoidance algorithm [START_REF] Adouane | Mobile robot navigation in cluttered environment using reactive elliptic trajectories[END_REF] which takes its parameters (elliptical limit-cycle to follows) from the combination of the proposed heuristic approach and EKF. Fig. 7. Robot trajectory using the heuristic and EKF approach to enclosing the obstacle.

Fig. 8. Distance from the robot to the elliptical obstacles.

Fig. 8 shows the minimum distance between the elliptical obstacles (obtained while knowing all the range data without noise which surround the obstacle) and the position of the robot along of the elliptical trajectory using only the heuristic method (red dotted line), and the combination of heuristic method and EKF (green line). This figure shows that the robot does never collide with any obstacles when the robust approach is used, therefore, the proposed robust on-line approach is efficient to deal with cluttered and unstructured environment.

Experimentations are implemented using Khepera III robot (cf. Fig. 9), its kinematic model is given by ( 2). The navigation is achieved on a platform using the local infrared sensors of the robot. This test demonstrate the efficiency of the proposed robust enclosing ellipse approach.

The real trajectory of the robot avoiding two obstacles is given in figure 9. It can be seen that the robot successfully converges to its target after avoiding two obstacles (surrounded with two ellipses of influence).

CONCLUSION

This paper proposes robust on-line elliptic trajectory to perform smooth and safe mobile robot navigation. This elliptic limit-cycle trajectory is obtained while using the heuristic method combined with Extended Kalman Filter which deals with the uncertain range data to obtain the parameters of the ellipse which change smoothly. The main contribution of this work is to perform this navigation in a completely reactive way while using only uncertain range data. The obstacle avoidance method permits us to obtain generic and flexible navigation in very cluttered environments. The proposed reactive navigation was embedded in multi-controller architecture and permits for a mobile robot to efficiently navigate in environments with different obstacles shapes. These methods were implemented to evaluate the evolution of obtained ellipse in simulations and experimental form.

In future works, the problem of outliers detection of the range data will be accurately considered and the method will be extended for multi-robot system. Furthermore, the presence of dynamic obstacles will be developed.

Fig. 2 .

 2 Fig. 2. Control architecture for mobile robot navigation.

Fig. 5 .

 5 Fig. 5. Range sensor model and data set of n points. Before describing below the proposed methods to obtain the enclosing ellipse, let us present the model of the perceived data from range sensor in the following subsection.

Fig. 6 .

 6 Fig.6. Obtained ellipse using heuristic approach for two data set of points.

Fig. 9 .

 9 Fig. 9. Top view of the robot trajectory in the platform and observed uncertain range data from the robot.


Lounis Adouane

An Adaptive Multi-Controller Architecture for Mobile Robot Navigation

Keywords: Mobile robot navigation, Hybrid architecture of control, Adaptive systems, Lyapunov controller synthesis

This paper proposes a hybrid control architecture dedicated to the navigation of autonomous mobile robots in presence of obstacles. The proposed control structure is flexible, adaptive and takes into account the different possible interactions between the multitude of controllers composing the architecture of control. This is enabled by the use of stable elementary controllers and to specific mechanisms of coordination and adaptation which guaranties the stability of the overall architecture.

Introduction

The navigation of autonomous mobile robots in a cluttered and open environment is a fundamental problem that has received a large amount of attention. A part of literature in this domain considers that the robot is fully actuated with no control bounds and focuses their contribution on path planning. Voronoï diagrams and visibility graphs [START_REF] Latombe | Robot Motion Planning[END_REF] or navigation functions [START_REF] Rimon | Exact robot navigation using artficial potential flelds[END_REF] are among these roadmap based methods. However, the other part of the literature considers that to control a robot with safety, flexibility and reliability, it is essential to accurately take into account: robot's structural constraints (e.g., nonholonomy); avoiding command discontinuities and jerking set points, etc. Nevertheless, even in this method, there are two schools of thoughts, the one which uses the notion of planning and re-planning to reach the target e.g., [START_REF] Belta | Discrete abstractions for robot motion planning and control in polygonal environments[END_REF] and [START_REF] Conner | Integrated planning and control for convex-bodied nonholonomic systems using local feedback[END_REF] and those which are more reactive (without planning) like in [START_REF] Egerstedt | A hybrid control approach to action coordination for mobile robots[END_REF] or [START_REF] Toibero | Switching control of mobile robots for autonomous navigation in unknown environments[END_REF]. Our proposed architecture of control/management is linked to this last approach.

The architecture that will be able to guaranties multi-objective criteria can be elaborated with modular and bottom-up manner as introduced in [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF] and so called behavioral architectures [START_REF] Adouane | Hybrid behavioral control architecture for the cooperation of minimalist mobile robots[END_REF]. They are based on the concept that a robot can achieve a global complex task while using only the coordination of several elementary behaviors. It is considered in a lot of studies (the proposed paper is among them), the investigation of the potentialities of the hybrid systems controllers [START_REF] Zefran | Design of switching controllers for systems with changing dynamics[END_REF] which provide a formal framework to demonstrate the robustness and the stability of such architecture. Thus, this formalism permits a rigorous automatic's control analysis on the performances of the architecture of control [START_REF] Branicky | Multiple lyapunov functions and other analysis tools for switched and hybrid systems[END_REF].

The rest of the paper is organized as follows. Section 1 gives the specificities of the proposed control architecture. In section 2, the architecture of control is applied to the task of navigation in presence of obstacles. Details of the proposed and implemented elementary controllers are given also in this last section. Section 3 is devoted to the description and analysis of the simulation results. This paper ends with some conclusions and further works.

Control architecture

The proposed structure of control (cf. figure. 1) has an objective to manage the interactions between different elementary controllers while guaranteing the stability of the overall control. It will also obtain a suppleness of the control command when the switch between controllers occurs. It will permit for example to an autonomous applications of travelers transportation [START_REF] Pradalier | The cycab: a car-like robot navigating autonomously and safely among pedestrians[END_REF] to have more comfortable displacements of the passengers. The specific blocks composing this control are detailed below.

Hierarchical action selection

The activation of one controller in favor of another is achieved here completely with a hierarchical manner like the principle of the subsumption proposed by Brooks in [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF].

Controllers

Every controller is characterized by a stable nominal law which is represented by the function: F i (P i , t) = η i (P i , t) with: P i perceptions useful to the controller "i". Otherwise, in order to avoid among others, the important jump of commands at the time of the switch between controllers (for example here from the controller "j" toward the controller "i" at the instant t 0 ), an adaptation of the nominal law is proposed:

F i (P i , t) = η i (P i , t) + G i (t) (1)
with: G i (t) a monotonous function that tends to zero at the end of a certain time"T " and

G i (t 0 ) = F j (P j , t 0 -Δt) -η i (P i , t 0 ) (2)
where: Δt represents the sampling time between two control commands. The definition of G i (t) allows us to guarantee that the law of control (cf. equation. 1) tends toward the nominal control law after a certain time "T ", i.e., F i (P i , t 0 + T ) = η i (P i , t 0 + T ).

The function of adaptation G i (t) is updated by "the parameters adaptation block (see section below)" every time the switch of control toward the "i" controller occurs. The main constraint emanating from this structure of control is to guarantee the stability of the updated control law (cf. equation. 1) during the period where G i (t) is not zero.

Parameters adaptation

This block has as input the "conditional block" (cf. figure. 1) that verifies if the controller which should be active in the current instant "t" is different than the one active at the instant "t-Δt". If it is the case then it must update its function of adaptation (cf. equation. 2).

Navigation in presence of obstacles

The investigated task that is used to illustrate the application of the proposed control structure corresponds to the navigation of an unicycle robot in presence of obstacles (cf. figure . 2). The controlled position of the unicycle can be off-center as it is given in figure 2 by (l x , l y ). One presents below the proposed elementary controllers to achieve the desired navigation task.

Attraction to the objective controller

This controller guides the robot toward the target to reach. Classical techniques of linear systems stabilization can be used here to asymptotically stabilize the error e x = xx T and e y = yy T to zero, where: (x, y) corresponds to the position of the robot and (x T , y T ) corresponds to the position of the target (cf. figure . 2). We use a simple proportional command which is given by:

v w = -K cos θ -l x sin θ sin θ l x cos θ -1 e = -K cos θ sin θ -sin θ / l x cos θ / l x e x e y (3)
With: v and w are respectively linear and angular speed controls; K > 0; l x = 0 (cf. figure . 2). To guaranty the right transition between controllers as described in sections (1.2) and (1.3), the modification to the above command becomes:

v w = -K cos θ sin θ -sin θ / l x cos θ / l x e x e y + G A_v (t) G A_w (t) (4)
While using the following Lyapunov function

V 1 = 1 2 d 2 (with d = e 2
x + e 2 y ), we therefore obtain V1 = d ḋ.

To guaranty that the proposed controller is asymptotically stable we must have V1 < 0. Therefore, after some simplification we can deduce that:

K > -(G A_v (t)e x + G A_w (t)e y ) e 2 x + e 2 y ( 5
)
Where G A_v (t) and G A_w (t) functions must be chosen with respect to the constraints given in sections (1.2) and (1.3) and to the fact that they decrease more quickly to zero than d 2 (to have bounded K).

Obstacle avoiding controller

To implement this controller, the method of the limit-cycle was used [START_REF] Kim | A real-time limit-cycle navigation method for fast mobile robots and its application to robot soccer[END_REF]. The control law proposed to follow these trajectories (which tends toward a circle of R A radius (cf. figure . 2)) is a control of orientation. The robot is controlled in relation to the center of its axle. The desired robot orientation θ d is given by θ d = arctan( ẏ ẋ ) where ( ẋ and ẏ) are given by a differential equation describing the limit-cycle [START_REF] Kim | A real-time limit-cycle navigation method for fast mobile robots and its application to robot soccer[END_REF], and the error by θ e = θ dθ.

One can control the robot to move to the desired orientation by using the following control law: w = θd + K p θ e + G O (t), where K p > 0 and G O (t) the function which guaranties the right transition between controllers (cf. sections (1.2) and (1.3)). It is noted that the nominal linear speed of the robot v for this controller is considered as a constant.

The derivative of θ e is given by θe = -K p θ e -G O (t). One takes the following Lyapunov function

V 2 = 1 2 θ 2 e . Therefore, V2 = θ e θe = -K p θ 2 e -G O (t)θ e .
To guaranty that the proposed controller is asymptotically stable we must have V2 < 0, so:

K p > - G O (t) θ e (6)
Where G O (t) function is chosen with respect to the constraints given in section 1.3 and the fact that it decreases more quickly to zero than θ e .

Simulation results

Before giving comments on the achieved simulation, it must be noted that G A_v (t), G A_w (t) and G O (t) were implemented using decreasing linear functions. Figures 3(a Figure 4 shows the effect of the use of adaptive parameters mechanism on v and w control commands (here the obstacle is clockwise skirting). v and w control becomes thus less abrupt and smoother when the switch between controllers occurs.

Conclusion and future works

In this paper, an adaptive multi-controller architecture of control is proposed and applied on the task of mobile robot navigation in presence of obstacles. The proposed adaptive mechanism permits to achieve the switch between controllers while guaranteeing the smoothness of the control commands and the stability of the overall system. Future works will test first the proposed architecture of control on the CyCab vehicle [START_REF] Pradalier | The cycab: a car-like robot navigating autonomously and safely among pedestrians[END_REF]. The second step is to apply the proposed structure of control on more complex tasks like navigation in highly dynamical environment.

Figure 1 .

 1 Figure 1. Hybrid control architecture for mobiles robots navigation

Figure 2 .

 2 Figure 2. Mobile robot and the task parameters for the navigation in presence of obstacles

  ) and3(b) show respectively the clockwise and counter-clockwise obstacle avoiding when the proposed control architecture is used.

Figure 3 .

 3 Figure 3. Application of the proposed control architecture for different target position

  w control with adaptive control

Figure 4 .

 4 Figure 4. Effect of the adaptive parameters mechanism on v and w control commands

Figure 5

 5 Figure5shows that the overall proposed structure of control is stable, and here the Lyapunov function attributed to each controller V i | i=1..2 decreases always asymptotically to the equilibrium point.

Figure 5 .

 5 Figure 5. Evolution of V 1 and V 2 Lyapunov functions


Lounis Adouane

Nadine Le Fort-Piat

METHODOLOGY FOR PARAMETERS OPTIMIZATION OF AN HYBRID ARCHITECTURE OF CONTROL

Keywords: Behavioral architecture of control, Cooperative mobile robotics, Parameters optimization, Genetic algorithms

This paper presents a methodology for parameters optimization applied to an hybrid behavioral control architecture. The coordination between behaviors in this architecture is insured using both hierarchical and fusion action mechanisms. This global mechanism of coordination is characterized by a multitude of parameters which must be finely tuned to enhance the efficiency of the execution of cooperative tasks. The proposed parameters optimization is obtained using genetic algorithms. Appropriate genetic operators are used to manipulate real chromosomes with a normalization relationship between its genes. The validation of the results is established using a large number of simulations.

INTRODUCTION

Behavioral architectures of control are based on the concept that a complex behavior of a robot can be obtained from the coordination of several elementary behaviors. This coordination can be either competitive or cooperative.

In competitive architectures, the command is given by an unique behavior, which has been selected temporarily among a set of active behaviors. The principle of competition can be defined by a set of fixed priorities like in subsumption architecture where a hierarchy is defined between behaviors [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF]. This principle can be also dynamic like in the actions selection architecture [START_REF] Maes | The dynamics of action selection[END_REF] where the behavior with a great level of activation is selected.

In cooperative architectures, the final command is the result of a compromise or a fusion between different behaviors, which are active at the same time. This include the fuzzy control [START_REF] Saffiotti | Robust execution of robot plans using fuzzy logic[END_REF] via the process of defuzzification, the schema-based architecture [START_REF] Arkin | Motor schema-based mobile robot navigation[END_REF] which uses vectorial addition to encode the robot's behavioral response.

Competitive like cooperative process of selection need to set or to adapt specific parameters according to the task to achieve. These parameters are generally tedious to obtain. For this reason, many works deal with their optimization. Parker (94) uses reinforcement learning for parameters adaptation of motivational behaviors blocks used to enhance the pushing of a long rectangular box. In (Ram,et al.,94), authors use a genetic algorithm to learn appropriate parameters corresponding to schemas motors dedicated for local navigation of a mobile robot.

This paper deals with Cooperative Box-Pushing

Task "CBPT". The proposed architecture of control combines the coordination principles of subsumption and motor schemas to obtain an efficient control architecture for cooperative robotics. The appropriate parameters of fusion blocks are determined using specific parameters optimization based on genetic algorithms.

The rest of this paper is organized as follows. Section 2 gives the specifications of the CBPT and a short description of the simulated mini-robots. Section 3 presents the details of the proposed hybrid architecture of control. Section 4 is devoted to the description and the analysis of the proposed methodology for parameters optimization. A brief description of MiRoCo simulator is also done. Conclusions and future directions are presented at the end of the paper.

COOPERATIVE BOX-PUSHING TASK

CBPT remains a privileged complex task for the study of reactive and distributed features for cooperative robotics control [START_REF] Kube | Collective Robotics: From Local Perception to Global Action[END_REF]. This task is difficult to control due to the large dynamic of entities interactions in direct surrounding of the object to push. In addition to that, the used robots in this study are very limited in structural, decisional and sensory point of views. Indeed, the mobile mini-robot named ALICE (Fig. 1) has very reduced dimensions of 2cm×2cm×2cm [START_REF] Caprari | Fascination of down scaling -Alice the sugar cube robot[END_REF] and has, in its original structure, only four infrared sensors IS1, IS2, IS3, IS4 which measure light intensity and local distance to obstacles.

Infrared Sensors

IS1

CONTROL ARCHITECTURE

The proposed behavioral architecture of control (Fig. 2) is composed by a set of elementary behaviors (Adouane and LeFort-Piat, 2004a) where each of them can send a command C among a set of discrete commands C d :

-

Go Forward GF = C(0 • , Tra cm), -Go Backward GB = C(0 • , -Tra cm), -Go Right-Rotate GRR = C(-Rot • , 0 cm), -Go Left-Rotate GLR = C(Rot • , 0 cm), -Go Right-Turn GRT = C(-Rot • , Tra cm), -Go Left-Turn GLT = C(Rot • , Tra cm),
-Remain There RT = C(0 • , 0 cm).

Where: Rot and Tra constants correspond respectively to rotational and translatory commands which will be executed by the robot in a coupled movement.

Each mini-robot can measure the θ angle that it makes with an active landmark in the environment. θ angle goes from -180 • to 180 • and it can be measured with an incertitude of ±15 • .

Elementary behaviors

Exploration This behavior sends commands to the motors according to predetermined constant coefficients of the occurrence probability of each command C ∈ C d .

Obstacles avoiding This behavior uses the four infrared sensors only in boolean mode. It consists therefore in avoiding the obstacles according to a pre-established strategy giving the response according to the sixteen possible stimuli of the infrared sensors.

Attraction to the Box This behavior consists in attracting the mini-robot towards the box, which broadcasts light. This is performed using the infrared sensors just in reception mode.

Alignment This behavior consists in insuring that the mini-robot is aligned with the box B before activating the behavior of Box-pushing or the one of Repositioning. Therefore, this behavior controls the relative angle δ that the mini-robot makes with B, so that δ ∈

[-η • , η • ].
Box-pushing After the detection of θ 1 and θ 2 angles that the mini-robot makes with respectively the box B and with the target T (Fig. 3), this behavior generates a response according to the following rule:

If ((|θ 1 |and |θ 2 |) ≤ θ Max ) Then apply the GF Else apply RT command.
With θ Max is a positive constant less than 90 • .

α = f(θ) ( 1 )
• after the rotation is ended, the robot moves forward for a distance of d[cm] such as

d = g(θ) ( 2 )
Where α and d are as big as |θ| is big.

Altruistic behaviors

The altruism is the fact to generate an effect (an action) with the objective to help its neighbors, and this without immediate obvious gain for the entity that generates this effect. The notion of altruism introduced in the proposed architecture of control is represented by the following two behaviors.

a -Broadcast of the altruistic signals: This behavior is activated when behaviors of Box-pushing or Repositioning are activated (Fig. 2). This purely altruistic behavior consists in giving out attractive or repulsive signals (Fig. 4) as follows.

If (|θ| < θ Max

) Then the signal is attractive Else the signal is repulsive.

Coordination of behaviors

Hierarchical coordination In the proposed architecture of control, the hierarchical coordination between behaviors is managed entirely through their responses. Indeed, among all the possible responses given by each behavior, it exists a specific response called Refuge Response "RR" (Adouane and LeFort-Piat, 2004a) which is generated for a particular stimulus of sensors.

The principle of using the "RR" to hierarchically coordinate a set of behaviors is the following: starting from the behavior "n" of highest level in the architecture of control (Alignment behavior in (Fig. 2)) If it generates a command C n = "RR n " Then C n is executed by robot's motors Else behavior "n" gives the hand to the behavior "n-1" which applies the same rule. Thus, by chain effect, the hierarchical coordination is achieved.

Fusion organization

To avoid undesirable effects linked to the pure hierarchical coordination, fusion blocks Σ 1 , Σ 2 , Σ 3 (Fig. 2) are introduced. These blocks compute a command as follows:

For each command "C j (Rot j , Tra j )| j=1..3 " in input of a fusion block Σ i | i=1..3 is associated a gain, respectively g ij | j=1..3 such as:

j=1..3 g ij = 1 with : g ij | j=1..3 ∈ ]0 1[ (3)
The output of the fusion block Σ i | i=1..3 is a command C i (Rot i , Tra i ) given by this method: If Box-pushing, Repositioning, or Attraction to the box behaviors give their RR Then the corresponding fusion block (respectively Σ 1 , Σ 2 and Σ 3 ) gives in output this RR which allows to not inhibit behaviors or fusion blocks of lower levels.

Else the Rot i and Tra i components of C i are computed as follows:

Rot i = ∠   j=1..n (g ij • -→ v ij )   (4) Where -→ v ij are unit vectors as ∠ -→ v ij (angle -→ v ij ) = "Rot j ". Tra i = j=1..n (g ij • Tra j ) ( 5 )

PARAMETERS OPTIMIZATION

To improve the achievement of the CBPT, the mini-robots must compute their commands in order to satisfy many criteria at the same time. For the case of Σ 3 which has as global objective to lead the robot toward the box, the different criteria are as follows: to move toward the box while avoiding others mini-robots (and/or obstacles) and if the mini-robot detects altruistic signals, to react consequently.

The choice of g ij | i=1..3,j=1..3 gains of the fusion blocks Σ 1 , Σ 2 , Σ 3 can be obtained empirically like in [START_REF] Adouane | Hybrid behavioral control architecture for the cooperation of minimalist mobile robots[END_REF] where they are chosen according to the emergence of some visual configurations of the mobile robots. However, this phase can be tedious. Thus to avoid a too long manual trial-error method to obtain the more suitable gains for the fusion blocks, we propose to use genetic algorithms "GA" which are very suitable for multicriteria and parameters optimization. In what follows, the proposed methodology of optimization will be explained through its application on the gains g ij | i=3,j=1..3 of Σ 3 fusion block.

The population used for the GA is constituted of a large number of chromosomes. Each of them contains three genes corresponding the the gains attributed to Σ 3 and which must satisfy (3).

These gains coupled to the commands generated by corresponding elementary behaviors (i.e., Attraction to the box, Obstacle avoiding and Altruistic signals answers) characterize completely the motion of the mini-robot when the fusion block Σ 3 is activated. Therefore, commands generated by Σ 3 should give the best compromise between keys objectives that lead the robot toward the box.

Figure 5 shows the method applied to the evaluation of each chromosome of the population.

The temporary fitness evaluation Fitness kij of one chromosome, is obtained according to (6): Where:

Fitness kij = α 1 × CRB kij + α 2 × DRB kij -α 3 × DRO kij +α 4 ×DRSA kij -α 5 ×DRSR kij (6)
• CRB kij is a boolean variable which represents the collision or not of the robot with the box, (CRB kij = '1' if the robot collides with the box, and '0' else),

• DRB kij , DRO kij , DRSA kij , DRSR kij
represent the relative displacement of the robot in relation to the box, obstacles and altruistic signals (attractive and repulsive) respectively, and this when they are detected by the robot's sensors. These relative displacements give the means to estimate if the robot goes closer (positive value) or moves away (negative value) from the detected agents, • α i | i=1..5 are the priority (balance) attributed to each corresponding criteria to achieve the attraction to the box behavior. We chose to give more priority respectively to the collision with the box α 1 = 2 to give more favor to chromosome which leads to reach the box quickly; α 2 = 1.4 to go toward the box; α 3 = 1 to avoid obstacles; α 4 =α 5 =0.4 to respond to altruistic signals.

The global fitness Fitness affected to each chromosome is calculated as follows:

Fitness = 1 k=0 iMax i=0 jMax j=0
Fitness kij (7)

Where: "k" corresponds to the iteration made with and without altruistic signals surrounding the box; "i" represents different initial positions and orientations taken by the robot at each start of simulation; and "j" corresponds to the number of steps before stopping the simulation number "i".

Simulation environment

To apply the proposed methodology of parameters optimization, we have used the MiRoCo (Mini-Robotics Collective) simulator (Fig. 6) which permits to have a good approximation of: ALICE mini-robot structure, the displacement and the accurate interaction between the mini-robot and its environment, etc. This simulator allows also to make a very big number of simulations to evaluate each chromosome of the population.

Genetic cycles

To achieve genetic cycles which allow to obtain optimal chromosome (gains) for Σ 3 which maximize (7), we use appropriate selection, crossover and mutation operators. These operators are adapted to manipulate real genes [START_REF] Guvenir | Multicreteria inventory classification using a genetic algorithm[END_REF], [START_REF] Muhlenbein | Predictive models for the breeder genetic algorithm. I: Continuous parameter optimization[END_REF], while taking into account (3).

Selection operator This is performed using the roulette wheel selection [START_REF] Goldberg | Gentic Algorithms[END_REF].

Crossover operator This operator allows to cross two chromosomes while preserving the sum of any sequence of genes. Given two normalized chromosomes x = x 1 , x 2 , x 3 and y = y 1 , y 2 , y 3 , the obtention of two normalized offsprings x = x 1 , x 2 , x 3 and y = y 1 , y 2 , y 3 is such as:

x i = sx i + (1 -s)y i y i = (1 -s)x i + sy i (8)
where "s" is a stride and changes randomly between [0, 0.5] for each crossover operation.

Mutation operator This operator transforms the value of a random gene to either 0 or 1 with equal probability. Therefore, if a chromosome undergone a mutation, it must be normalized according to (9).

x i=1..3 = x i 3 j=1 x j . ( 9
)

Simulations Results

The genetic algorithm is applied on a population of 1000 chromosomes, with the probability of crossover and mutation equal respectively to 0.8 and 0.02.

Figure 8 shows the evolution of the maximum and average fitness of consecutive populations. Optimal chromosome is obtained after 120 genetic cycles and it corresponds to:

• Σ * 3 : g * 31 = 0.181, g * 32 = 0.400, g * 33 = 0.419 For the fusion blocks Σ 1 and Σ 2 (Fig. 2), we consider the same parameters as in [START_REF] Adouane | Hybrid behavioral control architecture for the cooperation of minimalist mobile robots[END_REF]):

• Σ 1 : g 11 = 0.500, g 12 = 0.400, g 13 = 0.100 To validate the relevance of the proposed evaluation methodology, which assigns a fitness to chro-mosomes according to their adaptation to achieve the attraction to the box sub-task, we take the optimal chromosome x * = 0.181, 0.400, 0.419 and the chromosome y = 0.596, 0.397, 0.006 which has a fitness value on the middle part of the final population. The test consists in putting sequentially each of these two chromosomes on the fusion block Σ 3 and to perform a large number of CBPT with the global architecture of control (Fig. 2). The minimum number of robots to push the box Nc was chosen equal to 2. In the simulations, the number of robots N is increased from 2 to 11, and for each N, 50 simulations were made. Initial conditions of the simulations are the same for both chromosomes.

Figure 9 shows the number of activation NA of the fusion block Σ 3 for all the robots which participate to achieve the CBPT. Figure 10 shows the average time needed by the robots to lead the box from its initial position toward the target.

We observe that the NA corresponding to the best chromosome are smaller than those obtained for the less fitness chromosome. NA smaller indicates that robots found quickly the box and contribute thus actively to push it. This is confirmed in (Fig. 9) where the time necessary to achieve the CBPT becomes smaller when the best chromosome is used by the architecture of control.

CONCLUSIONS AND FUTURE WORKS

A methodology of parameters optimization for an hybrid architecture of control was proposed in this paper. The optimization has been done using a genetic algorithm via appropriate genetic operators, which deals with real value chromosomes. The adopted genetic operators prove to be very efficient to obtain quick convergence of the genetic algorithm toward appropriate parameters. The validity of the optimization is confirmed through a batch of cooperative box-pushing task simulations. Future works are going to use multiobjective optimization like Pareto-optimal method in order to attribute appropriate parameters of control according to robot's ecological niche. Experimentations with the physical mini-robots ALICE endowed with optimal parameters of control are going also to be made.

  Fig. 1. Mini-robots ALICE The CBPT can be summarized as follows. The environment contains a number N of robots that must push a box B towards a circular target T. The displacement of B requires in less the cooperation of a critical number Nc of robots.

Fig. 2 .

 2 Fig. 3. Box-pushing necessary information

Fig. 4 .

 4 Fig. 4. Attractive and repulsive signalsThese signals have the objectives to attract minirobots around the privileged zone (zone where the mini-robots are susceptible to appropriately push B toward T) and at opposite, to repulse minirobots from non-privileged zone. Figure4shows roughly these two zones.

Fig. 5 .

 5 Fig. 5. Adopted methodology for evaluate each chromosome affected to Σ 3

Fig. 6 .

 6 Fig. 6. MiRoCo, a simulator for collective mobile robotics

Fig. 8 .

 8 Fig. 8. Evolution of the GA optimization

Fig. 9 .

 9 Fig. 9. NA of Σ 3 according to N

  • Σ 2 : g 21 = 0.500, g 22 = 0.450, g 23 = 0.050

With: g 11 , g 21 , g * 31 are gains of commands corresponding respectively to Box-pushing, Repositioning and Attraction to the box behaviors; g 12 , g 22 , g * 32 correspond to Obstacles avoiding behavior and g 13 , g 23 , g * 33 correspond to Altruistic signals answers behavior.


Lounis Adouane

Nadine Le Fort-Piat

Hybrid Behavioral Control Architecture for the Cooperation of Minimalist Mobile Robots

Keywords: Cooperative robotics, Behavioral architecture of control, Altruistic behavior, Box-pushing task

This paper presents a hybrid control architecture based on subsumption and schemas motors principles in order to achieve complex and cooperative tasks. The control architecture implemented is constituted by a set of independent and elementary behaviors organized in layers of skills. Specific low-level behaviors, called altruistic behaviors and inspired by societies of insects (attractive or repulsive signals), are used to improve the efficiency of the control. Therefore, competitive and cooperative mechanisms are used in an unique hybrid architecture of control to perform a complex box-pushing task by a set of mini-robots. The analysis of an elevated number of simulations allows us to have statistical results (time to complete the task was chosen as performance criteria) which show the existence of an optimal number of robots to achieve the box-pushing task and underline the importance of the use of altruistic behaviors to enhance the cooperative task.

I. INTRODUCTION

Cooperative robotics constitutes an active research field especially for completion of complex tasks which requires coordination of several elementary entities. The behavioral architectures are based on the concept that a global behavior (complexe task) of a robot can be done by the coordination of several elementary behaviors. In the literature, two families of techniques of coordination exist, competitive and cooperative architectures.

In competitive architecture, the command is given by an unique behavior, which has been selected temporarily among a set of active behaviors. The principle of competition can be defined by a set of fixed priorities like in subsumption architecture where a hierarchy of the different behaviors is defined [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF]. This principle can be also dynamic like in the actions selection architecture [START_REF] Maes | The dynamics of action selection[END_REF] in which the behavior with a great level of activation is selected, this level is recomputed all time.

In cooperative architectures, the final command is the result of a compromise or a fusion between controls proposed by different behaviors, which can be active at the same time. The schema-based architecture [START_REF] Arkin | Motor schema-based mobile robot navigation[END_REF] [START_REF] Balch | Motor schema-based formation control for multiagent robot teams[END_REF] uses in a general manner the same potential field technique [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF] [START_REF] Arkin | Behavior-Based Robotics[END_REF] for the computation of the response of each elementary behavior and to encode the robot's behavioral response.

The box-pushing task "BPT" is among the reference task using by researchers who work in the field of cooperative robotics. Generally the reference task tests the efficiency and the robustness of their control strategy. In what follows we will mention some proposed control in the literature which deals with the BPT. Reference [START_REF] Emery | Behavior-based control of a non-holonomic robot in pushing tasks[END_REF] propose different schemabased motor control systems, among others the one which is used to position correctly the robot around desired object to push. Reference [START_REF] Parker | Adaptive heterogeneous multi-robot teams[END_REF] uses principally motivational behaviors, periodic communication between robots and the evaluation of a specific metric to perform the action selection strategy for the pushing of a long rectangular box. Reference [START_REF] Yamada | Adaptive action selection without explicit communication for multirobot box-pushing[END_REF] the authors shows the possibility of achieving a cooperative BPT without direct communication between the agents. In reference [START_REF] Kube | Task modeling in collective robotics[END_REF], the authors use eleven identical robots endowed with purely reactive behaviors, and specify transitions between behaviors using binary sensing predicates.

Our proposed architecture of control combine the two techniques of coordination mentioned above (i.e., the subsumption and motor schema principles) to obtain efficient control architecture to swarm robotics (i.e., with large number of robots) which roughly interact between them to realize the BPT. We also introduce in this architecture of control the use of simple attractive and/or repulsive signals broadcasted by robots to increase their cooperation, and thus the execution of the BPT.

Section II starts with the specifications of the box-pushing task and by the description of simulated mini-robots features. In section III, we present in details the proposed hybrid architecture of control. Section IV is devoted to the description and the analysis of the set of simulations. A brief description of MiRoCo simulator is also done. This paper ends with some conclusions and perspectives.

II. BOX-PUSHING TASK SPECIFICATIONS

Box-pushing task remains a privileged complex task for the study of the features of reactive and distributed control of a group of cooperative robots. Cooperative BPT is difficult to control [START_REF] Lynch | The mechanics of fine manipulation by pushing[END_REF], due to the multitudes of forces applied on the box (dry and/or viscous friction, directions and strength forces of contact applied by robots, weight...etc.). This task is made even more difficult due to the large dynamics of the entities in interaction (robots, obstacles, object to push, ...etc.) and by the use of robots that are very limited in structural (power delivered by the mini-robots), decisional and sensory point of views. Knowing the multiple difficulties generated by the task of pushing object, this one proves to be a very interesting task to show the multiple capabilities that an hybrid stimulusresponse control architecture can have on its realization. The box-pushing task can be summarized as follows. We have a number N of mini-robots that must drive a box B towards a circular target T. The displacement of B requires in less the cooperation of a critical number Nc of mini-robots.

A. ALICE mini-robot

We adopted for the experimental platform, the general structure of the ALICE mini-robot (Fig. 1) built at the EPFL 1 [START_REF] Caprari | Fascination of down scalingalice the sugar cube robot[END_REF]. ALICE mini-robot is based on a modular design, thus it is very easy to add and/or to take out new sensors and/or communication floors. The ALICE minirobot has very reduced dimensions (2cm×2cm×2cm), and is equipped with a PIC16F877 microcontroller with only 8 Kwords Flash EPROM program memory capacity. That considerably reduces the size of the control program that can be implemented. ALICE maximum speed is of 4cm/s and it has four infrared sensors IS1, IS2, IS3, IS4 positioned respectively at 0˚, 45˚, 180˚and -45˚in relation to the front face of the mini-robot. These sensors detect obstacles at a maximal distance of 4cm. This restricts the mini-robot to short localized information.

III. CONTROL ARCHITECTURE

Because the mini-robots used in this work have very basic perceptual and decisional capabilities, we implement a purely stimuli-responses control inspired of individuals constituting the societies of insects [START_REF] Bonabeau | Swarm intelligence 'from Natural to Artificial systems[END_REF].

We have defined a behavioral architecture, in which each behavior can be tested individually, in order to verify the reliability and the efficiency of this behavior to achieve a determined primitive. All these behaviors are gathered after in an unique and hybrid architecture (Fig. 2).

A. General features of behaviors

We adopt in what follows the next notations : -command (Ori, Dis) : This response is given by the behaviors and consists of making the execution by the mini-robot of a rotation of "Ori" degrees and a 1 Ecole Polytechnique Fédérale de Lausanne translatory motion of "Dis" centimeters in a coupled movement. All behaviors, except for the behavior of Broadcast of the altruistic signals, have the possibility of sending the following discrete commands :

-Go Forward GF = command (0˚, 1 cm), -Go Backward GB = command (0˚, -1 cm), -Go Right-Rotate GRR = command (-15˚, 0 cm), -Go Left-Rotate GLR= command (15˚, 0 cm), -Go Right-Turn GRT = command (-15˚, 1 cm), -Go Left-Turn GLT = command (15˚, 1 cm), -Remain There RT = command (0˚, 0 cm). The activation of Alignment, Box-pushing or Repositioning behaviors is linked to the direct contact between the mini-robot and the box to push.

We consider that at each moment the mini-robot can measure the angle θ that it makes with an active landmark in the environment. θ is between -180˚and 180˚.

B. Description of the control architecture

In the next sections, we start to present individually all elementary behaviors used in the proposed hybrid architecture of control. We will explain after the principles of coordination implemented between behaviors. e) Box-pushing behavior: After the detection of angles that the mini-robot makes with the box B and the one with the target T, respectively θ 1 and θ 2 (Fig. 3), this behavior f) Repositioning behavior: The aim of this behavior is to appropriately, and quickly reposition the mini-robot around B . According to the measured θ angle between the mini-robot and the target T at the instant t, this behavior is going to generate a sequence of commands [START_REF] Adouane | Bio-inspired behaviours of a group of microrobots for cooperative box-pushing task[END_REF] like following :

-the mini-robot rotates with an angle α [degrees] as in

α = f(θ). (1)
-after the rotation is ended, the mini-robot moves forward for a distance of d [centimeters] as in

d = g(θ). (2)
Where :

-f and g are linear functions of the θ angle, -α and d are as big as |θ| is big, -the direction of the rotation depends on the sign of θ as follows :

If (θ ≤ 0) Then apply GLR command Else apply GRR command.

g) Altruistic behaviors:

The altruism is the fact to generate an effect (an action) with the objective to help its neighbours, and this without immediate obvious gain for the entity that generates this effect. The notion of altruism introduced in the proposed hybrid architecture of control, can be summarised by these two behaviors : the first one is the Broadcast of the altruistic signals and the second is the Altruistic signals answers. The first generates altruistic signals and the second exploits the altruistic signals generated by other robotics entities.

Broadcast of the altruistic signals behavior This behavior is activated when behaviors of Box-pushing or Repositioning are activated (Fig. 2). This purely altruistic behavior consists in giving out attractive or repulsive signals (Fig. 4) as follows.

If (|θ| < θ Max ) Then the given out signal is attractive Else the signal is repulsive.

These signals have the objectives to attract mini-robots around the privileged zone (zone for which the mini-robots are susceptible to appropriately push B towards T ) and at opposite, to repulse mini-robots from non-privileged zone. Fig. 4, shows roughly these two zones.

The range E and the intensity I of the signal are modulated according to the θ angle that the mini-robot makes with the target T. This modulation is as large as :

-|θ| tends to 0˚in the case of attractive signal, indicating by this fact that the mini-robot is in the ideal position to push B. -|θ| tends to 180˚in the case of repulsive signal, indicating by this fact that mini-robot is positioned at opposite to where it must be to push B towards T .

Altruistic signals answers behavior

The answers to the altruistic signals are commands that attract the mini-robot towards the most attractive altruistic signals (of bigger intensity) and move away from the most repulsive altruistic signals read by the four infrared sensors. This kind of hierarchy is managed entirely in our architecture of control via the responses (commands) generated by the behaviors as follows.

In addition to all the possible responses given by the behaviors for corresponding stimuli of sensors, we add for each behavior a specific response called Refuge Response "RR" [START_REF] Adouane | Bio-inspired behaviours of a group of microrobots for cooperative box-pushing task[END_REF] generated for a particular stimulus of sensors. We notice that :

-a distinct RR is assigned to each elementary behavior, -each behavior knows the RR corresponding to the behavior which is one level hierarchically superior.

These two points allow to a low-level behavior to activate its command instead the one of a high-level only when it detects the activation of the Refuge Response corresponding to this one (the high-level behavior). Thus by chain effect, we realize the hierarchical coordination.

b) Fusion organisation:

The implementation of our control architecture based only on the previous subsumption coordination [START_REF] Adouane | Bio-inspired behaviours of a group of microrobots for cooperative box-pushing task[END_REF] leads us to observe the existence of some microscopic undesirable effects, which are directly linked to the elevated number of mini-robots in the immediate surrounding of the box to push. To avoid these undesirable effects (see section "Interest of using fusion blocks"), we introduce fusion blocks of behaviors (Σ 1 , Σ 2 , Σ 3 (Fig. 2)), which compute a command according to the commands given by merged behaviors. The principle of this fusion is explained below : For each command "command i (Ori i , Dis i )| i=1..3 " in input of a fusion block Σ j | j=1..3 (Fig. 2), two parameters are associated :

i) a gain, respectively g ji | i=1..3 that represents the weight of the corresponding command i as :

i=1..3 g ji = 1 with : g ji | i=1..3 ∈ ]0 1[ (3)
ii) and a vector v ji which have : -as module the gain "g ji " -and as orientation "Ori i "

The output of the fusion block Σ j | j=1..3 is a command "command j (Ori j , Dis j )" given by this method : If Box-pushing, Repositioning, or Attraction to the box behaviors give their RR . Then the corresponding fusion block (respectively Σ 1 , Σ 2 or Σ 3 ) gives in output this RR which permit to not subsume behaviors and/or fusions blocks of lower levels. Else the command j is calculated as follows :

i) "Ori j " is the orientation of V j vector as in

V j = i=1..3 v ji . ( 4
)
ii)

and "Dis j " is defined as scalar summation as in

Dis j = i=1..3 (g ji • Dis i ). (5)

c) Interest of using fusion blocks:

The main motivations to use fusion blocks are to improve the pure subsumption architecture [START_REF] Adouane | Bio-inspired behaviours of a group of microrobots for cooperative box-pushing task[END_REF] and to avoid undesirable effects linked to the elevated number of mini-robots in interaction. The details of motivations are explained next :

For the fusion block "Σ 1 ", we have note that when minirobots push the box at the same time, their trajectories go inevitably intersect (Fig. 5). These effects occur because the mini-robots tend always to push towards the centre of the box. To avoid this, the idea is to remain active the Obstacles avoiding behavior during the activation of the Box-pushing behavior. This is done in order to maintain always a minimal distance between mini-robots. As for the contribution of altruistic signals (if it exists in the environment) to this fusion block, it consists to attract the mini-robots closer to the most suitable zone to push (i.e., where the angle θ of observation of the target and the box tends to zero). Because the minirobots which are closer to this point, broadcast more intense attractive signal which attract other mini-robots towards it. The fusion block "Σ 2 "makes so that the repositioning of mini-robot becomes more quickly towards the privileged zone (contribution of altruistic signals) while avoiding other mini-robots in the immediate surrounding of the box (contribution of Obstacles avoiding behavior).

The fusion block "Σ 3 " is linked directly to the behavior of Attraction to the box. The main contribution of the Obstacles avoiding behavior consists in preventing that the mini-robots would be one behind the other (Fig. 6(a)) which stops them thus to interact directly with the box.

IV. SIMULATIONS

To estimate the relevance of the proposed control architecture, and to observe the importance of altruistic signals on the realization of a cooperative BPT (where the mini-robots are always in very strong interaction), we developed a simulator called MiRoCo (Fig. 7) to realize a very large number of simulations (some thousands) in order to make statistical studies. The criteria chosen to verify the relevance of the control architecture, is the evolution of time of execution of the BPT according to :

-the number of mini-robots N, -the minimal number of robots to displace the box Nc, -the use or not of altruistic signals.

A. MiRoCo simulator

MiRoCo (Mini-Robotics Collective) simulator (Fig. 7) developed in the LAB 2 is dedicated in general to the cooperative mobile robotics. The MFC 3 of Visual C++ has been used as support to the implantation of MiRoCo. It is based therefore on oriented object architecture in which are defined separately all entities constituting the environment (robots, box to push, obstacles, target, model of displacement of the box...etc.). The interaction of all entities is very accurate, so it allows us therefore to have reliable simulations. The display aspect is managed completely by using the OpenGL 4 graphic library. This gives us a very good indications about the dynamic of interactions of all entities.

B. Organisation of the sets of simulations

We achieve two sets of simulations with the proposed control architecture (Fig. 2), those with altruistic signals and those without. For each set of simulations, we proceed as 2 Laboratoire d'Automatique de Besançon 3 Microsoft Foundation Class Library 4 Open Graphics Library

With sign(θ) is the representative function of the algebraic sign of θ.

The gains of the fusion blocks are empirically obtained while following the expected behaviors of mini-robots considered in section "Interest of using fusion blocks".

-Σ 1 : g 11 = 0.50, g 12 = 0.40, g 13 = 0.10 -Σ 2 : g 21 = 0.50, g 22 = 0.45, g 23 = 0.05 -Σ 3 : g 31 = 0.20, g 32 = 0.16, g 33 = 0.64 With : g 11 , g 21 , g 31 are gains of commands corresponding respectively to Box-pushing, Repositioning and Attraction to the box behaviors, g 12 , g 22 , g 32 correspond to Obstacles avoiding behavior and g 13 , g 23 , g 33 correspond to Altruistic signals answers behavior.

These simulations allow us to observe following tendencies : Fig. 8(a) and Fig. 8(b), shows that the time of execution of BPT decreases when the number N of mini-robots increases, however this time increases when Nc increases. We note also the existence of an optimal number N * of minirobots to complete the BPT, beyond it there is not (or very little) enhancement of the time of execution. We see also that Fig. 8(b) is smoother than Fig. 8(a). This shows that the use of low-level of communication (attractive and/or repulsive signals) give to the cooperative task more coordination, and robustness of interactions between mini-robots. The proposed hybrid control architecture is very efficient to the realization of complex cooperative task like the one of the box-pushing which requires big interaction between a lot of mini-robots. We could note also the importance of the broadcasting of simple altruistic signals for the improvement of the BPT in term of time to complete the task. To summarize, the proposed reactive control remains extremely interesting seeing its intuitive aspect, robustness and flexibility for the resolution of complex tasks as for the BPT.

The future works are going firstly to implement the proposed hybrid architecture on the mini-robots ALICE, in order to test the efficiency of this hybrid control architecture in real situations. Secondly, knowing the multitude of parameters to be fixed, we will proceed by learning to determine the optimal parameters of control.

Fig. 1

 1 Fig. 1 ALICE mini-robot

1 )

 1 Elementary behaviors: a) Exploration behavior: This behavior sends commands to the motors according to predetermined constant coefficients of the occurrence probability of each command. b) Obstacles avoiding behavior: This behavior uses the infrared sensors only in all or nothing mode (boolean). It consists therefore in avoiding the obstacles according to a pre-established strategy giving the response according to the sixteen possible stimuli of the infrared sensors. c) Attraction to the Box behavior: This behavior consists in attracting the mini-robot towards the box, which broadcasts light. This is performed using the mini-robots infrared sensors just in reception mode. The commands sent to the motors depend then on the values read on the four infrared sensors. d) Alignment behavior: This behavior consists of insuring that the mini-robot is aligned with B before activating the behaviors of Box-pushing or the one of Repositioning. The idea is to control the relative angle that the mini-robot makes with B, to be inside the interval [-η˚, η˚].

Fig. 2 Fig. 3

 23 Fig. 2 Control based hybrid architecture

Fig. 4 Attractive and repulsive signals 2 )

 42 Fig. 4 Attractive and repulsive signals

Fig. 5

 5 Fig. 5 Observed effect without using Obstacles avoiding behavior when mini-robots push the box

Fig. 6 .Fig. 6

 66 Fig. 6. Influence of the gain of obstacles avoiding behaviour in the fusion block 3

Fig. 7

 7 Fig. 7 MiRoCo simulator

Fig. 8 Fig. 9 ,

 89 Fig. 8 Evolution of the number of iterations according to N and Nc

Fig. 9

 9 Fig. 9 Gain of time brought by altruistic signals