一种多算子协同进化的无人机三维多目标路径规划方法

本发明涉及无人机路径规划，具体是一种多算子协同进化的无人机三维多目标路径规划方法。

背景技术：

1、在无人机执行任务过程中，路径规划是实现自主飞行与可靠任务执行的关键技术，其核心目标是在复杂环境中为无人机生成一条从起点到目标点的可行飞行路径。现有技术中的路径规划方法通常仅以路径长度作为单一优化目标。然而，在复杂三维场景下进行无人机路径规划时，不仅需要考虑飞行距离，还需综合考虑障碍物分布、空间威胁区域以及飞行安全等多种因素。因此，现有单目标路径规划方法难以在复杂三维环境中生成兼顾路径长度与安全性的高质量飞行路径。

2、另外，现有方法在复杂三维环境中仍存在其他不足。部分算法在搜索过程中易陷入局部最优，导致路径质量和稳定性不足；此外，现有方法通常采用单一种群、固定算子或对全部个体实施同质化搜索，未能依据个体质量、目标瓶颈和搜索阶段构建功能互补的子种群，也缺少多类路径演化算子的差异化配置、顺序衔接机制，容易造成全局探索与局部开发失衡，对高质量解的信息利用不充分，从而影响复杂三维环境下的搜索效率与解质量。因此，亟需一种能够适用于复杂三维环境、兼顾路径长度与路径安全，并具备较强全局搜索能力的无人机多目标路径规划方法。

技术实现思路

1、本发明针对上述背景技术中所存在的技术问题，提出一种多算子协同进化的无人机三维多目标路径规划方法。

2、为了达到上述目的，本发明采用的技术方案为：

3、s1、建立无人机离散三维环境模型和飞行角约束模型，设置起点、目标点；

4、s2、初始化算法参数，包括种群规模、个体连续进化失败最大次数、截止运行时间；

5、s3、采用基于采样的初始化策略生成初始种群，利用快速扩展随机树算法生成同时满足障碍物避碰约束和飞行角约束的初始路径；

6、s4、对种群执行快速非支配排序与拥挤距离计算，将种群划分为精英子种群、中间子种群以及劣势子种群，并更新外部档案集；

7、s5、雇佣蜂阶段，对候选个体依次执行最近路径段交叉算子、方向引导变异算子、高度剖面塑形算子和曲率约束平滑算子，并依据子种群类别、个体目标瓶颈和进化状态差异化调用高度感知简化算子和距离有界安全算子，使同一算子池在不同子种群中形成不同协同路径，以兼顾全局搜索、局部开发与多目标平衡；

8、s6、观察蜂阶段，对非支配解执行基于领导者的信息引导策略，对支配解执行双源信息引导策略，以提高高质量解的收敛能力与支配解的开发能力；

9、s7、侦察蜂阶段，对长时间停滞未更新的个体执行个体重启策略，以维持种群活性并避免算法陷入局部最优；

10、s8、判断是否满足终止条件，若满足，则输出非支配解集，否则返回步骤s4。

11、作为优选，在步骤s1中采用离散三维路径表示方法对无人机飞行路径进行建模，一条可行路径表示为，其中，代表一条路径，s表示无人机起点，t表示目标点，每个航迹点由三维坐标表示；

12、飞行角约束包括水平转弯角约束和垂直转弯角约束，设相邻路径段在水平面的投影向量为，连续两段之间的水平转弯角为；设路径段的垂直分量为，连续两段之间的垂直转弯角为，则约束关系为：

13、，

14、，

15、其中，45°为相邻飞行段的最大水平转弯角，30°为相邻飞行段的最大垂直爬升或下降转弯角；所有新生成或重构的路径均需同时满足上述飞行角约束和障碍物避碰约束。

16、作为优选，在步骤s1中无人机路径规划模型同时以路径长度和路径威胁作为优化目标，路径长度目标通过对路径中相邻航迹点之间的三维欧氏距离进行累加得到，计算公式为：，其中，表示路径的长度；路径威胁目标通过计算各路径段与最近障碍物之间的最小距离得到，计算公式为：，其中，表示路径的威胁性，表示路径段与最近障碍物之间的最小距离，w为根据三维环境数据量级设置的显示缩放常数；w仅用于统一两个目标数值的展示尺度，不参与加权优化，也不改变个体之间的pareto支配关系；

17、无人机多目标路径规划问题是在满足障碍物避碰约束和飞行角约束的条件下，对路径长度与路径威胁进行pareto最小化。

18、作为优选，在步骤s3中基于采样的初始化策略采用快速扩展随机树算法从起点向目标点进行随机采样扩展，在生成新节点时，判断节点之间连线是否与障碍物发生碰撞，并检测新增路径段是否满足水平转弯角和垂直转弯角约束；仅当避碰约束与飞行角约束均满足时，才将新节点加入路径中，直至生成完整可行路径。

