基于规则的多船协调避碰决策算法及仿真验证

刘炯炯， 刘克中， 杨 星， 熊 勇， 袁志涛， 吴晓烈

(武汉理工大学 a.航运学院； b.智能交通系统研究中心; c.内河航运技术湖北省重点实验室， 武汉 430063)

随着人工智能、大数据和船联网技术的快速发展，船舶智能航行在航海上的应用已成为海上智能交通的重要研究领域。[1]自动驾驶技术是船舶智能航行的核心内容，而船舶避碰决策研究又是自动驾驶技术的重要组成部分。[2]

在船舶避碰决策研究中，多船会遇局面下的避碰决策为难点问题之一。[3]针对多船避碰决策研究，大部分研究仅考虑“本船”进行避让操作，假设“来船”保向保速或已知运动轨迹，利用遗传算法[4]、速度障碍[5]和粒子群优化算法[6]等制订船舶避碰方案；部分研究为每艘船舶规划航行路径，船舶只有依照生成的路径航行才能安全通过[7]，与实际海上船舶避碰决策存在较大差异。船舶分布式避碰决策过程更符合海上实际避让，船舶根据实时会遇场景做出避让操作，并取得一定的研究成果。LI等[8]提出一种分布式协调策略，基于船舶轨迹预测评估碰撞风险，通过优化策略找到最有效的避碰策略，避让中需进行多次协调通信，但未考虑《国际海上避碰规则》(International Regulations for Preventing Collisions at Sea,COLREGs)；KIM等[9-10]采用分布随机搜索算法(Distributed Stochastic Search Algorithm,DSSA)减少通信次数，缩短计算时间，研究中未融入COLREGs；ZHANG等[11]和张金奋[12]依据COLREGs建立让路船和直航船的避让行动模型并将其应用于多船避让中，但采取的避让行动主要依据两船避让，未考虑船舶避让对附近其他来船的影响。

由于COLREGs仅适用于两船会遇场景，无法直接应用到多船避碰中。现有的多船避碰研究主要是将COLREGs融入到避让效果评价函数中[13]和基于避让重点船[3,14-15]确定避让行动。将COLREGs融入到评价函数中，可能存在不完全遵守COLREGs的情况；基于重点船舶避让，由于本船周围存在多艘来船，可能会因采取避让行动而形成新的碰撞危险或更紧迫的碰撞危险局面。

针对多船会遇情景，船舶需同时避让多艘来船，避让各船的行动由于不一致，会产生避让冲突。为保证船舶安全航行，减少避让冲突对避让决策的影响，首先根据最近会遇距离(Distance to Closest Point of Approach，dCPA)和最近会遇时间(Time to Closest Point of Approach，tCPA)将来船分为安全航行船舶和存在碰撞危险船舶；其次，在判断避让方向时，根据安全航行船舶和存在碰撞危险船舶位置及相对运动参数，避免避让行动对安全船舶产生影响，形成新的碰撞危险；在确定避让幅度时，选择与所有来船在尽可能远的距离处通过，避免形成更紧迫的碰撞危险；同时，在避让决策过程中充分考虑多船避让下的协调性和合理性，从而构建基于避让冲突消解策略的多船避碰决策模型；最后，通过蒙特卡洛思想随机生成大量船舶初始会遇场景，并基于分布式框架对避碰决策模型的有效性进行验证。

1 船舶避让冲突

1.1 船舶避让冲突定义

船舶会遇具有一定的随机性和不确定性，特别是多船会遇场景，船舶周围存在多艘来船，船舶航向、航速、方位和距离等参数稍有不同，根据COLREGs制订的避让方案存在较大差异。在多船会遇场景下，“让路船”针对存在碰撞危险的来船采取避让行动之后，对附近其他航行船舶造成更紧迫的碰撞危险或形成新的碰撞危险，即由于会遇船舶位置和航行参数的随机性，“让路船”针对不同的会遇船舶采取的避让行动不一致，从而产生船舶避让冲突。

假设在一定距离范围内有n(n>2)艘船舶会遇，对于会遇船舶i(i∈N)，为避让与其存在碰撞危险的船舶j(j∈N，且j≠i)，采取避让行动δij·δcij，但在采取避让行动之后与另一艘船舶k(k∈N，且k≠i；k≠j)造成新的碰撞危险或更紧迫的碰撞危险。δij为船舶i避让船舶j的避让方向，左转为-，右转为+；δcij为船舶i避让船舶j的避让幅度。

