基于快速扩展随机树算法的多无人机编队重构方法研究

李樾, 韩维, 陈清阳, 张勇

(1.海军航空大学 航空基础学院, 山东 烟台 264001; 2.国防科技大学 空天科学学院, 湖南 长沙 410073)

多无人机编队飞行,即多架无人机为适应任务要求而进行的某种队形排列和任务分配的组织模式,它既包括编队飞行的队形产生、保持和变换,也包括飞行任务的规划和组织[1]。随着无人机数量不断增多以及所执行任务的日趋复杂,对多无人机编队飞行的控制要求也相应提高,同时,任务及环境的频繁变化要求编队中的各无人机必须能够进行灵活的位置变换,即编队的重构[2]。近年来随着多无人机编队技术的发展,该问题逐渐成为研究热点之一,其重点是对飞行安全及编队变换效率的研究。

目前,实现多无人机编队重构的主要方法包括:势能域函数法、概略图法、生物算法以及最优控制法等[3]。其中,势能域函数法应用较广,但是在环境条件未知且存在动态障碍的情况下,建模存在一定的难度,极易陷入局部最优值[4];概略图法利用网格图的形式进行航迹规划,是机器人领域广泛采用的一种重构方法[5],但在与无人机动力学模型结合时存在难度,且求解的实时性较差;生物算法包括蚁群算法、鱼群算法、粒子群算法等,这些算法的计算效率不一,并且为了规划出利于跟踪的航迹,往往还需要借助其他技术,如文献[6]将粒子群算法和Dubins轨迹相结合,以达到既满足无人机动力学约束又提高搜索效率的目的;最优控制方法的典型代表是伪谱法,其局限性与势能域函数方法类似[7],同时,计算的复杂也限制了其应用的范围。

近年来, RRT算法因适用于解决包含威胁区域和动力学约束条件的运动规划问题而受到了更多的关注。该方法原理简单,搜索效率高,由Lavalle在1998年首次提出[8],是一种基于采样的单查询随机搜索算法。其无需在规划前对节点扩展进行预处理,而是利用传感器采集的信息对规划空间进行迅速有效地搜索[9],但不足之处在于,计算量较大、节点处不利于跟踪、难以生成最优航迹等[10]。针对传统RRT算法的缺点,许多改进的RRT算法被运用到无人机航迹规划和编队重构中。

文献[11]提出了一种自适应步长的RRT算法,以解决复杂环境中无人机航迹规划的问题,该算法的改进体现在计算效率和搜索能力上;文献[12]提出了一种滚动时域与RRT算法相结合的无人机航迹规划算法,主要通过偏离采样和节点剔除的方法来提高算法的运算效率;文献[13]根据无人机航向角变化率,对基本RRT算法生成的航迹进行了优化处理;Farinella等[14]提出了一种基于模型预测法的RRT算法,该算法以中继卫星为探测传感器,能达到实时避障的目的;田晓亮[15]将改进的RRT算法应用到多无人机编队重构中,但仅以2架无人机为例进行仿真,并未考虑编队重构过程中可能发生的内部碰撞以及最终编队构型的问题。

总的来说,目前对传统RRT算法的改进多集中于计算效率和实时规划方面,对规划航迹的可跟踪性以及编队应用领域的研究相对较少。针对以上不足,本文提出了一种基于RRT算法的多无人机编队重构方法,以二维平面内按长-僚模式编队的无人机为研究对象,重点研究其在飞行器动力学、协同及防碰撞等约束下的航迹变换过程,并结合RRT算法的特点,对所规划的航迹进行冗余裁剪、光滑处理,以实现多无人机编队在复杂环境中安全、快速变换队形的目的。

1 问题提出

1.1 多无人机编队建模

当前,相对成熟的无人机编队控制模式包含:长-僚模式、模型预测控制模式、基于行为分析的模式、虚拟结构模式以及人工势场模式等[1]。其中,长-僚模式利用预设的编队队形,通过控制长机的飞行速度及姿态来调节僚机的飞行指令,以实现对编队队形的控制。长-僚模式具有控制简单、易实现等优点,因此本文采用该控制模式。

图1 编队坐标系下长-僚机的二维位置关系图

