多平台协同突防航路规划

贾正荣,卢发兴,王航宇

(海军工程大学 兵器工程学院,湖北 武汉 430033)

协同突防任务要求多个作战平台同时或尽可能同时到达指定的位置,并减少航行过程中被拦截的概率[1]。航路规划对于多平台的协同突防至关重要,相比于一般的协同任务,协同突防航路规划除了考虑包括航路可行性、障碍规避、冲突规避、航程优化之外,还需要考虑威胁规避,即尽可能减少被拦截的概率。另外,为形成饱和突防态势,协同突防一般要求平台同时到达目标位置,这一要求可以借鉴会和航路规划的相关方法。如文献[2]分析了多机器人在位置环境中协同探索的问题,研究给出了会和位置的选取方法,同时给出了到达会和位置的实时规划方法;文献[3]研究了欠驱动机器人的会和问题,给出了一种分布式的反馈控制策略,用于在离散空间内实时控制多机器人到达会和地点。现有研究大多关注在规避障碍的条件下给出可行的会和航路,较少涉及航路区域内存在威胁的情况,而在存在威胁的区域内执行会和任务广泛存在于实际应用中,有必要针对这种情况进行研究。

航路的表示方法对于航路规划至关重要。一般的航路表示方法主要有航路点航路[4-5]、DUBINS航路[6-7]、人工势场(artificial potential field,APF)航路[8]、插值型航路(或样条曲线航路)等。其中,插值型航路基于插值函数生成光滑的航路,可以准确预估航程,同时可以通过调整航路控制点的位置以规避障碍或威胁[9-10],而航路控制点可以基于各类进化算法进行求解[11-12]。可采用插值型航路进行求解协同突防航路规划问题。

综上,本文针对多平台协同突防航路规划问题进行研究,建立优化目标函数与约束条件,考虑多平台运动过程中所受威胁程度;同时给出多平台协同突防航路规划求解框架,通过控制点插值型航路构建航路描述与生成模型,基于粒子群优化方法(particle swarm optimization,PSO)进行航路参数求解。

1 问题描述

多个平台需要到达指定的目标位置以完成某一任务,平台的运动受到转弯半径的约束,即航路的曲率有界。平台在运动过程中可能被拦截,不同位置的被拦截概率不同。同时,空间中存在一定数量的障碍,平台的航路不能经过这些障碍。平台的初始位置给定,初始航向自由。

需要优化不同平台的航路,使处于不同初始位置的平台尽量同时到达目标位置,同时减少平台的航程,并降低累积的被拦截可能性。

协同突防航路规划如图1所示,图中平面内的威胁值通过等高线给出。为了尽可能同时到达目标位置,距离目标较远的平台-2应当选择近似直线的航路,虽然这样可能会增加被拦截的概率;而距离目标较近的平台-1则选择了较为弯曲的航路以增加航程;平台-3与平台-4则需要在规避障碍的同时选择与平台-1和平台-2航程接近的航路。

图1 协同突防航路规划示意图

可见,应当考虑的优化目标包括航路的长度(减少航程)、多平台航路长度差(尽可能同时到达目标位置)、累积威胁程度(使航路过程被拦截概率尽可能低),而航路规划需要考虑的因素包括转弯半径约束(使航路可行)、航路交叉约束(多平台航路间不能交叉)、障碍规避约束(航路不能经过给定的障碍)。事实上,在本文中航路的构建与优化求解与目标函数、约束条件是松耦合的,改变目标函数、约束条件,仍然可以使用航路的构建与优化求解方法得到航路规划方案。

2 协同突防问题的目标函数与约束条件

为便于分析,设平台数量为np,每个平台的航路为Li。

2.1 目标函数

目标函数为加权综合得到的单一指标,记为加权综合目标函数,该函数考虑了3个优化因素,分别为平均航路长度、航路长度标准差、累积威胁程度。

①加权综合目标函数。

设加权综合目标函数为J,则有:

(1)

②平均航路长度。

平均航路长度E(Li)即所有航路长度的均值,有:

(2)

式中:l(Li)为航路i的长度,由于每个平台对应唯一的航路,因此也使用下标i表示。

③航路长度标准差。

通过航路长度标准差描述多平台的航路长度差距,作为同时到达的指标,航路长度标准差σ(Li)是所有航路的标准差,有:

(3)

④累积威胁程度。

平台被拦截的概率通过累积威胁程度表示。本文定义累积威胁程度为航路曲线在威胁空间上的积分,给定空间内的威胁指标函数,其函数值与位置相关。根据实际问题特点,可以建立不同的累积威胁程度函数。

对于给定的威胁指标函数H(x,y),航路i的累积威胁程度为H(x,y)在曲线Li上的积分为

(4)

式中:dr为曲线积分微元。

在离散形式下,可以表示为

式中:j为实际航路曲线坐标点序号,(xi,jyi,j)T为离散形式下平台i的第j个航路点,n1为离散形式下航路点的数量。

2.2 约束条件

①合理航路的判断。

合理的航路即满足转弯半径约束,不与其他航路交叉,且不经过任意障碍的航路。航路的合理性判断需要依次进行转弯半径判断、航路交叉判断以及障碍冲突判断。

②转弯半径判断。

对于得到的实际航路Li,计算航路上每个位置(xi,jyi,j)T处的曲率半径ρi,j,有:

(5)

式中,一阶导数与二阶导数可以通过数值方法得到。

设平台的最小转弯半径为rmin,若有:ρi,j≥rmin,∀j,则航路Li通过转弯半径判断。

③航路交叉判断。

(6)

从而两线段的交点为以下线性方程的解:

(7)

若同时存在:

(8)

则交点同时位于两线段上而非线段的延长线上,此时两线段交叉,存在冲突。若对于任意2条航路的所有线段均不存在交叉,则不存在航路交叉。

④障碍冲突判断。

障碍通过有序的多边形顶点位置给出,因此航路与障碍的判断实质上也是插值航路点线段与障碍边界线段的相交判断,具体方法同③。

3 航路的构建与优化求解

实际的航路是连续的曲线,在描述与计算过程中存在一定的不便,因此通过控制点结合插值方法生成实际航路,而航路优化过程则直接求解航路控制点。在这种求解框架下,航路的优化与航路的构建、求解是相互解耦的,根据实际需求,当改变问题的目标函数、约束条件后,仍然可以通过这种航路构建、求解方法进行优化。

3.1 基于保形插值的航路生成

插值方法对于插值型航路的特征有主要的影响。本文采用分段保形二次插值方法(shape-preserving piecewise cubic interpolation method,SPCI),采用这种方法的优势在于能够得到一阶连续,且在控制点附近不会改变凹凸性的曲线,这种曲线更符合实际所希望的航路。如图2所示,相比于一般的非分段样条插值方法,SPCI方法得到的曲线不会在控制点之间震荡,更加符合实际情况。

图2 分段保形二次插值方法与一般样条插值方法的区别

由于采用PSO方法进行优化,参数粒子需要参考全局最优解,为了避免在优化求解过程中数值差异过大的情况,对航路控制点进行标准化。标准化过程即将实际坐标系下航路变换至标准化坐标系下,在标准化坐标系下平台初始位置为(0 0)T,目标位置为(1 0)T,如图3～图4所示。xψ和yψ为归一化后的坐标。

图3 标准化坐标系下的航路控制点

图4 实际空间中的航路控制点

对于任意一架平台,航路是连接初始位置与目标位置的曲线,设第i个平台的航路初始位置为Xps,i,目标位置为Xt。建立Xps,i的标准化坐标系,以Xps,i为原点,Xt-Xps,i向量为x轴。

设向量Xt-Xps,i的极坐标幅角为βi,标准化坐标系下第i个平台的控制点为Ψi,有:

(9)

式中:k为航路控制点序号,航路控制点数量为nc,此处的航路控制点是用于生成航路的参数(并非航路点),结合SPCI方法,可以得到最终的航路点。考虑到SPCI方法需要至少4个控制点,而平台初始位置与目标位置,即标准化坐标系下的(0 0)T与(1 0)T,已经提供了2个点,因此航路控制点数量nc≥2。

设实际坐标系下的控制点向量为Ti,则标准化坐标系下的控制点Ψi到实际坐标系下控制点Ti的变换为

(10)

基于控制点位置,通过SPCI生成实际的航路。SPCI方法在文献[13]中已经有详细的描述,文中不再赘述,并记SPCI算子为λ,对于实际坐标系下的控制点Ti,可以得到实际航路曲线Li为

Li=λ(Ti)

(11)

3.2 基于PSO的航路控制点优化

多平台的航路通过控制点基于插值方法生成,因此协同航路优化等同于优化调整控制点,对于这种难以得到梯度信息且优化参数为连续形式的复杂优化问题,可以通过PSO方法进行求解。PSO方法的优化过程为

(12)

式中:ξ为优化参数;V为优化参数的等效速度或等效梯度;p为序号;ω∈[0,1]为惯性系数,c1∈[0,1]与c2∈[0,1]为优化控制系数;r1与r2为在[0,1]内按照均匀分布随机生成的系数,为优化过程增加随机因素;ξl为局部最优解,即单个粒子更新过程中的最优解;ξg为全局最优解,即所有粒子的历史最优解。优化参数为所有航路控制点参数构成的向量,即ξ=(T1T2…Tnp)。

具体的优化流程包含2个部分,分别为粒子群初始化与粒子群优化。其中,粒子群初始化即生成给定数量且满足约束条件的粒子群,如图所示;粒子群优化即不断更新粒子群直至收敛并输出全局最优解,如图5～图6所示。

图5 粒子群初始化流程

图6 粒子群优化流程

在优化过程中,可能存在粒子更新后对应的航路不符合约束条件的情况,然而,由于粒子群初始化时已经生成了满足约束条件的初始解,每个粒子的历史局部最优解总是存在的,因此可以保证存在可行解。

4 仿真分析

为验证方法正确性并分析优化参数对于方法求解的影响,进行仿真分析。首先进行方法可行性分析;然后针对不同的场景,调整优化参数,分析优化参数取值不同时结果的差异。

分别在3个场景下进行协同航路规划,场景设置参数如表1所示。表中,nob为障碍数量,ntr为威胁区域数量。

表1 场景设置

在不同场景下进行协同突防航路规划,权值系数取0.3(平均航路长度)、0.3(航路长度标准差)、0.4(累积威胁程度),控制点数量nc取8个。得到的结果如图7～图9所示。

图7 场景1航路规划结果

图8 场景2航路规划结果

图9 场景3航路规划结果

不同场景下的3个优化指标以及加权综合目标函数值如表2所示。

表2 指标数值

图7～图9与表2的结果验证了方法的有效性,方法能够求解得到不相互冲突且规避障碍的可行航路;图中航路均能够一定程度地规避威胁区域;在同时到达方面,当航路标准差的权值为0.3时,航路长度标准差在1 km以下。特别地,由于场景3中没有障碍,因而得到航路规划结果的航路标准差为0.001 km。

5 结束语

本文提出了一种用于多平台协同突防航路规划的方法框架,方法特点主要包括:①给出了多平台协同突防航路规划的框架,框架中的目标函数、约束条件均可以根据实际需求更改而不影响求解流程;②除了考虑减少航程以及尽可能同时到达外,还考虑了航路上的累积威胁程度;③航路符合转弯半径约束,且一阶连续;④生成的航路不相互交叉,不与给定的障碍冲突。