1.2 船舶避让冲突场景介绍

近距离多船避让场景见图1，其中:初始时刻船舶1与船舶2和船舶4存在碰撞危险，与船舶3可在安全距离内通过。船舶4首先向右转向避让船舶1，船舶1为避让船舶2向右转向，并与船舶3在近距离内产生新的碰撞危险。在近距离内船舶1与船舶3采取最有效的避让行动进行避让；由于两船在近距离内同时避让，造成局面更为复杂多变。虽采取避让行动，但局面有进一步恶化的趋势，从而导致船舶间距离减小。船舶初始会遇参数和避碰方案见表1。

图1 近距离多船避让场景

表1 船舶初始会遇参数和避碰方案

2 基于避让冲突消解策略的协调避碰决策

由于多船避让冲突带来的影响主要为：与附近安全航行的船舶形成新的碰撞危险；与存在碰撞危险船舶的危险程度进一步加深。为减少多船避让中存在的避让冲突对避让的影响，分别考虑安全航行船舶和碰撞危险船舶。对于安全航行船舶，在判断避让方向时，避免转向与其形成新的碰撞危险；对于存在碰撞危险船舶，在选择避让幅度时，避免危险进一步增强。基于此，形成多船会遇避让冲突消解策略，构建多船避碰决策模型。

2.1 碰撞危险判断和会遇阶段划分

2.1.1碰撞危险判断

由于安全航行船舶和存在碰撞危险船舶需在方案制订的不同阶段进行考虑，首先应对船舶是否存在碰撞危险进行判断。

在t时刻，对于船舶i(i∈N)，在6 n mile范围内存在任意船舶j(j∈N，且j≠i)，同时满足式(1)和式(2)，则认为船舶i与船舶j存在碰撞危险。

dCPAij(t)

(1)

tCPAij(t)>0

(2)

式(1)和式(2)中：dCPAij(t)和tCPAij(t)分别为t时刻船舶i与船舶j的最近会遇距离和最近会遇时间；SDA的大小应与船舶航行水域的环境条件、交通繁忙程度和航行船舶尺度等因素有关。

目前，关于SDA的研究主要在数学模型确定和船舶领域。李丽娜等[16]依据船长、专家和驾驶员对COLREGs的理解以及操船经验，结合平面解析几何知识和运动学，基于雷达和船舶自动识别系统(Automatic Identification System,AIS)数据构建安全会遇距离数学模型。FU等[17]将船舶领域定义为绝大多数船舶避免进入另一船周围的领域，国内外学者对船舶领域的研究不断深入，研究中开阔水域多为正圆形或离心率较小的椭圆形。

本文研究的水域主要考虑为开阔水域，相对于繁忙水域，船舶航行密度相对较小。综合SDA数学模型和开阔水域船舶领域中的正圆形确定研究中应用的SDA。研究中两船会遇SDA设为2.0 n mile；三船会遇SDA设为1.5 n mile；四船会遇SDA设为1.2 n mile。

根据式(1)和式(2)，在t时刻，可将船舶i(i∈N)6 n mile范围内的任意船舶j(j∈N，且j≠i)分为安全航行船舶(safe_ship)和存在碰撞危险船舶(risk_ship)2类。

(1) safe_ship：对于任意船舶m(m∈N),有dim(t)<6 n mile,dCPAim(t)≥SDA或tCPAim(t)≤0。

(2) risk_ship：对于任意船舶k(k∈N),有dik(t)<6 n mile,dCPAik(t)0。

2.1.2会遇阶段划分

船舶在不同会遇阶段避让行动有所不同，对船舶会遇阶段进行划分很有必要。因此，根据船舶间距离对会遇阶段进行划分。

船舶会遇阶段可分为自由行动阶段、碰撞危险阶段、紧迫局面阶段和紧迫危险阶段等4个阶段，但会遇阶段的划分取决于多方面因素。[13]自由行动阶段船舶距离较远，尚不考虑COLREGs的应用；碰撞危险阶段一般在3～6 n mile；对于紧迫局面阶段和紧迫危险阶段没有明确的定量化描述，根据航海界普遍认可的定义[18]以及船舶应保持不小于SDA安全通过，综合考虑本文针对开阔水域研究多船避让问题，船舶尺度、航行速度和操作性等，分别将3.5 n mile、2.5 n mile和SDA作为定量划分界限。

