一种改进型A?算法的AGV路径规划
AGV path planning based on an improved A?algorithm
洪楚桐 1郭彦青 1张盼盼 1康瑞 1马鹏豪1
作者信息
- 1. 中北大学机械工程学院,山西 太原 030051
- 折叠
摘要
A∗算法是一种常见的AGV路径规划算法,然而当AGV的运动环境很复杂时,A∗算法的效率会显著下降.针对传统A∗算法存在路径搜索效率低、路径转折次数多等问题,提出一种改进型 A∗算法.首先基于栅格法对地图进行建模,随后对A∗算法的启发函数和邻域搜索策略展开研究,引入动态加权机制改进启发函数,并在此基础上加入动态五邻域搜索策略.最后在 Python编程环境下,分别使用两种不同障碍率的栅格地图对改进型A∗算法与传统A∗算法进行对比仿真实验.仿真结果表明,改进型A∗算法搜索时间平均缩短了69.3%,路径拓展节点数平均减少了74.5%,可以明显减少转弯次数,提升整体效率,尤其是在障碍率较高时优化效果更明显;引入贝塞尔曲线后,可使移动路径更加平滑.
Abstract
The A∗algorithm is a common AGV path planning algorithm,but the efficiency of the A∗ algorithm will be significantly reduced when the AGV movement environment is complex.In order to solve the problems of low path search efficiency and many path turns in the traditional A∗algorithm,an improved A∗algorithm is pro-posed.Firstly,the map is modeled based on the raster method,and then the heuristic function and neighborhood search strategy of the A∗algorithm are studied,the dynamic weighting mechanism is introduced to improve the heuristic function,and the dynamic five-neighborhood search strategy is added on this basis.Finally,in the python programming environment,two raster maps with different obstacle rates are used to compare and simulate the improved A∗algorithm and the traditional A∗algorithm.The simulation results show that the search time of the improved A∗algorithm is shortened by 69.3%on average,and the number of path expansion nodes is re-duced by 74.5%on average,which can significantly reduce the number of turns and improve the overall effi-ciency,especially when the obstacle rate is high.When Bezier curves are introduced,the movement path is smoother.
关键词
自动导向车/路径规划/改进型A∗算法/动态加权/搜索邻域/贝塞尔曲线Key words
AGV/path planning/improved A∗algorithm/dynamic weighting/search for neighborhoods/Bezier curves引用本文复制引用
出版年
2025
NETL
NSTL
万方数据