船舶动态避碰决策研究

船舶动态避碰决策研究

1船舶智能避拉中的机器学习国际海上防止冲突规则（以下简称“规则”）是几千年来海洋船舶实践的经验总结。旨在规范海上船舶之间的碰撞行为，尽可能保障海上船舶的安全航行。统计结果显示，96%以上的海上碰撞事故是由驾驶员无法严格遵守规则的合理行为造成的。为了解决人为因素引起的碰撞事故，近年来，日本著名学者稻石正明教授、英国利物浦工业大学copen教授、波兰格丁尼亚海事学院smilzchalaski教授、国内著名学者吴兆林教授、郑仲琦教授、上海海事大学教授、刘宇红博士和台湾学者h旺从专家理论、模糊专家系统方法、遗产理论方法、多因素联合技术和理论方法以及神经网络和模糊数学方法对水上作业的自动发出了许多良好的影响。然而，仍然处于模型方法研究和个人样品模拟阶段，研究方法、实验结果及其相关应用系统尚未出现。源于航海雷达模拟器的培训教学实践,本文作者于20世纪90年代初开始致力于船舶智能避碰的研究,经过十几年的研究已初步建立和形成了船舶拟人智能避碰决策(personifyingintelligentdecisionmakingforvesselcollisionavoidance,PIDVCA)理论体系,并创建了近似海试的仿真测试平台用于验证智能避碰模型和算法.大量的宽水域船舶自动避碰仿真试验表明,本研究方法形成的避碰决策已能同时避让2～4个目标船,显示了PIDVCA的自动化能力,使船舶的安全航行成为一种可能.一个智能决策系统应具有的特征:具有高级智能表现行为,能认识对象和事件,能表达环境模型中的知识,能对未来做出规划和推理.其中高级智能表现为具有感知(觉察)和推理能力,能在复杂甚至险恶的环境中进行明智选择,做出成功的决策,以求生存和进步.要使智能避碰决策系统具有高级智能,必须具备机器在线自动学习的能力.对于机器学习,较为严格的提法是:机器学习是一门研究机器(一般指计算机)获取新知识和新技能,并识别现有知识的学问PIDVCA模型的机器学习实质是研究如何使机器(计算机)通过识别和利用现有知识以及现场捕获的各类动静态信息来计算得出各类动态避碰知识,以最终形成科学有效的PIDVCA实施方案.如何将本船动态信息以及目标船的动态信息与现有的经验知识等静态定性的避碰知识有机融合,形成可供机器实现PIDVCA的各类动态避碰知识,从而形成一套按照特定的机器学习机制加以实现的策略.2pidvca的系统框架经过十多年的研究,以PIDVCA理论为研发船用智能避碰导航仪(VICAN)的理论基础的系统核心框架已初步构建下面在简要介绍传统的避碰方法基础上,说明PIDVCA方法概要,最后引出PIDVCA的机器学习机制.2.1时域组合的危险判定驾驶员利用雷达提供的目标回波信息、本船电罗经提供的航向信息以及计程仪提供的航速信息,借助相对运动人工标绘(如图1所示,其中SHM表示本船的船艏标志线)获得目标船的运动要素信息(包括本船相对目标的方位Bo,目标的相对方位B、相对距离R,相对运动方向Cr和速度Vr,目标船真运动航向Ct和速度Vt)、避碰参数(最近会遇距离DCPA和到达最近会遇距离的时间TCPA)进行会遇态势的判断;根据《规则》基本准则确定的危险判定阈值(综合考虑本船的操纵性能、大气以及航行海域的情况)判断本船与目标船是否存在碰撞危险,即将图中所示的目标船与本船的最近会遇距离DCPA与目标船到达最近会遇距离的时间与预先确定的危险判定阈值进行比较,如果有碰撞危险存在,则根据《规则》或海员的通常做法,确定避碰决策(左让、右让变速或变向加变速);根据作图求取相应的避让幅度、避让时机以及预测复航时机,最后根据求得的结果实施避让操船动作.2.2动态避拉pidvca的应然模型与传统避碰方法相比而言,研究“PIDVCA”的目标是要解决“船舶拟人智能避碰决策”的自动化问题,具体而言就是应用《规则》、船舶操纵与避碰学、船舶驾驶员的通常做法以及人工智能技术等知识,借助现场传感器获得的环境及目标信息,结合专家经验知识的定性分析,利用这些信息系统进行自动推理、定量计算和评价,并最终实现船舶避碰决策实施方案的自动生成和优化.PIDVCA的实现:将数理分析、机器学习、专家系统原理、模糊数学和航海知识有机结合形成集成化的人工智能方法,并以智能程序形式实现PIDVCA模型(如图2所示).该过程主要采用正向启发式规则推理、类比推理、范例推理与非单调推理相结合的集成推理(控制)策略,将构成智能避碰模型的机器学习模块、动态避碰知识模块、推理机以及由定性推理的决策准则与定量计算的决策实施方案动态优化目标函数等构成的决策分析评价体系有机地融为一体,并最终获得问题的解.动态避碰知识库是PIDVCA模型的核心内容,它用数据库的方法表示事实性知识(诸如来自AIS(automaticaidentificationsystem)的船舶基本参数、利用传感器和电子海图数据库获取的海域环境相关信息);用if＿then产生式模型表示有关避碰决策问题中与避碰决策的行动相联系的因果关系知识;最终用程序和过程代码表示由数据库、模型库、动态信息库和智能避碰决策库形成的元知识所体现的动态避碰决策知识模块.由于航行中船舶所形成的会遇态势是变化无穷的,因此对每一个会遇局面形成避碰决策的知识千变万化.纵然是同一个会遇局面,随着时间的推移,避碰决策方案也会发生相应的变化.这里特别要注意的一点是:动态避碰知识中提到的“动态”概念意旨通过机器学习,针对每一局面获取的避碰知识是实时的,在船舶执行避碰决策方案安全让清后可遗忘,不必永久存储.机器学习是构建动态避碰知识库的关键技术之一,其学习机理是以面向对象技术为基础,以产生式、决策树以及程序与过程代码组成的异构表示作为知识的表达形式,获得模块、概念、操作和启发式等不同形式的知识;以系统研究的各类“避碰模型”及其形成的各类“避碰决策算法”作为集成机器学习的表示形式;而学习的过程及其主要内容包括如何在系统推理机的控制下,利用数据库提供的来自各传感器的原始数据和信息以及利用模型库提供的各类避碰模型而实时获取的动态避碰信息、运用基于经验知识产生的规则集进行目标性质的识别、分类并最终构成动态避碰知识库,如图2所示.2.3基于人工学习的在线机器自动学习机制从2.1节阐述的驾驶员避让过程可以看出:本船和目标船的信息是避碰决策的基本资源,而避碰知识是经由信息加工(即相对运动人工标绘)后得到的抽象化产物,系统在决策过程中根据《规则》给出决定避碰措施的定性准则,同时采用定量的矢量作图计算确定避碰措施实施的具体幅度和时机,经由上述两者所形成的避碰决策是目标(客体)信息和本船(主体)信息以安全避让为目的演绎出来的智慧化身.因此这里所体现的拟人智能避碰思想是把来自传感器、电子海图信息和用户输入的各种动静态数据感知的目标信息资源加工成避碰知识,进而把避碰知识激活成为解决避碰问题的避碰决策,并在避碰决策信息引导下实现解决具体问题的全部能力.从传感器获得本船航向和航速信息以及目标船的位置信息到实现PIDVCA是一个复杂的智能避碰决策过程,依靠单一的学习策略是远远不够的,而且现有的学习策略也未必适应于“船舶拟人智能避碰”这一特定问题的学习和知识获取,因此本研究创建了一种基于人工学习的在线机器自动学习机制,并形成一套独特的集成机器学习策略加以实现.所谓PIDVCA的集成机器学习策略是建立在人工避碰经验发现和基于解释和范例的概括学习策略所构建的静态避碰知识基础之上,以在线启发式规则推理、类比推理、基于规则和范例的混合推理和非单调推理指导下的避碰知识发现(collisionavoidanceknowledgediscovery,CAKD)为核心,辅以启发式推理与强化学习策略.如图3所示,图中的实线矩形框表示研究人员利用原有的船舶避碰领域知识、经过人工学习预先获取的静态避碰知识;虚线矩形框表示系统根据用户输入的相关信息、利用原有的静态避碰知识和传感器现场采集的动态信息,在推理机的控制下,经过在线学习实时获取动态避碰知识和问题的解决方案.3释学习和模范学习策略本系统研究的集成机器学习策略是基于人工学习的在线自动学习方式.人工学习主要包括经验发现、解释学习和范例学习策略;在线学习方式包括在线启发式规则推理、类比推理、范例推理和非单调推理指导下的知识发现与强化学习策略.人工学习方式主要用于产生类比推理和范例推理学习的类比源和范例源以及在线获取新知识的避碰模型,以便通过在线自动学习实时获取(发现)解决问题的新知识以及新技能.3.1基于数据的策略机器发现始于科学发现的计算机建模.机器发现是指从观察的事例或经验中归纳出规律或规则,这是一种富有创造性和挑战性的学习方式.它属于-观察发现学习的一种策略,可划分为经验发现与知识发现两种.前者是指从经验数据中发现规律和定律,后者是指从已观察的事例或数据中发现新的知识本文提出的机器发现实质上是一种自动的动态知识获取方法,它借助人工方法为机器发现构建避碰模型和智能避碰决策算法,搭建知识框架,以便机器利用数据库的事实性知识用户输入的各种静态参数以及由传感器现场获得的目标和本船的动态信息)自动获取新知识,这是实现VICAN超越人的决策能力(即实现拟人智能避碰决策)的关键技术之一.3.1.1基于过程数据的避拉发现知识原始知识是机器学习发现新知识的基础数据,原始知识来源于《规则》、专家对《规则》的解释以及海员的通常做法这些定性的静态经验知识.本文提出的“避碰经验发现”就是解决如何从这些定性的静态经验知识(船舶避碰领域知识)和数据中发现相应的规律,实质是解决如何创建避碰模型和推理机的自动推理机制问题,或解决领域知识的形式化问题,以便“避碰知识发现”利用相应的规律,把这些定性的静态经验知识转换成为机器可识别的、可应用于自动生成最优避碰决策方案的动态信息和知识.本系统将其定义为离线知识获取与识别的学习方法,研究人员综合分析了《规则》及海员的通常做法,根据船舶相对运动几何关系(如图1所示)建立求解速度矢量三角形ABC、碰撞三角形CDO等解析几何关系以及估算公式等组成的各类避碰模型,构成动态避碰知识库的模型库,这些模型就是人工发现的规律,用于机器解算获取各类动态决策信息.避碰模型主要由目标运动要素(包括本船相对目标的方位Bo,目标船的相对方位B、相对距离R,相对运动方向Cr和速度Vr,真运动航向Ct和速度Vt)和碰撞参数DDCPA与TCPA的计算模型、碰撞危险判据(安全会遇距离SDA、及其最小值SDAmin)计算模型、碰撞危险度计算模型(紧迫局面距离DE及其最小值、即紧迫危险距离DEmin、本船初始避碰时机Tso和最晚施舵时机T1)、避碰决策实施方案(避让时机Ts、改向幅度AC或变速幅度AV以及预测复航时机Tr)量化模型以及避碰决策实施方案校验模型(包括预测目标运动要素模型和限制时间Tc计算模型)等构成.很显然,“避碰经验发现”是避碰知识发现的先决条件,为避碰知识发现策略奠定了基础.3.1.2避拉知识发现知识发现是从数据集中识别出有效的、新颖的、潜在有用的以及最终可理解的模式的非平凡过程.知识发现的目的是向使用者屏蔽原始数据的繁琐细节,从原始数据中提炼出有意义的、简洁的知识,直接向使用者报告.为解决无穷多的会遇态势所构成的船舶避碰问题,本文提出的“避碰知识发现”的目的是从本船和目标船的原始数据中提炼出有意义的、简洁的避碰知识,直接提供给驾驶员.所谓的“提炼”就是系统根据避碰经验发现构建的避碰模型、自动推理机制以及基于解释和范例的概括创建的各类避碰决策算法、智能避碰决策库以及多船避碰决策校验与寻优算法获得避碰知识的过程,而所谓的“有意义的、简洁的避碰知识”就是诸如DCPA和TCPA、会遇态势、目标性质、避碰决策实施方案之类便于驾驶员理解和获悉交会态势以及避碰决策指导的避碰知识.根据本文作者构建的避碰知识获取框架(如图3所示)和预先设计的推理机自动推理机制来实现“避碰知识发现”,避碰知识发现过程如下:①推理机根据数据库提供的事实性知识,运用启发式规则推理顺序调用“避碰经验发现”所建立的避碰模型,感知目标动态信息;②推理机根据感知的目标动态信息和基于解释的概括形成的规则库,运用类比推理的启发式规则匹配,认知目标;③推理机根据认知目标的结果和基于范例的概括结合避碰模型和避碰决策算法应用形成的智能避碰决策库,运用在线启发式规则与范例混合推理获得初始避碰决策方案;④推理机根据初始避碰决策方案,决定是否进入决策分析评价和优化,如果需要则运用启发式规则与非单调推理以及强化学习(必要时)策略,最终形成最佳的智能避碰决策方案.例如系统在推理机的启发式规则推理控制下,顺序选择相应的避碰模型,根据传感器观测的本船航向信息Co、航速信息Vo、目标相对距离信息R和相对方位信息B,利用目标运动要素和碰撞参数DCPA与TCPA计算模型以及碰撞危险判据估算模型,解算出感知目标所需的动态信息,并以动态数组的方式存储在图1所示动态避碰知识库中的动态信息库中.以下给出了上述模型的具体应用实例,假设本船OS1的航向航速分别为:Co=0°,Vo=11.0kn.则经过计算之后的相关避碰信息如表1所示,其中Bo为本船相对目标船的方位.3.2基于类比推理的避碰决策算法基于解释的学习,是一种从通用规则转换而来的较为特殊的学习方法.本文引用了基于解释的概括EBG(explanation-basedgeneralization)方法,其过程可分为解释和概括两个阶段,即:①解释:使用领域理论建立一个证明训练例子满足目标概念定义的解释结构(即一棵解释树),要求解释结构每个分枝的叶节点上的表达式都必须满足可操作性准则;②概括:确定一个充分条件集合,使在这些条件下,解释结构有效,且表达这个条件的描述满足可操作性准则.这可通过在解释结构中对目标概念进行回归来完成.回归所得的表达式合取便成为所求的目标概念描述.PIDVCA的离线解释学习与在线类比推理策略解释如下:首先运用EBG方法,根据船舶避碰领域知识建立相关解释结构,形成启发式规则推理的规则库,作为类比推理的类比源;再利用类比推理指导下的启发式规则匹配判断实际观测到的目标实例是否满足目标概念定义.学习认知的内容包括:目标是否危险、危险等级的定义、危险目标的性质、目标与本船交会关系的定义.具体学习过程是根据PIDVCA构建的决策分析评价体系以及《规则》中对目标船的性质及其与本船交会关系的相关定义,以离线的方式,通过基于解释的概括构造各种目标概念的解释结构,形成各类避碰决策算法,并以规则形式预先存储在图2所示动态避碰知识模块的规则库中;推理机根据动态信息库提供的目标信息源,运用启发式规则推理方式,首先根据目标的DCPA与SDA的计算结果,通过类比推理可判定目标船是否与本船存在潜在动态危险关系,当结论肯定时(即wx[i]=1,表示该目标处于潜在碰撞危险状态)再进一步从规则库中选择与之匹配的规则,确定实际观测到的目标的性质及其所属的基本会遇局面.下面以两船构成追越局面时的交互态势为例说明以上模型的具体应用.《规则》第十三条(追越)2款规定:“一船正从他船正横后大于22.5°的某一方向赶上他船时,即该船对其所追越的船所处的位置,在夜间只能看见被追越船的尾灯而不能看见它的任一舷灯时,应认为是在追越中.”因为只有两船存在碰撞危险的情况,才有必要考虑避碰决策,因此,作为机器要判定两船之间的会遇局面是否为追越局面,首先要判断两船之间是否存在潜在的碰撞危险;然后根据会遇态势判定模型确定会遇目标船的具体属性是追越船或被追越船;最后根据目标属性进一步确定其特征.根据《规则》关于“追越局面”的规定,经过分析可构造“追越局面”的解释结构如图4所示.图4中,mbxz为目标船属性标识符;wx为危险标识符,其值为1表示目标船与本船存在潜在的碰撞危险,其值为0表示目标船与本船无碰撞危险;Tzt为目标性质标识符,其值为1表示目标船为直航船(权利船),本船为让路船(义务船),如其值为2则相反.以产生式规则形式表示为:根据表1显示的信息,可知wx=1,显然根据图4提供的解释结构,运用类比推理的启发式规则匹配,则可以判定目标船为追越船(即mbxz[i]=4),进而判定会遇态势属于追越局面.3.3最优的避碰决策《规则》是从船舶驾驶员的大量避碰范例中抽象总结出来的基本避碰准则,主要适合于两船间的避让决策方法;对于多船的初始避碰决策方法,一般参照两船间的避让方法以及海员的通常做法行动.如图4所示,PIDVCA首先基于范例的概括CBG(case-basedgeneralization)方法解决范例推理的范例源问题,其过程类似于EBG方法,具体的实现方法是预先根据领域知识将各种典型会遇局面的避碰方法,以决策树的规则形式存放于图2的智能避碰决策库,作为范例推理的范例源;然后推理机利用启发式规则推理方法,根据PIDVCA的解释学习与类比推理学习策略认知得到的目标特征、会遇局面和目标性质,通过范例推理从智能避碰决策库中选择对应的典型避碰范例决策树(子程序),最后结合避碰模型和避碰决策算法的具体运用,确定智能避碰的初始决策.例如对于单船(只有一个目标船)会遇的情况,本船为让路船时的初始避碰决策是基于《规则》、专家对《规则》的解释以及几何分析解算得到的.除了目标为被追越船,对于其他属性的目标船,一般认为最佳改向避让幅度为30°,而对于被追越船,根据几何分析和仿真试验结果认为初始改向避让幅度为10°;当初始避碰时机Tso计算结果大于或等于零时,则分别以10°或30°作为初始避碰决策,如果Ts。计算结果小于0,说明两船已错过了避碰的最佳时机,则本船按照立即改向方式调用避碰方案计算模型,求解新的改向避让幅度并将其作为该条件下的初始避碰决策.由于初始避碰决策的形成机制符合《规则》的“早让宽让”避碰原则,因此除了能见度不良情况下避让左正横附近的目标船以外,其它态势下的单船初始避碰决策就是最优的避碰决策实施方案.在3.3节的例子中,如图5所示,显然目标船OS2为义务船,与以往仿真试验模式不同的是:该船配有智能避碰软件,简称智能目标船.在该试验中,目标船在其避让时机(10.25min)到来时向右改向10°,并在改向后的11.5min后恢复原航向,使本船与目标船在其SDA以外安全交会,其仿真回放如图5所示.如果OS2没有装载PIDVCA软件,其模拟的情形是让路船不履行避让义务,按照PIDVCA的研究思想,利用PIDVCA理论中建立的目标船避碰时机计算模型,可以获知OS2改向避让10°的避让时机Tso.因此,当OS2改向避让10°的时机到来之后(即Tso=0),如果OS2没有采取避让措施,OS1可通过AIS的短信技术自动以点对点的方式向OS2发出避让请求;如果OS2响应OS1的避让请求,则仿真效果雷同图5;否则,OS1基于自身处于最不利情况下的安全避让原则,将在其最晚施舵时机(27min)到来时采取向左改向49°的避让措施,并在改向避让5.5min后恢复原航向.图6(仅本船OS1装载PIDVCA软件)显示:当左舷来船T1与OS1构成碰撞危险时,在T1没有采取相应的避碰行动的互见和能见度不良两种状态下,OS1的避让时机和幅度不同,满足《规则》要求,符合航海实践情况.在OS1采取避让行动后,如果T1采取不协调的避让行动(如图6(b)所示),OS1能及时采取相应的补救措施避免发生碰撞.图7显示的是比较特殊的三船交会示例,三船之间均构成潜在的碰撞危险,图6中的(a)和(b)对应的OSi的参数相同,图6(a)的两船的距离在11、12e,图6(b)中的两船之间距离设置在4.5e～6e左右.从两船之间的交会关系而言,OS1与OS2为对遇关系,两船均为让路船;OS1与OS5为左交叉关系,OS1为直航船,OS5为让路船;OS2与OS5为右交叉关系,OS5为直航船,OS2为让路船.综上分析,只有OS2纯属让路船的身份,其它船舶均具有双重身份.多船避碰算法针对特殊的会遇局势规定:仅是让路船身份的OS2避让时机按照让路船确定;具有双重身份的OS5和OS1避让时机设置为直航船的避让时机.因此OS2应最先承担让路船向右改向的义务;接着是OS5,因为一旦OS2采取措施,OS5与OS2的危险关系便随之消失,此时OS5相对OS1而言则为让路船,必然要承担让路船的责任,OS5在其最佳初始避让时机到来时采取向右改向30°的避让措施,并在其预测的复航时机到来时安全复航.由于图7(a)的OS1在OS5的改向初期,它们之间的交会特征发生了变化,导致OS1对OS5的最晚施舵时机提前,并使其最晚改向角由原来的90°改为72°,在检测到复航时机时立即安全复航.如果OS5改为没有装载PIDVCA软件的T1,则OS5利用AIS短信技术自动向T1播发避让请求并得到响应,则其避让效果如同图7(b);否则当T1没有理会OS1的避让请求,即不履行避让义务,则避让效果如图7(c),即OS1在其最晚施舵时机改向90°,并在预计的复航时机到来时与T1和OS5安全通过.可见,PIDVCA算法中利用了AIS短信技术实现自动播发避让请求,在得到回应的情况下,一方面提升了PIDVCA的拟人,另一方面可优化避让的效果;在得不到回应的情况下,基于PIDVCA的原则,必须充分考虑了本船处于最不利的避让原则,同样能确保直航船在其避让的最晚时刻安全避让.3.4险目标船身份校验后的避拉方式设置在形成初始避碰决策之后,对于多船会遇局面,能否安全避开所有的目标船,还需进行避碰决策的校验,必要时进行决策方案的动态优化,即执行图3中的决策方案分析评价与方案寻优.这个过程基于避碰经验发现学习策略所形成的避碰决策校验算法、总结的基本范例(图8虚框所示为模拟海员通常做法的通用型算法)以及创建的时空动态寻优算法:系统在启发式规则推理指导下,根据初始避碰决策方案预测目标船与本船新的会遇态势,进入初级校验,即分析可能存在的危险性;如果分析结果没有存在新的潜在危险目标船,即初始避碰决策经初级校验就获得成功,则根据会遇局势和决策方案的具体情况,决定是否必要进行下一步的动态优化;如果初级校验不成功,则调用模拟海员习惯做法的通用型算法,进入二级校验;如果校验成功,即可输出相应的避碰决策实施方案;否则,系统将借助非单调推理,通过调整SDA的值或避让时机,进入时空搜索寻优的第三级校验,如果在最小的安全会遇距离与最晚的避让时机内未能找到合适的避碰决策,则进入紧迫危险避碰决策库搜索紧急避碰决策.图8中的NWX表示预测初始改向后出现的新危险目标船的数量,TCPAm为新危险目标到达本船最近会遇距离时间的最大值.图9(a)和(b)的避碰示例为互见情况下仅仅本船OS1装载PIDVCA软件且与T1构成潜在碰撞危险的多船避碰仿真示例.初始避碰决策方案:OS1立即向右改向30°.但因OS1立即向右改向30°,会导致其分别与图9(a)中的TS3和图9(b)中的TS2构成新的危险,所以该方案被否决.对图9(a)的例子,经过推理判断新危险船TS3到达最近会遇距离的时间TCPAm小于TL,因此本船以TS3的TCPAm为改向时机重新确定避碰决策实施方案为向右改向57°,通过预测目标与OS1新的会遇态势及可能存在的危险性,其结果为NWX=0,则输出避碰决策实施方案;对于图9(b)的例子,经过