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

Learn More →

Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm

Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm Hindawi Journal of Robotics Volume 2021, Article ID 4109821, 10 pages https://doi.org/10.1155/2021/4109821 Research Article Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm 1 1 2 1 Wenming Wang , Jiangdong Zhao , Zebin Li , and Ji Huang Experimental Training Teaching Management Department, West Anhui University, Lu’an 237012, China Robot Maker Laboratory, West Anhui University, Lu’an 237012, China Correspondence should be addressed to Wenming Wang; hellowwming@foxmail.com and Jiangdong Zhao; 39562466@qq.com Received 19 July 2021; Accepted 30 August 2021; Published 10 September 2021 Academic Editor: L. Fortuna Copyright © 2021 Wenming Wang et al. .is is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Aiming at the problems of slow convergence, easy to fall into local optimum, and poor smoothness of traditional ant colony algorithm in mobile robot path planning, an improved ant colony algorithm based on path smoothing factor was proposed. Firstly, the environment map was constructed based on the grid method, and each grid was marked to make the ant colony move from the initial grid to the target grid for path search. .en, the heuristic information is improved by referring to the direction information of the starting point and the end point and combining with the turning angle. By improving the heuristic in- formation, the direction of the search is increased and the turning angle of the robot is reduced. Finally, the pheromone updating rules were improved, the smoothness of the two-dimensional path was considered, the turning times of the robot were reduced, and a new path evaluation function was introduced to enhance the pheromone differentiation of the effective path. At the same time, the Max-Min Ant System (MMAS) algorithm was used to limit the pheromone concentration to avoid being trapped in the local optimum path. .e simulation results show that the improved ant colony algorithm can search the optimal path length and plan a smoother and safer path with fast convergence speed, which effectively solves the global path planning problem of mobile robot. algorithm [8], simulated annealing algorithm [9], and the 1. Introduction combined optimization algorithm among the algorithms With the rapid development of mobile robots, path planning [10–12]. has become the foundation and core of the research field of Among the above path planning methods, ant colony mobile robots. .e path planning technology of mobile algorithm has strong robustness and search ability, which robot is to find an optimal or suboptimal collision-free path was first proposed by the famous Italian scholar Dorigo in from the beginning to the end in a complex environment 1992 [13]. As a heuristic algorithm, it simulates the foraging according to certain evaluation criteria, such as the shortest process of the ant colony and obtains the solution path route, the least turning, the least energy consumption, etc. jointly planned by the ants. It has the characteristics of [1]. .e traditional algorithms to solve the path planning positive feedback, parallel computation, and easy fusion. problem mainly include artificial potential field algorithm However, there are still problems such as slow convergence [2], Dijkstra algorithm [3], and A algorithm [4]. In recent rate and easy to fall into local optimum in robot path years, some researchers have adopted bionic intelligent planning. Many scholars have improved the traditional ant optimization algorithms to solve the problem of path colony algorithm. Cao et al. proposed to build an initial planning. .ese bionic intelligent optimization algorithms pheromone model to avoid blind search and improve the mainly include ant colony algorithm [5], genetic algorithm convergence speed of the traditional ant colony algorithm [6], particle swarm optimization algorithm [7], immune [14]. Bai et al. designed ant colony algorithm with a negative 2 Journal of Robotics feedback mechanism to avoid falling into the local optimal 20 solution [15]. Zhang et al. proposed to construct a new heuristic function to make the pheromone volatile factor adapt to change and to ensure rapid convergence of ants even when searching the path comprehensively [16]. Ma and Mei integrated the search strategy of ant colony algorithm and hop search algorithm, introduced the decrease coeffi- cient of potential field resultant force, introduced the sim- plified hop search algorithm to update the initial pheromone, and proposed the ant colony algorithm based on potential field hop [17]. 6 Most of the above improved ant colony algorithms are devoted to optimizing the path length and improving the efficiency of pathfinding. Few scholars consider the prob- lems such as too large turning angle and too many turning 0 5 10 15 20 times of the whole path, leading to the increase of robot running time and energy consumption when looking for the Figure 1: Environment model of grid method. next mobile node. In view of this, this paper proposes an improved ant colony algorithm based on two-dimensional path smoothing factor for mobile robot path planning. called the grid coordinate, and the grid position in row i and column j is marked G(i, j). .en, the obstacle matrix is expressed as follows: 2. Environmental Modeling and Basic Ant Colony Algorithm 1, obstacles in the grid of row i and column j, G(i, j) � 􏼨 0, no obstacles in the grid of row i and column j. 2.1. Environmental Modeling. .e commonly used robot environment modeling methods include grid method, (1) viewable space method, free space method, geometric in- (2) Taking the lower-left corner of the grid map as the formation method, and topological map method [18]. In this paper, the grid method is selected to model the two-di- coordinate origin, the x-axis positive direction is defined as from left to right, and the y-axis positive mensional motion space of the mobile robot, as shown in Figure 1. direction is defined as from bottom to top. At this time, the corresponding coordinates of the grid are In order to ensure that the mobile robot does not collide with the edge of the obstacle during the movement and called the origin coordinates of the grid. Assuming ensure the smooth progress of each turn, the size of the that the number of rows on the grid map is M, the obstacle is properly expanded in this paper, and then a mapping relationship between the origin coordinates certain safe distance is reserved. .e safe distance is the (x, y) and the grid coordinates (i, j) is expressed as radius of the mobile robot, and the robot can be simplified as follows: a particle to deal with [19]. i � M + 0.5 − y, .e grid number is used to represent the specific po- 􏼨 (2) j � x + 0.5. sitions of robots and obstacles, in which the white grid is the free grid, representing the passable area, while the black grid is the obstacle area, which is impassable for mobile robots. .e movement of the robot can be regarded as the transfer 2.2. Basic Ant Colony Algorithm. Ant colony algorithm is to from the center of the current grid to the center of the next simulate the process of ant population from the starting grid. .e transferable grid is the grid of eight directions point to find the target point to obtain food. In the process adjacent to the current grid. .e eight adjacent grid steering of searching for food, ants will release a certain amount of labels are shown in Figure 2. pheromones in their path, and the ant colony uses these In the grid environment, it is assumed that grid S and pheromones to communicate with each other. When grid G are the starting point and end point of robot motion, more and more ants pass through a certain path, the respectively. .e problem to be solved in path planning is to pheromone concentration of this path will be higher, and search a series of ordered free grid nodes from S to G. In other ants will have a greater probability to choose this order to simplify the construction of the path search al- path, which plays a positive feedback role, but it is also gorithm, the following provisions are made for the grid easy to lead to the occurrence of local optimum or environment as shown in Figure 1. deadlock [20]. (1) Taking the upper-left corner of the grid map as the If there are multiple unvisited grids, the probability of an starting point, the grids are numbered in the order ant choosing the next grid from the current grid is deter- from top to bottom and from left to right. At this mined by the distance between them and the pheromone time, each grid has a corresponding coordinate concentration [21, 22]. .e state transition probability is Journal of Robotics 3 iteration. Q represents the intensity of pheromone, which is 12 3 a constant. L represents the path length of the ant k in this iteration. 3. Improved Ant Colony Algorithm for Path Planning In the traditional ant colony algorithm, the initial phero- 8 4 mone values of each grid are the same, and there is no obvious difference between the heuristic values, so the search time is often long, the algorithm convergence speed is slow, and it is difficult to find the global optimal solution [23]. At the same time, in the grid map, the path planned by the basic ant colony algorithm may have more turns, poor smooth- ness of the path, and consume a lot of energy of the robot. In 76 5 order to improve the performance of the original ant colony algorithm and overcome its defects, the following im- Figure 2: Direction of robot motion. provements were made in this paper. α β ⎧ ⎪ τ (t) ∗ η (t) ⎪ 􏽨 􏽩 􏽨 􏽩 ij ij ⎪ 3.1. Improve Heuristic Information. In the traditional ant , if j ∈ allowed , α β colony algorithm, the heuristic information η (t) is the 􏽐 􏼂τ (t)􏼃 ∗ 􏼂η (t)􏼃 ij s∈allowed is is P (t) � k ij ⎪ reciprocal of the distance between adjacent grids, so the heuristic weight difference of ants in adjacent grids is not 0, otherwise, obvious, which makes the heuristic function does not play an (3) obvious role in the ant transfer decision, making the search efficiency of the algorithm relatively low. In addition, when the robot passes through a group of obstacles, if only the η (t) � , (4) ij d shortest path is regarded as the main factor, it will cause the ij turning angle of the robot to be too large and easy to deviate where τ (t) is represents the pheromone concentration ij from the punctuation, which will greatly increase the time from grid i to grid j at time t; η (t) is the heuristic infor- ij and energy consumption. mation from grid i to grid j, indicating the degree of ex- .erefore, this paper adds the steering angle to the pectation of ants from grid i to grid j; it is usually the heuristic information of ant colony algorithm and combines reciprocal of the distance between two grids, η (t) � 1/d . α ij ij the direction information of the starting point and the target is the pheromone factor and β is the heuristic factor, re- point to improve the heuristic information, so that the spectively, indicating the concentration of pheromone and mobile robot can move to the target point and choose a path the relative importance of heuristic information. allowed with smaller turning angle as far as possible. By improving represents the grid set that can be selected by ant k in the the heuristic function, the purpose of ant colony search is next step at t time. increased, and the probability of falling into the local optimal When all ants complete a traversal, the pheromone solution is reduced. .e improved heuristic information is as concentration on the path will be updated by evaporating the follows: original pheromone and increasing the pheromone accu- m m m η (t) � φ (t) + c (t), (6) ij ij ij mulated by ants. .e pheromone updating formula is τ (t + 1) � (1 − ρ) · τ (t) + Δτ m ig ij ij ij φ (t) � , ij d + d ij jg 􏼌 􏼌 (7) 􏼌 􏼌 k m m 􏼌 􏼌 􏼌 􏼌 Δτ � 􏽘 Δτ , N (t) − N (t) ij 􏼌 􏼌 ij pi ij c (t) � 1 − , k�1 ij (5) where φ (t) represents the direction information of the ant ⎧ ⎪ ij , ant k passed through path(i, j), m from grid i to grid j at time t and guides the ant to move to k k Δτ � ij the adjacent grid in the direction of the end point, 0< ϕ≤ 1. d indicates the distance from the current grid i to the next ij 0, otherwise, grid j, d indicates the distance from the current grid j to the jg where ρ is the pheromone volatility coefficient, ρ ∈ (0, 1). end grid g. c (t) represents the turning angle of the ant m ij Δτ represents the increment of the pheromone from grid i from grid i to grid j at time t, guiding the ant to choose the ij k m to grid j in this iteration. Δτ represents the amount of path with small turning angle, 1/8≤ c≤ 1. N (t) represents ij pi pheromone released by the ant k from grid i to grid j in this the turn label of the ant from the previous grid p to the 4 Journal of Robotics current grid i, and N (t) indicates the turning label of the 4. Application of Improved Ant Colony ij ant from the current grid i to the next grid j. When ϕ � 1, Algorithm in Path Planning c � 1, the heuristic information is the largest, which indi- cates that the robot does not turn and moves to the terminal .e improved ant colony algorithm is applied to path with the optimal path. planning. .e specific steps are as follows: Step 1. Environment modeling: .e moving space environment of the robot was modeled by the grid 3.2. Improve Pheromone Update Rule method. .e starting point, ending point, and obstacle position of the robot were represented by grid coor- 3.2.1. Improve Pheromone Increment. When the traditional dinates, and all ants were placed at the starting point of ant colony algorithm is used to solve the problem of robot the robot. path planning, it usually takes the path length as the only reference to evaluate the path quality. However, in the actual Step 2. Initialize the parameters. .e starting position S, scene of robot walking, in order to improve the flexibility the target position G, the number of ants m, the and safety of robot walking, not only the length of the path, maximum number of iterations NC , the current max but also the turning times of the robot in the whole path number of iterations NC, the pheromone importance should be considered. In addition, when the obstacles in a factor α, the heuristic information importance factor β, certain area are densely distributed, the frequent turning of the pheromone volatility coefficient ρ, the strength of the robot in a short time should be avoided. .erefore, the pheromone Q, the path length adjustment coeffi- considering the smoothness of the two-dimensional path of cient x, and the turning times adjustment coefficient y. the robot, a new path evaluation function was introduced to Step 3. Calculate heuristic information. According to the enhance the pheromone differentiation of the effective path, current position of the ant, the heuristic information is so as to improve the smoothness of the search path, improve calculated according to equation (6), combining with the the security of the robot, and reduce the energy information of turning angle and direction. consumption. Step 4. Select path. Calculate the probability of ants moving from the current grid to the non-tabu grid ⎧ ⎪ ⎪ , (i, j) ∈ visited , ⎪ according to equation (3), select the next grid by k k Δτ � (8) roulette method, and update the tabu table. ij ⎪ Step 5. Determine whether all ants have reached the 0, else, target grid. If so, record each ant’s path, length of the path, and times of turns. Otherwise, return to Step 3. S � xL + yT , (9) k k k Step 6. Calculate pheromone increments. .e path where S is the evaluation function of the path traveled by evaluation function is calculated according to formula (9), and the pheromone increment is calculated the ant k, and the pheromone is allocated according to the evaluation function. .e smaller the evaluation function is, according to formula (8). the better the path is, and the more pheromone is released Step 7. Update the pheromone. .e pheromone is on this path, attracting more ants to search for this path. L updated according to equation (5), and the amount of is the path length of the ant k. T is the turning times of the k pheromone is limited by equation (10). ant k on the path, representing the smoothness of the path; Step 8. Record all the information of the ant’s path. the smaller the T , the better the smoothness of the path. Compare the optimal path of each iteration to find the Where x is the path length adjustment coefficient and y is current global optimal path. the times of turns adjustment coefficient, which are ap- Step 9. Determine whether the algorithm reaches the propriately valued according to the required path maximum number of iterations; then the algorithm properties. terminates and outputs the optimal path; otherwise, repeat Steps 3 to 8. 3.2.2. Pheromone Restriction. After several iterations, the .e flowchart of the improved ant colony algorithm path value of pheromone on one path may be much larger than or planning is shown in Figure 3. much smaller than other paths, which makes the search unable to continue and leads to premature convergence. In 5. Experimental Results and Analysis order to prevent this extreme situation, the value range of the pheromone is limited to τ to τ by referring to the min max In order to verify the effectiveness of the improved ant MMAS algorithm [24, 25]. colony algorithm (IACA), in this paper, the simulation experiment is carried out in MATLAB R2016A. .e com- ⎪ τ , if τ (t)> τ , ⎪ max ij max puter operating system is Windows10, AMD processor, the main frequency is 2.0 GHz, and 8G memory. .e moving τ (t) � τ , if τ (t)< τ , (10) min ij min ij environments of mobile robots are 20 × 20, 30 × 30, and τ (t), else. ij 50 × 50 grid maps, respectively. At the same time, in order to Journal of Robotics 5 In the experiment, it is found that in the 20 × 20 grid Start environment, all the three algorithms can search the shortest feasible path in the running process, so that the mobile robot Environmental Modeling can move safely from the starting point to the end point. However, the path planned by AS algorithm and ACS al- gorithm has a large number of turns and poor smoothness of Parameters initialization the path, leading to multiple turns when the robot moves a short distance, and frequent turns in a short time are not conducive to the safety of the robot. .e improved algorithm has obvious advantages in the number of turns, the planned Calculate heuristic information path is smoother, and the convergence speed is fast. Select the path and update the tabu table 5.2. 30 × 30 Grid Environment. In order to further verify the reliability of the improved algorithm in this paper, the grid map was expanded to 30 × 30 with more obstacles, and the simulation was carried out again. .e simulation results of All ants reach the target grid the three algorithms in the path planning research are shown in Figure 5. It can be seen from Figure 5 that when the scale of the grid map expands and the obstacles increases, the AS al- Calculate pheromone increment gorithm and the ACS algorithm cannot adapt well to the global path planning of this kind of relatively complex Update the pheromone environment and the optimal path lengths planned are 50.8 and 51.2, respectively. However, the algorithm in this paper can still perform well, and the optimal path found is 49.6, Record all the information of the ant's path which effectively shortens the path length compared with the former two algorithms. Figure 5(c) shows the convergence curve about the three algorithms (30 × 30); it can be seen that the algorithm in this paper converges faster and has the Whether the maximum shortest path length when the environment is complicated. iterations are reached Figure 5(b) shows the turns times curve about the three algorithms (30 × 30); it can be seen that the turn times of the optimal path of the algorithm in this paper are significantly lower than that of the AS algorithm and the ACS algorithm. Output the optimal path 5.3. 50 × 50 Grid Environment. In order to further verify the End adaptability of the improved algorithm in the large-scale grid map (50 × 50), the three algorithms were simulated in this Figure 3: Flowchart of improved ant colony algorithm path scale map. .e path planning is shown in Figure 6. planning. It can be seen from Figure 6(c) that in large-scale grid map, the time consumption of all three algorithms increases, the AS algorithm and ACS algorithm are easy to fall into the verify the superiority of the proposed algorithm, the results local optimum. As can be seen from Figure 6(b), in the grid obtained by the proposed algorithm are compared with those obtained by Ant System algorithm (AS) [13] and Ant map with many obstacles, AS algorithm and ACS algorithm make a lot of turns when searching the optimal path. It can Colony System algorithm (ACS) [26–28] in the same en- be seen from Figure 6(a) that the improved algorithm has vironment. In addition, in order to verify the stability of the obvious advantages, which not only reduces the number of improved ant colony algorithm, the three algorithms are turns and increases the smoothness of the path, but also has simulated for 10 times and the experimental results are faster convergence speed than AS algorithm and ACS al- shown in Table 1. .e relative parameters were set as follows: gorithm and can find the optimal path. α � 1, β � 6, ρ � 0.1, Q � 10, x � 1, y � 1, the number of ants It can be seen from the data in Table 1 that the path m � 50, and the maximum number of iterations length planned by the improved ant colony algorithm is NC � 200. .e starting point S is in the upper-left corner max shorter in the environment of large scale, more obstacles and and the end point G is in the lower-right corner. relatively complex (50 × 50). Compared with AS algorithm, the number of iterations required to converge to the optimal 5.1. 20 × 20 Grid Environment. First, in a simple grid envi- solution is reduced by about 61. Moreover, the times of turns in the optimal path is reduced from 37 in AS algorithm and ronment of 20 × 20, the simulation results of the three al- gorithms in the path planning research are shown in Figure 4. 53 in ACS algorithm to 4. .e smoothness of the path is 6 Journal of Robotics Table 1: Comparison of the results of the three algorithms in path planning. Grid map Algorithm Optimal path length Average path length Minimum number of iterations Turn times of optimal path AS 32.60 32.76 81 6 20 × 20 ACS 32.60 33.00 56 10 IACA 32.60 32.60 35 2 AS 50.80 51.20 84 9 30 × 30 ACS 51.20 51.55 65 17 IACA 49.60 49.90 61 5 AS 93.80 97.00 174 37 50 × 50 ACS 98.60 100.60 97 53 IACA 89.60 90.20 113 4 e turn times curve of the optimal path 10 20 0 5 10 15 20 0 50 100 150 200 Number of iterations AS AS ACS IACA ACS IACA (a) (b) e convergence curve of the optimal path 0 50 100 150 200 Number of iterations AS ACS IACA (c) Figure 4: Results of path planning about three algorithms (20 × 20). (a) Path planning in three algorithms (20 × 20). (b) .e turns times curve about three algorithms (20 × 20). (c) .e convergence curve about three algorithms (20 × 20). e optimal path length Number of turns Journal of Robotics 7 e turn times curve of the optimal path 20 40 15 30 10 20 0 5 10 15 20 25 30 0 50 100 150 200 Number of iterations AS AS ACS IACA ACS IACA (a) (b) e convergence curve of the optimal path 0 50 100 150 200 Number of iterations AS ACS IACA (c) Figure 5: Results of path planning about three algorithms (30 × 30). (a) Path planning in three algorithms (30 × 30). (b) .e turns times curve about three algorithms (30 × 30). (c) .e convergence curve about three algorithms (30 × 30). significantly improved and effectively avoids large-scale limitations in path planning in a complex environment. .e turns of the robot behavior. improved algorithm can quickly and effectively find the In summary, when the environment becomes relatively optimal path even in a complex environment, and the complex, the search path of traditional algorithms becomes planned path has fewer turns and better path smoothness. more tortuous, the optimization ability is not ideal, and it is .e effectiveness and superiority of the algorithm have been easy to fall into a local optimal solution. .ere are certain further proved. e optimal path length Number of turns 8 Journal of Robotics e turn times curve of the optimal path AS ACS 140 IACA 25 80 010 20 30 40 50 0 50 100 150 200 Number of iterations AS ACS IACA (a) (b) e convergence curve of the optimal path 0 50 100 150 200 Number of iterations AS ACS IACA (c) Figure 6: Results of path planning about three algorithms (50 × 50). (a) Path planning in three algorithms (50 × 50). (b) .e turns times curve about three algorithms (50 × 50). (c) .e convergence curve about three algorithms (50 × 50). updating the effective path with pheromone differentiation. 6. Conclusion .e simulation results of path planning in three different Path planning is a key technology for robots to move in grid environments show that the improved algorithm has complex environments. As a bionic algorithm, ant colony better path planning, faster convergence speed, fewer turns, algorithm can effectively realize the path planning of robot. and smoother path, which reduces the energy loss of mobile Aiming at the problems of slow convergence speed, low robot and makes it move to the target point safely and search efficiency, and poor path smoothness of traditional quickly. It effectively proves the effectiveness and adapt- ant colony algorithm in path planning, this paper improves ability of the algorithm in complex environment. the ant colony algorithm by improving the heuristic in- Microfluidics is a technology that integrates the basic formation, introducing a new path evaluation function, operation units such as sample preparation, reaction, sep- considering the smoothness of two-dimensional path, and aration, and detection in the process of biological, chemical, e optimal path length Number of turns Journal of Robotics 9 of gene network,” Journal of Computer and Communications, and medical analysis into a micron-scale chip to automat- vol. 7, no. 12, pp. 166–174, 2019. ically complete the whole process of analysis [29, 30]. Digital [9] L. Wang, J. Guo, Q. Wang, and J. Kan, “Ground robot path microfluidic biochip (DMFB) takes discrete microdroplets planning based on simulated annealing genetic algorithm,” in as the unit and realizes a variety of basic manipulation or Proceedings of the 2018 International Conference on Cyber- processing of droplets, such as generation, transportation, Enabled Distributed Computing and Knowledge Discovery merging, mixing, separation, storage, and detection, through (CyberC), pp. 417–4177, Zhengzhou, China, October 2018. a droplet driving mode. Droplet path planning is one of the [10] J. Q. Liao, “Research on PAGV path planning based on ar- core steps of advanced synthesis of DMFB. It aims to plan tificial immune ant colony fusion algorithm,” Journal of In- the moving path of a group of droplets and requires droplets telligent and Fuzzy Systems, vol. 35, no. 16, pp. 1–6, 2018. to correctly perform the reaction process of biochemical [11] L. Liu, J. Yao, D. He et al., “Global dynamic path planning detection and analysis. Each droplet is interpreted as a point fusion algorithm combining jump-A algorithm and dynamic robot moving in a discrete two-dimensional configuration window approach,” IEEE Access, vol. 9, pp. 19632–19638, space. Under this assumption, path planning of the droplets [12] A. Tiwari and S. Varma Nadimpalli, “New fusion algorithm becomes a motion planning problem with multiple moving provides an alternative approach to robotic path planning,” robots [31–34]. .erefore, in the future research, we will International Journal of Information Engineering and Elec- further try to use ant colony algorithm to solve the droplet tronic Business, vol. 12, no. 3, pp. 1–7, 2020. path planning and scheduling problem of DMFB. [13] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: op- timization by a colony of cooperating agents,” IEEE Trans- Data Availability actions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29–41, 1996. .e data used to support the findings of this study are [14] X.-L. Cao, Z.-W. Wang, J. Feng, M. Zha, and Y.-H. Wang, available from the corresponding author upon request. “Global path planning of robots based on improved ant colony algorithm,” Computer Engineering and Science, vol. 42, Conflicts of Interest no. 3, pp. 187–193, 2020. [15] J.-L. Bai, H.-H. Chen, Y.-B. Hu, M.-W. He, X.-D. Liang, and .e authors declare that there are no conflicts of interest D. Park, “Ant colony algorithm base on negative feedback and regarding the publication of this paper. its application on robot path planning,” Computer Integrated Manufacturing Systems, vol. 25, no. 7, pp. 1–9, 2019. Acknowledgments [16] J. Zhao, Y.-F. Tang, G.-P. Jiang, F.-Y. Xu, and J. Ding, “Mobile robot path planning base on improved ant colony algorithm,” .is work was supported by the Anhui Province University Journal of Nanjing University of Posts and Telecommunica- tions (Natural Science Edition), vol. 39, no. 6, pp. 73–78, 2019. Outstanding Young Talent Support Program Project (no. [17] X. Ma and H. Mei, “Mobile robot global path planning based gxyq2019072) and the Anhui Provincial Quality Engineering on improved ant colony system algorithm with potential Project for University (no. 2020jyxm2151). field,” Journal of Mechanical Engineering, vol. 57, no. 1, pp. 19–27, 2021. References [18] S. Tian, Y. Li, Y. Kang, and J. Xia, “Multi-robot path planning in wireless sensor networks based on jump mechanism PSO [1] D. H. Zhang, X. M. You, S. Liu, and H. Pan, “Dynamic multi- and safety gap obstacle avoidance,” Future Generation role adaptive collaborative ant colony optimization for robot Computer Systems, vol. 118, no. 6, pp. 37–47, 2020. path planning,” IEEE Access, vol. 8, pp. 129958–129974, 2020. [19] X. Guo, M. Ji, Z. Zhao, D. Wen, and W. Zhang, “Global path [2] F. L. Li, “An optimization path planning method based on planning and multi-objective path control for unmanned evolutionary artificial potential field,” Applied Mechanics and surface vehicle based on modified particle swarm optimiza- Materials, vol. 380-384, no. 384, pp. 1414–1417, 2013. tion (PSO) algorithm,” Ocean Engineering, vol. 216, Article ID [3] E. W. Dijkstra, “A note on two problems in connexion with 107693, 2020. graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, [20] Z. Wang, J. Li, M. Fang, and Y. Li, “A multimetric ant colony optimization algorithm for dynamic path planning in ve- [4] C. Huang, J. Fei, Y. Liu, H. Li, and X. Liu, “Smooth path hicular networks,” International Journal of Distributed Sensor planning method based on dynamic feedback A ant colony Networks, vol. 2015, Article ID 271067, 10 pages, 2015. algorithm,” Transactions of the Chinese Society for Agricultural [21] W. Gao, Q. Tang, B. Ye, Y. Yang, and J. Yao, “An enhanced Machinery, vol. 48, no. 4, pp. 34–40, 2017. heuristic ant colony optimization for mobile robot path [5] L. Yue and H. Chen, “Unmanned vehicle path planning using planning,” Soft Computing, vol. 24, no. 2, pp. 6139–6150, 2020. a novel ant colony algorithm,” EURASIP Journal on Wireless [22] Q. Luo, H. Wang, Y. Zheng, and J. He, “Research on path Communications and Networking, vol. 2019, no. 1, pp. 1–9, 2019. planning of mobile robot based on improved ant colony al- gorithm,” Neural Computing and Applications, vol. 32, no. 6, [6] C. Lamini, S. Benhlima, and A. Elbekri, “Genetic algorithm based approach for autonomous mobile robot path planning,” pp. 1555–1566, 2020. [23] J. Ning, Q. Zhang, C. Zhang, and B. Zhang, “A best-path- Procedia Computer Science, vol. 127, pp. 180–189, 2018. [7] Y. K. Ever, “Using simplified swarm optimization on path updating information-guided ant colony optimization algo- rithm,” Information Sciences, vol. 433-434, no. 434, planning for intelligent mobile robot,” Procedia Computer Science, vol. 120, pp. 83–90, 2017. pp. 142–162, 2018. [8] T. Gong and M. Wang, “An improved immune algorithm for [24] T. Stutzle and H. Hoos, “MAX-MIN ant system and local solving path optimization problem in deep immune learning search for the traveling salesman problem,” in Proceedings of 10 Journal of Robotics 1997 IEEE International Conference on Evolutionary Com- putation (ICEC ’97), pp. 309–314, Indianapolis, IN, USA, April 1997. [25] L. C. Lu and T. W. Yue, “Mission-oriented ant-team ACO for min-max MTSP,” Applied Soft Computing, vol. 76, pp. 436– 444, 2018. [26] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, 1997. [27] G. Z. Tan, H. Huan, and A. Sloman, “Ant colony system algorithm for real-time globally optimal path planning of mobile robots,” Acta Automatica Sinica, vol. 33, no. 3, pp. 279–285, 2007. [28] S.-Z. Zhou, Z.-H. Zhan, Z.-G. Chen, S. Kwong, and J. Zhang, “A multi-objective ant colony system algorithm for airline crew rostering problem with fairness and satisfaction,” IEEE Transactions on Intelligent Transportation Systems, pp. 1–15, [29] F. Sapuppo, F. Schembri, L. Fortuna, and M. Bucolo, “Microfluidic circuits and systems,” IEEE Circuits and Systems Magazine, vol. 9, no. 3, pp. 6–19, 2009. [30] F. Schembri, F. Sapuppo, and M. Bucolo, “Experimental classification of nonlinear dynamics in microfluidic bubbles’ flow,” Nonlinear Dynamics, vol. 67, no. 4, pp. 2807–2819, [31] K. F. Bohringer, “Modeling and controlling parallel tasks in droplet-based microfluidic systems,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 2, pp. 334–344, 2006. [32] I. Pan, P. Dasgupta, H. Rahaman, and T. Samanta, “Ant colony optimization based droplet routing technique in digital microfluidic biochip,” in Proceedings of the 2011 International Symposium on Electronic System Design, pp. 223–229, Kochi, India, December 2011. [33] W. Zheng, H. Yu, L. Feng, P. Fu, and H. Jiang, “Single droplet on-line testing path optimization for digital microfluidic biochips based on the improved ant colony algorithm,” in Proceedings of the 2017 IEEE International Instrumentation and Measurement Technology Conference (I2MTC), pp. 1–6, Turin, Italy, May 2017. [34] S. Mukherjee, I. Pan, and T. Samanta, “A particle swarm optimization method for fault localization and residue re- moval in digital microfluidic biochips,” Applied Soft Com- puting, vol. 85, no. 1, Article ID 105839, 2019. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Robotics Hindawi Publishing Corporation

Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm

