Swarm optimization approach for light source detection by multi - Robot system

. Improvement in best fitness: The swarm 
could be described by a sigmoid curve (Figure is said to be making progress if in 10 
2.). The potential field is time-varying. As the consecutive iterations, best fitness is improved 
position of particles change, global and by at least 0.1%. 
personal best positions are always improved. 2. Physical convergence: If in 10 
Figure 3 shows the potential energy consecutive iterations, the position of the 
configuration for a robot outside of sensing swarm’s center of mass does not change 
range of any others. The robot is also not close considerably (less than the radius of a particle) 
to any obstacles and its personal best and global and a certain number of particles are at a small 
best positions are respectively (15, 15) and (20, distance from the center, we said that the swarm 
-20). The search space is confined in x = [- has physically converged. The number of 
50,50] and y = [-50,50]. 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 
 Figure 3. Potential energy configuration. 
 swarm and is within a predefined radius from 
 The main difference between PSO and global best position. 
APSO is how velocity is updated. In APSO, 2.2. Simulation 
vseparation, a new velocity is introduced. Its 
inertial value depends on immediate population 2.2.1. Simulation setup and MRS 
density, vcognitive and vsocial are functions of configuration 
distance, described by the sigmoid function. In this research, we implement APSO on a 
This reduces the possibility of collision, homogeneous MRS in Matlab environment. 
meanwhile yields a high performance. The radius of each robot (r) is set as unit of 
 2.1.3. Criteria for convergence length. The system has direct communication, 
 We claim that the exploration is success the communication range is unlimited (beyond 
when the swarm converges atthe point of the limit of search space). r1 is 5×r, i.e. a robot 
maximum illuminance. The criterion for can detect obstacles at the distance of 5×r from 
convergence of the swarm in conventional PSO its position. Population size varies between 5, 
is simple and intuitive, as the swarm is said to 10 and 15. Maximum velocity is 1.5×r/step. 
be converged when all the particles is within a Each robot is able to acquire the illuminance at 
given radius, e.g. 10-3 of smallest dimension of its position via a light sensor on top. 
the search space, regardless of population size. 
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 In the next two scenarios, we test with real 
100×100. In the Cartesian coordinate system, light sources. Figure 6. and Figure 7. are 
the ranges of x and y coordinates are both [-50, contour maps of light intensity in regions 
50]. We evaluate the effectiveness of the illuminated by AVL1XMAMDG and 
modified PSO algorithm in three scenarios with 87517M56FG, respectively. 
the presence of an isotropic source and two real 
light sources: 87517M56FG [17] and 2000 4000 6000 8000 10000 12000
AVL1XMAMDG [18]. In the simulations, all 50 
obstacles in the search space are static 40
cylindrical obstacles. The radii of cylindrical 
 30
obstacles used in all scenarios are 4. 
 20
 10
 0
 -10
 -20
 -30
 -40
 -50 
 -50 0 50
 Figure 6. Scenario 2 - AVL1XMAMDG. 
 In each scenario, three population sizes: 5 
 robots, 10 robots and 15 robots are simulated. The 
 Figure 4. Scenario 1 - 3D View. 
 results acquired after 1000 runs (for each scenario 
 2.2.2. Detection of light sources in different and population size) is presented in Figure 9. The 
scenarios figures are statistical graphs given for analysis of 
 In the first scenario, a single light source is reliability and effectiveness of APSO. 
placed above the search space at (20, -20) 
 2000 4000 6000 8000 10000 12000 14000 16000
(Figure 5). There are four static obstacles at 
(-30, -30), (-20, 30), (0, 0) and (30, 20) as 50 
illustrated in Figure 4. 40
 30
 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045
 20
 50 
 10
 40
 0
 30
 20 -10
 10 -20
 0 -30
 -10
 -40
 -20
 -50 
 -30 -50 0 50
 -40 
 -50 
 -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 algorithm is used. The same pattern can be 
swarm progresses, the robots move towards observed in every scenario. 
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
 y coordinator y -10 
 Figure 9. Distribution of SC in scenario 1. 
 -20
 -30
 -40
 -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 
8 H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10 
 where number of iterations is restricted, due to 
 constraints on energy consumption or time, 
 success rate at a given maximum iteration may 
 become a crucial value to evaluate an 
 algorithm. Table 1 provides data regarding this 
 value, with the maximum iteration being 100. 
 The data in all the figures consistently 
 indicates low performance of the 5-robot 
 swarm. Both algorithms are not effective for 
 swarms of small population. The swarm with 
 larger initial coverage is less prone to premature 
 convergence. 
 APSO is also compared to the multi-search 
 algorithm inspired by PSO in the work of Pugh 
 Figure 11. Distribution of SC in scenario 3. et. al. [6]. With the same constraints and 
 When APSO is applied, there are typically conditions on the robot system, the respective 
