Artif Life Robotics (2012) 17:233–240 DOI 10.1007/s10015-012-0051-3

ORIGINAL ARTICLE

A faster path planner using accelerated particle swarm optimization Abdullah Zawawi Mohamed • Sang Heon Lee Hung Yao Hsu • Namrata Nath

•

Received: 8 December 2011 / Accepted: 30 July 2012 / Published online: 22 September 2012  ISAROB 2012

Abstract The idea of placing small mobile robots to move around in a large building to detect potential intruders has been around for some time. However, there are still two major hurdles to overcome: to locate itself in the environment and to make a decision on how to move around safely and effectively at a reasonable computation cost. This paper describes a mathematical model for developing a scheme for an autonomous low cost mobile robot system using visual simultaneous localization and mapping and accelerated particle swarm intelligent path planner. The results indicated that this system could provide a solution for the problem of indoor mobile robot navigation. Advances in computer technology make this technique a cost effective solution for a future home service robot. Keywords Artificial intelligence  Global path planning  Local path planning  SLAM  Swarm robotics

1 Introduction The success behind the navigation of autonomous mobile robots relies heavily on four factors: perception, or the A. Z. Mohamed (&) Faculty of Engineering and Built Environment, School of Materials and Mechanical Engineering, National University of Malaysia (UKM), 43600 Bangi, Malaysia e-mail: [email protected] A. Z. Mohamed  S. H. Lee  H. Y. Hsu  N. Nath Division of Information Technology, Engineering and Environment, School of Advanced Manufacturing and Mechanical Engineering, University of South Australia, Mawson Lakes, SA 5095, Australia e-mail: [email protected]

ability of the robot to interpret data from its sensors to make meaningful data; localization, i.e., the ability of the robot to determine its position in the environment; cognition, the ability of the robot to act to achieve its goals; and motion control, the robot’s ability to modulate its motor outputs to achieve the desired trajectory [1]. However, the noise from the sensors is accumulated with time and this would lead to misunderstandings about its true location. In the early stages of autonomous robot development, researchers used to combine data from a laser scanner, encoder, ultrasonic or infrared beacon, etc., as devices to avoid obstacles and obtain precise positions. Another critical factor in the successful navigation of a mobile robot is path planning. Path planning research is a few decades old and before the concept of mobile robots was born. However, still there is no explicit answer for the autonomous mobile robot navigation problem. Many suggestions and attempts have been made by researchers to solve this problem, for example, visibility graph, fuzzy logic, ant colony optimization (ACO), artificial potential field (APF), and genetic algorithm (GA). In order to implement such an algorithm in real-time applications, there is, however, one important issue that must be addressed and that is the cost of computation. In GA-based path planning, the environment around the robot usually coded from starting point to the goal and the optimal path is achieved through continuous optimization using the selection, crossover, and mutation operator, which is characterized by the global optimization ability and robustness. This technique has a major disadvantage in terms of large searching space, complicated coding, and high computation cost. ACO on the other hand has better robustness and global optimization [2]. Yet its searching ability is limited to the division of the grid. ACO is a good option to solve the shortest path searching problems when the paths are already

123

234

created [3]. While APF is a simple model and has low computation it can be easily trapped into local minima. The magnitude of grid division also affects the path planning directly [4]. A larger grid division will decrease the computation cost but the path finding ability will be compromised. Fuzzy logic can overcome the local minimum problem; however, the incompleteness of experiences and fuzzy reasoning table rapidly expanding with the increase of input quantity are the disadvantages of the fuzzy logic [5]. A review of the literature indicates that particle swarm optimization (PSO) proposed by Eberhart in 1995 has received much attention from researchers and particularly in the computer sciences. This is because it has special attributes, namely fast convergence to the global optima and robustness [6]. This research investigates the performance of PSO to solve the global path planning problem for mobile robots. Many experiments need to be done to obtain the best parameter settings to achieve the desired results. One of the biggest challenges is compromising between computational cost and the shortest path. A higher number of particles will have higher computational costs; however, it will produce the shorter path than less number of particles. The path planning is generated as the robot moves since Visual SLAM was assumed to be implemented in this experiment

Artif Life Robotics (2012) 17:233–240

