一种自适应双算子与嵌入式精炼的多UUV替换路径规划方法

摘要: 本发明属于无人潜航器智能路径规划,涉及洋流环境下多无人潜航器动态替换路径规划,尤其涉及一种自适应双算子与嵌入式精炼的多无人潜航器闭环路径规划方法。背景技术:1、...
一种自适应双算子与嵌入式精炼的多UUV替换路径规划方法

本发明属于无人潜航器智能路径规划,涉及洋流环境下多无人潜航器动态替换路径规划,尤其涉及一种自适应双算子与嵌入式精炼的多无人潜航器闭环路径规划方法。

背景技术:

1、无人潜航器(unmanned underwater vehicle, uuv)作为一种能够自主执行水下探测与作业任务的无人系统平台,已广泛应用于海洋资源勘探、水下目标搜索和海洋环境监测等领域,母平台对多无人潜航器实施协同替换是保障uuv集群持续作业能力的重要手段。然而,海洋环境中的复杂洋流会改变母平台的对地航行速度和各航段的实际通行时间,导致母平台与运动中的uuv难以准确会合,甚至产生运动学不可达路径,严重影响替换任务的执行效率。因此,研究高效的多uuv动态替换路径规划方法对提升水下无人系统的持续作业能力至关重要。当前主流的多uuv替换路径规划方法在洋流环境中仍存局限:基于传统组合优化的路径规划方法通常将航段代价简化为欧氏距离或恒定航速下的航行时间,难以准确描述洋流、母平台运动状态与uuv动态位置之间的关系,容易生成实际不可达的访问路径;基于智能优化算法的路径规划方法虽具备一定的全局搜索能力,但容易陷入局部最优,且在uuv数量增加时难以兼顾求解精度与收敛效率。

2、现有改进方案多聚焦于单一维度的性能提升,未系统解决洋流环境感知、动态会合可达性与全局局部协同寻优之间的综合优化问题。因此,亟需设计一种路径可达性强、替换耗时低、求解稳定性高的多无人潜航器动态替换路径规划方法,以突破复杂洋流条件下母平台协同替换任务的路径规划技术瓶颈。

3、文献《基于路径贡献度评判的双种群蚁群算法tsp问题求解分析方法》有以下问题:该方法主要利用两个独立蚁群分别执行快速收敛搜索与路径贡献度搜索,两个种群之间仅通过阶段最优路径比较实现协同,缺乏基于种群适应度分布和连续停滞状态的动态调度机制;同时,其搜索过程主要依赖信息素更新,未形成自适应交叉、定向变异与局部精炼之间的协同优化,难以进一步改善复杂场景下的近优路径。

4、文献《基于改进排挤遗传算法的旅行商问题研究》有以下问题:该方法主要通过小生境排挤和路径价值预处理维持种群多样性,其交叉与变异过程未根据种群适应度差异和连续停滞程度进行动态调节;同时,路径价值预处理依赖固定的节点间代价,缺少针对动态高耗时航段的定向优化。

5、文献《基于改进人工蜂群算法求解广义旅行商问题》有以下问题:该方法主要通过多种邻域更新规则和停滞次数自适应调整扰动强度,其自适应机制仅作用于单一扰动过程,缺乏交叉与变异双算子的协同调节;同时在搜索后期对近优访问序列的局部优化能力仍存在不足。

6、文献《基于matlab的改进蚁群算法求解旅行商问题》有以下问题:该方法通过动态参数调整、遗传种群重组和模拟退火扰动改善传统蚁群算法,但各优化机制主要按照预设阶段依次执行,缺乏基于种群实际停滞状态的动态切换机制;模拟退火仅作为后期扰动手段,未对精英路径进行周期性局部精炼并将优化结果持续回写种群,宏观全局搜索与微观局部优化之间的协同性不足。

7、专利cn111612217a《一种用于海上风电场巡检的水面无人艇改进ga-sa路径规划方法》有以下问题:该方法模拟退火主要围绕当前最优个体进行常规邻域扰动,未根据连续停滞程度区分周期性精英精炼与深度停滞救场,也缺少针对逆流高耗时航段的定向翻转和种群梯度重构机制。

技术实现思路

1、针对现有技术存在的问题,本发明提供了一种自适应双算子与嵌入式精炼的多uuv替换路径规划方法,目的是解决复杂洋流环境下母平台替换路径规划中动态会合点运动学不可达、访问顺序易陷入局部最优以及大规模任务求解效率较低的问题。首先,通过构建融合洋流速度、母平台航行能力与无人潜航器动态运动状态的时空可达性模型,实时计算母平台与各无人潜航器之间的最早可行会合时刻,并将运动学约束嵌入路径评价过程,以剔除不满足航行速度限制的不可达路径;其次,设计自适应遗传搜索机制,根据种群适应度分布和搜索状态动态调节交叉概率与变异概率,并结合高耗时航段识别结果实施定向翻转变异,在增强种群多样性的同时降低不利洋流航段造成的额外时间损失;最后,提出遗传搜索与模拟退火协同的混合优化策略,通过周期性嵌入模拟退火对优良个体进行局部精炼,并在种群长期停滞时触发深度退火与种群重构,从而兼顾全局探索能力与局部寻优精度,获得满足动态会合约束且总替换耗时最低的母平台最优访问路径。