less outliers and IQRs are smaller than when results are given in Figure 15. Initially, the 
MPSO is applied. We can come to the robots are deployed randomly in a square of the 
conclusion that APSO is more stable. size 8×8. The target is placed in the center of 
 Scenario 1 the square. The realistic conditions here are 
 1 wheel slip (10%) and noise (standard normal 
 0.8 distribution). In such conditions, APSO even 
 0.6 yields better results. In every case, the result is 
 0.4
 5 robots
 Success Rate Success improved when applying APSO. 
 0.2 10 robots
 15 robots Scenario 2
 0 1 
 20 40 60 80 100 120 140 160
 Maximum step allowed - APSO 0.8
 1 0.6
 0.8 0.4
 5 robots
 Success Rate Success
 0.6 0.2 10 robots
 15 robots
 0.4 0 
 5 robots 0 50 100 150 200 250
 Success Rate Success Maximum step allowed - APSO
 0.2 10 robots
 15 robots
 1 
 0 
 20 40 60 80 100 120 140 160
 Maximum step allowed - MPSO 0.8
 0.6
 Figure 12. CDF of SC in scenario 1. 
 0.4
 5 robots
 Figure 12-14 provide the most accurate way Rate Success 0.2 10 robots
 15 robots
 0 
to evaluate the effectiveness of APSO when 0 50 100 150 200 250
 Maximum step allowed - MPSO
time (or number of iterations) is limited. In 
general, to achieve the same rate of success, Figure 13. CDF of SC in scenario 2. 
APSO requires less iterations than MPSO. 
 In any scenario, if the maximum iteration is 
100, success rate of APSO approaches 100% 
when the swarm population is 10 or 15. The 
corresponding values of MPSO are all lower. If 
the maximum iteration is less than 50, there is 
little possibility that the swarm could converge, 
no matter which algorithm is chosen. In cases 
 H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10 9 
 th
 Scenario 3 Table 1. Success rate at 100 iteration 
 1 
 0.8 Scenario 1 Scenario 2 Scenario 3 
 N 
 0.6 A M A M A M 
 0.4
 5 robots 5 87 77 70 6 84 58 
 Success Rate Success 0.2 10 robots 10 98 96 97 32 100 99 
 15 robots
 0 
 0 50 100 150 200 250 15 100 98 100 95 100 100 
 Maximum step allowed - APSO D 
 1 
 0.8
 0.6
 0.4
 5 robots
 Success Rate Success 0.2 10 robots
 15 robots
 0 
 0 50 100 150 200 250
 Maximum step allowed - MPSO
O 
 Figure 14. CDF of SC in scenario 3. 
 3 
 Simplified
 Realistic
 2.5
 2
 1.5
 1
 (m) Target to Distance
 0.5
 0 
 1 2 3 5 10 20
 Number of Robots
 a) b) 
 Figure 15. Distance to target from the swarm’s point of strongest signal detection, 
 averaged over 1000 runs a) multi-search algorithm inspired by PSO. b) APSO. 
4. Conclusion and Future works dynamic deployment of robotic systems, flame 
 detection or optical wireless charging. 
 In this paper, a modified PSO algorithm, However, there are still some drawbacks in 
namely APSO, is presented for detecting light this algorithm, for example, the swarm is 
sources. In this algorithm, APF is integrated unable to detect multiple sources. Furthermore, 
into PSO and a new velocity component is it has yet to be tested in complex scenarios. 
introduced to keep the movement of the swarm In future works, we will focus on dealing 
collision-free. Experimental results in Matlab with them and applying the algorithm on a 
environment have shown good performance, real MRS. 
compared to previous works. With a high 
success rate, this proposed algorithm is 
promising for some practical problems 
involving the utilization of MRS, such as 
10 H.A. Quy, P.M. Trien / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 32, No. 3 (2016) 1-10 
Acknowledgements [9] B. Nakisa, M. N. Rastgoo, M. F. Nasrudin, 
 and M. Z. A. Nazri. "A multi-swarm particle 
 This work has been supported by Vietnam swarm optimization with local search on 
National University, Hanoi, under Project No. multi-robot search system." Journal of 
QG.15.25. This work is dedicated to the 20th Theoretical and Applied Information 
Anniversary of the IT Faculty of VNU UET. Technology 71, no. 1 (2015): 129-136. 
 [10] O. Khatib. "Real-time obstacle avoidance for 
References manipulators and mobile robots." The 
 international journal of robotics research 5, 
 no. 1 (1986): 90-98. 
 [1] A. Marjovi, J. G. Nunes, L. Marques, and A. 
 De Almeida. "Multi-robot exploration and fire [11] T. D. Ngo. "LinkMind: Link optimization in 
 searching." In Intelligent Robots and Systems, swarming mobile sensor networks." Sensors 
 2009. IROS 2009. IEEE/RSJ International 11, no. 8 (2011): 8180-8202. 
 Conference on, pp. 1929-1934. IEEE, 2009. [12] A. Howard, M. J. Matarić, and G. S. 
 [2] H. Ishida, T. Nakamoto, T. Moriizumi, T. Sukhatme. "Mobile sensor network 
 Kikas, and J. Janata. "Plume-tracking robots: deployment using potential fields: A 
 A new application of chemical sensors." The distributed, scalable solution to the area 
 Biological Bulletin 200, no. 2 (2001): 222- coverage problem." In Distributed 
 226. Autonomous Robotic Systems 5, pp. 299-308. 
 Springer Japan, 2002. 
 [3] L. Marques, and A. T. de Almeida. "Finding 
 odours across large search spaces: A particle [13] P. Song, and V. Kumar. "A potential field based 
 swarm-based approach." In Climbing and approach to multi-robot manipulation." In Robotics 
 Walking Robots, pp. 419-426. Springer Berlin and Automation, 2002. Proceedings. ICRA'02. 
 Heidelberg, 2005. IEEE International Conference on, vol. 2, pp. 1217-
 1222. IEEE, 2002. 
 [4] J. Kennedy, and R. Eberhart, “Particle Swarm 
 Optimization”, IEEE International Conference [14] M. M. Zavlanos, and G. J. Pappas. "Potential fields 
 on Neural Networks (Perth, Australia), IEEE for maintaining connectivity of mobile networks." 
 Service Center, Piscataway, NJ, IV, pp. 1942- IEEE Transactions on Robotics, Volume 23, Issue 
 1948, 1995. 4, August 2007, pages 812-816. 
 [5] Y. Tang, Q. Li, L. Wang, C. Zhang, and Y. [15] K. Y. Lee, and J. B Park. "Application of 
 Yin. "An improved PSO for path planning of particle swarm optimization to economic 
 mobile robots and its parameters discussion." dispatch problem: advantages and 
 InIntelligent Control and Information disadvantages." In Power Systems Conference 
 Processing (ICICIP), 2010 International and Exposition, 2006. PSCE'06. 2006 IEEE 
 Conference on, pp. 34-38. IEEE, 2010. PES, pp. 188-192. IEEE, 2006. 
 [6] J. Pugh, and A. Martinoli. "Inspiring and [16] M. S. Couceiro, S. Micael, Rocha R. P., and 
 modeling multi-robot search with particle N. M. Ferreira. "A novel multi-robot 
 swarm optimization." In Swarm Intelligence exploration approach based on particle swarm 
 Symposium, 2007. SIS 2007. IEEE, pp. 332- optimization algorithms." In Safety, Security, 
 339. IEEE, 2007. and Rescue Robotics (SSRR), 2011 IEEE 
 International Symposium on, pp. 327-332. 
 [7] S. Doctor, G. K. Venayagamoorthy, and V. G. 
 IEEE, 2011. 
 Gudise. "Optimal PSO for collective robotic 
 search applications." In Evolutionary [17] American Electric Lighting, “875 17M 56 
 Computation, 2004. CEC2004. Congress on, FG”, Photometric Data File, 2008. 
 vol. 2, pp. 1390-1395. IEEE, 2004. [18] American Electric Lighting, “AVL 1XM AM 
 [8] Y. Cai, and S. X. Yang. "An improved PSO-based DG”, Photometric Data File, 2008. 
 approach with dynamic parameter tuning for [19] A. Q. Hoang, and M. T. Pham. "Light Source 
 cooperative multi-robot target searching in Detection using Multirobot Systems with 
 complex unknown environments." International Particle Swarm Optimization Approach." 
 Journal of Control 86, no. 10 (2013): 1720-1732. In Proceedings of The 3rd Vietnam 
 Conference on Control and Automation, pp. 
 448-455. Thai Nguyen, 2015.