Journal of Frontiers of Computer Science and Technology ›› 2021, Vol. 15 ›› Issue (10): 1969-1979.DOI: 10.3778/j.issn.1673-9418.2011061

• Artificial Intelligence • Previous Articles     Next Articles

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

YIN Shaowei, PENG Li, DAI Feifei   

  1. 1. Engineering Research Center of Internet of Things Technology Applications of the Ministry of Education, School of Internet of Things Engineering, Jiangnan University, Wuxi, Jiangsu 214122, China
    2. Taizhou Institute of Product Quality and Safety Testing, Taizhou, Zhejiang 318000, China
  • Online:2021-10-01 Published:2021-09-30

融合改进A*蚁群和滚动窗口法的平滑路径规划

殷绍伟彭力戴菲菲   

  1. 1. 物联网技术应用教育部工程研究中心(江南大学 物联网工程学院),江苏 无锡 214122
    2. 台州市产品质量安全检测研究院,浙江 台州 318000

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), 贝塞尔曲线, 动态避障