人工鱼群算法的避碰路径规划决策支持

马文耀， 吴兆麟， 杨家轩， 李伟峰

(大连海事大学 航海学院，辽宁 大连 116026)

人工鱼群算法的避碰路径规划决策支持

马文耀， 吴兆麟， 杨家轩， 李伟峰

(大连海事大学 航海学院，辽宁 大连 116026)

为了能够在海上交通出现复杂局面时及时提供预警，并给出碰撞决策，从而有效减轻值班人员的工作负担、保证船舶航行安全，结合国际海上避碰规则和船舶安全领域相关知识，以本船避让过程中前进的距离为目标函数，采用遗传算法和人工鱼群算法规划船舶避碰路径，提供最优的避让转向时机、安全避让角度、复航时间和复航角度。通过计算机仿真实验计算对遇、追越和交叉3种会遇态势下的避碰路径参数，并在ECDIS上进行动态显示。结果表明，所得避碰路径参数符合实际情况，规划的路径既安全又经济。运用该算法可有效优化避碰航路，并能给出最优的避碰决策参数。

水路运输；船舶避碰；人工鱼群算法；船舶安全领域；优化

据调查，目前80%以上的碰撞事故都是由人为因素引起的。随着航运技术不断进步，驾驶台上的航行设备能够提供的航行信息越来越多，如果船员没有得到充分训练，大量的航行信息交织在一起，可能会导致船员做出不正确的判断和决策，这将导致巨大损失。有效减少人为因素导致的碰撞事故的方法是依靠科技技术提高船舶自动化航行水平，以减少船员的主观判断，减轻驾驶员的负担，并实现自动避碰。因此，研究船舶自动避碰决策系统对于保障船舶安全而言具有实际意义。

虽然自动雷达标绘仪能解决船舶避碰中信息处理的部分问题，但其不是一个完全的自动避碰系统。使用该系统时，驾驶员必须依据自身经验和专业技能进行主观判断，容易发生严重的错误。电子海图显示与信息系统(Electronic Chart Display and Information System, ECDIS)通过与其他设备(如雷达、罗经、计程仪等)连接获取航行信息并与之进行数据和信息交流，现已成为一种船舶导航和辅助决策系统，并逐渐成为船舶驾驶台的信息核心。船舶避碰策略是一个复杂的决策过程，包括有关航行数据的收集、数据的预处理、船舶会遇态势的划分、碰撞危险度的计算、避碰方法的选择、避碰行动的优化和复航选择。[1]船舶避碰决策是一个复杂的系统工程问题[2]，很难用精确的数学模型来描述，即使有非常精确的数学模型，也不可能用于需要实时采取避碰决策的环境。近年来，学者们开始将人工智能的方法(如人工神经网络、模糊逻辑、基因算法、蚁群算法等算法[1-5])引入到船舶避碰领域，开启了运用软计算代替纯粹数学模型的研究领域。

船舶避碰路径的决策是一个多指标、非线性规划问题，既要保证安全又要求经济消耗最小。因此，采用不同于数学模型的人工鱼群混合优化算法，模仿鱼群的觅食、聚群及追尾行为，搜寻最优解。结合国际海上避碰规则和船舶安全领域相关知识，利用该算法推荐合理的船舶避碰路径。通过研究将该算法实现，并将其与电子海图平台相结合，实现船舶自动避碰决策支持系统。

1 船舶领域和会遇态势划分

船舶领域为一艘船舶周围的有效区域，该船驾驶员将其他船舶和静止目标保持在该区域外，并认为此领域是任何一艘船舶保证航行安全所需的水域。船舶领域是海上交通工程中的一个重要概念，广泛应用于船舶避碰和危险评估。藤井等、GOODWIN和吴兆麟等[6-8]都对船舶领域进行了详细研究。此处研究的避碰支持决策系统产生的避碰路径需保证目标船在本船的船舶领域外驶过。根据避碰规则，会遇态势分为3种(见图1)。

图1 船舶会遇态势划分

1. 对遇：目标船从图1中F区接近。本船与目标船在相反或接近相反的航向上相遇，有碰撞危险时，双方应各自向右转向，从他船的左舷驶过。

2. 交叉：目标船从图中A区、B区和E区接近。本船与目标船交叉相遇，有碰撞危险时，有他船在本船右舷者，本船应给他船让路。

3. 追越：目标船从图中C区和D区接近。当一船正在从他船正横后gt;22.5°的方向后接近，认为正在追越他船。追越船给被追越船让路。

