CN119200642A - 一种基于采样的多无人机编队全局路径规划方法 - Google Patents

Abstract

一种基于采样的多无人机编队全局路径规划方法，包括：S1、构建全局栅格地图，给定编队起始状态、编队目标状态；S2、将编队起始状态加入到第一随机树作为根节点，将编队目标状态加入到第二随机树作为根节点；S3、采样获得新采样节点，并将迭代次数加1；S4、从新采样节点双向扩展两颗随机树；S5、判断扩展后两颗随机树是否完成连接，若完成连接，则通过区域修剪方法优化两颗随机树中节点的代价值；S6、判断是否达到终止运行条件，是则进入S7，否则执行S3；S7、若两颗随机树完成连接，则路径求解成功，获得路径规划结果，否则路径求解失败。本发明有效提高了复杂环境下基于采样的多无人机编队全局路径规划的求解速度和求解质量。

Description

一种基于采样的多无人机编队全局路径规划方法

技术领域

本发明涉及多无人机路径规划技术领域，特别涉及一种基于采样的多无人机编队全局路径规划方法。

背景技术

近年来，多无人机编队技术正在快速发展。多无人机编队凭借其视野范围大、载荷大以及弹性自适应能力强等优势，可完成单机不可企及的任务。然而，目前的编队技术大多考虑在理想空旷环境下，极大限制其应用范围。

多无人机在复杂环境下飞行，需有全局路径规划引导后续局部路径规划，否则容易陷入局部最优。然而，编队层级的全局路径规划相比单机的全局路径规划，其维度更高，难以获得较快的求解速率和较高的求解质量，这将极大降低多无人机编队的工作效率。基于以上难题，如何设计一种高效的多无人机编队全局路径规划方法对提升多无人机在复杂环境下的工作效率具有十分重要的意义。

发明内容

本发明提供了一种基于采样的多无人机编队全局路径规划方法，以解决背景技术所提到的技术问题。

为达到上述目的，本发明的技术方案是这样实现的：

本发明提供了一种基于采样的多无人机编队全局路径规划方法，包括如下步骤：

S1、构建全局栅格地图，给定编队起始状态S、编队目标状态G，并构建多无人机期望队形；

S2、将编队起始状态S加入到第一随机树T₁作为根节点，将编队目标状态G加入到第二随机树T₂作为根节点，迭代次数k置0；

S3、通过基于障碍物引导的高斯采样方法采样获得新采样节点qne_w，并将迭代次数k加1；

S4、根据全局栅格地图以及期望队形，从新采样节点q_new双向扩展第一随机树T₁和第二随机树T₂；

S5、判断扩展后两颗随机树是否完成连接，若已完成连接，则通过区域修剪方法优化两颗随机树中节点的代价值；

S6、判断是否达到终止运行条件，是则进入S7，否则执行S3；

S7、若第一随机树T₁、第二随机树T₂完成连接，则路径求解成功，获得最终路径规划结果，否则路径求解失败。

进一步地，所述S1具体包括如下步骤：

S11、构建全局栅格地图，给定编队起始状态S＝[x_s，y_s，z_s，1.0]^T、编队目标状态G＝[x_g，y_g，z_g，1.0]^T、最大试探次数M、邻居半径R、最大编队规模s_max、最小编队规模S_min、最大迭代次数N以及最大运行时间T_max，其中[x_s，y_s，z_s]^T∈表示编队起始状态的编队中心位置，表示编队目标状态的编队中心位置；T为矩阵的转置；

S12、构建n架无人机的期望队形[p_des，1 ^T，p_des，2 ^T，...，p_des，n ^T]^T，其中p_des，i∈表示第i架无人机在期望队形中的期望位置。

进一步地，所述S3具体包括如下步骤：

S31、通过随机采样获得随机采样节点q′_new，随机采样节点q′_new的编队中心位置在全局栅格地图内采样获得，随机采样节点q′_new的编队规模在[s_min，s_max]范围内采样获得；

S32、检查随机采样节点q′_new是否有效，如果无效，则将试探次数τ置0，并执行S33，否则执行S35；

