Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Mobile Robot Path Planning Based on Ant Colony Algorithm With A* Heuristic Method

Mobile Robot Path Planning Based on Ant Colony Algorithm With A* Heuristic Method METHODS published: 16 April 2019 doi: 10.3389/fnbot.2019.00015 Mobile Robot Path Planning Based on Ant Colony Algorithm With A Heuristic Method 1,2 1 1 1,2 Xiaolin Dai , Shuai Long , Zhiwen Zhang and Dawei Gong * 1 2 School of Mechatronics Engineering, University of Electronic Science and Technology of China, Chengdu, China, Center of Robot, University of Electronic Science and Technology of China, Chengdu, China This paper proposes an improved ant colony algorithm to achieve efficient searching capabilities of path planning in complicated maps for mobile robot. The improved ant colony algorithm uses the characteristics of A algorithm and MAX-MIN Ant system. Firstly, the grid environment model is constructed. The evaluation function of A algorithm and the bending suppression operator are introduced to improve the heuristic information of the Ant colony algorithm, which can accelerate the convergence speed and increase the smoothness of the global path. Secondly, the retraction mechanism is introduced to solve the deadlock problem. Then the MAX-MIN ant system is transformed into local diffusion pheromone and only the best solution from iteration trials can be added to pheromone update. And, strengths of the pheromone trails are effectively limited for Edited by: avoiding premature convergence of search. This gives an effective improvement and Caixia Cai, high performance to ACO in complex tunnel, trough and baffle maps and gives a better Agency for Science, Technology and ∗ result as compare to traditional versions of ACO. The simulation results show that the Research (A STAR), Singapore improved ant colony algorithm is more effective and faster. Reviewed by: Wenchao Gao, Keywords: path planning, ant colony algorithm, A algorithm, bending suppression, retraction mechanism Institute for Infocomm Research (A STAR), Singapore Ran Duan, INTRODUCTION Hong Kong Polytechnic University, Hong Kong Bonan Huang, Path planning is a key issue in the field of mobile robot research. Its main purpose is to find an Northeastern University, China optimal or suboptimal, safe and collision-free path from the starting point to the target point in the environment with obstacle (Cheng et al., 2010; Deepak et al., 2012; Zhou et al., 2013). According *Correspondence: Dawei Gong to the degree of intelligence in the process of path planning, mobile robot path planning can be pzhzhx@126.com divided into traditional path planning and intelligent path planning. The traditional path planning algorithm includes simulated annealing algorithm (Miao and Tian, 2013), potential function theory Received: 20 December 2018 (Cetin and Yilmaz, 2014; Nair et al., 2015), fuzzy logic algorithm (Li et al., 2013; Jiang and Li, 2014; Accepted: 25 March 2019 Bakdi et al., 2016) and so on. However, these traditional methods can’t be further improved in path Published: 16 April 2019 search efficiency and path optimization. Intelligent path planning algorithm includes Ant Colony Citation: Optimization (ACO) (Jovanovic et al., 2016; Wang et al., 2016), genetic algorithm (Arantes et al., Dai X, Long S, Zhang Z and Gong D 2017; Lin et al., 2017), neural network (He et al., 2016a, 2017a,b) and particle swarm algorithm (Das (2019) Mobile Robot Path Planning et al., 2016; Song et al., 2016) and so on. The ant colony algorithm has the advantages of strong Based on Ant Colony Algorithm With robustness, good global optimization ability and inherent parallelism. Moreover, it easily combines A Heuristic Method. with multiple heuristic algorithms to improve the performance of algorithms. So it is widely used Front. Neurorobot. 13:15. doi: 10.3389/fnbot.2019.00015 in path planning. Frontiers in Neurorobotics | www.frontiersin.org 1 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning However, due to the randomness of probabilistic transfer and the inappropriateness of pheromone intensity update, the traditional ACO will easily fall into the local optimum and tend to poor convergence. To this end, many scholars delivered a variety of improved methods to solve problems regarding pheromone update and path search strategy (Stützle and Hoos, 2000; Zeng et al., 2016; Zhao et al., 2016; Zhang et al., 2017). In Stützle and Hoos (2000), an Ant Colony System (ACS) algorithm was proposed to speed up the convergence rate of ACO by updating pheromones on the path of the optimal ant of each generation. In Zhao et al. (2016), by adaptively changing the volatilization rate and adjusting the pheromone updating formula, the search ability of the ant colony and the convergence rate of the algorithm were improved. In Zhao et al. (2016), some intelligent algorithm was proposed to generate an initial path, which can be transformed into the initial pheromone distribution to avoid blind search of ant colony. In Zhang et al. (2017), the path information (such as the crowded path and the steep path weight) was added into FIGURE 1 | Environment model. the initial pheromone matrix, which could affects the efficiency of the algorithm. In Zhao et al. (2016), the heuristic function was adjusted to improve the convergence rate of the algorithm (the robot can move). In order to identify obstacles, the white grid according to the target point. In Zeng et al. (2016), it unlimited cell is represented by 0 and the gray grid unit is represented by 1. step length of finding optimal path so that the improved ACO The grid method is simple and effective to create and maintain could find a shorter path and its convergence was better. In grid model. Moreover, the grid method have strong adaptability addition, many scholars have combined the ant colony algorithm for obstacle. This method is convenient for computer storage with other (intelligent) algorithms (He et al., 2016b; Liu et al., and processing. 2016; Yen and Cheng, 2016; He and Zhang, 2017) to improve the The grid model was placed into two-dimensional coordinate convergence rate and the smooth of path. In Liu et al. (2016), the system. And then serial number method is adopted to mark each geometric method was used to optimize path. Also in Liu et al. grid. In N N grid map, the starting node is named after Start (2016), the force factor in the artificial potential field method and the target node is named after Goal. The position coordinates is transformed into local diffusion pheromone to improve the x, y corresponding to any grid whose grid number is R as follow: ability of the ant colony algorithm to find the obstacle. In Yen and Cheng (2016), the fuzzy ant colony optimization method was mod (R, N) − 0.5 if mod (R, N)! = 0 proposed to minimize the iterative learning error. x = N + mod (R, N) − 0.5 otherwise (1) In this paper, an effective version of ant colony algorithm y = N + 0.5 − ceil is achieved. It utilizes the evaluation function of A algorithm to improve the heuristic information of Ant colony algorithm, Where mod is the surplus operation, ceil rounds the elements to which accelerates the convergence speed during the search. And the nearest integers toward infinity. MAX–MIN Ant System is used to make the global search ability better by updating the path pheromone of the optimal network. Ant Colony Algorithm At the same time, the bending suppression operator is introduced Heuristic Strategy With Direction Information to improve heuristic information, which aims to optimize the In the traditional ACO, the probability of the next node is selected smoothness of the path. The problem of deadlock is solved by by roulette wheel method as follows: using the retraction mechanism. All these procedures not only give an effective improvement and better performance to ACO, α β τ (t) · η (t)  ( ij ) ( ij ) but also give the best results as compare to traditional versions of s ∈ allow k α β (τ (t)) ·(η (t)) is is P (t) = (2) s∈allow the algorithm (Zhao et al., 2016) and ACO in complex tunnel, ij 0 s ∈/ allow trough and baffle maps. The simulation results show that the proposed algorithm is effective and fast. η (t) = ij ij MATERIALS AND METHODS 2 2 d = (x − x ) + (y − y ) ij j i j i Environment Model The work environment is built by using the grid model, which Where τ is the pheromone trail of the path grid i to grid j, and ij divides the robot working space into N N squares. As shown in η is the heuristic information of the path grid i to grid j. α is the ij Figure 1, the gray grids are represented as obstacles (the grid with stimulating factor of pheromone concentration which determine barriers) and the white grids are represented as free grid squares the relative influence of the pheromone trail. β is the stimulating Frontiers in Neurorobotics | www.frontiersin.org 2 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning factor of visibility which determine the relative influence of the The heuristic cost of A algorithm is expressed by the heuristic information. d is the distance between node i and node estimated function, and the estimated function equation f (n) is ij j. (x , y ) and (x , y ) is the coordinates of grid i and grid j. allow is as follows: i i j j k the collection of grids which ants can choose when ants in the grid f n = g n + h n (5) i (in other words, they are the grids around the grid i except the ( ) ( ) ( ) obstacle grid and taboo grid).   1/2 2 2 h(n) = n − g + n − g x x y y Coverage and Updating Strategy  1/2 g (n) = (n − s ) + n − s x x y y According to the traditional ACO, the next node is decided by the roulette wheel method and it is repeated until the target point is where g(n) is the minimum cost from the source node to the obtained. After each iteration is completed, pheromone trails are current node. h(n) is the minimum cost from the current node to updated in line with the length of path planning. For each trial the destination node. n and n are the coordinates of the current during pheromone update, all imperfect pheromones evaporates x y node n . g and g are the coordinates of the target node g, s , and only the best pheromones are updated to trials history, x x y because it enables ants to neglect all substandard pheromone and s are the coordinates of the initial node s. trails and improve its coverage efficiency to find a shorter path. The estimated function of A algorithm is used as heuristic Formula (3) is used to update the pheromone quantity on each information to search for global optimal path in ant colony vertex at the end of each cycle: algorithm, and the bending suppression operator is added to the heuristic value of ant colony algorithm to reduce the number of bending times and the large cumulative turning angle. The τ = (1 − ρ)τ + 1τ ij ij ij m improved heuristic information formula is as follows: (3) 1τ = 1τ , 0 < ρ < 1  ij ij k=1 η (t) = (6) ij h(n) + g (n) + cost(bend) where m is the number of ants. ρ is pheromone evaporation rate. cost bend = ϕ · turn + ψ · thita 1τ represents the value of pheromone that the ant k leaves in ij the path of grid i to grid j. This article uses the ant-cycle-system where Q is a constant more than 1. cost(bend) is a bending model, and 1τ is defined as follows: ij suppression operator. turn is the number of turns from node n− 1(previous node) to node n+ 1 (next node). thita is the angle between the line segment of node n − 1 to node n (current node) Q /L (t) if arc i, j is used by k in iteration t k 1 k 1τ k = (4) ij and the line segment of node n to node n + 1. ϕ is the coefficient 0 otherwise converting turning times into grid length. ψ is the coefficient converting angle into grid length. Where Q is a constant. L (t) is the length of the path that the 1 K ant k is looking for. Solve the Deadlock Problem When the robot environment is more complex (especially the Improved Ant Colony Algorithm ants go into the environment of concave obstacles), due to the The traditional ACO has the following shortcomings: Due to the presence of the taboo table, the ants may fall into a deadlock state lack of initial pheromone and the unapparent difference of the without the next grid to move. As shown in Figure 2, when the heuristic value between adjacent grids, it usually requires a longer ant travels from the grid T to the grid S, the next optional grid is search time, which leads to the slow convergence rate. When grid C. At this time, the ant is trapped in a deadlock state and it cannot model is complex, the robot maybe fall into a deadlock state in move to its surrounding grid. which the robot cannot move to the surrounding grids. In the For the deadlock problem, Wang and Yu (2011) adopted grid map, the path planning with traditional ACO may have more the early death strategy, which deleted the ants trapped in a bending times and big cumulative bending angle. To solve the deadlock state from the ant colony and did not update the global above problems, this paper makes the following improvements. pheromone. However, when more of the ants are trapped in the deadlock state, the number of ants that can reach the goal is Heuristic Information Based on A Algorithm significantly reduced, which results in a decrease in the diversity A algorithm (Duchon et al., 2014) is the most effective direct of solutions and is not conducive to the search of optimal path search method for solving the shortest path in static road for ants. In this paper, the improvement measure is that the ants network. It is developed on the basis of Dijkstra algorithm, adopt retraction mechanism when they fall into the deadlock which can avoid blind search to improve search efficiency. In this state. As shown in Figure 2, the ant, which has walked into paper, A algorithm is used as the heuristic information of path the grid, is trapped in the deadlock state, and the improved searching to improve the convergence speed of the algorithm strategy allows the ant to roll back one step and updates the and obtain the better path. The bending suppression operator is taboo table information. If the ant is still trapped into a deadlock added to the heuristic information to reduce bending times and state, the ant will continue to rollback untill grid T. At this cumulative bending angle. moment, the ant escapes the deadlock area. Since the deadlock Frontiers in Neurorobotics | www.frontiersin.org 3 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning represent different weight coefficient and are set by analyzing the robot’s structure and kinematics (Wu et al., 2013; Li et al., 2017). The w and w can convert turning angle and turning 1 2 times into grid length, respectively. V represents the constant robot speed of a mobile robot. W represents the angular speed of a robot mobile robot as it turns. t represents the time of acceleration and deceleration as the mobile robot turns once. (2) Pheromone trail limits. In order to avoid the situation that the traditional ant colony algorithm may falls into local optimal solution and loses the further search space ability by pheromone accumulation, the pheromone trail of the MMAS is limited in the upper limits and lower limits Tau Tau . The formula is: min, max,  Tau , Tau ≤ Tau min min Tau = Tau, Tau < Tau ≤ Tau (8) min max Tau , Tau > Tau max min Aco Procedure FIGURE 2 | Deadlock state diagram. To sum up, specific steps of mobile robot path planning based on the improved ant colony algorithm are as follows: Step 1: The working environment is modeled by the grid edge may be the part of global optimal path, no pheromone method, and the starting point start and the target point goal punishment is carried out on the deadlock edge. The retraction of the mobile robot are given. mechanism cannot prevent ants from entering a deadlock state, Step 2: Initialize the ant system. Set the number m of but it lets the deadlocked ants return back to the previous ants, parameter α which determines the relative influence grid until there is a feasible grid around the ants, so the ACO of the pheromone trail, parameter β which determines the with the retraction mechanism has higher efficiency and fewer heuristic value, the global pheromone volatilization coefficient iterations. The ACO with the retraction mechanism and without ρ, pheromone intensity Q and other related parameters. the retraction mechanism is compared in section The Retraction 1 Step 3: Update taboo table. Place the ant k (k = 1, 2, · · · , m) Mechanism Results Analysis below. on the current node and add the current node to the Max–Min Ant System corresponding taboo table. As the traditional ant colony algorithm may cause premature Step 4: Process deadlock. According to the taboo table, it will convergence and precocious phenomenon, it needs to improve judge whether ants are trapped in a deadlock state. If the algorithm to solve these problem. The MAX-MIN Ant System ants are in a deadlock state, the retraction mechanism will be (MMAS) (Stützle and Hoos, 2000) can solve these problems well. adopted and the deadlock node will be added to the taboo (1) Pheromone trail updating. After each iteration trial, the table. Conversely, it will judge whether the ants reach the target pheromone is submitted into update history in traditional point. If the ants reach the target point, it will turn to Step 6, ant colony algorithm. While in the MMAS, only the path otherwise it will turn to Step 5. pheromone of the optimal network is updated after the iteration Step 5: Select the next grid. It will calculate the heuristic is completed. Accordingly, the modified pheromone trail update function according to formula (6), and calculate the rule is stated by: probability function according to formula (2). Finally, it will use the roulette method to select the next feasible grid. If best τ (t + 1) = (1 − ρ)τ (t) + 1τ (7) ij ij ij the ants reach the target grid, it will turn to Step 6, otherwise it will turn to Step 3. Q Q 1 3 1τ (t) = + ij best best Step 6: If the ants reach the target node, it will repeat Step 3 turn until each ant completes the search target during its iteration best C = ω Cals l + ω Turns l 1 2 turn process and then turn to Step 7. Step 7: Update pheromone. After each iteration, if the robot ω = W number of iterations satisfies inequality N ≤ N , it max robot will update the path pheromone and determine whether it ω = V × t 2 robot a meets the convergence conditions. If it meets the convergence best where Q is a constant more than 1.L denotes to the shortest conditions, it will withdraw. If it does not meet, it will turn path currently found by the algorithm. Cals(l) represents the sum to Step 3. If the number of iterations satisfies inequality N > of all the angles of turning on the best optimized path. Turns(l) N , it will be not counted further. The final result is output max is the sum of the turns on the best optimized path. w and w as long as the end condition is satisfied. 1 2 Frontiers in Neurorobotics | www.frontiersin.org 4 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning The implementation process of improved ant colony algorithm is the improved ant colony algorithm proposed in this paper) are as in Table 1. simulated on each map in turn. The convergence speed, shortest path length and bending suppression effect of those algorithms are compared. RESULTS (1) Example 1. In this example, the environment of the In order to verify the effectiveness of the improved ant colony robot was built into the 20 20 grid model and the three algorithm, this paper uses MATLAB software to simulate. It algorithms are tested on the common map. The coordinates is more convincing to use comparative method to carry out of grid Start and grid Goal is (0.5, 19.5) and (19.5, 0.5) experiments under the same experimental conditions. In the (shown in Figure 3), respectively. simulation, the main parameter values of the ACO should be (2) Example 2. In this example, the environment of the determined firstly. The main parameters include number of robot was built into the 30 30 grid model and the three ants, stimulating factor of pheromone concentration, stimulating algorithms are tested on the tunnel map. The coordinates of factor of visibility and pheromone evaporation coefficient. grid Start and grid Goal is (0.5, 8.5) and (15.5, 18.5) (shown Through parameter analysis method (Wu et al., 2010), the in Figure 4), respectively. relationship between each parameter and simulation results (path (3) Example 3. In this example, the environment of the length, number of iterations) can be obtained. According to the robot was built into the 40 40 grid model and the three relationship between each parameter and simulation results (Shi algorithms are tested on the trough map. The coordinates of et al., 2014), we can get the value of the main parameters in the grid Start and grid Goal is (5.5, 34.5) and (28.5, 5.5) (shown ACO. In the simulation, value of each parameter in the ACO is as in Figure 5), respectively. in Table 2: (4) Example 4. In this example, the environment of the robot was built into the 20 20 grid model and the three Comparative Analysis of Path algorithms are tested on the baffle map. The coordinates Planning Algorithms of grid Start and grid Goal is (0.5, 14.5) and (14.5, 14.5) The experiment was divided into four parts according to four (shown in Figure 6), respectively. types of maps(the common map, the tunnel map, the trough map and the baffle map) and three algorithms (the traditional As shown in Figure 3, the optimized path length of the improved ant colony algorithm is 29.2133 and the number ant colony algorithm, the algorithm (Zhao et al., 2016) and of bending times is 6. The improved ant colony algorithm is basically as same as the path planning effect of the ant TABLE 1 | Description of ACO algorithm for solving path planning. colony algorithm (Zhao et al., 2016) on the path length, but it is 25% lower on bending times than the ant colony Algorithm A*MMAS algorithm (Zhao et al., 2016). Compared with the traditional Begin ant colony algorithm, it is 73% reduction in the number of create grid environment bending times. initialize the ant colony system As shown in Figure 4, the optimized length of the improved Repeat ant colony algorithm is 37.3849, and the number of bending for each ant k do times is 7. In the shortest path length, the improved ant colony if grid i ∈ allow then algorithm is basically as same as the algorithm (Zhao et al., 2016). if grid i ∈ taboo then deadlock In the number of bending times, it is 50% decrease than the fallback traditional ant colony algorithm and is 22% decrease than the end if algorithm (Zhao et al., 2016). according to formula (2) and (6) select next grid j As shown in Figure 5, the optimized path length of the Update taboo improved ant colony algorithm is 51.1128. In Figure 6, the end if optimized path length of the improved ant colony algorithm Update pheromone on each iteration by improved MMAS method according to is 50.7280. But in Figures 5, 6, both the traditional ant colony formula (7) and (8) algorithm and the algorithm (Zhao et al., 2016) can’t search the Until algorithm convergence global optimized path. Even as the scale of the problem expands Return best grid serial number and the environment map becomes more and more complex, the END improved algorithm can still perform very well. The results of the three algorithms that run 100 times in same map environments are shown in Table 3. Compared with TABLE 2 | Values of the main parameters in the ACO. the traditional ant colony algorithm and the algorithm (Zhao Number of ants Stimulating Stimulating Pheromone Pheromone et al., 2016), the improved algorithm has a good performance m factor of factor of evaporation intensity on the efficiency. At the same time, it has a good adaptability pheromone visibility coefficient Q in a complicated area. The improved algorithm proposed in concentration this paper can be used not only in the path planning of mobile α β ρ robots, but also in the path planning of robot manipulators 50 1 5 0.5 10 (Yang et al., 2017, 2018). Frontiers in Neurorobotics | www.frontiersin.org 5 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning FIGURE 3 | The test results of three algorithms run on common map. (A) Simulation results in 20*20 grid. (B) Convergence curve. FIGURE 4 | The test results of three algorithms run on tunnel map. (A) Simulation results in 30*30 grid. (B) Convergence curve. FIGURE 5 | The test results of three algorithms run on trough map. (A) Simulation results in 40*40 grid. (B) Convergence curve. (Other two algorithms is failed in trough map). The Retraction Mechanism retraction mechanism are tested on the trough map and the baffle map, respectively. Results Analysis As shown in Figures 7A, 8A, ACO with the retraction In order to show the function of retraction mechanism, the mechanism has higher efficiency and fewer iteration than ACO ACO with the retraction mechanism and ACO without the Frontiers in Neurorobotics | www.frontiersin.org 6 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning FIGURE 6 | The test results of three algorithms run on baffle map. (A) Simulation results in 20*20 grid. (B) Convergence curve. (Other two algorithms is failed in trough map). TABLE 3 | Test results for three algorithms under different maps. Map Algorithm Optimal solution The average of the Average Average time- Number of of the algorithm shortest distance iteration times consuming(sec) bends Common map À 37.4143 38.6335 40 9.22 22 Á 29.2133 29.4506 33 7.26 10 Â 29.2133 29.3807 12 4.89 10 Tunnel map À 38.2133 38.6325 47 26.92 17 Á 37.3849 38.4813 35 20.62 12 Â 37.3849 38.1262 16 17.97 10 Trough map À – – – – – Á – – – – – Â 51.1128 51.8471 40 88.20 13 Baffle map À – – – – – Á – – – – – Â 50.7280 51.0605 15 8.40 13 À: The traditional ant colony algorithm. Á: The algorithm [20]. Â: the improved ant colony algorithm. without the retraction mechanism. When ants fall into deadlock System method, the problem of ant deadlock is solved and the state, the retraction mechanism is used to replace the early death global search ability of the algorithm is improved. strategy, which avoids a large number of ant deaths in one Three algorithms are researched on path planning in the iteration. Therefore, each ant can obtain a path by using the common map, tunnel map, trough map and baffle map, retraction mechanism, which increases the diversity of results respectively. Compared with the traditional ant colony algorithm and is beneficial to find the optimal path. As shown in Figures 7B, and the algorithm (Zhao et al., 2016), the improved ant colony 8B, the number of ant retracted in the initial stage of the algorithm is better in the convergence rate and the bending algorithm is higher than in the middle and later stage of the suppression effect. Compared with the traditional ant colony algorithm and the retraction mechanism can effectively suppress algorithm, the improved ant colony algorithm has more than 65% the decline of the number of ants. reduction in number of iterations and 41% decrease in bending suppression. In addition, the improved ant colony algorithm is 54% lower than the algorithm (Zhao et al., 2016) in number of iterations. To sum up, this paper proves the effectiveness, rapidity DISCUSSION and adaptability of the improved ant colony algorithm in the complex map environment. This paper makes a valuable contribution to the improvement of ant colony algorithm in complicated maps for the mobile robot, especially the improvement on convergence speed, shortest path AUTHOR CONTRIBUTIONS length and bending suppression effect. The estimated function of improved A algorithm is used as the heuristic function to XD and DG proposed the innovation and designed the improve search efficiency and smoothness of path. By employing experiment in this study. ZZ and SL performed the simulation the retraction mechanism and the improved MAX–MIN Ant experiment and analyzed the experiment results. XD checked the Frontiers in Neurorobotics | www.frontiersin.org 7 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning FIGURE 7 | The test results of two algorithms run on trough map. (A) Path planning comparison. (B) Ant retraction number curve. FIGURE 8 | The test results of two algorithms run on baffle map. (A) Path planning comparison. (B) Ant retraction number curve. results. SL wrote the manuscript and DG provided writing advice and Science and Technology Support Program of Sichuan of manuscript. Province (2016GZ0198). FUNDING ACKNOWLEDGMENTS This work was supported by the National Natural Science We acknowledge the support of the School of Mechatronics Foundation of China (61603076) (51305066), Fundamental Engineering and Center of Robot in University of Electronic Research Funds for the Central Universities (ZYGX2016J116), Science and Technology of China. REFERENCES Cetin, O., and Yilmaz, G. (2014). Sigmoid limiting functions and potential field based autonomous air refueling path planning for Arantes, J. D., Arantes, M. D., Toledo, C. F., Júnior, O. T., and Williams, UAVs. J. Intelligent Robot. Syst. 73, 797–810. doi: 10.1007/s10846-013- B. C. (2017). Heuristic and genetic algorithm approaches for UAV path 9902-y planning under critical situation. Int. J. Artificial Intelligence Tools 26, 1–30. Cheng, C. T., Fallahi, K., Leung, H., and Tse, C. K. (2010). An AUVs doi: 10.1142/S0218213017600089 path planner using genetic algorithms with a deterministic crossover Bakdi, A., Hentout, A., Boutami, H., Maoudj, A., Hachour, O., and Bouzouia, operator. IEEE Int. Conference Robot. Automat. 2010, 2995–3000. B. (2016). Optimal path planning and execution for mobile robots using doi: 10.1109/ROBOT.2010.5509335 genetic algorithm and adaptive fuzzy-logic control. Robot. Autonomous Syst. Das, P. K., Behera, H. S., and Panigrahi, B. K. (2016). A hybridization 89, 95–109. doi: 10.1016/j.robot.2016.12.008 of an improved particle swarm optimization and gravitational search Frontiers in Neurorobotics | www.frontiersin.org 8 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning algorithm for multi-robot path planning. Swarm Evol. Comput. 28, 14-28. Song, B., Wang, Z., and Zou, L. (2016). On global smooth path planning for mobile doi: 10.1016/j.swevo.2015.10.011 robots using a novel multimodal delayed PSO algorithm. Cogn. Comput. 9, Deepak, B. B. V. L., Parhi, D. R., and Kundu, S. (2012). Innate immune based 5–17. doi: 10.1007/s12559-016-9442-4 path planner of an autonomous mobile robot. Procedia Eng. 38, 2663–2671. Stützle, T., and Hoos, H. H. (2000). MAX-MIN ant system. Fut. Gen. Comp. Syst. doi: 10.1016/j.proeng.2012.06.313 16, 889–914. doi: 10.1016/S0167-739X(00)00043-1 Duchon, F., Babinec, A., Kajan, M., Beno, P., Florek, M., Fico, T., et al. (2014). Path Wang, D. S., and Yu, H. F. (2011). Path planning of mobile robot in dynamic planning with modified A star algorithm for a mobile robot. Procedia Eng. 96, environments. Int. Conference Intelligent Control Info. Process. 2, 691–696. 59-69. doi: 10.1016/j.proeng.2014.12.098 doi: 10.1109/ICICIP.2011.6008338 He, W., Chen, Y., and Yin, Z. (2016a). Adaptive neural network control of an Wang, P., Lin, H. T., and Wang, T. S. (2016). An improved ant colony system uncertain robot with full-state constraints. IEEE Trans. Cybernet. 46, 620–629. algorithm for solving the IP traceback problem. Elsevier Science Inc. 326, doi: 10.1109/TCYB.2015.2411285 172–187. doi: 10.1016/j.ins.2015.07.006 He, W., Dong, Y., and Sun, C. (2016b). Adaptive neural impedance control of a Wu, J., Li, T., and Xu, B. (2013). Force optimization of planar 2-DOF robotic manipulator with input saturation. IEEE Trans. Syst. Man Cybernet. parallel manipulators with actuation redundancy considering deformation. Syst. 46, 334–344. doi: 10.1109/TSMC.2015.2429555 Proc. Inst. Mech. Eng. Part C J. Mech. Eng. Sci. 227, 1371-1377. He, W., Yan, Z., Sun, C., and Chen, Y. (2017a). Adaptive neural network control doi: 10.1177/0954406212458055 of a flapping wing micro aerial vehicle with disturbance observer. IEEE Trans. Wu, J., Wang, J., and You, Z. (2010). An overview of dynamic parameter Cybernet. 47, 3452–3465. doi: 10.1109/TCYB.2017.2720801 identification of robots. Robot. Computer Integr. Manufacturing 26, 414–419. He, W., Yin, Z., and Sun, C. (2017b). Adaptive neural network control of a marine doi: 10.1016/j.rcim.2010.03.013 vessel with constraints using the asymmetric barrier lyapunov function. IEEE Yang, C., Huang, K., Cheng, H., Li, Y., and Su, C. (2017). Haptic identification by Trans. Cybernet. 47, 1641–1651. doi: 10.1109/TCYB.2016.2554621 ELM-controlled uncertain manipulator. IEEE Trans. Syst. Man Cybernet. Syst. He, W., and Zhang, S. (2017). Control design for nonlinear flexible wings 47, 2398–2409. doi: 10.1109/TSMC.2017.2676022 of a robotic aircraft. IEEE Trans. Control Syst. Technol. 25, 351–357. Yang, C., Jiang, Y., He, W., Na, J., Li, Z., and Xu, B. (2018). Adaptive doi: 10.1109/TCST.2016.2536708 parameter estimation and control design for robot manipulators with Jiang, K., and Li, C. G. (2014). Path planning based on fuzzy logic algorithm finite-time convergence. IEEE Trans. Ind. Electronics 65, 8112–8123. for robots in hierarchical control. Appl. Mech. Mater. 644–650,701–704. doi: 10.1109/TIE.2018.2803773 doi: 10.4028/www.scientific.net/amm.644-650.701-704 Yen, C. T., and Cheng, M. F. (2016). A study of fuzzy control with ant Jovanovic, R., Tuba, M., and Vo,ß, S. (2016). An ant colony optimization algorithm colony algorithm used in mobile robot for shortest path planning and for partitioning graphs with supply and demand. Appl. Soft Comput. 41, obstacle avoidance. Microsyst. Technol. 2016, 1–11. doi: 10.1007/s00542-016- 317–330. doi: 10.1016/j.asoc.2016.01.013 3192-9 Li, Q., Zhang, C., Han, C. W., Zhang, T., and Zhang, W. (2013). Zeng, M., Xi, L., and Xiao, A. (2016). The free step length ant colony Path planning based fuzzy logic algorithm for mobile robots in dynamic algorithm in mobile robot path planning. Adv. Robot. 30, 1509–1514. environments. J. Central South Univ. Sci. Technol. 2013, 105–107. doi: 10.1080/01691864.2016.1240627 doi: 10.1109/CCDC.2013.6561434 Zhang, W., Gong, X., Han, G., and Zhao, Y. (2017). An improved ant colony Li, W. H., Yang, C. G., Jiang, Y. M., and Su, C. Y. (2017). Motion planning algorithm for path planning in one scenic area with many spots. IEEE Access. 5, for omnidirectional wheeled mobile robot by potential field method. J. Adv. 13260–13269. doi: 10.1109/ACCESS.2017.2723892 Transport. 3, 1–11. doi: 10.1155/2017/4961383 Zhao, J., Cheng, D., and Hao, C. (2016). An improved ant colony algorithm for Lin, D., Shen, B., Liu, Y., Alsaadi, F. E., Alsaedi, A., and Cheng, H. (2017). solving the path planning problem of the omnidirectional mobile vehicle. Math. Genetic algorithm-based compliant robot path planning: an improved Prob. Eng. 2016, 1–10. doi: 10.1155/2016/7672839 Bi-RRT-based initialization method. Assembly Automat. 37, 261–270. Zhou, Z., Nie, Y., and Min, G. (2013). Enhanced ant colony optimization algorithm doi: 10.1108/AA-12-2016-173 for global path planning of mobile robots. Int. Conference Comput. Info. Sci. Liu, J. , Yang, J., Liu, H., Tian, X., and Gao, M. (2016). An improved 2013, 698–701. doi: 10.1109/ICCIS.2013.189 ant colony algorithm for robot path planning. Soft Comput. 1, 1–11. doi: 10.1007/s00500-016-2161-7 Conflict of Interest Statement: The authors declare that the research was Miao, H., and Tian, Y. C. (2013). Dynamic robot path planning using an conducted in the absence of any commercial or financial relationships that could enhanced simulated annealing approach. Appl. Math. Comput. 222, 420–437. be construed as a potential conflict of interest. doi: 10.1016/j.amc.2013.07.022 Nair, R. R., Behera, L., Kumar, V., and Jamshidi, M. M. (2015). Multisatellite Copyright © 2019 Dai, Long, Zhang and Gong. This is an open-access article formation control for remote sensing applications using artificial potential distributed under the terms of the Creative Commons Attribution License (CC BY). field and adaptive fuzzy sliding mode control. IEEE Syst. J. 9, 508–518. The use, distribution or reproduction in other forums is permitted, provided the doi: 10.1109/jsyst.2014.2335442 original author(s) and the copyright owner(s) are credited and that the original Shi, E., Chen, M., Li, J., and Huang, Y. (2014). Research on method of global path- publication in this journal is cited, in accordance with accepted academic practice. planning for mobile robot based on ant-colony algorithm. Trans. Chin. Soc. No use, distribution or reproduction is permitted which does not comply with these Agri. Machinery 45, 53–57. doi: 10.6041/j.issn.1000-1298.2014.06.009 terms. Frontiers in Neurorobotics | www.frontiersin.org 9 April 2019 | Volume 13 | Article 15 http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Frontiers in Neurorobotics Pubmed Central

Mobile Robot Path Planning Based on Ant Colony Algorithm With A* Heuristic Method

Frontiers in Neurorobotics , Volume 13 – Apr 16, 2019

Loading next page...
 
/lp/pubmed-central/mobile-robot-path-planning-based-on-ant-colony-algorithm-with-a-uNv06Jygtp

References (36)

Publisher
Pubmed Central
Copyright
Copyright © 2019 Dai, Long, Zhang and Gong.
ISSN
1662-5218
eISSN
1662-5218
DOI
10.3389/fnbot.2019.00015
Publisher site
See Article on Publisher Site

Abstract

METHODS published: 16 April 2019 doi: 10.3389/fnbot.2019.00015 Mobile Robot Path Planning Based on Ant Colony Algorithm With A Heuristic Method 1,2 1 1 1,2 Xiaolin Dai , Shuai Long , Zhiwen Zhang and Dawei Gong * 1 2 School of Mechatronics Engineering, University of Electronic Science and Technology of China, Chengdu, China, Center of Robot, University of Electronic Science and Technology of China, Chengdu, China This paper proposes an improved ant colony algorithm to achieve efficient searching capabilities of path planning in complicated maps for mobile robot. The improved ant colony algorithm uses the characteristics of A algorithm and MAX-MIN Ant system. Firstly, the grid environment model is constructed. The evaluation function of A algorithm and the bending suppression operator are introduced to improve the heuristic information of the Ant colony algorithm, which can accelerate the convergence speed and increase the smoothness of the global path. Secondly, the retraction mechanism is introduced to solve the deadlock problem. Then the MAX-MIN ant system is transformed into local diffusion pheromone and only the best solution from iteration trials can be added to pheromone update. And, strengths of the pheromone trails are effectively limited for Edited by: avoiding premature convergence of search. This gives an effective improvement and Caixia Cai, high performance to ACO in complex tunnel, trough and baffle maps and gives a better Agency for Science, Technology and ∗ result as compare to traditional versions of ACO. The simulation results show that the Research (A STAR), Singapore improved ant colony algorithm is more effective and faster. Reviewed by: Wenchao Gao, Keywords: path planning, ant colony algorithm, A algorithm, bending suppression, retraction mechanism Institute for Infocomm Research (A STAR), Singapore Ran Duan, INTRODUCTION Hong Kong Polytechnic University, Hong Kong Bonan Huang, Path planning is a key issue in the field of mobile robot research. Its main purpose is to find an Northeastern University, China optimal or suboptimal, safe and collision-free path from the starting point to the target point in the environment with obstacle (Cheng et al., 2010; Deepak et al., 2012; Zhou et al., 2013). According *Correspondence: Dawei Gong to the degree of intelligence in the process of path planning, mobile robot path planning can be pzhzhx@126.com divided into traditional path planning and intelligent path planning. The traditional path planning algorithm includes simulated annealing algorithm (Miao and Tian, 2013), potential function theory Received: 20 December 2018 (Cetin and Yilmaz, 2014; Nair et al., 2015), fuzzy logic algorithm (Li et al., 2013; Jiang and Li, 2014; Accepted: 25 March 2019 Bakdi et al., 2016) and so on. However, these traditional methods can’t be further improved in path Published: 16 April 2019 search efficiency and path optimization. Intelligent path planning algorithm includes Ant Colony Citation: Optimization (ACO) (Jovanovic et al., 2016; Wang et al., 2016), genetic algorithm (Arantes et al., Dai X, Long S, Zhang Z and Gong D 2017; Lin et al., 2017), neural network (He et al., 2016a, 2017a,b) and particle swarm algorithm (Das (2019) Mobile Robot Path Planning et al., 2016; Song et al., 2016) and so on. The ant colony algorithm has the advantages of strong Based on Ant Colony Algorithm With robustness, good global optimization ability and inherent parallelism. Moreover, it easily combines A Heuristic Method. with multiple heuristic algorithms to improve the performance of algorithms. So it is widely used Front. Neurorobot. 13:15. doi: 10.3389/fnbot.2019.00015 in path planning. Frontiers in Neurorobotics | www.frontiersin.org 1 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning However, due to the randomness of probabilistic transfer and the inappropriateness of pheromone intensity update, the traditional ACO will easily fall into the local optimum and tend to poor convergence. To this end, many scholars delivered a variety of improved methods to solve problems regarding pheromone update and path search strategy (Stützle and Hoos, 2000; Zeng et al., 2016; Zhao et al., 2016; Zhang et al., 2017). In Stützle and Hoos (2000), an Ant Colony System (ACS) algorithm was proposed to speed up the convergence rate of ACO by updating pheromones on the path of the optimal ant of each generation. In Zhao et al. (2016), by adaptively changing the volatilization rate and adjusting the pheromone updating formula, the search ability of the ant colony and the convergence rate of the algorithm were improved. In Zhao et al. (2016), some intelligent algorithm was proposed to generate an initial path, which can be transformed into the initial pheromone distribution to avoid blind search of ant colony. In Zhang et al. (2017), the path information (such as the crowded path and the steep path weight) was added into FIGURE 1 | Environment model. the initial pheromone matrix, which could affects the efficiency of the algorithm. In Zhao et al. (2016), the heuristic function was adjusted to improve the convergence rate of the algorithm (the robot can move). In order to identify obstacles, the white grid according to the target point. In Zeng et al. (2016), it unlimited cell is represented by 0 and the gray grid unit is represented by 1. step length of finding optimal path so that the improved ACO The grid method is simple and effective to create and maintain could find a shorter path and its convergence was better. In grid model. Moreover, the grid method have strong adaptability addition, many scholars have combined the ant colony algorithm for obstacle. This method is convenient for computer storage with other (intelligent) algorithms (He et al., 2016b; Liu et al., and processing. 2016; Yen and Cheng, 2016; He and Zhang, 2017) to improve the The grid model was placed into two-dimensional coordinate convergence rate and the smooth of path. In Liu et al. (2016), the system. And then serial number method is adopted to mark each geometric method was used to optimize path. Also in Liu et al. grid. In N N grid map, the starting node is named after Start (2016), the force factor in the artificial potential field method and the target node is named after Goal. The position coordinates is transformed into local diffusion pheromone to improve the x, y corresponding to any grid whose grid number is R as follow: ability of the ant colony algorithm to find the obstacle. In Yen and Cheng (2016), the fuzzy ant colony optimization method was mod (R, N) − 0.5 if mod (R, N)! = 0 proposed to minimize the iterative learning error. x = N + mod (R, N) − 0.5 otherwise (1) In this paper, an effective version of ant colony algorithm y = N + 0.5 − ceil is achieved. It utilizes the evaluation function of A algorithm to improve the heuristic information of Ant colony algorithm, Where mod is the surplus operation, ceil rounds the elements to which accelerates the convergence speed during the search. And the nearest integers toward infinity. MAX–MIN Ant System is used to make the global search ability better by updating the path pheromone of the optimal network. Ant Colony Algorithm At the same time, the bending suppression operator is introduced Heuristic Strategy With Direction Information to improve heuristic information, which aims to optimize the In the traditional ACO, the probability of the next node is selected smoothness of the path. The problem of deadlock is solved by by roulette wheel method as follows: using the retraction mechanism. All these procedures not only give an effective improvement and better performance to ACO, α β τ (t) · η (t)  ( ij ) ( ij ) but also give the best results as compare to traditional versions of s ∈ allow k α β (τ (t)) ·(η (t)) is is P (t) = (2) s∈allow the algorithm (Zhao et al., 2016) and ACO in complex tunnel, ij 0 s ∈/ allow trough and baffle maps. The simulation results show that the proposed algorithm is effective and fast. η (t) = ij ij MATERIALS AND METHODS 2 2 d = (x − x ) + (y − y ) ij j i j i Environment Model The work environment is built by using the grid model, which Where τ is the pheromone trail of the path grid i to grid j, and ij divides the robot working space into N N squares. As shown in η is the heuristic information of the path grid i to grid j. α is the ij Figure 1, the gray grids are represented as obstacles (the grid with stimulating factor of pheromone concentration which determine barriers) and the white grids are represented as free grid squares the relative influence of the pheromone trail. β is the stimulating Frontiers in Neurorobotics | www.frontiersin.org 2 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning factor of visibility which determine the relative influence of the The heuristic cost of A algorithm is expressed by the heuristic information. d is the distance between node i and node estimated function, and the estimated function equation f (n) is ij j. (x , y ) and (x , y ) is the coordinates of grid i and grid j. allow is as follows: i i j j k the collection of grids which ants can choose when ants in the grid f n = g n + h n (5) i (in other words, they are the grids around the grid i except the ( ) ( ) ( ) obstacle grid and taboo grid).   1/2 2 2 h(n) = n − g + n − g x x y y Coverage and Updating Strategy  1/2 g (n) = (n − s ) + n − s x x y y According to the traditional ACO, the next node is decided by the roulette wheel method and it is repeated until the target point is where g(n) is the minimum cost from the source node to the obtained. After each iteration is completed, pheromone trails are current node. h(n) is the minimum cost from the current node to updated in line with the length of path planning. For each trial the destination node. n and n are the coordinates of the current during pheromone update, all imperfect pheromones evaporates x y node n . g and g are the coordinates of the target node g, s , and only the best pheromones are updated to trials history, x x y because it enables ants to neglect all substandard pheromone and s are the coordinates of the initial node s. trails and improve its coverage efficiency to find a shorter path. The estimated function of A algorithm is used as heuristic Formula (3) is used to update the pheromone quantity on each information to search for global optimal path in ant colony vertex at the end of each cycle: algorithm, and the bending suppression operator is added to the heuristic value of ant colony algorithm to reduce the number of bending times and the large cumulative turning angle. The τ = (1 − ρ)τ + 1τ ij ij ij m improved heuristic information formula is as follows: (3) 1τ = 1τ , 0 < ρ < 1  ij ij k=1 η (t) = (6) ij h(n) + g (n) + cost(bend) where m is the number of ants. ρ is pheromone evaporation rate. cost bend = ϕ · turn + ψ · thita 1τ represents the value of pheromone that the ant k leaves in ij the path of grid i to grid j. This article uses the ant-cycle-system where Q is a constant more than 1. cost(bend) is a bending model, and 1τ is defined as follows: ij suppression operator. turn is the number of turns from node n− 1(previous node) to node n+ 1 (next node). thita is the angle between the line segment of node n − 1 to node n (current node) Q /L (t) if arc i, j is used by k in iteration t k 1 k 1τ k = (4) ij and the line segment of node n to node n + 1. ϕ is the coefficient 0 otherwise converting turning times into grid length. ψ is the coefficient converting angle into grid length. Where Q is a constant. L (t) is the length of the path that the 1 K ant k is looking for. Solve the Deadlock Problem When the robot environment is more complex (especially the Improved Ant Colony Algorithm ants go into the environment of concave obstacles), due to the The traditional ACO has the following shortcomings: Due to the presence of the taboo table, the ants may fall into a deadlock state lack of initial pheromone and the unapparent difference of the without the next grid to move. As shown in Figure 2, when the heuristic value between adjacent grids, it usually requires a longer ant travels from the grid T to the grid S, the next optional grid is search time, which leads to the slow convergence rate. When grid C. At this time, the ant is trapped in a deadlock state and it cannot model is complex, the robot maybe fall into a deadlock state in move to its surrounding grid. which the robot cannot move to the surrounding grids. In the For the deadlock problem, Wang and Yu (2011) adopted grid map, the path planning with traditional ACO may have more the early death strategy, which deleted the ants trapped in a bending times and big cumulative bending angle. To solve the deadlock state from the ant colony and did not update the global above problems, this paper makes the following improvements. pheromone. However, when more of the ants are trapped in the deadlock state, the number of ants that can reach the goal is Heuristic Information Based on A Algorithm significantly reduced, which results in a decrease in the diversity A algorithm (Duchon et al., 2014) is the most effective direct of solutions and is not conducive to the search of optimal path search method for solving the shortest path in static road for ants. In this paper, the improvement measure is that the ants network. It is developed on the basis of Dijkstra algorithm, adopt retraction mechanism when they fall into the deadlock which can avoid blind search to improve search efficiency. In this state. As shown in Figure 2, the ant, which has walked into paper, A algorithm is used as the heuristic information of path the grid, is trapped in the deadlock state, and the improved searching to improve the convergence speed of the algorithm strategy allows the ant to roll back one step and updates the and obtain the better path. The bending suppression operator is taboo table information. If the ant is still trapped into a deadlock added to the heuristic information to reduce bending times and state, the ant will continue to rollback untill grid T. At this cumulative bending angle. moment, the ant escapes the deadlock area. Since the deadlock Frontiers in Neurorobotics | www.frontiersin.org 3 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning represent different weight coefficient and are set by analyzing the robot’s structure and kinematics (Wu et al., 2013; Li et al., 2017). The w and w can convert turning angle and turning 1 2 times into grid length, respectively. V represents the constant robot speed of a mobile robot. W represents the angular speed of a robot mobile robot as it turns. t represents the time of acceleration and deceleration as the mobile robot turns once. (2) Pheromone trail limits. In order to avoid the situation that the traditional ant colony algorithm may falls into local optimal solution and loses the further search space ability by pheromone accumulation, the pheromone trail of the MMAS is limited in the upper limits and lower limits Tau Tau . The formula is: min, max,  Tau , Tau ≤ Tau min min Tau = Tau, Tau < Tau ≤ Tau (8) min max Tau , Tau > Tau max min Aco Procedure FIGURE 2 | Deadlock state diagram. To sum up, specific steps of mobile robot path planning based on the improved ant colony algorithm are as follows: Step 1: The working environment is modeled by the grid edge may be the part of global optimal path, no pheromone method, and the starting point start and the target point goal punishment is carried out on the deadlock edge. The retraction of the mobile robot are given. mechanism cannot prevent ants from entering a deadlock state, Step 2: Initialize the ant system. Set the number m of but it lets the deadlocked ants return back to the previous ants, parameter α which determines the relative influence grid until there is a feasible grid around the ants, so the ACO of the pheromone trail, parameter β which determines the with the retraction mechanism has higher efficiency and fewer heuristic value, the global pheromone volatilization coefficient iterations. The ACO with the retraction mechanism and without ρ, pheromone intensity Q and other related parameters. the retraction mechanism is compared in section The Retraction 1 Step 3: Update taboo table. Place the ant k (k = 1, 2, · · · , m) Mechanism Results Analysis below. on the current node and add the current node to the Max–Min Ant System corresponding taboo table. As the traditional ant colony algorithm may cause premature Step 4: Process deadlock. According to the taboo table, it will convergence and precocious phenomenon, it needs to improve judge whether ants are trapped in a deadlock state. If the algorithm to solve these problem. The MAX-MIN Ant System ants are in a deadlock state, the retraction mechanism will be (MMAS) (Stützle and Hoos, 2000) can solve these problems well. adopted and the deadlock node will be added to the taboo (1) Pheromone trail updating. After each iteration trial, the table. Conversely, it will judge whether the ants reach the target pheromone is submitted into update history in traditional point. If the ants reach the target point, it will turn to Step 6, ant colony algorithm. While in the MMAS, only the path otherwise it will turn to Step 5. pheromone of the optimal network is updated after the iteration Step 5: Select the next grid. It will calculate the heuristic is completed. Accordingly, the modified pheromone trail update function according to formula (6), and calculate the rule is stated by: probability function according to formula (2). Finally, it will use the roulette method to select the next feasible grid. If best τ (t + 1) = (1 − ρ)τ (t) + 1τ (7) ij ij ij the ants reach the target grid, it will turn to Step 6, otherwise it will turn to Step 3. Q Q 1 3 1τ (t) = + ij best best Step 6: If the ants reach the target node, it will repeat Step 3 turn until each ant completes the search target during its iteration best C = ω Cals l + ω Turns l 1 2 turn process and then turn to Step 7. Step 7: Update pheromone. After each iteration, if the robot ω = W number of iterations satisfies inequality N ≤ N , it max robot will update the path pheromone and determine whether it ω = V × t 2 robot a meets the convergence conditions. If it meets the convergence best where Q is a constant more than 1.L denotes to the shortest conditions, it will withdraw. If it does not meet, it will turn path currently found by the algorithm. Cals(l) represents the sum to Step 3. If the number of iterations satisfies inequality N > of all the angles of turning on the best optimized path. Turns(l) N , it will be not counted further. The final result is output max is the sum of the turns on the best optimized path. w and w as long as the end condition is satisfied. 1 2 Frontiers in Neurorobotics | www.frontiersin.org 4 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning The implementation process of improved ant colony algorithm is the improved ant colony algorithm proposed in this paper) are as in Table 1. simulated on each map in turn. The convergence speed, shortest path length and bending suppression effect of those algorithms are compared. RESULTS (1) Example 1. In this example, the environment of the In order to verify the effectiveness of the improved ant colony robot was built into the 20 20 grid model and the three algorithm, this paper uses MATLAB software to simulate. It algorithms are tested on the common map. The coordinates is more convincing to use comparative method to carry out of grid Start and grid Goal is (0.5, 19.5) and (19.5, 0.5) experiments under the same experimental conditions. In the (shown in Figure 3), respectively. simulation, the main parameter values of the ACO should be (2) Example 2. In this example, the environment of the determined firstly. The main parameters include number of robot was built into the 30 30 grid model and the three ants, stimulating factor of pheromone concentration, stimulating algorithms are tested on the tunnel map. The coordinates of factor of visibility and pheromone evaporation coefficient. grid Start and grid Goal is (0.5, 8.5) and (15.5, 18.5) (shown Through parameter analysis method (Wu et al., 2010), the in Figure 4), respectively. relationship between each parameter and simulation results (path (3) Example 3. In this example, the environment of the length, number of iterations) can be obtained. According to the robot was built into the 40 40 grid model and the three relationship between each parameter and simulation results (Shi algorithms are tested on the trough map. The coordinates of et al., 2014), we can get the value of the main parameters in the grid Start and grid Goal is (5.5, 34.5) and (28.5, 5.5) (shown ACO. In the simulation, value of each parameter in the ACO is as in Figure 5), respectively. in Table 2: (4) Example 4. In this example, the environment of the robot was built into the 20 20 grid model and the three Comparative Analysis of Path algorithms are tested on the baffle map. The coordinates Planning Algorithms of grid Start and grid Goal is (0.5, 14.5) and (14.5, 14.5) The experiment was divided into four parts according to four (shown in Figure 6), respectively. types of maps(the common map, the tunnel map, the trough map and the baffle map) and three algorithms (the traditional As shown in Figure 3, the optimized path length of the improved ant colony algorithm is 29.2133 and the number ant colony algorithm, the algorithm (Zhao et al., 2016) and of bending times is 6. The improved ant colony algorithm is basically as same as the path planning effect of the ant TABLE 1 | Description of ACO algorithm for solving path planning. colony algorithm (Zhao et al., 2016) on the path length, but it is 25% lower on bending times than the ant colony Algorithm A*MMAS algorithm (Zhao et al., 2016). Compared with the traditional Begin ant colony algorithm, it is 73% reduction in the number of create grid environment bending times. initialize the ant colony system As shown in Figure 4, the optimized length of the improved Repeat ant colony algorithm is 37.3849, and the number of bending for each ant k do times is 7. In the shortest path length, the improved ant colony if grid i ∈ allow then algorithm is basically as same as the algorithm (Zhao et al., 2016). if grid i ∈ taboo then deadlock In the number of bending times, it is 50% decrease than the fallback traditional ant colony algorithm and is 22% decrease than the end if algorithm (Zhao et al., 2016). according to formula (2) and (6) select next grid j As shown in Figure 5, the optimized path length of the Update taboo improved ant colony algorithm is 51.1128. In Figure 6, the end if optimized path length of the improved ant colony algorithm Update pheromone on each iteration by improved MMAS method according to is 50.7280. But in Figures 5, 6, both the traditional ant colony formula (7) and (8) algorithm and the algorithm (Zhao et al., 2016) can’t search the Until algorithm convergence global optimized path. Even as the scale of the problem expands Return best grid serial number and the environment map becomes more and more complex, the END improved algorithm can still perform very well. The results of the three algorithms that run 100 times in same map environments are shown in Table 3. Compared with TABLE 2 | Values of the main parameters in the ACO. the traditional ant colony algorithm and the algorithm (Zhao Number of ants Stimulating Stimulating Pheromone Pheromone et al., 2016), the improved algorithm has a good performance m factor of factor of evaporation intensity on the efficiency. At the same time, it has a good adaptability pheromone visibility coefficient Q in a complicated area. The improved algorithm proposed in concentration this paper can be used not only in the path planning of mobile α β ρ robots, but also in the path planning of robot manipulators 50 1 5 0.5 10 (Yang et al., 2017, 2018). Frontiers in Neurorobotics | www.frontiersin.org 5 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning FIGURE 3 | The test results of three algorithms run on common map. (A) Simulation results in 20*20 grid. (B) Convergence curve. FIGURE 4 | The test results of three algorithms run on tunnel map. (A) Simulation results in 30*30 grid. (B) Convergence curve. FIGURE 5 | The test results of three algorithms run on trough map. (A) Simulation results in 40*40 grid. (B) Convergence curve. (Other two algorithms is failed in trough map). The Retraction Mechanism retraction mechanism are tested on the trough map and the baffle map, respectively. Results Analysis As shown in Figures 7A, 8A, ACO with the retraction In order to show the function of retraction mechanism, the mechanism has higher efficiency and fewer iteration than ACO ACO with the retraction mechanism and ACO without the Frontiers in Neurorobotics | www.frontiersin.org 6 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning FIGURE 6 | The test results of three algorithms run on baffle map. (A) Simulation results in 20*20 grid. (B) Convergence curve. (Other two algorithms is failed in trough map). TABLE 3 | Test results for three algorithms under different maps. Map Algorithm Optimal solution The average of the Average Average time- Number of of the algorithm shortest distance iteration times consuming(sec) bends Common map À 37.4143 38.6335 40 9.22 22 Á 29.2133 29.4506 33 7.26 10 Â 29.2133 29.3807 12 4.89 10 Tunnel map À 38.2133 38.6325 47 26.92 17 Á 37.3849 38.4813 35 20.62 12 Â 37.3849 38.1262 16 17.97 10 Trough map À – – – – – Á – – – – – Â 51.1128 51.8471 40 88.20 13 Baffle map À – – – – – Á – – – – – Â 50.7280 51.0605 15 8.40 13 À: The traditional ant colony algorithm. Á: The algorithm [20]. Â: the improved ant colony algorithm. without the retraction mechanism. When ants fall into deadlock System method, the problem of ant deadlock is solved and the state, the retraction mechanism is used to replace the early death global search ability of the algorithm is improved. strategy, which avoids a large number of ant deaths in one Three algorithms are researched on path planning in the iteration. Therefore, each ant can obtain a path by using the common map, tunnel map, trough map and baffle map, retraction mechanism, which increases the diversity of results respectively. Compared with the traditional ant colony algorithm and is beneficial to find the optimal path. As shown in Figures 7B, and the algorithm (Zhao et al., 2016), the improved ant colony 8B, the number of ant retracted in the initial stage of the algorithm is better in the convergence rate and the bending algorithm is higher than in the middle and later stage of the suppression effect. Compared with the traditional ant colony algorithm and the retraction mechanism can effectively suppress algorithm, the improved ant colony algorithm has more than 65% the decline of the number of ants. reduction in number of iterations and 41% decrease in bending suppression. In addition, the improved ant colony algorithm is 54% lower than the algorithm (Zhao et al., 2016) in number of iterations. To sum up, this paper proves the effectiveness, rapidity DISCUSSION and adaptability of the improved ant colony algorithm in the complex map environment. This paper makes a valuable contribution to the improvement of ant colony algorithm in complicated maps for the mobile robot, especially the improvement on convergence speed, shortest path AUTHOR CONTRIBUTIONS length and bending suppression effect. The estimated function of improved A algorithm is used as the heuristic function to XD and DG proposed the innovation and designed the improve search efficiency and smoothness of path. By employing experiment in this study. ZZ and SL performed the simulation the retraction mechanism and the improved MAX–MIN Ant experiment and analyzed the experiment results. XD checked the Frontiers in Neurorobotics | www.frontiersin.org 7 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning FIGURE 7 | The test results of two algorithms run on trough map. (A) Path planning comparison. (B) Ant retraction number curve. FIGURE 8 | The test results of two algorithms run on baffle map. (A) Path planning comparison. (B) Ant retraction number curve. results. SL wrote the manuscript and DG provided writing advice and Science and Technology Support Program of Sichuan of manuscript. Province (2016GZ0198). FUNDING ACKNOWLEDGMENTS This work was supported by the National Natural Science We acknowledge the support of the School of Mechatronics Foundation of China (61603076) (51305066), Fundamental Engineering and Center of Robot in University of Electronic Research Funds for the Central Universities (ZYGX2016J116), Science and Technology of China. REFERENCES Cetin, O., and Yilmaz, G. (2014). Sigmoid limiting functions and potential field based autonomous air refueling path planning for Arantes, J. D., Arantes, M. D., Toledo, C. F., Júnior, O. T., and Williams, UAVs. J. Intelligent Robot. Syst. 73, 797–810. doi: 10.1007/s10846-013- B. C. (2017). Heuristic and genetic algorithm approaches for UAV path 9902-y planning under critical situation. Int. J. Artificial Intelligence Tools 26, 1–30. Cheng, C. T., Fallahi, K., Leung, H., and Tse, C. K. (2010). An AUVs doi: 10.1142/S0218213017600089 path planner using genetic algorithms with a deterministic crossover Bakdi, A., Hentout, A., Boutami, H., Maoudj, A., Hachour, O., and Bouzouia, operator. IEEE Int. Conference Robot. Automat. 2010, 2995–3000. B. (2016). Optimal path planning and execution for mobile robots using doi: 10.1109/ROBOT.2010.5509335 genetic algorithm and adaptive fuzzy-logic control. Robot. Autonomous Syst. Das, P. K., Behera, H. S., and Panigrahi, B. K. (2016). A hybridization 89, 95–109. doi: 10.1016/j.robot.2016.12.008 of an improved particle swarm optimization and gravitational search Frontiers in Neurorobotics | www.frontiersin.org 8 April 2019 | Volume 13 | Article 15 Dai et al. Mobile Robot Path Planning algorithm for multi-robot path planning. Swarm Evol. Comput. 28, 14-28. Song, B., Wang, Z., and Zou, L. (2016). On global smooth path planning for mobile doi: 10.1016/j.swevo.2015.10.011 robots using a novel multimodal delayed PSO algorithm. Cogn. Comput. 9, Deepak, B. B. V. L., Parhi, D. R., and Kundu, S. (2012). Innate immune based 5–17. doi: 10.1007/s12559-016-9442-4 path planner of an autonomous mobile robot. Procedia Eng. 38, 2663–2671. Stützle, T., and Hoos, H. H. (2000). MAX-MIN ant system. Fut. Gen. Comp. Syst. doi: 10.1016/j.proeng.2012.06.313 16, 889–914. doi: 10.1016/S0167-739X(00)00043-1 Duchon, F., Babinec, A., Kajan, M., Beno, P., Florek, M., Fico, T., et al. (2014). Path Wang, D. S., and Yu, H. F. (2011). Path planning of mobile robot in dynamic planning with modified A star algorithm for a mobile robot. Procedia Eng. 96, environments. Int. Conference Intelligent Control Info. Process. 2, 691–696. 59-69. doi: 10.1016/j.proeng.2014.12.098 doi: 10.1109/ICICIP.2011.6008338 He, W., Chen, Y., and Yin, Z. (2016a). Adaptive neural network control of an Wang, P., Lin, H. T., and Wang, T. S. (2016). An improved ant colony system uncertain robot with full-state constraints. IEEE Trans. Cybernet. 46, 620–629. algorithm for solving the IP traceback problem. Elsevier Science Inc. 326, doi: 10.1109/TCYB.2015.2411285 172–187. doi: 10.1016/j.ins.2015.07.006 He, W., Dong, Y., and Sun, C. (2016b). Adaptive neural impedance control of a Wu, J., Li, T., and Xu, B. (2013). Force optimization of planar 2-DOF robotic manipulator with input saturation. IEEE Trans. Syst. Man Cybernet. parallel manipulators with actuation redundancy considering deformation. Syst. 46, 334–344. doi: 10.1109/TSMC.2015.2429555 Proc. Inst. Mech. Eng. Part C J. Mech. Eng. Sci. 227, 1371-1377. He, W., Yan, Z., Sun, C., and Chen, Y. (2017a). Adaptive neural network control doi: 10.1177/0954406212458055 of a flapping wing micro aerial vehicle with disturbance observer. IEEE Trans. Wu, J., Wang, J., and You, Z. (2010). An overview of dynamic parameter Cybernet. 47, 3452–3465. doi: 10.1109/TCYB.2017.2720801 identification of robots. Robot. Computer Integr. Manufacturing 26, 414–419. He, W., Yin, Z., and Sun, C. (2017b). Adaptive neural network control of a marine doi: 10.1016/j.rcim.2010.03.013 vessel with constraints using the asymmetric barrier lyapunov function. IEEE Yang, C., Huang, K., Cheng, H., Li, Y., and Su, C. (2017). Haptic identification by Trans. Cybernet. 47, 1641–1651. doi: 10.1109/TCYB.2016.2554621 ELM-controlled uncertain manipulator. IEEE Trans. Syst. Man Cybernet. Syst. He, W., and Zhang, S. (2017). Control design for nonlinear flexible wings 47, 2398–2409. doi: 10.1109/TSMC.2017.2676022 of a robotic aircraft. IEEE Trans. Control Syst. Technol. 25, 351–357. Yang, C., Jiang, Y., He, W., Na, J., Li, Z., and Xu, B. (2018). Adaptive doi: 10.1109/TCST.2016.2536708 parameter estimation and control design for robot manipulators with Jiang, K., and Li, C. G. (2014). Path planning based on fuzzy logic algorithm finite-time convergence. IEEE Trans. Ind. Electronics 65, 8112–8123. for robots in hierarchical control. Appl. Mech. Mater. 644–650,701–704. doi: 10.1109/TIE.2018.2803773 doi: 10.4028/www.scientific.net/amm.644-650.701-704 Yen, C. T., and Cheng, M. F. (2016). A study of fuzzy control with ant Jovanovic, R., Tuba, M., and Vo,ß, S. (2016). An ant colony optimization algorithm colony algorithm used in mobile robot for shortest path planning and for partitioning graphs with supply and demand. Appl. Soft Comput. 41, obstacle avoidance. Microsyst. Technol. 2016, 1–11. doi: 10.1007/s00542-016- 317–330. doi: 10.1016/j.asoc.2016.01.013 3192-9 Li, Q., Zhang, C., Han, C. W., Zhang, T., and Zhang, W. (2013). Zeng, M., Xi, L., and Xiao, A. (2016). The free step length ant colony Path planning based fuzzy logic algorithm for mobile robots in dynamic algorithm in mobile robot path planning. Adv. Robot. 30, 1509–1514. environments. J. Central South Univ. Sci. Technol. 2013, 105–107. doi: 10.1080/01691864.2016.1240627 doi: 10.1109/CCDC.2013.6561434 Zhang, W., Gong, X., Han, G., and Zhao, Y. (2017). An improved ant colony Li, W. H., Yang, C. G., Jiang, Y. M., and Su, C. Y. (2017). Motion planning algorithm for path planning in one scenic area with many spots. IEEE Access. 5, for omnidirectional wheeled mobile robot by potential field method. J. Adv. 13260–13269. doi: 10.1109/ACCESS.2017.2723892 Transport. 3, 1–11. doi: 10.1155/2017/4961383 Zhao, J., Cheng, D., and Hao, C. (2016). An improved ant colony algorithm for Lin, D., Shen, B., Liu, Y., Alsaadi, F. E., Alsaedi, A., and Cheng, H. (2017). solving the path planning problem of the omnidirectional mobile vehicle. Math. Genetic algorithm-based compliant robot path planning: an improved Prob. Eng. 2016, 1–10. doi: 10.1155/2016/7672839 Bi-RRT-based initialization method. Assembly Automat. 37, 261–270. Zhou, Z., Nie, Y., and Min, G. (2013). Enhanced ant colony optimization algorithm doi: 10.1108/AA-12-2016-173 for global path planning of mobile robots. Int. Conference Comput. Info. Sci. Liu, J. , Yang, J., Liu, H., Tian, X., and Gao, M. (2016). An improved 2013, 698–701. doi: 10.1109/ICCIS.2013.189 ant colony algorithm for robot path planning. Soft Comput. 1, 1–11. doi: 10.1007/s00500-016-2161-7 Conflict of Interest Statement: The authors declare that the research was Miao, H., and Tian, Y. C. (2013). Dynamic robot path planning using an conducted in the absence of any commercial or financial relationships that could enhanced simulated annealing approach. Appl. Math. Comput. 222, 420–437. be construed as a potential conflict of interest. doi: 10.1016/j.amc.2013.07.022 Nair, R. R., Behera, L., Kumar, V., and Jamshidi, M. M. (2015). Multisatellite Copyright © 2019 Dai, Long, Zhang and Gong. This is an open-access article formation control for remote sensing applications using artificial potential distributed under the terms of the Creative Commons Attribution License (CC BY). field and adaptive fuzzy sliding mode control. IEEE Syst. J. 9, 508–518. The use, distribution or reproduction in other forums is permitted, provided the doi: 10.1109/jsyst.2014.2335442 original author(s) and the copyright owner(s) are credited and that the original Shi, E., Chen, M., Li, J., and Huang, Y. (2014). Research on method of global path- publication in this journal is cited, in accordance with accepted academic practice. planning for mobile robot based on ant-colony algorithm. Trans. Chin. Soc. No use, distribution or reproduction is permitted which does not comply with these Agri. Machinery 45, 53–57. doi: 10.6041/j.issn.1000-1298.2014.06.009 terms. Frontiers in Neurorobotics | www.frontiersin.org 9 April 2019 | Volume 13 | Article 15

Journal

Frontiers in NeuroroboticsPubmed Central

Published: Apr 16, 2019

There are no references for this article.