舰船科学技术  2019, Vol. 41 Issue (12): 173-176   PDF    
基于混沌蜂群算法的USV路径规划
兰莹, 章甜     
上海海事大学,上海 201306
摘要: 针对多障碍物环境下,传统智能算法容易过早收敛、搜索精准度差等问题,为提高路径规划准确性,获得最佳路径,避免碰撞发生,提出一种基于人工蜂群算法的水上无人艇路径规划方法。通过栅格法建模,以无人艇目的地为蜜源,在蜂群信息交换阶段,采用混沌序列产生初始化雇佣蜂,跳出局部最优。与传统人工蜂群算法进行对比,仿真结果表明,混沌蜂群算法在路径优化方面更能找到全局最优路径。
关键词: 混沌算子     蜂群算法     无人艇     栅格法     路径规划     全局最优    
USV path planning problem based on chaotic bee colony algorithm
LAN Ying, ZHANG Tian     
Shanghai Maritime University, Shanghai 201306, China
Abstract: In this paper, the path planning problem of unattended boat USV on water is studied. aiming at the problem of safe navigation performance of unmanned boat on water in multi-obstacle environment, the traditional intelligent algorithm is easy to converge prematurely and the search accuracy is poor. In order to improve the accuracy of path planning, obtain the best path and avoid collision, a path planning method for unmanned boats on water based on artificial bee colony algorithm is proposed. Through grid modeling, taking the destination of unmanned boat as honey source, in the stage of bee colony information exchange, chaotic sequence is used to generate initial employment bee and jump out of local optimization. Compared with the traditional artificial bee colony algorithm, the simulation results show that the chaotic bee colony algorithm can find the global optimal path better in the aspect of path optimization.
Key words: chaotic operator     bee colony algorithm     unmanned vessel     grid method     path planning     Global optimum    
0 引 言

路径规划通常分为两类,一类是全局路径规划,即在已知的环境中,依照距离最短、能耗最低、耗时最短为目标,找到一条避开障碍物的最优路径,全局最优的典型算法包括A*算法、D*算法等。二类是局部路径规划,即事先并不完全知道地图环境,根据当前已探知的信息完成路径选择。近年来,不少学者将全局路径优化算法与智能算法相结合,尤其是新兴智能优化算法的使用。吴丰君[1]提出了基于协作思想的改进粒子群优化算法,郑佳春等[2]提出一种基于混合模拟退火与粒子群优化的无人艇路径规划算法,倪生科等[3]提出一种基于混合遗传算法的船舶避碰路径规划,YUE等[4]介绍了一种基于蚁群算法的无人小车路径规划算法,王鹏等[5]提出一种混合自适应蚁群算法的AUV路径规划方法,田屏[6]提出一种基于混沌搜索改进的人工蜂群算法。

人工蜂群算法(ABC)于2005年由Karaborg提出,在函数优化方面的效果明显[7],相比于上述优化算法,人工蜂群算法具有参数设置少、计算简单、收敛快等特点。但同样容易陷入局部最优,本文将基于人工蜂群算法结合Logistics混沌映射产生雇佣蜂的混合算法,优化USV作业路径。

1 模型建立

为方便问题分析,对无人艇作以下假设:

1)船载监测设备已探知小船周围障碍物位置;

2)无人艇行驶的环境为二维平面,忽略水面波浪所致小船起伏;

3)忽略障碍物高度,每一个障碍物占据一个二维栅格;

4)无人艇、目标点、障碍物位置均处于栅格中心点;

5)无人艇最大转向角为45°。

而路径规划之前,通常要对无人艇的作业环境进行建模。常见的环境建模法包括顶点图、邻接图、栅格法等,其中最为常见的即栅格法建模,通过栅格将地图环境进行存储,包括起点、终点、障碍点信息。栅格地图的距离计算通常有3种方式。

1)曼哈顿距离。曼哈顿距离即坐标系中两点的绝对轴距之和,其表达式如下式:

$ {h_M}(n) = \left(\left| {{x_n} - {x_{goal}}} \right| + \left| {{y_n} - {y_{goal}}} \right|\right){\text{,}} $ (1)

2)切比雪夫距离。切比雪夫距离被称为棋盘距离,其表达式下式:

${h_c}(n) = \max \left(\left| {{x_n} - {x_{goal}}} \right| + \left| {{y_n} - {y_{goal}}} \right|\right){\text{,}}$ (2)

3)欧几里得距离。其值直接可以看作两个位置点在欧式空间中的两点的直线距离,其表达式如下式:

${h_g}(n) = \sqrt {\left(\left| {{x_n} - {x_{goal}}} \right| + \left| {{y_n} - {y_{goal}}} \right|\right)}{\text{。}} $ (3)

无人艇的最大转向角设定为45°,曼哈顿距离只能支持横向、纵向的移动,故距离计算选择可以斜向行走的切比雪夫距离。

