基于路径规划的无人机飞行冲突解脱技术*

魏潇龙，姚登凯，戴喆，韩其松

（空军工程大学空管领航学院，西安710051）

基于路径规划的无人机飞行冲突解脱技术*

魏潇龙，姚登凯，戴喆，韩其松

（空军工程大学空管领航学院，西安710051）

在无人机与有人机共用空域时，随时可能发生飞行冲突，应当有一种可靠的冲突解脱技术，保证无人机的空域运行安全。为此，构建了基于正三角形栅格法的空域运行环境，改进了以往十字栅格环境规划动态路径的缺陷；提出了基于空间分割的改进蚁群算法，提高了算法的寻优性能与路径规划能力。最后结合ADS-B系统的工作原理，在利用卡尔曼滤波对ADS-B信息进行修正的基础上，设计了无人机冲突感知的技术方案，并用实时的路径重规划技术实现飞行冲突的解脱。最终的仿真实验验证了飞行冲突解脱技术方案的有效性，可为未来无人机的空域运行技术提供一定的理论参考。

无人机，蚁群算法，路径规划，ADS-B，冲突解脱

0　引言

无人机空域运行通常有“隔离空域”和“非隔离空域”运行［1］。在过去很长一段时间里，由于无人机“感知-避让”性能上的缺陷，国内外对无人机的管制一般都采取划设隔离空域的方式运行。但随着无人机技术的发展，无人机的飞行高度覆盖从近地面的几十米到几万米高空，航程可达上万公里，无人机早已具备了全空域飞行的能力［2］。随着无人机技术的进一步发展，以往划设“隔离空域”的方式无法再满足无人机的空域使用需求，无人机飞出“隔离空域”进入“非隔离空域”与有人机共同飞行已成为必然趋势。

为使无人机进入“非隔离空域”运行，美国国防部［3］与FAA（Federal Aviation Administration）［4］分别对军用无人机与民用无人机制定了详细的空域集成计划，以促进无人机尽快融入美国国家空域系统。其中，“感知-避让”系统是其研究重点，但主要基于路径规划技术对动态与静态的威胁源的避让，总体上还不够完善，这主要的原因就在于无人机“感知-避让”这一过程取决于很多的组合因素，需要进一步加以细化研究［1-5］。从国内的研究现状来看，大量研究都使用群智能算法作为无人机路径规划的基本模型，虽然在路径规划质量上都取得了较好的效果，实时性要求上还很难适应快速多变的空域环境；在技术应用方面，主要集中于无人机在作战或通用航空领域的任务执行效率上，对于无人机空域运行安全的研究较少，限制了无人机在各个领域的使用。

对于一些中小型无人机而言，一般航程较短，应用范围小，与有人机之间发生飞行冲突的可能性较小。对于大型的远程无人机，尤其是中空远程无人机，其使用空域与有人机存在较大的重叠［6］，对飞行冲突解脱技术具有迫切的需求，又由于远程无人机运载能力较强，具备加载防相撞设备的能力，因此，选取远程无人机作为主要研究对象。本文针对远程无人机巡航飞行阶段穿越空域范围广、发生飞行冲突频率高的特征，设计了一种基于路径规划的冲突解脱方案。该方案吸收了当前先进的ADS-B系统作为冲突信息源，通过实时的路径重规划来实现对动态威胁源的避让，最终使无人机具备实时快速的自主冲突解脱能力，提高无人机的空域运行安全。

1　空域运行环境建模

1.1地图的栅格化处理

为了创造一个路径规划空间，并进行快速地优化计算，一般都将地图进行栅格化处理。针对不同的问题可以构建不同维度与不同栅格方式的规划空间。当无人机遇到飞行冲突，可以采用上升、下降高度的方式实施避让，也可以利用向左、向右机动的方式进行避让。但为了缩小规划空间维度，生成更利于飞行的路径，统一实施水平面内的避让，此时可假设无人机在二维平面内以匀速飞行。动态路径规划与时间有较大的相关性，传统的十字栅格方式由于状态转移步长的不一致，在无人机冲突避让过程中会出现速度上的频繁波动，以至于严重脱离真实的飞行情景，因此，必须改进栅格方式，使无人机在巡航飞行过程中符合速度相对稳定的特征（十字形栅格中的转移步长如图1所示）。

本文所使用栅格方式是基于正三角形的空间栅格，可很好地实现无人机单位时间内转移步长的一致性，符合巡航飞行过程中飞行速度相对稳定的特征，如图2所示。

图1　十字形栅格中的转移步长

图2　改进栅格中的状态转移步长

