改进A^(*)算法的校园无人配送路径规划  

Campus Unmanned Distribution Path Planning Based on Improved A^(*) Algorithm

作　　者：张文明 吴岳忠[1] 文亚 刘富民 谭筠 邓彬 ZHANG Wenming;WU Yuezhong;WEN Ya;LIU Fumin;TAN Yun;DENG Bin(School of Railway Transportation,Hunan University of Technology,Hunan Zhuzhou 412007,China;School of Computer Science,Hunan University of Technology,Hunan Zhuzhou 412007,China;Department of Academic Periodicals,Hunan University of Technology,Hunan Zhuzhou 412007,China;Changsha Xingshen Intelligent Technology Co.,Ltd.,Changsha 410000,China)

机构地区：[1]湖南工业大学轨道交通学院,湖南株洲412007 [2]湖南工业大学计算机学院,湖南株洲412007 [3]湖南工业大学期刊社,湖南株洲412007 [4]长沙行深智能科技有限公司,长沙410000

出　　处：《包装工程》2024年第19期275-282,共8页Packaging Engineering

基　　金：湖南省教育厅科学研究重点项目(22A0422);中国高校产学研创新基金重点课题(2022IT052);国家级大学生创新训练项目(202211535026)。

摘　　要：目的以校园为应用场景,针对A^(*)算法规划的路径存在搜索效率低、拐角大且不符合校园无人配送车的运行约束条件等问题,提出一种基于A^(*)算法改进的高效路径搜索算法。方法首先通过改进评价函数的具体计算方式并为预估函数部分附加一个权重系数来减少不必要的往返搜索,以提高搜索速度;然后计算向量角和作线段来剔除冗余节点,以减小路径总长度;接着对OPEN表的数据存储结构进行替换,使用最小堆替换数组以更快访问最优节点,提升算法计算效率;最后采用贝塞尔曲线对路径进行平滑处理,使带尖角的地方变平滑,减小拐角。结果通过实验结果可知,改进后的A^(*)算法相比于传统A^(*)算法的搜索效率提高了58%,路径平滑程度也有显著提高。结论改进后的A^(*)算法可以用于校园无人车的路径规划,验证了算法的可行性。The work aims to propose an improved efficient path search algorithm based on the A^(*)algorithm to solve the problems of low search efficiency,large corner and non-compliance with the operation constraints of campus unmanned distribution vehicles in the application scenario of campuses.Firstly,the unnecessary round-trip search was reduced by improving the specific calculation method of the evaluation function and adding a weight coefficient to the prediction function to improve the search speed.Then the vector angle and the line segment were calculated to eliminate the redundant nodes to reduce the total length of the path.The data storage structure of the OPEN table was replaced,and the minimum heap was used to replace the array to access the optimal node faster,so as to improve the computational efficiency of the algorithm.Finally,the Bessel curve was used to smooth the path,to smoothen the place with sharp corners and reduce the corners.The experimental results showed that the improved A^(*)algorithm improved the search efficiency by 58%compared with the traditional A^(*)algorithm,and also significantly improved the path length and path smoothness.The experimental results show that the improved A^(*)algorithm can be used for the path planning of campus unmanned vehicles,which verifies the feasibility of the algorithm.

关 键 词：路径规划 A^(*)算法 评价函数 贝塞尔曲线 校园无人配送 

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