S33、通过高斯采样方法采样获得高斯采样节点q″_new，高斯采样节点q″_new的编队中心在全局栅格地图范围内以随机采样节点q′_new的编队中心为均值，以σ²为方差进行高斯采样获得，q″_new的编队规模在[s_min，s_max]范围内通过随机采样获得，并将试探次数τ加1；

S34、判断高斯采样节点q″_new是否有效，若无效且试探次数τ未超过最大试探次数M，则跳至S33执行，若无效且试探次数τ超过最大试探次数M，则跳至S31执行，否则，将高斯采样节点q″_new更新为随机采样节点q′_new，并执行S35；

S35、将随机采样节点q′_new作为新采样节点q_new，并将迭代次数k加1。

进一步地，所述S4具体包括如下步骤：

S41、分别获得新采样节点q_new在第一随机树T₁和第二随机树T₂的第一邻居节点集合Ψ₁和第二邻居节点集合Ψ₂，其中两个邻居节点集合中的每个邻居节点q_neigh满足邻居节点q_neigh的编队中心到新采样节点q_new的编队中心距离小于邻居半径R；

如果第一邻居节点集合Ψ₁和/或第二邻居节点集合Ψ₂为空，则将对应随机树中与新采样节点q_new的编队中心距离最小的节点加入到第一邻居节点集合Ψ₁和/或第二邻居节点集合Ψ₂中，保证该集合非空；

S42、在第一邻居节点集合Ψ₁中寻找节点q_u，1，满足节点q_u，1到新采样节点q_new连接有效且通过节点q_u，1到新采样节点q_new的编队层级代价δ₁最小；同理在第二邻居节点集合Ψ₂中寻找节点q_u，2，满足节点q_u，2到新采样节点q_new连接有效且通过q_u2到q_new的编队层级代价δ₂最小；连接有效即两节点的连接不与障碍物发生碰撞；

S43、如果未找到节点q_u，1和q_u，2，则说明生长失败，结束S4，并跳至S3；如果只找到节点q_u，1，则跳至S44，如果只找到节点q_u，2，则跳至S45，否则跳至S46；

S44、将新采样节点q_new加入到第一随机树T₁的节点集合V₁中，将节点连接关系(q_u，1，q_new)加入到第一随机树T₁的节点连接关系集合E₁中，并令新采样节点q_new的代价η(q_new)＝δ₁，然后跳至S48；

S45、将新采样节点q_new加入到第二随机树T₂的节点集合V₂中，将节点连接关系(q_u，2，q_new)加入到第二随机树T₂的节点连接关系集合E₂中，并令新采样节点q_new的代价η(q_new)＝δ₂，然后跳至S48；

S46、比较编队层级代价δ₁和δ₂，如果δ₁≤δ₂，则将新采样节点q_new加入到第一随机树T₁的节点集合V₁中，将节点连接关系(q_u，1，q_new)加入到第一随机树T₁的节点连接关系集合E₁中，并令新采样节点q_new的代价η(q_new)＝δ₁，并把节点q_u，2标记为新采样节点q_new的连接点，否则将新采样节点q_new加入到第二随机树T₂的节点集合V₂中，将节点连接关系(q_u，2，q_new)加入到第二随机树T₂的节点连接关系集合E₂中，并令新采样节点q_new的代价η(q_new)＝δ₂，并把节点q_u，1标记为新采样节点q_new的连接点；

S47、将新采样节点q_new添加到交汇点集合Π，此时说明两颗随机树已完成连接；

S48、在新采样节点q_new所在的随机树中执行重连接操作，即对于新采样节点q_new除了其父节点的其他邻居节点q_neigh，判断η(q_new)+c(q_new，q_neigh)＜η(q_neigh)是否成立，如果成立，则在新采样节点q_new所在的随机树的节点连接关系集合中删除节点连接关系(q_p，q_neigh)，增加节点连接关系(q_new，q_neigh)，其中q_p为q_neigh的原父节点。

进一步地，所述S42中的编队层级代价δ₁的计算公式为：

δ₁＝η(q_u，1)+c(q_u1，q_new)

式中，η(.)表示第一代价函数；c(.)表示状态转移代价函数；且η(q_u，1)和c(q_u1，q_new)满足以下关系式：

