多约束条件下多目标函数无人水下航行器航迹规划

邱千钧,郝翎钧,张福兴,李 梁

(1.海军驻北京地区军事代表局,北京 100854;2.海军工程大学,湖北 武汉 430033; 3.海军研究院,北京 100161)

随着自主导航、无人控制、人工智能等技术的迅速发展,无人水下航行器(Unmanned Undersea Vehicle,UUV)作为无人系统的重要组成部分,在民用和军事领域,展现出了越来越重要的作用[1-2]。在民用领域,UUV可以用于开展水下环境数据采集、海洋资源勘探、海底电缆检测等任务[3];在军事领域,UUV的使用不仅可以降低战场的伤亡率,而且其本身具有使用灵活、用途广泛、隐蔽性强的特点,使其被誉为“海上力量倍增器”[4]。UUV要完成上述一系列任务,并充分发挥其优势,最为基础、最为关键的技术之一就是UUV航迹规划问题。

航迹规划问题,在国内外已有大量研究,且解决方法也已相当成熟,比较常见的有A*算法、Dijkstra最短路径算法、遗传或蚁群算法等仿生智能算法,以及基于深度学习的人工智能算法等[5]。但是,众多的文献中,航迹规划针对的主要问题是最短路径、航行避碰、算法优化,对于UUV航迹规划问题,不仅需要解决如何寻求最短路径,更为重要的是,要解决航行过程中的定位误差校正。在海洋复杂环境下,由于水下通信困难,系统结构限制等问题,UUV的定位系统难以进行精确定位,导致定位误差累积,以至于最后无法完成既定的任务。因此,在航行过程中进行定位误差校正也是UUV航迹规划问题中的一项重要任务。

1 问题描述

本文研究的目标是在复杂海洋环境中的众多约束条件下找出一条满足以下两个条件的最优航迹:

1)UUV的航迹长度尽可能小;

2)经过校正点的个数尽可能少。

约束条件需要满足的定位误差为:

1)UUV按照规划的航迹从起点到终点的路径上,每航行一段距离就会在水平垂直方向上产生一段误差,因此,在可能路径上,会有众多的定位校正点,每当航行器到达定位校正点附近时,如果水平、垂直误差不大于δ个误差精度,那么,系统就能够对航行器进行误差校正,使其误差为0。

2)UUV按照规划的航迹到达终点之后,会产生累计误差,要求累计误差也不能大于ε个误差精度,否则,视为该航迹不可靠,即UUV按照该航迹无法达到终点。

该问题即为多约束条件下的多目标函数航迹规划问题[6],设目标函数分别为f1(x),f2(x),…,ft(x)(t≥2),问题中的约束条件分别为gi(x)≥0(i=1,2,…,m)和hj(x)=0(j=1,2,…,l),那么该问题就是在满足多种约束的前提下,使得目标函数的值达到最小,用数学形式表示为

(1)

2 模型构建与求解

针对多约束条件下的多目标函数航迹规划问题,采用层次分析法对多个目标函数进行无量纲化处理,加权得到新的单目标函数,将多目标函数问题转换降维为单目标函数问题,再使用遗传算法对模型进行求解,模型求解思路如图1所示。

图1 模型求解思路

2.1 层次分析法求解

层次分析法(AHP法)是将许多复杂且关系模糊不清的元素和相互关系转化为定量分析的一种决策分析方法,是定量和定性分析相结合的方法。

1)指标体系建立

将最终得到的单目标函数作为航迹评价,那么，由问题描述可知,影响航迹评价的因素有两点,分别是: UUV的航迹长度尽可能小和经过校正点的个数尽可能少。因此,建立指标体系如图2所示。

图2 航迹评价的指标体系

2)归一化处理

由于航迹评价中的指标值不在一个数量级上,因此，权重w1,w2值的大小对于目标函数的影响并不敏感,所以,必须要进行归一化处理。归一化处理的数学表达式如下,x为决策变量。

(2)

3)构造判断矩阵

判断矩阵是层次分析法的关键,是进行权重计算的基础。构造判断矩阵的方法是将影响因素x进行两两比对,通常采用1-9标度法,在这里不做赘述。

4)一致性检验

由于指标的复杂性以及人们对事物认识的模糊性和多样性,同时,评价影响因素的指标值是估计值,这种估计就会不可避免地存在一些误差,因此，有必要进行一致性检验,即相容性检验。

通过一致性检验之后,得出影响航迹评价因素的权重w1和w2,那么可以得到最终的目标函数minV为

