基于A*算法的无人机地面目标跟踪*

席庆彪，杨述星，张 帅，屈耀红（.西北工业大学自动化学院，西安 7006；2.西北工业大学第65研究所，西安 70065；.中国航空无线电电子研究所，上海 20024）

基于A*算法的无人机地面目标跟踪*

席庆彪1，2，杨述星1，张 帅3，屈耀红1
（1.西北工业大学自动化学院，西安 710061；2.西北工业大学第365研究所，西安 710065；3.中国航空无线电电子研究所，上海 200241）

提出一种在威胁环境下应用A*算法进行目标跟踪的方法。为了简化模型和便于分析，主要考虑地形和雷达威胁。在考虑了雷达盲区的安全区域内，利用目标的实时信息和改进后的A*算法对无人机航迹进行规划，以达到跟踪地面移动目标的目的。仿真结果表明，所提出的方法可以很好地实现目标跟踪。

无人机，目标跟踪，雷达威胁，A*算法，航迹规划

0 引言

应用无人机跟踪地面目标主要包括以下几个问题，目标信息的获取（主要是通过搭载在无人机平台上的传感器，如摄像机），传感器的控制和无人机的导航算法。由于目标大多是运动的，要保证目标始终处在无人机的跟踪范围之内，就要利用航迹规划算法使得无人机与目标的距离满足跟踪任务的要求。

文献［1-2］中运用引导律，可实现对地面非合作静止目标的跟踪。但这两种方法并没有考虑飞行过程中可能遇到的障碍，如地形、火力威胁等造成的不可飞行区。同时，文献［1］提出的跟踪方法仅仅考虑当前时刻跟踪目标的速度信息，无法及时响应目标的机动变化，导致在跟踪机动目标时效果较差。

由于跟踪目标为机动目标，不同于从A点飞往B点的全局规划，这里的航路规划不能一次性离线完成，必须根据无人机、目标的位置等在线实时进行，边飞行边规划，使规划的航路对目标的机动作出及时反应。本文采用改进后的A*算法对无人机跟踪目标时的航迹进行动态规划，即根据无人机与被跟踪目标的状态信息和环境信息，实时规划飞行航迹，完成对运动目标跟踪任务。

1 模型预测控制及跟踪流程

MPC（Model Prediction Control）称为模型预测控制［3］，又称为滚动时域控制（RecedingHorizon Control，RHC）是20世纪80年代在工业控制领域出现的一类新型计算机控制算法，能够不断地在有限时域内求解离散时间内的优化问题，由于采用了多步预测、滚动优化和反馈校正的控制策略，模型预测控制具有控制效果好、鲁棒性强、对模型精确性要求不高等优点。

在模型预测控制算法中有一个问题需要解决，那就是对被跟踪的地面运动目标的状态信息进行预测。当无人机跟踪机动目标时，需要根据测量值对其进行预估。对于视觉跟踪任务而言，就需要对摄像机获得的图像进行处理，提取目标并对目标进行定位。本文不涉及图像处理的内容，只根据机动目标模型进行模拟并预测，然后将其作为航迹规划时的数据。在众多预测方法中，UKF（Unscented Kalman Filter）滤波未对系统方程和量测方程提出任何附加条件，本文利用的协同转弯模型为非线性模型［4］，因此，选择既适用于线性对象，也适用于非线性对象的UKF算法，且非线性越强，其算法的优越性越强［5］。

①当前t0时刻，以Δt为步长，规划以后N步最优航迹点序列；

②将前步规划的航迹点作为实际飞行航迹点，其中0＜K＜N；

③在t0+KΔt时刻重复①②步，直到任务结束。

借用模型预测控制思想的目标跟踪流程图1所示。

2 A＊算法求解航迹点序列

A*启发式搜索需要定义一个评价函数:

A*算法通常会把规划空间划分网格，事先计算每个网格的评价函数值，但对于很大的规划空间，这样做会占用较多的存储空间。本文对扩展的航迹点进行编码，求解时仅对涉及到的航迹点进行计算，使搜索空间大大减少，同时节省存储空间。若UAV在每个位置上都有N个可以选择的航向，规划M步，则扩展的航迹点共有N（i1≤i≤M）个。设每个航迹点编码为［m n］，其中m（1≤m≤M）表示扩展的第m步，n（1≤n≤Nm）表示第m步的第n个扩展节点。因为此处航迹点的扩展属于一对多的方式，每个后继节点有且只有一个父节点，对于每个节点［m n］均可方便地计算出其父节点的编码。在使用A*算法寻找最优航迹点序列时将扩展节点的编码加入OpenList、CloseList，仅当需要到该航迹点时再根据航迹点的规划方法计算其状态信息。

式（1）中的评价函数（fk）有两个系数ωg，ωh，分别表示对真实代价和估计代价的加权，选择不同的系数A*算法规划出的无人机航迹不同，且ωg+ωh=1。