长-僚模式下的编队坐标系固联于长机,其原点Ol位于长机的质心,OlXl轴沿长机飞行速度的矢量方向,以前方为正;OlZl轴位于机体对称平面内,与OlXl轴垂直,指向下;OlYl轴与OlXlZl平面垂直,并与其余2轴构成右手直角坐标系[16]。以2架按长-僚模式编队的无人机为例,图1展示了其在编队坐标系下的二维位置关系图。其中,[x,y]为僚机F在该坐标系下相对长机L的坐标;V,ψ和μ分别表示无人机相对于惯性坐标系的速度、航迹方位角和航迹滚转角(μ并未在图1中标出),下标L表示长机、F表示僚机;ψE是长机和僚机的航迹方位角之差,即ψE=ψF-ψL,与之类似,μE=μF-μL。

(1)

(2)

1.2 传统RRT算法的原理

传统RRT算法通过随机采样并逐渐增加叶节点的方式生成随机扩展树T,主要包括3个步骤:构造采样点、寻找根节点和扩展节点[13]。下面对其基本原理进行简要介绍。

Zrand的连线上,以Znear为起点计算出Znew,如果Znew与Znear之间不存在威胁,则将Znew加入到T中,若不然则重新生成采样点Zrand;重复上述过程,直至|Znew-ZG|≤L,输出T,并依次连接各根节点,即得到了一条自ZI至ZG的航迹。

1.3 传统RRT算法在编队应用中的不足

利用传统RRT算法生成的航迹具有节点多、在转弯段曲率不连续等特点,无人机在跟踪该类航迹时,极易出现因航迹振荡而造成的飞机失稳现象。这是由于无人机在节点转弯段缺少提前的预切换,从而导致转弯时机的滞后,使得飞机允许的最小转弯半径与节点转弯处期望的转弯半径不匹配,特别是当飞机地速较大时,所允许的最小转弯半径与期望的转弯半径相差更大,振荡现象会更为明显;另外,节点的冗余对航迹跟踪的稳定性也会造成一定的影响。

在复杂的飞行环境中,航迹振荡不利于无人机飞行安全,特别是在多无人机编队重构过程中,极易导致机间碰撞或与外部障碍的碰撞。因此,基于RRT算法的多无人机编队重构算法应首先保证各无人机的安全。具体来说,应尽量减少无人机非必要的转弯,并确保无人机在必要的转弯处平稳过渡飞行,其关键是要满足无人机最小转弯半径的约束,避免提前转弯或滞后转弯。

2 基于传统RRT算法的航迹修正

根据1.3节的分析,针对传统RRT算法所生成的航迹,可以从两方面进行修正,一是对随机树中不必要的节点进行去除,避免多次机动引起的飞机失稳;另一方面是在节点之间生成过渡航迹,引导无人机转弯时进入其允许曲率的弧形航迹。其中,多余节点的去除在现有的文献中运用较为广泛[9,12,17],其思想也相对统一,具体在2.1节进行归纳总结。

2.1 多余节点的去除

设T中所有节点组成的集合为Root={ZI,Z1,Z2,Z2…Zn,ZG},由于节点扩展具有随机性,因而在保证航迹可行的基础上,Root中存在非必须经过的航迹节点,将这些节点视为“多余”的,并将去除多余节点后的节点集合记为Refined,显然Refined⊆Root,这表明新的航迹长度相较之前有所缩减。Refined的求解过程具体如下:

首先令Refined={ZI},检验ZI,ZG连线之间能否直接通行,即是否满足无碰撞威胁和飞机动力学约束,若可通行,则ZG加入Refined,结束循环;若不可通行,则依次检验ZI,Zi之间连线能否通行,其中初始循环i=n,每次循环后i=i-1(1

图2 多余节点去除算法的流程图

2.2 过渡航迹的生成

在传统RRT算法的节点切换过程中,为了解决飞机允许的最小转弯半径与期望转弯半径可能不匹配的问题,借鉴Dubins轨迹的思想[18],以飞机在节点处转弯过程中耗时最短为目标,提出了过渡航迹的概念,其思想是利用以Rmin为半径的弧形航迹作为连接节点前后2段航迹的规划航迹。问题解决的关键在于确定过渡航迹存在的条件及无人机切入、切出过渡航迹的条件。

(3)

(4)

(5)

当过渡航迹存在时,为避免迭代搜索带来的计算效率问题,利用几何法直接解算Oc,过程如(6)式所示

(6)

过渡航迹生成的示意图如图3所示,其中无人机满足逆时针盘旋转弯的条件。顺时针盘旋与之类似,在此不加赘述。

图3 过渡航迹生成的示意图

图4 节点切换策略的选择示意图

3 RRT算法在编队重构中的应用

多无人机编队的重构过程具有变量多、约束条件复杂等特点,并且由于空中环境的复杂与不确定性,保证编队的飞行安全是编队重构的首要要求。

3.1 环境设定

在编队重构过程中,空中可能会存在因地形、雷达或防空火炮等形成的障碍或禁飞区[15],它们统称为威胁区。威胁区的建模不作为本文的研究重点,统一将其近似为规划空域中的若干圆[13],且不可穿越,用Si表示,其圆心坐标及半径均采用随机数的方式获得,从而得到威胁区的模型如(7)式所示

∀i=1,2…,m

(7)

式中,(ai,bi),ri分别表示第i个威胁区的圆心坐标和半径,m为威胁区的个数。显然

(8)

在此基础上,设编队中飞机属同构飞机,初始队形和目标队形皆已知,各飞机保持匀速飞行,且速度域的区间长度小于15,即速度不作为调节重构时间的主要因素。编队重构过程的示意图如图5所示。其中,m=2,编队中无人机数v=3。

图5 编队重构过程的示意图

3.2 约束条件

在重构过程中,首先利用改进的RRT算法规划出长机航迹(设只有一架长机),后将其作为外部威胁输入到僚机的航迹规划中,并结合编队中另外的约束条件生成编队重构的整体方案。这些约束条件能保证重构过程中航迹变换的可行性,具体如下:

1) 无人机最小转弯半径的约束

过渡航迹的构造可以满足这一约束条件。

2) 最小航迹长度约束

飞机受机动能力的限制,在改变姿态前需要保持一段距离的平飞,将其允许的最小值定义为最小航迹长度,记为lmin。在利用RRT算法对随机树进行扩展时,步长L应满足最小航迹长度约束如(9)式所示

L≥lmin

(9)

3) 目标队形的几何约束

针对设定任务的需要,各无人机到达目标队形时,位置应满足一定的几何约束关系,即形成特定的编队队形。其中,梯行队形常用于攻击;“长龙”队形常用于轰炸、侦察、空投以及夜间截击;“一”字队形常用于宽大正面搜索;菱形队形常用于摧毁点、线状目标[16]。

4) 僚机节点扩展的约束

为保证长机在长-僚模式下的绝对领导,也为降低同时求解多机航迹的难度,首先利用改进的RRT算法求解出长机的航迹,并以此为基础扩展僚机的节点,具体通过降低近似时间段内采样点重合度的方式进行调节。

(10)

(11)

式中,xr为Zrand的横坐标;n0为x方向的单位向量。求解方程可得lx,并根据已知的长机航迹得到此时长机的位置(lx,ly)。当xI-xG≈0或xI-xG≪yI-yG时,可先求长机的纵坐标ly,其原理与(11)式类似。

利用僚机节点扩展的约束可以降低僚机与长机碰撞的可能,为下文所提的防碰撞约束打下基础。

5) 编队重构的时序约束

根据任务需求的不同,编队完成重构的时序要求也不同,具体包含同时到达、等间隔顺次到达和非等间隔顺次到达等。其中,同时到达新的队形有助于编队实施下一个作战任务,充分发挥协同作战的优势[20]。下面以同时到达为时序约束进行分析。

(12)

若保证同时到达,则僚机的路径长度应保证t在其到达时间的区间的交集内,具体约束见(13)式

(13)

等间隔顺次到达和非等间隔顺次到达等时序约束与上述过程类似。

6) 编队内部的防碰撞约束

为防止编队内部的碰撞,应检测飞行过程中各时刻的机间距。具体来讲,假设在修正后的航迹上每隔步长Δn进行一次采样,长机、僚机的采样个数依次记为n1、n2…nv;同理,时刻T下的采样点坐标记为[xi(T),yi(T)](i=1,2,…v)。由此可计算采样点的比例系数kij

∀i、j=1,2,…v且i≠j

(14)

则τ时刻各无人机间距|dij|τ可由(15)式得

|dij|τ=

∀i，j=1,2,…v且i≠j,0<τ≤t

(15)

式中,[ ]代表取整运算,则此时约束条件可表示为:

|dij|τ>dmin

(16)

7) 编队外部的防碰撞约束

以3.1节威胁区模型为基础,在重构过程中,每架飞机的位置到威胁区中心(aj,bj)的距离都应满足下式

[xi(T)-aj]2+[yi(T)-bj]2≥(λ*rj)2,