其中，p_u1，i、p_new，i分别表示节点q_u1和新采样节点q_new对应的无人机i的位置；p_u1，i、p_new，i分别通过以下公式计算得到：

其中，s_u1、s_new分别为节点q_u1和新采样节点q_new的编队规模，X_u1、X_new分别为节点q_u1和新采样节点q_new的编队中心位置。

进一步地，所述S42中的编队层级代价δ₂的计算公式为：

δ₂＝η(q_u，2)+c(q_u2，q_new)

式中，c(q_u2，q_new)满足以下关系式：

其中，p_u2，i表示节点q_u2对应的无人机i的位置；p_u2，i通过以下公式计算得到：

其中，s_u2为节点q_u2的编队规模，X_u2为节点q_u2的编队中心位置。

进一步地，所述S5具体包括如下步骤：

S51、判断生长后两颗随机树是否完成连接，若未连接，结束S5并跳至S6；

S52、定义更新集合Q，将新采样节点q_new加入到更新集合Q中；

S53、从更新集合Q中取出节点q_cur；

S54、检测节点q_cur是否有祖父节点q_g，如果没有，则执行S56，否则判断祖父节点q_g到节点q_cur的连接是否有效，如果无效，则执行S56；如果有效，则执行S55；

S55、在节点连接关系集合E₁或节点连接关系集合E₂中删除q_cur与其父节点q_p的连接关系(q_p，q_cur)，增加连接关系(q_g，q_cur)；此时q_g已更新为q_cur的父节点；之后跳至S54；

S56、将新采样节点q_new的子节点都加入到更新集合Q中；

S57、如果更新集合Q不为空，则跳至S53，否则结束S5，并执行S6。

进一步地，所述S6中的终止运行条件为迭代次数k是否超过最大迭代次数N或算法达到最大运行时间T_max。

进一步地，所述S7具体包括如下步骤：

S71、判断第一随机树T₁、第二随机树T₂是否完成连接，如果未完成连接，则说明路径求解失败，退出S7；如果连接成功，则进入S72；

S72、在交汇点集合Π中找到节点q_f，使通过节点q_f的路径代价L_f最小；

S73、从节点q_f分别往节点q_f的父节点和其连接点方向回溯，得到一条连接编队起始状态和编队目标状态的编队全局路径，作为求解结果。

进一步地，所述S72中节点q_f和路径代价L_f的计算公式为：

L_f＝η(q_f)+η(q_f′)+c(q_f，q_f′)

其中，q_σ′为节点q_σ的连接点，此外节点q_σ也是上式中函数η(q_σ)+η(q_σ′)+c(q_σ，q_σ′)的自变量。q_f′为节点q_f的连接点。

本发明的有益效果：

1、本发明定义了随机树的节点状态及代价函数，使基于采样的方法可应用于多无人机编队全局路径规划问题。

2、本发明采用双向采样的方法和基于障碍物引导的高斯采样方法，使得基于采样的方法在复杂环境下仍能保持快速收敛特性，极大减少了路径规划的求解时间。

3、本发明提出一种区域修剪方法，可减少随机树中节点的冗余连接，减少了节点的代价，优化了随机树的结构，提高了路径规划的求解质量。

附图说明

图1为本发明的流程图；

图2为本发明实施例中多无人机全局编队路径规划的结果；

图3为本发明实施例中多无人机全局编队路径规划结果对比图。

具体实施方式

为了便于理解本发明，下面将参照相关附图对本发明进行更全面的描述。附图中给出了本发明的较佳的实施例。但是，本发明可以通过许多其他不同的形式来实现，并不限于本文所描述的实施例。相反地，提供这些实施例的目的是使对本发明的公开内容的理解更加透彻全面。

术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。在本发明的描述中，“多个”的含义是两个或两个以上，除非另有明确具体的限定。

除非另有定义，本文所使用的所有的技术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。本文中在本发明的说明书中所使用的术语只是为了描述具体的实施例的目的，不是旨在于限制本发明。本文所使用的术语“及/或”包括一个或多个相关的所列项目的任意的和所有的组合。