在t时刻，对于任意船舶i和j(i、j∈N)，根据距离dij(t)对会遇阶段Staij(t)进行划分。

(1) 3.5 n mile

(2) 2.5 n mile

(3)SDA

2.2 基于避让冲突消解策略的避碰方案

船舶避让方案由避让时机、避让方向、避让幅度和恢复原航向时机组成。由于避让行动要求“极早地”以及本研究为实时避碰决策，避让时机的选取不作考虑；同时,恢复原航向是在保证安全的前提下,减少船舶航程损失和燃油消耗。因此，为消解船舶避让冲突，应针对避让方向和避让幅度进行设计。

2.2.1避让方向确定

在多船局面下，周围可能存在安全航行船舶和多艘碰撞危险船舶。目前，大多数研究中仅考虑碰撞危险船，采取“避让重点船”算法进行避让[15]，可能造成新的碰撞危险。

根据COLREGs第8条，避让采取的行动要求不得妨碍另一艘船舶通行或安全通行的船舶。为避免因采取避让行动而使船舶相对运动线向靠近安全船舶方向变化，需对船舶避让方向确定算法进行设计。

以i船为例，-1为左转，0为保向保速，1为右转，ms为远离安全航行船舶s避让方向(如存在多艘，选取距离最近安全航行船舶)，求取方法见文献[19]。δi(t)为t时刻i船避让方向，δir(t)为t时刻i船仅考虑r船避让方向。

(1)i船附近无碰撞危险船舶，此时没有碰撞危险，无需避让，δi(t)=0;

(2)i船附近均为碰撞危险船舶，此时船舶i根据距离最近的危险船r进行避让，δi(t)=δir(t);

(3)i船附近存在安全航行船舶和碰撞危险船舶，当存在多艘碰撞危险船舶时，根据距离确定最近碰撞危险船舶r和最近安全航行船舶s。

由COLREGs可知:除了对遇局面明确要求向右转向，其他条款并未明确要求船舶避让方向。基于不应妨碍另一艘船通行或安全通行的船舶，根据船舶r和船舶s与本船i船的不同会遇阶段，本船i在t时刻避让方向δi(t)确定算法如下：

Function determine avoidance direction()

Input:dir(t),Stair(t),δir(t),Sitir(t),RCir(t),RVCir(t),TCir(t) %输入t时刻r船相对i船参数

Input:dis(t),Stais(t),ms%输入t时刻s船相对i船参数

Input: SDA %输入SDA

δi(t) ← NULL %t时刻i船避让方向

1. ifSitir(t) is head-on situation then

2. ifdir(t)>dis(t) then

3. ifδir(t) ≠msthenδi(t) ← 0;

4. elseδi(t) ←δir(t);

5. end

6. elseδi(t) ←δir(t);

7. end %对遇局面下δir(t) = 1

8.elseifStair(t)=1&&Stais(t)=1 then

9. ifδir(t) =msthenδi(t) ←ms;

10. elseifdir(t)>dis(t) thenδi(t) ← 0;

11. elseδi(t) ←ms;

12. end

13.elseifStair(t)>1&&Stais(t)=1 thenδi(t) ←δir(t);

14.elseifStair(t)=1&&Stais(t)>1 then

15. ifδir(t) =msthenδi(t) ←ms;

16. elseifdir(t)>4.5 n mile thenδi(t) ←ms;

17. elseδi(t) ← 0;

18. end

19.elseifStair(t)>1&&Stais(t)>1 then

20. ifdir(t)>dis(t) thenδi(t) ←ms

21. elseifSitir(t) is overtaken

22. thenδi(t) ←δir(t);

23. elseif 0

24. elseδi(t) ← 1;

25. end

26.elseifdir(t)

27. if 0

28. if sin(RVCir(t)-TCir(t)+180°)≥0 thenδi(t) ← 1;

29. elseδi(t) ← -1;

30. end

31. elseif sin(RVCir(t)-TCir(t)+180°)<0 thenδi(t) ← 1;

32. elseδi(t) ← -1;

33. end

34.end

35.returnδi(t);

该算法中head on situation和overtaken分别为对遇局面和被追越局面；RCir(t)、TCir(t)和RVCir(t)分别为t时刻船舶r相对船舶i的相对方位、真方位和运动方向。