∀j=1,2…,m,1≤i≤v,0

(17)

式中,λ为安全系数,通常取λ=1.2～1.5。

4 仿真与试验验证

4.1 编队重构试验

已知编队重构的规划空间可以表示为集合{(x,y)|0≤x≤1 000,0≤y≤1 000},1架长机和2架僚机构成编队。初始队形构成“一”字型,用于横向搜索,长、僚机坐标分别为

[p1-int,p2-int,p3-int]T=

[(100,0),(0,0),(200,0)]T

在飞行过程中,3架飞机允许的空速范围为20～25 m/s,且受风的影响很小(可忽略不计),最大航迹滚转角为μmax=0.6 rad。设规划空间内存在三处随机生成的威胁区,表示为obsi=(ai,bi,ri)。现要求编队由原队形迅速变换成“长龙”队形,以进入备战状态,且各飞机同时抵达,忽略飞机进入目标队形时航向严格一致的约束,目标点具体坐标为

[p1-goal,p2-goal,p3-goal]T=

[(800,500),(800,400),(800,600)]T

其中随机生成的威胁区为

[obs1,obs2,obs3]T=

[(300,150,30),(500,300,45),(700,350,70)]T

以上述条件为基础,从飞行安全角度出发,取dmin=40 m,检测步长Δn=0.1 m,最小航迹段长度lmin=15 m,由公式(9)及文献[21]可确定此时节点扩展步长L=20 m较为合理;另外,外部防碰撞系数λ=1.2,最小转弯半径由(3)式求得Rmin≈120 m;根据参考文献[9]及多次试验室仿真发现,RRT算法中节点采样的概率取经验值P=0.5较为合理。

在MATLAB R2013a中进行仿真,计算机配置为:Intel酷睿i7处理器,主频3.60 GHz,内存32 G,64位win7操作系统。

下面首先从重构方法的可行性及无人机的安全2个方面对本文所提重构方法的结果进行分析,具体见表1。

表1 RRT算法求解的编队重构方案

从表1可以看出,3架飞机的规划速度均在设定范围内,并且在重构指令下达后的38.38 s同时到达新的队形位置,满足所要求的时序约束,实现了编队重构。图6展示了重构过程的航迹图,从图中看出,多余节点的去除,使得规划航迹大大缩短,并且裁剪后的航迹均满足过渡航迹存在的条件,通过过渡航迹引导,使得航迹平滑连续,为航迹的跟踪提供了有利保障。

下面分析重构过程的安全性。图7展示了重构过程中机间距的变化,结合图6和图7可以看出,利用RRT算法所规划的航迹与外部威胁区没有相交,满足与外部威胁之间无碰撞的约束;同时,虽然各飞机的航迹有些重合,但是经过空间内同一位置的时间并不一致,3架飞机在同一时刻的间距始终在40 m以上,满足机间安全距离的约束,没有内部碰撞的危险,利于无人机的安全飞行。

图6 RRT算法规划的航迹

接下来,为验证本文所提重构方法的优势,在相同仿真条件下,采用文献[6]中提出的改进的粒子群算法以及最优控制理论中常用的伪谱法[24]等2种方法进行对比试验,其中粒子群算法的参数与文献[6]保持一致,而伪谱法则基于GPOPS-Ⅱ工具包实现。2种方法所规划的重构方案如图8～9所示。

图7 编队重构中的飞机间距图 图8 粒子群算法规划的航迹 图9 伪谱法规划的航迹

从试验结果可以看出,粒子群算法和伪谱法均能实现同等约束条件下的编队队形重构,且航迹较为光滑,利于无人机实现航迹跟踪,具备一定的可行性。下面通过具体的试验数据(见表2),对比3种重构方法。

表2 3种编队重构方法对比

表2中数据均为各算法运行50次后所取得平均值。从表中可以看出伪谱法计算的到达时间最小(37.13 s),即求解精度最高,但耗时最长(34.83 s),计算效率较低;RRT算法的精度比伪谱法低,高于粒子群算法,但计算时间分别是二者的7.1%和12.1%;而粒子群算法因需要不断调整Dubins轨迹弧线段的半径而导致搜索效率降低,同时由于航迹构成的特殊性,其重构方案中的各机航迹最长,相应的到达时间也最长;另外三者的最小机间距均在40 m以上,最小障碍物间距均大于0 m,即满足重构过程中的安全性。

