双邻域选择扩展A^(*)路径规划算法  

A^(*)Algorithm of Path Planning Combining with Dual Neighborhood Selection Expansion

作　　者：杨秀建[1] 袁志豪 白永瑞 敖鹏 YANG Xiujian;YUAN Zhihao;BAI Yongrui;AO Peng(Faculty of Transportation Engineering,Kunming University of Science and Technology,Kunming 650504,China)

机构地区：[1]昆明理工大学交通工程学院,昆明650504

出　　处：《机械科学与技术》2025年第3期484-495,共12页Mechanical Science and Technology for Aerospace Engineering

基　　金：国家自然科学基金项目(52162046)。

摘　　要：针对A^(*)算法在路径规划过程中存在的扩展节点过多、路径冗余点过多等问题,对经典A^(*)算法进行了改进研究。提出了斜八邻域扩展的概念,与四邻域扩展结合组成一种新的双邻域选择扩展策略,在路径搜索过程中可以有效减少扩展节点的数量。为适应多种地图环境建立了新的启发函数,在相同地图环境下较经典A^(*)算法扩展的节点数量减少50%以上,路径搜索速度提高了一个数量级,算法效率明显提升。通过建立冗余点剔除策略与三次B样条曲线对初始路径进一步优化,剔除路径多余节点,减少路径转折,规划出一条符合机器人运动的最优路径。首先,在4种不同障碍物的地图环境下对改进后的A^(*)算法进行了仿真分析,并与Dijkstra、四邻域A^(*)算法、八邻域A^(*)算法进行了比较;然后,基于实验室的智能车试验平台进行了场地试验,对改进后的A^(*)算法进行了试验验证。结果表明:改进后A^(*)算法的路径搜索效率大幅提高,路径更有利于机器人运动,所提出的A^(*)改进算法是可行的、有效的。Focusing on the problems such as too many expansion nodes path redundancy points in path planning for the classical A^(*)algorithm,this paper aims to study the improvement of the classical A^(*)algorithm.Firstly,the concept of slant-eight-neighborhood expansion is proposed,and by combining with the four-neighborhood expansion,a novel dual-neighborhood selection expansion strategy is proposed.By this novel strategy,the number of expansion nodes can be greatly reduced in the path search process.In addition,a new heuristic function is established to adapt to a variety of map environments.Hence,the number of expanded nodes can be reduced by above 50%in the same map environment comparing with the classical A^(*)algorithm,and the path search speed can be improved by one order of magnitude,and the efficiency of the algorithm is significantly improved.Then,the initial path is further optimized by establishing a redundant point elimination strategy and the cubic B-spline curve.Thus,an optimal path that meets the robot motion can be obtained by eliminating the redundant nodes and reducing path turns.Finally,the improved A^(*)algorithm is evaluated and analyzed by comparing with the Dijkstra algorithm,four-neighborhood expansion algorithm and eightneighborhood expansion algorithm by simulation in four maps with different obstacles.And,also the present algorithm is verified by using the field tests based on the intelligent vehicle platform.The results show that by the improved A^(*)algorithm the path search efficiency can improved significantly,the planned path is more suitable for the robot motion.In summary,the present improved A^(*)algorithm is believed to be feasible and effective.

关 键 词：移动机器人 路径规划 A^(*)算法 邻域扩展 启发函数 冗余点剔除 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]