Download PDF
10 pages

Loading next page...
 
/lp/hindawi-publishing-corporation/smooth-path-planning-of-mobile-robot-based-on-improved-ant-colony-Wkiu9OX6M1

References (37)

Publisher
Hindawi Publishing Corporation
Copyright
Copyright © 2021 Wenming Wang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
ISSN
1687-9600
eISSN
1687-9619
DOI
10.1155/2021/4109821
Publisher site
See Article on Publisher Site

Abstract

Hindawi Journal of Robotics Volume 2021, Article ID 4109821, 10 pages https://doi.org/10.1155/2021/4109821 Research Article Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm 1 1 2 1 Wenming Wang , Jiangdong Zhao , Zebin Li , and Ji Huang Experimental Training Teaching Management Department, West Anhui University, Lu’an 237012, China Robot Maker Laboratory, West Anhui University, Lu’an 237012, China Correspondence should be addressed to Wenming Wang; hellowwming@foxmail.com and Jiangdong Zhao; 39562466@qq.com Received 19 July 2021; Accepted 30 August 2021; Published 10 September 2021 Academic Editor: L. Fortuna Copyright © 2021 Wenming Wang et al. .is is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Aiming at the problems of slow convergence, easy to fall into local optimum, and poor smoothness of traditional ant colony algorithm in mobile robot path planning, an improved ant colony algorithm based on path smoothing factor was proposed. Firstly, the environment map was constructed based on the grid method, and each grid was marked to make the ant colony move from the initial grid to the target grid for path search. .en, the heuristic information is improved by referring to the direction information of the starting point and the end point and combining with the turning angle. By improving the heuristic in- formation, the direction of the search is increased and the turning angle of the robot is reduced. Finally, the pheromone updating rules were improved, the smoothness of the two-dimensional path was considered, the turning times of the robot were reduced, and a new path evaluation function was introduced to enhance the pheromone differentiation of the effective path. At the same time, the Max-Min Ant System (MMAS) algorithm was used to limit the pheromone concentration to avoid being trapped in the local optimum path. .e simulation results show that the improved ant colony algorithm can search the optimal path length and plan a smoother and safer path with fast convergence speed, which effectively solves the global path planning problem of mobile robot. algorithm [8], simulated annealing algorithm [9], and the 1. Introduction combined optimization algorithm among the algorithms With the rapid development of mobile robots, path planning [10–12]. has become the foundation and core of the research field of Among the above path planning methods, ant colony mobile robots. .e path planning technology of mobile algorithm has strong robustness and search ability, which robot is to find an optimal or suboptimal collision-free path was first proposed by the famous Italian scholar Dorigo in from the beginning to the end in a complex environment 1992 [13]. As a heuristic algorithm, it simulates the foraging according to certain evaluation criteria, such as the shortest process of the ant colony and obtains the solution path route, the least turning, the least energy consumption, etc. jointly planned by the ants. It has the characteristics of [1]. .e traditional algorithms to solve the path planning positive feedback, parallel computation, and easy fusion. problem mainly include artificial potential field algorithm However, there are still problems such as slow convergence [2], Dijkstra algorithm [3], and A algorithm [4]. In recent rate and easy to fall into local optimum in robot path years, some researchers have adopted bionic intelligent planning. Many scholars have improved the traditional ant optimization algorithms to solve the problem of path colony algorithm. Cao et al. proposed to build an initial planning. .ese bionic intelligent optimization algorithms pheromone model to avoid blind search and improve the mainly include ant colony algorithm [5], genetic algorithm convergence speed of the traditional ant colony algorithm [6], particle swarm optimization algorithm [7], immune [14]. Bai et al. designed ant colony algorithm with a negative 2 Journal of Robotics feedback mechanism to avoid falling into the local optimal 20 solution [15]. Zhang et al. proposed to construct a new heuristic function to make the pheromone volatile factor adapt to change and to ensure rapid convergence of ants even when searching the path comprehensively [16]. Ma and Mei integrated the search strategy of ant colony algorithm and hop search algorithm, introduced the decrease coeffi- cient of potential field resultant force, introduced the sim- plified hop search algorithm to update the initial pheromone, and proposed the ant colony algorithm based on potential field hop [17]. 6 Most of the above improved ant colony algorithms are devoted to optimizing the path length and improving the efficiency of pathfinding. Few scholars consider the prob- lems such as too large turning angle and too many turning 0 5 10 15 20 times of the whole path, leading to the increase of robot running time and energy consumption when looking for the Figure 1: Environment model of grid method. next mobile node. In view of this, this paper proposes an improved ant colony algorithm based on two-dimensional path smoothing factor for mobile robot path planning. called the grid coordinate, and the grid position in row i and column j is marked G(i, j). .en, the obstacle matrix is expressed as follows: 2. Environmental Modeling and Basic Ant Colony Algorithm 1, obstacles in the grid of row i and column j, G(i, j) � 􏼨 0, no obstacles in the grid of row i and column j. 2.1. Environmental Modeling. .e commonly used robot environment modeling methods include grid method, (1) viewable space method, free space method, geometric in- (2) Taking the lower-left corner of the grid map as the formation method, and topological map method [18]. In this paper, the grid method is selected to model the two-di- coordinate origin, the x-axis positive direction is defined as from left to right, and the y-axis positive mensional motion space of the mobile robot, as shown in Figure 1. direction is defined as from bottom to top. At this time, the corresponding coordinates of the grid are In order to ensure that the mobile robot does not collide with the edge of the obstacle during the movement and called the origin coordinates of the grid. Assuming ensure the smooth progress of each turn, the size of the that the number of rows on the grid map is M, the obstacle is properly expanded in this paper, and then a mapping relationship between the origin coordinates certain safe distance is reserved. .e safe distance is the (x, y) and the grid coordinates (i, j) is expressed as radius of the mobile robot, and the robot can be simplified as follows: a particle to deal with [19]. i � M + 0.5 − y, .e grid number is used to represent the specific po- 􏼨 (2) j � x + 0.5. sitions of robots and obstacles, in which the white grid is the free grid, representing the passable area, while the black grid is the obstacle area, which is impassable for mobile robots. .e movement of the robot can be regarded as the transfer 2.2. Basic Ant Colony Algorithm. Ant colony algorithm is to from the center of the current grid to the center of the next simulate the process of ant population from the starting grid. .e transferable grid is the grid of eight directions point to find the target point to obtain food. In the process adjacent to the current grid. .e eight adjacent grid steering of searching for food, ants will release a certain amount of labels are shown in Figure 2. pheromones in their path, and the ant colony uses these In the grid environment, it is assumed that grid S and pheromones to communicate with each other. When grid G are the starting point and end point of robot motion, more and more ants pass through a certain path, the respectively. .e problem to be solved in path planning is to pheromone concentration of this path will be higher, and search a series of ordered free grid nodes from S to G. In other ants will have a greater probability to choose this order to simplify the construction of the path search al- path, which plays a positive feedback role, but it is also gorithm, the following provisions are made for the grid easy to lead to the occurrence of local optimum or environment as shown in Figure 1. deadlock [20]. (1) Taking the upper-left corner of the grid map as the If there are multiple unvisited grids, the probability of an starting point, the grids are numbered in the order ant choosing the next grid from the current grid is deter- from top to bottom and from left to right. At this mined by the distance between them and the pheromone time, each grid has a corresponding coordinate concentration [21, 22]. .e state transition probability is Journal of Robotics 3 iteration. Q represents the intensity of pheromone, which is 12 3 a constant. L represents the path length of the ant k in this iteration. 3. Improved Ant Colony Algorithm for Path Planning In the traditional ant colony algorithm, the initial phero- 8 4 mone values of each grid are the same, and there is no obvious difference between the heuristic values, so the search time is often long, the algorithm convergence speed is slow, and it is difficult to find the global optimal solution [23]. At the same time, in the grid map, the path planned by the basic ant colony algorithm may have more turns, poor smooth- ness of the path, and consume a lot of energy of the robot. In 76 5 order to improve the performance of the original ant colony algorithm and overcome its defects, the following im- Figure 2: Direction of robot motion. provements were made in this paper. α β ⎧ ⎪ τ (t) ∗ η (t) ⎪ 􏽨 􏽩 􏽨 􏽩 ij ij ⎪ 3.1. Improve Heuristic Information. In the traditional ant , if j ∈ allowed , α β colony algorithm, the heuristic information η (t) is the 􏽐 􏼂τ (t)􏼃 ∗ 􏼂η (t)􏼃 ij s∈allowed is is P (t) � k ij ⎪ reciprocal of the distance between adjacent grids, so the heuristic weight difference of ants in adjacent grids is not 0, otherwise, obvious, which makes the heuristic function does not play an (3) obvious role in the ant transfer decision, making the search efficiency of the algorithm relatively low. In addition, when the robot passes through a group of obstacles, if only the η (t) � , (4) ij d shortest path is regarded as the main factor, it will cause the ij turning angle of the robot to be too large and easy to deviate where τ (t) is represents the pheromone concentration ij from the punctuation, which will greatly increase the time from grid i to grid j at time t; η (t) is the heuristic infor- ij and energy consumption. mation from grid i to grid j, indicating the degree of ex- .erefore, this paper adds the steering angle to the pectation of ants from grid i to grid j; it is usually the heuristic information of ant colony algorithm and combines reciprocal of the distance between two grids, η (t) � 1/d . α ij ij the direction information of the starting point and the target is the pheromone factor and β is the heuristic factor, re- point to improve the heuristic information, so that the spectively, indicating the concentration of pheromone and mobile robot can move to the target point and choose a path the relative importance of heuristic information. allowed with smaller turning angle as far as possible. By improving represents the grid set that can be selected by ant k in the the heuristic function, the purpose of ant colony search is next step at t time. increased, and the probability of falling into the local optimal When all ants complete a traversal, the pheromone solution is reduced. .e improved heuristic information is as concentration on the path will be updated by evaporating the follows: original pheromone and increasing the pheromone accu- m m m η (t) � φ (t) + c (t), (6) ij ij ij mulated by ants. .e pheromone updating formula is τ (t + 1) � (1 − ρ) · τ (t) + Δτ m ig ij ij ij φ (t) � , ij d + d ij jg 􏼌 􏼌 (7) 􏼌 􏼌 k m m 􏼌 􏼌 􏼌 􏼌 Δτ � 􏽘 Δτ , N (t) − N (t) ij 􏼌 􏼌 ij pi ij c (t) � 1 − , k�1 ij (5) where φ (t) represents the direction information of the ant ⎧ ⎪ ij , ant k passed through path(i, j), m from grid i to grid j at time t and guides the ant to move to k k Δτ � ij the adjacent grid in the direction of the end point, 0< ϕ≤ 1. d indicates the distance from the current grid i to the next ij 0, otherwise, grid j, d indicates the distance from the current grid j to the jg where ρ is the pheromone volatility coefficient, ρ ∈ (0, 1). end grid g. c (t) represents the turning angle of the ant m ij Δτ represents the increment of the pheromone from grid i from grid i to grid j at time t, guiding the ant to choose the ij k m to grid j in this iteration. Δτ represents the amount of path with small turning angle, 1/8≤ c≤ 1. N (t) represents ij pi pheromone released by the ant k from grid i to grid j in this the turn label of the ant from the previous grid p to the 4 Journal of Robotics current grid i, and N (t) indicates the turning label of the 4. Application of Improved Ant Colony ij ant from the current grid i to the next grid j. When ϕ � 1, Algorithm in Path Planning c � 1, the heuristic information is the largest, which indi- cates that the robot does not turn and moves to the terminal .e improved ant colony algorithm is applied to path with the optimal path. planning. .e specific steps are as follows: Step 1. Environment modeling: .e moving space environment of the robot was modeled by the grid 3.2. Improve Pheromone Update Rule method. .e starting point, ending point, and obstacle position of the robot were represented by grid coor- 3.2.1. Improve Pheromone Increment. When the traditional dinates, and all ants were placed at the starting point of ant colony algorithm is used to solve the problem of robot the robot. path planning, it usually takes the path length as the only reference to evaluate the path quality. However, in the actual Step 2. Initialize the parameters. .e starting position S, scene of robot walking, in order to improve the flexibility the target position G, the number of ants m, the and safety of robot walking, not only the length of the path, maximum number of iterations NC , the current max but also the turning times of the robot in the whole path number of iterations NC, the pheromone importance should be considered. In addition, when the obstacles in a factor α, the heuristic information importance factor β, certain area are densely distributed, the frequent turning of the pheromone volatility coefficient ρ, the strength of the robot in a short time should be avoided. .erefore, the pheromone Q, the path length adjustment coeffi- considering the smoothness of the two-dimensional path of cient x, and the turning times adjustment coefficient y. the robot, a new path evaluation function was introduced to Step 3. Calculate heuristic information. According to the enhance the pheromone differentiation of the effective path, current position of the ant, the heuristic information is so as to improve the smoothness of the search path, improve calculated according to equation (6), combining with the the security of the robot, and reduce the energy information of turning angle and direction. consumption. Step 4. Select path. Calculate the probability of ants moving from the current grid to the non-tabu grid ⎧ ⎪ ⎪ , (i, j) ∈ visited , ⎪ according to equation (3), select the next grid by k k Δτ � (8) roulette method, and update the tabu table. ij ⎪ Step 5. Determine whether all ants have reached the 0, else, target grid. If so, record each ant’s path, length of the path, and times of turns. Otherwise, return to Step 3. S � xL + yT , (9) k k k Step 6. Calculate pheromone increments. .e path where S is the evaluation function of the path traveled by evaluation function is calculated according to formula (9), and the pheromone increment is calculated the ant k, and the pheromone is allocated according to the evaluation function. .e smaller the evaluation function is, according to formula (8). the better the path is, and the more pheromone is released Step 7. Update the pheromone. .e pheromone is on this path, attracting more ants to search for this path. L updated according to equation (5), and the amount of is the path length of the ant k. T is the turning times of the k pheromone is limited by equation (10). ant k on the path, representing the smoothness of the path; Step 8. Record all the information of the ant’s path. the smaller the T , the better the smoothness of the path. Compare the optimal path of each iteration to find the Where x is the path length adjustment coefficient and y is current global optimal path. the times of turns adjustment coefficient, which are ap- Step 9. Determine whether the algorithm reaches the propriately valued according to the required path maximum number of iterations; then the algorithm properties. terminates and outputs the optimal path; otherwise, repeat Steps 3 to 8. 3.2.2. Pheromone Restriction. After several iterations, the .e flowchart of the improved ant colony algorithm path value of pheromone on one path may be much larger than or planning is shown in Figure 3. much smaller than other paths, which makes the search unable to continue and leads to premature convergence. In 5. Experimental Results and Analysis order to prevent this extreme situation, the value range of the pheromone is limited to τ to τ by referring to the min max In order to verify the effectiveness of the improved ant MMAS algorithm [24, 25]. colony algorithm (IACA), in this paper, the simulation experiment is carried out in MATLAB R2016A. .e com- ⎪ τ , if τ (t)> τ , ⎪ max ij max puter operating system is Windows10, AMD processor, the main frequency is 2.0 GHz, and 8G memory. .e moving τ (t) � τ , if τ (t)< τ , (10) min ij min ij environments of mobile robots are 20 × 20, 30 × 30, and τ (t), else. ij 50 × 50 grid maps, respectively. At the same time, in order to Journal of Robotics 5 In the experiment, it is found that in the 20 × 20 grid Start environment, all the three algorithms can search the shortest feasible path in the running process, so that the mobile robot Environmental Modeling can move safely from the starting point to the end point. However, the path planned by AS algorithm and ACS al- gorithm has a large number of turns and poor smoothness of Parameters initialization the path, leading to multiple turns when the robot moves a short distance, and frequent turns in a short time are not conducive to the safety of the robot. .e improved algorithm has obvious advantages in the number of turns, the planned Calculate heuristic information path is smoother, and the convergence speed is fast. Select the path and update the tabu table 5.2. 30 × 30 Grid Environment. In order to further verify the reliability of the improved algorithm in this paper, the grid map was expanded to 30 × 30 with more obstacles, and the simulation was carried out again. .e simulation results of All ants reach the target grid the three algorithms in the path planning research are shown in Figure 5. It can be seen from Figure 5 that when the scale of the grid map expands and the obstacles increases, the AS al- Calculate pheromone increment gorithm and the ACS algorithm cannot adapt well to the global path planning of this kind of relatively complex Update the pheromone environment and the optimal path lengths planned are 50.8 and 51.2, respectively. However, the algorithm in this paper can still perform well, and the optimal path found is 49.6, Record all the information of the ant's path which effectively shortens the path length compared with the former two algorithms. Figure 5(c) shows the convergence curve about the three algorithms (30 × 30); it can be seen that the algorithm in this paper converges faster and has the Whether the maximum shortest path length when the environment is complicated. iterations are reached Figure 5(b) shows the turns times curve about the three algorithms (30 × 30); it can be seen that the turn times of the optimal path of the algorithm in this paper are significantly lower than that of the AS algorithm and the ACS algorithm. Output the optimal path 5.3. 50 × 50 Grid Environment. In order to further verify the End adaptability of the improved algorithm in the large-scale grid map (50 × 50), the three algorithms were simulated in this Figure 3: Flowchart of improved ant colony algorithm path scale map. .e path planning is shown in Figure 6. planning. It can be seen from Figure 6(c) that in large-scale grid map, the time consumption of all three algorithms increases, the AS algorithm and ACS algorithm are easy to fall into the verify the superiority of the proposed algorithm, the results local optimum. As can be seen from Figure 6(b), in the grid obtained by the proposed algorithm are compared with those obtained by Ant System algorithm (AS) [13] and Ant map with many obstacles, AS algorithm and ACS algorithm make a lot of turns when searching the optimal path. It can Colony System algorithm (ACS) [26–28] in the same en- be seen from Figure 6(a) that the improved algorithm has vironment. In addition, in order to verify the stability of the obvious advantages, which not only reduces the number of improved ant colony algorithm, the three algorithms are turns and increases the smoothness of the path, but also has simulated for 10 times and the experimental results are faster convergence speed than AS algorithm and ACS al- shown in Table 1. .e relative parameters were set as follows: gorithm and can find the optimal path. α � 1, β � 6, ρ � 0.1, Q � 10, x � 1, y � 1, the number of ants It can be seen from the data in Table 1 that the path m � 50, and the maximum number of iterations length planned by the improved ant colony algorithm is NC � 200. .e starting point S is in the upper-left corner max shorter in the environment of large scale, more obstacles and and the end point G is in the lower-right corner. relatively complex (50 × 50). Compared with AS algorithm, the number of iterations required to converge to the optimal 5.1. 20 × 20 Grid Environment. First, in a simple grid envi- solution is reduced by about 61. Moreover, the times of turns in the optimal path is reduced from 37 in AS algorithm and ronment of 20 × 20, the simulation results of the three al- gorithms in the path planning research are shown in Figure 4. 53 in ACS algorithm to 4. .e smoothness of the path is 6 Journal of Robotics Table 1: Comparison of the results of the three algorithms in path planning. Grid map Algorithm Optimal path length Average path length Minimum number of iterations Turn times of optimal path AS 32.60 32.76 81 6 20 × 20 ACS 32.60 33.00 56 10 IACA 32.60 32.60 35 2 AS 50.80 51.20 84 9 30 × 30 ACS 51.20 51.55 65 17 IACA 49.60 49.90 61 5 AS 93.80 97.00 174 37 50 × 50 ACS 98.60 100.60 97 53 IACA 89.60 90.20 113 4 e turn times curve of the optimal path 10 20 0 5 10 15 20 0 50 100 150 200 Number of iterations AS AS ACS IACA ACS IACA (a) (b) e convergence curve of the optimal path 0 50 100 150 200 Number of iterations AS ACS IACA (c) Figure 4: Results of path planning about three algorithms (20 × 20). (a) Path planning in three algorithms (20 × 20). (b) .e turns times curve about three algorithms (20 × 20). (c) .e convergence curve about three algorithms (20 × 20). e optimal path length Number of turns Journal of Robotics 7 e turn times curve of the optimal path 20 40 15 30 10 20 0 5 10 15 20 25 30 0 50 100 150 200 Number of iterations AS AS ACS IACA ACS IACA (a) (b) e convergence curve of the optimal path 0 50 100 150 200 Number of iterations AS ACS IACA (c) Figure 5: Results of path planning about three algorithms (30 × 30). (a) Path planning in three algorithms (30 × 30). (b) .e turns times curve about three algorithms (30 × 30). (c) .e convergence curve about three algorithms (30 × 30). significantly improved and effectively avoids large-scale limitations in path planning in a complex environment. .e turns of the robot behavior. improved algorithm can quickly and effectively find the In summary, when the environment becomes relatively optimal path even in a complex environment, and the complex, the search path of traditional algorithms becomes planned path has fewer turns and better path smoothness. more tortuous, the optimization ability is not ideal, and it is .e effectiveness and superiority of the algorithm have been easy to fall into a local optimal solution. .ere are certain further proved. e optimal path length Number of turns 8 Journal of Robotics e turn times curve of the optimal path AS ACS 140 IACA 25 80 010 20 30 40 50 0 50 100 150 200 Number of iterations AS ACS IACA (a) (b) e convergence curve of the optimal path 0 50 100 150 200 Number of iterations AS ACS IACA (c) Figure 6: Results of path planning about three algorithms (50 × 50). (a) Path planning in three algorithms (50 × 50). (b) .e turns times curve about three algorithms (50 × 50). (c) .e convergence curve about three algorithms (50 × 50). updating the effective path with pheromone differentiation. 6. Conclusion .e simulation results of path planning in three different Path planning is a key technology for robots to move in grid environments show that the improved algorithm has complex environments. As a bionic algorithm, ant colony better path planning, faster convergence speed, fewer turns, algorithm can effectively realize the path planning of robot. and smoother path, which reduces the energy loss of mobile Aiming at the problems of slow convergence speed, low robot and makes it move to the target point safely and search efficiency, and poor path smoothness of traditional quickly. It effectively proves the effectiveness and adapt- ant colony algorithm in path planning, this paper improves ability of the algorithm in complex environment. the ant colony algorithm by improving the heuristic in- Microfluidics is a technology that integrates the basic formation, introducing a new path evaluation function, operation units such as sample preparation, reaction, sep- considering the smoothness of two-dimensional path, and aration, and detection in the process of biological, chemical, e optimal path length Number of turns Journal of Robotics 9 of gene network,” Journal of Computer and Communications, and medical analysis into a micron-scale chip to automat- vol. 7, no. 12, pp. 166–174, 2019. ically complete the whole process of analysis [29, 30]. Digital [9] L. Wang, J. Guo, Q. Wang, and J. Kan, “Ground robot path microfluidic biochip (DMFB) takes discrete microdroplets planning based on simulated annealing genetic algorithm,” in as the unit and realizes a variety of basic manipulation or Proceedings of the 2018 International Conference on Cyber- processing of droplets, such as generation, transportation, Enabled Distributed Computing and Knowledge Discovery merging, mixing, separation, storage, and detection, through (CyberC), pp. 417–4177, Zhengzhou, China, October 2018. a droplet driving mode. Droplet path planning is one of the [10] J. Q. Liao, “Research on PAGV path planning based on ar- core steps of advanced synthesis of DMFB. It aims to plan tificial immune ant colony fusion algorithm,” Journal of In- the moving path of a group of droplets and requires droplets telligent and Fuzzy Systems, vol. 35, no. 16, pp. 1–6, 2018. to correctly perform the reaction process of biochemical [11] L. Liu, J. Yao, D. He et al., “Global dynamic path planning detection and analysis. Each droplet is interpreted as a point fusion algorithm combining jump-A algorithm and dynamic robot moving in a discrete two-dimensional configuration window approach,” IEEE Access, vol. 9, pp. 19632–19638, space. Under this assumption, path planning of the droplets [12] A. Tiwari and S. Varma Nadimpalli, “New fusion algorithm becomes a motion planning problem with multiple moving provides an alternative approach to robotic path planning,” robots [31–34]. .erefore, in the future research, we will International Journal of Information Engineering and Elec- further try to use ant colony algorithm to solve the droplet tronic Business, vol. 12, no. 3, pp. 1–7, 2020. path planning and scheduling problem of DMFB. [13] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: op- timization by a colony of cooperating agents,” IEEE Trans- Data Availability actions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29–41, 1996. .e data used to support the findings of this study are [14] X.-L. Cao, Z.-W. Wang, J. Feng, M. Zha, and Y.-H. Wang, available from the corresponding author upon request. “Global path planning of robots based on improved ant colony algorithm,” Computer Engineering and Science, vol. 42, Conflicts of Interest no. 3, pp. 187–193, 2020. [15] J.-L. Bai, H.-H. Chen, Y.-B. Hu, M.-W. He, X.-D. Liang, and .e authors declare that there are no conflicts of interest D. Park, “Ant colony algorithm base on negative feedback and regarding the publication of this paper. its application on robot path planning,” Computer Integrated Manufacturing Systems, vol. 25, no. 7, pp. 1–9, 2019. Acknowledgments [16] J. Zhao, Y.-F. Tang, G.-P. Jiang, F.-Y. Xu, and J. Ding, “Mobile robot path planning base on improved ant colony algorithm,” .is work was supported by the Anhui Province University Journal of Nanjing University of Posts and Telecommunica- tions (Natural Science Edition), vol. 39, no. 6, pp. 73–78, 2019. Outstanding Young Talent Support Program Project (no. [17] X. Ma and H. Mei, “Mobile robot global path planning based gxyq2019072) and the Anhui Provincial Quality Engineering on improved ant colony system algorithm with potential Project for University (no. 2020jyxm2151). field,” Journal of Mechanical Engineering, vol. 57, no. 1, pp. 19–27, 2021. References [18] S. Tian, Y. Li, Y. Kang, and J. Xia, “Multi-robot path planning in wireless sensor networks based on jump mechanism PSO [1] D. H. Zhang, X. M. You, S. Liu, and H. Pan, “Dynamic multi- and safety gap obstacle avoidance,” Future Generation role adaptive collaborative ant colony optimization for robot Computer Systems, vol. 118, no. 6, pp. 37–47, 2020. path planning,” IEEE Access, vol. 8, pp. 129958–129974, 2020. [19] X. Guo, M. Ji, Z. Zhao, D. Wen, and W. Zhang, “Global path [2] F. L. Li, “An optimization path planning method based on planning and multi-objective path control for unmanned evolutionary artificial potential field,” Applied Mechanics and surface vehicle based on modified particle swarm optimiza- Materials, vol. 380-384, no. 384, pp. 1414–1417, 2013. tion (PSO) algorithm,” Ocean Engineering, vol. 216, Article ID [3] E. W. Dijkstra, “A note on two problems in connexion with 107693, 2020. graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, [20] Z. Wang, J. Li, M. Fang, and Y. Li, “A multimetric ant colony optimization algorithm for dynamic path planning in ve- [4] C. Huang, J. Fei, Y. Liu, H. Li, and X. Liu, “Smooth path hicular networks,” International Journal of Distributed Sensor planning method based on dynamic feedback A ant colony Networks, vol. 2015, Article ID 271067, 10 pages, 2015. algorithm,” Transactions of the Chinese Society for Agricultural [21] W. Gao, Q. Tang, B. Ye, Y. Yang, and J. Yao, “An enhanced Machinery, vol. 48, no. 4, pp. 34–40, 2017. heuristic ant colony optimization for mobile robot path [5] L. Yue and H. Chen, “Unmanned vehicle path planning using planning,” Soft Computing, vol. 24, no. 2, pp. 6139–6150, 2020. a novel ant colony algorithm,” EURASIP Journal on Wireless [22] Q. Luo, H. Wang, Y. Zheng, and J. He, “Research on path Communications and Networking, vol. 2019, no. 1, pp. 1–9, 2019. planning of mobile robot based on improved ant colony al- gorithm,” Neural Computing and Applications, vol. 32, no. 6, [6] C. Lamini, S. Benhlima, and A. Elbekri, “Genetic algorithm based approach for autonomous mobile robot path planning,” pp. 1555–1566, 2020. [23] J. Ning, Q. Zhang, C. Zhang, and B. Zhang, “A best-path- Procedia Computer Science, vol. 127, pp. 180–189, 2018. [7] Y. K. Ever, “Using simplified swarm optimization on path updating information-guided ant colony optimization algo- rithm,” Information Sciences, vol. 433-434, no. 434, planning for intelligent mobile robot,” Procedia Computer Science, vol. 120, pp. 83–90, 2017. pp. 142–162, 2018. [8] T. Gong and M. Wang, “An improved immune algorithm for [24] T. Stutzle and H. Hoos, “MAX-MIN ant system and local solving path optimization problem in deep immune learning search for the traveling salesman problem,” in Proceedings of 10 Journal of Robotics 1997 IEEE International Conference on Evolutionary Com- putation (ICEC ’97), pp. 309–314, Indianapolis, IN, USA, April 1997. [25] L. C. Lu and T. W. Yue, “Mission-oriented ant-team ACO for min-max MTSP,” Applied Soft Computing, vol. 76, pp. 436– 444, 2018. [26] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, 1997. [27] G. Z. Tan, H. Huan, and A. Sloman, “Ant colony system algorithm for real-time globally optimal path planning of mobile robots,” Acta Automatica Sinica, vol. 33, no. 3, pp. 279–285, 2007. [28] S.-Z. Zhou, Z.-H. Zhan, Z.-G. Chen, S. Kwong, and J. Zhang, “A multi-objective ant colony system algorithm for airline crew rostering problem with fairness and satisfaction,” IEEE Transactions on Intelligent Transportation Systems, pp. 1–15, [29] F. Sapuppo, F. Schembri, L. Fortuna, and M. Bucolo, “Microfluidic circuits and systems,” IEEE Circuits and Systems Magazine, vol. 9, no. 3, pp. 6–19, 2009. [30] F. Schembri, F. Sapuppo, and M. Bucolo, “Experimental classification of nonlinear dynamics in microfluidic bubbles’ flow,” Nonlinear Dynamics, vol. 67, no. 4, pp. 2807–2819, [31] K. F. Bohringer, “Modeling and controlling parallel tasks in droplet-based microfluidic systems,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 2, pp. 334–344, 2006. [32] I. Pan, P. Dasgupta, H. Rahaman, and T. Samanta, “Ant colony optimization based droplet routing technique in digital microfluidic biochip,” in Proceedings of the 2011 International Symposium on Electronic System Design, pp. 223–229, Kochi, India, December 2011. [33] W. Zheng, H. Yu, L. Feng, P. Fu, and H. Jiang, “Single droplet on-line testing path optimization for digital microfluidic biochips based on the improved ant colony algorithm,” in Proceedings of the 2017 IEEE International Instrumentation and Measurement Technology Conference (I2MTC), pp. 1–6, Turin, Italy, May 2017. [34] S. Mukherjee, I. Pan, and T. Samanta, “A particle swarm optimization method for fault localization and residue re- moval in digital microfluidic biochips,” Applied Soft Com- puting, vol. 85, no. 1, Article ID 105839, 2019.

Journal

Journal of Robotics – Hindawi Publishing Corporation

Published: Sep 10, 2021

There are no references for this article.