基于空间映射的异构无人机在线冲突消解算法

杨健 钟紫凡 杨少博

随着与无人机相关的技术不断成熟,人们看到了将其用于各种场景和领域的巨大潜力.例如应用无人机进行交通情况监视、货物运输、灾难现场的搜索救援等等[1−2].我们可以畅想,在不远的未来,无人机会成为空中交通的重要一员.未来无人机将大量应用在大城市及其周边区域的上空,在那里无人机将与其他有人航空器(例如私人飞机)共享空域.无人机之间以及无人机与有人机之间的碰撞会对其他有人航空器或者地面的人和财产造成威胁.因此,政府在考虑发展无人机产业的同时由于担忧无人机产生的空域安全问题而有所顾虑.

如何让无人机在空中安全而高效地飞行？这个问题越来越成为人们关注的热点.我们知道有人机的安全飞行大多依赖细致的预先调度和周密的飞行计划[3].在周密细致的事前工作保证下,空中交通管理部门不需面临太大的实时处置压力.这种模式对无人机并不适用.首先,无人机的起飞场地要求比较低,一个城市内有很多场地都可供无人机起飞,难以对飞机进行全面监管;另外,未来无人机飞行应用灵活,可能会在一个局部空域中大量聚集,无人机为了完成既定的任务,其航迹可能由很多不规则的折线组成而不像有人飞机那样一般是起点到终点间的连线.因此,有人机的管控方法难以直接应用于无人机空中交通管理.为了满足将无人机纳入空中交通管理系统的需求,需要增强空中交通管理系统实时协调处理空中交通用户的能力.

无人机的种类多样,未来在空中飞行的无人机的类型各异,载荷和平台性能不同.针对异构无人机冲突消解问题的研究存在现实需求.当前学术界已经提出了很多处理冲突消解的方法,例如航线规划方法[4]、智能优化算法[5]、半正定规划方法[6]、几何导航算法[7].其中基于几何导航的方法不依靠需要大量计算的复杂预测和分析,在实时处理大量无人机冲突上具有较好的应用前景[8].

本文基于几何导航方法的研究分析无人机间的冲突.由于在天空中运行的无人机用处不同,因此,其载荷和平台性能有很大的差异.未来天空中飞行的无人机大部分是异构无人机.当两个无人机的速度不同时,它们的安全间隔约束条件是非线性的.非线性问题比线性问题的求解难度大.为提升计算效率,很多研究人员研究了多种方法归纳出线性的安全间隔约束条件[9−11].我们研究提出了一个两层次求解机制寻找局部最优解[12],该算法具有较好的计算效果.但这些已有方法的计算效率仍然难以满足实时冲突消解的需求.

本文研究异构无人机的冲突消解方法[13].应用空间映射方法将每个一对一的冲突约束条件推导为基于周期的线性约束不等式,并将问题建模为混合整数线性规划问题加以求解.

1 问题提出

假设无人机在空中执行具体任务的过程中其飞行高度不发生变化,因此,本文研究二维空间无人机的冲突消解问题.假设在局部区域中有N个无人机陷入空间冲突中,在二维空间,无人机Ai,i∈N的位置定义为Pi(t)=(xi(t),yi(t)),速度vi(t),运动方向φi(t).无人机的运动学模型描述为式(1):

加速度ai(t)与角速度wi(t)是控制无人机运动的两个变量.假设空域冲突时无人机速度保持不变,依靠调整运动方向保证飞行安全.空中交通管理系统动态监控空域中无人机的基本信息,如位置、速度、运动方向及既定的航路点.为了保证无人机飞行安全,需为每个无人机设定独立的安全空域.这个安全区域随着无人机的位置动态移动,其他的航空器进入这个区域会对本无人机产生较大的安全威胁.安全空域可被定义为球状区域,也可定义为圆柱状区域.研究同一平面内的无人机冲突问题时这两种区域在水平面上都是一个具有安全半径ri的圆形投影,被定义为Di(Pi(t),ri).由于无人机平台比有人机平台小很多,根据无人机的平台和飞行速度,将无人机的安全空域半径设定为数百米[14].无人机Ai和Aj的距离小于时定义为失距,是复合安全半径=max(ri,rj).将Ai与Aj间的安全约束定义为式(2):