假如我是水，遇到海洋生物搁浅沙滩，我会召集附近的兄弟们一起来帮忙，把搁浅的海洋生物送回大海，还要护送它们回到自己的族群。

2.1 A＊算法中启发函数的设计

作为启发式搜索算法，A*算法中的评价函数（fk）中包括消耗代价g（k）和估计代价h（k）。对于本文中的跟踪问题，可认为消耗代价g（k）主要由地形威胁和雷达威胁构成。h（k）有时也被称为启发函数，其主要作用是选择恰当的寻优方向，因此，h（k）设计的好坏，直接关系到该启发式搜索算法的性能优劣。文献［6-7］直接选择当前位置与目标位置两者之间的欧氏距离作为启发函数，针对跟踪问题，对每个航迹点，启发函数设为:

图1 目标跟踪流程图

式中:k为航迹点扩展步数；ρi为航迹点序列中第i个航迹点与目标的水平距离；ρd为UAV与目标的水平期望距离。

但是此启发函数并不能很好地反映当前节点的估计代价，容易导致前面搜索节点代价值f（k）较小，随着迭代的增加，后面添加的节点代价值较大，不利于算法快速收敛。因此，对其进行改进，本文选择启发函数为:

与式（2）相比，经式（3）改进后的启发函数结合了当前航迹点与待扩展航迹点的信息，有利于算法的收敛，能使UAV航迹更快的趋向于跟踪目标的期望航迹。

2.2 A＊算法中对雷达威胁代价的近似

在实际应用中，无人机的飞行环境中存在多种威胁，对于前面提出的实时规划航路方法，通过修改A*算法中的评价函数f（k），可以实现对威胁的规避［9］。把无人机飞行航迹的安全性纳入消耗代价g（k）中，即消耗代价为无人机所受各种威胁的综合，并将在威胁区域外的代价值设为0，这样做虽然可以确保当前时刻无人机处于威胁之外，但可能会导致无人机在未来时刻进入威胁区域。因此，需要对威胁建模进行改进。以雷达威胁为例，假设威胁半径为Rr，如图2所示，无人机当前位置为A，若使得无人机不会经过威胁区，则接下来的飞行航路必须限制在ABC围成的区域之外才能确保将来不会进入威胁区。

图2UAV规避威胁区示意图

设无人机与威胁中心水平距离为d，且以最大转弯角速率ψ˙max（对应最小转弯半径Rmin）进行转弯躲避威胁区，飞行航路与威胁区边界相切于点B、C，几何关系如下式:

由式（4）可以确定无人机在A位置能够规避威胁区的偏航角范围。只有规划的航迹点的偏航角处于此范围内才能确保无人机在未来时刻不会穿越威胁区。设求得到偏航角范围为［ψa，ψb］，扩展航迹点A的偏航角为ψk，若ψk∈［ψa，ψb］则表示若选择该航迹点，否则无人机无法规避威胁区。若按照文献［10］中建立的雷达威胁模型，此航迹点的消耗代价g（k）为0，显然并不合理，因此，必须赋予该航迹点一定的威胁代价，可选择如下的函数（5）作为雷达威胁区外的代价模型:

按式（5）对雷达威胁建模进行改进，利用无人机的最小转弯半径Rmin（对应最大偏航角速度ψ˙max）进行预先转弯，可迫使UAV在雷达可探测区域范围外就开始对威胁提前进行规避，降低了UAV在未来时刻进入雷达探测区域而被敌方发现的概率。

3 目标跟踪仿真

仿真在PC机（Windows7，2.4 GHz）MATLAB R2012a环境下进行。

假设无人机在威胁环境下对一协同机动目标进行跟踪，存在威胁为雷达波探测威胁且考虑地形的遮蔽作用［11］，两敌方雷达在北东地（NED）坐标系下的坐标分别为（12 500，6 000，5 000），（7 500，17 000，6 000），期望无人机能够在距离目标500 m的范围对目标进行跟踪。

无人机参数:飞行高度为1000m，速度为50m/s，最大偏航角速度ψ˙max为0.2 rad/s，北东地坐标系下的起始坐标为（-500，0，-1 000）。假设目标做协同转弯机动，其运动状态如下表:

时间t（s） 角速度ω（rad/s）0～200 0.006 201～300 0 301～400 -0.002 5 401～450 0 451～500 -0.02 501～600 0 601～850 0.008 851～1 000 0

采用本文的实时航路规划方法，且采用式（1）作为A*算法的评价函数，式（1）中的ωg、ωh决定了规划航路中对航路安全性及任务的侧重程度，选取不同的权值规划出的航路不同。

取ωg=0.9、ωh=0.1，仿真结果如下页图3所示。

取ωg=0.1、ωh=0.9，仿真结果如下页图4所示。