参照图1，本申请实施例提供了一种基于采样的多无人机编队全局路径规划方法，包括如下步骤：

S1、构建全局栅格地图，给定编队起始状态S、编队目标状态G，并构建多无人机期望队形；

S2、将编队起始状态S加入到第一随机树T₁作为根节点，将编队目标状态G加入到第二随机树T₂作为根节点，迭代次数k置0；

S3、通过基于障碍物引导的高斯采样方法采样获得新采样节点q_new，并将迭代次数k加1；

S4、根据全局栅格地图以及期望队形，从新采样节点q_new双向扩展第一随机树T₁和第二随机树T₂；

S5、判断扩展后两颗随机树是否完成连接，若已完成连接，则通过区域修剪方法优化两颗随机树中节点的代价值；

S6、判断是否达到终止运行条件，是则进入S7，否则执行S3；

S7、若第一随机树T₁、第二随机树T₂完成连接，则路径求解成功，获得最终路径规划结果，否则路径求解失败。

在一些实施例中，所述S1具体包括如下步骤：

S11、构建全局栅格地图，给定编队起始状态S＝[x_s，y_s，z_s，1.0]^T、编队目标状态G＝[x_g，y_g，z_g，1.0]^T、最大试探次数M、邻居半径R、最大编队规模s_max、最小编队规模s_min、最大迭代次数N以及最大运行时间T_max，其中 表示编队起始状态的编队中心位置，表示编队目标状态的编队中心位置；T为矩阵的转置；

S12、构建n架无人机的期望队形[p_des，1 ^T，p_des，2 ^T，...，p_des，n ^T]^T，其中 表示第i架无人机在期望队形中的期望位置(1≤i≤n)。

在一些实施例中，所述S2中的中的随机树T(第一随机树T₁、第二随机树T₂通称为T)定义如下：

随机树T定义为T＝(V，E)，其中V为节点集合，为节点连接关系集合。V中的节点q＝[X^T，s]^T可表示编队信息，其中表示编队中心位置，表示编队规模。节点q有效定义为：对于队形中任意一架无人机i，均满足其中X_free表示无碰撞区域，通过全局栅格地图获取，p_q，i为节点q对应的无人机i的位置，由以下式子计算获得

对于节点连接关系(u，v)∈E，表示节点u∈V和节点v∈V连接，且u为v的父节点，v为u的子节点。除了根节点，随机树中每个节点均有且仅有一个父节点。根节点代价为0，其他节点的代价可由代价函数计算获得，定义如下

η(v)＝η(u)+c(u，v)

其中为状态转移代价函数，p_u，i、p_v，i分别为u和v对应的无人机i的位置。

随机树中节点连接关系(u，v)有效定义为：对于队形中任意一架无人机i，p_u，i和p_v，i之间的连线不与障碍物发生碰撞。

在一些实施例中，所述S3具体包括如下步骤：

S31、通过随机采样获得随机采样节点q′_new，随机采样节点q′_new的编队中心位置在全局栅格地图内采样获得，随机采样节点q′_new的编队规模在[s_min，s_max]范围内采样获得；

S32、检查随机采样节点q′_new是否有效，如果无效，则将试探次数τ置0，并执行S33，否则执行S35；

S33、通过高斯采样方法采样获得高斯采样节点q″_new，高斯采样节点q″_new的编队中心在全局栅格地图范围内以随机采样节点q′_new的编队中心为均值，以σ²为方差进行高斯采样获得，q″_new的编队规模在[s_min，s_max]范围内通过随机采样获得，并将试探次数τ加1；

S34、判断高斯采样节点q″_new是否有效，若无效且试探次数τ未超过最大试探次数M，则跳至S33执行，若无效且试探次数τ超过最大试探次数M，则跳至S31执行，否则，将高斯采样节点q″_new更新为随机采样节点q′_new，并执行S35；

S35、将随机采样节点q′_new作为新采样节点q_new，并将迭代次数k加1。

在一些实施例中，所述S4具体包括如下步骤：

