摘要
针对传统A*算法在路径规划时,扩展节点与路径包含节点较多、搜索效率低、路径不平滑等问题,提出了一种基于12方向24邻域节点搜索的改进A*算法。给A*算法启发函数设置一个权重系数以减少冗余节点的数量;并且改进了传统A*算法8邻域的搜索策略,在父节点周围7×7的栅格地图中选取24个搜索邻域,按照目标点与当前点的位置关系剔除一半的冗余节点,保留12个方向的节点;然后利用贝塞尔曲线对规划的路径进行平滑处理。仿真及实验结果表明,改进后的A*算法相较于传统A*算法,扩展节点数减少了约44%,路径包含节点数减少了约43%,搜索时间减少了约69%,以此验证了该方案的可行性与有效性。
An improved A* algorithm based on 12 direction 24 neighborhood node search is proposed to address the problems of traditional A* algorithm in path planning,such as having more extended nodes and paths containing nodes,low search efficiency,and uneven paths.Set a weight coefficient for the heuristic function of the A* algorithm to reduce the number of redundant nodes.And it has improved the search strategy of the traditional A* algorithm in the neighborhood of 8,with 7 around the parent node×Select 24 search neighborhoods from the grid map of 7,remove half of the redundant nodes based on the positional relationship between the target point and the current point,and retain nodes in 12 directions;Then use the Bezier curve to smooth the planned path.The simulation and experimental results show that compared to the traditional A* algorithm,the improved A* algorithm reduces the number of extended nodes by about 44%,the number of nodes included in the path by about 43%,and the search time by about 69%,verifying the feasibility and effectiveness of this scheme.
作者
远子涵
张皓
左晋
张镇
YUAN Zihan;ZHANG Hao;ZUO Jin;ZHANG Zhen(School of Mechanical and Electrical Engineering,Beijing Institute of Graphic Communication,Beijing 102600,China;Intelligent Manufacturing Laboratory,Beijing Institute of Graphic Communication,Beijing 102600,China)
出处
《北京印刷学院学报》
2023年第9期38-43,共6页
Journal of Beijing Institute of Graphic Communication
关键词
A*算法
路径规划
搜索邻域
动态加权
贝塞尔曲线
A* algorithm
path planning
search neighborhood
dynamic weighting
Bezier curve
