路径规划通常分为两类,一类是全局路径规划,即在已知的环境中,依照距离最短、能耗最低、耗时最短为目标,找到一条避开障碍物的最优路径,全局最优的典型算法包括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) |
其中:Ymax和Xmax分别为探测范围内的纵向、横向的最远距离。
无人艇路径规划是避免碰撞的前提下,保证路径长度最短,是一个典型的约束最优问题,数学模型描述如下:
$\min f(x),X \in R{\text{,}}$ | (5) |
约束条件[8]为
对于此类带约束非线性最优化问题,可以将其转化为无约束最优化问题,等价于一个能量优化函数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) |
其中:
$E = {\mu _l}{E_l} + {\mu _c}{E_c}{\text{。}}$ | (8) |
其中权值
$\min E(X \in {R^N}){\text{。}}$ | (9) |
人工蜂群算法(Artificial Bee Colony Algorithm,ABC算法)是一个由蜂群行为启发的算法,在2005年由Karaboga小组为优化代数问题而提出。人工蜂群算法包含3个基本元素:蜜源、雇佣蜂、侦察蜂[9]。其中蜜源代表问题解空间内的各种可行解,每个解是
在标准人工蜂群中,蜜源更新位置公式如下:
${V_{ij}} = {x_{ij}} + {R_{ij}} \times ({x_{ij}} - {x_{kj}}){\text{。}}$ | (10) |
式中:
侦察蜂的蜜源选择概率公式:
${P_i} = \frac{{fi{t_i}}}{{\sum\nolimits_{i = 1}^{SN} {fi{t_i}} }}{\text{。}}$ | (11) |
针对传统蜂群算法的不足,本文提出在信息素更新时引入混沌算子,通过混沌序列的全空间遍历和变异操作的特性来增加算法种群多样性,迭代后期则去除混沌扰动避免振荡。
引入混沌序列对随机数序列进行动态调整改进,目的是当一定参数设置下,混沌序列的输出可以呈现完全无序,随机,遍历状态,起源于虫口模型的Logistic混沌序列在
${\tau _{{\rm{ij}}}}(t + 1) = \mu {\tau _{ij}}(1 - {\tau _{ij}}(t)){\text{。}}$ | (12) |
式中:
当雇佣蜂转变为侦察蜂时,将产生一个D维随机向量
${\overline \tau _{ij}} = {x_{ij}} + {R_{ij}}(2{\tau _{ij}} - 1){\text{。}}$ | (13) |
目的是将
1)建立栅格化环境模型。
2)设置混合混沌ABC算法的基本参数,包括种群大小,最大迭代次数itermax,当前迭代次数iter,蜜源数量。
3)雇佣蜂阶段,根据蜜源更新公式随机搜索附近新蜜源,贪心原则,选择更优的蜜源位置。
4)侦察蜂阶段,根据概率选择公式,对雇佣蜂所分享的蜜源信息进行选择。
5)侦察蜂阶段,重新根据蜜源更新公式在新被选中的蜜源附近进行搜索,计算收益度,收益度高的置为当前蜜源,否则不变。
6)迭代进行,当蜜源未更新次数达到limit值,雇佣蜂转变为侦察蜂,利用混算搜索算子搜索新蜜源。
3 算法仿真蜜源表示可能的最优解,即设置在Win10环境下,基于Matlab2016b安照表1初始化数据进行仿真计算,结果如图6~图9所示。
由图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. |