S41、分别获得新采样节点q_new在第一随机树T₁和第二随机树T₂的第一邻居节点集合Ψ₁和第二邻居节点集合Ψ₂，其中两个邻居节点集合中的每个邻居节点q_neigh满足邻居节点q_neigh的编队中心到新采样节点q_new的编队中心距离小于邻居半径R；

如果第一邻居节点集合Ψ₁和/或第二邻居节点集合Ψ₂为空，则将对应随机树中与新采样节点q_new的编队中心距离最小的节点加入到第一邻居节点集合Ψ₁和/或第二邻居节点集合Ψ₂中，保证该集合非空；

S42、在第一邻居节点集合Ψ₁中寻找节点q_u，1，满足节点q_u，1到新采样节点q_new连接有效且通过节点q_u，1到新采样节点q_new的编队层级代价δ₁最小；同理在第二邻居节点集合Ψ₂中寻找节点q_u，2，满足节点q_u，2到新采样节点q_new连接有效且通过q_u2到q_new的编队层级代价δ₂最小；连接有效即两节点的连接不与障碍物发生碰撞；

S43、如果未找到节点q_u，1和q_u，2，则说明生长失败，结束S4，并跳至S3；如果只找到节点q_u，1，则跳至S44，如果只找到节点q_u，2，则跳至S45，否则跳至S46；

S44、将新采样节点q_new加入到第一随机树T₁的节点集合V₁中，将节点连接关系(q_u，1，q_new)加入到第一随机树T₁的节点连接关系集合E₁中，并令新采样节点q_new的代价η(q_new)＝δ₁，然后跳至S48；

S45、将新采样节点q_new加入到第二随机树T₂的节点集合V₂中，将节点连接关系(q_u，2，q_new)加入到第二随机树T₂的节点连接关系集合E₂中，并令新采样节点q_new的代价η(q_new)＝δ₂，然后跳至S48；

S46、比较编队层级代价δ₁和δ₂，如果δ₁≤δ₂，则将新采样节点q_new加入到第一随机树T₁的节点集合V₁中，将节点连接关系(q_u，1，q_new)加入到第一随机树T₁的节点连接关系集合E₁中，并令新采样节点q_new的代价η(q_new)＝δ₁，并把节点q_u，2标记为新采样节点q_new的连接点，否则将新采样节点q_new加入到第二随机树T₂的节点集合V₂中，将节点连接关系(q_u，2，q_new)加入到第二随机树T₂的节点连接关系集合E₂中，并令新采样节点q_new的代价η(q_new)＝δ₂，并把节点q_u，1标记为新采样节点q_new的连接点；

S47、将新采样节点q_new添加到交汇点集合Π，此时说明两颗随机树已完成连接；

S48、在新采样节点q_new所在的随机树中执行重连接操作，即对于新采样节点q_new除了其父节点的其他邻居节点q_neigh，判断η(q_new)+c(q_new，q_neigh)＜η(q_neigh)是否成立，如果成立，则在新采样节点q_new所在的随机树的节点连接关系集合中删除节点连接关系(q_p，q_neigh)，增加节点连接关系(q_new，q_neigh)，其中q_p为q_neigh的原父节点。

在一些实施例中，所述S42中的编队层级代价δ₁的计算公式为：

δ₁＝η(q_u，1)+c(q_u1，q_new)

式中，η(.)表示第一代价函数；c(.)表示状态转移代价函数；且η(q_u，1)和c(q_u1，q_new)满足以下关系式：

其中，p_u1，i、p_new，i分别表示节点q_u1和新采样节点q_new对应的无人机i的位置；p_u1，i、p_new，i分别通过以下公式计算得到：

其中，s_u1、s_new分别为节点q_u1和新采样节点q_new的编队规模，X_u1、X_new分别为节点q_u1和新采样节点q_new的编队中心位置。

在一些实施例中，所述S42中的编队层级代价δ₂的计算公式为：

δ₂＝η(q_u，2)+c(q_u2，q_new)

式中，c(q_u2，q_new)满足以下关系式：

其中，p_u2，i表示节点q_u2对应的无人机i的位置；p_u2，i通过以下公式计算得到：

其中，s_u2为节点q_u2的编队规模，X_u2为节点q_u2的编队中心位置。

