付其喜1,2,梁晓龙1,张佳强1,侯岳奇1
(1.陕西省电子信息系统综合集成重点实验室(空军工程大学),西安 710051; 2.中国人民解放军94582部队,河南 驻马店 463200)
摘要:
为解决多无人机基于航向的合作式短期冲突探测与解脱问题,提出一种局部集中双层优化的合作式方法.首先将既有冲突约束与潜在冲突约束视为同一类型约束,以保证多无人机冲突问题在最大范围内求解,并设计了基于采样的冲突探测方法；通过旋转局部坐标系减少了搜索的可行区域数量,且分析了终点约束与切线约束两种解脱约束条件；然后运用图论的方法对多无人机冲突问题进行冲突关系划分,将由机动导致的无人机额外飞行距离作为解脱代价设计了机动代价函数,为求解所设计的机动代价函数这个非线性优化问题提出了双层优化策略,即先利用随机并行梯度下降法(stochastic parallel gradient descent,SPGD)搜索航向解脱的初始可行解,再运用序列二次规划(sequential quadratic programming,SQP)求得最优解以进行最优的航向解脱. 最后运用蒙特卡洛法对算法进行了可靠性评价.结果表明,本方法能够满足在线规划的需要,在解脱开始距离Davo=τ×vi（τ=25 s）的情况下能够实现100%的冲突解脱,该方法能够在保证多无人机冲突解脱安全性的基础上减少机动消耗.
关键词: 无人机 冲突解脱 双层优化 随机并行梯度下降法 序列二次规划 蒙特卡洛法
DOI：10.11918/201808108
分类号:V249.1,TP29
文献标识码:A
基金项目:国家自然科学基金(7,3)； 陕西省自然科学基础研究计划(2017JQ6035)
Cooperative conflict detection and resolution for multiple UAVs using two-layer optimization
FU Qixi1,2,LIANG Xiaolong1,ZHANG Jiaqiang1,HOU Yueqi1
(1.Shaanxi Province Lab of Meta-synthesis for Electronic & Information System (Air Force Engineering University), Xi’an 710051, China; 2.Unit 94582 of PLA, Zhumadian 463200, Henan, China)
Abstract:
Aiming at the problem of cooperative collision detection and resolution of multi-UAVs by heading control, this paper proposes a local centralized two-layer optimization method. First, the practical conflict constraints and the potential conflict constraints are regarded as the same type of constraints to ensure that the multi-UAV conflict problem can be solved in great degree. The method of conflict detection based on sampling is designed, and the number of searching feasible regions is reduced by rotating local coordinate system, and two kinds of constraint conditions, including the terminal point constraint and the tangential constraint, are analyzed. Then, the conflict relation of multi-UAV conflict problem is divided by graph theory, and the additional flight distance caused by maneuver is taken as the cost of resolution to design the maneuver cost function. In order to solve the non-linear optimization problem of the designed maneuvering cost function, a two-layer optimization strategy is proposed. The initial feasible solution is firstly searched by Stochastic Parallel Gradient Descent (SPGD), and then the optimal solution is obtained by using Sequential Quadratic Programming (SQP). Finally, Monte Carlo method is used to evaluate the reliability of the algorithm. The simulation results show that this method can satisfy the need of online planning and can achieve 100% conflict resolution under the condition of conflict start distance Davo=τ×vi(τ=25 s). This method can reduce the maneuvering consumption on the basis of ensuring the security of multi-UAV conflict resolution.
Key words: UAVs collision detection and resolution two-layer optimization SPGD SQP Monte Carlo simulation
付其喜, 梁晓龙, 张佳强, 侯岳奇. 双层优化的多无人机合作式冲突探测与解脱[J]. 哈尔滨工业大学学报, 2020, 52(4): 74-83. DOI: 10.11918/201808108.
FU Qixi, LIANG Xiaolong, ZHANG Jiaqiang, HOU Yueqi. Cooperative conflict detection and resolution for multiple UAVs using two-layer optimization[J]. Journal of Harbin Institute of Technology, 2020, 52(4): 74-83. DOI: 10.11918/201808108.
基金项目 国家自然科学基金(61703427, 61472443);陕西省自然科学基础研究计划(2017JQ6035) 作者简介 付其喜(1994—), 男, 硕士 通信作者 梁晓龙, afeu_lxl@sina.com 文章历史 收稿日期: 2018-08-22
Abstract Full text Figures/Tables PDF
双层优化的多无人机合作式冲突探测与解脱
付其喜1,2, 梁晓龙1
, 张佳强1, 侯岳奇1 1. 陕西省电子信息系统综合集成重点实验室(空军工程大学), 西安 710051;
2. 中国人民解放军94582部队, 河南 驻马店 463200
收稿日期: 2018-08-22
基金项目: 国家自然科学基金(61703427, 61472443);陕西省自然科学基础研究计划(2017JQ6035)
作者简介: 付其喜(1994—), 男, 硕士
通信作者: 梁晓龙, afeu_lxl@sina.com
摘要: 为解决多无人机基于航向的合作式短期冲突探测与解脱问题, 提出一种局部集中双层优化的合作式方法.首先将既有冲突约束与潜在冲突约束视为同一类型约束, 以保证多无人机冲突问题在最大范围内求解, 并设计了基于采样的冲突探测方法; 通过旋转局部坐标系减少了搜索的可行区域数量, 且分析了终点约束与切线约束两种解脱约束条件; 然后运用图论的方法对多无人机冲突问题进行冲突关系划分, 将由机动导致的无人机额外飞行距离作为解脱代价设计了机动代价函数, 为求解所设计的机动代价函数这个非线性优化问题提出了双层优化策略, 即先利用随机并行梯度下降法(stochastic parallel gradient descent, SPGD)搜索航向解脱的初始可行解, 再运用序列二次规划(sequential quadratic programming, SQP)求得最优解以进行最优的航向解脱.最后运用蒙特卡洛法对算法进行了可靠性评价.结果表明, 本方法能够满足在线规划的需要, 在解脱开始距离Davo=τ×vi(τ=25 s)的情况下能够实现100%的冲突解脱, 该方法能够在保证多无人机冲突解脱安全性的基础上减少机动消耗.
关键词: 无人机 冲突解脱 双层优化 随机并行梯度下降法 序列二次规划 蒙特卡洛法
Cooperative conflict detection and resolution for multiple UAVs using two-layer optimization
FU Qixi1,2, LIANG Xiaolong1
, ZHANG Jiaqiang1, HOU Yueqi1 1. Shaanxi Province Lab of Meta-synthesis for Electronic & Information System (Air Force Engineering University), Xi'an 710051, China;
2. Unit 94582 of PLA, Zhumadian 463200, Henan, China
Abstract: Aiming at the problem of cooperative collision detection and resolution of multi-UAVs by heading control, this paper proposes a local centralized two-layer optimization method. First, the practical conflict constraints and the potential conflict constraints are regarded as the same type of constraints to ensure that the multi-UAV conflict problem can be solved in great degree. The method of conflict detection based on sampling is designed, and the number of searching feasible regions is reduced by rotating local coordinate system, and two kinds of constraint conditions, including the terminal point constraint and the tangential constraint, are analyzed. Then, the conflict relation of multi-UAV conflict problem is divided by graph theory, and the additional flight distance caused by maneuver is taken as the cost of resolution to design the maneuver cost function. In order to solve the non-linear optimization problem of the designed maneuvering cost function, a two-layer optimization strategy is proposed. The initial feasible solution is firstly searched by Stochastic Parallel Gradient Descent (SPGD), and then the optimal solution is obtained by using Sequential Quadratic Programming (SQP). Finally, Monte Carlo method is used to evaluate the reliability of the algorithm. The simulation results show that this method can satisfy the need of online planning and can achieve 100% conflict resolution under the condition of conflict start distance Davo=τ×vi(τ=25 s). This method can reduce the maneuvering consumption on the basis of ensuring the security of multi-UAV conflict resolution.
Keywords: UAVs collision detection and resolution two-layer optimization SPGD SQP Monte Carlo simulation
无人机(unmanned aerial vehicle, UAV)在基础设施监测、货物运输、精准农业和搜索营救等方面得到了广泛应用[1].随着应用的不断拓展, 无人机在非隔离空域中运行的需求日益增加[2].无人机在非隔离空域中一旦发生空中相撞事故将酿成灾难性的后果, 所以冲突解脱问题成为亟待研究的重点[3].
无人机的短期冲突解脱在未来的无人机交通管理系统(unmanned aircraft systems traffic management, UTM)中具有重要地位.文献[4]提出了导航函数法, 既考虑了安全间隔又兼顾了预先规划的航路点, 但是会产生过多额外的飞行距离.文献[5-9]提出并完善了一种双向的分布式优化冲突解脱算法.它的基本思想是冲突双方在解脱过程中处于平等的地位, 共同负责完成冲突解脱机动.文献[10]提出了一种选择性速度障碍法, 在速度障碍法中借鉴了有人机的目视飞行规则.该方法能够实现有人机/无人机空域飞行规则的兼容, 但由于在某些空中态势下冲突双方只有一方负责机动, 所以容易产生兜圈的情况, 造成了额外的解脱机动消耗.文献[11]提出了一种将集中式优化和双向冲突解脱结合的方法.文献[12-13]拓展和改进了改变速度策略解脱模型, 在冲突解脱过程中将非线性航迹考虑在内, 并可以通过线性方程来完成解脱方案求解.但方法采用集中式优化, 无人机通常采用分布式在线冲突探测与解脱.
本文在无人机双向分布式优化的基础上, 提出了一种双层优化的合作式分布冲突解脱的方法.首先分析了无人机的冲突解脱模型, 提出了一种基于采样的冲突探测算法, 然后考虑了无人机的运动约束条件(运动约束包括飞行包线约束、转弯角度约束和角速度约束等)及无人机的机动消耗, 针对多无人机冲突解脱提出了一种双层优化的冲突解脱算法与对应求解过程.最后运用蒙特卡洛法验证了运用双层优化算法进行冲突解脱的安全性.仿真结果表明, 该方法能够实现多无人机的双向解脱机动和分布式优化, 在保证冲突解脱安全性的基础上减少了解脱机动消耗.
1 冲突解脱模型 1.1 无人机几何模型Dsi(pi, ri), i∈N为无人机Ai在二维空间的保护区, 即
${D_{{\rm{si}}}}\left( {{p_i},{r_i}} \right) = \left\{ {p\left\| {{p_x} - {x_i},{p_y} - {y_i}} \right\| < {r_i}} \right\}.$
式中：i为无人机编号; pi=(xi, yi)为Ai的坐标; N为无人机的数量; ri为Ai保护区半径.
本文采用的无人机运动方程为：
${{\dot p}_i}\left( t \right) = \left\{ {\begin{array}{*{20}{l}}{{v_i}\left( t \right)\cos {\varphi _i}\left( t \right),}\\{{v_i}\left( t \right)\sin {\varphi _i}\left( t \right),}\end{array}} \right.$
${{\dot \varphi }_i}\left( t \right) = w\left( t \right),$
$0 < {\varphi _i}\left( t \right) < 2{\rm{ \mathsf{ π} }}{\rm{.}}$
式中:φi(t)、vi(t)、w(t)分别为Ai的航向、速度及角速度.假定无人机在解脱过程中速度大小不变, 无人机Ai的状态为：(xi, yi, φi, vi, wi), 其中wmaxi≥wi(t)≥－wmaxi.Ai在有限的时间前瞻量τ(以下简称前瞻时间τ)内以一定的可调整角度φi调整航向以确保相互之间的安全间隔.可调整角度φi表示Ai在前瞻时间τ内航向改变角与位移偏角均为φi.本文通过Dubins[14]曲线得到Ai最大可调整角度φmaxi(τ), φi满足：
${\varphi _i} \le \varphi _{\max }^i\left( \tau \right),\forall i \in N.$
1.2 冲突解脱几何关系本文通过建立局部坐标系来分析无人机的冲突关系, 如图 1(a)所示, 以Aj的当前位置为原点建立局部坐标系.则Ai在t=0时的坐标为
Fig. 1
图 1 两机速度障碍示意 Fig. 1 Schematic diagram of the speed obstacle of the two UAVs ${P_i}\left( 0 \right) = \left( {{x_i}\left( 0 \right) - {x_j}\left( 0 \right),{y_i}\left( 0 \right) - {y_j}\left( 0 \right)} \right).$
假设Ai是静止的, 则Aj相对于Ai的速度为
${v_{ji}}\left( t \right) = \left( {{{\dot x}_j}\left( t \right) - {{\dot x}_i}\left( t \right),{{\dot y}_j}\left( t \right) - {{\dot y}_i}\left( t \right)} \right).$
本文采用速度障碍法[4]描述冲突解脱问题.速度障碍VOj|it是指在[0~τ]时间段内造成Aj与Ai冲突的vji的集合, 如图 1(a)所示.VOj|it定义为
$VO_{j|i}^t = \left\{ {{v_{ji}}|\exists t \in \left[ {0,\tau } \right]::t{v_{ji}} \in {D_{ij}}\left( {{P_i}\left( 0 \right),r_{\rm{s}}^{ij}} \right)} \right\},$
式中, Dij为Aj与Ai的复合保护区, 且rsij=max(ri, rj).若vji在VOj|it内, 则Aj与Ai发生了冲突, 否则就没有冲突.因此, 冲突解脱就是调整vi与vj使得vji不在VOj|it内.
为了分析无人机位移之间的关系, 本文根据速度、位移与时间的关系将速度坐标系转换成位移坐标系, 如图 1(b)所示.Aj与Ai在τ内的相对位移为Lji=Lj-Li, 其中Lj、Li分别为Aj与Ai在τ内的位移, Lj、Li在线规划过程中视为直线.Lji在Aj与Ai进行解脱机动后改变为L′ji, 而L′ji应位于Dij之外.
2 冲突探测 2.1 无人机态势应用速度障碍模型只能判断一对无人机在前瞻时间τ内是否发生冲突.即使两个无人机的当前相对速度vji不在由它们的当前状态所构成的速度障碍VOj|iτ中, 也有可能会由于不当的速度调整使vji进入速度障碍中.由于无人机在一定时间范围内可机动范围有限, 因此不是所有相互临近的无人机都可能在前瞻时间τ内发生冲突.因此需要对相互临近的无人机之间的关系进行分析.
图 2中阴影区域为无人机在[0~τ]时间内的可达区域.临近无人机在[0~τ]时间内存在3种态势.图 2(a)为两机处于安全态势, 在前瞻时间τ内不会发生冲突, 图 2(b)为两机已经有冲突存在, 图 2(c)为两机在前瞻时间τ内若进行不合适的机动就会存在冲突的可能.本文将图 2(b)、图 2(c)分别定义为既有冲突与潜在冲突.在多无人机的冲突解脱过程中, 若只考虑既有冲突, 则无人机在进行解脱机动时仍会与其他存在潜在冲突的无人机发生冲突, 因此本文将潜在冲突与既有冲突均视为存在冲突危险, 用crij表示为
Fig. 2
图 2 临近无人机的3种态势 Fig. 2 Three situations of adjacent unmanned aerial vehicles $c{r_{ij}} = \left\{ \begin{array}{l}1,{A_i}\;与\;{A_j}\;存在既有冲突或潜在冲突;\\0,其他.\end{array} \right.$
为了避免诱发冲突的出现, 本文将既有冲突约束与潜在冲突约束视为同一类型约束, 这样能够保证多无人机冲突问题在最大范围内求解.
2.2 冲突探测算法冲突探测算法一般只考虑既有冲突[15-16], 双层优化算法根据无人机状态, 通过采样进行冲突探测.首先基于位移矢量Lji与前瞻时间τ在无人机的飞行路径上进行预测采样, 再根据采样值及无人机位置构建空间区域, 最后判断被检测无人机与所构建的空间区域的关系即能进行冲突探测.
二维空间内无人机冲突检测步骤如下.
Step1??根据无人机Ai与Aj当前的状态以及它们在前瞻时间τ内可机动的角度或速度范围采样在τ时刻相对位移Lji到达的终点散布区域, 如图 3所示的蓝色散布点.
Fig. 3
图 3 冲突探测示意 Fig. 3 Schematic diagram of conflict detection Step2??根据无人机Ai与Aj的初始速度和运动方向获得Aj的初始相对速度vji.得到vji与正向X坐标轴之间的夹角σji, 将坐标系XOY旋转σji.所有采样点的坐标点在新的坐标系中关于X轴对称.得到采样点集的极值xmax、xmin、ymax、ymin.根据极值点构建一个包含所有终点的矩形区域, 将其定义为终点区域, 如图 3中的黑色矩形框包围的区域.
Step3??综合考虑Aj相对位移的终点区域以及无人机之间的安全间隔rsij, 将终点区域向外扩展, 得到形状为圆角矩形的终点影响区域.为了简化求解将圆角矩形简化为直角矩形区域, 如图 3所示.Aj的安全区域为圆形区域.
Step4??根据冲突的定义, Aj在τ时间段内运动的过程中如果与Ai的距离小于rsij, 则说明两个无人机之间存在冲突, 因此从Aj的安全区域到终点区域的所有连线都是Aj的飞行过程影响区域.根据终点影响区域与Aj的安全区域可以确定Aj的飞行过程影响区域, 即由终点影响区域边界点到Aj安全区域的切线包裹的凸区域.
Step5??产生各类区域后算法采用分区域的方法检测冲突：首先检查Ai的坐标是否在终点影响区域中, 然后检查Ai的位置是否在飞行过程影响区域中.在检查飞行过程影响区域时首先检查Ai的坐标点是否在由终点影响区域边界点EA与EB到安全区域圆的切线的交点IAB与EA和EB构成的三角形内, 如果在三角形区域中, 需要考虑Ai在绿色非威胁区域内的误检测情况.
3 冲突解脱约束条件 3.1 解脱机动的约束条件如冲突解脱几何关系所述, L′ji在[0~τ]时间内应位于Dij之外, 将其归结为两个约束条件, 即终点约束与切线约束. Ai与Aj在t时刻的距离为
${d_{ij}}\left( {t,{\varphi _i},{\varphi _j}} \right) = \left\| {{P_i}\left( 0 \right) - {v_{ji}}t} \right\|,$
则无人机在τ的终点约束为
${d_{ij}}\left( {t,{\varphi _i},{\varphi _j}} \right) - r_s^{ij} \ge 0.$
切线约束为如果两无人机在[0~τ)时间内的最短距离为Pi(0)到L′ji所在直线的距离dijp, 则dijp应不小于rsij.
$d_{ij}^p\left( {{\varphi _i},{\varphi _j}} \right) = \left| { - {k_{ji}}{P_{ix}} + {P_{iy}}} \right|/\sqrt {1 + k_{ji}^2} .$
式中：kji为L′ji的斜率; Pix、Piy为Pi(0)的坐标.其中kji的表达式为
${k_{ji}}\left( {{\varphi _j},{\varphi _i}} \right) = \frac{{\sin \left( {{\phi _j} + {\varphi _j}} \right){v_j} - \sin \left( {{\phi _i} + {j_i}} \right){v_i}}}{{\cos \left( {{\phi _j} + {\varphi _j}} \right){v_j} - \cos \left( {{\phi _i} + {\varphi _i}} \right){v_i}}}.$
式中:kji为周期函数, 其定义域为[-π/2+kπ, π/2+kπ], k∈Z; vji的航向范围为H1=[-π/2, π/2]和H2=[π/2, 3π/2], 这是kji的两个不连续的周期.vji航向的可行区域如图 4所示.图 4(a)表示的是可行区域的第1种情况, 两个可行子区域分别位于kji的两个周期内.图 4(b)表示的是可行区域的第2种情况.本文采用旋转局部坐标系的方法将情况1转变为情况2, 如图 4(b)所示, 旋转之后P′ix=0且P′iy>0.
Fig. 4
图 4 vji航向的可行区域 Fig. 4 Feasible region of the heading of vji 冲突解脱的约束条件中, 终点约束能够保证无人机在解脱过程中进行尽量少的机动, 而切线约束能够保证无人机解脱机动的安全性.考虑到解脱的安全与效率, 不同的态势应该采用不同的约束条件.本文定义变量cvij来对约束条件进行选择：
$c_v^{ij} = {\left\| {{P_i}\left( 0 \right)} \right\|^2} - r_s^{ij2} - {\left( {{{\left\| {{S_i}} \right\|}_2} + {{\left\| {{S_j}} \right\|}_2}} \right)^2},$
式中cvij≥0为两无人机处于相对较远的距离, 这样就能将φi与φj的约束条件总结如下：
$g\left( {{\varphi _i},{\varphi _j}} \right) \ge r_{\rm{s}}^{ij},g\left( {{\varphi _i},{\varphi _j}} \right) = \left\{ {\begin{array}{*{20}{l}}{{d_{ij}}\left( {\tau ,{\varphi _i},{\varphi _j}} \right),{\rm{ if }}\;c_v^{ij} \ge 0;}\\{d_{ij}^p\left( {{\varphi _i},{\varphi _j}} \right),{\rm{other\;wise}}{\rm{.}}}\end{array}} \right.$
3.2 目标函数将由于机动导致的无人机额外飞行距离作为目标函数, 记为
$f_{{\rm{addis}}}^i\left( {{\varphi _j}} \right) = f_{{\rm{maneuverdis}}}^i\left( {{\varphi _j}} \right) - L_{{\rm{original}}}^i.$
式中：Loriginali为Ai的机动路径在原始路径上的投影长度, 如图 5中的PoPr; fmaneuverdisi(φj)为Ai的机动路径长度.Ai的飞行路径分为3个阶段.
Fig. 5
图 5 冲突解脱机动过程 Fig. 5 Maneuver process of conflict resolution 1) Ai在时间τ内沿着规划的航向φi+φi飞行.PoP1在原始路径上的投影为PoPa, 投影长度为viτcos(|φi+φdi|).Ai在P1点与原始路径的偏离距离为viτsin(|φi+φdi|), 其中φdi为Ai与其原始路径的航相差.
2) Ai以最大角速度wmaxi调整航向至与其原始路径平行.飞行距离为|φi+φdi|·Rmini.P1P2在原始路径上的投影长度为sin(|φi+φdi|)·Rmini.Ai与原始路径的最大偏离距离为
$\begin{array}{l}f_d^i(\varphi ) = {v_i}\tau \cdot \sin \left( {\left| {{\varphi _i} + \varphi _d^i} \right|} \right) + \\\;\;\;\;\;\;\;\;\;\;\;\left( {1 - \cos \left( {\left| {{\varphi _i} + \varphi _d^i} \right|} \right)} \right) \cdot R_{\min }^i.\end{array}$
3) Ai返回原始路径.额外飞行距离为
$\begin{array}{l}f_{{\rm{addis}}}^i\left( {{\varphi _j}} \right) = {v_i}\tau \left( {1 - \cos \left( {\left| {{\varphi _i} + \varphi _{\rm{d}}^i} \right|} \right)} \right) + \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {\left| {{\varphi _i} + \varphi _d^i} \right| - \sin \left( {\left| {{\varphi _i} + \varphi _d^i} \right|} \right)} \right)R_{\min }^i + \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {\alpha - \beta } \right)\left[ {{v_i}\tau \sin \left( {\left| {{\varphi _i} + \varphi _{\rm{d}}^i} \right|} \right) + } \right.\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {\left( {1 - \cos \left( {\left| {{\varphi _i} + \varphi _{\rm{d}}^i} \right|} \right)} \right)R_{\min }^i} \right].\end{array}$
式中:α为无人机的返回路径与偏离距离的比例系数; β为无人机的返回路径在原始路径上的投影PfPr与偏离距离的比例系数; α、β均为定值.
4 双层优化多无人机冲突解脱集中式优化冲突解脱在无人机数量较少时可以取得理想的结果.随着无人机数量的增多, 集中式优化冲突解脱难以保证所有无人机的冲突解脱.本文采用分群的思想[17], 将多无人机冲突分解为若干无人机冲突群进行分布式冲突解脱.
由于目前能够快速找到局部最优解的算法软件包(如SQP)的计算速度和精度与初始解的好坏有关, 所以本文算法采用双层优化的方法获得解脱方案.先采用随机并行梯度下降法(stochastic parallel gradient descent, SPGD)[18]来搜索无人机的初始可行解以得到冲突解脱的可行解区域, 然后在可行解区域的基础之上运用序列二次规划(SQP)的方法获得最优解.
4.1 产生无人机冲突群运用图论的方法来对多无人机冲突问题进行冲突关系划分.相关无人机的冲突关系用约束图G(t)=(V, E(t))来表示, 如图 6(b)所示, 其中V={1, …, N}为图的顶点集, 每一个顶点表示一架无人机.E(t)={(j, i)|cij=1}为表示冲突关系的图的对应边集合.无人机之间冲突关系随时间改变时G(t)也相应改变.无人机之间的冲突矩阵CM可由G(t)的邻接矩阵得到：
Fig. 6
图 6 8机冲突构型 Fig. 6 Conflict configuration of eight UAVs $\begin{array}{*{20}{c}}{CM = \left\{ {cm\left( {i,j} \right) = g\left( {{\varphi _i},{\varphi _j}} \right){\rm{if}}\;{e_{ij}}\left( {{\varphi _i}} \right) \in E\left( t \right),} \right.}\\{\left. {cm\left( {i,j} \right) = 0\;{\rm{else}}\left| {i,j \in n} \right.} \right\}.}\end{array}$
如图 6(b)所示, 一些无人机之间没有冲突关系.因此, 本文提出根据无人机之间的冲突关系将其聚类为若干冲突群, 每个冲突群组成一个连通子图.这样空域内的无人机被拆分为若干冲突群, 而多无人机冲突解脱问题也就被分解为在每个冲突群内搜索可行的解脱方案, 因此可以大大降低算法的复杂度.
4.2 SPGD求解可行区域产生初始解的随机并行梯度下降算法是一种迭代寻优算法, 其流程如图 7所示.
Fig. 7
图 7 随机并行梯度下降法流程 Fig. 7 Flow chart of SPGD 图中γ为搜索步长, 它的取值与迭代次数有关.δφ(m)服从均值为0的高斯分布, σ为方差, 取值与rsij和g(φi, φj)有关, 性能指标J为
$J = \frac{1}{{2n_{\rm{c}}^1}}\sum\limits_{i = 1}^{{n_1}} {\sum\limits_{j = 1}^{{n_i}} {C_f^{ij}} } ,$
式中, Cfij(φi, φj)为Ai与Aj之间关系的归一化函数, 即
$\begin{array}{l}C_f^{ij}\left( {{\varphi _i},{\varphi _j}} \right) = {\lambda _0}\left( {g\left( {{\varphi _i},{\varphi _j}} \right)} \right) + \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {1 - {\lambda _0}\left( {g\left( {{\varphi _i},{\varphi _j}} \right)} \right)} \right)g\left( {{\varphi _i},{\varphi _j}} \right)/r_s^{ij}.\end{array}$
如果crij=0, 则Cfij(φi, φj)=0.λ0(x)为示性函数, 如果x≥rsij, 则λ0(x)=1, 否则λ0(x)=0.根据随机并行梯度下降法, 当且仅当所有无人机都满足解脱条件时性能指标才能取得全局最大值, 能够高效地产生无人机的初始可行解.如图 4所示, 产生初始可行解后就能够得到无人机冲突解脱的可行解区域.
引理1??给定一个由nl个无人机构成的冲突簇(nl>2), 在局部单调空间中存在能够保证冲突簇中无人机安全间隔可行解区域的前提下, 应用SPGD算法求解初始可行解可以保证收敛到该可行区域.
证明??首先假设在当前的搜索区域Do内存在保证所有无人机安全间隔的子区域Dof.为了不失一般性, 假设冲突簇中有nl个无人机.由于每个一对一冲突的安全约束函数都是局部单调的, 因此可以认为能够保证任意无人机对Ai与Aj安全间隔的角度范围Di, jf与Dof相连通.根据SPGD算法的迭代规则, 在统计学意义上算法每次迭代时都会向使J取值增加的方向调整.由于每个约束函数都是局部单调的, 因此搜索方向会保证J的取值持续增加.
假设在迭代的过程中, 冲突簇中有一个子集合sl1内数量为nl1的无人机之间相互保持安全间隔, 另一个无人机集合sl2中数量为nl－nl1的无人机还没有搜索得到可行解.因此可以得到以下关系：
${c_k}\left( {{\varphi _i},{\varphi _j}} \right) = 1,i,j \in s_1^1,{\rm{and}}\;{c_k}\left( {{\varphi _i},{\varphi _j}} \right) < 1\;{\rm{ if }}\;i \notin s_1^1\;{\rm{ or }}\;j \notin s_1^1.$
由于sl1集合中的无人机能够保持安全间隔, 因此迭代的过程中它们的机动对(φi, φj)只要不导致新的冲突都不会影响搜索方向.而影响搜索飞行的是尚没有找到可行解的冲突对, 根据迭代规则, 搜索算法将搜索能够使尚没有找到可行解的冲突对的函数ck(φi, φj)取值增加的方向, 循环搜索直到找到可行解.
因此, 在统计意义上, 随机并行梯度下降方法能够找到确保多个无人机安全间隔的初始可行解.
4.3 搜索最优解本文已经讨论了解脱机动航向的可行解区域的产生, 在此基础上进一步求解机动航向的最优解.基于航向调整的冲突解脱问题是一个非线性优化问题, 采用序列二次规划来求解最优解.对于第l个冲突群, 其优化目标函数为：
$\begin{array}{l}\min F = \sum\limits_{i = 1}^{{n_1}} {f_{{\rm{addis}}}^i} \left( {{\varphi _j}} \right),\\{\rm{s}}.\;{\rm{t}}.\;\;{\varphi _i} = {\varphi _i}\left( 0 \right),{v_i} = {v_i}\left( 0 \right),{x_i} = {x_i}\left( 0 \right),{y_i} = {y_i}\left( 0 \right),\\\;\;\;\;\;\;{g_{ij}}\left( {{\varphi _i},{\varphi _j}} \right) \ge r_s^{ij},r_s^{ij} = \max \left( {{r_i},{r_j}} \right)\;{\rm{ if }}\;c{r_{ij}} = 1,\\\;\;\;\;\;\; - \varphi _{\max }^i\left( \tau \right) \ge {\varphi _i} \ge \varphi _{\max }^i\left( \tau \right),i,j \in {n_1}.\end{array}$
由于每架无人机机动航向的可行区域分为两个子区域, 所以对于n架无人机, 需要搜索2n个子空间.为保证算法的实时性, 当涉及无人机数量较多时, 将优化目标降低为搜索若干个子空间内的局部最优解.
4.4 算法对比验证分析为验证SPGD算法的有效性, 本文设计了多无人机飞行的冲突场景, 在不同规模下分别利用SPGD与遗传算法(GA)和典型的非线性优化求解器(Snopt)进行1 000次冲突解脱解算, 并收集了不同数量无人机(2~21)涉及冲突时的算法平均求解时间, 将SPGD与遗传算法和Snopt的平均计算时间进行比较, 结果如图 8所示.
Fig. 8
图 8 不同算法对比 Fig. 8 Comparison of Different Algorithms 由图 8可以看出, SPGD明显优于Snopt和遗传算法, 即使当涉及冲突的无人机数量达到21时, SPGD的求解时间也没有超过0.5 s, 能够满足在线求解需要.当涉及冲突的无人机数量小于14时, Snopt的求解时间不超过1 s, 但与SPGD相比, 明显时间复杂度更高.而遗传算法在求解中明显效率很低, 不能满足实时性的要求.
5 仿真分析本文运用MATLAB2014对本文所提方法进行了仿真验证, 仿真以小型无人机为例, 依据美国颁布的无人机规定Part107[19], 小型无人机的速度应小于45 m/s.仿真中最大转弯角速度为wmaxi=5(°)/s, 预警距离为40 s×vi, 且τ=25 s, i∈N[20].无人机的保护区半径为8 s×vi.
图 9(a)显示了8机相同速度相遇时的情况, 共同在(0 km, 0 km)处遭遇.无人机的速度为40 m/s, 复合保护区半径为320 m.图 9(b)显示了8架无人机在解脱过程中任意时刻与它机的最小间隔.仿真结果表明8架无人机成功解脱, 没有发生冲突, 并在解脱完成以后返回到原始路径.
Fig. 9
图 9 8机相同速度 Fig. 9 Eight UAVs with the same speed 图 10比较了双层优化法与选择性速度障碍法(selective velocity obstacle, SVO)在进行多无人机不同速度解脱中的性能.从图 10中可以看出, SVO进行解脱时无人机在某些态势下, 只有冲突中的一方负责进行解脱机动, 这可能导致无人机出现兜圈的情况.而且某些情况SVO会造成无人机进行不可能的机动, 比如图 10(b)中的无人机A3.图 11对两种方法偏离计划位置的距离进行了比较, 在初始阶段, 由于采用双向解脱方案, 双层优化法机动更快, 能够首先完成解脱机动.解脱完成之后, 双层优化法也能够产生更少的额外飞行距离.无人机之间的最小间隔如图 12所示, 结果表明双层优化法能够保证无人机在冲突解脱时的安全间隔.
Fig. 10
图 10 9机不同速度 Fig. 10 Nine UAVs with different speeds Fig. 11
图 11 偏离计划位置的距离 Fig. 11 Deviation of the distance from the planned location Fig. 12
图 12 双层优化法无人机之间的最小距离 Fig. 12 Minimum distance between UAVs by two-layer optimization 6 蒙特卡洛法冲突概率分析在上述仿真分析中, 多无人机的冲突全部成功解脱.但是, 由于无人机在实际运行过程中环境相当复杂, 上述的仿真只是基于位置、速度和航向均固定的冲突态势, 不能保证算法的普适性.因此, 通过蒙特卡洛法产生大量随机的无人机冲突来得到多无人机的冲突概率.与上述类似, 本文依然基于小型无人机来进行仿真.
由于现实中的实验具有高风险、耗费高和耗时长的特性, 所以本文采用简单、经济、实用的蒙特卡洛法来产生无人机的冲突概率.根据无人机的等效安全水平原则[21], 无人机冲突解脱算法的成功率应为100%.
6.1 蒙特卡洛仿真条件为了评价本文算法的性能, 需要设置一些蒙特卡洛仿真的参数.算法的性能可以通过冲突概率Pvio来评价.
${P_{{\rm{vio}}}} = \frac{{{N_{{\rm{vio}}}}}}{{{N_{{\rm{MC}}}}}}.$
式中:Nvio、NMC分别为蒙特卡洛仿真过程中的冲突个数和采样个数; Pvio将随着NMC波动, 但随着NMC逐渐增大, Pvio将逐渐趋于一个稳定值.
蒙特卡洛仿真条件如下：
1) 为了简化仿真条件, 蒙特卡洛仿真中无人机均保持在一个固定的正方形区域Asqu中飞行, 如图 13所示.无人机的位置(xi, yi)随机分布在正方形区域Asqu中, 横纵坐标范围为[－4 km, 4 km], 无人机的探测半径Adeti为vi×40 s.
Fig. 13
图 13 4机随机态势 Fig. 13 Random situation of four UAVs 2) 双层优化法中标准无人机解脱开始距离为Davo=τ×vi(τ=25 s).本文在冲突概率分析中考虑解脱开始距离小于Davo的情况, 并定义比例系数ρavo为
${\rho _{{\rm{avo}}}} = \frac{{{{D'}_{{\rm{avo}}}}}}{{{D_{{\rm{avo}}}}}},$
式中D′avo为仿真中的无人机冲突解脱开始距离.如表 1所示, 蒙特卡洛仿真采用3种仿真类型：MC1、MC2、MC3. MC1中, ρavo∈[0, 0], 即不使用冲突解脱算法. MC2中, ρavo∈[0, 1], 即所有无人机的解脱开始距离D′avo小于标准解脱开始距离Davo.MC3中, ρavo∈[1, 1], 即所有无人机的解脱开始距离D′avo等于标准解脱开始距离Davo.为了避免无人机的初始间隔对冲突概率的影响, 仿真中t=0时无人机的间隔均大于D′avo.
表 1
表 1 蒙特卡洛仿真参数设置 Tab. 1 Parameter setting of Monte Carlo simulation 仿真类型 (xi, yi)/km vi/(m·s-1) φi/rad ρavo/Davo MC1 [－4, 4] (0, 45) (0, 2π] [0, 0]
MC2 [－4, 4] (0, 45) (0, 2π] [0, 1]
MC3 [－4, 4] (0, 45) (0, 2π] [1, 1]
表 1 蒙特卡洛仿真参数设置 Tab. 1 Parameter setting of Monte Carlo simulation
3) 由于小型无人机的规定速度为小于45 m/s, 蒙特卡洛仿真中随机产生的无人机初始速度vi∈(0 m/s, 45 m/s), 且整个仿真过程中无人机的速度保持不变(见表 1).
4) 为了产生无人机的所有可能相遇态势(对头相遇、交叉相遇和追及相遇), 仿真产生的无人机初始航向范围为(0, 2π], 且在冲突解脱开始之前航向保持不变(见表 1).
仿真过程中, 首先在正方形区域Asqu中产生N(N=2, 3, 4, 5)架无人机, 并根据仿真类型和表 1中的参数范围随机产生无人机的位置、速度、航向和比例系数ρavo.若无人机在飞行过程中探测到了冲突存在则无人机运用双层优化法进行冲突解脱, 否则无人机航向保持不变.
6.2 结果分析蒙特卡洛仿真采样次数为106次.仿真结果中的Pvio与采样次数的关系如图 14所示, 无人机不同数量下的冲突概率如图 15所示.由图 14、15中可以看出, MC3的冲突概率在2~5机时的冲突概率均为0, 符合等效安全水平的要求.MC2中虽然冲突概率比不使用算法的情况下大幅下降, 但不能够解脱一切冲突, 不满足等效安全水平的要求, 解脱失败的原因在于冲突解脱的距离过短.
Fig. 14
图 14 不同仿真类型的冲突概率 Fig. 14 Collision probability of different simulation types Fig. 15
图 15 冲突概率对比 Fig. 15 Comparison of conflict probability 通过分析可以得出, 在标准的冲突解脱开始距离下双层优化算法的解脱成功率能够达到100%, 满足无人机等效安全水平的要求.
7 结论1) 算法能够解决多无人机的冲突解脱问题, 减少解脱代价, 满足在线规划需要并降低了对空中交通的影响.可满足无人机等效安全水平的要求, 在解脱开始距离Davo=τ×vi(τ=25 s)的情况下能够实现100%的冲突解脱.
2) 分析了冲突解脱的几何模型和约束条件, 重点研究了冲突几何的终点约束、切线约束和kji的周期性特点, 并同时考虑了无人机的既有冲突与潜在冲突, 有效避免了诱发冲突, 保证冲突解脱问题在最大范围内求解.
3) 提出了一种双层优化算法, 首先通过随机并行梯度下降法求得冲突群的可行解区域, 再用序列二次规划进行最优解的求解, 能够在保证成功解脱的情况下进行航向机动的优化.通过蒙特卡洛法设置不同的仿真条件比较验证了双层优化算法进行多无人机冲突探测与解脱的安全性.
参考文献
[1] FLOREANO D, ROBERT J W. Science, technology and the future of small autonomous drones[J]. Nature, 2015, 521(7553): 460. DOI:10.1038/nature14542
[2] 陈金良, 郭芳月. 基于当前环境的无人驾驶航空器飞行管理设想[J]. 北京航空航天大学学报(社会科学版), 2017, 30(5): 37.
CHEN Jinliang, GUO Fangyue. Assumption of UAV flight management based on current environment[J]. Journal of Beijing University of Aeronautics and Astronautics (Social Sciences Edition), 2017, 30(5): 37. DOI:10.13766/j.bhsk.1008-2204.2017.0179
[3] DALAMAGKIDIS K, VALAVANIS K P, PIEGL L A. On integrating unmanned aircraft systems into the national airspace system: Issues, challenges, operational restrictions, certification, and recommendations[M]. Berlin: Springer, 2012: 22. DOI:10.1007/978-94-007-2479-2
[4] ROELOFSEN S, MARTINOLI A, GILLET D. Distributed de-confliction algorithm for Unmanned Aerial Vehicles with limited range and field of view sensors[C]//Proceedings of American Control Conference. Chicago, IL: IEEE, 2015, 321: 4356. DOI: 10.1109/ACC.2015.7172014
[5] BERG J V D, GUY S J, LIN Ming, et al. Reciprocal n-body collision avoidance[J]. Springer Tracts in Advanced Robotics, 2011, 70: 3. DOI:10.1007/978-3-642-19457-3_1
[6] ALEJO D, COBANO J A, HEREDIA G, et al. Optimal reciprocal collision avoidance with mobile and static obstacles for multi-UAV systems[C]//Proceedings of International Conference on Unmanned Aircraft Systems (ICUAS). Orlando, FL: IEEE, 2014, 3: 1259. DOI: 10.1109/ICUAS.2014.6842383
[7] CONROY P, BAREISS D, BERG J P V D, et al. 3-D reciprocal collision avoidance on physical quadrotor helicopters with on-board sensing for relative positioning[J/OL]. Computer Science Robotics(2014-09-14)[2018-06-01]. https://arxiv.org/abs/1411.3794
[8] YANG Jian, YIN Dong, SHEN Lincheng. Reciprocal geometric conflict resolution on unmanned aerial vehicles by heading control[J]. Journal of Guidance Control and Dynamics, 2017, 40(10): 2511. DOI:10.2514/1.G002607
[9] YANG Jian, YIN Dong, CHEN Qiao, et al. Two-layered mechanism of online Unmanned Aerial Vehicles conflict detection and resolution[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 19(10): 3230. DOI:10.1109/TITS.2017.2771465
[10] JENIE Y I, VAN KAMPEN E-J, DE VISSER C C, et al. Selective velocity obstacle method for de-conflicting maneuvers applied to unmanned aerial vehicles[J]. Journal of Guidance Control and Dynamics, 2015, 38(6): 1140. DOI:10.2514/1.G000737
[11] ALONSO-MORA J, NAEGELI T, SIEGWART R, et al. Collision avoidance for aerial vehicles in multi-agent scenarios[J]. Autonomous Robots, 2015, 39(1): 101. DOI:10.1007/s10514-015-9429-0
[12] ALONSO-AYUSO A, ESCUDERO L F, MARTIN-CAMPO F J, et al. Collision avoidance in air traffic management: A mixed-integer linear optimization approach[J]. IEEE Transactions on Intelligent Transportation System, 2011, 12(1): 45. DOI:10.1109/TITS.2010.2061971
[13] ALONSO-AYUSO A, ESCUDERO L F, MARTIN-CAMPO F J, et al. A mixed 0-1 nonlinear optimization model and algorithmic approach for the collision avoidance in ATM: Velocity changes through a time horizon[J]. Computers & Operation Research, 2012, 39(12): 3136. DOI:10.1016/j.cor.2012.03.015
[14] DUBINS L E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[J]. American Journal of Mathematics, 1957, 79(3): 497. DOI:10.2307/2372560
[15] 韩冬, 张学军, 聂尊礼, 等. 一种基于SVM的低空飞行冲突探测算法[J]. 北京航空航天大学学报, 2018, 44(3): 576.
HAN Dong, ZHANG Xuejun, NIE Zunli, et al. A conflict detection algorithm for low-altitude flights based on SVM[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(3): 576. DOI:10.13700/j.bh.1001-5965.2017.0159
[16] 刘洋, 向锦武, 罗漳平, 等. 低空自由飞行短期冲突探测算法[J]. 北京航空航天大学学报, 2017, 43(9): 1873.
LIU Yang, XIANG Jinwu, LUO Zhangping, et al. Short-term conflict detection algorithm for free flight in low-altitude airspace[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(9): 1873. DOI:10.13700/j.bh.1001-5965.2016.0687
[17] 梁晓龙, 张佳强, 祝捷, 等. 基于CPS的空中交通系统架构及能力涌现方法[J]. 空军工程大学学报(自然科学版), 2016, 17(1): 1.
LIANG Xiaolong, ZHANG Jiaqiang, ZHU Jie, et al. Air traffic control system architecture and ability emergence method based on Cyber-Physical System[J]. Journal of Air Force Engineering Universit (Natural Science Edition), 2016, 17(1): 1. DOI:10.3969/j.issn.1009-3516.2016.01.001
[18] 靳冬欢.基于随机并行梯度下降算法的波前校正技术研究[D].长沙: 国防科技大学, 2006: 30
JIN Donghuan. Research on wave-front correction technique based on stochastic parallel gradient descent algorithm[D]. Changsha: National University of Defense Technology, 2006: 30
[19] Federal Aviation Administration (FAA).Summary of small unmanned aircraft rule (part 107): AC No: 107-2[S]. America: Federal Aviation Administration (FAA), 2016: 5-1-5-14
[20] BARELD F. Autonomous collision avoidance: The technical requirements[C]//Proceedings of the National Aerospace and Electronics Conference. Dayton, OH: IEEE, 2000: 808. DOI: 10.1109/NAECON.2000.894998
[21] 尹树悦, 王少飞, 陈超. 无人机安全性指标要求确定方法研究[J]. 现代防御技术, 2015, 43(2): 154.
YIN Shuyue, WANG Shaofei, CHEN Chao. Research on method for determination of UAV safety index requirements[J]. Modern Defense Technology, 2015, 43(2): 154. DOI:10.3969/j.issn.1009-086x.2015.02.025
