基于改进蚁群与动态窗口法的AGV动态路径规划

doi:10.3778/j.issn.1002-8331.2108-0501

摘要/Abstract

摘要： 针对全局静态路径规划算法无法有效躲避动态障碍物、局部动态路径规划算法缺少全局环境信息指导规划路径质量差或无法成功到达目标点等问题，提出了一种结合改进蚁群算法和动态窗口法的全局动态路径规划算法，实现在动态环境中的全局最优路径实时规划。对传统蚁群算法提出了初始信息素不均匀、双向分布、引入放大系数[A]增大相邻栅格启发信息差异、选择最优路径时考虑转弯次数的影响等改进策略；改进动态窗口法的距离评价子函数和初始航向角；提取改进蚁群算法规划的全局最优路径的转折点作为子目标点来引导动态窗口法沿着全局最优路径方向进行实时动态路径规划。经过不同环境下的仿真实验结果表明，提出的全局动态路径规划算法可以通过实时动态路径规划实现有效躲避动态障碍物的同时规划全局最优路径。

关键词: 改进蚁群算法, 动态窗口法, 全局动态路径规划

Abstract: Given the defects that the global static path planning algorithm cannot effectively avoid dynamic obstacles, and the local dynamic path planning algorithm lacks the guidance of global environmental information that the planning path quality is poor or cannot successfully reach the target point. A global dynamic path planning algorithm combining an improved ant colony algorithm and a dynamic window approach is proposed in this paper to realize the globally optimal path real-time planning in the dynamic environment. For the traditional ant colony algorithm, the improved strategies such as uneven and bidirectional distribution of the initial pheromone, increasing the difference of heuristic information between adjacent grids by introducing the increasing coefficient [A,] and considering the influence of turning times when selecting the optimal path are proposed. The distance evaluation sub-function and initial heading angle of the dynamic window approach are improved. The turning point of the globally optimal path planned by the improved ant colony algorithm is extracted as the sub-target point to guide the dynamic window method to carry out real-time dynamic path planning along the direction of the globally optimal path. Simulation experiments in different environments show that the global dynamic path planning algorithm proposed in this paper can effectively plan the globally optimal path while avoiding dynamic obstacles through real-time dynamic path planning.

Key words: improved ant colony algorithm, dynamic window approach, global dynamic path planning

杨周, 刘海滨. 基于改进蚁群与动态窗口法的AGV动态路径规划[J]. 计算机工程与应用, 2022, 58(6): 287-295.

YANG Zhou, LIU Haibin. AGV Dynamic Path Planning Based on Improved Ant Colony Algorithm and Dynamic Window Approach[J]. Computer Engineering and Applications, 2022, 58(6): 287-295.

参考文献

[1] 胡春阳，姜平，周根荣.改进蚁群算法在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.
[2] YU L，WEI Z，HUI W，et al.Path planning for mobile robot based on fast convergence ant colony algorithm[C]//2017 IEEE International Conference on Mechatronics and Automation（ICMA），2017.
[3] LUO M，HOU X，YANG J.Surface optimal path planning using an extended Dijkstra algorithm[J].IEEE Access，2020，8：147827-147838.
[4] XIONG X，MIN H，YU Y，et al.Application improvement of A* algorithm in intelligent vehicle trajectory planning[J].Mathematical Biosciences and Engineering，2020，18（1）：1-21.
[5] 张松灿，普杰信，司彦娜，等.蚁群算法在移动机器人路径规划中的应用综述[J].计算机工程与应用，2020，56（8）：10-19.
ZHANG S C，PU J X，SI Y N，et al.Survey on application of ant colony algorithm in path planning of mobile robot[J].Computer Engineering and Applications，2020，56（8）：10-19.
[6] 陈娇，徐菱，陈佳，等.改进A*和动态窗口法的移动机器人路径规划[J].计算机集成制造系统：1-17[2021-08-17].http：//kns.cnki.net/kcms/detail/11.5946.tp.20201026.1053.026.html.
CHEN J，XU L，CHEN J，et al.Path planning based on improved A* and dynamic window approach for mobile robot[J].Computer Integrated Manufacturing Systems：1-17[2021-08-17].http：//kns.cnki.net/kcms/detail/11.5946.tp.
20201026.1053.026.html.
[7] 武曲，张义，郭坤，等.结合LSTM的强化学习动态环境路径规划算法[J].小型微型计算机系统，2021，42（2）：334-339.
WU Q，ZHANG Y，GUO K，et al.LSTM combined with reinforcement learning dynamic environment path planning algorithm[J].Journal of Chinese Computer Systems，2021，42（2）：334-339.
[8] 葛志远，肖本贤.使用改进蚁群算法的AGV路径规划研究[J].机械设计与制造，2020，352（6）：241-244.
GE Z Y，XIAO B X.Research on path planning for AGV based on improved ant colony algorithm[J].Machinery Design ＆ Manufacture，2020，352（6）：241-244.
[9] 王晓燕，杨乐，张宇，等.基于改进势场蚁群算法的机器人路径规划[J].控制与决策，2018，33（10）：50-56.
WANG X Y，YANG L，ZHANG Y，et al.Robot path planning based on improved ant colony algorithm with potential field heuristic[J].Control and Decision，2018，33（10）：50-56.
[10] 殷绍伟，彭力，戴菲菲.融合改进A*蚁群和滚动窗口法的平滑路径规划[J].计算机科学与探索，2021，15（10）：1969-1979.
YIN S W，PENG L，DAI F F.Smooth path planning based on improved A* ant colony and rolling window method[J].Journal of Frontiers of Computer Science and Technology，2021，15（10）：1969-1979.
[11] 槐创锋，郭龙，贾雪艳，等.改进A*算法与动态窗口法的机器人动态路径规划[J].计算机工程与应用，2021，57（8）：244-248.
HUAI C F，GUO L，JIA X Y，et al.Improved A* algorithm and dynamic window method for robot dynamic path planning[J].Computer Engineering and Applications，2021，57（8）：244-248.
[12] 王群笑.基于改进蚁群算法的路径寻优研究[D].杭州：杭州电子科技大学，2019.
WANG Q X.Path optimization research based on improved ant colony algorithm[D].Hangzhou：Hangzhou University of Electronic Science and Technology，2019.
[13] 胡立华，马瑞，张名师，等.基于改进蚁群算法的智能小车路径规划方法[J].太原科技大学学报，2020，41（6）：463-469.
HU L H，MA R，ZHANG M S，et al.Intelligent trolley path planning method based on improved ant colony algorithm[J].Journal of Taiyuan University of Science and Technology，2020，41（6）：463-469.
[14] 马向华，张谦.改进蚁群算法在机器人路径规划上的研究[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.
[15] 张晓熠.融合动态窗口法与A*算法的港口AGV路径规划方法研究[D].北京：北京交通大学，2019.
ZHANG X Y.Research on port AGV path planning method based on dynamic window approach integrated with A* algorithm[D].Beijing：Beijing Jiaotong University，2019.