target will produce a greater fitness value, in contrast if the position of an agent is nearer to the obstacle it will produce a lower fitness value. Lu et al. have tested their algorithm with two robots moving in opposite directions to the target with the existence of a moving obstacle. Their robots arrived at the target without a single collision. However, in the initial setting they set the speed of the mobile robot at a relatively slow one to allow the computer to optimize the path planning. Compared to the other systems this one only needs partial information from the limited range sensors to navigate without collision in a dynamic environment. PSO algorithm works by simultaneously maintaining several particles or potential solutions in the search space. For each iteration of the algorithm, each particle is evaluated by the objective function being optimized, based on the fitness of that solution. The PSO algorithm is developed in three steps, which will only stop when it meets the exit condition. The pseudo code for the canonical PSO is shown below: Step 1: Initialise population with random positions and velocities Step 2: Evaluate-compute fitness of each particle in the swarm Step 3: Do for each particle in swarm { Step 3.1: Find particle best (pbest) - calculate fitness value of each particle. If pbest in current iteration > previous pbest Pbest = current pbest Endif

2 Autonomous mobile robot system concept

Step 3.2: Find global best (gbest) – best fitness of all pbest Step 3.3: Update velocity of particle as per Eq. 1

The accelerated PSO global path planning system is just one of 3 parts that make up the autonomous mobile robot system. The first part of the system is the hippocampal based visual simultaneous localization and mapping (Hv-SLAM) while the second part consists of the Tangent Bug algorithm for local path planning. It is also known as the obstacle avoidance algorithm. Hv-SLAM will generate and maintain the level of accuracy which will later be used by the APSO global path planning to generate the paths. After the APSO has generated the path, the Tangent Bug algorithm will be activated to guide the robot to the target by following the path generated by the APSO. The map generation will be faster if the system uses more robots instead of only one robot.

3 PSO for global path planning Particle swarm optimization is a method for finding the best solution by imitating social behavior of schools of fish or flocks of birds [7]. Groups achieve the objective based on common information that every member has. Lu et al. [8] have researched the potential of PSO in path planning in unknown environments. The basic principle in their algorithm is that an agent’s position that is nearer to the

123

Step 3.4: Update position of particle as per Eq. 2 Step 4 :} Repeat step 3.1 through 3.4 until termination condition is reached

Vi ðt þ 1Þ ¼ wVi ðtÞ þ c1 r1 ½x^i ðtÞ  xi ðtÞ þ c2 r2 ½^ gi ðtÞ  xi ðtÞ

ð1Þ

xi ðt þ 1Þ ¼ xi ðtÞ þ Vi ðt þ 1Þ

ð2Þ

where parameters used are: w is the inertia coefficient; Vi(t ? 1) the current particle’s velocity; Vi(t) the previous particle’s velocity; xi(t ? 1) the current particle’s position; xi ðtÞ the previous particle’s position; r1 the uniformly distributed random number [0:1]; r2 the uniformly distributed random number [0:1]; c1 and c2 the acceleration constants; x^i ðtÞ the current pbest ; xi ðtÞ the previous particle’s position, g^i ðtÞ is the current gbest. A population of particles is created and then evaluated to compute their fitness and find both the particle’s best position and global best population from the population of the swarm. The particle best, pbest, represents the best fitness value for a particle up to that moment in time, whereas the global best, gbest, represents the best particle’s fitness value in the swarm. Each particle is accelerated toward its pbest and gbest locations using acceleration values c1 and c2 at each time step. These constants c1 and

Artif Life Robotics (2012) 17:233–240

235

c2 decide the relative influence of the social and cognition components. Typically these constants have the same value to give equal weight to each social and cognition component. The search process is terminated when gbest arrives at the target position. If the particles move too far away from the search space then two common problems will occur: first, the system will converge in fewer iterations despite the paths not being smooth; and second, the particles will move outside the search space without converging. Velocity clamping is a technique to limit the maximum velocity of each particle. For a search space bounded by the range [-xmax, xmax], velocity clamping limits the velocity to the range [-vmax, vmax], where vmax ¼ k  xmax . The value of kcan be set by the user. Another important element in PSO is x, an inertia factor which was introduced by Eberhart and Shi [9] after they found that PSO searched wide area effectively. However, it tends to lack local search precision. x helps PSO to dynamically adjust the velocity over time by gradually focusing the PSO into a local search.

4 Accelerated PSO for global path planning A simplified version which could accelerate the convergence of the algorithm is to use the global best only. This simplified version of accelerated PSO was developed by Xin-She Yang [10] at Cambridge University in 2007, in which the velocity vector is generated by Vi ðt þ 1Þ ¼ Vi ðtÞ þ a½r  0:5 þ b½^ g1 ðtÞ  gi ðtÞ

