计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (21): 270-277.DOI: 10.3778/j.issn.1002-8331.2106-0061

• 工程与应用 • 上一篇    下一篇

基于双向搜索的改进蚁群路径规划算法

张子然,黄卫华,陈阳,章政,李梓远   

  1. 1.武汉科技大学 机器人与智能系统研究院,武汉 430081
    2.武汉科技大学 冶金自动化与检测技术教育部工程研究中心,武汉 430081
    3.武汉科技大学 信息科学与工程学院,武汉 430081
  • 出版日期:2021-11-01 发布日期:2021-11-04

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

摘要:

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

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

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