19、作为优选，步骤s4中快速非支配排序方法根据路径长度目标和路径威胁目标对种群个体进行支配关系比较，并将个体划分至不同前沿；拥挤距离计算方法通过计算同一前沿中个体在目标空间内的拥挤距离，优先保留拥挤距离较大的个体，以提高种群分布均匀性；且步骤s4采用动态子种群规模调整机制，精英子种群的规模随算法运行逐渐增大，劣势子种群规模随算法运行逐渐减小，中间子种群规模根据总种群规模以及其余两个子种群规模确定，使算法由早期多样化探索逐步过渡到后期瓶颈目标精细化优化，精英子种群规模的计算公式为：，其中，为种群规模，分别表示精英子种群的初始比例和最终比例，t表示当前时间，为最大运行时间；劣势子种群规模的计算公式为：，其中，分别表示劣势子种群的初始比例和最终比例；中间子种群规模的计算方式为：；

20、在完成快速非支配排序后，首先从第一前沿中选择个体构建精英子种群，当第一前沿中的个体数量超过预设精英子种群规模时，通过拥挤距离排序优先选择拥挤距离较大的个体加入精英子种群；当第一前沿中的个体数量不足时，则继续从后续前沿中按照支配等级由高到低依次选择个体，并优先保留拥挤距离较大的个体，直至达到预设精英子种群规模；

21、在精英子种群划分完成后，根据剩余个体继续构建中间子种群，中间子种群按照非支配等级以及拥挤距离进行选择，优先保留支配等级较高且拥挤距离较大的个体，直至达到预设中间子种群规模；

22、在完成精英子种群和中间子种群划分后，其余未被选中的个体构成劣势子种群；

23、外部档案集用于保存高质量非支配解，当产生新的非支配解时，判断外部档案集中是否存在被支配个体，若存在，则删除被支配个体，并将新的非支配解加入外部档案集，其大小为。

24、作为优选，在步骤s5中，精英子种群中的个体全部参与进化；中间子种群中的个体依据适应度值以及进化成功次数选择部分个体参与进化；劣势子种群中的个体依据进化成功次数选择部分个体参与进化；

25、适应度值通过对路径长度目标和路径威胁目标分别进行归一化处理后求和得到，其计算公式为：，其中和分别表示第i个个体的路径长度值和路径威胁值，与分别表示对应子种群中的最大路径长度值和最小路径长度值，与分别表示对应子种群中的最大路径威胁值和最小路径威胁值。

26、作为优选，在步骤s5中：

27、最近路径段交叉算子的输入为两个父代路径个体，分别记为与，其中s表示起点，t表示目标点，表示路径中的中间航迹点，计算两个父代路径中任意路径段对的空间距离，确定距离最小的路径段对和；若连接与以及与的线段均不与障碍物发生碰撞，则通过重连端点生成两条候选路径，并检验候选路径是否满足飞行角约束；对父代路径与候选路径执行快速非支配排序，选择非支配解作为输出，否则保持当前路径不变；

28、方向引导变异算子的输入为最近路径段交叉算子输出的路径，随机选取中间航迹点，并构造其前驱节点与后继节点之间的直线l；当位于l下方时，使沿高度方向向上移动且不越过l，当位于l上方时，使沿高度方向向下移动且不越过l，得到候选节点，仅当和均满足障碍物避碰约束且重构路径满足飞行角约束时，才在原路径与新路径之间选择较优路径作为输出；

29、高度剖面塑形算子用于协同调整局部路径段的高度分布，随机选取两个中间航迹点和，其中，保持二者之间各航迹点的水平坐标不变，以和的高度作为边界，并按累计路径距离建立线性参考高度；对于的航迹点，其高度按照下式更新：，，其中，为航迹点的原始高度，为从至的累计路径长度，为调整强度系数，更新后对整条路径执行障碍物碰撞检测和飞行角约束检测，并在原路径与新路径之间选择较优路径，以抑制不必要的高度振荡；

30、曲率约束平滑算子首先计算各中间航迹点的水平转弯角和垂直转弯角，分别确定垂直转弯角最大的航迹点ni和水平转弯角最大的航迹点；针对每个所述航迹点，在其相邻两条路径段上分别插入辅助航迹点，辅助航迹点与所述航迹点之间的距离为对应路径段长度的三分之一，并通过辅助航迹点重构局部路径，重构路径仅在满足障碍物避碰约束和飞行角约束时被接受，以将集中于单个节点的方向变化分散到多个连续路径段。

31、作为优选，在步骤s5中，对精英子种群、中间子种群和劣势子种群中被选中的候选个体，均依次执行最近路径段交叉算子、方向引导变异算子、高度剖面塑形算子和曲率约束平滑算子；随后，根据个体所属子种群及其目标表现应用目标导向算子，针对精英子种群中的个体，根据路径长度目标和路径威胁目标的归一化结果确定瓶颈目标，其计算公式为：，其中，为第i个个体的瓶颈目标，当路径长度目标对应的归一化结果较大时，仅执行高度感知简化算子；当路径威胁目标对应的归一化结果较大时，仅执行距离有界安全算子，从而优先改进较弱目标并尽量保留另一目标的已有优势；

