VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10
Swarm Optimization Approach
for Light Source Detection by Multi-robot System1
Hoang Anh Quy, Pham Minh Trien
VNU University of Engineering and Technology, 144 Xuan Thuy, Cau Giay, Hanoi, Vietnam
Abstract
Exploration and searching in unknown or hazardous environments using multi-robot systems (MRS) is among the principal topics in robotics. There have been numerous works on searching and detection of odor, fire or pollution sources. In this paper, a modified Particle Swarm Optimization Algorithm (PSO) was presented for MRS on detecting light sources, namely APSO. In the proposed algorithm, an integration of conventional PSO and Artificial Potential Field (APF) is employed to use swarm intelligence for space exploration and light source detection. The formulas for APSO velocities are based on those of PSO and APF. Furthermore, each particle is surrounded by an APF that forms repulsive force to prevent collision while the swarm is in operation. The simulation results of APSO in Matlab by various scenarios confirmed the reliability and efficiency of the proposed algorithm.
Received 04 December 2015, Revised 09 January 2016, Accepted 26 September 2016 Keywords: PSO, MRS, APF, APSO, light source detection.
1. Introduction*
Owing to their robustness to local optima, widespread coverage and high degree of accuracy, multi-robot systems (MRS) are highly efficient in the tasks of space exploration and searching in unknown environments. There have been numerous works in which MRS was used to detect fire, pollutant sources and odor sources [1, 2, 3].
Among a variety of potential algorithms to implement on MRS, Particle Swarm Optimization (PSO) has become a natural choice for MRS in searching tasks. PSO was first introduced by Russel Ebenhart and James Kennedy in 1995 [4] and has gained popularity among bio-inspired heuristic algorithms
_______
1 This work is dedicated to the 20th Anniversary of the IT Faculty of VNU-UET
* Corresponding author. E-mail.: quyha@vnu.edu.vn
1
because of its efficiency, intuitiveness and simplicity. Motivated by social searching behavior of natural swarm, PSO is especially effective in optimization problems and widely applied in various fields. Searching tasks of MRS are in fact optimization problems, in which the robots attempt to locate the regions or spots of extreme signal intensity.
Although the idea of applying PSO to multi-robot search is not novel, many problems still need to be addressed adequately in order to put that idea into practice. Some of them are proneness to collision and premature convergence. Many of the related works are concerned with improving performance of the MRS. In [5], the authors concentrated on adjusting learning parameters for better results. In [6] the PSO algorithm was applied to model multi-robot search and the effects of system parameters were also evaluated. In [7], Doctor
2 H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10
et al. proposed a two PSO loops model to control their robot system. The inner loop was applied for collective robotic search and the outer was used to optimize quality parameters of the inner. In [8], Cai et. al. proposed a potential field-based PSO algorithm for cooperative multi-robots in target searching tasks. The problem of premature convergence, which may adversely affect performance of PSO, was addressed in [9], where Nakisa et. al. applied a method based on PSO and Local Search. In spite of various works on application of PSO for MRS in the tasks of exploration or searching in unknown environments, there has not been a standard approach with optimal result. All of the PSO-based algorithms still need further experiments and improvements.
In this paper, we present another approach and a specific application: detecting light sources or in other words, searching for the brightest region in a search space. This method is then compared with one of those mentioned above. In our simulations, an MRS is successfully used to detect light sources (by gathering all the swarm robots around the area of highest luminance in the search space). In all scenarios, each robot (or particle as described in PSO) has to move towards the mutual target and meanwhile avoid obstacles. For the robot swarm to exhibit this behavior, we modified PSO algorithm by associating each particle with an artificial potential field (APF) that can exert repulsive forces to any other particle if their distance is less than a predetermined value called repulsive radius. This method of avoiding collisions is inspired by APF algorithm, which was proposed by Oussama Khatib in 1986 for single robot path planning [10]. APF is widely used nowadays in works on MRS that demonstrate the interaction between robots and obstacles in their work space [11]. The proposed PSO algorithm is named APSO, its details will be presented in the next sections. The simulation in Matlab shows reliable and promising results, which could be applied in various further applications such as dynamic
deployment of robotic systems, flame detection or optical wireless charging.
The methodology and simulation are discussed in detail in part 2, the results and discussions follow in part 3. Finally, part 4 concludes this paper with main conclusions and directions for further research.
2. Methodology and simulation
2.1. Methodology
2.1.1. Artificial Potential Field
The APF model is inspired by Artificial Physics with quadratic function, where the choice of coefficients is commensurate to the wireless sensor network of MRS. Myriads of architectures for APF have been developed in accordance with users’ definitions and specific tasks, e.g. deploying mobile sensor networks in unknown environment [12], controlling and coordinating a group of robots for cooperative manipulation tasks [13] or maintaining connectivity of mobile networks [14]. In any architecture, magnitude of the potential force existing around each robot is continuously updated based on information collected from its immediate surrounding environment and other robots via connection network. Therefore, APF is used to regulate the relation between robots in term of position. Potential force is categorized into two main groups: passive force and active force. Passive force is generated when robot emit signal and determine distance to neighboring robots or obstacles by the magnitude of reflected signal to avoid obstacle or remain relative position with other robots. The signal used in the application could be infrared, ultrasound, laser or camera [15]. On the contrary, active force is generated from external signals. These signals are usually emitted by other robots and transmitted via communication system [11]. In this research, APF is only utilized for the purpose of collision avoidance and only generates repulsive forces on other particles within repulsive region, as defined in this formula:
H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10 3
FAPFij = (Fmax – k ij2) ij (1) ij
where Fmax and k are predetermined constants to regulate the magnitude of potential force, FAPFij is the APF force exerted on robot i by robot j. rij is the end-to-end distance vector from robot j to robot i. rij is the module of rij.
Total force exerted on i-th robot of the system is:
N
FAPFi = FAPFij (2) j=1
where N is the number of robots, FAPFij is zero if i = j. The impact of FAPFi on overall velocity is controlled by Fmax and k. As Fmax increases, the particle is less likely to approach obstacles. In subsection 2.1.2, this will be discussed further.
2.1.2 APSO for MRS
The main contribution of this paper is to propose and evaluate the efficiency of APSO, a modified PSO algorithm. In this subsection, we briefly present principles of PSO and then explain APSO in detail.
In PSO, the swarm consists of homogeneous particles that can explore the search space collectively. During the exploration, the movement of a particle is controlled by a velocity comprised of three components: inertial, cognitive and social velocity. Cognitive velocity leads the particle towards its personal best position and social velocity leads the particle towards the global best. Inertial velocity guides each particle towards their previous directions and thus keeps particles’ movement smooth [16]. Besides, high inertial velocity and cognitive velocity at initial steps make the swarm discover search space better. The social learning factor should be increased and cognitive factor should be decreased throughout the exploration in order to enlarge the swarm’s coverage at initial steps and make it converge faster at final steps. The searching process using PSO is implemented in four stages: initializing, updating best positions, updating velocity and position, and finally, checking for stopping criteria. PSO velocities
and particles’ positions are updated with the following formulae:
vinertial = w´ vt- 1 (3)
vcognitive = 1´ u1´ j (pt- 1 - xt- 1) (4) vsocial = a2 ´ u2 ´ j (gt- 1 - xt- 1) (5) vt = vinertial + vcognitive + vsocial (6)
xt = xt- 1 + vt (7) where:
vt: velocity of the swarm at t (time) w: inertial factor
a1 : cognitive coefficient
a2 : social coefficient
u1 : random number in [0, 1] u2 : random number in [0, 1]
pt: personal best positions at t gt: global best positions at t xt: position of the swarm at t
φ(x): a matrix function that returns a row vector with each element being Euclidean norm of corresponding column in the matrix argument.
In (4), φ(pt-1 – xt-1) returns a vector. Each element of this vector is distance from a corresponding particle to its own best position. It is noteworthy that both position and velocity are vectors, so in the step of updating position, they are added directly to get new position, without any dimensional conflict.
To apply PSO to an MRS, each robot is modelled as a particle of the swarm and their movements in the search space resemble those of ideal particles described above. Actual implementation of PSO for MRS involves additional techniques to solve problems which are not covered in its conventional version, such as collision avoidance. APSO is developed to solve that problem. The steps in APSO are basically the same as those of PSO, but the velocities and positions are updated with APF-based formulae. Artificial potential fields are also created around every particle in the search space. The repulsive force between a particle and another particle or an obstacle is given by:
4 H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10
F= (F ax - k´ r2 )´ (H(0)- H(r)) (8) where r is the distance between the two objects,
Fmax is the maximum value of the repulsive force. H(x) is Heaviside step function. r1 is the radius of separation, i.e., repulsive forces are only applicable to particles or points whose distance to each other is smaller than r1. A robot has a limited sensing range, this range must be larger than r1. k is a parameter dependent upon r1, it is calculated so that F is equal to zero when r = r1. Total repulsive force exerted on a robot is the sum of all the repulsive forces exerted by other objects, according to (8).
vseparation is defined as the forth component velocity, responsible for assuring a collision-free exploration of the MRS. In implementation, vseparation corresponds to total repulsive forces on robots in the swarm.
The set of formulae used to update velocity and position in APSO is:
w = sig(d´ k + l) (9)
vinertial = w.´ vt- 1 (10)
vcognitive = C´ sig(j (pt- 1 - xt- 1)´ u+ v)(11) vsocial = S´ sig(j (gt- 1 - xt- 1)´ u+ v)(12)
vt = vinertial + vcognitive + vsocial + vseparation (13)
between two quantities, in which the first quantity progresses from a small beginning, then accelerates and approach its climax as the second quantity increase. There are three regions on the curve: beginning, acceleration and saturation region.
Algorithm: APSO 1. Initializing
- Generate the population
- Evaluate objective function
2. Update personal best position
- For each particle, compare fitness of past positions and choose the optimum position as its new personal best position
3. Update global best position
- Compare personal best positions of particles and choose the optimum position as global best position
4. Update and regulate velocity - Update velocity using (13)
- Limit velocity if needed 5. Update position
- Calculate new position using (14)
- Evaluate objective function for each particle 6. Check stopping criteria
- Stop if maximum step is reached or the swarm has converged - Otherwise, come back to step 2.
Figure 1. Implementation of APSO.
Fmax
xt = xt- 1 + vt (14)
where:
d: represents immediate population density at the position of a robot.
. ×: element-wise matrix multiplication sig(x): element-wise sigmoid function on
matrix:
sig(x)(i, j)= 1+ e- x(i, j) (15)
k, l, u, v: adjusting parameters used to adjust values of quantities of interest.
C: maximum value of vcognitive S: maximum value of vsocial
In Figure 1, the implementation of APSO is presented.
In APSO, sigmoid function is widely used because of an appropriate property of the sigmoid curve. It exhibits a relationship
Fmax/2
Fmin0 r1 r2 Distance
Figure 2. Attractive force.
This property was used to control velocities in APSO. vcognitive and vsocial are dependent upon the distances of particle to their personal best position and global best position. These velocities are regulated so that their magnitude and the corresponding distance could be described by a monotonically increasing relationship. With k being negative, (9) gives a
H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10 5
lower inertia for a higher population density. During the exploration, each robot sees the search space as a potential field, with repulsive force being proportional to vseparation; attractive force proportional to a combination of vcognitive and vsocial. The magnitude of attractive force could be described by a sigmoid curve (Figure 2.). The potential field is time-varying. As the position of particles change, global and personal best positions are always improved. Figure 3 shows the potential energy configuration for a robot outside of sensing range of any others. The robot is also not close to any obstacles and its personal best and global best positions are respectively (15, 15) and (20, -20). The search space is confined in x = [-50,50] and y = [-50,50].
Figure 3. Potential energy configuration.
The main difference between PSO and APSO is how velocity is updated. In APSO, vseparation, a new velocity is introduced. Its inertial value depends on immediate population density, vcognitive and vsocial are functions of distance, described by the sigmoid function. This reduces the possibility of collision, meanwhile yields a high performance.
2.1.3. Criteria for convergence
We claim that the exploration is success when the swarm converges atthe point of maximum illuminance. The criterion for convergence of the swarm in conventional PSO is simple and intuitive, as the swarm is said to be converged when all the particles is within a given radius, e.g. 10-3 of smallest dimension of the search space, regardless of population size.
However, in APSO, such criterion is not applicable because each particle has to maintain a distance to other particles. In our simulation, the two following criteria are used to determine whether the swarm is converged:
1. Improvement in best fitness: The swarm is said to be making progress if in 10 consecutive iterations, best fitness is improved by at least 0.1%.
2. Physical convergence: If in 10 consecutive iterations, the position of the swarm’s center of mass does not change considerably (less than the radius of a particle) and a certain number of particles are at a small distance from the center, we said that the swarm has physically converged. The number of particles and the distance are proportional to swarm population.
In short, if there is no improvement in best fitness and the change in the swarm’s position is inconsiderable, the swarm is considered to be converged and the searching process is terminated. It is worth noting that this kind of convergence criterion is not absolute convergence since not all particles gather around the swarm’s center. The operation is deemed successful if after convergence, the point of highest luminance is covered by the swarm and is within a predefined radius from global best position.
2.2. Simulation
2.2.1. Simulation setup and MRS configuration
In this research, we implement APSO on a homogeneous MRS in Matlab environment. The radius of each robot (r) is set as unit of length. The system has direct communication, the communication range is unlimited (beyond the limit of search space). r1 is 5×r, i.e. a robot can detect obstacles at the distance of 5×r from its position. Population size varies between 5, 10 and 15. Maximum velocity is 1.5×r/step. Each robot is able to acquire the illuminance at its position via a light sensor on top.
6 H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10
If we set r = 1, the search space size is 100×100. In the Cartesian coordinate system, the ranges of x and y coordinates are both [-50, 50]. We evaluate the effectiveness of the modified PSO algorithm in three scenarios with the presence of an isotropic source and two real light sources: 87517M56FG [17] and AVL1XMAMDG [18]. In the simulations, all obstacles in the search space are static cylindrical obstacles. The radii of cylindrical obstacles used in all scenarios are 4.
In the next two scenarios, we test with real light sources. Figure 6. and Figure 7. are contour maps of light intensity in regions illuminated by AVL1XMAMDG and 87517M56FG, respectively.
2000 4000 6000 8000 10000 12000
50
40
30
20
10
0
-10
-20
-30
-40
- -50 0 50
Figure 4. Scenario 1 - 3D View.
2.2.2. Detection of light sources in different scenarios
In the first scenario, a single light source is placed above the search space at (20, -20) (Figure 5). There are four static obstacles at (-30, -30), (-20, 30), (0, 0) and (30, 20) as illustrated in Figure 4.
0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045
50
40
30
20
10
0
-10
Figure 6. Scenario 2 - AVL1XMAMDG.
In each scenario, three population sizes: 5 robots, 10 robots and 15 robots are simulated. The results acquired after 1000 runs (for each scenario and population size) is presented in Figure 9. The figures are statistical graphs given for analysis of reliabilityand effectiveness ofAPSO.
2000 4000 6000 8000 10000 12000 14000 16000
50
40
30
20
10
0
-10
-20
-30
-40
-20
-30 - -50 0 50
-40
- -50 0 50
Figure 7. Scenario 3 - 87517M56FG.
Figure 5. Scenario 1 - Single isotropic light source.
H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10 7
In a typical run, as the exploration of this swarm progresses, the robots move towards global best position. As the population size increases and the robots have to maintain a minimum distance from each other, the swarm covers a large area even after convergence. This can be seen clearly in Figure 8.
Step: 100 Best Value = 12945.3969 50
40
30
20
10
0
-10
-20
-30
-40
algorithm is used. The same pattern can be observed in every scenario.
Figure 9. Distribution of SC in scenario 1.
-50
-50 0 50 x coordinator
Figure 8. Final distribution of robot swarm - scenario 2.
3. Results and discussion
The main results of these simulations are summarized in the following figures and tables. The results with MPSO - an algorithm from our previous work [19] - are also presented for
comparison. Figure 9-11 display the Figure 10. Distribution of SC in scenario 2. distribution of step of convergence (SC) in each
scenario after 100 runs. Figure 12-14 show the cumulative distribution of SC. Only data from successful operations is included.
From the figures, it can be concluded that as the swarm population increases, the step of convergence tends to decrease. However, while there is a large gap in performance between the 5-robot and the 10-robot swarm, there is not much improvement when the population increases from 10 to 15, regardless which