一种用于群无人艇避碰的动态分组策略

2019-05-10王玉龙

中国航海 2019年1期

王玉龙, 马勇

(武汉理工大学 a. 航运学院，武汉 430063； b. 内河航运技术湖北省重点实验室，武汉 430063)

随着智能控制、动态轨迹规划等新兴技术的发展，水面无人艇(Unmanned Surface Vehicle，USV)已具备了一定的自主航行能力，在海洋科考、海事管理和水上搜救等领域发挥了重要作用。[1]多年来以单个无人艇为中心的自主避碰已经取得一定的研究成果[2]，但是在群无人艇避碰方面的研究尚存在诸多问题需要解决。

针对避碰过程中需考虑的因素，研究者从船舶避碰的经验中抽象出各种概念并加以量化运用。文献[3]在遵守国际海上避碰规则(International Regulations for Preventing Collisions at Sea, COLREG)的基础上分析航行规则。文献[4]利用航速、航向等计算碰撞危险度。文献[5]对船舶领域进行划分并分析会遇态势。文献[6]采用KT方程作为船舶运动控制模型，为应对复杂的碰撞环境，考虑操纵性能并使用PID(Proportion Integral Differential)算法作为控制策略。文献[7]在矢量障碍物算法的基础上提出最优化互利避碰算法，进而计算出最佳的转向角度。为进一步找出最优的避碰路径。文献[8]使用蚁群优化算法规划静态的避碰路径。文献[9]使用多目标非线性优化方法求解最优路径，但是传统的避碰方法存在诸多缺陷，首先静态的路径规划不能适应多变的避碰环境，其次没有考虑避碰对象的能动性。为克服传统避碰方法的缺陷，研究者从行为控制的角度研究，基于行为控制表示导航和任务行为[10]找出最优的避碰方案。文献[11]使用模糊推断的方法预测船舶一段时间后的运动轨迹。文献[12]采用分布式随机搜索算法结合时间窗来预测船舶的航行状态。当前诸多研究中仅考虑一般态势下的无人艇避碰问题，较少关注群无人艇的避碰问题；在无人艇的态势划分、操纵性和航行规则应用等方面有一定的改进空间；同时，设计的避碰算法尚未体现出群无人艇避碰问题中运动障碍物的能动性等实际情况。

针对无人艇避碰中存在的相关不足，本文拟提出一种动态分组策略以有效地解决群无人艇避碰问题。主要工作包括：

1) 在建立无人艇控制模型、避碰规则模型后，提出解决群无人艇复杂会遇局面下的避碰问题。

2) 提出动态分组策略，考虑交通流的特性并对无人艇行为预测，实现群无人艇的动态分组。

3) 开展多种场景下群无人艇避碰仿真试验，证实动态分组策略的有效性。

1 无人艇避碰规则建模

USV是指具有自主航行能力并且操纵性良好的一种无人艇。为实现避碰过程中的计算，建立无人艇艇体坐标系见图1。

图1中无人艇具有运动属性航向C0、航速V0和舵角δ0，以无人艇为中心，将直角坐标系和极坐标系融合，无人艇航向作为Oy轴，与其垂直的右正横方向作为Ox轴，从航向开始顺时针旋转的极角作为相对方位角θ0。

无人艇航向操纵使用比例积分微分PID算法控制，具有通过控制舵角实现快速调整航向的能力。根据野本谦作方程和PID控制算法，可推导出离散化操舵公式为

e(k)=r(k)-ψ(k)

(1)

(2)

(3)

δk=δk-1+Δu(k)

(4)

式(1)～式(4)中：e(k)为第k次航向偏差值；r(k)为目标航向；ψ(k)为第k次航向角；K0、T0为旋回性系数和稳定性系数；δ0为初始舵角；T为采样周期；Δu(k)为第k次舵角增量；δk为第k次舵角。

根据无人艇航向自主控制公式，可计算其转向进距Ad和转向横距Td(见图2)。用Ck表示第k次采样得到的无人艇航向，设初始航向为C0，在第n次采样时航向达到目标航向Cn，由式(2)和式(3)可推导出Ad、Td。

Ck=Ck-1+ψ(k)

(5)

(6)

(7)

为使无人艇满足自身的操纵性能同时遵守COLREGs，将会遇态势进一步量化，参考英国航海协会推荐的雷达避碰操纵方法[13]在艇体坐标系下将会遇态势划分对遇、交叉相遇和追越等3种，效果见图3。

图3 无人艇艇体坐标系下的会遇态势划分

同时，为判断无人艇间的碰撞危险，将无人艇转向进距的2倍作为无人艇危险距离S，即S=2Ad，Td保证无人艇转向过程中能安全驶过，并且考虑无人艇属性艇长L和艇宽W，将无人艇长度L的2倍[14]作为最小安全距离Dm。在COLREGS的基础上对无人艇做出以下操纵约束[15]。