在一些实施例中，所述S5具体包括如下步骤：

S51、判断生长后两颗随机树是否完成连接，若未连接，结束S5并跳至S6；

S52、定义更新集合Q，将新采样节点q_new加入到更新集合Q中；

S53、从更新集合Q中取出节点q_cur；

S54、检测节点q_cur是否有祖父节点q_g，如果没有，则执行S56，否则判断祖父节点q_g到节点q_cur的连接是否有效，如果无效，则执行S56；如果有效，则执行S55；

S55、在节点连接关系集合E₁或节点连接关系集合E₂中删除q_cur与其父节点q_p的连接关系(q_p，q_cur)，增加连接关系(q_g，q_cur)；此时q_g已更新为q_cur的父节点；之后跳至S54；

S56、将新采样节点q_new的子节点都加入到更新集合Q中；

S57、如果更新集合Q不为空，则跳至S53，否则结束S5，并执行S6。

在一些实施例中，所述S6中的终止运行条件为迭代次数k是否超过最大迭代次数N或算法达到最大运行时间T_max。

在一些实施例中，所述S7具体包括如下步骤：

S71、判断第一随机树T₁、第二随机树T₂是否完成连接，如果未完成连接，则说明路径求解失败，退出S7；如果连接成功，则进入S72；

S72、在交汇点集合Π中找到节点q_f，使通过节点q_f的路径代价L_f最小；

S73、从节点q_f分别往节点q_f的父节点和其连接点方向回溯，得到一条连接编队起始状态和编队目标状态的编队全局路径，作为求解结果。

在一些实施例中，所述S72中节点q_f和路径代价L_f的计算公式为：

L_f＝η(q_f)+η(q_f′)+c(q_f，q_f′)

其中，q_σ′为节点q_σ的连接点，此外节点q_σ也是上式中函数η(q_σ)+η(q_σ′)+c(q_σ，q_σ′)的自变量。q_f′为节点q_f的连接点。

本发明在一复杂地图上完成了多无人机编队全局路径规划，规划的路径结果如图2所示。为了充分体现本发明中的高斯采样方法与区域修剪方法的优势，把仅基于双向采样的方法(BRRT*)、基于双向采样与高斯采样的方法(BRRT*-OGS)、基于双向采样与区域修剪的方法(BRRT*-RP)和基于双向采样、高斯采样与区域修剪的方法(BRRT*-OGS-RP)进行对比，其路径长度随时间的变化曲线如图3所示，可看出本发明提出的方法有效提高了复杂环境下基于采样的多无人机编队全局路径规划的求解速度和求解质量。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。并且，本发明各个实施方式之间的技术方案可以相互结合，但是必须是以本领域普通技术人员能够实现为基础，当技术方案的结合出现相互矛盾或无法实现时应当认为这种技术方案的结合不存在，也不在本发明要求的保护范围之内。因此，本发明的保护范围应以所述权利要求的保护范围为准。

Claims (10)

1.一种基于采样的多无人机编队全局路径规划方法，其特征在于，包括如下步骤：

S1、构建全局栅格地图，给定编队起始状态S、编队目标状态G，并构建多无人机期望队形；

S2、将编队起始状态S加入到第一随机树T₁作为根节点，将编队目标状态G加入到第二随机树T₂作为根节点，迭代次数k置0；

S3、通过基于障碍物引导的高斯采样方法采样获得新采样节点qne_w，并将迭代次数k加1；

S4、根据全局栅格地图以及期望队形，从新采样节点q_new双向扩展第一随机树T₁和第二随机树T₂；

S5、判断扩展后两颗随机树是否完成连接，若已完成连接，则通过区域修剪方法优化两颗随机树中节点的代价值；

S6、判断是否达到终止运行条件，是则进入S7，否则执行S3；

S7、若第一随机树T₁、第二随机树T₂完成连接，则路径求解成功，获得最终路径规划结果，否则路径求解失败。

2.根据权利要求1所述的多无人机编队全局路径规划方法，其特征在于，所述S1具体包括如下步骤：