假设无人艇单位时间内移动的距离为R,则根据探测器探测范围距离内的海域按栅格进行等距划分,每一行、每一列的栅格数为:

$\left\{\begin{aligned} {N_x} = \dfrac{{{Y_{\max }}}}{R} {\text{,}}\\ {N_y} = \dfrac{{{X_{\max }}}}{R}{\text{。}} \end{aligned}\right. $ (4)

其中:YmaxXmax分别为探测范围内的纵向、横向的最远距离。

无人艇路径规划是避免碰撞的前提下,保证路径长度最短,是一个典型的约束最优问题,数学模型描述如下:

$\min f(x),X \in R{\text{,}}$ (5)

约束条件[8] ${g_i}(X) \leqslant 0,i = 1,2, \cdots ,p$

对于此类带约束非线性最优化问题,可以将其转化为无约束最优化问题,等价于一个能量优化函数E,其由路径长度函数(Ei)和碰撞惩罚函数(Ec)组成。

含有N个路径节点的情况,路径长度函数El为所有线段长度之和,即

${E_l} = \sum\nolimits_{i = 1}^{N - 1} {L_i^2} = \sum\nolimits_{i = 1}^{N - 1} {[{{({x_{i + 1}} - {x_i})}^2} + {{({y_{i + 1}} - {y_i})}^2}]} {\text{。}}$ (6)

碰撞惩罚函数Ec为无人小船在作业过程中,全部路径节点的碰撞惩罚函数能量之和,即

${E_c} = \sum\nolimits_{i = 1}^N {\sum\nolimits_{}^K {C_i^k} }{\text{。}} $ (7)

其中: ${{C}}_{{i}}^{{k}}$ 为第i个路径节点对于第k个障碍点的碰撞惩罚函数,K为障碍点数量,N为路径节点数量。整条路径能量函数E为:

$E = {\mu _l}{E_l} + {\mu _c}{E_c}{\text{。}}$ (8)

其中权值 ${\mu _l} + {\mu _c} = 1$ ,目标函数为:

$\min E(X \in {R^N}){\text{。}}$ (9)
2 蜂群算法与改进

人工蜂群算法(Artificial Bee Colony Algorithm,ABC算法)是一个由蜂群行为启发的算法,在2005年由Karaboga小组为优化代数问题而提出。人工蜂群算法包含3个基本元素:蜜源、雇佣蜂、侦察蜂[9]。其中蜜源代表问题解空间内的各种可行解,每个解是 ${X_i}(1,2 \cdots ,m)$ 一个D维向量。雇佣蜂则是用来引领蜂群,并保存蜜源的相关信息,其数量和蜜源数量相等。侦察蜂则需要在蜜源附近随机搜索新的蜜源,选中蜜源后,雇佣蜂继续引领蜂群保存蜜源信息,并留下较优解。循环直至算法结束。

在标准人工蜂群中,蜜源更新位置公式如下:

${V_{ij}} = {x_{ij}} + {R_{ij}} \times ({x_{ij}} - {x_{kj}}){\text{。}}$ (10)

式中: $K \in (1,2 \cdots ,SN)$ ,SN是种群规模, $j \in (1,2 \cdots , $ $d)$ ,即随机选取下标。Rij是[−1,1]之间的随机数。

侦察蜂的蜜源选择概率公式:

${P_i} = \frac{{fi{t_i}}}{{\sum\nolimits_{i = 1}^{SN} {fi{t_i}} }}{\text{。}}$ (11)

针对传统蜂群算法的不足,本文提出在信息素更新时引入混沌算子,通过混沌序列的全空间遍历和变异操作的特性来增加算法种群多样性,迭代后期则去除混沌扰动避免振荡。

引入混沌序列对随机数序列进行动态调整改进,目的是当一定参数设置下,混沌序列的输出可以呈现完全无序,随机,遍历状态,起源于虫口模型的Logistic混沌序列在 $\mu = 4$ 时( $\mu $ 为增长率),系统处于混沌工作状态[10],公式如下:

${\tau _{{\rm{ij}}}}(t + 1) = \mu {\tau _{ij}}(1 - {\tau _{ij}}(t)){\text{。}}$ (12)

式中: ${\tau _{ij}}(0)$ 为初值, ${\tau _{ij}}(t)$ 指算法在第iter次迭代时的值,根据混沌理论,当初值 ${\tau _{ij}}(0)$ 不等于0.25,0.5,0.75时,序列完全处于混沌态,提高搜索多样性。

图1图4为处于混沌状态的随机序列和特殊值下的混沌序列。

图 1 µ=4 τ=0.3 Fig. 1 µ=4 τ=0.3

图 2 µ=4 τ=0.6 Fig. 2 µ=4 τ=0.3

图 3 µ=4 τ=0.9 Fig. 3 µ=4 τ=0.9

图 4 µ=4 τ=0.25 Fig. 4 µ=4 τ=0.25

当雇佣蜂转变为侦察蜂时,将产生一个D维随机向量 ${\tau _0} = [{\tau _{01}},{\tau _{02}}, \cdots {\tau _{0D}}]$ ${\tau _0} \in [0,1]$ 并不等于特殊值。 ${\tau _0}$ 作为初始值,由Logistic混沌映射式得到蜜源附近多个邻域解,从而得到经混沌操作后的新蜜源:

${\overline \tau _{ij}} = {x_{ij}} + {R_{ij}}(2{\tau _{ij}} - 1){\text{。}}$ (13)

目的是将 ${\tau _{ij}}$ 映射到优化变量 ${\overline \tau _{ij}}$ 上, ${\overline \tau _{ij}}$ 是在雇佣蜂所在的蜜源为中心,以 ${R_{ij}}$ 为半径的区域上。算法流程图如图5所示。

图 5 算法流程图 Fig. 5 Flow chart of algorithm

1)建立栅格化环境模型。

