﻿ 基于量子蚁群算法的无人水面艇航迹规划
«上一篇
 文章快速检索 高级检索

 哈尔滨工程大学学报  2019, Vol. 40 Issue (7): 1263-1268  DOI: 10.11990/jheu.201807059 0

### 引用本文

XIA Guoqing, HAN Zhiwei, ZHAO Bo, et al. Unmanned surface vessel path planning based on quantum ant colony algorithm[J]. Journal of Harbin Engineering University, 2019, 40(7), 1263-1268. DOI: 10.11990/jheu.201807059.

### 文章历史

1. 哈尔滨工程大学 自动化学院, 黑龙江 哈尔滨 150001;
2. 中国船舶工业集团有限公司 第七〇八研究所, 上海 200011

Unmanned surface vessel path planning based on quantum ant colony algorithm
XIA Guoqing 1, HAN Zhiwei 1, ZHAO Bo 1, YANG Ying 2
1. College of Automation, Harbin Engineering University, Harbin 150001, China;
2. 708th Research Institute, China State Shipbuilding Corporation Limited, Shanghai 200011, China
Abstract: Aiming at the problem of path planning for unmanned surface vehicle, the quantum ant colony algorithm is used in this paper to plan the shortest path with the lowest energy consumption and obstacle avoidance for unmanned surface vehicles in marine environments. The quantum ant colony algorithm shows high efficiency of quantum parallel computing and features a better optimizing ability of the ant colony algorithm. Simulation results show that the proposed algorithm can avoid the local extremum and converge faster than the ant colony algorithm, and therefore, it can plan the optimal path of an unmanned surface vehicle in complex marine environments.
Keywords: unmanned surface vessels (USV)    path searching    quantum theory    ant colony optimization    length    energy consumption    obstacle avoidance

1 USV及海洋环境建模 1.1 USV的动力学模型

 $\mathit{\boldsymbol{M\dot \nu }} + \mathit{\boldsymbol{C}}\left( \mathit{\boldsymbol{v}} \right)\mathit{\boldsymbol{v}} + \mathit{\boldsymbol{D}}\left( \mathit{\boldsymbol{v}} \right)\mathit{\boldsymbol{v}} = {\mathit{\boldsymbol{\tau }}_w} + {\mathit{\boldsymbol{\tau }}_{{\text{thr}}}}$ (1)
 ${\mathit{\boldsymbol{\tau }}_w} = {\mathit{\boldsymbol{\tau }}_{{\text{wind}}}} + {\mathit{\boldsymbol{\tau }}_{{\text{wave}}}} + {\mathit{\boldsymbol{\tau }}_{{\text{current}}}}$ (2)

1.2 海洋环境建模

