一种用于AUV实时路径规划的免疫遗传算法

摘要

本发明涉及自主水下机器人的实时路径规划方法，是AUV实时避碰过程中根据在线地图进行在线、实时局部路径规划的方法。本发明根据AUV路径点数目设定小种群个数，并初始化；对每个小种群进行免疫选择后得到子群；将其中一个子群进行遗传操作，另一个进行细胞克隆；然后通过接种疫苗和抗体聚类形成下一代小种群，判断其是否满足条件；如果满足则选出这些小种群的最优个体；从所有最优个体组成的集合中选择最优个体最为规划路径。本发明利用抗体群聚类机理维持群体的多样性，既避免了算法过早收敛问题，又有利于达到全局优化。所建立的免疫遗传算法采用自我调节机制对生成的子代进行聚类分析，保证了群体的多样性。

说明书

技术领域

本发明涉及自主水下机器人（AUV，Autonomous Underwater Vehicle）的实 时路径规划方法，更具体地说，是AUV实时避碰过程中根据在线地图进行在线、 实时局部路径规划的方法。

背景技术

自主水下机器人是一种自身携带能源，依靠自主导航系统，通过智能的规 划决策，自主航行到作业区域，自主完成作业使命的潜水器。自主性要求自主 水下机器人能在无外界控制条件下自主地适应多变、复杂的外界环境，特别是 要应对事先未知的障碍。这就需要自主水下机器人在具备实时避碰功能的同时， 还应具备在线、实时局部路径规划的能力。

实时路径规划定义为：在AUV航行过程中根据传感器信息生成的在线地图 按照一定评价标准寻找一条从起点到目标点的优选路径的过程。常用的实时路 径规划算法有人工势场法、A*或D*算法、遗传算法等。人工势场法具有良好的 实时性，但存在陷阱区域和在相近障碍物之间不能发现路径等缺点。A*或D* 等优化搜索算法更适用于解决单目标优化问题。遗传算法是一种基于自然选择 和自然遗传的全局优化算法，采用群体方法对目标函数空间进行多线索的并行 搜索，更适用于AUV实时路径规划这类多目标优化问题。但传统遗传算法存在 早熟和收敛速度慢两个难题，并不适用于AUV实时路径规划要求。

发明内容

本发明要解决的技术问题是提供一种具有较好收敛速度和收敛性的AUV实 时路径规划方法，当AUV实时避碰策略陷入死循环时，该方法能引导AUV避 开障碍、跳出死循环，并且继续执行使命任务。

本发明为实现上述目的所采用的技术方案是：一种用于AUV实时路径规划 的免疫遗传算法，包括以下步骤，

1）根据AUV路径点数目设定小种群个数，初始化小种群的规模、最多进 化代数和随机生成小种群的个体；

2）对每个小种群进行免疫选择后，每个小种群得到两个子群；将其中一个 子群进行遗传操作，另一个进行细胞克隆；将得到的两个子群进行接种疫苗和 抗体聚类，形成下一代小种群；

3）判断下一代小种群是否满足最多进化代数或Pareto最优解条件；如果满 足，则根据亲和度的值选出这些小种群的最优个体；如果不满足，则返回步骤2）；

4）从每个小种群最优个体组成的集合中，根据每个最优个体的亲和度选择 亲和度值最大的一个作为最优个体，该最优个体即为规划的路径。

所述免疫选择具体为：选择亲和度高的个体，且个体个数满足设定值； 亲和度的值通过公式$A\left(P_{\mathrm{mk}}\right)=\frac{1}{1+|J\left(P_{\mathrm{mk}}\right)-\underset{i=1}{\overset{N_{\mathrm{bm}}}{\min }}J\left(B_{\mathrm{mi}}\right)|}$得到；

其中，适应值

$J\left(P_{\mathrm{mk}}\right)=\frac{\underset{l=0}{\overset{m}{\Sigma }}d(p_{k,l},p_{k,l+1})-d(p_s,p_e)}{d(p_s,p_e)}+\underset{l=1}{\overset{m}{\Sigma }}\frac{{\psi }_{k,l}}{\pi }$