2、为达到上述目的,本发明采用以下具体技术方案予以解决:

3、一种自适应双算子与嵌入式精炼的多uuv替换路径规划方法,包括以下步骤:

4、s1、建立母平台与多uuv的系统运动学模型,将动态协同替换任务构建为移动目标旅行商问题,并进行死锁过滤,具体包含以下子步骤:

5、s11、建立全局二维直角坐标系,设作业海域内存在个待替换的uuv,记为集合,其中,为uuv的编号,表示第个待替换的uuv;针对任意uuv,设其巡游轨迹的几何中心坐标为,其中,和分别表示第个uuv巡游轨迹几何中心在轴和轴方向上的坐标,巡游半径为,以恒定对水线速度进行圆周巡游;

6、s12、设作业海域内存在稳定的宏观洋流场,其流速矢量恒定为,其中,和分别表示洋流速度在轴和轴方向上的分量;设为母平台对地实际速度矢量;为母平台相对静水推力速度矢量;为母平台在静水环境下的最大动力航速,母平台对地运动满足zermelo导航方程:

7、

8、s13、在动态协同替换过程中,设表示母平台当前已完成的追击航段数,母平台于时刻从当前位置矢量启航,追击目标uuv;则必须满足绝对空间位置重合约束,即:

9、

10、式中,表示当前追击航段的起始时刻,表示母平台在时刻的位置矢量,表示母平台与目标uuv的候选交会时刻,表示第个uuv在交会时刻的实际位置矢量;

11、由于母平台在两节点间采取直线最短趋近策略,可推导出母平台实现该次交会所需的对地平均速度矢量:

12、

13、式中,表示在候选交会时刻达到第个uuv所需的平均对地速度矢量;

14、将式(3)代入式(1),可得母平台在趋近过程中所需的静水推进速度:

15、

16、为使交会在物理层面切实可行,母平台所需静水推力必须严格满足运动学边界约束:

17、

18、当洋流迫使母平台以逆水方向趋近时,若在所有可行交会时刻下所需静水推力均超出动力极限,即恒成立,则判定该替换航段发生运动学死锁,该访问序列物理不可达;

19、s14、设母平台的访问序列为,其中表示母平台从uuv出发并最终返回,为的一个排列,描述了母平台对个uuv的访问顺序;

20、对于序列中的第个追击航段,设母平台在时刻完成对前序节点的替换,当前位置为。由于目标uuv处于持续圆周巡游状态,母平台的实际追击耗时无法通过静态欧氏距离计算获得,而须依据zermelo运动学约束,求解满足动力边界条件的最早可行交会时刻:

21、

22、式中,表示候选交会时刻,表示前一交会时刻,表示第个航段的最早可行会合时刻,表示母平台在第个航段起始时刻的位置矢量,表示目标uuv在时刻的动态位置矢量;

23、若式(6)在整个时间范围内无解,对其适应度施加极值惩罚:,为访问序列的适应度;

24、s15、将路径规划问题定义为在满足zermelo运动学约束与每个uuv恰好被访问一次的条件下,求解使母平台完成全部个uuv替换任务总耗时最小的访问序列,其数学模型如下:

25、

26、

27、

28、式中,表示访问序列对应的母平台总替换任务耗时;表示第个追击航段的耗时;表示母平台执行第个追击航段时所需的相对静水推进速度矢量;为上所有合法排列的集合;

29、s16、对种群中每个个体的访问序列,依据式(6)逐航段提取最早可行交会时刻,将各航段耗时累加至序列总耗时,并将母平台位置逐段更新为,其中,表示母平台完成第个目标uuv替换后的新位置矢量;若某航段在整个时间范围内无可行交会时刻,则判定触发运动学死锁,立即终止递推并施加极值惩罚,将其排除于有效候选集之外;

30、s2、计算种群适应度,并进行演化状态动态监测,具体包含以下子步骤:

31、s21、提取当前世代有效个体的最小任务耗时与种群平均耗时,定义演化停滞度指数:

32、

33、s22、设全局历史最优耗时为,上一次记录的全局最优耗时为,若,即当前代发掘出更短的母平台替换路径,将更新为当前的最优抗流场路径。连续停滞计数器的更新公式定义如下:

34、

35、式中,为设定的容差,若持续累加并达到预设阈值,则判定母平台的替换路径寻优陷入停滞,进而触发宏微观机制切换;