1.2.1 风的干扰力模型

 $\left\{ \begin{array}{l} {\mathit{\boldsymbol{\tau }}_{{\rm{wind}}X}} = \frac{1}{2}{\rho _a}{A_f}V_w^2{C_{wx}}\left( {{\alpha _R}} \right)\\ {\mathit{\boldsymbol{\tau }}_{{\rm{wind}}Y}} = \frac{1}{2}{\rho _a}{A_s}V_w^2{C_{wy}}\left( {{\alpha _R}} \right) \end{array} \right.$ (3)

1.2.2 浪的干扰力模型

 $\left\{ \begin{array}{l} {\mathit{\boldsymbol{\tau }}_{{\rm{wave}}X}} = \frac{1}{2}\rho L\zeta _{\rm{D}}^2{C_{XD}}\left( \lambda \right)\cos \chi \\ {\mathit{\boldsymbol{\tau }}_{{\rm{wave}}Y}} = \frac{1}{2}\rho L\zeta _{\rm{D}}^2{C_{YD}}\left( \lambda \right)\sin \chi \end{array} \right.$ (4)

1.2.3 流的干扰力模型

 $\left\{ \begin{array}{l} {\mathit{\boldsymbol{\tau }}_{{\rm{current}}X}} = \frac{1}{2}\rho {A_{\rm{f}}}V_{\rm{c}}^2{C_X}\left( \beta \right)\\ {\mathit{\boldsymbol{\tau }}_{{\rm{current}}Y}} = \frac{1}{2}\rho {A_{\rm{s}}}V_{\rm{c}}^2{C_Y}\left( \beta \right) \end{array} \right.$ (5)

1.3 栅格法环境建模

 ${L_{i,i + 1}} = \left\{ \begin{array}{l} \;\;1,\;\;\;\;\;{x_i} = {x_{i + 1}},{y_i} = {y_{i + 1}}\\ \sqrt 2 ,\;\;\;\;其他 \end{array} \right.$ (6)

1.4 USV全局航迹规划的优化目标

1.4.1 航迹长度

USV的航迹总长度为：

 $L = \sum\limits_{i = 1}^m {{L_{i,i + 1}}}$ (7)

1.4.2 航迹能耗

 $E = \sum\limits_{i = 1}^m {{E_{i,i + 1}}}$ (8)

 $E_{i, i+1}=\tau_{w}\left|\boldsymbol{v}_{\mathrm{usv}}\right| t$ (9)
 $t=L_{i, i+1} /|\boldsymbol{v}|$ (10)

1.4.3 航行安全避障

 ${P_{{\rm{safe}}}} = \left\{ {\begin{array}{*{20}{l}} {1,}&{d \ge {d_{{\rm{safe}}}}}\\ {\infty ,}&{d < {d_{{\rm{sfe}}}}} \end{array}} \right.$ (11)

1.4.4 综合代价函数

 $\min J=P_{\mathrm{safe}}\left(w_{L} L+w_{E} E\right)$ (12)

 $\left\{ {\begin{array}{*{20}{l}} {L \le {L_{\max }}}\\ {0 < \left| {{\mathit{\boldsymbol{v}}_i}} \right| \le {\mathit{\boldsymbol{v}}_{\max }}} \end{array}} \right.$ (13)

2 量子蚁群算法 2.1 量子编码与量子旋转门

 ${\mathit{\boldsymbol{X}}_i} = \left[ {\begin{array}{*{20}{c}} {\cos {\theta _{i1}}}&{\cos {\theta _{i2}}}& \cdots &{\cos {\theta _{{\rm{in}}}}}\\ {\sin {\theta _{i1}}}&{\sin {\theta _{i2}}}& \cdots &{\sin {\theta _{{\rm{in}}}}} \end{array}} \right]$ (14)

 $U\left( \theta \right) = \left[ {\begin{array}{*{20}{c}} {\cos \theta }&{ - \sin \theta }\\ {\sin \theta }&{\cos \theta } \end{array}} \right]$ (15)

 $\left[ {\begin{array}{*{20}{c}} {\cos \varphi _{ij}^{t + 1}}\\ {\sin \varphi _{ij}^{t + 1}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\cos \theta }&{ - \sin \theta }\\ {\sin \theta }&{\cos \theta } \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {\cos \varphi _{ij}^t}\\ {\sin \varphi _{ij}^t} \end{array}} \right]$ (16)

2.2 蚂蚁转移规则与转移概率

 $\begin{array}{*{20}{c}} {s = }\\ {\left\{ \begin{array}{l} \arg \mathop {\max }\limits_{s \in S} \left\{ {{{\left[ {\tau _{ij}^k\left( t \right)} \right]}^a}{{\left[ {\eta _{ij}^k\left( t \right)} \right]}^b}{{\left[ {{\varepsilon _{ij}}\left( t \right)} \right]}^c}} \right\},\;\;\;\;q \le {q_0}\\ \bar s,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;q > {q_0} \end{array} \right.} \end{array}$ (17)

 $p_{ij}^k\left( t \right) = \frac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^a}{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^b}{{\left[ {{\varepsilon _{ij}}\left( t \right)} \right]}^c}}}{{\sum\limits_{s \in {\rm{allowed}}\left( i \right)} {{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^a}{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^b}{{\left[ {{\varepsilon _{ij}}\left( t \right)} \right]}^c}} }}$ (18)

2.3 信息素更新规则

 $\tau \left( {{p_j}} \right) = \left( {1 - {\rho _1}} \right)\tau \left( {{p_i}} \right) + {\rho _1}\Delta {\tau _{ij}}$ (19)

 $\Delta {\tau _{ij}} = \sum\limits_{k = 1}^n {\Delta \tau _{ij}^k}$ (20)
 $\Delta \tau _{ij}^k = \left\{ \begin{array}{l} Q/{J_k},\;\;\;\;第\;k\;只蚂蚁所走的路径\\ 0,\;\;\;\;\;\;\;\;\;\;\;其他 \end{array} \right.$ (21)

 $\tau \left( {{p_j}} \right) = \left\{ {\begin{array}{*{20}{l}} {\left( {1 - {\rho _2}} \right)\tau \left( {{p_j}} \right) + {\rho _2}\Delta {\tau _{{\rm{best}}}},}&{{p_u} = \tilde s}\\ {\left( {1 - {\rho _2}} \right)\tau \left( {{p_j}} \right),}&{{p_u} \ne \tilde s} \end{array}} \right.$ (22)
 $\Delta {\tau _{{\rm{best}}}} = \left\{ \begin{array}{l} Q/{J_e},\;\;\;边\left( {i,j} \right)属于本次循环中的\\ \;\;\;\;\;\;\;\;\;\;\;\;最优路径\\ 0,\;\;\;\;\;\;\;\;\;\;其他 \end{array} \right.$ (23)

2.4 基于QACA的USV全局航迹规划

QACA的原理是通过量子比特对ACA中蚂蚁在路径上留下的信息素进行编码，得到量子信息素，并根据路径上的量子信息素浓度来选择蚂蚁的转移方向。并通过量子旋转门改变蚂蚁自身携带的量子比特的相位。算法的具体步骤如下：

1) 初始化量子蚁群。设蚁群中蚂蚁个数为n，则每只蚂蚁会携带2个量子比特，最大迭代次数Nmax，其中t时刻量子蚁群可表示为：A(t)=(τ1t, τ2t, …, τnt)，则在第t次迭代中第i(i=1，2，…，n)只蚂蚁个体的量子比特可表示为τijt=[cosφijt, sinφijt]T，通过量子比特来表示各节点上的信息素浓度，即[cosφijt, sinφijt]T表示在第t次迭代时第i只量子蚂蚁在第j个节点上留下的信息素浓度值，φij=2π×Rnd为量子比特的相位；Rnd是(0, 1)之间随机数；

2) 将蚂蚁置于航迹规划空间的起始点上，然后按照蚂蚁的转移规则和转移概率选择节点；

3) 对每只蚂蚁经过一次一步移动后进行信息素局部更新，对所有蚂蚁完成一次迭代后的得到的最优路径进行全局更新；

4) 通过量子旋转门对量子蚁群A(t)的相位进行变换更新；

5) 整个蚁群走过所有的节点，根据蚂蚁对每个节点的选择信息，生成候选解，并计算相应候选解的航迹综合代价值；

6) 若tNmax，则转向步骤7)；否则，转向步骤2)；

