Aimed at the problems of a traditional ant colony algorithm, such as the path search direction and
field of view, an inability to find the shortest path, a propensity toward deadlock and an unsmooth path, an ant
colony algorithm for use in a new environment is proposed. First, the feature points of an obstacle are extracted
to preprocess the grid map environment, which can avoid entering a trap and solve the deadlock problem. Second,
these feature points are used as pathfinding access nodes to reduce the node access, with more moving directions
to be selected, and the locations of the feature points to be selected determine the range of the pathfinding field
of view. Then, based on the feature points, an unequal distribution of pheromones and a two-way parallel path
search are used to improve the construction efficiency of the solution, an improved heuristic function is used to
enhance the guiding role of the path search, and the pheromone volatilization coefficient is dynamically adjusted
to avoid a premature convergence of the algorithm. Third, a Bezier curve is used to smooth the shortest path
obtained. Finally, using grid maps with a different complexity and different scales, a simulation comparing the
results of the proposed algorithm with those of traditional and other improved ant colony algorithms verifies its
feasibility and superiority.
LI Erchao∗ (李二超), QI Kuankuan (齐款款)
. Ant Colony Algorithm Path Planning Based on Grid Feature Point Extraction[J]. Journal of Shanghai Jiaotong University(Science), 2023
, 28(1)
: 86
-99
.
DOI: 10.1007/s12204-023-2572-4
[1] CHEN W W, YAN G Z, WANG Z W, et al. Intestinal biopsy endoscopic robot system [J]. Journal of Shanghai Jiao Tong University, 2014, 48(5): 674-678 (in Chinese).
[2] GARDU?O-APARICIO M, RODRíGUEZRESéNDIZ J, MACIAS-BOBADILLA G, et al. A multidisciplinary industrial robot approach forteaching mechatronics-related courses [J]. IEEE Transactions on Education, 2018, 61(1): 55-62.
[3] PALACIN J, SALSE J A, VALGANON I, et al. Building a mobile robot for a floor-cleaning operation in domestic environments [J]. IEEE Transactions on Instrumentation and Measurement, 2004, 53(5): 1418-1424.
[4] WANG B Y, LIU Z, LI Q B, et al. Mobile robot path planning in dynamic environments through globally guided reinforcement learning [J]. IEEE Robotics and Automation Letters, 2020, 5(4): 6932-6939.
[5] LI S F, CHENG C Y. Particle swarm optimization with fitness adjustment parameters [J]. Computers & Industrial Engineering, 2017, 113: 831-841.
[6] SONG B Y, WANG Z D, SHENG L. A new genetic algorithm approach to smooth path planning for mobile robots [J]. Assembly Automation, 2016, 36(2): 138-145.
[7] ZHANG A, LI C, BI W H. Rectangle expansion A? pathfinding for grid maps [J]. Chinese Journal of Aeronautics, 2016, 29(5): 1385-1396.
[8] ZHANG Y X, WANG Y Q, LI S, et al. Global path planning for AUV based on charts and the improved particle swarm optimization algorithm [J]. Robot, 2020, 42(1): 120-128 (in Chinese).
[9] BAO H, ZHU H T, LIU D. Path planning of mobile robot based on ±3σ normal probability interval population division using genetic ant-colony algorithm [J]. Control and Decision, 2021, 36(12): 2861-2870 (in Chinese).
[10] DUCHO F, BABINEC A, KAJAN M, et al. Path planning with modified a star algorithm for a mobile robot [J]. Procedia Engineering, 2014, 96: 59-69.
[11] SUN L. A real-time collision-free path planning of a rust removal robot using an improved neural network [J]. Journal of Shanghai Jiao Tong University (Science), 2017, 22(5): 633-640.
[12] ZHANG Y, QUAN H, WEN J F. Mobile robot path planning based on the wolf ant colony hybrid algorithm [J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2020, 48(1): 127-132 (in Chinese).
[13] ZHANG Q, CHEN B K, LIU X Y, et al. Ant colony optimization with improved potential field heuristic for robot path planning [J]. Transactions of the Chinese Society for Agricultural Machinery, 2019, 50(5): 23-32 (in Chinese).
[14] XU L, FU W H, JIANG W H, et al. Mobile robots path planning based on 16-directions 24-neighborhoods improved ant colony algorithm [J]. Control and Decision, 2021, 36(5): 1137-1146 (in Chinese).
[15] ZHAO J P, GAO X W, LIU J G, et al. Parameters self-adaptive fuzzy ant colony optimization algorithm with searching window for path planning of mobile robot [J]. Control and Decision, 2011, 26(7): 1096-1100 (in Chinese).
[16] WU X X, WEI G L, SONG Y, et al. Improved ACO based path planning with rollback and death strategies [J]. Systems Science & Control Engineering, 2018, 6(1): 102-107.
[17] KANG B, WANG X H, LIU F. Path planning of searching robot based on improved ant colony algorithm [J]. Journal of Jilin University (Engineering and Technology Edition), 2014, 44(4): 1062-1068 (in Chinese).
[18] AO B Q, YANG S, YE Z H. Improved ant colony algorithm for unmanned surface vehicle smooth path planning [J]. Control Theory & Applications, 2021(7): 1006-1014 (in Chinese).
[19] PAN J, WANG X S, CHENG Y H. Improved ant colony algorithm for mobile robot path planning [J]. Journal of China University of Mining & Technology, 2012, 41(1): 108-113 (in Chinese).
[20] ZHANG S Y, GUO B L, CHEN L Z, et al. Path planning of intelligent fire evacuation map based on bidirectional ant colony algorithm [J]. Computer Engineering and Applications, 2021(14): 259-266 (in Chinese).
[21] HU H M, YU X C. Improved ant colony path planning algorithm based on bidirectional search strategy [J]. Agricultural Equipment & Vehicle Engineering, 2019, 57(7): 9-12 (in Chinese).
[22] ZHAO J, TANG Y F, JIANG G P, et al. Mobile robot path planning based on improved ant colony algorithm [J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2019, 39(6): 73-78 (in Chinese).
[23] YOU H L, LU Z Q. A fast ant colony algorithm for α, β and ρ adaptive adjustment [J]. Manufacturing Automation, 2018, 40(6): 99-102 (in Chinese).
