Journal of Frontiers of Computer Science and Technology ›› 2019, Vol. 13 ›› Issue (5): 846-857.DOI: 10.3778/j.issn.1673-9418.1811015

Previous Articles     Next Articles

Self-Adjustable Dynamic Path Planning of Unknown Environment Based on Ant Colony-Clustering Algorithm

LIU Xinyu, TAN Liming, YANG Chunxi+, ZHAI Chi   

  1. Faculty of Chemical Engineering, Kunming University of Science and Technology, Kunming 650500, China
  • Online:2019-05-01 Published:2019-05-08

未知环境下的蚁群-聚类自适应动态路径规划

刘新宇谭力铭杨春曦+,翟  持   

  1. 昆明理工大学 化学工程学院,昆明 650500

Abstract: When the traditional ant colony algorithm is applied to the path planning of robot in the time-varying environments, there are several problems such as slower convergence speed, lager path integral turning angle and poor self-adaptive ability. So, a self-adjustable dynamic path plan algorithm is presented based on both the ant colony and the clustering algorithm in this paper. In the new ant colony-clustering algorithm proposed here, a suitable searching radius is chosen automatically by using the clustering algorithm for different environmental complexities, which can make full use of the limited computing resources of the robot and improve the convergence speed. By identifying the diagonal obstacles with the proposed virtual obstacle generation method, virtual obstacles are used to guarantee that the problem of planning path crossing diagonal obstacles is nonexistent. The dynamic searching path is smoothed and optimized by the smoothing mechanism, which can effectively reduce the path length and the cumulative turning angle. Simulation examples are provided to show that the algorithm can find suitable searching radius according to different obstacle distributions, complete the dynamic path planning, show good environmental self-adaptability and better total path optimization performances.

Key words: ant colony-clustering algorithm, dynamic path planning, self-adjusting radius, diagonal obstacle, smoothing mechanism

摘要: 针对用于动态环境中的机器人路径规划的蚁群算法存在收敛速度慢,路径累计转折角大,对环境变化适应性低等问题,提出了一种未知环境下的蚁群-聚类自适应动态路径规划方法。依据聚类算法对环境复杂程度的准确判别自动改变寻优半径,达到充分利用机器人有限的计算能力,提高收敛速度的目的;通过识别对角障碍,生成虚拟障碍,确保规划的路径不穿过对角障碍;通过平滑机制对搜索的动态路径做平滑优化处理,有效降低了路径长度,减少了累计转折角。仿真结果表明,提出的算法能够根据障碍的复杂程度自动选择合适的搜索半径,完成路径的动态规划,体现出良好的环境适应能力和较好的综合路径优化性能。

关键词: 蚁群-聚类算法, 动态路径规划, 自适应半径, 对角障碍, 平滑机制