ð3Þ

where r is a random variable with values from 0 to 1. The updated position is simply xi ðt þ 1Þ ¼ xi ðtÞ þ Vi ðt þ 1Þ

ð4Þ

By merging these two equations into a single equation, the speed of convergence will increase even further. gi ðtÞ þ a½r  0:5 xi ðt þ 1Þ ¼ ð1  bÞxi þ b^

ð5Þ

This simpler version will give the same order of convergence. The typical values for this accelerated PSO are a & 0.1 * .4 and b & 0.1 * 0.7; however, a & 0.2 and b & 0.5 are recommended. Reducing the randomness as iterations proceed will further improve accelerated PSO. This means a monotonically decreasing function as shown in the equation below: a ¼ a0 ect or a ¼ a0 ct ; ðc\1Þ

ð6Þ

where a0 & 0.5–1 is the suggested initial value of the randomness parameter. t is the number of iterations of time

steps and c \ 1 is a control parameter. xi ðtÞ is the previous particle’s position; r the uniformly distributed random number [0:1]; g^i ðtÞ the current gbest; gi ðtÞ the previous gbest; s the randomness parameter; b the social ratio. Step 1: Initialise population with random positions and velocities Step 2: Evaluate-compute fitness of each particle in swarm Step 3: Do for each particle in swarm { Step 3.1: Find global best (gbest) Step 3.2: Update position of particle as per Eq. 5 Step 4 :} Repeat step 3.1 through 3.2 until termination condition is reached

