Smooth Path Planning Based on Improved A* Ant Colony and Rolling Window Method

doi:10.3778/j.issn.1673-9418.2011061

Abstract

Abstract:

In order to solve the problems of deadlock, slow convergence, easy to get into local optimum and uneven path when ant colony algorithm is applied to the path planning of mobile robots, a smooth path planning method combining improved A* ant colony algorithm and the rolling window method is proposed. Firstly, the improved A* algorithm is used to initialize the ant colony pheromone to solve the problem of low ant colony efficiency. Then, the state transition probability function is improved to consider the feasible path “activity” and the end position in the function to avoid deadlock phenomenon. At the same time, based on the mechanism of inequality principle, the pheromone of ant colony is updated to avoid falling into the local optimal path and accelerate the convergence speed of the algorithm. Secondly, based on the global path planning, local real-time path planning is carried out by integ-rating the rolling window method and the dynamic obstacle avoidance strategy. Finally, Bessel curve is used to process the smoothness of the planned path, so that the smoothed path is closer to the actual motion path. In order to ensure the best performance of the algorithm, genetic algorithm with elite strategy is used to optimize the parameters of the algorithm. Three sets of experimental results show that the proposed algorithm is effective in the presence of simple or complex, static or dynamic obstacles.

Key words: path planning, ant colony optimization (ACO), A* algorithm, rolling window method, genetic algorithm (GA), Bessel curve, dynamic obstacle avoidance

摘要：

针对蚁群算法应用于移动机器人路径规划时，出现的死锁、收敛慢、易陷入局部最优以及路径不平滑的问题，提出了一种融合改进A*蚁群算法与滚动窗口法的平滑路径规划方法。首先，用改进的A*算法初始化蚁群信息素，解决前期蚁群效率低的问题。然后，改进状态转移概率函数，在函数中考虑可行路径“活跃度”以及终点位置，避免死锁现象。同时，基于不平等原则机制更新蚁群的信息素，避免陷入局部最优路径，加快算法的收敛速度。其次，融合滚动窗口法，在全局路径规划的基础上，结合动态避障策略进行局部实时路径规划。最后，使用贝塞尔曲线对所规划出的路径进行平滑度处理，使平滑后的路径更加接近实际运动路径。为确保算法表现出最好的性能，利用带精英策略的遗传算法对该算法中的参数进行自主优化选择。三组实验结果表明，无论是简单还是复杂的静态或动态障碍物存在的环境中，该算法均有不错的效果。

关键词: 路径规划, 蚁群算法（ACO）, A*算法, 滚动窗口法, 遗传算法（GA）, 贝塞尔曲线, 动态避障

YIN Shaowei, PENG Li, DAI Feifei. 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.

殷绍伟, 彭力, 戴菲菲. 融合改进A*蚁群和滚动窗口法的平滑路径规划[J]. 计算机科学与探索, 2021, 15(10): 1969-1979.

References

[1] WU Z P, TANG N, CHEN Y L, et al. AUV path planning based on improved artificial potential field method[J]. Control and Instruments in Chemical Industry, 2014, 41(2): 1421-1423.
[2] DAVOODI M, PANAHI M, MOHADES A, et al. Multi-objective path planning in discrete space[J]. Applied Soft Computing Journal, 2013, 13(1): 709-720.
[3] HUANG J, CHEN H W, UNIVERSITY S T. Research on global path planning algorithm of mobile robot[J]. Instrument Technique & Sensor, 2014(12): 80-83.
[4] ZHANG Y, LI S, GUO H. A type of biased consensus-based distributed neural network for path planning[J]. Nonlinear Dynamics, 2017, 89(3): 1-13.
[5] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman pro-blem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[6] GEETHA S, CHITRA G M, JAYALAKSHMI V. Multi objective mobile robot path planning based on hybrid algorithm[C]//Proceedings of the 2011 3rd International Conference on Electronics Computer Technology, Kanyakumari, Apr 8-10, 2011. Piscataway: IEEE, 2011: 251-255.
[7] LIU X Y, TAN L M, YANG C X, et al. Self-adjustable dynamic path planning of unknown environment based on ant colony-clustering algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(5): 846-857.
刘新宇, 谭力铭, 杨春曦, 等. 未知环境下的蚁群-聚类自适应动态路径规划[J]. 计算机科学与探索, 2019, 13(5): 846-857.
[8] ZHU Y, YOU X M, LIU S, et al. Research for robot path planning problem based on improved ant colony system (ACS) algorithm[J]. Computer Engineering and Applications, 2018, 54(19): 129-134.
朱艳, 游晓明, 刘升, 等. 基于改进蚁群算法的机器人路径规划问题研究[J]. 计算机工程与应用, 2018, 54(19): 129-134.
[9] SILVA J L, NEDJAH N, MACEDO M L, et al. ACO-based static routing for network-on-chips[C]//LNCS 7333: Procee-dings of the 12th International Conference on Computational Science and Its Applications, Salvador de Bahia, Jun 18-21, 2012. Berlin, Heidelberg: Springer, 2012: 113-124.
[10] LIU J H, YANG J G, LIU H P, et al. An improved ant colony algorithm for robot path planning[J]. Soft Computing, 2017, 21(19): 5829-5839.
[11] YOU X M, LIU S, LV J Q. Ant colony algorithm based on dynamic search strategy and its application on path planning of robot[J]. Control and Decision, 2017, 32(3): 552-556.
游晓明, 刘升, 吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J]. 控制与决策, 2017, 32(3): 552-556.
[12] SUN W, LV Y F, TANG H W, et al. Mobile robot path plan-ning based on an improved A* algorithm[J]. Journal of Hunan University (Natural Sciences), 2017, 44(4): 94-101.
孙炜, 吕云峰, 唐宏伟, 等. 基于一种改进A*算法的移动机器人路径规划[J]. 湖南大学学报(自然科学版), 2017, 44(4): 94-101.
[13] QU H, HUANG L W, KE X. Research on robot path planning based on improved ant colony algorithm in dynamic environ-ment[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(2): 260-265.
屈鸿, 黄利伟, 柯星. 动态环境下基于改进蚁群算法的机器人路径规划研究[J]. 电子科技大学学报, 2015, 44(2): 260-265.
[14] DONG S W, HUA F Y. Path planning of mobile robot in dynamic environments[C]//Proceedings of the 2011 2nd Inter-national Conference on Intelligent Control and Information Processing, Harbin, Jul 25-28, 2011. Piscataway: IEEE, 2011: 691-696.
[15] MAHI M, BAYKAN ? K, KODAZ H. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem[J]. Applied Soft Computing, 2015, 30: 484-490.
[16] ZHANG Y Y. Mobile robot path planning based on improved multi-step ant colony algorithm[D]. Wuhan: Wuhan University of Science and Technology, 2018.
张原艺. 基于改进多步长蚁群算法的移动机器人路径规划[D]. 武汉: 武汉科技大学, 2018.
[17] XU Y, CUI Y Y. Path planning based on Q-IGA dynamic fitting Bessel curve[J]. Journal of Hunan University (Natural Sciences), 2020, 47(10): 68-75.
徐岩, 崔媛媛. 基于Q-IGA动态拟合贝塞尔曲线的路径规划[J]. 湖南大学学报(自然科学版), 2020, 47(10): 68-75.