J. Cent. South Univ. (2013) 20: 3391−3400 DOI: 10.1007/s11771-013-1864-5
Mobile robot path planning based on adaptive bacterial foraging algorithm LIANG Xiao-dan(梁晓丹)1, LI Liang-yu(李亮玉)2, WU Ji-gang(武继刚)1, CHEN Han-ning(陈瀚宁)3 1. School of Computer Science and Software, Tianjin Polytechnic University, Tianjin 300160, China; 2. School of Mechanical and Engineering, Tianjin Polytechnic University, Tianjin 300160, China; 3. Laboratory of Information Service and Intelligent Control, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China © Central South University Press and Springer-Verlag Berlin Heidelberg 2013 Abstract: The utilization of biomimicry of bacterial foraging strategy was considered to develop an adaptive control strategy for mobile robot, and a bacterial foraging approach was proposed for robot path planning. In the proposed model, robot that mimics the behavior of bacteria is able to determine an optimal collision-free path between a start and a target point in the environment surrounded by obstacles. In the simulation, two test scenarios of static environment with different number obstacles were adopted to evaluate the performance of the proposed method. Simulation results show that the robot which reflects the bacterial foraging behavior can adapt to complex environments in the planned trajectories with both satisfactory accuracy and stability. Key words: robot path planning; bacterial foraging behaviors; swarm intelligence; adaptation
1 Introduction The goal of robot system is to do tasks at a cost as low as possible. Thus, optimal path planning for robot manipulators is always a hot spot in research fields of robotics [1]. The goal of robot path planning is to find an optimal, collision-free trajectory between two points in a working environment composed of many obstacles. That is, the path planning approach can be applied in static, dynamic or both environments, depending on the mode in which the environment is known and given in advance. The optimality of the path is usually measured by the traveling time and penalty for obstacle avoidance of the mobile robot. Navigation in mobile robot is a methodology that allows guiding a robot to accomplish a mission through an environment with obstacles in a good and safe way. The two basic tasks involved in navigation are the environment perception and path planning. Generally, global planning methods complemented with local methods are used for indoor missions since the environments are known or partially known; for outdoor applications, local planning methods are more suitable, global planning methods become a complement because of the scant information of the environment. Literature is rich in boarding to solve mobile robots trajectory planning in presence of static or dynamic
obstacles [2−3]. One of the most popular planning methods is the artificial potential fields [4]. However, this method gives only one trajectory solution that may not be the smaller trajectory in a static environment. In the past few years, many artificial intelligence algorithms were proposed as solutions to the robot path planning problem. In Ref. [5], a fuzzy algorithm was developed to navigate a mobile robot in an unknown dynamic environment filled with obstacles. The method requires the robot to be equipped with a variety and highly accurate sensors to produce collision free paths while increasing the total cost of the system. In addition, YANG and LUO [6] proposed a novel neural network approach to complete coverage path planning in static environments with, nevertheless, a high computational cost. In Ref. [7−8], MARCHESE introduced the use of a multilayered cellular automaton (MCA) to create the desired shortest path for a single robot. Recently, the interest in using evolutionary algorithms (EA) and swarm intelligence (SI) for robot path planning is increasing. Up to now, the genetic algorithm and bacterial foraging optimization are used in mobile robots trajectory planning. Generally, when the environment description is given [9−10]. Although the heuristic EA and SI approaches can not guarantee optimal performance on all engineering problems, however, if they can, they will find optimal solution faster than most classical methods [11].
Foundation item: Project(61173032) supported by the National Natural Science Foundation of China; Project(20090406) supported by the Tianjin Scientific and Technological Development Fund of Higher Education of China Received date: 2012−07−27; Accepted date: 2012−11−29 Corresponding author: LIANG Xiao-dan, Associate Professor, PhD; Tel: +86−22−58685358; E-mail:
[email protected]
J. Cent. South Univ. (2013) 20: 3394−3400
3392
In recent years, with the emergence of another member of the swarm intelligence family, i.e., bacterial foraging optimization (BFO), the selfadaptability of individuals in the bacterial foraging activities has attracted a great deal of interests. A few models have been developed to mimic bacterial foraging behavior and have been applied for solving some practical problems. Among them, bacterial foraging optimization (BFO) is a simple but powerful optimization tool that mimics the foraging behavior of E. coli bacteria [12]. Up to now, BFO has been applied successfully to some engineering problems [13−15], such as RFID network planning, harmonic estimation, transmission loss reduction and machine learning. This work uses a recently developed BFO based search model, namely the self-adaptive bacterial foraging optimization (SABFO) [16], to create optimal collision-free trajectories for mobile robot. Instead of the simple description of chemotactic behavior in original bacterial foraging optimization (BFO) algorithm, SABFO also incorporates the adaptive search strategy, which allows each bacterium strikes a good balance between exploration and exploitation during algorithmic execution by tuning its run-length unit self-adaptively. In the experiments, two case studies of static environment with obstacles are presented and evaluated. Simulation results show the adaptation of the bacterial robot in different environments in the planned trajectories.
2
Self-adaptive optimization
bacterial
foraging
2.1 BFO model The original bacterial foraging optimization (BFO) algorithm is one of the state-of-the-art evolutionary algorithms [17−18], which consists of three principal mechanisms, namely chemotaxis, reproduction, and elimination-dispersal. Each of these processes is briefly described as follows: 2.1.1 Chemotaxis In the original BFO, a unit walk with random direction represents a “tumble” and a unit walk with the same direction in the last step indicates a “run”. Suppose θi(j, k, l) represents the bacterium at j-th chemotactic, k-th reproductive, and l-th elimination-dispersal step. C(i) is the chemotactic step size during each run or tumble (run-length unit). Then, in each computational chemotactic step, the movement of the i-th bacterium can be represented as
i ( j 1, k , l ) i ( j , k , l ) C (i )
(i ) T (i ) (i )
(1)
where Δ(i) is the direction vector of the j-th chemotactic step. When the bacterial movement is run, Δ(i) is the
same with the last chemotactic step; otherwise, Δ(i) is a random vector whose elements lie in [−1, 1]. With the activity of run or tumble taken at each step of the chemotaxis process, a step fitness, denoted as J (i, j, k, l), will be evaluated. 2.1.2 Reproduction The health status of each bacterium is calculated as the sum of the step fitness during its life, i, e., Nc
J (i, j, k , l ) ,
where Nc is the maximum step in a
j 1
chemotaxis process. All bacteria are sorted in reverse order according to health status. In the reproduction step, only the first half of population survives and a surviving bacterium splits into two identical ones, which are then placed in the same locations. Thus, the population of bacteria keeps constant. 2.1.3 Elimination and dispersal The chemotaxis provides a basis for local search, and the reproduction process speeds up the convergence which has been simulated by the classical BFO. While to a large extent, only chemotaxis and reproduction are not enough for global optima searching. Since bacteria may get stuck around the initial positions or local optima, it is possible for the diversity of BFO to change either gradually or suddenly to eliminate the accidents of being trapped into the local optima. In BFO, the dispersion event happens after a certain number of reproduction processes. Then, some bacteria are chosen, according to a preset probability Ped, to be killed and moved to another position within the environment. In the context of original BFO model, the bacteria with large run-length unit have exploring ability (global investigation of the search place) while the bacteria with relatively small run-length unit have exploiting skill (the fine search around a local optimum). However, it is difficult to decide which value of static run-length unit is best suited for a given problem. Hence, this section introduces the preprogrammed change of this parameter during the evolution to balance exploration and exploitation, which results in the significant improvement in performance of the original algorithm. 2.2 SABFO model In the SABFO algorithm, an “individual run-length unit” to the i-th bacterium of the colony is introduced and each bacterium can only modify the search behavior of itself by using the current status of its own. In this way, not only the position (solution vector) but also the run-length unit of each bacterium undergoes evolution, respectively. This individual-level self-adaptation may provide us with more accurate information about the search because it is the separate individual that engages in searching the solution space not just the whole colony.
J. Cent. South Univ. (2013) 20: 3391−3400
In the foraging process of SABFO model, each bacterium displays alternatively two distinct search states: 1) Exploration state, during which the bacterium employs a large run-length unit to explore the previously unscanned regions in the search space as fast as possible. 2) Exploitation state, during which the bacterium uses a small run-length unit to exploit the promising regions slowly in its immediate vicinity. Each bacterium in the colony has to permanently maintain an appropriate balance between Exploration and Exploitation states by varying its own run-length unit adaptively. In SABFO, the adaptation of the individual run-length unit is done by taking into account two decision indicators: a fitness improvement (finding a promising domain) and no improvement registered lately (current domain is food exhausted). The criteria that determine the adjustment of individual run-length unit and the entrance into one of the states (i.e. Exploitation and Exploration) are the following. Criterion-1: If the bacterium discovers a new, promising domain, the run-length unit of this bacterium is adapted to another smaller one. Here, “discovers a new promising domain” means this bacterium registers a fitness improvement beyond a certain precision from the last generation to the current. Following Criterion-1, the bacterium’s behavior will self-adapt into exploitation state. Criterion-2: If the bacterium’s current fitness is unchanged for a number Ku (user-defined) of consecutive generations, then augment this bacterium’s run-length unit and this bacterium enters exploration state. This situation means that the bacterium searches on an un-promising domain or the domain where this bacterium focuses its search has nothing new to offer. This self-adaptive strategy is given in pseudocode in Fig. 1, where t is the current generation number, Ci(t) is
3393
the current run-length unit of the i-th bacterium, (t) is the required precision in the current generation of the i-th bacterium, and β are user-defined constants, Cinitial and εinitial are the initialized run-length unit and precision goal, respectively. The flowchart of the SABFO algorithm can be illustrated by Fig. 2, where S is the colony size, t is the chemotactic generation counter from 1 to maxgeneration, i is the bacterium’s ID counter from 1 to S, Xi is the i-th bacterium’s position of the bacteria colony, Ns is the maximum number of steps for a single activity of i is the number of generations that the i-th swim, N flag bacterium has not improved its own fitness. i
3 Benchmark test 3.1 Benchmark functions The set of benchmark functions contains four functions that are commonly used in evolutionary computation literature to show solution quality and convergence rate [19−20]. The formulas of these functions are listed below. Sphere function: n
f1 ( x) xi2 , x [5.12, 5.12]D Rosenbrock function: n
f 2 ( x) 100 ( xi 1 xi2 ) 2 (1 xi ) 2 , x [3, 3]D (3) i 1
Rastrigrin function: n
f3 ( x) ( xi2 10 cos(2πxi ) 10, x [5.12, 5.12]D i 1
(4) Griewank function: f 4 ( x)
1:
FOR (each bacterium i) IN PARALLEL
2: 3:
IF (Criterion-1) then i
C (t+1)=Ci(t)/α; //exploitation i
i
4:
ε (t+1)=ε /β;
5:
ELSE IF (Criterion-2) then
6:
Ci(t+1)=Cinitial; //exploration
7:
εi(t+1)=εinitial;
8:
ELSE
9:
Ci(t+1)=Ci(t);
10:
εi(t+1)=εi(t);
11:
END IF
12:
END FOR IN PARALLEL
Fig. 1 Pseudocode for dynamic self-adaptive strategy
(2)
i 1
x 1 n 2 n xi cos( i ) 1, x [600, 600]D 4000 i 1 i i 1 (5)
3.2 Parameter settings for algorithms Experiment was conducted to compare four algorithms (including the original BFO, the real-coded genetic algorithm (GA), the standard particle swarm optimization (PSO) and the proposed SABFO) on four benchmark functions with two dimensions. The experiments run 30 times respectively for each algorithm on each benchmark function and the maximum generation is set at 1 000. The mean values and standard deviation of the results are presented. The parameters settings for SA-BFO are summarized in Table 1. For the original BFO algorithm, this test takes C=0.1 and Ped=0.25, which is the standard
J. Cent. South Univ. (2013) 20: 3394−3400
3394
Fig. 2 Flowchart of SABFO algorithm Table 1 Parameters of SABFO Function
S
Cinitial
initial
Ku
β
Sphere
100
0.1
100
20
10
10
Rosenbrock
100
0.1
100
20
10
10
Rastrigrin
100
0.1
100
20
10
10
Griewank
100
10
100
20
10
10
set of these two parameter values as recommended in Ref. [12]. This test sets S=100, Nc=100, Ns=4, Nre=5 and Ned=2, then BFO performs totally 1 000 chemotactic steps in each run, which makes a fair comparison in regard of the parameter values. The tested PSO algorithm is the standard one and the parameters were given by the default setting of Ref. [11]. The tested GA algorithm is a real-coded genetic algorithm with intermediate crossover
and Gaussian mutation (the parameters were to be the same of Ref. [21]). The population size of all the algorithms was set at 100. 3.3 Simulation results and discussion The representative results obtained are presented in Table 2, including the best, worst, mean and standard deviations of the function values found in 30 runs. Figure 3 presents the evolution process for all algorithms according to the reported results in Table 2. From the results, it can be observed that SABFO achieved significantly better performance on all benchmark functions than the original BFO algorithm. SABFO surpassed all other algorithms on function 1, which is the unimodal function that adopted to assess the convergence rates of optimization algorithm. SABFO
J. Cent. South Univ. (2013) 20: 3391−3400
3395
Table 2 Comparison among SA-BFO, BFO, PSO and GA Function
f1
f2
f3
f4
2-D
BFO
ABFO1
PSO
GA
Best
5.642 3×10−7
0
5.057 6×10−124
2.863 8×10−48
Worst
3.340 4×10−5
0
2.489 2×10−114
1.058 7×10−45
Mean
1.429 1×10−5
0
8.522 6×10−116
2.310 5×10−46
Standard
9.603 5×10−6
0
4.540 8×10−115
2.723 7×10−46
Best
1.529 4×10−6
7.888 6×10−31
0
6.856 4×10−10
Worst
9.293 5×10−4
2.190 5×10−14
5.307 5×10−25
3.857 8×10−5
Mean
1.735 3×10−4
7.352 8×10−16
3.989 3×10−26
1.902 1×10−6
Standard
2.134 4×10−4
3.998 3×10−15
1.194 7×10−25
7.074 3×10−6
Best
9.082 5×10−4
4.650 9×10−11
0
0
2.734 9×10
−9
0
0
1.265 5×10
−9
0
0
−10
0
0
Worst Mean
0.125 6 0.025 9
Standard
0.030 6
Best
0.029 6
Worst Mean Standard
2.997 4 0.997 5 0.814 2
7.495 0×10 0
0.031 1
0
7.741 1×10
−5
3.879 1
0.027 1
5.154 2×10
−6
1.117 8
0.006 3
1.589 2×10
−5
1.052 1
0.006 1
Fig. 3 Convergence results of SABFO, BFO, PSO, and GA on 2-D benchmark functions: (a) Sphere function; (b) Rosenbrock function; (c) Rastrigrin function; (d) Griewank function
3396
performed better on multimodal functions 4 when the other algorithms missed the global optimum basin. In order to further analyze the adaptive foraging behaviors of the proposed SABFO model, the other experiment simulated the self-adaptive behaviors in SABFO to show how the algorithm decides by itself when to explore and when to exploit the searching space. In this simulation, the reproduction, elimination and dispersion events were excluded to illustrate the bacterial behaviors clearly. Figures 4(a)−(d) illustrate the trajectories of a single bacterium on the four benchmark functions respectively, namely the 2D Dejong, Rosenbrock, Rastrigrin and Griewank functions, which are contour plotted. In all the cases, the evolution process proceeds 1 000 chemotatic steps, and the same parameter setting is chosen as in Table 1, except S=1. It can be seen clearly, the proposed self-adaptive strategy is important because it permits the bacteria refining its foraging behavior adaptively. It can be observed that the bacterium switched between exploitation and exploration states by self-adapting its run-length unit. Figures 4(a) and (b) illustrate bacterial trajectories in the 2-D unimodal function (Sphere and Rosenbrock). At the beginning of the simulation, the bacterium started exploring the search space using a large run-length unit. In this way, the bacterium did not waste much time before finding the promising region
J. Cent. South Univ. (2013) 20: 3394−3400
that contains the global optimum because of the large run-length unit encourages long-range search. Then, the bacterium slowed down (i.e., the bacterium gradually decreased its run-length unit) near the optimum to pursue the more and more precise solutions. Figures 4(c) and (d) present the bacterial trajectories in the contour plotted 2-D multimodal function. It should be noted that whenever the bacterium encounters a fitness improvement, this forager starts searching intensively in this promising region. Whereas, whenever it is highly probable that the good solutions lying in this region have been found, it moves away from this region and starts exploring the other regions of the search space until another better region is discovered. Finally, the bacterium will find the domain that contains the global optimum. Clearly, this result captures the important aspects of the self-adaptive behaviors that take place in nature. The associated evolution processes of the run-length unit of this bacterium during foraging are illustrated in Fig. 5. This provides an intuitive explanation of what is happening during the execution of SABFO. From Fig. 5, it can be noticed that when the bacterium finds difficulties during an exploit state (with low run-length unit), it increases the run-length unit to improve the exploration, and vice versa.
Fig. 4 Single bacterium self-adaptive foraging trajectories of SA-BFO model on 2-D benchmark functions: (a) Sphere function; (b) Rosenbrock function; (c) Rastrigrin function; (d) Griewank function
J. Cent. South Univ. (2013) 20: 3391−3400
3397
Fig. 5 Dynamics of run-length unit automatically produced by self-adaptive criterion during single bacterium foraging on 2-D benchmark functions: (a) Sphere function; (b) Rosenbrock function; (c) Rastrigrin function; (d) Griewank function
4 Robot path planning based on SABFO Optimal collision-free trajectory planning for mobile robot, known as the path planning problem, is always a major issue in robotics due to the necessity for the robots’ course of movement. In this work, based on the proposed SABFO model, the utilization of biomimicry of bacterial chemotaxis and self-adaptive foraging strategy was considered to develop a bio-inspired path planning strategy for mobile robot. In the proposed model, a bacterial robot that mimics the behavior of bacteria is able to determine an optimal collision-free path between a start and a target point in an environment surrounded by obstacles. That is, the bacterial chemotaxis mechanism enable the robot explore the environment and finally locate the target point without colliding any obstacles; while the self-adaptive foraging strategy can efficiently save the traveling time and actuators’ energy of the self navigating robot. In the navigation process, the location of bacterial robot can be evaluated as a multi-objective cost function: Minimize f ( xt ) w1 f g ( xt ) w2 f o ( xt )
(6)
where x represents the coordinate of the robot in the working environment, t is the time step, fg is the goal
function that represents the distance between the current robot position and the target point, fo is the obstacle function that represents the distance between the current robot position and the obstacles nearby, w1 and w2 are the weight parameters that specify the relative importance of achieving obstacle avoidance and reaching the goal. The overall operating process of robot path planning based on SABFO can be described as in Fig. 6.
5 Simulation results In this experiment, the proposed planning method is evaluated against an ideal 2-dimensional square working area. The 2D sphere function with the global minimum (i.e., the goal point) in Ref. [25] is used for the goal function that is given by f g ( x, y ) ( x 25) 2 ( y 25)2 x, y [0, 30]
(7)
Figures 7(a) and (b) show the landscape and contour plot of the sphere goal function, respectively. That is, at each time step, the bacterial chemotaxis drives the robot moving to go down the surface toward the goal, while maybe run into an obstacle. In this work, Gaussian function of unity height was taken to represent an obstacle. Then, the obstacle function can be formulated as a composition of a number
J. Cent. South Univ. (2013) 20: 3394−3400
3398
of Gaussian functions and can be formulated as n
o 2
f o ( x, y ) max exp 0.8(( x xi ) i 1
Fig. 6 Flowchart of mobile robot path planning based on SABFO
Fig. 7 Fitness landscape and contour plot of goal function with initial (square) and goal (star) positions: (a) Fitness landscape; (b) Contour plot
( y yio )2 )
(8)
where n is the number of the obstacles in the working environment and ( xio , yio ) is the position of the i-th obstacle. It should be noted that the use of the maximum of all the Gaussian functions ensures that each obstacle position is represented independent of the others. Since the more obstacles cause more environmental complexity, two obstacle, functions, namely fo1 and fo2 with 6 and 20 obstacles respectively, are evaluated in our experiment. The landscapes of fo1 and fo2 are shown in Figs. 8 and 9, respectively. Figures 10(a) and (b) show the contour plots of the final working environments combining the goal and obstacle function of two test cases respectively, along with the initial position and goal position. This experiment sets w1=1 and w2=0.000 1. For the tested case 1 with six obstacles, the optimal trajectory and fitness convergence obtained by the proposed planning strategy are illustrated in Figs. 11(a) and (b), respectively. It can be observed from the results that the bacterial chemotaxis mechanism enables the robot avoiding the obstacles but tries to stay on course to the goal. It should be noted that the self-adaptive strategy enables the robot locate the area with the target point more quickly. That is, the self-adaptive foraging strategy can efficiently save the traveling time and actuators’ energy of the self navigating robot. In order to start the path planning procedure, the parameters of SABFO are set as S =1, C i n i t i a l =0.1,
Fig. 8 Fitness landscape and contour plot of obstacle function 1 with initial (square) and goal (star) positions: (a) Fitness landscape; (b) Contour plot
J. Cent. South Univ. (2013) 20: 3391−3400
initial=100, Ku=100, =β=10, and the maximum generation is 1 000.
Fig. 9 Fitness landscape and contour plot of obstacle function 2 with initial (square) and goal (star) positions: (a) fitness landscape; (b) contour plot
Fig. 10 Contour plot of cost function combining goal and obstacle functions: (a) Contour plot of fo1; (b) Contour plot of fo2
3399
The simulation results on tested case 2 with 20 obstacles are illustrated in Fig. 12. Although the
Fig. 11 Simulation results on case 1: (a) Robot path to avoid obstacles and reach goal; (b) Fitness convergence
Fig. 12 Simulation results on case 2: (a) Robot path to avoid obstacles and reach goal; (b) Fitness convergence
J. Cent. South Univ. (2013) 20: 3394−3400
3400
environment is more complex in this case, the robot using bacterial foraging strategy was still able to find the target point without colliding into any obstacles. Figures 11(b) and 12(b) show that the robust convergences of path planning for both cases are obtained after about 400 generations.
6 Conclusions 1) A bacterial foraging approach is proposed for robot path planning based on bacterial foraging algorithm. In the proposed path planning model, the bacterial chemotaxis mechanism enables the robot explore the environment and finally locates the target point without colliding any obstacles, while the self-adaptive foraging strategy can efficiently save the traveling time and actuators’ energy of the self navigating robot. 2) In the case study, two test scenarios with different number, of obstacles are adopted to evaluate the performance of the proposed path planning method. The simulation results show that the robot which mimics the bacterial foraging behavior can adapt to different environments in the planned trajectories with both satisfactory accuracy and stability. 3) There are ways to improve the proposed path planning method. The overall optimal solution for robot path planning is represented by a simple linear combination of two objectives of robot system. The future work should extend the model to multi-objective optimizer to search the pareto frontier that can optimize the trade off between multiple requirements of robot system; Moreover, it remains to see how practically useful the bacterial foraging based robot path planning methods are for many real-world applications, where the work space of robots often involves various danger sources that robots must evade, such as fire in a rescue mission, land mines and enemies in a war field.
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16] [17]
[18]
References
[19]
[1]
[20]
[2]
[3]
WILLMS A R, YANG S X. An efficient dynamic system for real-time robot-path planning [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 2006, 36(4): 755−766. BENNEWITZ M, BURGARD, W, THRUN S. Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots [J]. Robotics and Autonomous Systems, 2002, 41: 89−99 CHETTIBI T, LEHTIHET H E, HADDAD M, HANCHI S.
[21]
Minimum cost trajectory planning for industrial robots [J]. European Journal of Mechanics A/Solids, 2004, 23: 703−715. TSUJI T, TANAKA Y, MORASSO P G, SANGUINETI V, KANEKO M. Bio-mimetic trajectory generation of robots via artificial potential field with time base generator [J]. IEEE Transactions on Systems, Man and Cybernetics-Part C, 2002, 32(4): 426−439. LEE T L, WU C J. Fuzzy motion planning of mobile robots in unknown environments [J]. Journal of Intelligent and Robotic Systems, 2003, 37(2): 177−191. YANG S X, LUO C. A neural network approach to complete coverage path planning [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 2004, 34(1): 718−724. MARCHESE F M. A directional diffusion algorithm on cellular automata for robot path planning [J]. Future Generation Computer Systems, 2002, 18: 983−994. MARCHESE F M, NEGRO M D. Path planning for multiple generic-shaped mobile robots with MCA [J]. Lecture Notes in Computer Science, 2006, 3993: 264−271. IOANNIDIS K, SIRAKOULIS G CH, ANDREADIS I. Cellular ants: A method to create collision free trajectories for a cooperative robot team [J]. Robotics and Autonomous Systems, 2011, 59(2): 113−127. GEMEINDER M, GERKE M. GA-based path planning for mobile robot systems employing an active search algorithm [J]. Applied Soft Computing, 2003, 3: 149−158. CHEN H N, ZHU Y L, HU K Y. Discrete and continuous optimization based on multi-swarm coevolution [J]. Natural Computing, 2010, 9(3): 659−682. PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control [J]. IEEE Control System Magazine, 2002, 22(3): 52−67. TANG W J, LI M S, WU Q H, SAUNDERS J R. Bacterial foraging algorithm for optimal power flow in dynamic environments [J]. IEEE Transactions on Circuits and Systems I, 2008, 55(8): 2433−2442. HANMANDLU M, VERMA O P, KUMAR N K, KULKARNI M. A novel optimal fuzzy system for color image enhancement using bacterial foraging [J]. IEEE Transactions on Instrumentation and Measurement, 2009, 58(8): 2867−2879. CHEN H N, ZHU Y L, HU K Y, KU T. Multi-colony bacteria foraging optimization with cell-to-cell communication for RFID network planning [J]. Applied Soft Computing, 2010, 10(2): 539−547. CHEN H N, ZHU Y L, HU K Y. Adaptive bacterial foraging optimization [J]. Abstract and Applied Analysis, 2011, 2011: 1−27. BADAMCHIZADEH M A, NIKDEL A, KOUZEHGAR M. Comparison of genetic algorithm and particle swarm optimization for data fusion method based on Kalman filter [J]. International Journal of Artificial Intelligence, 2010, 5(10): 67−78. ZHAO Z Y, XIE W F, HONG H. Hybrid optimization method of evolutionary parallel gradient search [J]. International Journal of Artificial Intelligence, 2010, 5(10): 1−16. CHEN H N, ZHU Y L. Optimization based on symbiotic multi-species coevolution [J]. Applied Mathematics and Computation, 2008, 205(1): 47−60. RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: A gravitational search algorithm [J]. Information Sciences, 2009, 179(13): 2232−2248. CHEN, H N, ZHU Y L, HU K Y. RFID network planning using a multi-swarm optimizer [J]. Journal of Network and Computer Applications, 2011, 34(3): 888−901. (Edited by HE Yun-bin)