minV={f1(x),f2(x)}=w1·f1(x)+w2·f2(x)

(3)

2.2 遗传算法求解

遗传算法是基于生物自然选择规律和基因遗传学机理,通过数学模式来模拟“物竞天择,适者生存”的一种随机搜索方法,其基本思路是把问题的决策变量编码为染色体,再利用迭代的方式进行选择、交叉以及变异等运算来不断更新染色体信息,直到生成符合优化目标的染色体[7]。

1)基因编码方式

编码是应用遗传算法时要解决的首要问题,以此反映需要解决的问题,是设计遗传算法时的一个关键步骤。编码方式除了决定个体基因染色体排列方式外,还决定了个体从搜索空间基因型变换到解空间表现型时的解码方法,编码方法影响到交叉算子、变异算子等遗传算子的运算方法,很大程度上决定了遗传进化的效率。

航迹规划中,基因编码通常采用参数方程法、直角坐标系法和经纬度坐标系法等。参数方程和直角坐标系法对航行器状态掌控要求高,不利于构造航行器空间模型;单纯的经纬度坐标系法不能全面反映航行器当前状态,因此,模型中设计了一种航迹结构体的编码方案,能够减少航迹规划时重复的计算量,提高计算内存的利用效率,其结构体格式如图3所示。

图3 航迹结构体格式

其中，Ni表示航迹节点校正点,由5个基本特征组成。Nik表示航迹节点基因,其特征如表1所示。

表1 基因编码在航迹中对应的物理量

①x,y,z表示航行器在航迹校正点所处的空间位置;

②Index是对航行器的航迹校正点进行排序,生成完整航迹;

③Ti表示航行器完成的航迹序列;

④Type表示校正点类型,Type=0代表水平校正点,Type=1代表垂直校正点;

⑤r表示航行器的最小转弯半径,大于最小转弯半径rmin,则航迹可行。

这种基因编码方式的优点是减少了重复的计算量,同时能够实时提取出航行器航迹的相关信息,在不用解码的情况下就能直接计算参考航迹的代价函数值,使得表达式更有效,能生成更好的解,缺点是增加了计算机的物理内存。

2)遗传操作算子

遗传算子是遗传算法具有强大搜索能力的核心,是模拟自然选择过程中的繁殖和基因遗传过程中发生的基因交叉、变异的主要载体。为解决该航迹规划问题,本文采用了以下六种遗传算子[8-9]:

①交叉算子:其主要思想是将两条父代航迹进行重新组合,得到两条具有父代航迹基因的新的子代航迹。

如图4a)所示,首先将两条父代航迹随机分为两个部分,将航迹a的前半部分与航迹b的后半部分组合,航迹a的后半部分与航迹b的前半部分组合,得到两条新的子代航迹c和d。新的航迹既可以是可行解,也可以是不可行解,并且,航迹的节点数可以是不相同的。

②扰动算子:其主要思想是对发生变异的航迹的一个节点坐标进行随机改变。

如图4b)所示,当原始航迹为可行解时进行小范围扰动,将其控制在可行区域内,以航迹上发生变异的点为圆心,设该变异点与距离该变异点最近的点之间的距离为rmin,k扰动为小范围扰动系数(k扰动>1),则扰动半径为

r扰动=k扰动·rmin

(4)

在扰动半径内剔除掉原始航迹上的点后,随机选择一个点的坐标替换掉原始航迹上发生变异的点的坐标。

当原始航迹为不可行解时,进行大范围扰动,尽可能跳出限定的范围,以期望获得的新航迹为可行解,仍然以原航迹上发生变异的点为圆心,设该变异点与距离该变异点最远的点之间的距离为rmax,k′扰动为大范围扰动系数(k′扰动<1),则扰动半径为

r′扰动=k′扰动·rmax

(5)

③插入算子:其主要思想是在发生变异的航迹中随机选择两个相邻航迹节点,在这两个节点中插入一个新的航迹节点,如图4c)所示。

④删除算子:其主要思想是在发生变异的航迹中随机删除一个航迹节点(其中,起点和终点不可删除),如图4d)所示。

⑤交换算子:其主要思想是在发生变异的航迹中随机交换两个相邻航迹节点的先后顺序,如图4e)所示。交换算子只作用于不可行解的航迹,如果相邻航迹节点处的转角越大,那么,进行交换变异的概率也就越大,目的是尽可能地减小转弯角。

