基于动态加权A*算法的无人机航迹规划

何燕

摘 要：随着无人机航迹规划高维空间的扩展，无人机的飞行环境变得异常复杂，其外部威胁不再是简单的二维静态威胁，传统的蚁群算法和人工势场算法已经不能满足实时性和高复杂环境的要求。为解决上述问题，提出新的基于动态加权A*算法的无人机航迹规划。首先对无人机的飞行环境进行建模，通过研究航迹规划的转弯半径、航迹段长度和最大航程限制等约束条件，用于保证无人机的安全飞行，从而降低坠机率和威胁概率；其次，通过研究无人机的航迹和外部威胁参数，设计出新的航行方式，降低航行危险和减少损失；然后，通过扩展顶点势能定位和网格图整体變化的动态权重，获得动态环境下的代价函数，增加避障搜索速度、精度和加深回避程度。最后，通过仿真结果表明，在同一应用环境下，所提算法与蚁群算法和人工势场算法相比，航迹路径最优、威胁代价最小和算法执行的时间最短。综上，基于动态加权A*算法很好地应用于无人机航迹规划，降低了无人机航迹代价，缩短了算法完成时间，提高了复杂环境下无人机航迹规划的搜索速度和精度。

关键词：机电一体化技术；无人机；航迹规划；动态加权；高维空间；复杂环境；A*算法

中图分类号：TP13 文献标志码：A

文章编号：1008-1542（2018）04-0349-07doi：10.7535/hbkd.2018yx04009

Abstract： With the expansion of high dimensional space in UAV trajectory planning， the flying environment of UAV is very complex， and the external threat of UAV is no longer a simple two-dimensional static threat. The traditional ant colony algorithm and artificial potential field algorithm cannot meet the requirements of real-time and high complex environment. To solve the above problems， a new dynamic programming algorithm based on dynamic weighted A* algorithm is proposed. Firstly， the flight environment of UAV is modeled. By studying the constraints such as the turning radius， the length of track section and the limit of the maximum range， the safe flight of UAV is ensured， thus reducing the crash rate and the threat probability. Secondly， a new navigation mode is designed by studying the track and external threat parameters of the UAV， which can reduce the danger of navigation and reduce the loss. Then， the potential energy of the vertex can be expanded. The dynamic weight of the overall change of location and grid graph is obtained， and the cost function in dynamic environment is obtained， which increases the speed， accuracy and evasion degree of obstacle avoidance search. Finally， the simulation results show that under the same application environment， the proposed algorithm has the best path， the least threat cost and the shortest execution time compared with the ant colony algorithm and artificial potential field algorithm. To sum up， the dynamic weighted A* algorithm can be well applied to UAV trajectory planning， reducing the cost of UAV track， shortening the completion time of the algorithm and improving the search speed and precision of unmanned aerial vehicle trajectory planning in complex environment.

Keywords：mechatronics technology； UAV； route planning； dynamic weighting； high dimensional space； complex environment； A* algorithm

近年来无人机（UAV）技术得到了迅猛发展，无人机越来越多地应用于测绘、监视、周边巡逻或喷洒农药[1-5]，特别是无人机具有比地面或水上飞行器更宽的视野和更灵活的机动性，更适用于目标搜索应用所需的覆盖任务。假设一个人在野外迷路或一艘船沉入海中，随着时间的推移，生存的可能性会迅速下降。在这个时间敏感的情况下，无人机需要有效地检测感兴趣的区域，以便尽快找到目标。因此，覆盖搜索任务可以模拟为规划可行路线的优化问题，沿着该优化问题，传感器覆盖重要区域，以便在有限的飞行时间内使累积检测概率最大化[6]。与传统的从起点到目的地产生避障路线的路线规划任务不同[7-8]，由于需要覆盖可能重要的区域，这项任务更为复杂。路径规划是无人机任务管理系统的关键技术之一，也是无人机自主控制改进的重要环节[9]，在实际应用中，由于飞行环境的复杂性，无人机本身和环境存在很多限制。因此，建立高效的无人机路径规划算法已成为无人机飞行路径规划的关键。目前存在多种无人机路径规划算法[10]。大多数研究都集中在任务分配策略上[11-14]，主要关注最小化旅行距离或完成任务的时间。Voronoi图是解决路径规划问题的有效方法，但是如果不结合其他搜索算法[15]，很难找到最优解。蚁群算法[16-17]、遗传算法[18]以及粒子群算法[19]在二维路径规划中表现良好，并且有一些改进的策略。但是，随着搜索空间的扩展，这些算法已不能满足实时要求。人工势场[20-21]在无人机领域已经有很多的讨论，尽管研究者们在改善目标不可达性和轨道震荡现象等方面付出了很多努力，但解决这些问题的有效方法还有待开发。A*算法[22]是一种启发式算法，广泛应用于各种搜索问题，如机器人路径规划，计算机游戏AI和无人机障碍物无碰撞场等。