$+\underset{l=o}{\overset{m}{\Sigma }}\underset{g}{\overset{G}{\max }}b\left(p_{k,l}{p}_{k,l+1}{\Omega }_g\right)+\underset{1=0}{\overset{m}{\Sigma }}g(p_{k,l}{p}_{k,l+1},T_{\mathrm{AUV}})$

p_s、p_e分别表示路径的起点和终点，p_k,0＝p_s，p_k,m+1＝p_e；d(p_x,p_y)为距 离函数，表示两点之间的空间距离；Ψ_kl表示线段p_k,l-1p_k,l与线段p_k,lp_k,l+1延长线 的夹角，Ψ_kl∈[0,π]；P_mk为群体P_m(t)中的抗体，B_mi为群体P_m(t)中的抗原；

b(p_k,lp_k,l+1,Ω_g)表示线段p_k，lp_k，l+1与障碍Ω_g相对方位的系数；d_min表示AUV与 障碍的最小安全距离，O_d表示线段与障碍相交的惩罚系数，d(p_k,lp_k,l+1,Ω_g)表示 线段p_k,lp_k,l+1与障碍Ω_g的最近距离；b(p_k,lp_k,l+1,Ω_g)计算公式为：

$b(p_{k,l}{p}_{k,l+1},{\Omega }_g)=\left(\begin{array}{cc}0& \mathrm{ifd}(p_{k,l}{p}_{k,l+1},{\Omega }_g)\ge d_{\min }\\ O_d& \mathrm{otherwise}\end{array}\right)$

g(p_k,lp_k,l+1,T_AUV)表示路径p_k，lp_k，l+1是否与AUV航行轨迹T_AUV相交，如果路径与AUV 航行轨迹相交，则对相应的染色体进行惩罚，惩罚值为较大的正数O_g：

所述遗传操作包括以下步骤：

从当前群体P_m(t)中根据选择概率选择一定数量的个体，生 成交配池，其中T＞0是退火温度，J_mk=J(P_mk)，N_m为群体P_m(t)的规模；

从交配池中选择两个染色体进行交叉操作，具体为：两个染色体均随机的 从相同位置分开，一个染色体的前半部分和另一个染色体的后半部分结合，另 一个染色体的前半部分和前一个染色体的后半部分结合，从而形成两个全新的 个体进入新的子群；

再对交配池中的个体进行变异操作，在进化初期，采用统一繁殖方式，也 称无性交叉：选择一个染色体，随机改变某一位或多位染色体的基因；收敛到 一定程度后，改用非统一繁殖，也称启发式交叉：选择距离障碍较近的基因位 置，沿垂直理想路径方向按长度分辨率产生突变，得到的个体进入新的子群。

所述细胞克隆具体为：根据抗体X_i与抗原Y_j的超突变公式X_i←X_i+β(Y_j-X_i) 进行抗体繁殖；其中β∈[0,α]，

所述抗体聚类包括以下步骤：将给定群体划分为q个子群 Q_k：$Q_k=\{P_{k1},P_{k2},···P_{k{p}_k}\},$${\forall P}_{\mathrm{ki}},P_{\mathrm{kj}}\in Q_k,$M(P_ki,P_kj)≤δ；

相似度$M(P_{\mathrm{mk}1},P_{\mathrm{mk}2})=\underset{i=0}{\overset{m}{\Sigma }}d(p_{k1,i},p_{k2,i}),$δ为自定义常数；

根据|F(P_ki)-F(P_kj)|≤δ₀,P_ki,P_kj∈Q_k处罚激励度低的个体P_kj，将未被处罚的 个体存入Q中；

其中，激励度其中β为调节因子，β≥1； $C\left(P_{\mathrm{mk}}\right)=\frac{\left|\right\{P_{\mathrm{mi}}\in X|M(P_{\mathrm{mk}},P_{\mathrm{mi}})\le \delta \}|}{N_{\mathrm{pm}}},$$X⋐P_m$为P_mk所属的抗体群，N_pm为小种群的规模。

