Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (21): 270-277.DOI: 10.3778/j.issn.1002-8331.2106-0061

Previous Articles     Next Articles

Improved Ant Colony Path Planning Algorithm Based on Bidirectional Search

ZHANG Ziran, HUANG Weihua, CHEN Yang, ZHANG Zheng, LI Ziyuan   

  1. 1.Institute of Robotics and Intelligent Systems, Wuhan University of Science and Technology, Wuhan 430081, China
    2.Engineering Research Center for Metallurgical Automation and Measurement Technology of Ministry of Education, Wuhan University of Science and Technology, Wuhan 430081, China
    3.School of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan 430081, China
  • Online:2021-11-01 Published:2021-11-04



  1. 1.武汉科技大学 机器人与智能系统研究院,武汉 430081
    2.武汉科技大学 冶金自动化与检测技术教育部工程研究中心,武汉 430081
    3.武汉科技大学 信息科学与工程学院,武汉 430081


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聚类算法, 双向搜索策略, 蚁群算法