其中k.k是二维空间中的欧氏范数.

冲突消解的目标是为每个无人机找到在时间段[0,τ]内合适的调整方向ϕi以保证局部空域的无人机在τ时刻前不会发生失距.无人机的动力学性能约束其不可能在瞬时完成规划的机动角度的调整.我们假设无人机的跟踪系统能够在其性能范围内跟踪ϕi.本文考虑应用dubins曲线近似无人机调整方向的过程,如图1所示.假设无人机将通过两次方向调整θ1和θ2达到角度调整的目标[15].

为了确保为Ai规划的机动角度ϕi满足其动力学约束,应确定Ai在时间段[0,τ]内的最大可跟踪角度(τ).可应用τ与最大角速度估计(τ)的取值[15].ϕi应满足约束:

实时规划中为了提高计算效率假设无人机的飞行线路为直线,如图1所示的点划线.点划线的距离与飞机实际飞行的距离有误差,这些误差在无人机跟踪路径过程中消除[16].

首选分析两个无人机的安全间隔约束.在局部坐标系中讨论无人机间的关系.如图2所示,Ai和Aj存在空域冲突,以Aj当前位置为局部坐标系原点,在t=0时刻Ai在局部坐标系中位置如式(4):

Ai与Aj间存在空域冲突.这类空域冲突被定义为既有冲突,意为如不调整运动方向,两无人机将发生失距[16].假设它们分别调整ϕi与ϕj.经过调整后两机速度为式(5):

Aj相对Ai的速度为:

为保证Ai与Aj的安全间隔,v v vj j ji应在图2中灰色区域以外,安全间隔约束条件式(2)转换为:

其中kji是v v vj j ji的斜率.为了讨论式(7)的可行解,定义等式:

其判别式:

假设两个无人机在t=0时保持着安全间隔,故有∆>0.式(8)的两个实数根:

式(7)的可行域由和确定.通过坐标系旋转将可行域归纳为[15]:

将kji展开为式(12):

kji是周期为 [−π/2+kπ,π/2+kπ],k∈Z的周期函数.整理式(12)为式(13):

如图3所示,完整的可行解区域被划分为区域1和区域2.虽然这两个区域是联通的,但因为这两个区域属于kji不同的周期而难以将其描述为一个整体区域并求解冲突消解策略.本文研究在kji的不同周期分别求解冲突消解策略.定义kji的分母函数式14):

为了方便讨论,设定v v vji在4个象限的方位角为[−π/2,3π/2].(ϕi,ϕj)确定了kji的周期性.应用函数(ϕi,ϕj)取值正负判断kji的周期[15].定义布尔变量dsij判断函数(ϕi,ϕj)在区域1与区域2上的正负值.定义v v vji的朝向为φji,dsij的取值定义:

a)若(0,0)6=0,如果φji∈[π/2,π∗3/2]且0,0)<0,或φji∈[−π/2,π/2]且(0,0)>0,dsij=1否则dsij=0.

b)若(0,0)=0,给无人机的飞行方向增加一个微小的扰动(使得=0.将会得到新的值.可以根据)的正负确定dsij的取值.

由此可确定能保证安全间隔的(ϕiϕj)应满足:

1)若dsij=1可行解区域满足

或

2)当dsij=0可行解区间满足约束:

或

当涉及冲突的无人机多于两个时,需考虑飞机间的潜在冲突[12],定义变量cij:

2 空间映射方法