1) 对于分到同一组的无人艇做同组计算。无人艇在航行过程中考虑同组无人艇密度ρ=A/d，其中A表示同组无人艇所占区域面积，d表示同组中无人艇的平均间距，如果ρ>L2/Dm，则无人艇应当调整航速小于等于前方无人艇，使其能在给定的前进方向上不与前方无人艇形成最小安全距离Dm。

2) 避碰中采取动作的原则。无人艇根据航向、航速和周边无人艇的位置关系调整避碰动作，在保证最小安全距离Dm的同时，尽可能采取大幅度动作避碰。

3) 无人艇会遇局面，在无人艇接近到碰撞危险距离s时判定有碰撞危险，会遇局面形成。

(1) 对遇局面。运动目标在艇艏向(-5°，5°]范围时，认为处于对遇局面，向右转向避碰；

(2) 交叉相遇局面。运动目标在舷角(5° 90°]和(247.5°，355°]时，向右转向避碰，运动目标在舷角(90°，112.5°]时向左转向避碰；

(3) 追越。避碰过程中禁止主动追越，应当调整航速小于等于前方无人艇。同时，运动目标在舷角(112.5°，210°]时向左转向避碰;运动目标在舷角(210°，247.5°]时，向右转向避碰。

2 多目标动态分组策略

水上交通流是在水路交通中表现出来的类似于流体特征的交通工具运动总体。[16]无人艇作为水上交通流的组成部分，在交通流影响下具有相似的个体行为特征，分组算法基于交通流宏观思想，结合几何分析和聚类算法对群无人艇进行分组，实现快捷、高效的避碰。

图4 全局坐标系x0O0y0中群无人艇位置关系

在全局坐标系x0Ο0y0中有n艘无人艇(见图4)，其艇长均为L，艇宽均为W，第i艘无人艇为USVi，运动属性有航行方向Ci，前进速度Vi，映射到Ο0x0轴的坐标为posxi、映射到O0y0轴的坐标为posyi。

实际中USV获取的是周边无人艇/船舶相对位置关系，所以需要将全局坐标USV转换成艇体坐标系中，进而分析本艇USV0与周边无人艇/船舶的关系(见图5)。艇体坐标系中USVi属性[Xpi,Ypi]表示位置，ci表示航向。vi表示航速，转换式(8)～式(10)如下，将无人艇/船舶按照转换公式转换到艇体坐标系xOy中，有

[XpiYpi]=[posxi-posx0posyi-posy0]

(8)

ci=Ci-C0

(9)

vi=Vi

(10)

在艇体坐标系中可得出USVi的相对方位角θi。

图5 转换后USV0与其他无人艇位置关系

无人艇在同一交通流中具有相似的航行行为，具体表现在位置相关度高及航行轨迹相似。据此原理可推导出无人艇相似度μ的表达式为

μ=

(11)

式(11)中：xpi、xpj为无人艇USVi、USVj的Ox轴坐标；ypi、ypj为无人艇USVi、USVj的Oy轴坐标；ci、cj为无人艇USVi、USVj的航向；vi、vj为无人艇USVi、USVj的航速。

根据转换后的位置关系，可得出周边无人艇可分为一组的最大相似度值μmax为

(12)

式(12)中：α为相似航向角最大值，最小相似度值μmin为

(13)

计算无人艇USVi与周无人艇USVj的相似度为

(14)

式(14)中：0≤μij≤1，表明USVi、USVj具有相似的行为属性而分为一组，if USVi～USVjand USVj～USVkthen USVi～USVk。

按照相似度计算公式对周边无人艇进行分组，分为G1,G2,…，Gi,…，Gm共m个分组，通过凸包扫描算法可求取各分组边界。

1) 将周边USV按照相对方位角θi排序。

2) 根据式(14)将群无人艇中各无人艇分到不同的组Gi中。

3) 求取凸包边界点序列H，将分组中的USV看作质点，根据Graham算法依次判断是否加入凸包栈H中，最终得到凸包点序列。

由此，根据上述分组策略，得到分组聚类效果示意见图6。

群无人艇的运动既促成交通流的形成，同时其操纵行为又会对现有的交通流造成影响。为能够更好地做出正确决策，需要对无人艇/船舶运动轨迹做出预测，前向预测根据航行规则和当前运动状态，可计算出时间段Δt后无人艇的运动状态和位置变化。设无人艇在时间t的状态属性是Q(t)，无人艇在不同会遇态势下所做的操纵可表示为R(t)，由此可得出Δt后无人艇的运动状态。

(15)

(16)

式(16)中:t0为t0时刻;θ为USV相对方位角;M(Q(t),R(t))表示USV在t时刻的运动状态和航行规则时做出的定性操纵决策。

在第1节的避碰规则下，交差相遇局面的无人艇会逐渐演变为对遇局面，追越局面因其中同组安全航速规则而消除碰撞危险，对遇局面成为最难判断的局面，所以对于对遇局面的前向预测需要进一步分析。现根据前向预测来分析无人艇对遇局面的状态变化，将两组之间状态的预测进行划分，得出式(17)的3种情况(见图7)，图7中分别为分组G1、G2，其位置水平分量为PG1(x)、PG2(x)，速度水平分量为VG1(x)、VG2(x)。