32、针对中间子种群中的个体，在完成最近路径段交叉算子、方向引导变异算子、高度剖面塑形算子和曲率约束平滑算子四种基础演化算子后，依次执行高度感知简化算子和距离有界安全算子，以同时探索路径长度与路径威胁之间的折中关系；针对劣势子种群中的个体，在完成前述四种基础演化算子后，随机选择高度感知简化算子或距离有界安全算子进行操作，以从不同目标方向开展广泛探索并向种群引入新的多样性；

33、所述高度感知简化算子是面向路径长度目标的算子，首先将原路径投影至与起点s至目标点t连线方向一致的竖直平面，并确定投影路径与起终点直线的交点，若存在交点，则按照投影路径位于直线上方或下方将其划分为两部分，计算两部分投影至起终点直线后的占比，选择占比较小的部分作为冗余路径段予以删除；以被删除路径段的前驱节点为连接起点，在与其后相邻交点之间的中点生成新航迹点，重构较短路径，若投影路径完全位于起终点直线的一侧，则随机删除一个冗余中间航迹点，并直接连接其前驱节点与后继节点，仅当重构路径同时满足障碍物避碰约束和飞行角约束时接受该路径；

34、所述距离有界安全算子是面向路径威胁目标的算子，首先识别与障碍物净空距离最小的中间航迹点，并计算其至最近障碍物的距离d，同时构造与之间的局部连接线l，当位于l下方时，使沿高度方向向上随机移动，位移不超过d且新节点不得越过l；当位于l上方时，仍使其向上移动，但最大位移限制为0.5d，仅当重构路径满足障碍物避碰约束和飞行角约束时，用替换，以在增大障碍物净空距离的同时抑制过度高度波动。

35、作为优选，在步骤s6中，基于领导者的信息引导策略用于对非支配解进行更新，根据非支配解集中个体的拥挤距离采用轮盘赌方法选择领导者个体，记为，拥挤距离较大的个体位于目标空间中较稀疏区域，因此更容易被选为领导者个体，从而引导种群向未充分搜索区域进行搜索，对于当前待更新的非支配个体，采用更新公式：生成新的个体，其中，为取值范围在[-1,1]之间的随机数，a为取值范围在[0,1]之间的调节参数，对更新后生成的新个体同时执行障碍物避碰检测和飞行角约束检测；当两类约束均满足时，依据支配关系在新旧个体之间进行选择；

36、双源信息引导策略用于对支配解进行更新，从当前非支配解集中分别选取路径长度目标最优个体和路径威胁目标最优个体作为参考个体，其中，路径长度目标最优个体记为，路径威胁目标最优个体记为，对于当前待更新的支配个体，采用更新公式：，生成新的候选个体，其中为引导权重系数，均为取值范围在[0,1]之间的随机数，然后对更新后生成的新个体同时执行障碍物避碰检测和飞行角约束检测；当两类约束均满足时，依据支配关系在新旧个体之间进行选择。

37、作为优选，在步骤s7中个体重启策略用于处理种群中的长期停滞个体，当个体连续进化失败次数超过预设阈值时，将该个体判定为停滞个体，表明其在当前进化方向下难以继续获得有效改进，为提高种群活性并避免算法陷入局部最优，针对非支配解和支配解分别采用不同的重启更新方式；

38、对于长期停滞的非支配个体，从外部档案集中随机选择高质量解对其进行替换，使重启后的个体继承历史高质量解中的有效路径信息；

39、对于长期停滞的支配个体，首先从外部档案集中随机选择两个高质量解，分别记为与，随后对与执行最近路径段交叉算子，以生成新的候选个体，当生成的新个体同时满足障碍物避碰约束和飞行角约束时，用新个体替换对应的停滞支配个体。

40、与现有技术相比，本发明的优点和积极效果在于，本发明所提供的一种多算子协同进化的无人机三维多目标路径规划方法，针对复杂三维环境中路径规划存在易陷入局部最优、路径安全性不足以及多目标平衡能力较弱的问题，同时以路径长度和路径威胁作为优化目标，在保证路径安全性的基础上有效缩短飞行距离。首先，采用快速扩展随机树生成具有较高质量与多样性的可行初始种群；其次，构建动态子种群分工机制，将精英子种群、中间子种群和劣势子种群分别用于精细开发、折中搜索和多样性探索，并随运行时间动态调整三类子种群规模。在雇佣蜂阶段，最近路径段交叉、方向引导变异、高度剖面塑形和曲率约束平滑算子依次作用于候选路径，以重组有效路径片段、抑制冗余高度振荡并平滑过大转弯；高度感知简化算子和距离有界安全算子分别面向路径长度与路径威胁目标，并按精英、中间和劣势子种群的不同进化状态进行差异化配置。进一步地，基于领导者的信息引导策略与双源信息引导策略分别用于非支配解和支配解的开发，个体重启策略利用外部档案中的高质量解重构停滞个体。综上所述，本发明能够有效提高复杂环境下无人机多目标路径规划的解质量与搜索效率，具有收敛速度快、路径安全性高以及全局搜索能力强的积极效果。