河北科技大学学报2018年第4期何 燕：基于动态加权A*算法的无人机航迹规划本文提出了一种改进的动态加权A*算法用于复杂环境下的无人机路径规划。首先给出航迹规划的约束条件，保证了无人机的安全飞行，降低坠机率和威胁概率；其次通过设计无人机的航迹代价，对外部威胁进行全面分析，设计出较好的航行方式，降低航行危险，减少损失；再者，通过扩展顶点势能定位，获得动态环境下的代价函数，根据网格图整体变化的动态权重，在接近障碍物时增加搜索速度，加深回避程度，在接近目标时提高搜索精度。

1 无人机飞行环境建模

无人机航迹规划是在三维空间中进行搜索，设（x，y，z）是任务空间中的扩展顶点n，其中xn，yn分别为纵向坐标和横向坐标，zn为该点的地形高度，该搜索空间可表示为Ωn={（xn，yn，zn）|0≤xn≤max Xn，0≤yn≤max Yn，0≤zn≤max Zn}。（1）在三维空间中，如图1所示对每个步骤都需要搜索24个点（整个空间被划分为一个小网格，只能在这些节点上选择飞行节点）。 因为不同类型的威胁会不同程度地影响无人机的飞行，所以约束条件比较复杂。

三维搜索空间中的问题更加复杂，因此需要缩小搜索空间的范围。在实际情况下，无人机的飞行路径必须满足最小转弯半径约束，最小航迹段长度、最大航程限制、最低飞行高度限制、最大爬升/俯冲角的要求等限制条件。由约束条件得到的当前节点的搜索区域如图2所示，在水平方向上，对称区域的最大偏航角度约束了选择，而在垂直方向最大上升角度中起到相同的作用。

1.1 无人机路径规划的约束

1）转弯半径最小化约束

受无人机硬件设施的性能限制，机身的转弯半径受到一定约束。在三维网格化搜索环境中，无人机必须在有限的方位上选取候选顶点，根据无人机所在顶点的方位信息，选出合适的待选顶点如图3所示。图3中mi为当前所在顶点，mi-1为进入该扩展节点的前一顶点， mj为待选顶点。

2）无人机航迹段长度最小化约束

2 基于动态加权A*算法的无人机航迹规划

由于A*算法不仅可以用来寻找最短路径，还可以使用启发式引导自己，将Dijkstra算法使用的信息（偏向接近起始的顶点）和Greedy Best-First-Search使用的信息（偏向接近目标的顶点）进行有效组合。A*算法通过执行最佳优先搜索找到从起始顶点S到目标顶点G的图中的路径。从S开始，A*算法迭代地扩展顶点n，这使得成本函数f（n）=g（n）+h（n）最低。g（n）表示从起始S到任意顶点n的路径的确切成本，即从S到n的最佳发现路径的代价；h（n）表示从扩展顶点n到目標G的启发式估计成本，即估计从状态n到G的代价的启发函数。每次通过主循环时，它检查具有最低启发函数的扩展顶点n：

3 仿真分析

在仿真部分，可以建立一个飞行环境，假设无人机可以在北纬25°到北纬36°，东经101°到东经115°，高度为0～7 000 m。比较了改进的加权A*算法与蚁群算法和人工势场算法在无人机飞行1 000 m以上的情况。在本文中，假设无人机以不同类型的威胁从起点飞向目的地，并且必须穿过每个任务点。改进的A*算法仿真结果如图6所示，黑色圆圈代表威胁源，黑色圆点为无人机必须通过的任务点，曲线为无人机的航行轨迹。

在同一环境中使用蚁群算法和人工势场算法，仿真航迹分别如图7和图8所示。

为了比较这3种算法，使用3个指标来描述其质量，即航迹长度，航迹代价和算法完成时间。所有的模拟都在同一个平台上执行，3种算法航迹规划性能比较如表1所示。

从结果中可以看到改进的A*算法优于蚁群算法和人工势场算法。首先，改进的A*算法在航迹代价和航迹长度上具有很大的优势。尽管人工势场算法的完成时间比A*算法快一点儿，但与蚁群算法相比，A*算法的速度也很快了，这意味着它的实时重新计算能力是可以接受的。

4 结 论

针对无人机高维复杂飞行环境下，高维地形数学建模、任务目标搜索路径规划及航迹代价设计等问题，对A*算法、人工势场算法和蚁群算法进行了深入研究，提出基于动态加权A*算法的无人机航迹规划方案，以解决无人机路径规划问题。首先对基本的A*算法进行了一系列改进，使其更适应复杂的真实环境，通过无人机路径规划的约束保证无人机安全飞行，达到很好的避障效果；根据无人机所在的任务区域，综合考虑影响航行轨迹性能的各种因素，包括威胁代价、高度代价和航程代价的综合航迹代价指标，设计了精确的实际代价函数；将归一化的全局势场作为启发函数的权重系数，提高了搜索精度和实时性。最后的实验结果验证了基于动态加权的A*算法在解决无人机路径规划问题中的可行性和有效性，降低了无人机的航行成本，减少了算法执行时间，提高了复杂环境下无人机航迹规划的搜索速度和精度。

参考文献/References：

[1] BEARD R W， MCLAIN T W，NELSON D B， et al. Decentralized cooperative aerial surveillance using fixed-wing miniature UAVs[J]. IEEE， 2006，94（7）： 1306-1324.