2 避碰路径规划的决策模型

会遇开始时，本船与目标船保持原航向和航速。当目标船进入观测距离内时，相对运动方向、最近会遇距离(DCPA)和到达最近会遇距离的时间(TCPA)将开始被计算。根据国际海上避碰规则建立的知识库判断两船会遇态势，判定本船是否为让路船。如果本船为让路船，且与目标船存在碰撞危险，决策支持系统将执行避碰路径规划，推荐一条安全且经济的路径。实际上，路径可能不是最可行的航路，但至少能保证理论上安全和经济，有助于预警和辅助决策。因此，驾驶员能将航路作为避碰方案的参考。根据不同的任务阶段，避让路径被分为3个阶段。

2.1预警阶段

当目标船进入观测和跟踪阶段时，根据国际海上避碰规则判定本船与目标船的会遇态势。根据目标船的DCPA是否小于本船的安全领域距离判断是否存在碰撞危险。如果存在碰撞危险且本船为让路船，避碰路径规划算法开始执行。此阶段，该算法将给出最迟的转向避碰点、保持原航向和航速航行的可持续时间。驾驶员可将其作为制定避碰决策的参考。

2.2避碰航行阶段

本船转向避让后进入避碰航行阶段，此时转向避让角度不能太小，如果太小，目标船不能有效觉察本船的操纵意图；如果太大，将导致本船偏离原航路太远。但是，该角度必须保证目标船能在本船的安全领域外通过。当本船转向避让后，应在新的航向上航行一段时间后再开始复航航行阶段。

2.3复航航行阶段

复航时机和复航转向角应能保证在复航阶段不会有新的危险情形出现。同时，采用最优的复航时间和角度，尽可能地减少船舶在偏航上的经济损失。

3 人工鱼群算法的避碰路径规划

3.1人工鱼群算法的原理

在一片水域中，鱼能自行或尾随其他鱼找到营养物质丰富的地方，因此鱼生存数目最多的地方一般就是本水域中营养物质最丰富的地方。人工鱼群算法就是根据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群和追尾以及鱼群之间的相互协助等行为，从而达到全局寻优的目的。

一般情况下，鱼为了更大范围地寻找食物点或身边的伙伴，会在水中自由游动；当发现食物时，会向食物逐渐增多(即适应值增大)的方向快速游去。其在游动过程中，为保证生存和躲避危害会自然地聚集成群，向群体的中心游动，此时不仅要尽量避免与邻近伙伴过于拥挤，还要保持与邻近伙伴的平均方向一致。当鱼群中的一条或几条鱼发现食物时,其邻近的伙伴会尾随其快速到达食物点。因此，觅食是一种个体极值寻优过程，属于自学过程，而聚群与追尾是鱼和外界环境相互交互的过程。

人工鱼群算法通过人工鱼个体的觅食、聚群以及追尾3种行为进行迭代计算，最终获取最优解。[10-11]可见，其也是一种仿生智能全局优化方法，每个人工鱼能根据自身和周围环境信息自适应调整搜寻方向，最终使人工鱼群体达到食物中心(即全局极值)。因此，与其他传统优化方法相比，该算法在解决复杂优化问题时具有独特的优越性能。

3.2人工鱼个体的编码方案

避碰路径规划决策模型主要用于求解TS和ΔCO，Ta，ΔCb4个参数，具体含义为：

1)TS为本船从当前位置航行到避让转向点所需时间。本船必须在TS时刻内转向，即船舶最迟要在避让转向点处进行转向，否则存在碰撞风险。

2)CO为避让航向改变量，表示本船的船首向改变ΔCO后，能够保持最小安全距离通过目标船。实际避让角度应≥ΔCO，否则存在碰撞风险。

3)Ta为本船从采取避让转向措施到复航开始时所经历的时间，本船转向后至少沿新航向航行Ta时间后才可以再启动复航行动。

4)ΔCb为复航时航向改变量，为返回计划航线，本船转向角应≤ΔCb，以防新的危险情况出现。

基于人工鱼群算法的避碰航路优化决策的4个参数变量可以使用人工鱼个体进行编码，其中θi对应第i个人工鱼个体，θi=[TS，ΔCO，Ta，ΔCb]。

3.3决策目标函数

从采取转向避让措施开始，到复航至初始航线，本船航行的距离可衡量避碰路径规划的优劣，因此可将其作为决策目标函数(也称自适应函数)。采用人工鱼群优化算法获取最短的避碰路径，并使其满足目标函数和相应约束条件。为此，本船应满足：

