Improved Ant Colony Path Planning Algorithm Based on Bidirectional Search

doi:10.3778/j.issn.1002-8331.2106-0061

Abstract

Abstract:

An improved ant colony path planning algorithm based on bidirectional search is designed to solve the problem that mobile robots in complex map environment are time-consuming to move and easy to fall into local optimum. The map is preprocessed based on the K-means algorithm to quantify the degree of local complexity of the map, and the local environmental information is fused into the state transition probability function to make the robot choose the region with low complexity first, reduce path inflection points. Then, the bidirectional search rules are set and the heuristic function is improved to improve the local direction search accuracy and global search efficiency. In order to solve the problem that ants in ant colony algorithm encounter U obstacle and fall into deadlock, the deadlock judgment coefficient is proposed to increase the number of effective ants and further improve the performance of the algorithm. The simulation results show that the algorithm designed in this paper is more efficient than the traditional ant colony algorithm in the path search of mobile robot in complex map environment.

Key words: mobile robot, path planning, K-means clustering algorithm, bidirectional search strategy, ant colony algorithm

摘要：

针对移动机器人在复杂地图环境中移动耗时长、易陷入局部最优等问题，设计了一种基于双向搜索的改进蚁群路径规划算法。基于K-means算法对地图预处理，量化地图的局部复杂度程度，并将局部环境信息融合到状态转移概率函数，使机器人优先选择在复杂程度小的区域进行寻优，减少路径拐点。设定双向搜索规则，改进启发函数，提高算法的局部方向搜索精度和全局搜索效率。针对蚁群算法中蚂蚁遇到U障碍物陷入死锁的问题，提出死锁判断系数，增加了有效蚂蚁的数量，进一步提高了算法性能。仿真结果表明所设计的算法在复杂地图环境中相较于传统蚁群算法移动机器人的路径搜索效率更高。

关键词: 移动机器人, 路径规划, K-means聚类算法, 双向搜索策略, 蚁群算法

ZHANG Ziran, HUANG Weihua, CHEN Yang, ZHANG Zheng, LI Ziyuan. Improved Ant Colony Path Planning Algorithm Based on Bidirectional Search[J]. Computer Engineering and Applications, 2021, 57(21): 270-277.

张子然，黄卫华，陈阳，章政，李梓远. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.

References

[1] 马向华，张谦.改进蚁群算法在机器人路径规划上的研究[J].计算机工程与应用，2021，57（5）：210-215.
MA X H，ZHANG Q.Research on improved ant colony algorithm in robots path planning[J].Computer Engineering and Applications，2021，57（5）：210-215.
[2] 黄书召，田军委，乔路，等.基于改进遗传算法的无人机路径规划[J].计算机应用，2021，41（2）：390-397.
HUANG S Z，TIAN J W，QIAO L，et al.Unmanned aerial vehicle path planning based on improved genetic algorithm[J].Journal of Computer Applications，2021，41（2）：390-397.
[3] 付兴武，胡洋.基于改进粒子群算法的三维路径规划[J].电光与控制，2021，28（3）：86-89.
FU X W，HU Y.Three-dimensional path planning based on improved PSO algorithm[J].Electronics Optics & Control，2021，28（3）：86-89.
[4] 刘宁宁，王宏伟.基于改进灰狼优化算法的移动机器人路径规划[J].电测与仪表，2020，57（1）：76-83.
LIU N N，WANG H W.Path planning of mobile robot based on improved grey wolf optimization algorithm[J].Electrical Measurement & Instrumentation，2020，57（1）：76-83.
[5] 胡春阳，姜平，周根荣.改进蚁群算法在AGV路径规划中的应用[J].计算机工程与应用，2020，56（8）：270-278.
HU C Y，JIANG P，ZHOU G R.Application of improved ant colony optimization in AGV path planning[J].Computer Engineering and Applications，2020，56（8）：270-278.
[6] 刘新宇，谭力铭，杨春曦，等.未知环境下的蚁群-聚类自适应动态路径规划[J].计算机科学与探索，2019，13（5）：846-857.
LIU X Y，TAN L M，YANG C X，et al.Whole unsupervised domain adaptation using sparse representation of parameter dictionary[J].Journal of Frontiers of Computer Science and Technology，2019，13（5）：846-857.
[7] 马小铭，靳伍银.基于改进蚁群算法的多目标路径规划研究[J].计算技术与自动化，2020，39（4）：100-105.
MA X M，JIN W Y.Multi-objective path planning based on improved ant colony algorithm[J].Computing Technology and Automation，2020，39（4）：100-105.
[8] 杜磊，史健芳.改进蚁群算法用于移动机器人路径规划时的研究[J].太原理工大学学报，2019，50（4）：523-528.
DU L，SHI J F.Research on improved ant colony algorithm in mobile robot path planning[J].Journal of Taiyuan University of Technology，2019，50（4）：523-528.
[9] 高民东，张雅妮，朱凌云.应用于机器人路径规划的双向时效A*算法[J].计算机应用研究，2019，36（3）：792-795.
GAO M D，ZHANG Y N，ZHU L Y.Bidirectional time-efficient A* algorithm for robot path planning[J].Application Research of Computers，2019，36（3）：792-795.
[10] 马小陆，梅宏.双向跳点搜索算法的移动机器人全局路径规划研究[J].机械科学与技术，2020，39（10）：1624-1631.
MA X L，MEI H.Research on bidirectional jump point search algorithm of global path planning for mobile robots[J].Mechanical Science and Technology for Aerospace Engineering，2020，39（10）：1624-1631.
[11] 赵迪，于丽平，胡梦雅，等.月面探测器路径规划优化算法研究[J].机械科学与技术，2021，40（3）：364-370.
ZHAO D，YU L P，HU M Y，et al.Research on lunar surface path planning optimization algorithm of lunar probes[J].Mechanical Science and Technology for Aerospace Engineering，2021，40（3）：364-370.
[12] 张晓莉，杨亚新，谢永成.改进的蚁群算法在机器人路径规划上的应用[J].计算机工程与应用，2020，56（2）：29-34.
ZHANG X L，YANG Y X，XIE Y C.Application of improved ant colony algorithm in robot path planning[J].Computer Engineering and Applications，2020，56（2）：29-34.
[13] DUCHON F，BABINEC A，KMAN M，et al.Path planning with modified a star algorithm for a mobile robot[J].Precedia Engineering，2014，96：59-69．
[14] LUO Y Z，DING W R，ZHANG B C，et al.Optimization of bits allocation and path planning with trajectory constraint in UAV-enabled mobile edge computing system[J].Chinese Journal of Aeronautics，2020，33（10）：2716-2727.
[15] SUN P，SHAN R.Predictive control with velocity observer for cushion robot based on pso for path planning[J].Journal of Systems Science & Complexity，2020，33（4）：988-1011.
[16] 郭永坤，章新友，刘莉萍，等.优化初始聚类中心的K-means聚类算法[J].计算机工程与应用，2020，56（15）：172-178.
GUO Y K，ZHANG X Y，LIU L P，et al.K-means clustering algorithm of optimizing initial clustering center[J].Computer Engineering and Applications，2020，56（15）：172-178.