本发明具有以下优点：

1.本发明利用抗体群聚类机理维持群体的多样性，既避免了算法过早收敛 问题，又有利于达到全局优化。所建立的免疫遗传算法采用自我调节机制对生 成的子代进行聚类分析，保证了群体的多样性。

2.本发明建立的细胞克隆操作加强了遗传算法的局部搜索能力。亲和突变 和均匀突变策略更强调对当前子空间的局部搜索，在保证遗传算法全局搜索能 力的同时也加强了局部搜索能力。

3.本发明利用免疫记忆机制，保留计算过程中出现的高效可行抗体作为疫 苗，并适时为种群接种疫苗从而加快算法的收敛速度。

附图说明

图1为本发明建立的双层AUV实时避碰系统结构图；

图2为本发明建立的免疫遗传算法流程图；

图3为实施例一中免疫遗传算法与令两种方法规划路径和收敛速度的对比；

图4为实施例二中有无实时路径规划情况下的AUV航行轨迹；

图5为实施例二中两次实时路径规划的结果。

具体实施方式

下面结合附图及实施例对本发明做进一步的详细说明。

如图1所示，本发明在原有自主水下机器人实时避碰系统框架中增加实时 路径规划模块，建立了双层的实时避碰系统框架。实时路径规划模块由监控规 划模块触发，根据数据处理模块生成的在线地图和AUV当前状态规划出新的期 望路径。

本发明建立的实时路径规划模块采用基于免疫遗传算法的实时路径规划技 术方案，如图2所示，核心部分由免疫选择、遗传操作、细胞克隆和抗体聚类4 个模块组成，主要流程为：首先从待进化种群P_m(t)中确定性地选择应答能力强 的抗体组成子群进行免疫应答，剩余个体组成对中的个体进行 细胞克隆操作，对中的个体进行遗传操作，两项操作的结果组成进行 抗体聚类，清除相同或相似的抗体。最后从中选择最优的个体形成下一代 群体P_m(t+1)。待进化种群表示多条路径，个体表示路径，根据AUV路径点数目 设定小种群个数。

（1）免疫选择

免疫选择的目的是按选择概率p_o从P_m(t)中选择亲和力较高的个体组成待进 化群体P_m¹(t)，其中个体个数满足设定值（本实施例设定值为100）；。所谓亲和 力是指抗体与抗原的匹配程度，代表着待选个体与当前最优个体的匹配程度。 本发明建立的亲和度是用适应值差异来衡量亲和度的大小，首先找到适应值最 小的抗原，个体P_mk的适应值与该抗原的适应值做差值，个体P_mk的亲和度和该差 值成反比。个体P_mk表示抗体，B_mi表示抗原（可设定为几十个），当亲和度最大 时，P_mk和B_mi最匹配。亲和度的计算公式为：

$A\left(P_{\mathrm{mk}}\right)=\frac{1}{1+|J\left(P_{\mathrm{mk}}\right)-\underset{i=1}{\overset{N_{\mathrm{bm}}}{\min }}J\left(B_{\mathrm{mi}}\right)|}---\left(1\right)$

式(1)中J(P_mk)为个体P_mk的适应性函数，该函数表示路径长度、安全性和平 滑度，更能反应AUV实时路径规划的需求。

计算公式为：

$J\left(P_{\mathrm{mk}}\right)=\frac{\underset{l=0}{\overset{m}{\Sigma }}d(p_{k,l},p_{k,l+1})-d(p_s,p_e)}{d(p_s,p_e)}+\underset{l=1}{\overset{m}{\Sigma }}\frac{{\psi }_{k,l}}{\pi }---\left(2\right)$

$+\underset{l=o}{\overset{m}{\Sigma }}\underset{g}{\overset{G}{\max }}b\left(p_{k,l}{p}_{k,l+1}{\Omega }_g\right)+\underset{1=0}{\overset{m}{\Sigma }}g(p_{k,l}{p}_{k,l+1},T_{\mathrm{AUV}})$