[2] KALYANAM K， CHANDLER P， PACHTER M， et al. Optimization of perimeter patrol operations using unmanned aerial vehicles[J]. Journal of Guidance Control & Dynamics， 2015，35（2）：434-441.

[3] OH H， KIM S， SHIN H S， et al. Coordinated standoff tracking of moving target groups using multiple UAVs[J]. IEEE Trans， 2015， 51（2） ：1501-1514.

[4] WANG Y， WANG S， TAN M . Path generation of autonomous approach to a moving ship for unmanned vehicles[J]. IEEE Trans， 2015， 62（9）：5619-5629.

[5] 李永伟，王红飞.六旋翼植保无人机模糊自适应PID控制[J].河北科技大学学报，2017，38（1）：59-65.

LI Yongwei， WANG Hongfei. Fuzzy-adaptive PID control of six-rotor wing plant protection UAV[J]. Journal of Hebei University of Science and Technology， 2017， 38（1）：59-65.

[6] BOURGAULT F， FURUKAWA T， DURRANT-WHYTE H F. Coordinated decentralized search for a lost target in a Bayesian world[C]//Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas： IEEE， 2003： 48-53.

[7] ROBERGE V， TARBOUCHI M， LABONTE G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. IEEE ， 2013， 9（1）：132-141.

[8] YAO P， WANG H L， SU Z K. UAV feasible path planning based on disturbed fluid and trajectory pro-pagation[J].Chinese Journal of Aer-onautics，2015，28（4）： 1163-1177.

[9] CHANDLER P R， PACHTER M. Research issues in autonomous control of tactical UAVs[J]. IEEE， American Control Conference， 1998，1：394-398.

[10]BORTOFF S A. Path planning for UAVs[J]. IEEE，American Control Conference， 2000，1（6）： 364-368.

[11]BERTUCCELLI L F， HOW J P. Search for dynamic targets with uncertain probability maps[J]. IEEE，2006， 6：737-742.

[12]ZHU Hongguo，ZHENG Changwen，HU Xiaohu， et al. Path planner for unmanned aerial vehicles based on modified PSO algorithm[C]// International Conference on Information and Automation.Changsha：[s.n.]， 2008：541-544.

[13]RATHINAM S， SENGUPTA R. Lower and upper bounds for a multiple depot UAV routing problem[C]// Proceedings of the 45th IEEE Conference on Decision and Control.San Diego：IEEE，2006：5287-5292.

[14]SUJIT P B， BEARD R. Multiple UAV path planning using anytime algorithms[C]//2009 American Control Conference.St. Louis：IEEE， 2009：2978-2983.

[15]PEHLIVANOGLU Y V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J]. Aerospace Science and Technology， 2012， 16（1）： 47-55.

[16]DORIGO M， MANIEZZO V， COLORNI A. Ant system： Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， 1996，26（1）： 29-41.

[17]吳学礼，贾云聪，张建华，等.一种改进蚁群算法的无人机避险方法仿真研究[J].河北科技大学学报，2018，39（2）：166-175.

WU Xueli， JIA Yuncong， ZHANG Jianhua， et al. Simulation research on hedging method of UAV based on improved ant colony algorithm [J]. Journal of Hebei University of Science and Technology， 2018， 39（2）：166-175.

[18]NIKOLOS I K， VALAVANIS K P， TSOURVELOUDIS N C， et al. Evolutionary algorithm based offline/online path planner for UAV navigation[J]. IEEE， 2003， 33（6）： 898-912.

[19]ALEJO D， COBANO J A， HEREDIA G， et al. Particle swarm optimization for collision-free 4d trajectory planning in unmanned aerial vehicles[C]//2013 International Conference on Unmanned Aircraft Systems.Seville：IEEE，2013： 298-307.

[20]LIN C L， LEE C S， HUANG C H， et al. Unmanned aerial vehicles evolutional flight route planner using the potential field approach[J]. Journal of Aerospace Computing Information and Communication， 1971，9（9）：92-109.

[21]甄然，甄士博，吳学礼.一种基于人工势场的无人机航迹规划算法[J].河北科技大学学报，2017，38（3）：278-284.

ZHEN Ran， ZHEN Shibo， WU Xueli. An improved route planning algorithm for unmanned aerial vehicle based on artificial potential field[J]. Journal of Hebei University of Science and Technology， 2017， 38（3）： 278-284.

[22]李季，孙秀霞.基于改进A-Star算法的无人机航迹规划算法研究[J].兵工学报，2008，29（7）：788-792.

LI Ji， SUN Xiuxia. A route planning's method for unmanned aerial vehicles based on improved A-Star algorithm [J]. Acta Armamentarii，2008，29（7）：788-792.

[23]李猛.基于智能优化与RRT 算法的无人机任务规划方法研究[D].南京：南京航空航天大学，2012.

LI Meng. Research on Mission Planning of UAV Based on Intelligent Optimization and RRT Algorithm[D]. Nanjing：Nanjing University of Aeronautics and Astronautics，2012.