基于改进A*算法的应急救援无人机路径规划  

Path Planning of Emergency Rescue UAV Based on Improved AAlgorithm

作　　者：王其[1,2] 王磊[1,2] 倪世松[1,2] 陈明星[1,2] WANG Qi;WANG Lei;NI Shi-song;CHEN Ming-xing(School of Computer Science,School of Software,School of Cyberspace Security,Nanjing University of Information Technology,Nanjing Jiangsu 210044,China;Engineering Research Center of Digital Forensics,Ministry of Education,Nanjing Jiangsu 210044,China)

机构地区：[1]南京信息工程大学计算机学院、软件学院、网络空间安全学院,江苏南京210044 [2]数字取证教育部工程研究中心,江苏南京210044

出　　处：《计算机仿真》2024年第6期84-88,353,共6页Computer Simulation

基　　金：江苏省自然科学基金青年基金项目(BK20160955);江苏省产学研合作项目(BY2020648)。

摘　　要：针对救援无人机传统路径规划算法存在搜索扩展节点数多、搜索路径时间长、规划轨迹不平滑的缺点,提出了一种改进A*算法的应急救援无人机路径规划方法。采用对角线距离作为启发函数并进行指数加权,通过双向搜索策略进行搜索优化,对生成的路径点使用贝塞尔曲线进行曲线拟合。实验中设计了多种非结构化地图,对Dijkstra算法、传统A*算法和改进A*算法在搜索扩展节点数、规划路径长度和搜索路径时间三方面进行对比。实验结果表明,设计的多种地图中改进A*算法在搜索扩展节点数较Dijkstra算法和传统A*算法分别至少降低了59.82%、39.40%,在搜索路径时间分别至少降低了57.38%、33.46%,规划后的路径经过贝塞尔曲线优化后满足无人机的实际飞行要求,可以实现高效率无人机应急救援。Aiming at the shortcomings of the traditional path planning algorithm for rescue UAVs,such as a large number of search expansion nodes,long search path time,and uneven planning trajectory,an improved A∗algorithm for emergency rescue UAV path planning was proposed.The diagonal distance was used as a heuristic function and exponentially weighted,and the search optimization was carried out through a two-way search strategy,and the gener⁃ated path points were fitted with a Bezier curve.A variety of unstructured maps were designed in the experiment,and the Dijkstra algorithm,the traditional A∗algorithm and the improved A∗algorithm were compared in terms of the number of search expansion nodes,the length of the planned path and the search path time.The experimental results show that the number of search expansion nodes of the improved A∗algorithm in the various maps designed is at least 59.82%and 39.40%lower than that of the Dijkstra algorithm and the traditional A∗algorithm,and the search path time is reduced by at least 57.38%and 33.46%,respectively.,the planned path is optimized by the Bezier curve to meet the actual flight requirements of the UAV,which can achieve high-efficiency UAV emergency rescue.

关 键 词：应急救援 指数加权 双向搜索 贝塞尔曲线 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]