带定位误差约束的多无人机快速协同航迹规划

顾 伟，吴 靖，李 晟，赵啸宇

(1. 中国人民解放军第31113部队，江苏 南京210018；2. 军事科学院国防科技创新研究院，北京 100091)

1 引言

近年来，无人机由于具有环境要求低、操作简单不易出错、灵活可靠成本低等特点，在各领域都获得了广泛应用[1]。但随着任务环境越来越复杂、任务要求越来越高，单个无人机的有限容量已经不能够满足日益复杂的任务需求，利用多无人机协同执行任务成为了重要发展趋势。特别是在军事应用中，利用多架无人机协同执行侦察、定位、打击等任务，可以有效提高任务完成质效，确保战场优势[2，3]。

文献[4]研究了多无人机协同覆盖航迹规划问题，利用几何方法进行了求解。文献[5]研究了在多无人机的任务执行能力、能源资源和所受威胁等约束下的多无人机协同任务规划问题，采用改进的遗传算法进行求解。文献[6]以无人机的飞行总航程、攻击目标收益、完成任务时间和执行任务时的威胁代价为子目标函数，然后将多目标规划问题转化为单目标规划，运用改进的遗传算法进行求解。文献[7]利用几何运动模型研究了多无人机对组网雷达的协同干扰问题。文献[8]引入位置、速度和航向作为协同变量，设计了具有线性混合器的编队保持控制器，实现了编队队形的精确保持。文献[9]利用多无人机与目标之间的距离，实现了目标位置估算。

学者们针对不同的应用场景进行了研究，考虑了很多不同的约束条件，包括无人机的转弯半径约束、障碍物约束等，但是对实际广泛存在的定位误差约束的研究比较少。在战场环境中，定位误差的存在将极大影响任务完成质量，甚至会直接导致任务失败。本文重点研究在定位存在误差情况下的多无人机协同航迹规划问题。

2 问题描述

2.1 打击问题

对敌方某一军事目标进行打击摧毁，要求位于目标附近的几架无人机快速实施打击任务。为保证打击效果及避免提前暴露，需要所有无人机同时(在较小时间差内)到达目标位置并执行打击。已知，受限于系统结构限制，无人机的定位系统无法对自身进行精准定位，并且误差将累积。而当定位误差积累到一定程度，将偏离预定航线，导致任务失败。因此，无人机在飞行过程中需要对定位误差进行校正。

2.2 约束分析

以一架无人机为例，无人机的出发点为A点，目标点为B点。其在飞行中受到约束如下：

1)无人机在飞行时存在定位误差，包括垂直误差和水平误差。无人机每飞行1m，垂直误差和水平误差各增加δ个单位。为保证打击的精准性，要求无人机在到达目标点B时垂直误差和水平误差均应小于θ个单位。为简化问题，假设当垂直误差和水平误差均小于θ个单位时，无人机仍能够按照规划路径飞行；

2)无人机在飞行过程中需要对定位误差进行校正。飞行区域中存在一些已知校正点(如图1，绿的点为水平误差校正点，蓝色的点为垂直误差校正点)，当无人机到达校正点即能够根据该位置的误差校正类型进行误差校正。若垂直误差、水平误差都能得到及时校正，则飞行器可以按照预定航线飞行，通过若干个校正点进行误差校正后最终到达目的地；

3)在出发地A点，飞行器的垂直和水平误差均为0；

4)飞行器在垂直误差校正点进行垂直误差校正后，其垂直误差将变为0，水平误差保持不变；

5)飞行器在水平误差校正点进行水平误差校正后，其水平误差将变为0，垂直误差保持不变；

6)当飞行器的垂直误差不大于α1个单位，水平误差不大于α2个单位时才能进行垂直误差校正；

7)当飞行器的垂直误差不大于β1个单位，水平误差不大于β2个单位时才能进行水平误差校正；

8)无人机的最小转弯半径为200m。

图1 单架无人机飞行区域示意图

3 模型建立

3.1 启发式数据处理