⑥平滑算子:如图4f)所示,其主要思想是将发生变异的航迹中转弯角大的“部位”进行平滑处理,在相邻的两个航迹段上插入一个新的航迹节点,并且删除原来的航迹节点,即切除转弯角大的“部位”,使航迹中的尖角平滑。与交换算子类似,平滑算子只作用于不可行解的航迹,如果相邻航迹节点处的转角越大,那么,进行平滑变异的概率也就越大。

图4 遗传操作算子

3)适应度函数

该问题是一个多约束的优化问题,其难点在于如何有效合理地处理约束条件,罚函数是一种解决约束优化问题常用的方法,所谓罚函数,就是基于优化目标和约束条件构造的有惩罚效果的函数,一般可表示为

Fitness(x)=F(x)+χ(g)P(x)

(6)

式中,F(x)为原约束化问题的适应度函数,χ(g)为惩罚因子，P(x)为惩罚项。惩罚因子和惩罚项的设置是罚函数设计的难点,设置为零,导致种群多样性降低,算法易陷入局部最优;设置得太小,罚函数失效,造成误差种群中不可行解的数量变多,算法难以快速收敛;设置太大,会导致惩罚过度,算法陷入早熟。因此，本文根据种群当前状态设计了能自适应调整的动态罚函数,其原理如图5所示。

图5 动态罚函数机制示意图

动态罚函数的具体形式如下：

(7)

式中,g为当前的进化代数;θ(eu(x))为分层次的惩罚函数;τ为惩罚强度;eu(x)为种群中个体x违反第u个约束条件的程度函数,其表达式为

(8)

因此,经过罚函数转化后个体xi的适应度函数可表示为

(9)

2.3 模型求解基本流程

通过对上述目标函数和约束条件的处理,按照层次分析法和遗传算法处理步骤,总结出该问题模型求解的基本流程。

Step1.确定目标函数以及约束条件。

Step2.用层次分析法将问题转化为单目标函数问题。

Step3.选择合适的基因编码方式对问题集进行编码。

Step4.依据可行航迹初始化种群,种群是进行遗传算法操作的空间。

Step5.定义适应度函数,评价种群中个体的适应度。

Step6.找出适应度较好的个体放入繁殖池。

Step7.判断是否满足终止条件,如果满足,则程序结束;如果不满足,则继续下一步。

Step8.设计遗传算子,确定遗传参数如交叉概率pc和变异概率pm,对繁殖池内的个体进行选择、交叉、变异等遗传操作。

Step9.对生成的新的子代个体用适应度函数进行评价,即跳转到Step5。

模型求解基本工作流程如图6所示。

图6 模型求解基本流程图

3 仿真验证

为了验证多约束条件下多目标函数无人水下航行器航迹规划问题解决方法的可行性,对复杂海洋环境下的校正点区域数据集进行仿真验证,设定初始参数δ=30，ε=20,随机生成500个校正点数据集，得到遗传算法的进化过程如图7所示。

图7 遗传算法进化过程

由图7可知,蓝色线段代表的是航行器的航迹,遗传算法的代数、航迹评价的值、航迹最短距离、校正点个数和航迹是否可行都显示在图中。图7a)表示的是初始种群的航迹,可以看出,初始解的航行轨迹杂乱无章,经过遗传算法的不断迭代,由图7b)、7c)可以看出,到第20代左右的时候,航行器的航迹出现较为明显的改善,到第50代左右的时候,航行轨迹出现较为优化的结果,从图7d)中可知,到第100代左右的时候,航行轨迹基本上已经收敛,但尚未达到最优可行解。

图8表示数据集1的种群进化到第123代时,算法所得到的结果已经完全收敛,并且，已经得到最优可行路径,经过的校正点个数为10。

由图8算法搜索过程和最优可行航迹可知,本文

所采用的改进遗传算法能够解决多约束条件下的多目标函数的航迹规划问题,且可以找到最优可行航迹,验证了算法的有效性。

4 结束语

本文针对复杂海洋环境误差定位校正的约束条件下,以最短路径和经过最少校正点为目标的UUV航迹规划问题,采用基于层次分析法和动态罚函数法的遗传算法对该问题进行建模分析,最后的仿真结果表明，所建立的模型和使用的算法能够有效解决多约束条件下多目标函数的无人水下航行器航迹规划问题,可以找出一条既满足最短距离又满足经过最少校正点的最优路径。

图8 算法搜索过程和最优化可行航迹