2)设置混合混沌ABC算法的基本参数,包括种群大小,最大迭代次数itermax,当前迭代次数iter,蜜源数量。

3)雇佣蜂阶段,根据蜜源更新公式随机搜索附近新蜜源,贪心原则,选择更优的蜜源位置。

4)侦察蜂阶段,根据概率选择公式,对雇佣蜂所分享的蜜源信息进行选择。

5)侦察蜂阶段,重新根据蜜源更新公式在新被选中的蜜源附近进行搜索,计算收益度,收益度高的置为当前蜜源,否则不变。

6)迭代进行,当蜜源未更新次数达到limit值,雇佣蜂转变为侦察蜂,利用混算搜索算子搜索新蜜源。

3 算法仿真

蜜源表示可能的最优解,即设置在Win10环境下,基于Matlab2016b安照表1初始化数据进行仿真计算,结果如图6~图9所示。

表 1 初始化数据 Tab.1 Initialization data

图 6 传统ABC算法路径结果 Fig. 6 Path results of traditional ABC algorithm

图 7 传统ABC算法迭代图 Fig. 7 Iterative diagram of traditional ABC algorithm

图 8 混沌ABC算法路径结果 Fig. 8 Path result of chaotic ABC algorithm

图 9 混沌ABC算法迭代图 Fig. 9 Iterative diagram of chaotic ABC algorithm.

图6图7可以看出,改进后的混沌ABC算法比传统ABC算法明显降低了路径长度。由图8图9可以看出,改进后的算法有效避免了ABC算法的早熟收敛问题。

4 结 语

提出结合混沌局部搜索算法的改进人工蜂群算法,用以解决USV的路径规划问题。该算法利用Logistcis混沌序列的全空间遍历特性避免ABC算法陷入局部最优,从而快速找到全局最优解。算例测试表明,与传统蜂群算法相比,改进后的算法在求解质量上有了提升,能够有效解决传统ABC算法局部收敛的问题,避免早熟收敛,并能为无人艇规划出一条可通行且较优的路径。

参考文献
[1]
吴丰君. 多机器人路径规划[D]. 北京化工大学. 2011(05): 33-35.
[2]
郑佳春, 吴建华, 马勇, 等. 混合模拟退火与粒子群优化算法的无人艇路径规划[J]. 中国海洋大学学报(自然科学版), 2016, 46(09): 116-122.
[3]
倪生科, 刘正江, 蔡垚, 等. 基于混合遗传算法得船舶避碰路径规划[J]. 上海海事大学学报, 2019, 40(01): 21-26.
[4]
Longwang YUE, Hanning CHEN. Unmanned vehicle path planning using a novel ant colony algorithm[J]. EURASIP Journal on Wireless Communications and Networking, 2019(1): 136.
[5]
王鹏, 孟鹏, 宁腾飞. AUV巡航路径规划建模及仿真研究[J]. 计算机应用与软件, 2014(31): 268-270.
[6]
田屏. 一种基于混沌搜索改进的人工蜂群算法[J]. 西南师范大学学报(自然科学版), 2018(07): 39-45.
[7]
KARABOGA Dcrvis. An idea based on honey bee swarm for numerical optimization[J]. Technical report-tr06 Erciyes University, Engineering Faculty, Computer Engineering Department, 2005, 213-223.
[8]
黎竹娟. 人工蜂群算法在移动机器人路径规划中的应用[J]. 计算机仿真, 2012(29): 247-250.
[9]
李端明, 程八一. 基于人工蜂群算法求解不同尺寸工件单机批调度问题[J]. 四川大学学报: 自然科学版, 2009(3): 657-662.
[10]
郑永爱, 宣蕾. 混沌映射的随机性分析[J]. 计算机应用与软件, 2011(12): 276-276.