由于必须经过校正点，因此这是一个离散空间搜索问题。首先计算任意两点间的距离，由于无人机存在转弯半径约束，无法瞬间改变速度方向，因此计算任意两点间的最短距离时必须同时考虑无人机的速度方向。为了便于模型建立和计算，引入启发式，无人机在各点的方向均指向目标点。

在二维平面上，Dubins[10]几何地给出了固定初始和最终位置及速度方向的光滑最短路径。针对问题中带曲率的三维最短路径，SikhaHota[11]给出了在给定初始和最终构型参数的情况下，若两点间距足够远(距离大于四倍曲率半径)，在给定曲率约束下，计算三维空间中的最优路径的方法。运用该方法对离散点数据进行预处理。

表1 符号说明

3.2 规划模型

3.2.1 符号说明

3.2.2 混合整数规划模型

根据题目中的优化目标和约束要求，建立如下航迹规划的混合混合整数规划模型：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

M(1-xkij)+Δxkj≥δdij+Δxki·li，∀k，i，j

(8)

M(1-xkij)+Δykj≥δdij+Δyki·(1-li)，∀k，i，j

(9)

Δxki≤α2，i∈V，∀k

(10)

Δyki≤α1，i∈V，∀k

(11)

Δxki≤β2，i∈L，∀k

(12)

Δyki≤β1，i∈L，∀k

(13)

Δxkn≤θ，i∈L，∀k

(14)

Δykn≤θ，i∈L，∀k

(15)

(16)

penalty≥0

(17)

其中，式(1)表示最小化所有无人机航迹长度之和。式(2)和(3)表示每个点最多只能经过一次，点本身不存在边，即无人机不能在一个点上绕圈。约束(4)要求除出发点和终点外，航迹要实现节点的流平衡，即进入该节点的次数等于出于该节点的次数。约束(5)、(6)和(7)要求无人机必须从出发点出发，最终在终点停止，并且不能从终点飞往其它节点。约束(8)和(9)为无人机误差传递约束，无人机在一个节点的水平和垂直误差等于前一个节点校正后误差加上从前一节点到本节点的飞行距离造成的误差之和，当上一个节点为水平误差校正点时，校正后水平误差变为0，垂直误差不变。当上一个节点为垂直误差校正点时，校正后垂直误差变为0，水平误差不变。约束(10)至(15)要求飞行器在垂直误差校正点、水平误差校正点和终点要小于允许的垂直误差和水平误差最大值。约束(16)表示所有无人机轨迹长度要尽可能平均，即与平均值的差的绝对值之和不能超过参数γ。式(17)中penalty是为了便于模型求解引入的惩罚因子。在目标函数(1)中，只有当惩罚因子penalty为零时才能取到最优值。

直观的目标应该是几条航迹中的最大值最小，而本模型是几条航迹之和最小。一方面是因为这样便于模型求解，航迹最大值最小是一个非线性问题，不符合快速航迹规划的要求。另一方面，约束是航迹差较小，极端情况航迹差为零时，航迹和最小和航迹最大值最小是等价的，因此当航迹差较小时，两者差别在可接受范围之内。同理，在航迹差约束的表达上，理论上是最长航迹减最短航迹的差小于一个参数，而本模型实际采用了与平均值差的绝对值之和小于一个参数。采用以上两个替换实现了在建模时提高模型的可解性。利用惩罚因子penalty，将约束放到目标函数中进行考虑实现了在模型求解时提高模型的可解性。

综合以上手段可以实现模型的快速求解，从而达到快速航迹规划的目的。

4 实验分析

4.1 实验参数

校正点位置数据采用2019年中国研究生数学建模竞赛F题(单无人机航迹规划)附件二。原始数据如表2，基于三维Dubins曲线数据预处理(假定每个点的方向均指向目标点)后收据如表3所示。

表2 原始数据

表3 预处理后数据

实验采用JAVA语言调用CPLEX的API进行航迹规划混合整数规划模型求解。在配置为CORE i7 8550U，主频2.0GHZ，8GB内存的电脑上，运行时间均为300s。其它实验参数如表4所示。

表4 实验参数

4.2 实验结果及分析

4.2.1 无人机初始位置的影响实验