S11、构建全局栅格地图，给定编队起始状态S＝[x_s，y_s，z_s，1.0]^T、编队目标状态G＝[x_g，y_g，z_g，1.0]^T、最大试探次数M、邻居半径R、最大编队规模s_max、最小编队规模s_min、最大迭代次数N以及最大运行时间T_max，其中 表示编队起始状态的编队中心位置，表示编队目标状态的编队中心位置；T为矩阵的转置；表示实数集；

S12、构建n架无人机的期望队形[p_des，1 ^T，p_des，2 ^T，...，p_des，n ^T]^T，其中 表示第i架无人机在期望队形中的期望位置。

3.根据权利要求2所述的多无人机编队全局路径规划方法，其特征在于，所述S3具体包括如下步骤：

S31、通过随机采样获得随机采样节点q′_new，随机采样节点q′_new的编队中心位置在全局栅格地图内采样获得，随机采样节点q′_new的编队规模在[s_min，s_max]范围内采样获得；

S32、检查随机采样节点q′_new是否有效，如果无效，则将试探次数τ置0，并执行S33，否则执行S35；

S33、通过高斯采样方法采样获得高斯采样节点q″_new，高斯采样节点q″_new的编队中心在全局栅格地图范围内以随机采样节点q′_new的编队中心为均值，以σ²为方差进行高斯采样获得，q″_new的编队规模在[s_min，s_max]范围内通过随机采样获得，并将试探次数T加1；

S34、判断高斯采样节点q″_new是否有效，若无效且试探次数τ未超过最大试探次数M，则跳至S33执行，若无效且试探次数τ超过最大试探次数M，则跳至S31执行，否则，将高斯采样节点q″_new更新为随机采样节点q′_new，并执行S35；

S35、将随机采样节点q′_new作为新采样节点q_new，并将迭代次数k加1。

4.根据权利要求3所述的多无人机编队全局路径规划方法，其特征在于，所述S4具体包括如下步骤：

S41、分别获得新采样节点q_new在第一随机树T₁和第二随机树T₂的第一邻居节点集合Ψ₁和第二邻居节点集合Ψ₂，其中两个邻居节点集合中的每个邻居节点q_neigh满足邻居节点q_neigh的编队中心到新采样节点q_new的编队中心距离小于邻居半径R；

如果第一邻居节点集合Ψ₁和/或第二邻居节点集合Ψ₂为空，则将对应随机树中与新采样节点q_new的编队中心距离最小的节点加入到第一邻居节点集合Ψ₁和/或第二邻居节点集合Ψ₂中，保证该集合非空；

S42、在第一邻居节点集合Ψ₁中寻找节点q_u,1，满足节点q_u,1到新采样节点q_new连接有效且通过节点q_u，1到新采样节点q_new的编队层级代价δ₁最小；同理在第二邻居节点集合Ψ₂中寻找节点q_u,2，满足节点q_u,2到新采样节点q_new连接有效且通过q_u2到q_new的编队层级代价δ₂最小；连接有效即两节点的连接不与障碍物发生碰撞；

S43、如果未找到节点q_u,1和q_u,2，则说明生长失败，结束S4，并跳至S3；如果只找到节点q_u,1，则跳至S44，如果只找到节点q_u,2，则跳至S45，否则跳至S46；

S44、将新采样节点q_new加入到第一随机树T₁的节点集合V₁中，将节点连接关系(q_u，1，q_new)加入到第一随机树T₁的节点连接关系集合E₁中，并令新采样节点q_new的代价η(q_new)＝δ₁，然后跳至S48；

S45、将新采样节点q_new加入到第二随机树T₂的节点集合V₂中，将节点连接关系(q_u，2，q_new)加入到第二随机树T₂的节点连接关系集合E₂中，并令新采样节点q_new的代价η(q_new)＝δ₂，然后跳至S48；

S46、比较编队层级代价δ₁和δ₂，如果δ₁≤δ₂，则将新采样节点q_new加入到第一随机树T₁的节点集合V₁中，将节点连接关系(q_u，1，q_new)加入到第一随机树T₁的节点连接关系集合E₁中，并令新采样节点q_new的代价η(q_new)＝δ₁，并把节点q_u，2标记为新采样节点q_new的连接点，否则将新采样节点q_new加入到第二随机树T₂的节点集合V₂中，将节点连接关系(q_u，2，q_new)加入到第二随机树T₂的节点连接关系集合E₂中，并令新采样节点q_new的代价η(q_new)＝δ₂，并把节点q_u,1标记为新采样节点q_new的连接点；