式(2)中$\frac{\underset{l=0}{\overset{m}{\Sigma }}d(p_{k,l},p_{k,l+1})-d(p_s,p_e)}{d(p_d,p_e)}$表示路径的长度适应性，$\underset{l=1}{\overset{m}{\Sigma }}\frac{{\psi }_{k,l}}{\pi }$表示路径平滑 度的适应性，$\underset{l=o}{\overset{m}{\Sigma }}\underset{g}{\overset{T}{\max }}b(p_{k,l}{p}_{k,l+1},{\Omega }_g)$表示路径安全性尺度，$\underset{1=0}{\overset{m}{\Sigma }}g(p_{k,l}{p}_{k,l+1},T_{\mathrm{AUV}})$表示路径是否与AUV航行轨迹相交；上述长度适应性、路径平滑度适应性、路 径安全性尺度、路径是否与AUV航行轨迹相交等数据可以根据在线电子海图和 AUV当前状态（即传感器数据）计算得出。

p_s、p_e分别表示路径的起点和终点，并且定义p_k，0＝p_s，p_k,m+1＝p_e。d(p_x,p_y) 为距离函数，表示两点之间的空间距离。Ψ_kl表示线段p_k，l-1p_k,l与线段p_k,lp_k,l+1延 长线的夹角，Ψ_kl[0,π]。

b(p_k,lp_k，l+1,Ω_g)表示线段p_k,lp_k,l+1与障碍Ω_g相对方位的系数。设d_min表示AUV 与障碍的最小安全距离，O_d表示线段与障碍相交的惩罚系数（通常设定为较大 的正整数），d(p_k，lp_k，l+1，Ω_g)表示线段p_k，lp_k，l+1与障碍Ω_g的最近距离。则 b(p_k,lp_k，l+1,Ω_g)计算公式为：

$b(p_{k,l}{p}_{k,l+1},{\Omega }_g)=\left(\begin{array}{cc}0& \mathrm{ifd}(p_{k,l}{p}_{k,l+1},{\Omega }_g)\ge d_{\min }\\ O_d& \mathrm{otherwise}\end{array}\right)---\left(3\right)$

g(p_k,lp_k,l+1,T_AUV)表示路径p_k,lp_k,l+1是否与AUV航行轨迹T_AUV相交，如果路径与 AUV航行轨迹相交，则对相应的染色体进行惩罚，惩罚值为较大的正数O_g：

确定性地选择应答抗原能力强的抗体进行免疫应答，参与细胞克隆和亲和 突变。亲和突变能微调靠近障碍的路径点位置，和细胞克隆操作共同作用，增 强障碍区域附近的局部搜索能力。

免疫选择一方面给亲和力高的抗体提供更多选择机会，而且也给亲和力及 浓度皆低的抗体提供生存机会，使得存活的抗体群具有多样性。

（2）遗传操作

本发明建立的遗传操作模块由三个遗传算子组成：选择算子、特异交叉算 子和变异算子。

选择算子是从当前群体P_m(t)中选择一定数量的个体，生成交配池。设T＞0是 退火温度，选择概率为：

$S_s\left(P_{\mathrm{mk}}\right)=\frac{e^{\frac{J_{\mathrm{mk}}}{T}}}{\underset{k=1}{\overset{N_m}{\Sigma }}{e}^{\frac{J_{\mathrm{mk}}}{t}}}---\left(5\right)$

其中，J_mk=J(P_mk)，N_m为群体P_m(t)的规模。

交叉算子是从交配池中选择两个染色体，均随机的从相同位置分开，一个 染色体的前半部分和另一个染色体的后半部分结合，另一个染色体的前半部分 和前一个染色体的后半部分结合，从而形成两个全新的个体。

