基于栅格图特征点提取下的蚁群算法路径规划

doi:10.1007/s12204-023-2572-4

摘要/Abstract

摘要： 针对传统蚁群算法路径搜索方向和视野范围、无法找到最短路径、容易发生死锁和路径不平滑等问题，提出一种新环境下的蚁群算法。首先，提取障碍物特征点对栅格地图环境进行预处理，能够避免进入陷阱，从而解决死锁问题；其次，以这些特征点为寻路访问节点，减少节点的访问，待选移动的方向更多，待选特征点的位置决定寻路视野范围；然后，以特征点为基础，采用信息素不平等分布和双向并行路径搜索，提高解的构造效率，采用改进启发函数，增强路径搜索的引导作用，动态调整信息素挥发系数避免算法陷入早熟；接着，采用贝塞尔曲线平滑路径，得到的路径平滑且最短；最后，在不同复杂程度和不同尺度的栅格地图中，与传统蚁群算法和其他改进蚁群算法进行仿真对比，验证了本文算法的可行性和优越性。

关键词: 蚁群算法，移动机器人，路径规划，特征点，贝塞尔曲线，栅格地图

Abstract: 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.

Key words: ant colony algorithm, mobile robot, path planning, feature points, Bezier curve, grid map

中图分类号:

TP242

. 基于栅格图特征点提取下的蚁群算法路径规划[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 86-99.

LI Erchao∗ (李二超), QI Kuankuan (齐款款). Ant Colony Algorithm Path Planning Based on Grid Feature Point Extraction[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 86-99.

参考文献

[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).