1.2主要威胁模型的构建

1.2.1空域模型

为了空域使用的安全有序，航空管制部门会根据各个空域用户任务执行或空中作业的需要划设一定的空域范围，对于一些具有政治、军事特殊敏感性的城市上空，还会划设空中禁区或限制区，未经批准，所有航空器严禁飞入。因此，无人机在高空巡航过程中所飞行的路径必须避开这些空域，以免航空事故的发生。管制部门所划设的空域一般可近似为矩形或圆形，因此，空域的威胁模型可基于矩形与圆构造。矩形空域威胁计算如图3所示。

图3　矩形空域威胁计算

矩形空域威胁代价计算公式为：

其中，f1为常数；（xa，ya）为空域的中心点；（x，y）为无人机路径节点坐标；p为某条路径点的集合；a，b分别为空域的竖边与横边长度的一半。

对圆形空域的威胁代价计算公式为：

其中，（xr，yr）为圆形空域的中心点。

1.2.2移动航空器威胁模型

根据《飞行间隔规定》的要求，在雷达管制的条件下，航空器在巡航阶段的间隔应保持在10 km以上。因此，可以借鉴Reich改进模型建立碰撞模型［7］，将无人机看成质点，而将其他周围的航空器看成是半径为10 km的圆，当无人机质点进入航空器的移动圆内，则认为发生了飞行冲突，存在较大的相撞风险。威胁的计算公式为：

其中，（xf，yf）为其他航空器的位置坐标；f2为常数。

1.2.3航程威胁

在无人机的路径规划中，加入航程约束不但可以使模型符合无人机真实的性能约束，还可以起到优化路径冗余度的作用。航程威胁计算公式为：

其中，l为路径长度；f3为常数。

2　基于改进蚁群算法的路径规划算法

蚁群算法作为一种最新提出的仿生进化算法具有：鲁棒性强、并行计算能力、全局搜索能力、正反馈机制、易于与其他算法混合等优点［8-9］。目前为止，蚁群算法已经成功解决了旅行商问题、指派问题、调度问题、车辆路由问题、网络路由问题等组合优化问题，且与旅行商问题具有一定的相似性，但由于蚁群算法具有搜索时间长、易陷入局部解两大缺点，必须要加以改善才能适应无人机路径规划的复杂性与对时效性的要求。

2.1基于基本蚁群算法的路径规划模型

蚁群的搜寻空间为一个被正三角形栅格化的二维平面，平面内的所有栅格节点按从左至右，从上至下的顺序编号，并将所有蚂蚁置于路径规划的起点。为每一只蚂蚁制定禁忌表，并把起始节点放入禁忌表中。对所有的栅格点赋予初始信息素浓度，赋予能见度ηn，其中：

其中，dn为节点到终点的距离，n为节点的编号。

在考虑无人机转弯率小于60°的情况下，蚂蚁状态转移的概率选择公式为：

在所有蚂蚁进行完一次路径规划后，则需要进行信息素的更新，信息素更新公式为：

在完成一次信息素更新之后，一次循环结束，对形成的路径进行适应性评价，适应性函数为：

其中，w1，w2，w3为权重；J为综合代价。

记录适应性最佳的路径，将所有蚂蚁重新置于起点，再次进行路径规划，并在每次迭代结束后更新最优路径，循环计算NCmax次，输出最优路径，计算结束。

2.2引入最大最小蚂蚁系统

在基本蚁群算法中，所有蚂蚁都被一视同仁，在迭代过程中产生的最优解很有可能被次优解掩盖，寻优速度缓慢，且容易出现收敛停滞的现象。为了抵消上述的影响，引入最大最小蚂蚁系统。该系统将所有节点的信息素变化范围限制在区间［min，max］内，并在初始化时将所有节点都赋予信息素浓度max，这样可以避免因某条路径浓度过高发生收敛停滞的现象。

2.3引入基于排序的蚂蚁系统

在无人机路径规划问题中，有时候最优解与次优解之间会相差较大距离，甚至不在同一方向上。最大最小蚂蚁系统中只有最优蚂蚁才释放信息素，将所有蚂蚁趋向最优蚂蚁附近，当最优蚂蚁附近的解与真实的最优解之间差距较大时，最优解就有可能被错过，对此，引入基于排序的蚂蚁系统。每次迭代完成，对所有蚂蚁进行排序，除最优蚂蚁释放信息素外，适应度为前γ的蚂蚁都进行信息素的释放，信息素更新公式为：

2.4基于空间分割的改进蚁群算法

