基于动态启发的双向搜索A*路径规划算法
A Bidirectional Search A* Path Planning Algorithm Based on Dynamic Heuristic Method
陈家伟 1许颖婷 1陈淑婧 1张霖 1蔡志明2
作者信息
- 1. 福建理工大学 电子电气与物理学院,福建 福州 350118
- 2. 福建理工大学 电子电气与物理学院,福建 福州 350118;福建理工大学 电子信息与电气技术国家级实验教学示范中心,福建 福州 350118
- 折叠
摘要
针对传统路径规划A*算法搜索速度慢,且所得路径转角过大的问题,提出了一种基于双向搜索的A*路径规划算法.首先调整A*搜索算法的整体搜索方向为双向搜索,初步提升搜索速度;其次,在规划过程中引入动态权重系数来调节启发式函数,通过平衡路径长短与规划速度之间的关系,进一步提高搜索速度;最后采用B样条曲线对所规划的路径进行平滑优化,解决A*算法规划路径转角过多无法满足移动机器人实际运动控制的问题.仿真实验结果表明,相比传统的A*算法,该算法在搜索节点和规划时间方面分别平均减少79.24%和62.56%.
Abstract
Aiming at the problem that the traditional path planning A* algorithm has slow search speed and the resulting path turning angle too large,an A* path planning algorithm based on bidirectional search is proposed.Firstly,the overall search direction of A* search algorithm is adjusted to bidirectional search to initially improve the search speed.Secondly,dynamic weight coefficients are introduced in the planning process to adjust the heuristic function to further improve the search speed by balancing the relationship between path length and planning speed.Finally,B-spline curve is used to smooth and optimize the planned paths to solve the problem that the A* algorithm planning paths with too many turning angles cannot meet the actual motion control.The results of simulation experiments show that compared with the traditional A* algorithm,the algorithm in this paper reduces the search nodes and planning time by 79.24%and 62.56%,respectively.
关键词
移动机器人/A*路径规划/双向搜索/动态权重系数/B样条曲线优化Key words
mobile robot/A* path planning/bidirectional search/dynamic weight coefficient/B-spline curve optimization引用本文复制引用
基金项目
福建工程学院校科研启动基金(GY-Z21064)
出版年
2024
国家科技期刊平台
NSTL
万方数据