从图3中可以看出，在该参数设置下，在A处由于无人机规避威胁，在威胁区外飞行，导致其与目标水平方向的距离不断增大，借助B处雷达地形遮蔽盲区，无人机与目标水平方向的距离减小，直至到达期望距离。同样在C处，雷达地形遮蔽区的存在使得无人机可以与目标保持相对稳定的水平方向距离。在整个过程中无人机没有经过威胁区域，安全性较好，但t=370 s～580 s阶段无人机与目标的水平方向距离较大，有可能使得目标逃出无人机的跟踪范围，一定程度上影响任务的执行。

图3 ωg＞ωh时仿真图

图4 ωg＜ωh时仿真图

从图4中可以看出，在该参数设置下，无人机与目标的距离基本保持在500 m左右，使得无人机始终可以对目标的持续跟踪，保证了无人机对目标跟踪过程中的有效性，但是无人机在某些时刻进入了雷达威胁区域，安全性有所降低。

由图3、图4的对比可以看出，通过改变相应权值的值可以选择航路侧重任务图像的有效性或者航路的安全性，地面工作人员可根据具体情况设置相应权值以满足不同的跟踪任务要求。

4 结论

本文提出了一种将改进后的A*算法运用于地面移动目标跟踪的方法，算法中将启发函数加以改进，加快了UVA在跟踪目标过程当中寻找航迹时算法的收敛性，并且对雷达威胁之外的代价加以调整，使得威胁区之外的代价不在单纯地为0，避免了在后期跟踪过程中直接穿越威胁区，增加了UAV在完成任务时的安全性，对无人机实时跟踪目标具有一定的参考意义。

［1］TAY B C.Development and implement-ation of New Control Law for Vision Based Target Tracking system onboard small unmanned aerial vehicles［D］.Monterey，California.Naval Postgraduate School，2006.

［2］王勋，孔维玮，张代兵，等.无人机跟踪地面非合作目标的分段引导与控制方法［J］.中国科学技术大学学报，2012，42（9）:733-738.

［3］黄丁才.无人侦察机航线与传感器规划方法研究［D］.长沙:国防科学技术大学，2009.

［4］何祖军，尚明玲.基于无味粒子滤波和交互多模型算法的多机动目标跟踪［J］.江苏科技大学学报（自然科学版），2008，22（6）:48-52.

［5］崔锦泰，陈关荣.卡尔曼滤波及其实时应用［M］.北京:清华大学出版社，2013.

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

［7］蒙波，皮亦鸣，曹宗杰.基于改进A*算法的无人机航迹规划［J］.计算机仿真，2010，27（9）:29-32.

［8］FREW E W，LAWRENCE D A，MORRIS S.Coordinated standoff tracking of moving targets using Lyapunovguidance vector fields［J］.Journal of Guidance，Control，and Dynamics，2008，31（2）:290-306.

［9］席庆彪，苏鹏，刘慧霞.基于A*算法的无人机航路规划算法［J］.火力与指挥控制，2013，38（11）:5-9.

［10］丁鹭飞，耿富录.雷达原理［M］.西安:西安电子科技大学出版社，2002.

［11］葛津华，王红军，刘文正，等.多部干扰机支援干扰压制区建模与效果仿真［J］.舰船电子对抗，2010，33（4）: 33-35.

［12］FOO J L，KNUTZON J S，OLIVER J H，et al.Three dimensional multi-objective path planning of unmanned aerial vehicles using particle swarm optimization［J］.AIAA，2007 （4）:1-10.

［13］周代忠，张安，陶勇.无人战斗机航路规则圆切线算法［J］.火力与指挥控制，2007，32（3）:49-51.

Ground Target Tracking Base on A*Algorithm for Unmanned Aerial Vehicles

XI Qing-biao1，2，YANG Shu-xing1，ZHANG Shuai3，QU Yao-hong1
（1.School of Automation，Northwest Polytechnical University，Xi’an 710061，China；2.No.365 Research Institute，Northwest Polytechnical University，Xi’an 710065，China；3.China Aeronautical Radio Electronics Research Institute，Shanghai 200241，China）

A kind of method applying A*algorithm is proposed to track the object under threat environment in this paper.The influence of terrain and radar threat is mainly consideredfor the purpose of simplifying the mathematical model and facilitating the analysis.With considering the security zone of radar observation blind area，the real-time information of target and theimproved A*algorithmare used to plan the UAV flight path so as to track the groundmoving target.Experimental results show that the proposed method improves the performance of target tracking effectively.

unmanned aerialvehicles （UAV），targettracking，radarthreat，A*algorithm，routeplanning

TJ85

A

1002-0640（2017）03-0025-04

2016-01-06

2016-02-20

国家自然科学基金资助项目（61473229）

席庆彪（1964- ），男，安徽合肥人，研究员，硕士生导师。研究方向：无人机，导航、制导与控制，飞行控制与仿真技术。