2.2.2避让幅度的确定

确定t时刻避让方向δi(t)之后，进而需确定避让幅度δci(t)。设置候选避让幅度集为

ΔC={0°，10°，20°，30°，40°，50°，60°}

(3)

由于决策模型以步长Δt=5 s进行滚动更新，但因决策步长5 s不能完成整个避让幅度转向，这里根据候选避让幅度大小设置5 s内的航向变化集

δc={0°，1°，2°，3°，3°，3°，3°}

(4)

当本船周围存在多艘碰撞危险船舶，且无法通过一次转向完成对所有船舶的安全避让时，无论本船针对哪艘船舶制订避让方案，在执行过程中都有可能与另一船舶的碰撞危险增大。为避免因采取避让行动而对部分船舶造成更为紧迫的危险局面，通过优化船舶避让幅度对避让冲突进行消解。避让幅度选择策略如下(以船舶i为例)：

(1) 尽可能让清所有来船，即对于任意船舶j(j∈N)有

δci(t)={c|c∈ΔC，dCPAij,c(t)≥SDA}

(5)

式(5)中：dCPAij,c(t)为i船避让角度C后与j船的dCPA值。

(2) 若无法让清所有来船，尽可能让清6 n mile以内的来船，即对于任意船舶j(j∈N，dij(t)<6 n mile)，有

δci(t)={c|c∈ΔC，dCPAij,c(t)≥SDA}

(6)

(3) 若仍无法让清6 n mile内的来船，则选择避让ΔC后尽量能保证通过最大距离，避免更紧迫的碰撞危险，即

δci(t)={c|c∈ΔC，max(min(dCPAij,c))}

(7)

根据避让行动应大幅度的要求，让路船避让幅度应不小于30°，即

∑δci(t)≥30°

(8)

2.2.3恢复原航向条件

在采取避让行动之后的一段时间，在保证船舶能在SDA通过的基础上，为减小航迹偏移量、航程、避让时间和燃油消耗，船舶应恢复原航向。恢复原航向时刻条件(以船舶i为例)为

(1) 船舶i恢复航向之后与任意船舶j(j∈N)不存在碰撞危险，即

dCPAij，b(t)≥SDA或{tCPAij,b(t)≤0且dij(t)>SDA}

(9)

式(9)中：dCPAij，b(t)和tCPAij，b(t)分别为i船恢复原航向之后与j船的dCPA和tCPA值。

(2) 对于任意船舶j(j∈N，j≠i)，距离船舶i均大于8 n mile。

3 避碰决策试验验证

为验证避让决策模型的普适性，依据蒙特卡洛思想随机生成3艘船舶和4艘船舶初始会遇场景各3组，每组10 000次，验证避让冲突消解策略的有效性。试验中船舶采取分布式决策避让，即每艘船舶均根据所处场景，依据避碰决策模型独立制订避让行动，对模型的普适性进行验证。

设置4艘船舶会遇场景，对避让中船舶避让幅度、避让时间和避让轨迹进行展示，并在4艘船会遇时设置船舶未根据决策进行避让和船舶根据避让重点船舶进行避让，对模型的鲁棒性进行验证。

3.1 会遇场景生成与参数设置

随机生成特定数量(3～4艘)船舶会遇场景，包含船舶位置(x，y)、航向c和速度v。各参数取值范围和分布见表2。

表2 初始参数取值范围和分布

随机生成的会遇场景中存在部分场景并不存在碰撞危险的情况，为更好地验证避让冲突消解策略的有效性，对生成的会遇场景进行筛选。筛选原则如下：

1) 为避免船舶会遇刚开始进入紧迫局面，甚至紧迫危险局面，两两船舶间的初始距离应不小于6 n mile。

2) 所有船舶应相互靠近，即任意2艘船舶tCPA>0。

3) 船舶间存在碰撞危险，即至少存在2艘船舶dCPA<0.8SDA，同时任意2艘船舶的dCPA不大于设置SDA的2倍。

3.2 试验结果与分析

3.2.1随机试验结果统计

分别对3艘船舶和4艘船舶会遇进行3组试验，每组随机生成符合筛选原则的会遇场景有10 000次，结果统计见表3。

表3 随机试验结果统计