综上,本文所提的基于RRT算法的重构方法可以较好地满足编队飞行的安全需求,且更适用于对求解效率要求较高的场景,同时求解精度较高,对实际工程有一定的指导性。

4.2 过渡航迹的效果验证

针对本文对传统RRT算法所做改进,利用文献[19]所述的引导长度自适应的航迹跟踪算法进行试验,主要考察过渡航迹的跟踪效果。试验用无人机如图10所示。其翼展2.4 m,机身长度1.6 m,起飞重量6.4 kg,动力来源于电机驱动的螺旋桨。飞机为常规式布局,翼型较厚,适宜低速飞行。

图10 试验用无人机

试验前,由4个预设的航路点围成一个边长为500 m、邻角为0.75π rad(0.25π rad)的菱形,并将其作为规划航迹,其中4个航路点自西南角开始,逆时针依次记为A、B、C、D,用来模拟RRT算法中生成的节点。

飞行试验时,有大约3 m/s的偏南风,设定期望空速恒为15 m/s,允许最大航迹滚转角μmax=0.6 rad,相应的最小转弯半径Rmin≈50 m,为安全起见,实际飞行时取Rmin=70 m,其他试验参数与文献[19]保持一致。

试验共进行2个架次,在每个架次中,待飞行高度达到约120 m上空时,地面站引导无人机逆时针依次经过A～D航路点,完成一圈飞行后引导无人机下降并对其进行捕网回收。其中,第一个架次不加过渡航迹,利用跟踪算法中引导线变化自行转弯,第二个架次加入过渡航迹引导,令无人机跟踪过渡航迹完成转弯。飞行结束后保存并记录试验数据,截取以航路点A为起点到飞机开始下降的一段数据进行分析,得到航迹跟踪图如图11所示:

图11 有无过渡航迹引导的航迹跟踪对比图

从图11可以看出,未加过渡航迹进行引导飞行时,虽然在拐钝角弯时(如经过B航路点时)能保持较好的跟踪精度,但在拐锐角弯(如经过C航路点时)则会出现十分明显的振荡现象;加入过渡航迹引导时,虽然受偏南风影响会在经过C航路点时出现一定的飞行误差,但总体而言,能实现较为平稳的转弯,不需要在直线飞行段进行长时间姿态调节,跟踪精度更高。

飞机航迹滚转角的变化情况,是衡量飞行稳定性的一个重要指标,截取由BC段向CD段转弯时航迹滚转角的变化进行分析,如图12所示。图12中,未加过渡航迹的μ值相比过渡航迹的μ值变化更迟(滞后大约10 s),且调节时间更长(过渡航迹只用了13 s完成转弯,而无过渡航迹时持续了约25 s),甚至持续到节点C时仍未调整平稳。另外,由于按过渡航迹飞行时,设定的转弯半径略大于无人机实际所允许的Rmin,因此其在转弯段的μ值并没有长时间维持在μmax,而未加过渡航迹引导时,飞机则长时间处于μmax下飞行,这也从另一个角度验证了1.3节关于转弯段产生振荡原因的假设。

图12 有无过渡航迹引导的航迹滚转角对比图

综上,过渡航迹利于飞机平稳的跟踪,适用于解决诸如RRT算法生成的多节点机动转弯的问题,能为飞行安全提供有效保障。

5 结 论

本文基于快速随机树算法,对二维平面内多无人机编队的重构问题进行了研究。分析和试验的结果表明:

1) RRT算法具有搜索范围广、效率高的特点,适用于解决包含威胁区和动力学约束条件的运动规划问题,以此为基础可以拓展到多无人机编队的重构方法当中。

2) 通过多余节点去除、过渡航迹生成等修正策略,提高了RRT算法所规划航迹的可跟踪性。其中,过渡航迹的引入能避免因转弯时滞而造成的期望转弯转弯半径与无人机最小转弯半径不匹配的问题,相比非过渡航迹有较为明显的优势。

3) 所提的编队重构方法以无人机自身动力学、编队协同以及防碰撞等约束为基础,结合RRT算法可实现诸如同时到达等时序要求的编队重构,且方案安全可行。

4) 通过与粒子群及伪谱法等重构方法对比,所提重构方法在安全性的前提下具有较高的计算效率和求解精度。将提出的重构方法利用飞行试验进行验证并拓展到三维复杂环境中、优化重构完成的时间以及提高动态威胁下在线重构能力,是下一步值得研究的内容。