蚁群算法本质上是一种基于概率搜索的群智能算法［10］，寻优空间的大小与复杂度会对计算结果产生巨大影响。算法本身的寻优性能决定了最终解与真实最优解之间的差距，无论怎样增加迭代次数或初始种群数，优化效果都极为有限，特别是部分路径节点上的冗余路径很难剔除，且冗余路径会随着规划空间规模与结构复杂度的增大而增加。以往有大量改进算法都从改变算法的收敛性与全局搜索性入手以提高最终解的质量，但对于路径规划一类较复杂的问题，最终解仍会有一些明显的冗余度，需要改变思路加以优化。

为了从根本上改变因规划空间过大，影响算法寻优性能的缺陷，本文提出了基于空间分割的改进蚁群算法。在进行初步路径规划的基础上，选取中间路径节点作为路径精细规划的出发点或终点，从而达到空间分割的目的。由于空间在初步规划的基础上被重新分割，在较小的空间内进行路径规划可以有效降低寻优的难度，实现路径优化的目的（规划空间的分割原理如图4所示）。

图4　空间分割基本原理

最终改进算法的流程如图5所示。

3　基于路径规划的冲突解脱方案设计

3.1飞行冲突感知方案设计

ADS-B（Automatic Dependent Surveillance-Broadcasting）是ADS技术的一种，是在ADS、TCAS（Traffic Alert and Collision Avoidance System）和场面监视的基础上，综合其三者的特点提出的一种监视技术，作为未来主要的航空监视手段之一，已成为ICAO（International Civil Aviation Organization）新航行系统方案中的一个重要组成部分［11］。无人机装载ADS-B系统进行冲突感知可有效节省无人机空域运行系统建设的成本，且保持与当前有人机空域运行系统较好的兼容性。ADS-B系统播报的信息丰富，包括三维位置信息、速度信息、二次雷达代码、机号等，可以为无人机的冲突预测提供充足的数据基础。

图5　基于空间分割的改进蚁群算法流程

图6　无人机冲突感知系统方案设计

无人机的位置信息主要来自GNSS（Global NavigationSatelliteSystem）与自身的惯导系统，通过ADS-B系统每隔1s的报文发送与实时的报文接收实现与周围航空器间的态势感知。利用AES（Aircraft Earth Station）/ACARS（Aircraft Communications Addressing and Reporting System）向RGS（Remote GroundStation）或通信卫星发送自身的状态参数，传递至地面的管制中心，最后实现管制部门对无人机运行状态的实时监视。无人机的冲突感知主要基于航空计算机对其他飞机状态参数的解算与预测，地面管制员基于监视画面的冲突发现也起到一定作用（无人机飞行冲突感知的系统方案设计如图6所示）。

3.2飞行冲突预测算法

对周围航空器的冲突预测需要先建立各个航空器的历史航迹。ADS系统对航迹信息的处理主要包括3个过程，既航迹的起始、航迹的滤波与航迹的终止［11］。当无人机的机载ADS设备收到某架航空器的ADS-B信息时首先进行航空器呼号的识别与比对，若在历史记录中存在该航空器的记录，则进行历史航迹的更新，若没有该航空器的历史记录，则建立新的航迹。如果在足够长的一段时间内没有收到某个已有记录航空器的ADS-B信息，则认为该航空器的飞行已经终止，应该清除航迹记录。航迹的滤波则主要是为了对ADS-B信息进行修正，降低导航源的噪声影响。

根据ADS-B系统的工作原理，结合卡尔曼滤波技术，可建立飞行冲突的预测模型。将有人机的状态记为Xk，表示时刻k时的状态，此状态矢量可表示为：

有人机的状态转移矩阵为：

T为采样间隔。

由于受到风、驾驶员人为因素或发动机不规则短期推力的影响，飞机会受到一定的扰动，可表示为：

由此可建立航空器的状态转移方程：

其中：

根据无人机接收到的ADS-B信息，可建立观测方程：

观测矩阵为：

根据ADS-B设备的工作原理，当无人机第1次接收到周围某架航空器的位置报时，则开始建立该航空器的航迹，并将该航空器的初始位置记为，但此时只有二维位置的估计，没有速度的估计。当第2次接收到位置报，记为，则可利用这两次观测的信息进行滤波估值的计算［12］。具体步骤如下：

①用z1，2和z2，2直接作为x轴方向和y轴方向的估计xˆ1，2和xˆ3，2，再利用Z1与Z2对x2，2和x4，2进行估计，则有：

②再进行预测协方差矩阵P2的计算，由于

则有：

可求得：

由此，即可根据卡尔曼滤波的基本方程进行递推计算［13］。