Fitness evaluation qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi f1 ¼ ðxt  targetxÞ2  ðyt  targetyÞ2 8 9  < 1m  1 ; k dm k  df = f j j kdj k d f2 ¼ : 0; k dm k [ df ; j

F ¼ f1 þ f2

ð7Þ ð8Þ

j

ð9Þ

where, xt and yt are the particle’s position at x and y coordinates; f1 the Euclidean distance from the robot’s position to the target; f2 the safe distance from the particle to the obstacles; F the fitness function for the whole path planning optimization problem; k djm k the radius of the circled obstacle; djf is the particle’s distance to the center point of the obstacle. The goal of PSO is to minimize the fitness function F. Therefore, the path planning problem must be described in terms of fitness function; this path planning problem then becomes an optimization issue. The path planning problem in this research can be divided into two smaller fitness functions: the first fitness function f1 is to make the path to the target; and the second fitness function f2 is to avoid the obstacles. djf is the particle distance to the center point of the obstacle. If the particle distance is larger than the radius of the circle obstacle, the particle is in a safe distance and therefore no correction action needs to be taken. Figure 1 shows the process of determining the center point of the obstacle by an image processing technique. The detected obstacle’s area is wrapped in a rectangular box (Fig. 1a) to find the center point and diameter. Based on this center point and diameter a circle is created to simplify the obstacle avoidance system as well as minimize the risk of local optima trap (Fig. 2). The particle’s obstacle avoidance is based on the equation below: A¼

r  B  ðr  pÞ  c rp

ð10Þ

123

236

Artif Life Robotics (2012) 17:233–240

•

• Fig. 1 a Wrapped obstacle in rectangular box. b Obstacle in circle

•

• •

The neighborhood topology: In this simulation, gbest swarm as shown in Fig. 4 is used as the neighborhood topology, i.e., all particles are neighbors of each other. Therefore, the position of the best overall particle in the swarm is used in the social term of the velocity update equation. This is based on the assumption that gbest swarms converge quickly because all the particles are attracted simultaneously to the best position of the search space. The swarm will converge slowly in the best swarm form because only a specific number of particles can affect the velocity of a given particle [11]. Safe distance: The safe distance between the robot and obstacles is set to 5 pixels. Cognitive and social coefficients c1 and c2: Both these coefficients are set to 2.05 (full model) based on the setting in the experiments in previous studies [12, 13]. However, in the cognitive and social coefficient experiment these values varied. Inertia x is set to 1.3 as a benchmark. Hv-SLAM is assumed to be implemented in this simulation.

Fig. 2 Particle’s obstacle avoidance algorithm

6 Results where, A is the new coordinates; B the particle’s position fall into the obstacle’s area; C the center point of the circled obstacle; r radius of the circled obstacle; p is the distance from B to C. If any particle falls into the obstacle’s area, obstacle avoidance mechanism based on Eq. 10 is activated to find the new position for the particle. The particle is forced out perpendicularly to the perimeter of the obstacle.

5 Simulation set up This PSO path planner was performed in MATLAB with the simulation environment as presented below: • •

• •

The simulation space is 100 pixels by 100 pixels rectangular plane with 3 obstacles as shown in Fig. 3. Only several parts of the obstacle’s body will be perceived by the camera, simulating a partially known environment path planning. The safe distance from the robot to obstacles is 5 pixels. Population size: In general, any evolutionary search algorithm shows improved performance with a relatively larger population. However, a very large population will cost more in terms of fitness function evaluations without producing significant improvements. In this simulation, the population size is set to 1000, 100, and 30.

123

Two different situations were simulated in this experiment. The first experiment is the simulation for the path planning in the known environment, both complex and simple obstacle avoidance. The second situation is the path planning with time updated obstacle’s information; the positions of the obstacles were updated as the robot moved toward the target. In this experiment, the number of the obstacles will increase as the robot moves toward the target. The results from the final simulation show the effect of capping Xmax. Figure 5 illustrates the simulation results for the unknown environment. The robots will update the path planning based on the information from the camera at the time t. In this experiment, the robot managed to find the path and avoided the obstacles appearing in its vision system. Every time the robot found a new obstacle that was not in its library it would stop and recalculate the path. 6.1 Xmax setting In addition to canonical PSO, to control the randomness of the possible solution in this algorithm, Xmax is implemented. Xmax is the maximum distance that a particle can move. Limiting the maximum distance will help the particles find a better set of solution so that it can create a smoother path compared to a non-capping algorithm. On the other hand, this effort will slow down the system’s convergence time. The number of particles of either 100 or

Artif Life Robotics (2012) 17:233–240

237

Fig. 3 The position of the obstacles in the simulation study

6.3 Cognitive and social ratio

Fig. 4 Graphical representation of the gbest swarm (left) and lbest (right) neighborhood topologies

10000 would not affect computational costs much. However, implementing Xmax will increase non-capping algorithm by 5 times as shown in Fig. 6. Based on Fig. 7, when Xmax is set too high the possibilities of the system to create an invalid path is higher as shown in the black square. Xmax is not only important to smooth and optimize the path, but also constitutes a major factor for creating a valid path to the target. 6.2 Population size Population size has a big impact on the performance of the path planner. Even though Shi and Eberhart [14] reported that ‘‘PSO is not sensitive to the population size,’’ for the path planning problem the fact contradicts to their belief that when the larger population size is chosen the longer computational time is needed without improving much on the results. Carlisle [15] suggested that a population of 30 is a good option but he also indicated that it might be too small to be efficient, yet large enough to produce a reliable result. Table 1 summarizes the results from the experiments of various particle populations. When the population increased it resulted in a shorter distance and little in the way of computational cost increase. The environment for this simulation is based on Fig. 5 where the target is (800, 900).

Kennedy [16] suggested that the sum of the values of cognitive and social components of the PSO (C1 and C2) should be about 4.0 and it is common to set each component to 2.05. Carlisle [15] varied the setting of C1 and C2 and found that by setting a higher social component the performance of the PSO improved. He set C1 to 1.3 and C2 to 2.8. Based on Table 2, it is clear that a higher social coefficient as suggested by Carlisle produced an optimal distance compared to other settings. 6.4 APSO versus PSO Table 3 shows a comparison of performances between canonical PSO and accelerated PSO for the environment as per Fig. 7. The number of particles and Xmax are the same for both algorithms. From the literature it appears difficult to converge APSO with very small error tolerance. In order to overcome this problem, the error tolerance for APSO is set to 2 % while the error tolerance for PSO is set to 0.2 %. The experiment results for PSO with a 2 % error tolerance are presented as a benchmark showing that APSO can converge faster for the same condition. The position of the target is set to (800, 900) while the number of particles is set to 36 and the Xmax is set to 25. Table 3 shows a significant improvement in the time that the system needed to generate a path. At the same time, APSO also produced an efficient path in comparison to the canonical PSO algorithm. Figure 8 shows that APSO not only performed better at the computational speed and path length, but also generated a smoother path in comparison to the PSO algorithm.

123

238 Fig. 5 Simulation results for the path planning in for an unknown environment

Fig. 6 Paths created by the system in several different Xmax settings

123

Artif Life Robotics (2012) 17:233–240

Artif Life Robotics (2012) 17:233–240

239

Fig. 7 Invalid path in complex known environment Xmax = 100

Table 1 Effects of population size on performance

7 Conclusions

Population

30

100

500

1000

Distance

1327

1322

1315

1310

Time (s)

8.7

9

11.8

14.9

Table 2 Effects of cognitive and social ratio on performance C1 and C2 = 1.49

C1 and C2 = 2.05

Distance

1320

1310

1307

1295

Time (s)

15.2

15

14.6

14.6

Inertia value

C1 and C2 = 2.5

C1 = 1.3 and C2 = 2.8

Table 3 Performance comparisons between APSO and PSO Algorithms

PSO-0.2

PSO-2

APSO

Distance

1407

1360

1303

Time (s)

6.7

6.8

5.2

In this paper, investigative results on using PSM to solve the near optimal path problem have been reported. A higher population APSO will increase the quality of the results; however, its drawback is that higher computational costs are needed. Depending on the application, either the target is to make fast decision or to obtain an optimal path, the exact number of particle can be tuned. Larger number of particle will slow down the process; however, in many cases it will improve the optimality of the path. Social ratio also plays an important role in increasing the performance of the APSO. A higher value social ratio leads to better results in contrast with full model where the cognitive and social ratios have the same value. The next step in this research is to solve the optimization problem of SLAM by PSM. The results are highly encouraging with much better performance exhibited by the proposed PSM based path planner. It should be noted that the performance of the APSO path planner can be improved further if the best

Fig. 8 Comparison of the paths generated by APSO and PSO

123

240

Artif Life Robotics (2012) 17:233–240

parameters combinations are found and further investigations are underway for this purpose. Acknowledgments A.Z. Mohamed would like to acknowledge the support provided by the Ministry of Higher Education, Malaysia for the scholarship given to carry out this research.

7. 8.

References 9. 1. Rusu RB, Robotin R, Lazea G et al (2006) Towards open architectures for mobile robots: zeero. In: Proceedings international conference on automation, quality and testing, robotics 2006, pp 260–265 2. Gao M, Xu J, Wu H (2008) Path planning for mobile robot based on chaos genetic algorithm. In: Proceedings 4th international conference on natural computation, ICNC 2008, pp 409–413 3. Yuwan C, Choingzhi S, Nanggang X, Lu W (2008) Path planning method for mobile robot based on ant colony optimisation algorithm, electronics and applications. In: 3rd IEEE conference on electronics and applications, pp 298–301 4. Ningning Q, Bojun M, Xian’en L et al (2008) A modified artificial potential field algorithm for mobile robot path planning. In: Proceedings of World Congress on intelligent control and automation 2008, pp 2603–2607 5. Prandhan SK, Parhi DR, Panda AK (2007) Fuzzy logic techniques for navigation of several mobile robots. Appl Soft Comput J 9(1):290–304 6. Lu M, Wu DP, Zhang JP (2006) A particle swarm optimizationbased approach to tackling simulation optimization of stochastic,

123

10. 11.

12.

13.

14.

15. 16.

large-scale and complex systems. Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics) 3930 LNAI, 2006, pp 528–537 James K, Russell CE, Yuhui S (2001) The particle swarm, swarm intelligence, pp 287–325 Li L, Dunwei G (2008) Robot path planning in unknown environments using particle swarm optimization, natural computation, 2008. ICNC ‘08. In: Fourth international conference, vol 4, Oct 18–20, 2008, pp 422–426 Shi YH, Eberhart RC (1998) Parameter selection in particle swarm optimization. In: The 7th annual conference on evolutionary programming, San Diego Xin SY (2008) Computational mathematics, world scientific, pp 231–234 Kennedy J, Mendes R (2002) Population structure and particle swarm performance. In: Proceedings of the IEEE congress on evolutionary computation (CEC) 2002, pp 1671–1676 Parsopoulos KE, Vrahatis MN (2007) Parameter selection and adaptation in unified particle swarm optimization. Math Comput Model 46(1–2):198–213 Shi YH, Eberhart RC (1998) Parameter selection in particle swarm optimization. In: Proceedings of the seventh annual conference on evolutionary programming, pp 591–600 Shi YH, Eberhart RC (1998) Empirical study of particle swarm optimization, 1999 congress on evolutionary computing, vol III, pp 1945–1950 Carlisle A, Dozier G (2001) An off-the-shelf PSO. In: Proceedings of the particle swarm optimization workshop, pp 1–6 Kennedy J (1998) The behavior of particles. In: 7th annual conference on evolutionary programming, San Diego, pp 579–589