计算机应用 ›› 2021, Vol. 41 ›› Issue (9): 2560-2568.DOI: 10.11772/j.issn.1001-9081.2020111713

所属专题: 人工智能

• 人工智能 • 上一篇    下一篇

基于转角约束的改进蚁群优化算法路径规划

李开荣, 刘爽, 胡倩倩, 唐亦媛   

  1. 扬州大学 信息工程学院, 江苏 扬州 225127
  • 收稿日期:2020-11-04 修回日期:2021-01-24 出版日期:2021-09-10 发布日期:2021-05-08
  • 通讯作者: 刘爽
  • 作者简介:李开荣(1963-),男,江苏兴化人,教授,硕士,主要研究方向:人工智能、知识工程;刘爽(1997-),女,安徽合肥人,硕士研究生,主要研究方向:路径规划、智能优化算法;胡倩倩(1996-),女,江苏南京人,硕士研究生,主要研究方向:路径规划、智能优化算法;唐亦媛(1998-),女,广西桂林人,硕士研究生,主要研究方向:人工智能、知识管理。
  • 基金资助:
    国家自然科学基金资助项目(61872313);江苏省应急管理科技项目(YJGL-YF-2020-17)。

Improved ant colony optimization algorithm for path planning based on turning angle constraint

LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan   

  1. College of Information Engineering, Yangzhou University, Yangzhou Jiangsu 225127, China
  • Received:2020-11-04 Revised:2021-01-24 Online:2021-09-10 Published:2021-05-08
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61872313), the Jiangsu Provincial Emergency Management Science and Technology Project (YJGL-YF-2020-17).

摘要: 针对传统蚁群优化(ACO)算法搜索路径时易陷入局部最优、路径过长、转弯角度过大等问题,提出一种基于转弯角度约束的改进ACO算法。首先,增加起始点与目标点之间区域的初始信息素浓度,以避免初期盲目搜索;然后,在启发函数中加入A*算法的估价函数和转弯角度因子,以便在下一步选择路径长度和转角次数综合最优的节点;最后,在信息素更新部分引入狼群算法的分配原则,来加强优质种群的影响力,同时借鉴最大最小蚁群(MMAS)算法进行信息素浓度的限制,从而避免算法陷入局部最优。Matlab仿真结果表明,改进算法与传统ACO算法相比,规划出的路径长度缩短了13.7%,转弯次数减小了64.3%,累计转弯角度减少了76.7%。实验结果表明,所提改进算法能有效解决全局路径规划问题,避免了移动机器人过多的能耗损失。

关键词: 移动机器人, 路径规划, 蚁群优化算法, 转角约束, 狼群分配原则

Abstract: Concerning the problems that basic Ant Colony Optimization (ACO) is easy to fall into the local optimum, and has too long path and excessive turning angles during path search, an improved ACO algorithm based on turning angle constraint was proposed. Firstly, the initial pheromone concentration of the area between the starting point and the target point was enhanced to avoid the initial blind search. Then, the A* algorithm's evaluation function and the turning angle constraint factor were added to the heuristic function. In this way, the node with the shortest path length and least number of turns was able to be selected at the next step. Finally, the distribution principle of wolf pack algorithm was introduced in the pheromone updating part to enhance the influence of high-quality population. At the same time, the Max and Min Ant System (MMAS) algorithm was used to limit the pheromone concentration to avoid the algorithm being trapped into the local optimum. Matlab simulation showed that compared with the traditional ACO, the improved algorithm was able to shorten the planned path length by 13.7%, reduce the number of turns by 64.3% and decrease the accumulated turning angle by 76.7%. Experimental results show that the improved ACO algorithm can effectively solve the global path planning problem and avoid the excessive energy loss of mobile robots.

Key words: mobile robot, path planning, Ant Colony Optimization (ACO) algorithm, turning angle constraint, distribution principle of wolf pack algorithm

中图分类号: