CN105700549A - 一种基于序列小生境粒子群算法的无人机多航迹规划方法 - Google Patents

Abstract

本发明涉及一种基于序列小生境粒子群算法的无人机多航迹规划方法，属于无人机多航迹规划技术领域。该方法首先对所需规划的问题进行建模，构建航迹代价函数以及约束条件；使用PSO算法对模型进行第一次规划得到第一组航迹；结合序列小生境技术更新当前最优航迹附近的代价函数模型，增大最优航迹小生境内其它方案的代价值；然后再使用PSO算法对更新后的模型进行下一次规划，获得次优航迹；重复上述两个步骤便可将最初构建的代价函数模型的最优航迹及次优航迹依次找出，当找到足够数量的航迹时，算法终止并输出满足任务要求的多航迹结果。本发明可更好地应对由实际环境变化和未知性导致的单条航迹不可行问题，并能为多无人机协同任务提供预先航迹。

Description

一种基于序列小生境粒子群算法的无人机多航迹规划方法

技术领域

本发明涉及一种基于序列小生境粒子群算法的无人机多航迹规划方法，属于无人机多航迹规划技术领域。

背景技术

无人机(UnmannedAerialVehicle,UAV)航迹规划问题是在满足飞行性能以及地形、威胁等约束条件下，为无人机规划出一条使飞行航程，到达时间，燃料消耗等代价相对较小的飞行航迹，保证其圆满完成飞行任务。在实际的航迹规划过程中，由于实际环境的复杂性，无人机很难事先获得全部的威胁和环境信息，而且这些因素也可能会实时发生变化，这可能导致预先规划的单条最优航迹在无人机执行任务时无法使用。另一方面，当多机协同执行任务时，往往需要规划多条不同的航迹，从不同的方向到达目标区域执行任务。要解决上述问题一种有效的途径就是使用多航迹规划方法，预先规划出多条航迹，然后在执行任务时根据不同需要临时决定适合的航迹或多机协同航迹。

无人机的多航迹规划方法一般直接采用多峰值函数优化的方法从而生成多条相对较优的航迹。目前对于此类多峰值函数的优化问题多采用小生境技术结合智能进化优化算法进行求解。小生境技术(niche)的基本思想是将生物学中的小生境概念应用于进化计算中，它模拟生态平衡中的一种仿生技术，在大种群中形成若干个相互独立的小的子种群，即小生境。在进化过程中所有的个体只在自己所在的小生境内部进化，追逐出不同的极值点从而得到各自的最优解。而本发明中采用序列小生境技术结合粒子群优化算法，能够有效而且相对高效的对无人机多航迹规划问题进行求解。

粒子群优化算法(ParticleSwarmOptimization,PSO)是一种模拟鸟类飞行过程中迁徙和群聚行为的智能优化算法。在PSO算法中，每个优化问题的备选解假设为n维搜索空间中的一个点，称为“粒子”。粒子的优劣程度通过由代价函数响应得到适应值来度量，同时每个粒子都会有一个速度决定它们飞行的方向和距离。粒子根据记忆追踪两个极值在解空间内进行搜索：一个是粒子本身找到的最优解pBest，另一个是整个种群找到的最优解gBest。第i粒子的第j维位置和速度的更新公式如下

$v_{ij}^{(t+1)}={\mathrm{\ω}}^{\left(t\right)}{v}_{ij}^{\left(t\right)}+c_1{r}_1({\mathrm{pBest}}_{ij}^{\left(t\right)}-x_{ij}^{\left(t\right)})+c_2{r}_2({\mathrm{gBest}}_{ij}^{\left(t\right)}-x_{ij}^{\left(t\right)})$

$x_{ij}^{(t+1)}=x_{ij}^{\left(t\right)}+v_{ij}^{(t+1)}$

其中，t为粒子群当前代数；r₁和r₂为[0,1]间的随机数；c₁是粒子跟踪自身历史最优值的权重系数；c₂是粒子跟踪群体最优值的权重系数；ω是惯性权重系数，惯性权重系数越大代表粒子越倾向于执行全局搜索，反之则代表粒子越倾向于局部搜索，故而惯性权重随迭代次数的增加而减小，其更新公式为

ω^(t+1)＝ω^(t)×ω_decay

其中ω_decay为惯性权重衰减系数。

序列小生境技术(sequentialnichetechnique,SNT)的主要思想是优化算法在搜索空间找到一个最优解后，则认为该最优解的附近区域为一个小生境区域。人为修改小生境区域内的函数模型，使其在之后的迭代优化中不再吸引粒子，迫使优化算法去寻找未被发现的局部最优解。再依次生成这样的小生境，直到所需的局部最优解依次被找到。

发明内容

本发明针对标准小生境技术在进行无人机多航迹规划时存在计算量大与时效性较差的问题，提出了基于序列小生境技术PSO算法的无人机多航迹问题规划方法，并设计了针对此类问题的小生境半径确定方法。

本发明提出的方法首先对所需规划的问题进行建模，构建航迹代价函数以及约束条件；使用PSO算法对模型进行第一次规划得到第一组航迹；结合序列小生境技术更新当前最优航迹附近的代价函数模型，增大最优航迹小生境内其它方案的代价值；然后再使用PSO算法对更新后的模型进行下一次规划，获得次优航迹；重复上述两个步骤便可将最初构建的代价函数模型的最优航迹及次优航迹依次找出，当找到足够数量的航迹时，算法终止并输出满足任务要求的多航迹结果。

本发明的目的是通过下述技术方案实现的。

一种基于序列小生境粒子群算法的无人机多航迹规划方法，包括步骤如下：

步骤1获取无人机飞行环境设定以及无人机飞行性能参数；

步骤2构建航迹规划求解模型，包含以下两个步骤；

步骤2.1确定粒子的编码方式

基于序列小生境PSO算法求解无人机多航迹规划问题过程中，种群中的每个粒子表示一条备选航迹，每条航迹又包括一定数量的航迹点，故而每一个粒子x表征一组航迹点坐标，例如

x＝(x_start，y_start，x₁，y₁，...，x_n，y_n，x_gool，y_gool)

其中(x_start，y_start)、(x_gool，y_gool)为已知的起始点和目标点坐标；n为待规划的航迹点数。

步骤2.2构造的代价函数包括航迹长度、平均飞行高度等；约束条件包括转弯角约束、爬升角约束、最短航迹段约束、威胁约束与地形约束等。

步骤3航迹规划问题的环境初始化设置，包括规划区域边界，起始点和目标位置，威胁位置及其大小，以及所需规划的航迹数目K，并令已规划航迹数量i＝0；

步骤4PSO算法初始设置，包括最大迭代次数与种群规模等；本发明设计了一种针对多航迹规划问题的小生境半径计算方法，如下

$r=P\×\sqrt{S}/(2\×D)$

式中，D为设计变量的维度；P为每条航迹的航点个数；S为规划区域的面积大小。

步骤5使用拉丁超方试验设计方法生成初始粒子种群；

步骤6判断i是否等于0。若是转步骤7；否则转步骤10

步骤7计算每个粒子的代价函数值，保存pBest和gBest，及其相应位置；

步骤8根据pBest和gBest更新粒子的速度矢量，并根据速度矢量更新粒子位置；

步骤9判断粒子是否收敛，若是，输出最优航迹解x，且令i＝i+1，并记录此解航迹为s_i；否则转步骤7；

步骤10判断i是否等于K。若是，算法终止并输出多航迹结果；否则按以下步骤修改解航迹s_i附近小生境半径区域r内的代价函数值，并返回步骤7。

代价函数的更新公式如下

∏_n+1(x)＝∏_n(x)×G(x，s_n)

式中，∏_n+1(x)为搜索第n+1个航迹时使用的代价函数；∏_n(x)为搜索第n个最优航迹时使用的代价函数；G(x，s_n)为指数缩减函数，其表达式如下

$G(x,s_n)=\left\{\begin{array}{cc}\exp \left(lg\right(m)\×\frac{r-d(x,s_n)}{r}),& d(x,s_n)\≤r\\ 1,& d(x,s_n)\≤r\end{array}\right.$

式中m为缩减系数，应取得足够大，才能保证代价函数值在小生境范围内显著改变而在下一次迭代中不再吸引粒子，根据经验m建议取值为100。式中距离d(x,s_n)表示当前航迹和之前找到的较优航迹s_n之间的距离，d(x,s_n)的计算步骤如下

步骤10.1对起始点到目标点的x坐标区间进行P+1等分；

步骤10.2在步骤10.1的等分线上，分别对之前局部最优解航迹s_n和当前航迹x进行插值计算，得到两组航迹特征点；

步骤10.3根据上述两组航迹特征点，计算两组点间对应的欧式距离，并求和得到d(x,s_n)。

至此，就实现了基于序列小生境粒子群算法的无人机多航迹规划过程。

有益效果

将序列小生境技术与PSO算法相结合应用于无人机多航迹规划，可规划出多条可行较优航迹。规划出的航迹能够合理规避威胁，且满足飞行性能约束，并具有较短的航程。由于采用的是序列规划的方法，所以能够有效控制算法的计算时间，避免了标准的小生境技术导致的多条航迹重复进入同一小生境而难以收敛的情况。同时，由于小生境半径的合理设计，规划出的多航迹在空间上分布较为离散，可以更好地应对由实际环境变化和未知性导致的单条航迹不可行问题，并能为多无人机协同任务提供预先航迹。

附图说明

图1为本发明的基于序列小生境技术结合粒子群算法无人机多航迹规划方法流程图；

图2为具体实施方式中K＝3时得到多航迹结果图；

图3为具体实施方式中K＝4时得到多航迹结果图；

图4为具体实施方式中K＝5时得到多航迹结果图；

图5为具体实施方式中K＝3时各条航迹代价值收敛的过程；

图6为具体实施方式中K＝4时各条航迹代价值收敛的过程；

图7为具体实施方式中K＝5时各条航迹代价值收敛的过程。

具体实施方式

为了更好的说明本发明的目的与优点，下面通过无人机多航迹规划实例，结合附图与表格对本发明做进一步说明，并通过与标准小生境结合粒子群算法的多航迹规划方法结果进行比较，对本发明的综合性能进行验证分析。

一种基于序列小生境粒子群算法的无人机多航迹规划方法，其步骤如图1所示：

步骤1获取无人机飞行环境设定。其中包括规划的起始点和目标点，飞行区域大小，威胁位置及大小，飞行器的最大转弯角θ_max以及最短航迹段长度l_min。

在本例中，设置飞行区域为为45km×45km的方形区域，规划的起始点为(5000，5000)，目标点为(40000，40000)，飞行区域内存在三个圆形威胁，位置分别为(1000010400)、(2000030000)、(2800018900)；威胁半径分别为2000m、2500m、2400m。最大转弯角为90°，最短航迹段长度为4000m。

步骤2无人机航迹规划问题建模。航迹规划问题的模型可分为代价函数和约束条件两个部分，构建过程如下：

步骤2.1无人机航迹规划时考虑的主要代价为航程代价，以使在满足约束条件的情况下尽可能缩短飞行距离，降低油耗。航程代价函数为各航迹点之间的航段长度l_i之和，其表达式如下

$C_{length}=\underset{i=1}{\overset{n+1}{\Σ}}{l}_i$

步骤2.2由于无人机自身性能的局限以及实际情况中存在的威胁区域无法飞行，所以在航迹规划中需对无人机的航迹进行一定的约束限制，主要的几个约束条件如下：

威胁约束。由于威胁区域内可能存在着地形威胁、雷达威胁等，所以无人机的飞行航迹需要绕开这些区域。设每段航迹穿越威胁区域的长度为L_i，则该约束可表达为

$\underset{i=1}{\overset{n+1}{\Σ}}{L}_i\≤0$

转弯角约束。由于无人机机动性能的限制，在每个航点上航迹的转弯角不能过大，设最大转弯角为θ_max，该约束可表示为：

θ_i≤θ_maxi＝1，2，...，n

最小航迹段长度约束。无人机在改变飞行方向前，需要保证一定的直飞距离。设该距离为L_min，则该约束可表示为：

l_i≥L_mini＝1，2，...，n+1

综合本步骤的内容，航迹规划问题的模型可以描述为，在满足约束条件(9)、(10)和(11)的情况下，获得多个使代价函数值尽可能小的解。

步骤3设置每条航迹的航点个数P＝3，设置需要规划的航迹数目K，令K分别等于3、4、5，做三次仿真实验。

步骤4设置PSO算法的参数，最大迭代次数为150次，种群数量为20×P，惯性权重系数ω＝0.796，c₁＝1.496，c₂＝2，惯性权重衰减系数 _decay＝0.996；计算小生境半径r

$r=P\×\sqrt{S}/(2\×D)$

针对本例，P＝3，S＝2025km²，D为6，故小生境半径r＝11.25km；

步骤5使用拉丁超方初始化粒子种群；

步骤6判断i是否等于0。若是转步骤7；否则，转步骤10；

步骤7计算每个粒子即每组航迹的代价值，保存个体值pBest和种群最优值gBest，及其相应位置；

步骤8根据pBest和gBest更新粒子的速度矢量，并根据速度矢量更新粒子位置；

步骤9判断粒子是否收敛，若是，输出最优解航迹x，且令i＝i+1，并记录此最优解航迹为s_i；否则转步骤7；

步骤10判断i是否等于K。若是，算法终止并输出多航迹结果，画出多航迹的结果图；否则修改最优解航迹s_i附近小生境半径区域r内的代价函数值返回步骤7。

利用本发明所述的基于序列小生境粒子群优化算法无人机多航迹规划方法，为无人机规划出多条较优航迹，规划得到航迹能够有效回避环境中存在的威胁区域并且满足飞行约束的多航迹结果，三次仿真试验的多航迹结果如图2、图3和图4所示。图中圆圈代表威胁区域，黑点表示航迹点。在优化过程中每条航迹代价值的收敛过程如图5、图6和图7所示。仿真试验的具体数据如表1所示：

表1仿真试验数据

为了体现本发明的优势，对同样的环境设定下，分别用本发明方法和传统小生境结合粒子群算法规划4条不同的航迹，做100次的仿真试验，得到如下的对比结果

表2SNT和niche分别结合PSO对多航迹优化结果比较

算法	平均规划时间(s)	航迹平均代价	模型调用次数
				SNT&PSO	19.52	59.03	62988
niche&PSO	38.38	58.76	2978460

由仿真试验数据可知，序列小生境粒子群算法对多航迹问题的优化效率要明显高于标准小生境粒子群算法。这是由于序列小生技术避免了标准小生境技术与PSO结合方法在航迹数目增加的情况下，PSO陷入同一小生境搜索可能性增大的问题，而这一问题将导致优化计算反复迭代，计算时间大大增加。而且规划出的多航迹在空间上分布较为离散，说明本发明中确定小生境半径r的方法合理有效。

Claims (4)

1.一种基于序列小生境粒子群算法的无人机多航迹规划方法，其特征在于包括步骤如下：

步骤1获取无人机飞行环境设定以及无人机飞行性能参数；

步骤2构建航迹规划求解模型，包含以下两个步骤；

步骤2.1确定粒子的编码方式

基于序列小生境PSO算法求解无人机多航迹规划问题过程中，种群中的每个粒子表示一条备选航迹，每条航迹又包括一定数量的航迹点，故而每一个粒子x表征一组航迹点坐标；

步骤2.2构造的代价函数包括航迹长度、平均飞行高度；约束条件包括转弯角约束、爬升角约束、最短航迹段约束、威胁约束与地形约束；

步骤3航迹规划问题的环境初始化设置，包括规划区域边界，起始点和目标位置，威胁位置及其大小，以及所需规划的航迹数目K，并令已规划航迹数量i＝0；

步骤4PSO算法初始设置，包括最大迭代次数与种群规模；并通过设计，计算得到所需使用的小生境半径r；

步骤5使用拉丁超方试验设计方法生成初始粒子种群；

步骤6判断i是否等于0，若是转步骤7；否则转步骤10；

步骤7计算每个粒子的代价函数值，保存pBest和gBest，及其相应位置；粒子根据记忆追踪两个极值在解空间内进行搜索：一个是粒子本身找到的最优解pBest，另一个是整个种群找到的最优解gBest；

步骤8根据pBest和gBest更新粒子的速度矢量，并根据速度矢量更新粒子位置；

步骤9判断粒子是否收敛，若是，输出最优航迹解x，且令i＝i+1，并记录此解航迹为s_i；否则转步骤7；

步骤10判断i是否等于K；若是，算法终止并输出多航迹结果；否则修改更新解航迹s_i附近小生境半径区域r内的代价函数值，并返回步骤7；

至此，就实现了基于序列小生境粒子群算法的无人机多航迹规划过程。

2.根据权利要求1所述的一种基于序列小生境粒子群算法的无人机多航迹规划方法，其特征在于：所述步骤4中，针对无人机的多航迹规划问题设计了一种小生境半径r的确定方法，确定半径的公式如下：

$r=P\×\sqrt{S}/(2\×D)$

式中，D为设计变量的维度；P为每条航迹的航点个数；S为规划区域的面积大小。

3.根据权利要求1所述的一种基于序列小生境粒子群算法的无人机多航迹规划方法，其特征在于，所述步骤10中代价函数的更新公式如下：

${\mathrm{\Π}}_{n+1}\left(x\right)={\mathrm{\Π}}_n\left(x\right)\×G(x,s_n)$

式中，Π_n+1(x)为搜索第n+1个航迹时使用的代价函数；Π_n(x)为搜索第n个最优航迹时使用的代价函数；G(x，s_n)为指数缩减函数，其表达式如下：

$G(x,s_n)=\left\{\begin{array}{cc}\exp \left(\lg \right(m)\×\frac{r-d(x,s_n)}{r}),& d(x,s_n)\≤r\\ 1,& d(x,s_n)\≤r\end{array}\right.$

式中m为缩减系数，应取得足够大，才能保证代价函数值在小生境范围内显著改变而在下一次迭代中不再吸引粒子，根据经验m建议取值为100；式中距离d(x,s_n)表示当前航迹和之前找到的较优航迹s_n之间的欧式距离。

4.根据权利要求3所述的一种基于序列小生境粒子群算法的无人机多航迹规划方法，其特征在于，所述步骤10中的d(x,s_n)的计算步骤如下：

步骤10.1对起始点到目标点的x坐标区间进行P+1等分；

步骤10.2在步骤10.1的等分线上，分别对之前局部最优解航迹s_n和当前航迹x进行插值计算，得到两组航迹特征点；

步骤10.3根据上述两组航迹特征点，计算两组点间对应的欧式距离，并求和得到d(x,s_n)。