(17)

根据图7的状态划分，可计算获得两两分组G1、G2间的可行角度ξ，进而为群无人艇做出可信的操纵决策。

1) 当G1、G2呈现聚合运动趋势时，计算G1、G2各自凸包边界无人艇的最近会遇距离(Distance to Closest Point of Approach, DCPA)，设最小|dCPA|一侧的相对方位角为θ，则可行转向角度ξ=θ。

2) 当G1、G2呈现分散运动趋势时，计算G1、G2的最小会遇时间(Time to Closest Point of Approach, TCPA)，取最小tCPA作为预测时间间隔Δt，计算G1、G2在Δt时间后的最小夹角(ξ1,ξ2)，则ξ= (ξ1+ξ2)/2。

3) 当G1、G2呈现同向运动趋势时，计算G1、G2凸包边界无人艇的DCPA，取形成最小|dCPA|无人艇的相对方位角为θ，则可行转向角度ξ=θ。

根据分组策略将无人艇分成多股交通流，结合航行规则并利用前向预测对无人艇的运动状态做出一段时间的预测。在此基础上，依据速度矢量计算[7]可得出最终的转向角度，解决群无人艇避碰问题。动态分组策略下的群无人艇避碰决策过程见图8。

3 群无人艇避碰仿真

在全局坐标系x0O0y0下开展多种场景下的群无人艇避碰仿真，借鉴文献[17]中的仿真分析模式，验证本文提出的动态分组策略的有效性。

图8 动态分组策略下的群无人艇避碰决策过程

3.1 无人艇属性定义

无人艇艇长L=3 m，艇宽W=1 m，操纵性KT指数K0=2，T0=5，PID控制算法参数Kp=0.8，Ki=5，Kd=10，可计算出群无人艇间最小安全距离Dm= 2L= 6 m。使用此无人艇在多种场景下进行如下仿真。

3.2 多场景下的群无人艇避碰仿真

3.2.1一般会遇态势下的群无人艇避碰仿真

为明确本文方法的优越性，特选择文献[4] 中5艘USV避碰的案例进行对比，还考虑了USV操纵性、避碰规则以及危险距离等因素，在此条件下应用本文的避碰方法进行仿真测试。群无人艇的初始参数见表1，5艘USV形成复杂的多艇会遇态势，包含了对遇、追越、交叉相遇等3种会遇情况，测试结果见图9。

表1 仿真案例1中的5艘无人艇初始参数

b)时段1～125 s的无人艇轨迹

c) 航向C历时曲线

d) 舵角δ历时曲线

e) 速度V历时曲线

f) USV1与其它无人艇间距变化历时曲线

图9 5艘USV避碰过程参数变化组图

从结果中可看出：

(1) 从本案例结果与文献[4]的仿真结果来看，本案例避碰的动作更加自然。从图9 a可知，起初5艘无人艇处于复杂的会遇态势之中，但是经过40 s后，本文的避碰算法使得整体的态势发生了转变，USV1、USV2与USV4形成一股交通流，USV3和USV5则按照避碰规则向右转向，使得会遇态势迅速简化。相对于文献[4]的结果，本文不仅考虑无人艇之间的态势变化，而且兼顾航速航向，如图9 e速度的变化，由于分组的影响，最终速度趋于一致，同时航向也有接近的趋势，总体的避碰决策随着周边态势的变化而调整；

(2) 仿真结果表明在经过125 s后，5艘USV都能安全避碰并且驶过，同时本文中的避碰动作更加自然流畅，想比于文献[4]中的规划路线，本文避碰过程中不断调整航向和航速，针对态势的变化调整避碰决策，能够应对复杂多变的避碰环境。

3.2.2多组复杂交通流场景下的群无人艇避碰仿真

为进一步证实动态分组策略能够应对更为复杂的会遇态势，突出对群无人艇避碰的优势，特针对多组群无人艇避碰进行了仿真演示。现在仿真中初始化9艘USV，初始运动状态见表2。

表2 案例2中的9艘无人艇初始状态

由图10可知：9艘USV自主分为3组并形成3股交通流，具有一致的避碰行为，USV1、USV2、USV3作为G1组和USV4、USV5、USV6为G2组均处在交叉相遇和对遇的态势中， USV7、USV8、USV9为G3处在复杂交叉相遇态势中，G1组向右转向避让，G2组小幅度操纵并最终和G3组形成一股交通流。86 s后会遇态势简化并且安全驶过。

3.3 仿真结果分析

对仿真结果进行分析后可知:案例1在一般态势下能够以最少的操纵方法避让周边无人艇/船舶，同时，协调周边无人艇/船舶形成有规律的交通流，最终完成避碰。案例2在无人艇/船舶较多的情况下，交通流情形更为复杂，因此，可充分体现出动态分组策略在群无人艇避碰问题中的优越性和有效性。动态分组策略充分考虑交通流的特性，将处于复杂态势下的无人艇/船舶引导至有规律的交通流，进而有效解决群无人艇的避碰问题。