对周围航空器的一步预测方程为：

状态估计方程为：

滤波增益为：

一步预测协方差为：

滤波协方差为：

其中Q和R分别为Wk和Vk的协方差矩阵。

因此，在无人机收取到最初连续的两个ADS-B信息报文后即可对航空器进行当前航行状态的估计计算，通过一定时间步长内的趋势预推，实现冲突预测的目的。

3.3基于路径规划的飞行冲突解脱原理

由于空域的态势信息具有很强的不定性，飞行冲突的发生与解脱是一个动态的过程，需要无人机基于当前的态势信息不断更新航路，最终实现对潜在飞行冲突的避让。因此，对周围航空器的观测与路径的重规划需要交替循环进行。在每一次观测之后，无人机对周围航空器进行一次趋势预推，将当前的预测位置当作该时刻的静态威胁进行避让。无人机的当前位置成为路径规划的起点，终点位置不变，路径重规划的信息成为无人机避让决策的结果信息，传送至飞行控制系统进行单步避让控制（冲突解脱算法流程如图7所示）。

图7　冲突解脱算法流程

4　仿真验证

本文在PC机上利用Matlab2008b对算法模型进行仿真验证。首先在一个100km×100km的范围内构造无人机的空域运行环境（空域结构如图8所示）。图中红色的为空中禁区，用F表示；紫色的为危险区，用D表示；浅蓝色的为正在使用的训练空域，用T表示；Start为路径起点，Goal为终点。

图8　空域结构

对改进蚁群算法的参数设定如表1所示。

表1　改进蚁群算法的参数设置

首先验证无人机在没有动态威胁情况下的路径规划能力，无人机应当在避开所有空域威胁的情况下，尽可能以精简的路径到达目标点。本文对利用基本蚁群算法、未进行空间分割的改进蚁群算法与基于空间分割的改进蚁群算法分别进行规划试验，并进行对比分析，规划结果如下页图9所示。

在利用基本蚁群算法进行路径规划的过程中，最后得到的解不但路径冗余度高，有时甚至会出现绕行的现象，总体效果较差，如图9（a）所示。在引入了最大最小蚂蚁系统与基于排序的蚂蚁系统后，路径冗余度得到了明显的降低，如图9（b）所示。但在部分节点上依然存在不必要的转弯路径，无人机如果沿着这样的路径飞行，会对无人机的任务执行效率与飞行稳定性产生负面影响。在引入了基于空间分割的蚁群算法后，路径的冗余度得到了再次降低（图9（c）所示），且路径具有更好的可飞行性。

图9　基于不同算法的路径对比

在无人机的空域运行过程中，每隔时间T，根据ADS-B信息对周围航空器进行一次滤波估计，利用得出的估计信息对3T之后的运行态势进行趋势预推，根据航路规划的决策信息进行时长为T的冲突避让机动。在仿真试验中，T=10 s，并加入两架与无人机在同高度飞行且存在飞行冲突的航空器，冲突避让过程如图10所示。

图10　飞行冲突避让过程

从图10中可以看出，无人机可以很好地进行飞行冲突的解脱，始终保持与其他航空器间10 km的距离，并顺利到达目标点。从路径的精简性来看，在路径的不断更新过程中也保持了较低的冗余度，可以为无人机的避让机动提供可靠的决策支撑。

基于空间分割的改进蚁群算法本质上是一种利用时间换取质量的路径规划方法，但论文提出的方法已经能够满足无人机路径规划对实时性提出的要求。在基于基本蚁群算法的路径规划中，静态环境下平均用时为0.4367s，使用以往改进蚁群算法的静态路径规划仿真试验中，单次路径规划平均用时为0.2225s，而基于空间分割的改进蚁群算法平均用时略大，为0.4953s。

无人机动态路径规划的用时与空间大小、空域结构复杂度及无人机与目标点的位置有较大关联，在路径规划的初始阶段往往要花费较多时间，而在运行后期，随着无人机距离目标点越来越近，则用时越来越少。本文设计的冲突解脱方案在初始阶段路径规划单步决策用时最长，而后不断递减，时间变化曲线如图11所示。中间之所以出现阶跃性降低是因为在路径剩余步长小于30的情况下，规划空间已经大大缩小，因此，不再使用基于空间分割的改进蚁群算法。

图11　动态路径规划时间消耗变化趋势

相比有人机的冲突避让过程，从飞行员发现冲突，到做出冲突避让的决策，直至进行飞行控制使航空器开始改变飞行姿态进行飞行冲突避让，平均用时为10 s～12.5 s［1］，无人机进行飞行决策的用时完全可以满足冲突避让机动的需要。