变异算子分成两种，在进化初期，采用统一繁殖方式，也称无性交叉：选 择一个染色体，随机改变某一位或多位染色体的基因。收敛到一定程度后，改 用非统一繁殖，也称启发式交叉：选择距离障碍较近的基因位置，沿垂直理想 路径方向按长度分辨率产生突变。

（3）细胞克隆

细胞克隆是指在给定的繁殖数下，抗体群中所有抗体繁殖克隆的映射。设 定X，Y分别为给定的抗体群和抗原群，抗体抗原本发明建立 的抗体X_i的繁殖数计算公式为：

$N_{x_i}={(N_{\mathrm{bm}}-\frac{1}{\mathrm{\lambda A}\left(X_i\right)})}^{\theta },$$\lambda \in [\frac{1}{2(1+A\left(X_i\right))},\frac{1}{(1+A\left(X_i\right))}]$

其中λ为随机数，表示抗体X_i的繁殖率；1.0＜θ＜1.5，为设定参数。

本发明建立的细胞克隆过程是抗体群P_m¹(t)中每个抗体按照上述繁殖数公式 繁殖克隆，然后所繁殖的N_bm个克隆与抗原群B_m(t)中的抗原进行超突变。对其余 的克隆，随机选择B_m(t)中的一个抗原，进行均匀随机突变。

本发明建立的抗体X_i与抗原Y_j的超突变公式：

X_i←X_i+β(Y_j-X_i)，β∈[0,α]，$\alpha =1-e^{-\left|\right|x_i-Y_j\left|\right|}---\left(6\right)$

其中β为[0,α]上的随机数。

抗体X_i与抗原Y_j的均匀随机突变是指抗体X_i以突变率α₀作为概率对其各基 因位置上的基因在0到9的整数之间随机突变，λ位常数，其中α₀由下式确定。

${\alpha }_0=1-{\mathrm{\lambda e}}^{-\left|\right|x_i-Y_j\left|\right|}---\left(7\right)$

（4）抗体聚类

本发明引入聚类算法处理抗体群中过剩的个体。给定群体将P划分为q个子群Q_k

$Q_k=\{P_{k1},P_{k2},···P_{k{p}_k}\},$${\forall P}_{\mathrm{ki}},P_{\mathrm{kj}}\in Q_k,$M(P_ki,P_kj)≤δ        (8)

根据

|F(P_ki)-F(P_kj)|≤δ₀,P_ki,P_kj∈Q_k                  (9)

处罚P_ki，P_kj中激励度低的个体，将未被处罚的个体存入Q中。

其中激励度是指抗体群中抗体应答抗原和被其他抗体激活的综合能力，本 发明将其定义为函数F:计算公式为：

$F\left(P_{\mathrm{mk}}\right)=A\left(P_{\mathrm{mk}}\right)e^{-\frac{C\left(P_{\mathrm{mk}}\right)}{\beta }}---\left(10\right)$

式(10)中β为调节因子，β≥1，为P_mk所属的抗体群。抗体浓度C(P_mk) 的计算公式为：

$C\left(P_{\mathrm{mk}}\right)=\frac{\left|\right\{P_{\mathrm{mi}}\in X|M(P_{\mathrm{mk}},P_{\mathrm{mi}})\le \delta \}|}{N_{\mathrm{pm}}}$

式中M(P_mk1，P_mk2)为相似度，其值越大，相似度越小；计算公式为：

$M(P_{\mathrm{mk}1},P_{\mathrm{mk}2})=\underset{i=0}{\overset{m}{\Sigma }}d(p_{k1,i},p_{k2,i})$

聚类算法促使抗体群中相同或相似的抗体被确定性地清除，其作用不仅在 于保持种群多样性，而且为免疫选择算子选择存活抗体减轻选择压力。

如图2所示，本发明以遗传算法为主、引入抗体识别抗原的免疫机制，形 成一种新的用于AUV实时路径规划的免疫遗传算法，其基本流程为：

步骤1，如果路径起始点和目标点的连线满足公式（2），则将起始点和目标 点作为抗体转到第9步；否则，根据路径点数目要求设定小种群个数M， 通常2≤M≤100；设疫苗的集合为记忆细胞群，另起始点和目标点的连线作为记 忆细胞群的初值M₁(t)，令m＝2；

