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

Learn More →

Robot Path Planning Using Improved Ant Colony Algorithm in the Environment of Internet of Things

Robot Path Planning Using Improved Ant Colony Algorithm in the Environment of Internet of Things Hindawi Journal of Robotics Volume 2022, Article ID 1739884, 8 pages https://doi.org/10.1155/2022/1739884 Research Article Robot Path Planning Using Improved Ant Colony Algorithm in the Environment of Internet of Things 1 2 1 Hongliu Huang , Guo Tan , and Linli Jiang School of Mathematics and Computer Science, Guangxi Science and Technology Normal University, Laibin, Guangxi 546199, China Experimental Training Centre, Guangxi Science and Technology Normal University, Laibin, Guangxi 546199, China Correspondence should be addressed to Guo Tan; 47462043@qq.com Received 18 January 2022; Revised 16 March 2022; Accepted 17 March 2022; Published 4 April 2022 Academic Editor: Shan Zhong Copyright © 2022 Hongliu Huang 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. It is a research topic of practical significance to study the path planning technology of mobile robot navigation technology. Aiming at the problems of slow convergence speed, redundant planning path, and easy to fall into local optimal value of ant colony algorithm in a complex environment, a robot path planning based on improved ant colony algorithm is proposed. First, the grid method is used to model the path environment, which marks each grid to make the ant colony move from the initial grid to the target grid for path search. Second, the ant colony is divided according to different planning tasks. Let some ants explore the way first, and carry out basic optimization planning for the map environment. -e antecedent ants mark the basic advantage on a target value of the path with pheromone concentration so as to guide the subsequent route-finding operation of the main ant colony. Finally, in order to avoid the individual ants falling into a deadlock state in the early search, the obstacle avoidance factor is increased, the transition probability is improved, and the amount of information on each path is dynamically adjusted according to the local path information, so as to avoid the excessive concentration of pheromones. Experimental results show that the algorithm has high global search ability, significantly speeds up the convergence speed, and can effectively improve the efficiency of mobile robot in path planning. navigation [6–8]. -e navigation of mobile robot refers to 1. Introduction “based on the surrounding environment information per- Nowadays, with the continuous integration of informati- ceived by the sensors carried by the mobile robot and the zation and industrialization, the intelligent industry repre- state information of the mobile robot, the target-oriented sented by robot technology is booming, which is also the key motion of the mobile robot can be realized safely in the development field of scientific and technological innovation environment containing a limited number of obstacles.” in various countries [1–4]. Only when the mobile robot accurately grasps its own position and the position of obstacles in its environment, can Mobile robots can be divided into three types: remote control, semiautonomy, and autonomy. Autonomous mo- it safely realize the target-oriented movement and complete bile robots have the ability to perceive, make decisions, and the navigation task [9–11]. -erefore, the research on path adapt to the environment, so they can meet a wider range of planning technology in mobile robot navigation technology task requirements [5]. At present, the focus and difficulty of is a research topic with practical significance. mobile robot research are how to make the robot complete a After decades of development, researchers have pro- predetermined task autonomously in a complex environ- posed many effective path planning methods, such as a ment. -e process of a mobile robot completing a pre- algorithm, genetic algorithm, and fuzzy logic algorithm determined task autonomously is called mobile robot [9, 12–15]. Ant colony algorithm has fast convergence speed, 2 Journal of Robotics but it also has some problems, such as algorithm search (2) By increasing the obstacle avoidance factor and stagnation, and is easy to fall into local optimization. In improving the transition probability, it greatly avoids the individual ant falling into a deadlock state in the order to solve these problems, researchers have proposed many improvement strategies [16–19]. Reference [20] an- early search. By dynamically adjusting the amount of alyzed the influence of pheromone Volatilization Coefficient information on each path according to the local path on the optimization ability of ant colony algorithm and information, the excessive concentration of phero- proposed an adaptive pheromone Volatilization Coefficient mones is avoided, which speeds up the speed of path to improve the global searchability. In order to avoid falling planning. into local optimization, [21] considered the path length and time of each ant and proposed an adaptive ant colony 2. Introduction to Problem Model optimization algorithm to balance the optimal path and When the robot performs a task, its working area is divided planning time. Reference [22] proposed a free step ant into grids. In size 30 × 30 grid map as an example. -e robot colony algorithm and designed the corresponding local can pass through the white area normally, and black is an pheromone update rules. -e simulation showed that the obstacle. When the robot does not encounter obstacles, it path found by this algorithm is shorter and the convergence can move in any direction at its current position and cannot is better. Reference [23] designed a path planner composed return. Grid coordinates are as follows: of heterogeneous ant colonies. Different kinds of ant col- onies have different visual ranges and motion speeds and x � mod(i, N) − 0.5, modified the state transition rules and pheromone update (1) method. Reference [24] uses the genetic algorithm to gen- y � N + 0.5 − ceil􏼒 􏼓, erate the initial path to reduce the blindness of the ant colony algorithm in the initial search and then uses the ant colony where N is the number of rows and columns of the grid map algorithm to further optimize the initial path. Reference [25] and i is the grid sequence number, as shown in Figure 1. obtained a series of suboptimal solutions by roughly In order to ensure that the mobile robot can effectively searching the initial pheromone distribution of the ant avoid obstacles, the obstacles are expanded according to the colony algorithm and then obtained the optimal solution by the ant colony algorithm. Reference [26] studied the physical size. -e expanded size of the obstacles is the sum of the radius of the mobile robot and the safe reserved distance updating strategy of residual pheromone and proposed an improved ant colony algorithm to solve the time-dependent so the mobile robot can be regarded as a particle. If there are irregular obstacles in the working environment, when it fills road network planning problem. Reference [27] used the search mode of the visual field to limit the search range, one or more grids, the additional part is still recorded as a grid. adopted the deadlock-free mechanism for the deadlock problem, and proposed an improved pheromone update algorithm. Reference [28] introduced the evaluation func- 3. Global Path Planning Based on Improved Ant tion and bending suppression operator of a algorithm, Colony Algorithm improved the heuristic information of the ant colony al- gorithm, and speeded up the convergence speed. -e results Ant colony algorithm is easy to fall into local optimization and slow convergence. In order to find the optimal path and showed that the improved ant colony algorithm is more efficient. Most of the above improved algorithms are avoid blind search, a global path planning method based on committed to improving the search efficiency of the ant an improved ant colony algorithm is proposed in this article. colony algorithm and getting the shortest search path possible, but they have not studied other optimal factors of 3.1. Ant Population Adaptive Strategy. In the classical ant the path. colony algorithm, the task of each ant is roughly the same. In Based on the above analysis, aiming at the problems of addition to the sharing of information, the behavior of ants is slow convergence speed and path redundancy of ant colony relatively independent. -is method has brought many algorithm, a robot path planning method based on an benefits in the single-objective programming problem, but it improved ant colony algorithm is proposed. In the proposed is insufficient if still used in the multiobjective programming method, the working area of the mobile robot is modeled by problem. In the way of independent action, ant individual the grid method, and each grid is marked to make the ant needs to measure multiple target values to release phero- colony move from the initial grid to the target grid for path mones independently, so it needs to obtain an overall search. -e contribution of the proposed method is sum- evaluation value in one way, which is the standard to release marized as follows: the corresponding concentration of pheromones. In this (1) An adaptive strategy of ant population division is way, the advantages and disadvantages of various target proposed, which divides the ant population values in the information left for subsequent ants are mixed according to different planning tasks, allows some together, and the information is relatively vague. It is unable ants to explore the way first, and makes basic op- to give the different advantages and disadvantages of the timization planning for the map environment so that path in the two target values, which is not conducive to the the mobile robot can quickly find the optimal path. distinction and selection of subsequent ants and reduces the Journal of Robotics 3 Start Pheromone initialization e first ant colony carries 15 out the planning task e cost based global Periodic programming results iteration are obtained e main ant colony 10 15 20 25 30 carries out the planning task Figure 1: Grid map. End diversity of understanding to some extent. At the same time, there is such a situation that in a map, the distribution of Figure 2: Algorithm flow. path cost is uneven, the cost values between different regions are very different, but the difference between the path lengths of different sections is almost the same. At this time, 3.2. Transition Probability Improvement. Due to the limi- if one set of criteria is used to determine the distribution of tation of the algorithm tabu table, ants can only move pheromones, it will inevitably lose its adaptability. -erefore, forward and cannot go back in the process of finding the in order to adapt to multiple target values, an adaptive path, which makes a large number of ants fall into a locked strategy for ant population division is proposed. By dividing state in the early search, and finally “lose,” that is, stop the the ant population according to different planning tasks, let search without reaching the end. As shown in Figure 3, for some ants explore the way first, carry out basic optimization the three paths A, B, and C, because the ants fall into planning for the map environment, and then let the main ant deadlock and stay at the last searched path node, they do not group carry out pathfinding operation based on the planning reach the target point safely and correctly, and the path results obtained by the previous ant group. In other words, search efficiency is low. Especially when the environment let the antecedent ants mark the basic advantage of a target scale becomes larger and the terrain is complex, the deadlock value of the path with pheromone concentration so as to phenomenon of the ant colony algorithm is more serious. bring planning guidance to the subsequent pathfinding In the t-th iteration, the state transition probability of the operation of the main ant group. As mentioned above, the ant k selecting the next node j from the current node i is as proposed improved algorithm splits the ant colony as follows: follows: α β ⎧ ⎪ 􏽨τ (t)􏽩 􏽨n (t)􏽩 ij ij pre Antecedent ant colony , j ∈ C , ⎪ k α β AntNum􏼨 , ⎨ 􏽐 􏽨τ (t)􏽩 􏽨n (t)􏽩 j∈C ij ij AntNum − pre Main pathfinding ant colony p (t) � (3) ij ⎪ (2) ⎪ 0, j ∉ C , where pre is the number of antecedent ant groups. -e antecedent ant group will optimize according to the target where C represents the set of all reachable path nodes in the value of path traffic cost to obtain the result of global cost next step and α is the information heuristic factor. -e larger planning. -en, based on the cost planning results, the main the value α, the stronger the guiding role of the pheromone. pathfinding ant group optimizes the path by comprehensive β is the expected heuristic factor. τ is the pheromone ij indicators. In this way, multiple target values have obvious concentration of the path and n is the heuristic function. ij advantages in their respective target fields, which can better Deadlock ants are inevitable in the ant colony algorithm. reflect the advantages and disadvantages of different paths. -e fundamental reason is that when searching the path, -erefore, the pathfinding process of the algorithm is ants will inevitably encounter the situation that the sur- generally divided into two steps, as shown in Figure 2. rounding nodes have passed or there are obstacles. Ants 4 Journal of Robotics 10 15 20 Path A Path B Path C Figure 3: Algorithm flow. cannot pass through and can only stay in place. -erefore, where N is the maximum number of iterations, N is the max m the obstacle avoidance strategy is adopted at the initial stage current number of iterations, and δ is the adjustment co- of search, and the obstacle avoidance factor s is introduced efficient, the value range of which is (0.5, 1). as follows: α β ε 3.3. Pheromone Update. In the standard ant colony opti- ⎧ ⎪ τ (t) n (t) s 􏽨 􏽩 􏽨 􏽩 􏽨 􏽩 ij ij j ⎪ , j ∈ C , mization algorithm, set τ (0) � C, where C is a constant. k ij α β ε 􏽐 􏽨τ (t)􏽩 􏽨n (t)􏽩 􏽨s 􏽩 In order to accelerate the early convergence speed of the j∈C ij ij j p (t) � (4) ij algorithm, this article changes the method of selecting τ (0) as a constant and proposes an initialization allo- ij 0, j ∉ C , cation of τ according to the proportion of the local path ij length d in the lengths of all connected paths between A − O − L ij j j j s � , (5) points i and j. τ (0) � Z · M , where O is the total number of grids adjacent to the node j ij j j ⎧ ⎪ and with obstacles and L refers to the total number of grids (7) adjacent to the node j and restricted by the tabu table. A is j ⎪ ⎪ d ij the total number of grids adjacent to the node j and ε is the ⎪ Z � , average d i,j∈n ij obstacle avoidance coefficient, which takes a small positive number. By adding the obstacle avoidance strategy, the ants where d avoid the surrounding obstacles as much as possible every represents the distance between two nodes i and j, ij time they iterate to search the path, and the number of average􏽐 d represents the average distance of all paths i,j∈n ij directly connected to nodes i and j, and M represents the deadlock ants is significantly reduced. Parameter adaptive pseudorandom transfer strategy is adopted as follows: number of paths connected to node j. -e initialization allocation method of τ comprehen- ij α β ε ⎧ ⎪ sively considers the ratio Z of the length of a path to the arg max τ (t) n (t) s , q≤ q , 􏼒􏽨 􏽩 􏽨 􏽩 􏽨 􏽩 􏼓 ij ij j 0 average length of the paths in the local region and the j � ⎪ number of paths M that ants can choose next. Figure 4 ⎪ j p , else, (6) ij shows the path diagram of two points connected. -e more the paths to be selected, the greater the diversity of algorithm N − N max m solutions. -e calculation formula of average 􏽐 d is as i,j∈n ij q � δ , follows: max Journal of Robotics 5 3.4. Specific Implementation Steps of Improved Algorithm. a d d =c i,j -e improved ant colony algorithm divides the ant colony j into two parts. Each part has its own planning task. On the whole, the steps of the algorithm are as follows: Step 1: Set the corresponding parameters required by Figure 4: Path connected with two points. the algorithm and read the grid map information, including the grid map scale and some content in- formation. -e required parameters include the fol- a + b + c + d + e + f lowing: grid size, number of ant populations, number average 􏽘 d � . ij (8) i,j∈n of antecedent ant populations, number of iterations, initial amount of pheromone, and pheromone weight. It is called an iterative process that all ants in the ant Step 2: Initialize all ants, including the ant taboo table, colony with population W move once. After n iterative path table, path length, total traffic cost, and initial processes, all ants complete a cycle. At this time, the position of ants. pheromone on each path that the ants pass through needs to Step 3: -e cycle iteration starts, and the antecedent ant be adjusted. After the ants complete a cycle, it will produce group starts planning tasks. an optimal solution l and the worst solution l in the Best Worst current cycle: Step 4: -e antecedent ants calculate the transfer probability according to the formula, then select the l + l Best Worst (9) l ≤ . walking node, and update the path table, path length, s⟶g total communication cost, and other information. If the After determining the path that meets the update con- ant reaches the destination, the pheromone concen- ditions, update the pheromone of each path according to tration on the path is updated and volatilized according formula (10). ρ is pheromone residue operator and Δτ to the pheromone update and volatilization rules. ij represents the amount of pheromone left by ants on the path Step 5: If all the antecedent ant groups reach the i ⟶ j: destination, continue the planning task of the main ant group; otherwise, turn to Step 4 to continue to find the τ (t + 1) � ρτ (t) + Δτ . (10) ij ij ij way. Among them, Step 6: -e main ant colony carries out the planning task. According to the pheromone concentration left by ⎧ ⎪ ⎪ ε , If the ant passes the path i ⟶ j, the antecedent ant, the transfer probability is calculated ⎨ d ij Δτ � (11) ij according to formula (4). -e path is selected by combining the two target values, and the relevant in- 0, else, formation table and variables are updated after selecting the next node. If the ant reaches the desti- min ⎧ ⎪ d ⎪ j nation, the pheromone concentration on the path is , M ≥ M , j i updated and volatilized according to the pheromone ⎪ d ⎨ ij ε � (12) update and volatilization rules. min Step 7: If all ants complete the planning task, retain the ⎪ i , M < M , j i d global optimal path information, compare the obtained ij paths, and give corresponding rewards and punish- min where d represents the distance between nodes i and j, d ments according to the advantages and disadvantages ij j represents the shortest path distance among all paths con- of the paths. nected to node j, M represents the number of paths Step 8: If all the iteration cycle has been completed at connected to node i, M represents the number of paths this time, the planning result is output and the algo- connected to node j, andM and M do not include path i j rithm ends. Otherwise, turn to Step 3, reset the ant i ⟶ j. Formula (12) updates the pheromone of each path information and continue the iteration. according to different conditions by using the local path information of the area around each path. It can be seen that this algorithm only allows some ants to find relatively short 4. Example Verification and Discussion paths to update pheromones. According to the path length obtained by ants in this cycle, select to increase the amount 4.1. Simulation Environment Setting and Parameter Selection. of information of some better paths and dynamically adjust In this article, MATLAB R2016a simulation software is used the amount of information on each path according to the to simulate the path planning process of the mobile robot on local path information so as to avoid the excessive con- the ground with obstacles. Because Roulette is used in the centration of pheromones. -is algorithm accelerates the simulation process of the ant colony algorithm, the results convergence speed and optimization ability of the algorithm will be different each time. In the simulation, the method of and avoids premature convergence of the algorithm. averaging multiple experiments is adopted. -e simulation 6 Journal of Robotics Table 1: Initialization parameters. Parameter Value ρ 0.2 C 15 σ 1 y 100 l 1 W 80 Q 100 100 1000 90 800 80 600 70 400 60 200 50 0 0 2 4 6 8 10 12 14 β/α Comprehensive index Number of dead ants Figure 5: β/α variation curve. Table 2: Comparison of 30 m × 30 m environmental experiment results. Optimal Number of Number of convergence Algorithm Robot running Algorithm path length (m) path nodes iterations running time (s) time (s) Ant colony algorithm 44.623 21 40 22.368 150.876 Reference [26] 42.569 12 23 20.157 127.148 Reference [28] 42.357 11 20 20.845 125.758 Proposed algorithm 41.248 9 8 17.236 120.347 show that when α is large and β is small, the ant search path environment is Windows 10 64-bit operating system, Intel Core I5-3210m CPU @ 2.50 GHz processor, 8 GB memory. is chaotic, many ants are entering the dead end, and the At present, there is no perfect theoretical method for the number of ants moving towards the target grid is small, so parameter selection of the ant colony algorithm. -e usual the algorithm is easy to fall into local optimization. When method is to take values according to experience and the value of β/α is about 10, the algorithm has a wide search compare them through experiments to obtain better pa- range and obtains better results, as shown in Figure 5. When rameter values. In this article, the parameter selection ex- the value of β/α continues to increase, the convergence speed periment is carried out on a 30m × 30 m map. Because the of the algorithm slows down, and it is easy to fall into the main parameters of the ant colony algorithm are α and β, local optimal situation only under the guidance of local heuristic information. -erefore, take α � 1, β � 10. this article only shows the value selection process of α and β. -e values of other parameters are shown in Table 1 according to experience and experimental simulation 4.2. Comparison of Simulation Results. At 30m × 30 m comparison. Change α and β based on the above values. α reflects the complex environment, the proposed algorithm, ant colony algorithm, the algorithm in literature [26], and the algorithm importance of the inspiration of the previous ant colony to the current ant, and β reflects the importance of the in- in literature [28] are compared and analyzed. Set the grid size to 1 m × 1 m; the average speed of the mobile robot is spiration of the current local environment to the ant. -e values of the two are relative, so they must be combined to 0.5 m/s. Considering safety factors, set the deceleration of the mobile robot to 0.1 m/s when reaching each node. In change. In order to facilitate the experiment, let α � 1, so the value of β/α equals the value of β. -e simulation results addition, the turning time is set to 1 s at each node. -e Comprehensive index of optimal path Number of ants walking into the dead end Journal of Robotics 7 30 70 0 10 20 30 40 50 60 Number of iterations Ant colony algorithm Literature[29] Proposed algorithm Literature[27] Figure 8: Comparison of the number of high-quality solutions of the four algorithms. -rough comparison, it can be seen that the improved 5 1015202530 algorithm in this article still achieves good results in im- Figure 6: Improved algorithm planning path. proving deadlock ants in complex environment and greatly reduces the number of deadlock ants. -is shows the supe- riority of this algorithm, which still has high global perfor- mance and fast convergence in complex environment. Due to the reduction of turning times and driving time, the energy consumption of mobile robot is most likely to be reduced. -e larger the environmental scale is, the more complex the terrain is, and the more obvious the advantages are. 5. Conclusion In order to solve the problems of slow convergence speed and easy to fall into local optimal value in path planning, a robot 40 path planning method based on an improved ant colony 0 10 20 30 40 50 60 70 algorithm is proposed. -e main improvements are as fol- Number of iterations lows: the grid method is used for modeling, and each grid is Ant colony algorithm Literature[29] marked. Let the antecedent ants mark the basic advantage on Proposed algorithm Literature[27] a target value of the path with pheromone concentration so as to guide the subsequent pathfinding operation of the main ant Figure 7: Comparison of convergence curves. group. -e obstacle avoidance factor is added to improve the transition probability, and the amount of information on each path is dynamically adjusted according to the local path experimental data are shown in Table 2. -e basic ant colony information to avoid the excessive concentration of phero- algorithm finds the global optimal value of 44.623 m in the mones. Experiments show that compared with the compar- 40th iteration. In [26], the algorithm converged to 42.569 m ative references, the iteration times of the proposed algorithm in the 23rd iteration, and in [28], the algorithm converged to are reduced by 65.22% and 60.00%, respectively, and the travel 42.357 m in the 20th iteration. -e proposed algorithm time of the mobile robot is reduced by 5.35% and 4.30%, converged in the 8th iteration and found the global optimal respectively, which can effectively improve the work efficiency value of 41.248 m. Compared with [26] and [28], the number of the mobile robot in path planning. of iterations of the algorithm is reduced by 65.22% and In the future research, we will study how to complete 60.00%, respectively, the number of turns is reduced by efficient and high-quality path planning tasks in a dynamic 25.00% and 18.18%, respectively, the path length is reduced environment. Moreover, a neural network can be used to by 3.10% and 2.62%, respectively, and the driving time of dynamically calculate various parameters and weights to mobile robot is reduced by 5.35% and 4.30%, respectively make the planning more intelligent. [29]. Figure 6 shows the path planning diagram of the improved algorithm, Figure 7 shows the comparison of the Data Availability convergence curves of the four algorithms, and Figure 8 shows the comparison of the number of high-quality so- -e data used to support the findings of this study are in- lutions of the three algorithms. cluded within the article. Optimal path length Quantity of high quality solutions 8 Journal of Robotics vehicles,” Defence Science Journal, vol. 69, no. 2, pp. 167–172, Conflicts of Interest [14] L. Wang, C. Luo, M. Li, and J. Kai, “Trajectory planning of an -e authors declare that there are no conflicts of interest autonomous mobile robot by evolving ant colony system,” regarding the publication of this article. International Journal of Robotics and Automation, vol. 32, no. 4, pp. 33–43, 2017. Acknowledgments [15] X.-Y. Zhang, M. Wu, J. Peng, and K.-C. Lin, “Target attraction based ant colony for dynamic path planning of rescue robot,” -is work was supported by the National Natural Science Journal of System Simulation, vol. 9, no. 5, pp. 48–56, 2011. Fund Project (No. 42065004) and the project for improving [16] M. R. Jabbarpour, H. Zarrabi, J. J. Jung, and P. Kim, “A green the basic scientific research ability of young and middle-aged ant-based method for path planning of unmanned ground teachers in Guangxi Colleges and Universities (No. vehicles,” IEEE access, vol. 5, no. 11, pp. 1820–1832, 2017. [17] C. Sahu, D. R. Parhi, and P. B. Kumar, “An approach to 2019KY0868). optimize the path of humanoids using adaptive ant colony optimization,” Journal of Bionics Engineering, vol. 15, no. 4, References pp. 623–635, 2018. [18] M. J. Rostami, A. Zarandi, and S. M. Hoseininasab, “MSDP [1] L. Xie, L. Yan, X. Zhang, and H. Zhang, “A security situation with ACO: a maximal SRLG disjoint routing algorithm based assessment model of information system for smart mobile on ant colony optimization,” Journal of Network and Com- devices,” Wireless Communications and Mobile Computing, puter Applications, vol. 35, no. 1, pp. 394–402, 2012. vol. 2020, Article ID 8886516, 11 pages, 2020. [19] X. Jiang, Z. Lin, T. He, X. Ma, S. Ma, and S. Li, “Optimal path [2] H. Choset, “Coverage for robotics–a survey of recent results,” finding with beetle antennae search algorithm by using ant Annals of Mathematics and Artificial Intelligence, vol. 31, no. 1, colony optimization initialization and different searching pp. 113–126, 2001. strategies,” IEEE Access, vol. 8, no. 12, pp. 15459–15471, 2020. [3] S. Aggarwal and N. Kumar, “Path planning techniques for [20] C. C. Yuan, Y. Wei, J. Shen et al., “Research on path planning unmanned aerial vehicles: a review, solutions, and chal- based on new fusion algorithm for autonomous vehicle,” lenges,” Computer Communications, vol. 149, no. 5, International Journal of Advanced Robotic Systems, vol. 17, pp. 270–299, 2020. no. 3, pp. 172–181, 2020. [4] H. Jahanshahi, M. Jafarzadeh, N. Naeimeh, V.-T. Pham, [21] J. Liu, J. Yang, H. Liu, and X. Tian, “An improved ant colony V. H. Van, and Q. N. Xuan, “Robot motion planning in an algorithm for robot path planning,” Soft Computing, vol. 21, unknown environment with danger space,” Electronics, vol. 8, no. 19, pp. 5829–5839, 2017. no. 2, pp. 201–212, 2019. [22] M. R. Zeng, L. Xi, and A. M. Xiao, “-e free step length ant [5] B. Sahu, P. K. Das, M. R. Kabat, and R. Kumar, “Multi-robot colony algorithm in mobile robot path planning,” Advanced cooperation and performance analysis with particle swarm Robotics, vol. 30, no. 23, pp. 1509–1514, 2016. optimization variants,” Multimedia Tools and Applications, [23] J. Lee, “Heterogeneous-ants-based path planner for global vol. 5, no. 9, pp. 1–24, 2021. path planning of mobile robot applications,” International [6] R. Liu and X. Zhang, “A review of methodologies for natural- Journal of Control, Automation and Systems, vol. 15, no. 4, language-facilitated human–robot cooperation,” Interna- pp. 1754–1769, 2017. tional Journal of Advanced Robotic Systems, vol. 16, no. 3, [24] L. Wang, C. Luo, M. Li, and J. Cai, “Trajectory planning of an pp. 172–179, 2019. autonomous mobile robot by evolving ant colony system,” [7] G. S. Chirikjian, “Design and analysis of some non- International Journal of Robotics and Automation, vol. 32, anthropomorphic, biologically inspired robots: an overview,” no. 4, pp. 1500–1515, 2017. Journal of Robotic Systems, vol. 18, no. 12, pp. 701–713, 2001. [25] W. Deng, R. Chen, B. He, Y. Liu, L. Yin, and J. Guo, “A novel [8] B. C. Mohan and R. Baskaran, “A survey: ant colony opti- two-stage hybrid swarm intelligence optimization algorithm mization based recent research and implementation on sev- and application,” Soft Computing, vol. 16, no. 10, pp. 1707– eral engineering domain,” Expert Systems with Applications, 1722, 2012. vol. 39, no. 4, pp. 4618–4627, 2012. [26] H. Fa-Mei, X. Yi-na, W. Xu-ren, X. Meng-bo, and X. Zi-han, [9] B. K. Patle, A. Pandey, D. R. K. Parhi, J. Anne, and “An improved ant colony algorithm for solving time-de- B. L. Ganesh, “A review: on path planning strategies for pendent road network path planning problem,” in Proceedings navigation of mobile robot,” Defence Technology, vol. 15, no. 4, of the 2019 6th International Conference on Information pp. 582–606, 2019. Science and Control Engineering (ICISCE), pp. 126–130, IEEE, [10] B. Velusamy and S. C. Pushpan, “A review on swarm intel- Shanghai, China, December 2019. ligence based routing approaches,” International Journal of [27] L. Wang, J. Kan, J. Guo, and C. Wang, “3D path planning for Engineering and Technology, vol. 9, no. 3, pp. 182–195, 2019. the ground robot with improved ant colony optimization,” [11] Z. Masoumi, J. Van Genderen, and A. Sadeghi Niaraki, “An Sensors, vol. 19, no. 4, pp. 815–824, 2019. improved ant colony optimization-based algorithm for user- [28] X. Dai, S. Long, Z. Zhang, and D. Gong, “Mobile robot path centric multi-objective path planning for ubiquitous environ- planning based on ant colony algorithm with A heuristic ments,” Geocarto International, vol. 36, no. 2, pp. 137–154, 2021. method,” Frontiers in Neurorobotics, vol. 13, no. 5, pp. 15–26, [12] V. Sangeetha, R. Krishankumar, K. S. Ravichandran, and S. Kar, “Energy-efficient green ant colony optimization for [29] A. Majumder, “Contrast enhancement of multi-displays using path planning in dynamic 3D environments,” Soft Computing, human contrast sensitivity,” in Proceedings of the IEEE vol. 25, no. 6, pp. 4749–4769, 2021. Computer Society Conference on Computer Vision and Pattern [13] V. Sangeetha, K. S. Ravichandran, S. Shekhar, and Recognition (CVPR’05), pp. 377–382, IEEE, Piscataway, NJ, M. T. Anand, “An intelligent gain-based ant colony opti- USA, July 2005. misation method for path planning of unmanned ground http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Robotics Hindawi Publishing Corporation