7) 输出得到的最优解的节点及其相应的航迹总代价值，并根据最优解的节点得到最优航迹，算法结束。

3 航迹规划仿真实验 3.1 QACA和ACA在静态环境中的USV航迹规划

3.2 QACA在海洋环境中的USV航迹规划

 Download: 图 2 实验3和实验4中有海洋环境与无海洋环境的航迹对比 Fig. 2 Comparison of the path with the marine environment and without the marine environment in experiment 3 and experiment 4

4 结论

1) 量子蚁群算法相比较于蚁群算法拥有更快的收敛速度，并且可以有效地避免局部极值；

2) 量子蚁群算法可以在海洋环境中为无人水面艇规划出一条航程最短、航行能耗最低和能够安全避障的全局航迹。

1) 分析航迹规划问题中的各个优化目标之间的相关性，来得到更为合理的航行代价函数；

2) 对量子蚁群算法中涉及到的一些参数进行自适应处理，以实现在算法优化能力的提高；

3) 将量子蚁群算法应用到动态未知环境中的无人水面艇航迹规划。

 [1] CHU K, LEE M, SUNWOO M. Local path planning for off-road autonomous driving with avoidance of static obstacles[J]. IEEE transactions on intelligent transportation systems, 2012, 13(4): 1599-1616. DOI:10.1109/TITS.2012.2198214 (0) [2] NIU Hanlin, LU Yu, SAVVARIS A, et al. An energy-efficient path planning algorithm for unmanned surface vehicles[J]. Ocean engineering, 2018, 161: 308-321. DOI:10.1016/j.oceaneng.2018.01.025 (0) [3] 唐平鹏.复杂海况下水面无人艇分层危险规避方法研究[D].哈尔滨: 哈尔滨工程大学, 2014. TANG Pingpeng. Research on hierarchical obstacle avoidance for unmanned surface vehicle in complicated marine environments[D]. Harbin: Harbin Engineering University, 2014. https://max.book118.com/html/2017/0509/105530768.shtm (0) [4] KIM H, KIM S H, JEON M, et al. A study on path optimization method of an unmanned surface vehicle under environmental loads using genetic algorithm[J]. Ocean engineering, 2017, 142: 616-624. DOI:10.1016/j.oceaneng.2017.07.040 (0) [5] MA Yong, HU Mengqi, YAN Xinping. Multi-objective path planning for unmanned surface vehicle with currents effects[J]. ISA transactions, 2018, 75: 137-156. DOI:10.1016/j.isatra.2018.02.003 (0) [6] WU Peng, XIE Shaorong, LIU Hengli, et al. Autonomous obstacle avoidance of an unmanned surface vehicle based on cooperative manoeuvring[J]. Industrial robot:an international journal, 2017, 44(1): 64-74. DOI:10.1108/IR-04-2016-0127 (0) [7] AHMED F, DEB K. Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms[J]. Soft computing, 2013, 17(7): 1283-1299. DOI:10.1007/s00500-012-0964-8 (0) [8] 李明, 李铜桥. 基于非奇异终端滑模的欠驱动UUV航迹跟踪控制[J]. 应用科技, 2018, 45(2): 11-16. LI Ming, LI Tongqiao. Path-following control for an underactuated UUV based on non-singular terminal sliding mode[J]. Applied science and technology, 2018, 45(2): 11-16. (0) [9] 马英凯, 刘志林, 冯江, 等. 基于航向控制的欠驱动船舶曲线航迹控制[J]. 应用科技, 2018, 45(1): 26-32. MA Yingkai, LIU Zhilin, FENG Jiang, et al. Control on the curve track of an underactuated surface vessel based on heading control[J]. Applied science and technology, 2018, 45(1): 26-32. (0) [10] 韩鹏, 刘志林, 周泽才, 等. 基于LOS法的自航模航迹跟踪控制算法实现[J]. 应用科技, 2018, 45(3): 66-70. HAN Peng, LIU Zhilin, ZHOU Zecai, et al. Path tracking control algorithm based on LOS method for surface self-propulsion vessel[J]. Applied science and technology, 2018, 45(3): 66-70. (0) [11] FOSSEN T I. Handbook of marine craft hydrodynamics and motion control[M]. New York: Wiley, 2011. (0) [12] KIM H, KIM D, SHIN J U, et al. Angular rate-constrained path planning algorithm for unmanned surface vehicles[J]. Ocean engineering, 2014, 84: 37-44. DOI:10.1016/j.oceaneng.2014.03.034 (0) [13] LEE T, KIM H, CHUNG H, et al. Energy efficient path planning for a marine surface vehicle considering heading angle[J]. Ocean engineering, 2015, 107: 118-131. DOI:10.1016/j.oceaneng.2015.07.030 (0) [14] NARAYANAN A, MOORE M. Quantum-inspired genetic algorithms[C]//Proceedings of IEEE international conference on evolutionary computation. IEEE, 1996: 61-66. (0) [15] HAN K H, KIM J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE transactions on evolutionary computation, 2002, 6(6): 580-593. DOI:10.1109/TEVC.2002.804320 (0) [16] 李士勇, 李盼池. 量子计算与量子优化算法[M]. 哈尔滨: 哈尔滨工业大学出版社, 2009: 108-112. LI Shiyong, LI Panchi. Quantum computation and quantum optimization algorithms[M]. Harbin: Harbin Institute of Technology Press, 2009: 108-112. (0) [17] 李士勇, 柏继云. 连续函数寻优的改进量子扩展蚁群算法[J]. 哈尔滨工程大学学报, 2012, 33(1): 80-84. LI Shiyong, BAI Jiyun. Extended quantum ant colony algorithm for continuous function optimization[J]. Journal of Harbin Engineering University, 2012, 33(1): 80-84. DOI:10.3969/j.issn.1007-7043.201011062 (0) [18] 王芳.基于量子蚁群算法的多无人机协同航迹规划研究[D].哈尔滨: 哈尔滨工业大学, 2015. WANG Fang. Collaborative path planning of UAVs based on quantum ant colony algorithm[D]. Harbin: Harbin Institute of Technology, 2015. (0) [19] LIU Min, ZHANG Feng, MA Yunlong, et al. Evacuation path optimization based on quantum ant colony algorithm[J]. Advanced engineering informatics, 2016, 30(3): 259-267. DOI:10.1016/j.aei.2016.04.005 (0) [20] 何小锋, 马良. 带时间窗车辆路径问题的量子蚁群算法[J]. 系统工程理论与实践, 2013, 33(5): 1255-1261. HE Xiaofeng, MA Liang. Quantum-inspired ant colony algorithm for vehicle routing problem with time windows[J]. Systems engineering-theory & practice, 2013, 33(5): 1255-1261. DOI:10.3969/j.issn.1000-6788.2013.05.021 (0)