由表3可知：在三船会遇局面下,最近距离大于SDA平均占比99.83%，大于0.95SDA平均占比99.95%，任意两船最近点距离为1.30 n mile；在四船会遇局面下,99.51%能在SDA及以上距离通过，99.68%能在0.95SDA及以上距离通过，任意两船最近点距离为0.92 n mile。随着船舶数量的增加，船舶会遇局面越来越复杂，最近点距离大于SDA的占比略有减小，但仍为99.51%，证明避碰决策模型具有较好的普适性。

3.2.2船舶避让试验展示

对船舶避让试验结果进行展示，其中避让方案中避让时机和复航时机为试验时间，单位为s，避让幅度单位为(°)。

3.2.2.1 存在避让冲突场景的四船会遇

初始船舶位置、航向和航速与避碰方案如表1所示，在采取船舶避让冲突消解策略之后，船舶运动轨迹和两船距离随时间变化曲线分别见图2和图3。

图2 船舶避让过程

图3 任意两船距离随时间变化曲线

由图2和图3可知：在采取船舶避让冲突消解策略之后，通过每艘船舶调用避让算法，船舶间能在安全距离内通过；与图1对比，说明船舶冲突消解策略和避碰决策能较好地解决多船避让冲突问题。

3.2.2.2 对遇、交叉和追越局面共存的四船会遇

针对交叉局面、对遇局面和追越局面共存情况设置多船会遇场景，初始船舶参数和避碰方案见表4，船舶运动轨迹和任意两船距离随时间的变化曲线分别见图4和图5。

表4 初始船舶参数与避碰方案

图4 船舶避让过程

图5 任意两船距离随时间变化曲线

3.2.2.3 协调行动下的四船会遇

随机生成四船会遇场景，初始船舶参数和避碰方案见表5，船舶运动轨迹和任意两船距离随时间变化曲线分别见图6和图7。

3.2.2.4 不协调行动下四船会遇

针对第3.2.2.1节存在避让冲突场景的四船会遇，将船舶1设置为根据避让重点船舶算法进行避让，船舶初始参数与避碰方案见表6，船舶运动轨迹和任意两船距离随时间的变化曲线分别见图8和图9。由图2和图8可知：船舶1避让方向相反，但均能保证在安全距离内通过，证明避让决策算法能在他船采取不协调行动时，具备一定的应变能力。

表5 初始船舶参数与避碰方案

图6 船舶避让过程

图7 任意两船距离随时间变化曲线

表6 初始船舶参数与避碰方案

图8 船舶避让过程

图9 任意两船距离随时间变化曲线

3.2.2.5 船舶避让效果分析

由图2、图4、图6和图8可知:正常情况下船舶均能在偏航一定距离之后恢复原航向，运动轨迹较为平滑。由图3、图5、图7和图9可知：船舶间距离不小于安全会遇距离，距离变化均匀，符合良好船艺要求。

由存在避让冲突场景的四船会遇场景试验可知，船舶避碰决策模型能在存在避让冲突的情况下保证船舶安全；由对遇、交叉和追越局面共存的四船会遇场景试验结果可知，决策模型能处理多局面共存情况下的船舶会遇场景；同时,由协调行动和不协调行动下的四船会遇场景可知，模型能在周围船舶采取协调和不协调行动下安全避让。

4 结束语

多船会遇局面具有一定的随机性和不确定性，因此在避让不同船舶时需采取不同的避让行动。由于避让行动不一致，会产生避让冲突。本文在避免影响安全航行船舶的基础上，避免船舶避让产生新的碰撞危险或更紧迫的碰撞危险，构建避让冲突消减策略下的避碰决策模型。分别针对3艘船舶和4艘船舶进行随机避碰测试，验证决策模型的普适性。由多船会遇避让过程和任意两船距离的变化情况可知：船舶运动轨迹平滑，船舶间距离变化均匀，能适应周围船舶动态变化和存在部分不协调行动的会遇情景，具有较好的避让效果。研究中存在一定的假设和局限性，如尚未针对不同船舶尺度和不同船舶的操纵性进行分析，没有考虑来船数据更新时的延时和错误，且研究水域仅为开阔水域等。为实现船舶智能航行，还需进行更深层次的研究，如在海上实际航行时，受风、浪、流的作用，船舶航向和航速均在一定范围内波动，并非定值，如何在参数波动下制订安全避让方案仍需进一步研究。目前，由于仅针对部分船舶采取避让重点船算法下的不协调行动进行试验，在下一步研究中，需对模型进行更充分的验证。