1)避碰航行距离应是最小的。

2)碰撞危险最小且目标船保持在本船避碰安全领域以外。

3)在保证目标船在安全领域外通过的情况下，避让角度应是最小的。

4)在最少时间的迂回航行后，本船返回到初始航线上。

5)当不会出现新的会遇态势或其他紧迫局面时，转向角度应是最小的。

J=min{ds+dr}

(1)

式(1)中：ds为采取避让行动后本船的航行距离；dr为复航阶段本船的航行距离。

ds=TaVO

(2)

(3)

模型的约束条件为

(4)

图3 本船转向后避碰决策模型

最近会遇距离dCPA和最近会遇时间TCPA是满足目标函数限制条件的关键因素，其计算方法参照文献[12]中提到计算方法。图3避让转向后新的dCPA1和TCPA1可用下面方法计算

(5)

(6)

(7)

(8)

(9)

dG表示安全通过距离圈的半径，即新的dCPA应至少大于安全通过距离圈的半径。该值的大小取决于海上交通环境和船型。

3.4算法步骤

3.4.1初始化人工鱼群体

在变量可行域内随机生成N条人工鱼，形成初始鱼群。人工鱼的可视域设定为Visual，鱼个体的最大游动步长设为step，拥挤度因子为δ，鱼个体每次移动时的最大试探次数为trynumber，初始公告板中人工鱼群最优状态连续不变化或变化极小时的迭代次数Beststep设为0，初始迭代次数Num设为0。

3.4.2公告板赋初值

计算初始鱼群各人工鱼的目标函数值并比较大小，取最优的人工鱼状态及其值传递给公告板。

3.4.3行为选择

为选择最优的仿生行为，对人工鱼个体分别执行追尾行为和聚群行为的模拟计算，并比较目标函数，缺省为觅食行为。

3.4.4更新公告板

每条人工鱼将自身的目标函数值与公告板的值进行比较，如优于公告板的值则取代之，否则公告板的值不变。

3.4.5引入遗传算法的条件判断

若Beststep已达到预先设定的连续不变化次数的阈值Maxbest，则执行“3.4.6”遗传算法的交叉、变异操作，否则转到“3.4.7”。

3.4.6遗传算法的交叉、变异操作

除公告板中最优人工鱼个体除外，对其他所有人工鱼执行以下操作：

(1) 根据交叉概率Pc随机从人工鱼群中选择出若干个体，然后将其分组，并对两两人工鱼个体执行交叉操作，计算形成的新个体的目标函数值后与公告板中的最优值相比，若比公告板中的值更优，则将其取代，并以新个体取代旧个体；

(2) 根据变异概率Pm随机从鱼群中选择若干人工鱼个体，并对其进行变异操作。计算新形成的鱼群中各人工鱼的目标函数值，并与公告板中的最优值相比，若优于公告板中的值，则以自身取代之；

(3) 置Beststep=0。

3.4.7终止条件判断

重复步骤“3.4.3～3.4.6”，直到公告板上的最优解达到满意的误差界内为止。

3.4.8算法终止

输出最优解，即公告板上的人工鱼状态及其目标函数值。

4 仿真实验结果

该算法的决策支持系统设置和结果见图4。船舶动态信息来自AIS，本船速度设为14 kn，初始航向为000°，仅在需执行避碰决策时才改变航向；目标船速度设定为15 kn。根据避碰规则，船舶避碰分为对遇、追越和交叉3种会遇态势。通过下面3种典型案例对算法进行模拟：

图4 避碰路径规划的决策支持系统

1. 本船与右前方目标船交叉会遇。

2. 本船与右后方目标船交叉会遇。

3. 船舶对遇。

表1为上述3个案例的模拟结果和路径规划数据。其中，dCPA和tCPA为初始状态下，本船与目标船的最近会遇距离和最近会遇时间。dCPAgt;0，目标船通过本船船首；dCPAlt;0，目标船通过本船船尾。T1为转向时机，表示从观测时刻开始计算，当到达T1时转向；C1为向右避让转向角，其限制在[30°，60°]范围内，如果避让角度lt;C1，则存在碰撞危险；T2表示避让转向后至少按新航向航行T2min，才能保证目标船安全通过；C2为复航时转向角度，如果复航转向角太大，将会引起新的目标船靠近危险。