S47、将新采样节点q_new添加到交汇点集合Π，此时说明两颗随机树已完成连接；

S48、在新采样节点q_new所在的随机树中执行重连接操作，即对于新采样节点q_new除了其父节点的其他邻居节点q_neigh，判断η(q_new)+c(q_new，q_neigh)<η(q_neigh)是否成立，如果成立，则在新采样节点q_new所在的随机树的节点连接关系集合中删除节点连接关系(q_p，q_neigh)，增加节点连接关系(q_new，q_neigh)，其中q_p为q_neigh的原父节点。

5.根据权利要求4所述的多无人机编队全局路径规划方法，其特征在于，所述S42中的编队层级代价δ₁的计算公式为：

δ₁＝η(q_u,1)+c(q_u1，q_new)

式中，η(.)表示第一代价函数；c(.)表示状态转移代价函数；且η(q_u,1)和c(q_u1，q_new)满足以下关系式：

其中，p_u1，i、p_new，i分别表示节点q_u1和新采样节点qn_ew对应的无人机i的位置；p_u1,i、p_new，i分别通过以下公式计算得到：

其中，s_u1、s_new分别为节点q_u1和新采样节点q_new的编队规模，X_u1、X_new分别为节点q_u1和新采样节点q_new的编队中心位置。

6.根据权利要求5所述的多无人机编队全局路径规划方法，其特征在于，所述S42中的编队层级代价δ₂的计算公式为：

δ₂＝η(q_u,2)+c(q_u2，q_new)

式中，c(q_u2，q_new)满足以下关系式：

其中，p_u2,i表示节点q_u2对应的无人机i的位置；p_u2,i通过以下公式计算得到：

其中，s_u2为节点q_u2的编队规模，X_u2为节点q_u2的编队中心位置。

7.根据权利要求4所述的多无人机编队全局路径规划方法，其特征在于，所述S5具体包括如下步骤：

S51、判断生长后两颗随机树是否完成连接，若未连接，结束S5并跳至S6；

S52、定义更新集合Q，将新采样节点q_new加入到更新集合Q中；

S53、从更新集合Q中取出节点q_cur；

S54、检测节点q_cur是否有祖父节点q_g，如果没有，则执行S56，否则判断祖父节点q_g到节点q_cur的连接是否有效，如果无效，则执行S56；如果有效，则执行S55；

S55、在节点连接关系集合E₁或节点连接关系集合E₂中删除q_cur与其父节点q_p的连接关系(q_p，q_cur)，增加连接关系(q_g，q_cur)；此时q_g已更新为q_cur的父节点；之后跳至S54；

S56、将新采样节点q_new的子节点都加入到更新集合Q中；

S57、如果更新集合Q不为空，则跳至S53，否则结束S5，并执行S6。

8.根据权利要求5所述的多无人机编队全局路径规划方法，其特征在于，所述S6中的终止运行条件为迭代次数k是否超过最大迭代次数N或算法达到最大运行时间T_max。

9.根据权利要求5所述的多无人机编队全局路径规划方法，其特征在于，所述S7具体包括如下步骤：

S71、判断第一随机树T₁、第二随机树T₂是否完成连接，如果未完成连接，则说明路径求解失败，退出S7；如果连接成功，则进入S72；

S72、在交汇点集合Π中找到节点q_f，使通过节点q_f的路径代价L_f最小；

S73、从节点q_f分别往节点q_f的父节点和其连接点方向回溯，得到一条连接编队起始状态和编队目标状态的编队全局路径，作为求解结果。

10.根据权利要求9所述的多无人机编队全局路径规划方法，其特征在于，所述S72中节点q_f和路径代价L_f的计算公式为：

L_f＝η(q_f)+η(q_f′)+c(q_f，q_f′)

其中，q_σ′为节点q_σ的连接点，q_f′为节点q_f的连接点。