36、s3、进入自适应遗传阶段,动态调整个体的交叉概率与变异概率,具体包含以下子步骤:

37、s31、通过锦标赛选择保留总耗时较短者进入父代池;在交叉环节采用基于个体适应度的非线性自适应交叉概率,设参与交叉的两个父代中较优者的耗时为,计算规则如下:

38、

39、式中,与分别为交叉概率的上界与下界;

40、s32、在变异环节采用基于种群停滞度指数的指数型自适应变异概率:

41、

42、式中,与分别为变异概率的上下界,为变异敏感度调节因子,为演化停滞度指数;

43、s33、对于每一个待变异个体,首先提取其路径各航段的耗时数据,定位其中母平台逆洋流趋近uuv、耗时最高的逆水瓶颈航段,随后对以该航段为中心的局部路径片段执行翻转操作,强制将逆水高耗时航段逐出母平台的当前访问序列。相比于随机翻转,该定向策略能够以更精准的方式在洋流干扰的路径层面消除运动学死锁风险,生成阻力更低的顺流候选路径;

44、s4、执行模拟退火协同精炼与深度停滞处理,周期性对精英访问序列进行局部精炼,并在种群深度停滞时触发深度模拟退火与种群重构,具体包含以下子步骤:

45、s41、当连续停滞计数器达到设定阈值时,触发宏微观切换,提取当前全局最优访问序列作为初始解调用深度模拟退火算法;在每一温度下对当前母平台访问序列随机施加邻域扰动操作生成候选新解,邻域扰动采用两种操作交替执行:其一为2-opt翻转,随机选取序列中两个位置并翻转其间的uuv访问子序列;其二为节点交换,随机选取两个uuv并交换其在访问序列中的先后位置;候选解的接受遵循metropolis准则:

46、

47、式中,表示模拟退火过程中的当前温度,为候选解与当前解的母平台替换路径总耗时差值;

48、s42、深度退火结束后,无论是否取得改善,均执行梯度换血操作:种群第1位强制填入当前全局最优访问序列;第2至第位依适应度排名依次填入次优精英个体,为梯度换血过程中保留的精英个体数量,由精英保留比例与种群规模确定;第至第位全部替换为随机生成的合法访问序列,为种群规模。换血完成后将连续停滞计数器清零;此外在常态演化阶段,每隔代将种群中适应度排名靠后的部分个体按随机注入比例替换为随机生成的合法访问序列,作为抑制同质化的常态补充;

49、s43、当未触发深度停滞,且当前进化代数为嵌入精炼触发周期的整数倍时,启动嵌入式遗传-模拟退火协同精炼:选取个最优的母平台替换uuv路径执行局部精炼,对每个精英个体计算动态初始温度:

50、

51、式中,为温度系数,为当前精英替换路径的总耗时;

52、s44、重复执行上述步骤,直至达到最大进化代数,终止迭代,输出母平台对多uuv执行动态协同替换任务的最优规划路径与最短总耗时;

53、本发明具有如下有益效果:

54、(1) 针对多uuv替换任务中局部寻优能力不足、宏观搜索与微观开发相互割裂的问题,本发明提出了嵌入式精炼与宏微观切换机制。通过周期性调用模拟退火算法对精英访问序列进行局部精炼,并将精炼后的优良结果回写至遗传种群,实现局部优化结果对全局演化过程的持续反馈;当种群进入深度停滞状态时,触发深度模拟退火与梯度换血操作,恢复种群的全局寻优活力。在仿真实验中,本发明方法的平均替换耗时相较于传统遗传算法降低了27.52%,为洋流环境下多uuv替换路径规划提供了可靠的技术支撑。

55、(2) 针对传统遗传算法采用固定交叉概率和变异概率,易破坏优良路径片段且难以跳出局部最优的问题,本发明设计了自适应双算子机制。其中,根据种群适应度分布动态调整交叉概率,对优良顺流路径片段进行保护;根据种群演化停滞程度动态调整变异概率,并结合高耗时航段识别结果实施定向翻转变异。通过自适应交叉算子与定向变异算子的协同作用,在保护优良个体的同时增强种群多样性,提高了本方法的全局搜索能力与多uuv替换路径优化效率,平均替换耗时相较于传统模拟退火算法8.33%。

56、(3) 针对复杂洋流环境下传统路径规划方法采用静态距离作为航段代价,难以准确描述母平台与动态无人潜航器会合过程的问题,本发明构建了融合洋流速度、母平台航行能力与无人潜航器运动状态的时空可达性模型。通过计算母平台与目标无人潜航器之间的最早可行会合时刻,并将运动学约束嵌入路径评价过程,能够有效剔除不满足航速约束的不可达航段,提高了航段耗时计算的准确性与替换路径的实际可执行性。