仿真实例说明，运用基于改进的人工鱼群算法解决船舶避碰路径规划问题时，能给出最优的避碰路径，该路径既安全又经济。与ECDIS连接后，能在电子海图平台上动态显示避碰参数，为ECDIS提供避免碰撞的决策支持，可有效减轻值班人员的工作负担、提高海上交通安全。

表1 人工鱼群算法提供优化避碰路径参数

5 结 语

将船舶安全领域和国际海上避碰规则相结合，采用人工鱼群优化模型，对避碰决策模型中关键参数进行优化，并开发避碰决策支持系统。该系统能快速为驾驶员提供一条安全、经济的避碰路径。一旦与驾驶台航海仪器及ECDIS相结合，将给海上船舶避让和水域VTS(Vessel Traffic Services)监控提供一定的安全保障和支持。

[1] 白一鸣，韩新洁，孟宪尧.危险模式免疫控制算法优化船舶避碰策略[J].中国航海，2012,35(2):29-32.

[2] LEE S.M., KWON K Y, JOH J. A Fuzzy Logic for Autonomous Navigation of Marine Vehicles Satisfying COLREG Guidelines[J]. International Journal of Control Automation And Systems, 2004(2)：171-181.

[3] GEMEINDER M, GERKE M. GA-Based Path Planning for Mobile Robot System Employing an Active Search Algorithm [J]. Applied Soft Computing, 2003(3):149-158.

[4] TSOU Mingcheng，KAO Shenglong，SU Chienmin. Decision Support from Genetic Algorithms for Ship Collision Avoidance Route Planning and Alerts[J]. Journal of Navigation, 2010, 63(1): 1-16.

[5] TSOU Mingcheng, HSUEH Chaokuang. The Study of Ship Collision Avoidance Route Planning by Ant Colony Algorithm[J]. Journal of Marine Science and Technology, 2010,18(5):746-756.

[6] FUJII Y, TANNAKA K. Traffic Capacity[J]. Journal of Navigation, 1971, 28(3): 328-344.

[7] GOODWIN E M. A Statistical Study of Ship Domains[J]. Journal of Navigation, 1975, 28(3): 328-344.

[8] 吴兆麟,朱军.海上交通工程[M].大连:大连海事出版社,2004.

[9] 江铭炎,袁东风.人工鱼群算法及其应用[M].北京:科学出版社,2011.

[10] 张梅凤. 人工鱼群智能优化算法的改进及应用研究 [D].大连:大连理工大学，2008.

[11] 姜山，季业飞. 改进的人工鱼群混合算法在交通分配中的应用[J].计算机仿真，2011,28(6):326-329.

[12] 刘德新，吴兆麟，贾传荧. 目标船运动参数及dCPA、tCPA决策模型[J].大连海事大学学报，2004,30(1)：22-25.

[13] 毕修颖,贾传荧,吴兆麟，等.船舶避碰行动领域模型的研究[J].大连海事大学学报,2003,29(1):9-12.

DecisionSupportfromArtificialFishSwarmAlgorithmforShipCollisionAvoidanceRoutePlanning

MAWenyao，WUZhaolin，YANGJiaxuan,LIWeifeng

(Navigation College, Dalian Maritime University, Dalian 116026, China)

When an complicated traffic situation happens on the sea, the early warning and collision avoidance decision support are needed to reduce the pressure on the Officer On the Watch (OOW) and improve the safety of marine traffic. This research integrates the genetic algorithm and the Artificial fish swarm algorithm used in artificial intelligence to find a theoretical safety-critical recommendation for the shortest distance of collision avoidance from an economic viewpoint with the consideration of the International Regulations for Preventing Collisions at Sea (COLREGS) and the safety domain of a ship. Such an optimal safe avoidance turning angle, navigation restoration time and navigational restoration angle was obtained. The results from the simulations of head-on situation, overtaking situation and crossing situation based on ECDIS platform show that the algorithm can be used to optimize collision avoidance route effectively and gives an optimal collision avoidance route parameter. It is proved to suite to make decisions for collision avoidance.

waterway transportation; collision avoidance; artificial fish swarm algorithm; safety domain of ship; optimization

2014-04-18

国家自然科学基金(51109020)；中央高校基本科研业务费专项资金(3132013015)

马文耀(1980—)，男，湖北潜江人，副教授，博士生，从事海上交通工程、航海安全保障研究。E-mail：wenyaoma1980@163.com

1000-4653(2014)03-0063-05

TP18；U675.9

A