5　结论

为提高无人机的空域运行能力，本文以路径规划入手，设计了用于无人机巡航阶段飞行冲突解脱的技术方案，通过仿真实验可得出：①在动态路径规划问题中，基于正三角形栅格的规划空间比传统的十字栅格具有更好的时间同步性，规划得出的路径符合无人机巡航阶段速度相对稳定的特征。②基于空间分割的改进蚁群算法能有效去除飞行路径中的冗余路径，提高路径的可飞性，通过实时的路径重规划原理，可以为无人机空域运行的冲突解脱提供很好的避让决策支撑。③基于ADS-B信息的冲突感知方案可以应用于无人机的空域运行，通过滤波处理能够为无人机的冲突感知提供充足的信息支撑。在冲突感知的基础上，本文提出的冲突解脱方案可以实现无人机对空域中各类静态威胁源的规避与动态飞行冲突的解脱，可对未来无人机的空域运行安全技术提供理论参考。

［1］李春锦，文泾.无人机系统的运行管理［M］.北京：北京航空航天大学出版社，2011.

［2］蔡志浩，杨丽曼，王英勋，等.无人机全空域飞行影响因素分析［J］.北京航空航天大学学报，2011，37（2）：175-179.

［3］Departmentof Defense.Unmannedsystemintegratedroadmap FY2013～2038［R］.Washington，DC：Department of Defense，2013.

［4］U.S.Department of Transportation，Federal AviationAdministration.Integration of civil unmanned aircraft systems（UAS）inthenational airspacesystem（NAS）roadmap［R］，Washington，DC：U.S.DepartmentofTransportation，2013.

［5］HENDRICSON Adam.Aninvestigationof alertingandprioritization criteria for sense and avoid［R］.Washington，DC：Technical Management DirectorateAviation and Missile Research，Development，andEngineeringCenter，2013.

［6］EVACRüCK，JOHN L.Senseandavoidsystemfor aMALE UAV［C］//Guidance，Navigation and Control Conference and Exhibit，South Carolina：American Institute of Aeronautics andAstronautics，2007.

［7］张兆宁，王莉莉，李冬宾.飞行间隔安全评估引论［M］.北京：科学出版社，2009.

［8］宋锦娟.一种改进的蚁群算法及其在最短路径问题中的应用［D］.太原：中北大学，2013.

［9］吴虎发.蚁群优化算法在求解最短路径问题中的研究与应用［D］.合肥：安徽大学，2012.

［10］高尚，杨静宇.群智能算法及其应用［M］.北京：中国水利水电出版社，2006.

［11］张军.现代空中交通管理［M］.北京：北京航空航天大学出版社，2005.

［12］闫丽萍，夏元清，杨毅.随机过程理论及其在自动控制中的应用［M］.北京：国防工业出版社，2012.

［13］王社伟，梁国伟，陶军.基于马尔可夫模型的无人机路径规划的线性化［J］.四川兵工学报，2015，36（1）:95-98.

［14］秦永元，张洪钺，汪叔华.卡尔曼滤波与组合导航原理［M］.西安：西北工业大学出版社，2012.

UAV Flight Conflict Resolution Technology Based on Path Planning

WEI Xiao-long，YAODeng-kai，DAI Zhe，HANQi-song
（School of Air Traffic Control and Navigation，Air Force Engineering University，Xi’an 710051，China）

When the UAV and manned aircraft operating in the same airspace，flight conflicts may occur at any time.It is important for UAV to find a reliable flight conflict resolution technology to ensure the operation safety.Therefor，a grid airspace environment based on regular triangle is constructed，which mends the shortage that cross grid environment not suitable for dynamic path planning.The principle of space partition is introduced to enhance the optimization performance of ant colony algorithm and improve the path planning ability effectively.Combining with the operation principle of ADS-B system，and in the bases of revised ADS-B information according to the theory of Kalman filtering，the technical plan of conflict sense is designed.Based on the technology of real-time path re-planning，UAV’s flight conflict resolution could be achieved finally.Simulation results demonstrate the validity of the conflict resolution technology，and could support the theory reference for UAV’s airspace operation technology in the future.

UAV，antcolonyalgorithm，pathplanning，ADS-B，conflictresolution

V249

A

1002-0640（2016）10-0048-07

2015-08-17

2015-09-16

国家空管科研基金资助项目（GKG201410005）

魏潇龙（1989-），男，浙江嵊州人，硕士研究生。研究方向：空域规划和空中交通流量管理。