步骤2，设定小种群P_m(t)的规模N_pm、最多进化代数T_m，令t＝1；

步骤3，以记忆细胞群为基础，随机生成N_pm个个体组成小种群P_m(t)；

步骤4按照公式（2）计算P_m(t)中每一个个体的适应值；

步骤5，从抗体群P_m(t)中选择适应值较大的个体组成备选抗原群，与原有抗 原群B_m(t)一起进行抗原聚类，从而更新抗原群B_m(t)，抗原群规模为N_bm；

步骤6，从最新抗原中选择可行的最优路径作为疫苗，加入原记忆细胞群 M_m-1(t)形成新的记忆细胞群M_m(t)；

步骤7，计算P_m(t)中抗体的亲和力；并以此为度量按选择概率p_o从P_m(t)中选 择N_pm1个最佳个体组成待进化群体P_m¹(t)，其余个体组成群体P_m²(t)；

步骤8，将P_m¹(t)进行细胞克隆操作，形成一个子代P_m¹¹(t)；

步骤9，对P_m²(t)中个体进行交叉和变异等遗传操作，生成P_m(t)的子代P_m²¹(t)；

步骤10，令P_m³(t)＝[P_m¹¹(t)P_m²¹(t)]，计算P_m³(t)中每一个个体的适应值，如果 最优个体所对应的路径是不可行的，则随机选择部分个体和基因位进行疫苗接 种。

步骤11，对抗体群P_m³(t)进行聚类分析，选择每个聚类中适应能力较强的个 体组成子代代表P_m⁴(t)；

步骤12，当|P_m⁴(t)|≥N_pm时，从P_m⁴(t)中选择最优的N_pm个抗体形成下一代群 体P_m(t+1)；当|P_m⁴(t)|＜N_pm时，随机生成部分新个体和P_m⁴(t)一起形成下一代群体 P_m(t+1)；

步骤13计算P_m(t+1)中每一个个体的适应值；

步骤14，t＝t+1；如果t＞T_m或满足Pareto最优解条件，输出当前群体中的 最优个体转到第15步；如果t≤T_m并且不满足Pareto最优解条件，转到第5 步；

步骤15，m＝m+1；如果m＞M或满足终止循环条件，转到第16步；如果m≤M 并且不满足终止循环条件，返回第2步；

步骤16，从每一个小种群最优个体组成的集合中，选择一个根 据公式（1）得到的亲和度最大值的最优个体，生成优选路径。保存疫苗信息 Mm(t)。

图3为实施例一，设AUV当前点为（24，10），目标点为（24，50）。设m＝2， 分别采用免疫遗传算法（IGA）、免疫算法（IA）和遗传算法（GA）进行路径规 划，三种算法均用相同的适应性函数。取第100代的最优个体作为规划结果， 则图3a为三种算法规划的路径结果。显然，免疫遗传算法规划的路径更短、更 优。取每一代最优个体的适应值表示收敛速度，如图3b所示，三种算法在100 代时均处于收敛状态，但是收敛值却各不相同。免疫遗传算法第100代最优个 体的适应值是0.36967，遗传算法第100代最优个体的适应值是1.02796，免疫 算法第100代最优个体的适应值是0.41559。

图4和图5为实施例二，AUV的期望路径为AB，图4a为未采用实时路径 规划策略时AUV的航行轨迹，显然AUV无法通过半封闭的障碍区域，图4b 为加入本发明建立的免疫遗传算法进行实时路径规划后AUV的航行轨迹，由此 可见，本发明建立的免疫遗传实时路径规划方法为AUV提供了逃脱半封闭等陷 阱区域的手段。

实施例二中在第643.5秒、1234.5秒、724秒和1347秒共进行了4次实时 路径规划，图5a为第643.5秒时实时路径规划的结果，图5b为第1347秒时实 时路径规划的结果。