Robot Path Planning Using Improved Ant Colony Algorithm in the Environment of Internet of Things

Huang, Hongliu; Tan, Guo; Jiang, Linli
Journal of Robotics , Volume 2022 – Apr 4, 2022
Download PDF
8 pages

Loading next page...
 
/lp/hindawi-publishing-corporation/robot-path-planning-using-improved-ant-colony-algorithm-in-the-Wtf2l0zbmp

References (30)

Publisher
Hindawi Publishing Corporation
Copyright
Copyright © 2022 Hongliu Huang 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/2022/1739884
Publisher site
See Article on Publisher Site

Abstract

Hindawi Journal of Robotics Volume 2022, Article ID 1739884, 8 pages https://doi.org/10.1155/2022/1739884 Research Article Robot Path Planning Using Improved Ant Colony Algorithm in the Environment of Internet of Things 1 2 1 Hongliu Huang , Guo Tan , and Linli Jiang School of Mathematics and Computer Science, Guangxi Science and Technology Normal University, Laibin, Guangxi 546199, China Experimental Training Centre, Guangxi Science and Technology Normal University, Laibin, Guangxi 546199, China Correspondence should be addressed to Guo Tan; 47462043@qq.com Received 18 January 2022; Revised 16 March 2022; Accepted 17 March 2022; Published 4 April 2022 Academic Editor: Shan Zhong Copyright © 2022 Hongliu Huang 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. It is a research topic of practical significance to study the path planning technology of mobile robot navigation technology. Aiming at the problems of slow convergence speed, redundant planning path, and easy to fall into local optimal value of ant colony algorithm in a complex environment, a robot path planning based on improved ant colony algorithm is proposed. First, the grid method is used to model the path environment, which marks each grid to make the ant colony move from the initial grid to the target grid for path search. Second, the ant colony is divided according to different planning tasks. Let some ants explore the way first, and carry out basic optimization planning for the map environment. -e antecedent ants mark the basic advantage on a target value of the path with pheromone concentration so as to guide the subsequent route-finding operation of the main ant colony. Finally, in order to avoid the individual ants falling into a deadlock state in the early search, the obstacle avoidance factor is increased, the transition probability is improved, and the amount of information on each path is dynamically adjusted according to the local path information, so as to avoid the excessive concentration of pheromones. Experimental results show that the algorithm has high global search ability, significantly speeds up the convergence speed, and can effectively improve the efficiency of mobile robot in path planning. navigation [6–8]. -e navigation of mobile robot refers to 1. Introduction “based on the surrounding environment information per- Nowadays, with the continuous integration of informati- ceived by the sensors carried by the mobile robot and the zation and industrialization, the intelligent industry repre- state information of the mobile robot, the target-oriented sented by robot technology is booming, which is also the key motion of the mobile robot can be realized safely in the development field of scientific and technological innovation environment containing a limited number of obstacles.” in various countries [1–4]. Only when the mobile robot accurately grasps its own position and the position of obstacles in its environment, can Mobile robots can be divided into three types: remote control, semiautonomy, and autonomy. Autonomous mo- it safely realize the target-oriented movement and complete bile robots have the ability to perceive, make decisions, and the navigation task [9–11]. -erefore, the research on path adapt to the environment, so they can meet a wider range of planning technology in mobile robot navigation technology task requirements [5]. At present, the focus and difficulty of is a research topic with practical significance. mobile robot research are how to make the robot complete a After decades of development, researchers have pro- predetermined task autonomously in a complex environ- posed many effective path planning methods, such as a ment. -e process of a mobile robot completing a pre- algorithm, genetic algorithm, and fuzzy logic algorithm determined task autonomously is called mobile robot [9, 12–15]. Ant colony algorithm has fast convergence speed, 2 Journal of Robotics but it also has some problems, such as algorithm search (2) By increasing the obstacle avoidance factor and stagnation, and is easy to fall into local optimization. In improving the transition probability, it greatly avoids the individual ant falling into a deadlock state in the order to solve these problems, researchers have proposed many improvement strategies [16–19]. Reference [20] an- early search. By dynamically adjusting the amount of alyzed the influence of pheromone Volatilization Coefficient information on each path according to the local path on the optimization ability of ant colony algorithm and information, the excessive concentration of phero- proposed an adaptive pheromone Volatilization Coefficient mones is avoided, which speeds up the speed of path to improve the global searchability. In order to avoid falling planning. into local optimization, [21] considered the path length and time of each ant and proposed an adaptive ant colony 2. Introduction to Problem Model optimization algorithm to balance the optimal path and When the robot performs a task, its working area is divided planning time. Reference [22] proposed a free step ant into grids. In size 30 × 30 grid map as an example. -e robot colony algorithm and designed the corresponding local can pass through the white area normally, and black is an pheromone update rules. -e simulation showed that the obstacle. When the robot does not encounter obstacles, it path found by this algorithm is shorter and the convergence can move in any direction at its current position and cannot is better. Reference [23] designed a path planner composed return. Grid coordinates are as follows: of heterogeneous ant colonies. Different kinds of ant col- onies have different visual ranges and motion speeds and x � mod(i, N) − 0.5, modified the state transition rules and pheromone update (1) method. Reference [24] uses the genetic algorithm to gen- y � N + 0.5 − ceil􏼒 􏼓, erate the initial path to reduce the blindness of the ant colony algorithm in the initial search and then uses the ant colony where N is the number of rows and columns of the grid map algorithm to further optimize the initial path. Reference [25] and i is the grid sequence number, as shown in Figure 1. obtained a series of suboptimal solutions by roughly In order to ensure that the mobile robot can effectively searching the initial pheromone distribution of the ant avoid obstacles, the obstacles are expanded according to the colony algorithm and then obtained the optimal solution by the ant colony algorithm. Reference [26] studied the physical size. -e expanded size of the obstacles is the sum of the radius of the mobile robot and the safe reserved distance updating strategy of residual pheromone and proposed an improved ant colony algorithm to solve the time-dependent so the mobile robot can be regarded as a particle. If there are irregular obstacles in the working environment, when it fills road network planning problem. Reference [27] used the search mode of the visual field to limit the search range, one or more grids, the additional part is still recorded as a grid. adopted the deadlock-free mechanism for the deadlock problem, and proposed an improved pheromone update algorithm. Reference [28] introduced the evaluation func- 3. Global Path Planning Based on Improved Ant tion and bending suppression operator of a algorithm, Colony Algorithm improved the heuristic information of the ant colony al- gorithm, and speeded up the convergence speed. -e results Ant colony algorithm is easy to fall into local optimization and slow convergence. In order to find the optimal path and showed that the improved ant colony algorithm is more efficient. Most of the above improved algorithms are avoid blind search, a global path planning method based on committed to improving the search efficiency of the ant an improved ant colony algorithm is proposed in this article. colony algorithm and getting the shortest search path possible, but they have not studied other optimal factors of 3.1. Ant Population Adaptive Strategy. In the classical ant the path. colony algorithm, the task of each ant is roughly the same. In Based on the above analysis, aiming at the problems of addition to the sharing of information, the behavior of ants is slow convergence speed and path redundancy of ant colony relatively independent. -is method has brought many algorithm, a robot path planning method based on an benefits in the single-objective programming problem, but it improved ant colony algorithm is proposed. In the proposed is insufficient if still used in the multiobjective programming method, the working area of the mobile robot is modeled by problem. In the way of independent action, ant individual the grid method, and each grid is marked to make the ant needs to measure multiple target values to release phero- colony move from the initial grid to the target grid for path mones independently, so it needs to obtain an overall search. -e contribution of the proposed method is sum- evaluation value in one way, which is the standard to release marized as follows: the corresponding concentration of pheromones. In this (1) An adaptive strategy of ant population division is way, the advantages and disadvantages of various target proposed, which divides the ant population values in the information left for subsequent ants are mixed according to different planning tasks, allows some together, and the information is relatively vague. It is unable ants to explore the way first, and makes basic op- to give the different advantages and disadvantages of the timization planning for the map environment so that path in the two target values, which is not conducive to the the mobile robot can quickly find the optimal path. distinction and selection of subsequent ants and reduces the Journal of Robotics 3 Start Pheromone initialization e first ant colony carries 15 out the planning task e cost based global Periodic programming results iteration are obtained e main ant colony 10 15 20 25 30 carries out the planning task Figure 1: Grid map. End diversity of understanding to some extent. At the same time, there is such a situation that in a map, the distribution of Figure 2: Algorithm flow. path cost is uneven, the cost values between different regions are very different, but the difference between the path lengths of different sections is almost the same. At this time, 3.2. Transition Probability Improvement. Due to the limi- if one set of criteria is used to determine the distribution of tation of the algorithm tabu table, ants can only move pheromones, it will inevitably lose its adaptability. -erefore, forward and cannot go back in the process of finding the in order to adapt to multiple target values, an adaptive path, which makes a large number of ants fall into a locked strategy for ant population division is proposed. By dividing state in the early search, and finally “lose,” that is, stop the the ant population according to different planning tasks, let search without reaching the end. As shown in Figure 3, for some ants explore the way first, carry out basic optimization the three paths A, B, and C, because the ants fall into planning for the map environment, and then let the main ant deadlock and stay at the last searched path node, they do not group carry out pathfinding operation based on the planning reach the target point safely and correctly, and the path results obtained by the previous ant group. In other words, search efficiency is low. Especially when the environment let the antecedent ants mark the basic advantage of a target scale becomes larger and the terrain is complex, the deadlock value of the path with pheromone concentration so as to phenomenon of the ant colony algorithm is more serious. bring planning guidance to the subsequent pathfinding In the t-th iteration, the state transition probability of the operation of the main ant group. As mentioned above, the ant k selecting the next node j from the current node i is as proposed improved algorithm splits the ant colony as follows: follows: α β ⎧ ⎪ 􏽨τ (t)􏽩 􏽨n (t)􏽩 ij ij pre Antecedent ant colony , j ∈ C , ⎪ k α β AntNum􏼨 , ⎨ 􏽐 􏽨τ (t)􏽩 􏽨n (t)􏽩 j∈C ij ij AntNum − pre Main pathfinding ant colony p (t) � (3) ij ⎪ (2) ⎪ 0, j ∉ C , where pre is the number of antecedent ant groups. -e antecedent ant group will optimize according to the target where C represents the set of all reachable path nodes in the value of path traffic cost to obtain the result of global cost next step and α is the information heuristic factor. -e larger planning. -en, based on the cost planning results, the main the value α, the stronger the guiding role of the pheromone. pathfinding ant group optimizes the path by comprehensive β is the expected heuristic factor. τ is the pheromone ij indicators. In this way, multiple target values have obvious concentration of the path and n is the heuristic function. ij advantages in their respective target fields, which can better Deadlock ants are inevitable in the ant colony algorithm. reflect the advantages and disadvantages of different paths. -e fundamental reason is that when searching the path, -erefore, the pathfinding process of the algorithm is ants will inevitably encounter the situation that the sur- generally divided into two steps, as shown in Figure 2. rounding nodes have passed or there are obstacles. Ants 4 Journal of Robotics 10 15 20 Path A Path B Path C Figure 3: Algorithm flow. cannot pass through and can only stay in place. -erefore, where N is the maximum number of iterations, N is the max m the obstacle avoidance strategy is adopted at the initial stage current number of iterations, and δ is the adjustment co- of search, and the obstacle avoidance factor s is introduced efficient, the value range of which is (0.5, 1). as follows: α β ε 3.3. Pheromone Update. In the standard ant colony opti- ⎧ ⎪ τ (t) n (t) s 􏽨 􏽩 􏽨 􏽩 􏽨 􏽩 ij ij j ⎪ , j ∈ C , mization algorithm, set τ (0) � C, where C is a constant. k ij α β ε 􏽐 􏽨τ (t)􏽩 􏽨n (t)􏽩 􏽨s 􏽩 In order to accelerate the early convergence speed of the j∈C ij ij j p (t) � (4) ij algorithm, this article changes the method of selecting τ (0) as a constant and proposes an initialization allo- ij 0, j ∉ C , cation of τ according to the proportion of the local path ij length d in the lengths of all connected paths between A − O − L ij j j j s � , (5) points i and j. τ (0) � Z · M , where O is the total number of grids adjacent to the node j ij j j ⎧ ⎪ and with obstacles and L refers to the total number of grids (7) adjacent to the node j and restricted by the tabu table. A is j ⎪ ⎪ d ij the total number of grids adjacent to the node j and ε is the ⎪ Z � , average d i,j∈n ij obstacle avoidance coefficient, which takes a small positive number. By adding the obstacle avoidance strategy, the ants where d avoid the surrounding obstacles as much as possible every represents the distance between two nodes i and j, ij time they iterate to search the path, and the number of average􏽐 d represents the average distance of all paths i,j∈n ij directly connected to nodes i and j, and M represents the deadlock ants is significantly reduced. Parameter adaptive pseudorandom transfer strategy is adopted as follows: number of paths connected to node j. -e initialization allocation method of τ comprehen- ij α β ε ⎧ ⎪ sively considers the ratio Z of the length of a path to the arg max τ (t) n (t) s , q≤ q , 􏼒􏽨 􏽩 􏽨 􏽩 􏽨 􏽩 􏼓 ij ij j 0 average length of the paths in the local region and the j � ⎪ number of paths M that ants can choose next. Figure 4 ⎪ j p , else, (6) ij shows the path diagram of two points connected. -e more the paths to be selected, the greater the diversity of algorithm N − N max m solutions. -e calculation formula of average 􏽐 d is as i,j∈n ij q � δ , follows: max Journal of Robotics 5 3.4. Specific Implementation Steps of Improved Algorithm. a d d =c i,j -e improved ant colony algorithm divides the ant colony j into two parts. Each part has its own planning task. On the whole, the steps of the algorithm are as follows: Step 1: Set the corresponding parameters required by Figure 4: Path connected with two points. the algorithm and read the grid map information, including the grid map scale and some content in- formation. -e required parameters include the fol- a + b + c + d + e + f lowing: grid size, number of ant populations, number average 􏽘 d � . ij (8) i,j∈n of antecedent ant populations, number of iterations, initial amount of pheromone, and pheromone weight. It is called an iterative process that all ants in the ant Step 2: Initialize all ants, including the ant taboo table, colony with population W move once. After n iterative path table, path length, total traffic cost, and initial processes, all ants complete a cycle. At this time, the position of ants. pheromone on each path that the ants pass through needs to Step 3: -e cycle iteration starts, and the antecedent ant be adjusted. After the ants complete a cycle, it will produce group starts planning tasks. an optimal solution l and the worst solution l in the Best Worst current cycle: Step 4: -e antecedent ants calculate the transfer probability according to the formula, then select the l + l Best Worst (9) l ≤ . walking node, and update the path table, path length, s⟶g total communication cost, and other information. If the After determining the path that meets the update con- ant reaches the destination, the pheromone concen- ditions, update the pheromone of each path according to tration on the path is updated and volatilized according formula (10). ρ is pheromone residue operator and Δτ to the pheromone update and volatilization rules. ij represents the amount of pheromone left by ants on the path Step 5: If all the antecedent ant groups reach the i ⟶ j: destination, continue the planning task of the main ant group; otherwise, turn to Step 4 to continue to find the τ (t + 1) � ρτ (t) + Δτ . (10) ij ij ij way. Among them, Step 6: -e main ant colony carries out the planning task. According to the pheromone concentration left by ⎧ ⎪ ⎪ ε , If the ant passes the path i ⟶ j, the antecedent ant, the transfer probability is calculated ⎨ d ij Δτ � (11) ij according to formula (4). -e path is selected by combining the two target values, and the relevant in- 0, else, formation table and variables are updated after selecting the next node. If the ant reaches the desti- min ⎧ ⎪ d ⎪ j nation, the pheromone concentration on the path is , M ≥ M , j i updated and volatilized according to the pheromone ⎪ d ⎨ ij ε � (12) update and volatilization rules. min Step 7: If all ants complete the planning task, retain the ⎪ i , M < M , j i d global optimal path information, compare the obtained ij paths, and give corresponding rewards and punish- min where d represents the distance between nodes i and j, d ments according to the advantages and disadvantages ij j represents the shortest path distance among all paths con- of the paths. nected to node j, M represents the number of paths Step 8: If all the iteration cycle has been completed at connected to node i, M represents the number of paths this time, the planning result is output and the algo- connected to node j, andM and M do not include path i j rithm ends. Otherwise, turn to Step 3, reset the ant i ⟶ j. Formula (12) updates the pheromone of each path information and continue the iteration. according to different conditions by using the local path information of the area around each path. It can be seen that this algorithm only allows some ants to find relatively short 4. Example Verification and Discussion paths to update pheromones. According to the path length obtained by ants in this cycle, select to increase the amount 4.1. Simulation Environment Setting and Parameter Selection. of information of some better paths and dynamically adjust In this article, MATLAB R2016a simulation software is used the amount of information on each path according to the to simulate the path planning process of the mobile robot on local path information so as to avoid the excessive con- the ground with obstacles. Because Roulette is used in the centration of pheromones. -is algorithm accelerates the simulation process of the ant colony algorithm, the results convergence speed and optimization ability of the algorithm will be different each time. In the simulation, the method of and avoids premature convergence of the algorithm. averaging multiple experiments is adopted. -e simulation 6 Journal of Robotics Table 1: Initialization parameters. Parameter Value ρ 0.2 C 15 σ 1 y 100 l 1 W 80 Q 100 100 1000 90 800 80 600 70 400 60 200 50 0 0 2 4 6 8 10 12 14 β/α Comprehensive index Number of dead ants Figure 5: β/α variation curve. Table 2: Comparison of 30 m × 30 m environmental experiment results. Optimal Number of Number of convergence Algorithm Robot running Algorithm path length (m) path nodes iterations running time (s) time (s) Ant colony algorithm 44.623 21 40 22.368 150.876 Reference [26] 42.569 12 23 20.157 127.148 Reference [28] 42.357 11 20 20.845 125.758 Proposed algorithm 41.248 9 8 17.236 120.347 show that when α is large and β is small, the ant search path environment is Windows 10 64-bit operating system, Intel Core I5-3210m CPU @ 2.50 GHz processor, 8 GB memory. is chaotic, many ants are entering the dead end, and the At present, there is no perfect theoretical method for the number of ants moving towards the target grid is small, so parameter selection of the ant colony algorithm. -e usual the algorithm is easy to fall into local optimization. When method is to take values according to experience and the value of β/α is about 10, the algorithm has a wide search compare them through experiments to obtain better pa- range and obtains better results, as shown in Figure 5. When rameter values. In this article, the parameter selection ex- the value of β/α continues to increase, the convergence speed periment is carried out on a 30m × 30 m map. Because the of the algorithm slows down, and it is easy to fall into the main parameters of the ant colony algorithm are α and β, local optimal situation only under the guidance of local heuristic information. -erefore, take α � 1, β � 10. this article only shows the value selection process of α and β. -e values of other parameters are shown in Table 1 according to experience and experimental simulation 4.2. Comparison of Simulation Results. At 30m × 30 m comparison. Change α and β based on the above values. α reflects the complex environment, the proposed algorithm, ant colony algorithm, the algorithm in literature [26], and the algorithm importance of the inspiration of the previous ant colony to the current ant, and β reflects the importance of the in- in literature [28] are compared and analyzed. Set the grid size to 1 m × 1 m; the average speed of the mobile robot is spiration of the current local environment to the ant. -e values of the two are relative, so they must be combined to 0.5 m/s. Considering safety factors, set the deceleration of the mobile robot to 0.1 m/s when reaching each node. In change. In order to facilitate the experiment, let α � 1, so the value of β/α equals the value of β. -e simulation results addition, the turning time is set to 1 s at each node. -e Comprehensive index of optimal path Number of ants walking into the dead end Journal of Robotics 7 30 70 0 10 20 30 40 50 60 Number of iterations Ant colony algorithm Literature[29] Proposed algorithm Literature[27] Figure 8: Comparison of the number of high-quality solutions of the four algorithms. -rough comparison, it can be seen that the improved 5 1015202530 algorithm in this article still achieves good results in im- Figure 6: Improved algorithm planning path. proving deadlock ants in complex environment and greatly reduces the number of deadlock ants. -is shows the supe- riority of this algorithm, which still has high global perfor- mance and fast convergence in complex environment. Due to the reduction of turning times and driving time, the energy consumption of mobile robot is most likely to be reduced. -e larger the environmental scale is, the more complex the terrain is, and the more obvious the advantages are. 5. Conclusion In order to solve the problems of slow convergence speed and easy to fall into local optimal value in path planning, a robot 40 path planning method based on an improved ant colony 0 10 20 30 40 50 60 70 algorithm is proposed. -e main improvements are as fol- Number of iterations lows: the grid method is used for modeling, and each grid is Ant colony algorithm Literature[29] marked. Let the antecedent ants mark the basic advantage on Proposed algorithm Literature[27] a target value of the path with pheromone concentration so as to guide the subsequent pathfinding operation of the main ant Figure 7: Comparison of convergence curves. group. -e obstacle avoidance factor is added to improve the transition probability, and the amount of information on each path is dynamically adjusted according to the local path experimental data are shown in Table 2. -e basic ant colony information to avoid the excessive concentration of phero- algorithm finds the global optimal value of 44.623 m in the mones. Experiments show that compared with the compar- 40th iteration. In [26], the algorithm converged to 42.569 m ative references, the iteration times of the proposed algorithm in the 23rd iteration, and in [28], the algorithm converged to are reduced by 65.22% and 60.00%, respectively, and the travel 42.357 m in the 20th iteration. -e proposed algorithm time of the mobile robot is reduced by 5.35% and 4.30%, converged in the 8th iteration and found the global optimal respectively, which can effectively improve the work efficiency value of 41.248 m. Compared with [26] and [28], the number of the mobile robot in path planning. of iterations of the algorithm is reduced by 65.22% and In the future research, we will study how to complete 60.00%, respectively, the number of turns is reduced by efficient and high-quality path planning tasks in a dynamic 25.00% and 18.18%, respectively, the path length is reduced environment. Moreover, a neural network can be used to by 3.10% and 2.62%, respectively, and the driving time of dynamically calculate various parameters and weights to mobile robot is reduced by 5.35% and 4.30%, respectively make the planning more intelligent. [29]. Figure 6 shows the path planning diagram of the improved algorithm, Figure 7 shows the comparison of the Data Availability convergence curves of the four algorithms, and Figure 8 shows the comparison of the number of high-quality so- -e data used to support the findings of this study are in- lutions of the three algorithms. cluded within the article. Optimal path length Quantity of high quality solutions 8 Journal of Robotics vehicles,” Defence Science Journal, vol. 69, no. 2, pp. 167–172, Conflicts of Interest [14] L. Wang, C. Luo, M. Li, and J. Kai, “Trajectory planning of an -e authors declare that there are no conflicts of interest autonomous mobile robot by evolving ant colony system,” regarding the publication of this article. International Journal of Robotics and Automation, vol. 32, no. 4, pp. 33–43, 2017. Acknowledgments [15] X.-Y. Zhang, M. Wu, J. Peng, and K.-C. Lin, “Target attraction based ant colony for dynamic path planning of rescue robot,” -is work was supported by the National Natural Science Journal of System Simulation, vol. 9, no. 5, pp. 48–56, 2011. Fund Project (No. 42065004) and the project for improving [16] M. R. Jabbarpour, H. Zarrabi, J. J. Jung, and P. Kim, “A green the basic scientific research ability of young and middle-aged ant-based method for path planning of unmanned ground teachers in Guangxi Colleges and Universities (No. vehicles,” IEEE access, vol. 5, no. 11, pp. 1820–1832, 2017. [17] C. Sahu, D. R. Parhi, and P. B. Kumar, “An approach to 2019KY0868). optimize the path of humanoids using adaptive ant colony optimization,” Journal of Bionics Engineering, vol. 15, no. 4, References pp. 623–635, 2018. [18] M. J. Rostami, A. Zarandi, and S. M. Hoseininasab, “MSDP [1] L. Xie, L. Yan, X. Zhang, and H. Zhang, “A security situation with ACO: a maximal SRLG disjoint routing algorithm based assessment model of information system for smart mobile on ant colony optimization,” Journal of Network and Com- devices,” Wireless Communications and Mobile Computing, puter Applications, vol. 35, no. 1, pp. 394–402, 2012. vol. 2020, Article ID 8886516, 11 pages, 2020. [19] X. Jiang, Z. Lin, T. He, X. Ma, S. Ma, and S. Li, “Optimal path [2] H. Choset, “Coverage for robotics–a survey of recent results,” finding with beetle antennae search algorithm by using ant Annals of Mathematics and Artificial Intelligence, vol. 31, no. 1, colony optimization initialization and different searching pp. 113–126, 2001. strategies,” IEEE Access, vol. 8, no. 12, pp. 15459–15471, 2020. [3] S. Aggarwal and N. Kumar, “Path planning techniques for [20] C. C. Yuan, Y. Wei, J. Shen et al., “Research on path planning unmanned aerial vehicles: a review, solutions, and chal- based on new fusion algorithm for autonomous vehicle,” lenges,” Computer Communications, vol. 149, no. 5, International Journal of Advanced Robotic Systems, vol. 17, pp. 270–299, 2020. no. 3, pp. 172–181, 2020. [4] H. Jahanshahi, M. Jafarzadeh, N. Naeimeh, V.-T. Pham, [21] J. Liu, J. Yang, H. Liu, and X. Tian, “An improved ant colony V. H. Van, and Q. N. Xuan, “Robot motion planning in an algorithm for robot path planning,” Soft Computing, vol. 21, unknown environment with danger space,” Electronics, vol. 8, no. 19, pp. 5829–5839, 2017. no. 2, pp. 201–212, 2019. [22] M. R. Zeng, L. Xi, and A. M. Xiao, “-e free step length ant [5] B. Sahu, P. K. Das, M. R. Kabat, and R. Kumar, “Multi-robot colony algorithm in mobile robot path planning,” Advanced cooperation and performance analysis with particle swarm Robotics, vol. 30, no. 23, pp. 1509–1514, 2016. optimization variants,” Multimedia Tools and Applications, [23] J. Lee, “Heterogeneous-ants-based path planner for global vol. 5, no. 9, pp. 1–24, 2021. path planning of mobile robot applications,” International [6] R. Liu and X. Zhang, “A review of methodologies for natural- Journal of Control, Automation and Systems, vol. 15, no. 4, language-facilitated human–robot cooperation,” Interna- pp. 1754–1769, 2017. tional Journal of Advanced Robotic Systems, vol. 16, no. 3, [24] L. Wang, C. Luo, M. Li, and J. Cai, “Trajectory planning of an pp. 172–179, 2019. autonomous mobile robot by evolving ant colony system,” [7] G. S. Chirikjian, “Design and analysis of some non- International Journal of Robotics and Automation, vol. 32, anthropomorphic, biologically inspired robots: an overview,” no. 4, pp. 1500–1515, 2017. Journal of Robotic Systems, vol. 18, no. 12, pp. 701–713, 2001. [25] W. Deng, R. Chen, B. He, Y. Liu, L. Yin, and J. Guo, “A novel [8] B. C. Mohan and R. Baskaran, “A survey: ant colony opti- two-stage hybrid swarm intelligence optimization algorithm mization based recent research and implementation on sev- and application,” Soft Computing, vol. 16, no. 10, pp. 1707– eral engineering domain,” Expert Systems with Applications, 1722, 2012. vol. 39, no. 4, pp. 4618–4627, 2012. [26] H. Fa-Mei, X. Yi-na, W. Xu-ren, X. Meng-bo, and X. Zi-han, [9] B. K. Patle, A. Pandey, D. R. K. Parhi, J. Anne, and “An improved ant colony algorithm for solving time-de- B. L. Ganesh, “A review: on path planning strategies for pendent road network path planning problem,” in Proceedings navigation of mobile robot,” Defence Technology, vol. 15, no. 4, of the 2019 6th International Conference on Information pp. 582–606, 2019. Science and Control Engineering (ICISCE), pp. 126–130, IEEE, [10] B. Velusamy and S. C. Pushpan, “A review on swarm intel- Shanghai, China, December 2019. ligence based routing approaches,” International Journal of [27] L. Wang, J. Kan, J. Guo, and C. Wang, “3D path planning for Engineering and Technology, vol. 9, no. 3, pp. 182–195, 2019. the ground robot with improved ant colony optimization,” [11] Z. Masoumi, J. Van Genderen, and A. Sadeghi Niaraki, “An Sensors, vol. 19, no. 4, pp. 815–824, 2019. improved ant colony optimization-based algorithm for user- [28] X. Dai, S. Long, Z. Zhang, and D. Gong, “Mobile robot path centric multi-objective path planning for ubiquitous environ- planning based on ant colony algorithm with A heuristic ments,” Geocarto International, vol. 36, no. 2, pp. 137–154, 2021. method,” Frontiers in Neurorobotics, vol. 13, no. 5, pp. 15–26, [12] V. Sangeetha, R. Krishankumar, K. S. Ravichandran, and S. Kar, “Energy-efficient green ant colony optimization for [29] A. Majumder, “Contrast enhancement of multi-displays using path planning in dynamic 3D environments,” Soft Computing, human contrast sensitivity,” in Proceedings of the IEEE vol. 25, no. 6, pp. 4749–4769, 2021. Computer Society Conference on Computer Vision and Pattern [13] V. Sangeetha, K. S. Ravichandran, S. Shekhar, and Recognition (CVPR’05), pp. 377–382, IEEE, Piscataway, NJ, M. T. Anand, “An intelligent gain-based ant colony opti- USA, July 2005. misation method for path planning of unmanned ground

Journal

Journal of Robotics – Hindawi Publishing Corporation

Published: Apr 4, 2022

There are no references for this article.