Oussama Moslah
email: oussama.moslah@enit.rnu.tn

Yassine Hacha Ïchi
email: yassine.hachaichi@ipeiem.rnu.tn

Younes Lahbib
email: younes.lahbib@enicarthage.rnu.tn

Democratic Inspired Particle Swarm Optimization for Multi-Robot Exploration Task

Keywords: Swarm robotic, Multi-robot system, mobile robotics, collective exploration, SLAM, Particle Swarm Optimisation

In this paper, we propose a new method for exploring an unknown environment with a team of homogeneous mobile robots. The goal of our approach is to minimize the exploration time. The challenge in multi-robot exploration is how to develop distributed algorithm to govern the colony of robots while choosing its new direction so that they simultaneously explore different regions. In this paper we use the extended version of Particle Swarm Optimization (PSO) to robotic applications, which is referred to as Robotic Particle Swarm Optimization (RPSO), a technique to compute robots new location. To better adapt this technique to the collective exploration problem, and maximize the exploring area, we propose a new method for computing PSO's global best parameter. Experiment results obtained in a simulated environment show that our new method of computing PSO's global best parameter increases the explored area with a shorter time convergence.

Introduction

The exploration and mapping of an unknown environment, which is also defined as simultanius localization and mapping (SLAM), is a fundamental problem for mobile robots and multi-robot systems. Many applications such as rescue [1,[START_REF] Couceiro | A collective robotic architecture in search and rescue scenarios[END_REF] mowing [START_REF] Huang | Automatic operation for a robot lawn mower[END_REF] and cleaning [START_REF] Sugiyama | Autonomous strategy determination with learning of environments in multi-agent continuous cleaning[END_REF] require full coverage of the environment,its center of gravity, and also the sides, in the fastest time possible (especially in rescue operations).

Explore an environment using several robots instead of one is much more advantageous. But in order to avoid the exploration of the same surface multiple times, or by more than one robot, there is a need to develop a movement strategy which allows the robots to coordinate their movements, and without the use of a centralized control unit.

In the collective exploration of an unknown space, each robot must: maintain communication with other robots to share the progress and the discovered surface over a period T, detect and distinguish between obstacles and free space, avoid obstacles when moving, and choose the best path where a robot can move to discover a maximum space that hasnt been discovered yet.

Particle Swarm Optimization (PSO) is one of the techniques used for collective exploration of swarm robotic 25 systems which abides by those requirements. PSO is an optimization technique developed by James Kennedy and Russell Eberhart in 1995 [START_REF] Eberhart | A new optimizer using particle swarm theory[END_REF] that models a set of potential solutions to a particle moving in the space search. The aim of this method is to be suitable for multi-robot appli-30 cations, improvement has been made to take into account the real world environmental constraints.

In this paper, in order to develop our strategy to govern the whole colony of heterogeneous robots, we propose a method inspired from Particle Swarm Optimization. We 35 adapt it to the exploration task. Our idea is to control the robots in order to explore the space on two steps: in the first, they try to converge to their center of gravity to explore it, which is probably the center of the space to explore. While in the second step, robots will carry on to 40 explore the sides. This way, we will have the map of the entire space.

With the aim of exploring the space in two steps as explained above, we have changed the way of calculating the global best solution of the PSO (it will be detailed 45 in the section 4) in order to calculate it by taking into account all local optima of the colony, not only the best performing candidate.

This paper is organized as follows. In section 2, we will discuss related works. Section 3 presents the theo-50 retical background of the PSO and its application in the multi-robot field RPSO, in section 4 we will introduce our theoretic approach to help robots decision in motion coordinated exploration with mobile robots. Section 5 presents series of experiments which are carried out in simulations and results. Finally, we discuss the results and use cases in Section 6.

Related works

The multi-robotic exploration, instead of one, is nowadays an advantageous approach which has several known implementation techniques. These techniques can be classified into three categories: techniques in which the robots move randomly, techniques that require planning the movements of robots in advance, and techniques in which robots do not plan their trips in advance, but they coordinate with each other.

Techniques where robots move randomly: In order to explore an unknown environment, the author in [START_REF] Konolige | Distributed multi-robot exploration and mapping[END_REF] focuses on the relative location between robots and random robots exploration. The goal is to generate a collective map of the explored area. The system works as follows. Initially, robots might not know their relative positions. In such a case, each robot explores on its own map. The explored portion increases in the robots memory until two robots can communicate. In this case, they begin exchanging data and estimating their relative location. Once they have a good hypothesis for their relative location, they actively verify this hypothesis using a rendezvous technique. If successful, the robots form an exploration map, they combine their data in a shared map and begin to coordinate their exploration activities. On the other hand, if the assumption of relative location proves to be false, robots continue to explore independently and exchange data in order to refine their estimations of relative location. During the exploration, the size of the explored map increases more and more when a new robot can determine its relative position.

Another approach was presented in [START_REF] Burgard | Coordinated multi-robot exploration[END_REF], in which authors represent the environment as a matrix of pixels (occupancy grid maps). They define discovered pixels that have undiscovered adjacent pixels as frontier pixels. After detecting frontier pixels, the algorithm considers the possibility to send a robot to a pixel by calculating the cost of moving the robot to each pixel and estimating the utility of the pixel. The cost of moving is proportional to the distance between the robot and the pixel. On the other hand, the utility of the pixel depends on the number of robots that move towards that pixel or at a nearby location.

Keeping in mind that the robots moves randomly, algorithms based on one of those techniques, will takes more time especially when the map is quite complex and big compared with the number of robot. Contrarily with our approach, in which the robots movement is coordinated, enables us to optimize the time of exploration.

Techniques that require planning of the robots movement in advance: Generally divide the environment into regions, and affect a robot to every region in order to explore all regions. One of those methods, allowing the division of the environment to regions, is the Voronoi diagram [START_REF] Choset | Sensor-based exploration: The hierarchical generalized voronoi graph[END_REF]. It is a distribution of the map to 110 regions based on the distance between a point and a reference. The reference can be a robot or an obstacle, it depends on the application. In each region, each point is closer to the robot (or obstacle) in which the region is affected than others.

115

In reference [START_REF] Yang | Self-organized swarm robot for target search and trapping inspired by bacterial chemotaxis[END_REF] authors propose a method for the detection and trapping of an object / target using algorithms inspired by the bacterial chemotaxis (BC). They followed four main steps: the first step is the establishment of a coordination system between robots [START_REF] Guo | A morphogenetic framework for selforganized multirobot pattern formation and boundary coverage[END_REF], this step con-120 sists of choosing a robot of the colony as a location reference. Then, the positions of the other robots (or any point in the area) will be determined based on their distances from the reference robot. The second step is to build the Voronoi diagram [START_REF] Choset | Sensor-based exploration: The hierarchical generalized voronoi graph[END_REF]. Step 3 is the target research phase 125 (victim, terror ...). In this step each robot is looking for the target in its region using the algorithm imitating BC. In step 4 robots surround targets detected in step 3 using the same algorithm (BC). In order to solve the problem of distributed control of the colony, each robot moves in 130 the search space by imitating the movement mechanism of BCs. While moving, a bacterium seeks to find a maximum concentration of nutrient. The main steps of the BC algorithm are:

• Put to the target position a large concentration of 135 nutrient.

• Calculate the new direction of the bacteria.

• The bacterium moves in its direction previously calculated in order to go forward to the target.

• The nutrient concentration in a pixel decreases when-140 ever the bacterium finds it.

Similar work has been introduced in [START_REF] Wurm | Coordinated multirobot exploration using a segmentation of the environment[END_REF] in which authors presented their approach to the inspection of an environment which know its map previously. The algorithm is summarized in the following steps: • Define regions to be inspected by the robot using the Voronoi diagram.

• Identify the frontiers cells to be traveled by the robots.

• Calculating the cost of moving each robot to each frontier cell.

150

• Associate each robot to a frontier cells using the Hungarian method [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF].

• Finally, repeat the assignment of robots to frontiers until travel up all frontiers.

In [START_REF] Arezoumand | Finding objects with segmentation strategy based multi robot exploration in unknown environment[END_REF] the authors also divided the map into regions, but 155 they divided it into equal rectangular segments. At first they affect robots to segments randomly. When two robots meet, they exchange research results. Then each robot changes its direction to the least explored segment. Opposed to our exploration approach of an unknown environment, these approaches require prior knowledge of the research area so that they can divide it into segments. In addition, the decomposition of the field is done at a single computer (or central control or leader robot). Therefore, the malfunction of the calculator will lead to the stopping of all robots. Also, robots are not synchronized as in our approach. In other hand, robot's motion doesn't depend on status/position of other robots, so, the robot's motion, while exploring, isn't fully coordinated.

Techniques where robots do not plan their trips in advance: As in our approach, robots recalculate their new direction in each iteration based on the surroundings and other robots. Using these methods, robots seem more coordinated than using others previously presented.

In [START_REF] Couceiro | A novel multi-robot exploration approach based on particle swarm optimization algorithms[END_REF] authors implemented an extended version of Particle Swarm Optimization (PSO) [START_REF] Eberhart | A new optimizer using particle swarm theory[END_REF] which is an algorithm inspired by the movement of birds in search of food. This version is called Robotic Darwin Particle Swarm Optimization (RDPSO). In which, authors have implemented two key ideas in PSO:

1. Adapt PSO to robotic applications RPSO, in which they added two vectors, the first vector allows the robot to avoid obstacles, and the second vector allows maintaining communication between all the robots. 2. In the second idea, they used the Darwinian punishment and reward mechanism (DPSO). It divides the colony in sub-colonies, the algorithm punished the sub-colony that is not improved by subtracting the least performing robot, and rewards sub-colony which improves by adding a robot from the excluded 190 ones. This mechanism allows the colony to avoid being trapped in sub-optimal solutions. Other works inspired by the behavior of social insects and animals have been compared in [START_REF] Couceiro | Benchmark of swarm robotics distributed techniques in a search task[END_REF]. Authors have compared five algorithms implemented in the problem of explo-195 ration. In their article, they compared the RDPSO with the Extended PSO (EPSO) [START_REF] Pugh | Inspiring and modeling multi-robot search with particle swarm optimization[END_REF] and Physically-embedded PSO (PPSO) [START_REF] Hereford | Bio-inspired search strategies for robot swarms[END_REF], which are three algorithms inspired from the PSO. And they compared them with Glowworm Swarm Optimization (GSO) [START_REF] Krishnanand | Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions[END_REF] and Aggregation of For-200 aging Swarm (AFS) [START_REF] Gazi | Stability analysis of social foraging swarms[END_REF].

EPSO is one of the first extended versions of PSO adapted to the constraints of the real world. The main idea in the EPSO is that each robot only considers the robots within the limits of its communication area. After 205 calculating the motion vector, authors use the Braitenberg [START_REF] Braitenberg | Vehicles: Experiments in synthetic psychology[END_REF] obstacle avoidance algorithm.

In PPSO, like RDPSO, there is no central agent for coordinating the movements or actions of robots. The algorithm also requires full synchronization of robots. Robots can calculate their position only after all other robots exchange needed information (eg, individual solutions). Also, a robot does not share its position if its own solution isnt the best solution throughout the colony. This reduces communication traffic. However, it is also neces-215 sary that the robots are stopped after each iteration to process all relevant information. In addition, the collision avoidance behavior was not considered in the equation of the algorithm. Unlike the approach that we adopted where avoidance collusion and obstacle are taken into account 220 when calculating the displacement. Instead of that, when a robot will be trapped (or gets stuck), it moves back and turns right.

GSO is an algorithm inspired by the behavior of Glowworm. Where each robot (Glowworm) chooses a nearby 225 robot and goes toward him. The robot which has the greater brightness value (luciferin) has the highest probability of being chosen as the robot to what its neighbors are heading. The brightness value is completely proportional to the relevance of the solution found by the robot. This 230 will lead to divide the colony of robots into sub-colonies. Each colony has a sub-leader. All robots in the same subcolony will diverge to the same point/solution (to their leader), and explores in his neighborhood. The problem here is that all the robots of the same sub-colony will ex-235 plore the same surface. This is the same problem using RDPSO. Maybe in other tasks, such as finding food, will be a good idea to split the colony into sub-colonies. Unlike our approach, which is more suited to the exploration problem. The authors also used a low obstacle avoidance 240 mechanism.

In AFS, robots move following attractive and repulsive forces between robots. The force of attraction dominates over long distances, and the force of repulsion dominates over short distances. In this approach, the authors con-245 sider obstacles as a part of the objective function of the colony. In other words, if the robots need to maximize a given measure, for example, find the highest density of victims in a disaster site, the obstacles are considered global minima of their objective function.

250

The results of comparison made in [START_REF] Couceiro | Benchmark of swarm robotics distributed techniques in a search task[END_REF] show a better result in terms of percentage exploration using RDPSO in any configuration (number of robot, communication distance). On the other side, in the problem of collective exploration, the global optimum notion is not completely 255 true. In fact, a site that has been explored at time t is not a solution for the time t + 1. So the use of the Darwinian principle has no great influence on the operation of the algorithm.

Our approach extends the Robotic Particle Swarm Op-260 timization idea in order to generate a faster exploration algorithm. In contrast to [START_REF] Konolige | Distributed multi-robot exploration and mapping[END_REF] and [START_REF] Burgard | Coordinated multi-robot exploration[END_REF] in our method, robots dont move in the search space randomly, but they choose their new directions in order to move to the less discovered area. Also, in contrast to [START_REF] Yang | Self-organized swarm robot for target search and trapping inspired by bacterial chemotaxis[END_REF], [START_REF] Wurm | Coordinated multirobot exploration using a segmentation of the environment[END_REF] and [START_REF] Arezoumand | Finding objects with segmentation strategy based multi robot exploration in unknown environment[END_REF], our ap-

265
proach doesnt require any prerequisites information about the map shape or size. This makes our approach more flexible and easier to implement in all shapes of maps. However, similar to [START_REF] Couceiro | A novel multi-robot exploration approach based on particle swarm optimization algorithms[END_REF], [START_REF] Pugh | Inspiring and modeling multi-robot search with particle swarm optimization[END_REF], [START_REF] Hereford | Bio-inspired search strategies for robot swarms[END_REF], [START_REF] Krishnanand | Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions[END_REF] and [START_REF] Gazi | Stability analysis of social foraging swarms[END_REF], algorithms using our approach dont need any prerequisites knowledge of the area, and the decision making is fully decentralized. But comparison results presented in [START_REF] Couceiro | Benchmark of swarm robotics distributed techniques in a search task[END_REF] shows a better result found using RDPSO presented in [START_REF] Couceiro | A novel multi-robot exploration approach based on particle swarm optimization algorithms[END_REF]. In this paper we will present an extended version of PSO that democratizes the colony while choosing their new directions.

Experimental results show a faster exploration using our method.

PSO and RPSO: Theoretical background

This section is organized as follows: first we will introduce the PSO technique, and then we will discuss its main variants, after that we will introduce its extended version to the multi-robot applications as presented in [START_REF] Couceiro | A novel multi-robot exploration approach based on particle swarm optimization algorithms[END_REF].

Particle Swarm Optimization

Particle Swarm Optimization is a stochastic method inspired by le behavior of the flocking of the bird, it has been developed by Dr. Kennedy and Dr. Eberhart in 1995 [START_REF] Eberhart | A new optimizer using particle swarm theory[END_REF]. The system is initialized with a population of random particles. Each particle is a potential solution, moves in the search space in order to find the optimal solution. A particle is characterized by its position (Pos) and its objective function (OF), and which moves into the search space by following:

• The local optimal solution in its knowledge, minimizing or maximizing its objective function;

• The global optimal solution, which is the best solution between local optima of the whole colony;

• Without completely changing its direction.

In every optimization step, each particle has to update its new solution through equations 1 and 2.

∆P os(t) = w.∆P os(t -1)

+r l .w l .(P os lBest -P os(t -1)) +r g .w g .(P os gBest -P os(t -1))

P os(t) = P os(t -1) + ∆P os(t)

Wherein P os(t) is the desired position, ∆P os(t) the velocity of the particle, P os lBest the optimal solution in its local knowledge (Local Best), P os gBest the global optimal solution (Global Best) in the swarm knowledge (thats doesnt mean the best solution can be found), coefficient w, w l and w g are the assigned weights to the inertia influence, local optimum solution and global swarm optimum solution respectively, t is the time (or iteration number) r l and r g are random vectors between 0 and 1. PSO is a computing method, which allows iteratively the growth of the results of potential solution in order to optimize a problem. The evaluation of the convergence of the optimization problem to a solution is through an objective function which reflects the result of the potential solution.

The idea of our approach is to suggest a new method to calculate the position of the global optimum P os gBest , which is more adapted to the collective exploration problem of multi-robot system, a detailed explanation of the classic method (classic Robotic PSO) and our new method 320 (Democratic Robotic PSO) will be presented in the following sections.

Particle swarm optimizations variant and extended version

Since the first appearance of the PSO, and due to its 325 effectiveness and simplicity in implementation, it has been applied in many optimization problems such as power system [START_REF] Sharafi | Multi-objective optimal design of hybrid renewable energy systems using pso-simulation based approach[END_REF], Robotics [START_REF] Das | A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning[END_REF] [23], transportation [START_REF] Zeng | Antithetic method-based particle swarm optimization for a queuing network problem with fuzzy data in concrete transportation systems[END_REF][START_REF] Validi | Integrated low-carbon distribution system for the demand side of a product distribution supply chain: a doe-guided mopso optimiser-based solution approach[END_REF], data clustering [START_REF] Alam | Analysis of particle swarm optimization based hierarchical data clustering approaches[END_REF] and electronics [START_REF] Sahu | Application 710 mapping onto mesh-based network-on-chip using discrete particle swarm optimization, Very Large Scale Integration[END_REF]. This has led to the development of many variant in order to adapt it in deferent 330 field.

In [START_REF] Rini | Particle swarm optimization: technique, system and challenges[END_REF] authors reviewed diferent studies focusing on PSO, advantages and disadvantages, the basic variants, modifications and applications that have implemented using PSO. They divided the deferent versions of PSO into 335 two groups: Basic Variants, and Modifications. Basic Variants are influenced by the PSO control parameters such as dimension of the search space, number of particles, acceleration coefficients. The modification in PSO consists of three categories: extension of field searching space, adjust-340 ment the parameters, and hybrid with another technique.

In this paper, we will adjust the global best parameter, in order to adapt the extended version of PSO, called RPSO, to the multi-robot exploration problem.

Robotic Particle Swarm Optimization

345

PSO technique has been extended to multi robot system application [START_REF] Couceiro | A novel multi-robot exploration approach based on particle swarm optimization algorithms[END_REF]and referred to as Robotic Particle Swarm Optimization (RPSO), in addition to the PSO parameters, RPSO takes into account real-world constraints to avoid obstacles and keep robots at a convenient dis-350 tance to maintain communication between them without interfering with each other.

In every optimization step, each robot has to update its new position through equations 3 and 2.

∆P os(t) =

w.∆P os(t -1) Wherein P os obs the optimal solution that allows the 355 robot to avoid obstacles, P os Comm is the optimal solution that permits the robot to keep communication with other robots within the swarm, coefficient w obs and w Comm are the assigned weights to the avoidance obstacle component and maintaining communication component, r obs and 360 r Comm are random vectors between 0 and 1.

An illustration of the influence of the parameters in the final velocity of the robot can be seen in Figure 1.In which the robot is represented by a blue triangle, a half circle represents its limit of detection, the optimal solution is shown in green and an obstacle is schematized as black rectangle. • V1 which is w. ∆P os(t-1), represents the old veloc-370 ity at time t -1 robot. Weighted by w to increase or decrease the importance of this vector. This vector is used to keep the robot loyal to its previously made choices.

• V2 which is r l .w l .(P os lBest -P os(t -1)), represents 375 the cognitive vector. Weighted by w l which is used to increase or decrease the importance of this vector, and a random number r l which give it a stochastic aspects. This vector is used to drive the robot toward to the position maximizing its objective func-380 tion from its own local knowledge.

• V3 which is r g .w g .(P os gBest -P os(t -1)), represents the global knowledge vector. Similar to V2, it is weighted by w g and a random number r g . This vector is used to drive the robot toward to the position maximizing its objective function from global robots knowledge.

• V4 which is r obs .w obs .(P os obs -P os(t -1)), represents the avoidance obstacle vector. Similar to V2, it is weighted by w obs and a random number r obs .

This vector is used to drive the robot far from obstacle based on its own local sensing.

• V5 which is r Comm .w Comm .(P os Comm -P os(t -1)), represents the maintaining communication vector. Similar to V2, it is weighted by w comm and a random 395 number r comm . This vector is used to keep the robot at convenient distance in order to maintain communication between all robots within the swarm.

• V6 which is ∆P os(t), represents the new robot's velocity. It's computed by the of V1, V2, V3, V4 and 400 V5.

In the following section, we present our proposed modification in the RPSO's global best solution in order to help robots to chose it in a democratic way.

Democratic Robotic Particle Swarm Optimiza-

tion

In order to adapt the RPSO to the multi-robot exploration problem, in this section, we propose a new method which calculates the position of the global best solution in democratic way.

410

Even if democratizing the swarm isn't a new idea, the way how democratizing it makes the difference. In [START_REF] Burman | Democracy-inspired particle swarm optimizer with the concept of peer groups[END_REF] authors introduced Democracy-inspired Particle Swarm Optimization with concept of Peer Group (DPG-PSO), which integrate the PSO with the concept of governance in hu-415 man society. In DPG-PSO, population has a governor which represents the global best solution, and an opposition which takes certain properties from the governor and some are random. Instead of being influenced by only the global best solution, in DPG-PSO each particle has the 420 choice to vote to the governor or its opposition to lead the group while in our approach all particles (even the worst) participate in choosing the global best solution not a leader to follow.

An older attempt to democratize the swarm has been

425

introduced as Democratic PSO (DPSO) [START_REF] Kaveh | Democratic pso for truss layout and size 720 optimization with frequency constraints[END_REF] which uses an extra term in the velocity update equation. The extra term represents a global best solution, in which all particles, like our method, participate in the choosing process. While in our approach, no extra term has been used but the voted 430 global best solution replace the P os gBest solution in the equation 3, also the computing process is not the same.

Description of our proposed approach

Usually, in the PSO the global optimum solution, as described in the equation 4, is the best solution between 435 local optima of all the particles has ever discovered [START_REF] Eberhart | A new optimizer using particle swarm theory[END_REF] :

P os gBest = M ax(P os lBest (i, T )); ∀i ∈ (1, N ); ∀T ∈ (0, t)(4)
With P os lBest (i, T ), as described before, is the local best solution of the i th particle from the N particles, in any time T from the beginning of the optimization until the 440 current time t. This will guide all particles to the same solution imposed by a single particle (the most efficient), which is not always necessarily the best existing solution.

SLAM is not used to be an optimization problem, because a solution which has been discovered in any time T 445 (which represent the size of the new discovered area) would not be anymore a solution for any time t > T . So the PSO used as source of inspiration, and the update role of the global best solution has been changed in order adapt it to the multi-robot exploration problem.

In our work we have democratized the swarm. The global optimum solution is calculated according to all local optimums multiplied by their objective functions as follows (equation 5):

P os gBest = N i=1 (OF (i) * P os lBest (i)) N * M oy(OF ) (5)
455 Wherein P os lBest(i) and OF (i) the local best solution (position) and the objective function value of particle i respectively, N is the number of particles within the swarm, and M oy(OF ) is the average value of the objective function in the whole colony.

In the collective exploration problem, the objective is to maximize the explored surface, hence, the objective function OF (i) depends only on the explored area by the i th robot at a time t.

The same equation of P os gBest is also as follows 6:

465 P os gBest = N i=1 (OF (i) * P os lBest (i)) N i=1 OF (i) (6)
This approach will guide all particles toward a middle point (center of gravity). It will influence robots to discover the center of the map without discovering the sides (as shown in figure 2). For this reason, as describes equa-Figure 2: Explored area after 1000 iteration using Democratic RPSO with fixed weights(in the same map used in [START_REF] Couceiro | A novel multi-robot exploration approach based on particle swarm optimization algorithms[END_REF]).

tion 7 we changed the value of the weight of the social component of PSO w g (which is, in most cases, a fixed value), in a way that guide robots to discover their center of gravity firstly, and, secondly the corners of the map (as shown in figure 3). To do so, g BestV alue (which is the average value of objective functions of all robots) was compared with a threshold value g bestV alueT hreshold , which is the value that decides when to switch from the first part to the second, and was divided by the maximum value that can take g BestV alue and then, multiply it by the classic weight value that should take w gStandard /w gClassic .

w g = g BestV alue -g bestV alueT hreshold M axg BestV alue * w gClassic [START_REF] Burgard | Coordinated multi-robot exploration[END_REF] But, this will limit the value of w g between -g bestV alueT hreshold M axg BestV alue * w gClassic In this way, the robot will be penalized by decreasing its step of advancement (which is strongly connected to the sum of weight assigned to different RPSOs variables). To 485 adjust this limitation we, also, modified w l (the cognitive vectors weight) as described equation 8.

w l = w lClassic + w gClassic -abs(w g ) (8)
with abs(w g ) is the absolute value of w g . Thus the exploration is carried out in two steps, 490 1. When the value of w g is positive, robots will tend to converge on the center of their gravity. This will helps the colony to explore their center of gravity, which is the center of the work map. 2. And when the value of w g is negative, robots will 495 tend to diverge far from the center of their gravity. This will helps the colony to explore the sides of the work map.

When the value of w g is equal to zero, each robot will compute its new position without taking in consideration 500 the social component.

DRPSO algorithm

As algorithm 1 describes, the steps of execution are listed below:

First, initialize local best position, global best posi-505 tion, the best position allows the robot to avoid obstacles and the best position allows the robot to maintain communication with other robots in its own position. Second, initialize all the cells of the map on the robots memory as unknown cells. After that, the robot repeats the following 510 step in each iteration until a stopping criterion:

1. Read data from sensors and update the map in the robots memory.

Compute :

• The new fitness value (ObjectiveF unction) of 515 the robot. Which is the number of new discovered cells.

• The local best position according to the concentration of the new discovered cells. End.

• The avoidance obstacles position, which is the symmetrical position of the obstacle relative to the robot. In other words, it is the position which allows the robot to move far away from obstacles.

+

OF (i) * P os lBest (i) (N -1)gBest V alue +1+OF (i) gBest V alue = (N -1)gBest V alue + OF (i) N (10)
6. Compute w g and w l according to equations 7 and 8. 7. Compute Pos(t) according to equation 3. 8. move to the new position Pos(t+1) using equation

Experimental result

In this part we will present an evaluation of the results of two simulations, in the first simulation, we used the RDPSO [START_REF] Couceiro | A novel multi-robot exploration approach based on particle swarm optimization algorithms[END_REF] (with P os gBest is the best solution between 545 local optima), which is, according to [START_REF] Couceiro | Benchmark of swarm robotics distributed techniques in a search task[END_REF], the most efficient algorithm. In the second simulation, we used the new method of calculating P os gBest , which we named Democratic RPSO.

In this experiment, simulations are conducted only in 550 software simulation platform, real word constrains has not been tackled. For a real robots simulation, the problems of localization and noisy sensor inputs make a huge barrier for this purpose.

In order to ensure the loyalty of the simulation result,

555

we simulated the two methods 20 times and calculated the average values of each method. Each simulation lasted 1480 iterations. Both simulations were run on the same map with the same initial conditions and on the same simulation platform MRSim (Multi-Robot Simulator), which 560 is an extension of the Autonomous mobile robotics toolbox SIMROBOT developed for MatLab [START_REF] Couceiro | A collective robotic architecture in search and rescue scenarios[END_REF].

The constants parameters used in simulations are the following : The assigned weights to the inertia influence w = 0.6 ; The assigned weights to the local optimum so-565 lution w l = (0.42 in the RDPSO algorithm, and is calculated using equation 8 in the Democratic RPSO) ; The assigned weights to the global optimum solution w g = (0.42 in the RDPSO algorithm, and is calculated using equation 7 in the Democratic RPSO) ; The assigned weights In these simulations, we used a colony which was formed by 10 simulation models of homogeneous robots, equipped with a laser scanner. The evaluation criterion is the area covered by the colony during a period of time T (or af-585 ter number of iteration). Table 1 presents a percentage of the explored surface compared to the total area of the environment of the two methods each 40 iterations, and a comparison between the two methods.

Table 1 shows an advantage of the new method of 590 calculating P os gBest (Democratic RPSO) all along the exploration operation. An advantage of 13.11% of the discovered area of the total environment after 360 iterations has been shown, which would translate into faster response times in a rescue operation.

595

Figure 4 shows the progress state (discovered area) of the two methods during the exploration time (based on the number of iteration). We can see the benefits of our new method throughout curves in figure 4, the simulation result of the RDPSO method is shown in red color, and 600 the result of the our new method of computing P os gBest is represented in the blue curve. As shown in Figure 4 the new method allows us to discover near 75% of the card after 320 iterations, against 480 iterations for the RDPSO method, making it a benefit 605 of 160 iterations.

On the first steps (before 160 iterations) of the simulation there is no big difference between the two simulations, because the whole map has not been explored yet, and in each direction the robot chooses to move, it will discover 610 a new area.

In the last iterations (after 840 iterations) both methods will end up discovering the whole map.

Conclusion

This paper presents a new method of calculating the 615 global best parameter of the PSO technique to better adapt to the problem of collective exploration of an unknown environment. The idea of our method is to democratize the colony when selecting the global optimum solution.

Simulations in a virtual environment have been made,

620
showing the benefit of our method. Democratizing the colony saves the time (iterations) in the problems that have a variable global optimum (e.g. exploration, foraging, cleaning) but not necessarily in the problem with a fixed global optimum (e.g. solving a math-625 ematical equation).

For future work, we will implement the democratic RPSO algorithm on physical robots in order to verify its performance in the real world constraints.

Acknowledgment

These research and innovation are carried out as part of a MOBIDOC thesis financed by the EU in the program PASRI.

  145

Figure 1 :

 1 Figure 1: Robot position's updating Vectors V1, V2, V3, V4, V5 and V6 shown in Figure1 represent respectively :

Figure 3 :

 3 Figure3: Explored area after 1000 iteration using Democratic RPSO with changed weights (in the same map used in[START_REF] Couceiro | A novel multi-robot exploration approach based on particle swarm optimization algorithms[END_REF]).

570

  to the avoidance obstacle component w obs = 0.18 ; The assigned weights to the maintaining communication component w Comm = 0.4 ; The global best threshold value g bestV alueT hreshold = 90, which is the average value that could take ; The classic weight value of the global solu-575 tion and the local solution are w gClassic = w lClassic = 0.42 are the same used in the RDPSO algorithm ; The maximum number of free cells that a robot can sens in our simulation experiments is M axg BestV alue = 210. Parameters presented here are obtained empirically without 580 giving benefit to an algorithm against other.

Figure 4 :

 4 Figure 4: Discovered area using RDPSO and Democratic RPSO.

  Algorithm 1: DRPSO algorithm Initialize P os lBest , P os gBest , P os obs and P os Comm as own position. Update OF , P os lBest and P os obs . 3. Update P os Comm . 4. Share P os lBest and OF with other robots of the swarm. 5. Read other robots P os lBest (i) and OF (i) compute P os gBest and g bestV alue . 6. Compute w g and w l . 7. Compute ∆P os(t). 8. Move to the new position P os(t + 1).

	Initialize the map in the robots memory as
	unknown.
	While stopping criteria (convergence/time) not
	satisfied.
	1. Read sensors.
	2.

  3. Update the position which allows the swarm to main-

	525
		tain communication. Each robot should maintain
		communication with the nearest neighbor robot that
		hasnt been chosen as nearest neighbor before.
		4. Share its own best position (P os lBest ) and fitness
	530	value (OF ) with other robots in the swarm.
		5. Read other robots local best position (P oslBest(i))
		and fitness value (OF (i)), and compute P os gBest
		according to the equation 9 and 10. With N is
		the number of the robots. This method calculates
	535	P os gBest with minimal iteration.
		P os gBest =	(N -1)gBest V alue * P os gBest (N -1)gBest V alue +1+OF (i)

Table 1 :

 1 Discovered space with RDPSO and Democratic RPSO

					100	Gap of 13.11% of discovered
								area at iteration 360
						90
						80
	Iter	RDPSO Democratic Dem RPSO RPSO -RPSO 29.06% 29.46% 0.40% 38.45% 39.51% 1.06% 46.27% 47.37% 1.09%	Discovered area [%]	30 40 50 60 70			Gap of 160 iteration to discover 75% of the area
		51.38%	54.15%	2.77%		20
		54.36%	60.36%	6.00%						Democratic RPSO
		56.82%	65.94%	9.12%		10				RDPSO
		59.50%	71.04%	11.54%
		62.30% 65.29% 68.60%	75.08% 78.40% 81.15%	12.78% 13.11% 12.55%		0	0	300	600 Iteration number 900	1200	1500
		71.91%	83.29%	11.38%
		75.04%	85.01%	9.98%
		78.16%	86.49%	8.33%
		80.91%	87.97%	7.06%
		83.56%	89.30%	5.74%
		86.03%	90.48%	4.45%
		88.04%	91.44%	3.39%
		89.73%	92.32%	2.60%
		91.51%	93.25%	1.74%
		93.02%	94.10%	1.09%
		94.22%	94.81%	0.60%
		95.05%	95.54%	0.49%
		95.64%	96.11%	0.46%
		96.18%	96.59%	0.41%
		96.66%	97.03%	0.37%
		97.17%	97.38%	0.21%
		97.60%	97.75%	0.15%
		98.07%	98.00%	-0.07%
		98.37%	98.20%	-0.17%
		98.56%	98.36%	-0.20%
		98.70%	98.46%	-0.24%
		98.82%	98.52%	-0.30%
		98.93%	98.61%	-0.31%
		99.03%	98.73%	-0.30%
		99.10%	98.82%	-0.28%
		99.16%	98.89%	-0.27%
		99.23%	98.93%	-0.29%