Ai与Aj速度相同时,kji与(ϕiϕj)的关系是线性的[7].但大多数情况下无人机速度不相同,此时基于方向调整的冲突消解问题是一个混合整数非线性优化问题,其计算复杂度比线性优化问题复杂[9,16].当无人机的速度不同时为了建立kji与(ϕi,ϕj)的线性关系,对式(13)进行进一步讨论.

两个无人机的安全间隔约束为式(15)、式(16)与式(17)、式(18).根据约束条件特点,定义映射关系如式(20):

与的值域为[−1,1].式(20)将角度值关系映射为正弦值关系.式(13)转换为xis,b与ysj,b的关系:

由此,安全间隔约束被转换为正弦值空间的线性关系.对式(21)进行进一步讨论以得到每个无人机的机动约束.以不等式约束的可行解为例,如图4所示.深灰色区域为可行解元组()对应的可行解区域,将其定义为,b∈1,2.∀()对应在角度空间能保证Ai与Aj安全间隔的机动策略对(φi,φj).深黑线是可行解边界,其表达式如式(21).与坐标轴的夹角为

坐标系中,当Ai与Aj的运动方向不变时初始点为=xis,,bo=sin(φi(0)−δ(),=sin(φj(0)− δ().当Ai与Aj存在既有冲突时.此时需Ai和Aj调整(ϕi,ϕj)以使(φi(0)+ϕi,ϕj(0)+ϕj)的映射在区域内.定义向量如式(23):

uhh的范数为从到可行域的最小距离.根据可计算得Ai应负担的调整量在映射空间中的取值和Aj应负担的调整量在映射空间中的取值(φi(0)+ϕi,φj(0)+ϕj)经过映射后在坐标系上的坐标为=.从到映射的向量被定义为,如图4(a)所示.为了保证Ai与Aj的安全间隔,需满足约束:

无人机间存在潜在冲突时,其机动角度约束也可被描述为式(15),式(16)或式(17),式(18).由于安全区域边界的影响,由潜在冲突会得到两个不同的约束,一个与既有冲突的相同,另一个约束定义了Ai与Aj在当前状态下可机动角度而不是须机动角度.如图4(b)所示,深灰色区域为可行解区域,定义为1or2,且.定义一个向量

为保证无人机间安全间隔,应满足约束:

Ai与Aj的机动角度在正弦值空间的映射需分别满足或在各坐标系上映射分量的约束.

基于这个规则,涉及既有冲突的Ai与Aj应满足如下约束.

无人机之间存在潜在约束时应当满足下面的不等式:

由此由非线性冲突约束推导出线性约束条件.在计算获得正弦值空间内的线性约束条件后经过反三角函数运算即可得到Ai在与Aj的冲突中的机动角度约束条件,如同样也可以得到Ai的机动角度约束条件进一步可分别得到由与分别确定的Ai和Aj的可机动区域.最终可建立Ai与Aj一对一冲突中的可行域集合Sij.由于篇幅限制本文不再赘述.

3 冲突消解问题建模

3.1 冲突消解目标函数

冲突消解的目的是找到能使无人机消耗降低的安全机动解,需要设计合理的目标函数.由于无人机速度不变,认为无人机机动消耗与当前飞行方向和期望飞行方向的角度差正相关[17].由于无人机可能在处理当前面临的冲突前由于风力或者其他因素的影响而偏离原定的航线,设当前Ai原本偏离期望航线的角度为,经过机动过后偏离期望航向的角度变为fi=|ϕi+.无人机采用机动角度造成的损失定义为:

为消去绝对值带来的非线性特性,将目标函数定义为式(32)[18]:

其中0,且0.它们满足约束:

3.2 混合整数线性规划模型

应用在正弦值空间定义的向量可将非线性约束转化为解耦的线性约束.由于两个无人机的冲突可行解区域分布在kji的两个周期中,每个周期内有ϕi与ϕj的一到两个可行解区间.最优方向调整解需在多个独立可行解区间中搜索.

在多无人机发生冲突时,对每个一对一冲突Ai与Aj可行解区间的选择会影响它们与其他无人机构成冲突对的优化解的搜索.因此,多无人机冲突可以看作是多个相互耦合的一对一冲突,本文应用混合整数线性规划方法求解多无人机冲突消解问题.

将多无人机集中协作式方向调整问题建模为混合整数线性规划问题.目标函数为降低所有无人机的机动角度之和:

M是一个较大的数值.是布尔变量以建模安全约束的或条件.它可以被用来标示优化时选择了哪个约束,也就是在集合Sij的哪个子区间中搜索最优解.由于目标函数和安全约束都是选定的参数的线性约束,因此,整个问题就是一个标准化的混合整数线性规划模型,可应用高效的求解器求解.

4 仿真验证

本文设置了两个场景展示算法对复杂冲突场景的处置效果.仿真计算的平台条件是Intel Core i5 2.8GHz,4GB RAM.软件平台为Microsoft Windows 7 Professional系统,采用 MATLAB 2014编程求解.求解混合整数线性规划的求解器为CPLEX.空中交通管理要素持续监视无人机的状态,过程中不存在时延或丢包现象.仿真二维环境中消解无人机的冲突.无人机的速度范围为[40m/s∼60m/s].考虑到无人机的速度,空中交通管理系统对无人机的监视距离为2.5km.τ取值为35s.无人机Aii∈N的安全空域半径为.在仿真中设定为5deg/s.在实际场景中每个无人机的方向调整可能不同.

4.1 聚集场景

图5展示大量异构无人机汇聚的场景.多无人机汇聚场景经常被用于在检验一个算法的有效性[11].因为在汇聚场景中每个无人机都与其他无人机存在冲突,一对一的冲突个数为N(N−1)/2,此时的冲突场景可以建模为一个无向全联通图[12].很多研究人员展示了他们的算法在处理同构无人机汇聚场景中的表现,实际上这种条件下的安全间隔约束是线性约束,计算容易.本文展示当无人机的速度不同时采用方向调整策略解决冲突的场景.无人机的初始状态如表1.

应用本算法消解无人机冲突结果如图5所示.

冲突消解结果如图5所示,无人机采用右转以摆脱失距风险.完成消解冲突后无人机将返回原定航线.表1记录了每个无人机的安全区域半径和它在飞行过程中与其他无人机的最小距离.针对12个异构无人机汇聚冲突,CPLEX求解器计算时间为0.2s左右.该计算效率能够满足在线实时的冲突消解规划需求.规划结果说明应用本算法能够使无人机通过合适的角度调整保持安全间隔.

4.2 方格场景冲突消解

图6展示了异构多无人机在方格场景中的冲突消解问题.本场景中,12个无人机被分为4组.无人机初始状态如表2所示.无人机会在十字交叉区域处发生冲突.方格场景中由于无人机不向同一个方向汇聚,其冲突的复杂性较汇聚场景简单,处置每组冲突的计算时间为0.05s左右.应用本文算法解决无人机冲突得到能够保证无人机飞行安全的航线如图6所示.无人机在飞行过程中与其他飞机间的最小距离如表2所示.数据说明应用本文的算法能保证无人机飞行过程中的安全间隔.

表1 多异构无人机冲突消解信息

表2 多异构无人机冲突消解信息

这两个冲突消解的场景证明了本文提出的算法解决复杂冲突的有效性.应用本文的算法无人机在规避冲突时不会进行多余方向调整.由于在优化计算时会考虑事先规划的路径,因此,产生的偏移量较小,造成的机动消耗也较小.

5 结论

本文提出了解决异构无人机间冲突的局部集中式优化方法.该方法应用空间映射方法由非线性安全间隔约束推导得到线性约束.从而问题可被建模为混合整数线性规划模型.算法具有实时消解多无人机复杂冲突的能力,可以用于解决通信带宽较大条件下的多无人机冲突消解问题.算法可以集成到空域管理系统中用于处置航空器的非预期过度接近问题.