设置3架无人机分别从点0，点2，点48出发，前往点326。无人机1的航迹为：0-184-163-114-8-309-305-123-45-160-92-93-61-292-326，航迹长110140.79；无人机2的航迹为：2-40-290-209-8-309-121-123-45-160-191-92-93-61-292-326，航迹长110126.97。无人机3的航迹为：48-56-58-8-309-305-123-45-160-191-92-93-61-292-326，航迹长110127.25。航迹间最大差值为13.82。

图2 三架无人机实验结果(0、2、48出发)

图3 两点之间航迹示意图

图2的结果图由于比例原因(转弯半径相对地图空间太小)，看不到无人机转弯，随机找两个点，中间航迹如图3所示。任意两点之间的航迹均由切出弧、弧切线和切入弧构成。

图4 中间航迹点切入弧与切出弧相接示意图

对于每个中间航迹点都是两个圆弧的交点，图4显示了半径为200的辅助圆。

设置3架无人机分别从点23，点102，点152出发，前往点326。无人机1的航迹为：23-26-206-3-281-197-112-151-190-108-168-115-160-92-93-61-292-326，航迹长140564.83。无人机2的航迹为：102-26-206-3-281-197-112-296-205-171-168-115-160-92-93-61-292-326，航迹长140544.29。无人机3的航迹为：152-23-26-206-3-281-197-112-151-190-108-168-115-160-92-93-61-292-326，航迹长140561.28。航迹间最大差值为20.54。

图5 三架无人机实验结果(23、102、152出发)

设置3架无人机分别从点0，点1，点2出发，前往点326。无人机1的航迹为：0-163-114-8-309-305-123-45-160-92-93-61-292-326，航迹长109405.51。无人机2的航迹为1-200-122-316-98-76-6-12-216-279-302-161-326，航迹长109408.27。无人机3的航迹为2-56-290-158-8-309-305-123-231-160-92-93-61-292-326，航迹长109389.22。航迹间最大差值为19.05，实际运行时间91秒。

图6 三架无人机实验结果(0、1、2出发)

上述3个实验表明：1)无人机初始位置会影响航迹的长度；2)本模型可以在较短时间内为任意起点的三架无人机规划出满足约束条件的协同航迹。

4.2.2 无人机数量的影响实验

在三架无人机的航迹规划实验中，前两个运行300秒获得了可行解(惩罚因子penalty为0的解)，第三个实际运行91秒，得到了最优解。初始位置会对求解速度有影响，但是并不是问题规模的决定因素。从理论上可以分析出，问题规模(搜索空间)将随无人机的增加而大大增长。下面对无人机的数量对模型实际求解时间进行分析，以验证理论上的结论。对于航迹差参数γ，取每架无人机航迹长度到平均值的差值为10。

初始分别设置5架、7架、10架无人机，设置不同运行时间，获得几次结果如表6所示。

表6 实验结果

五架无人机在运行300秒时无法获得可行解，运行500秒才能获得可行解，说明问题规模确实会随着无人机数量的增加而增加。五架无人机运行500秒获得可行解，七架无人机运行1000秒获得可行解，十架运行2000秒才能获得可行解，说明问题规模的增长并不是呈线性的。当然，可行解并不是唯一确定的，选取的运行时间也都是间隔很大的离散点，并不能算是严格证明，但是也足够表明问题规模随无人机的数量增加而大大增加。

5 总结展望

本文模型可用于解决多无人机在多约束条件下的时序到达问题。存在的不足是，首先在数据预处理时，引入三维Dubins曲线，精确解得因转弯造成的航迹变化。但是三维Dubins曲线的入射速度方向与出射速度方向应该均为决策变量，为简化计算量，提升求解效率，本文假设了速度方向均朝向终点方向，在以后的研究中可以进一步考虑无人机速度方向的影响。其次，本文采用了数学规划方法，数学规划方法始终存在着无法解决大规模问题的局限性。总体而言，本章提出的多无人机在多约束条件下的协同航迹快速生成模型可以用于较少无人机协同打击时飞行的合理安全以及任务执行的高效稳定。

表7 五架无人机实验结果

表8 七架无人机实验结果

表9 十架无人机实验结果