港口内运车辆作业轨迹异常检测
2022-01-28胡俊雅李勇华
胡俊雅 李勇华 唐 晨
(武汉理工大学计算机科学与技术学院 湖北 武汉 430063)(武汉理工大学交通物联网技术湖北省重点实验室 湖北 武汉 430070)
0 引 言
港口是水陆运输枢纽中心,内河港口的装卸船作业通常采用内运车辆对货物进行中转,一般涉及将码头的货物运输到堆场(卸货作业)、将堆场的货物运输到码头(装货作业)、将堆场的货物运输到其他堆场(转堆作业)等作业行为。在中转过程中,由于港内道路复杂、中转作业类型多样、堆场环境恶劣,以及人为因素不可控等原因,该过程极易发生一些异常作业行为(偷运货物、装卸货紊乱、未按流程作业等),货物的安全亟需得到监管,而货物的安全与内运车的运行意图密切相关。内运车在作业过程中会产生海量的轨迹数据,通过对轨迹数据[1]进行分析,可以发现内运车的移动特征。而轨迹的异常行为表现出与正常行为不一致的现象,通过对轨迹进行异常检测,能够发现移动对象隐藏在正常行为模式中的真实行为模式,暴露出内运车运行的异常意图,可令监管人员做出相应措施。
目前,轨迹异常检测[2]已成为学术界和工业界研究领域的热点。然而国内外针对港口内运车作业轨迹异常检测的研究较少,在社会安全[3-4]、智能交通[5-6]、海事航行[7-8]等领域的研究较多。
Le等[3]针对办公场所的非法入侵问题,提出一个线性距离函数来比较两个轨迹活动序列,并使用动态时间规整(Dynamic Time Warping,DTW)的度量方法来计算序列间的相似性,最后利用单分类支持向量机(One Class Support Vector Machine,One-Class SVM)对轨迹活动序列进行分类,检测异常轨迹活动序列。该方法能够成功检测到误报率极低情景中的异常序列,然而并未在真实数据集中进行校验且构建检测模型的过程耗时较长。Wang等[5]针对交通流量异常问题提出了一种基于特征的流量异常检测方法,该方法对原始轨迹进行地图匹配,通过索引结构聚合路段所有轨迹,并通过路段及轨迹特征等方面进行分析,检索异常候选段,最后根据候选段的密度变化、驶出比率等推断交通异常情况。但是该方法考虑的特征并不全面,没有误报率的评估实验。Toloue等[7]针对船舶航海安全问题,结合船舶的速度、位置、航向等参数,提出了一种基于隐马尔可夫模型(Hidden Markov Model,HMM)的海上船舶异常行为检测方法,该方法相比于SVM方法有效地降低了误报率,提高了检测精度等。然而随着船舶海上航线的增加,也需要为每个路径构建不同的行为模型。文献[2]对现有的异常检测技术进行了分类,并阐述了每个类型的异常检测方法的不足之处。
本文考虑到港口内运车作业的特殊性(部分路网较为密集、作业类型和作业货物多样、作业环节存在驻留和移动状态、作业司机可更换等),提出轨迹真实状态提取方法并设计自适应有限状态机(Adaptive Finite State Machine,AFSM)对内运车作业轨迹进行异常检测。首先根据路网匹配知识[9]获取轨迹点所属路段,形成临时状态序列集;然后利用规则和DBSCAN[10]聚类算法将临时状态序列转化为真实状态序列;最后结合港口领域专家经验、港口实时情况、作业真实数据等制定规则,利用每趟序列得到的反馈结果来构建AFSM,将轨迹真实状态序列作为AFSM的输入,检测内运车作业轨迹是否异常。
1 轨迹真实状态序列提取方法
港口调度人员发布作业指令后,内运车根据该指令执行对应的作业流程,同时产生海量的轨迹数据。这些轨迹数据根据行驶路径、作业流程的每个作业环节等形成不同的轨迹状态,如直接过磅的移动状态、堆场/码头作业的耗时驻留状态等。虽然通过传统的聚类方法能够得到轨迹驻留状态,然而由于GPS的精度问题和港区路网较为密集等原因,传统的聚类方法得到的轨迹真实状态并不足够准确,此外类似过磅的这种移动状态更是无法聚类。为此,本文提出轨迹真实状态序列提取方法,其流程如图1所示,首先搜索轨迹点的候选路段,结合轨迹数据以及港口路网数据,基于启发式半径搜索轨迹点的候选路段集(候选点集)。然后结合轨迹点的上下文信息,计算轨迹点到候选点的观测概率和候选点间的形成的状态转移概率,并根据1.2节提出的算法为每个轨迹点匹配路段信息。最后基于规则和DBSCAN聚类算法判断轨迹的真实状态,并形成轨迹真实状态序列,该规则结合了作业流程和作业数据,DBSCAN聚类算法是用于判断状态内的轨迹数据集的驻留情况,其中轨迹真实状态是指轨迹形成的驻留区域以及满足作业环节的区域。
图1 轨迹真实状态序列提取方法的工作流程
1.1 基于上下文的轨迹所属路段判断算法
内河港口的道路结构复杂,某港口道路结构如图2所示,其中:粗框矩形的边框为堆场道路;左下角矩形边框区域为码头道路;五角星所标区域为地磅所在位置。由于GPS定位不可避免地存在精度问题,在堆场区域,堆场和堆场之间的距离较近,且部分堆场相通,轨迹点很容易因为偏差而被识别到另一个堆场中,对于地磅区域,其与其他道路的距离更为接近,基于传统的几何路网匹配方法很难精确地将轨迹点匹配到正确的路段上,这给内运车作业轨迹的异常检测带来了挑战。
图2 某港口道路区域
为此本文基于港口领域,充分结合轨迹点上下文信息和路网拓扑结构,提出基于上下文的轨迹所属路段判断算法(TBRSJ)。如图3所示,确定轨迹点A的候选点是由其自身及其前序和后序轨迹点共同决定的。
图3 基于上下文的轨迹候选点判断
(1)基于启发式半径的轨迹候选路段搜索。本文对港口路网模型建立路网索引,并根据该索引确定观测轨迹点Pi所属网格,以该网格为中心,基于网格索引查询出3×3网格内的路段集L={l1,l2,…,ln},计算观测点Pi到路段li的投影点,投影点是指观测点投射到路段上的候选点,其与观测点的距离最近。计算投影点时,需考虑观测点与路段的三种位置关系:路段中的投影点、路段左侧的投影点、路段右侧的投影点。如图4所示,观测点Pi对应的候选点即为Pc、Pa、Pb,观测点到候选点的投影距离即为dic、dia、dib,投影距离是指两点间的大圆距离。
图4 轨迹点到路段的投影
如果以观测点为中心,设置一个半径大小为R的阈值,简单地将投影距离小于R的路段添加到候选集中,R大小的选取直接影响候选集的大小。考虑到GPS的误差以及路段自身存在的宽度等因素,本文将R≤w/2+p的路段加入到该点所属的候选集中,其中:w为路段宽度;p为轨迹点的定位精度。候选点即为其投影点。路宽因素确定了观测点到路段投影的阈值选取,经验证可以减少候选集的大小,降低后续算法的时间开销且保证了算法的有效性。
(2)观测概率。观测概率是指GPS观测点和候选点的匹配程度,匹配程度越高说明该候选点与观测点越接近。文献[11]认为观测到的轨迹点符合正态分布,可以使用高斯函数来表达距离因素的观测概率,文献[12]使用均值μ=0、标准差σ=20的高斯分布来模拟观测概率,如式(1)所示。
(1)
(2)
(3)状态转移概率。轨迹点所属路段不仅与前序轨迹相关,后序轨迹也是其重要权重因素。在图5中,对于P2,仅考虑前序P1的影响,易丢失下文信息,而导致P2匹配到路段L2的概率更大。
图5 点到路段位置
因此在本文中,状态转移概率是指结合了相邻轨迹状态到该轨迹状态转移这一过程的概率,其公式为:
(3)
算法1TBRSJ算法
输入:预处理后的轨迹集Traj。
输出:包含所属路段的轨迹集TrajRes。
1TrajRes=[]
2 计算每个轨迹点的候选路段集合L、轨迹点到候选点的观测概率Po、候选点到候选点的转移概率Pt等
4 foriin range(1,len(Traj)-1)
9 forliinLi
11 forli+1inLi+1
16TrajRes.push(pi,l)
18TrajRes.push(pend,l)
19 returnTrajRes
对于此算法,设T为某趟作业的轨迹数据个数,V为路网节点数,E为路网中的路段数,假设每个轨迹点的候选路段最多为K。基于HMM的后联合概率计算时要计算观测概率、转移概率和联合概率,候选路段到候选路段的条数共有(T-1)×K2个,观测概率、联合概率需要计算T×K次,又因A*算法最坏的时间复杂度为O(V2),因此转移概率的时间复杂度为O(TK2V2),该过程的全局复杂度为O(2KT+TK2V2),状态转移概率需要计算T(K2+1),所以此算法的时间复杂度为O(2KT+TK2V2+T(K2+1))。在实际中,K可以取较小的值,因此,该算法的时间复杂度接近于O(TV2)。
1.2 基于规则和DBSCAN的真实状态判断
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。DBSCAN聚类算法过程是从数据集中,任选一个核心对象作为种子,再由此对象出发找出其密度可达的样本,生成聚类簇,直到所有核心对象均被访问,即确定了最终相应的聚类簇。由于该算法有着优良的管理空间特征能力,能够发现任意形状的聚类簇,且对数据集的噪声数据不敏感,因此本文通过DBSCAN聚类判断内运车的真实驻留状态。然而车辆过磅这类作业环节属于非耗时操作,简单地通过密度聚类容易丢失某些内运车轨迹的真实状态且全局的聚类算法耗时较长,因此本文从实际作业流程和真实的作业数据制定相应规则,提出基于规则和DBSCAN的轨迹真实状态提取算法。
对1.1节中提取的TrajRes进行状态合并,得到轨迹临时状态序列tState=(S1,S2,…,Sn),其中状态S是一个五元组S=(sName,trajList,enTime,exTime,trajNum),包含状态名称、轨迹数据集、驶入时间、驶出时间和轨迹总数量。图6显示了几辆内运车的轨迹临时状态,其中驶入和驶出时间是用时间戳进行表示的。
图6 临时轨迹状态序列结构
轨迹的临时状态序列反映了内运车在港内作业每条路段上的行驶情况,其作为基于规则和DBSCAN的轨迹真实状态提取算法的输入。其算法流程如算法2所示,其中:Rule1表示如果状态si处于作业区域且实际的作业时间点处于该状态的时间段内则为True;Rule2表示如果状态si的轨迹数量大于15或时间段长度超过了120 s则为True。
算法2基于规则和DBSCAN的轨迹真实状态提取算法
输入:轨迹临时状态序列集tState。
输出:轨迹真实状态集合RealState=(S1,S2,…,Sm)。
1Rule1:∃si∈tState∧W(si)→True
W(si):si处于作业区域且时间段包含实际作业时间
2Rule2:∃si∈tState∧(si.trajNum>15∨si.time>120 s)→True
3RealState=[]
4 foriin range(len(tState))
5 ifsiinRule1
6RealState.push(si)
7 else ifsiinRule2
8clusterRes=_DBSCAN(si.trajList)
#返回聚类结果
9 ifclusterRes.num>0
#有聚类簇
10RealState.push(si)
11 returnRealState
算法2首先制定了作业规则,然后遍历状态序列,将符合的状态加入到真实状态中,对该状态内的轨迹数据集进行DBSCAN聚类处理,如果存在聚类类簇则将该状态加入到真实状态中,否则进行下一次状态判断,最后得到轨迹的真实状态序列。
2 自适应FSM的轨迹异常行为检测
轨迹异常是指该轨迹没有遵守某种预期模式的事件,或者是根据某种相似性准则表现出与其他轨迹相异的行为。在不同的应用中对轨迹异常存在不同的定义。基于港口监管人员对内运车作业长期观察得到的作业异常类型,本文将内运车作业的异常行为定义为:(1)未按标准作业流程作业;(2)同一指令下的多趟作业的作业区域不同;(3)在非作业区域驻留超时或作业区域作业超时;(4)违法关闭作业终端逃避监管。
港口内运车根据作业指令进行生产作业,在正常的作业流程中,按照每个指令环节执行相应操作,从一个工作状态迁移到另一个工作状态,直至作业流程完结,整个作业环节的状态是确定且有限的,该过程符合有限状态机(Finite State Machine,FSM)这一数学模型[14]。轨迹的真实状态代表了内运车作业的行驶意图,可将第一节中提取到的轨迹真实状态序列放入内运车作业的FSM中检测其是否异常。然而在内运车作业过程中,不同的作业指令存在不同的作业类型,每个环节的作业时长跟作业类型、作业货物密切相关,同一指令下的多趟作业的作业区域应当相差无几,且某些停车、加油等状态属于合法状态,这些因素都影响着内运车轨迹异常检测的精度。因此为了更好适应各种异常类型,本文在FSM的基础上对其进行调整,通过制定一些规则和获取一些反馈数据,设计了自适应有限状态机AFSM来检测内运车作业轨迹是否异常。
2.1 AFSM自适应的有限状态
AFSM在FSM的基础上自适应地制定了作业规则以及结合了该条指令下的反馈数据,将这些因素作为状态迁移的前置条件。通过AFSM能够更加精确地判断内运车作业轨迹异常。AFSM由一个七元组M=(S,Σ,R,δ,s0,F,φ)表示。其中:S=(s0,s1,…,sn)是一个非空的有限状态集合,在每个确定的时刻,AFSM只能处于一个确定的状态si;Σ=(σ1,σ2,…,σn)是一个非空的输入消息集合,在每个确定的时刻,AFSM只能接收一个确定的输入σk;R=(r1,r2,…,rn)是状态的规则集合,每个状态存在最多一个确定的规则集rk;δ:S×Σ×R×φ→S是状态转移函数,在某一个状态下,给定输入且满足前置条件,AFSM将由状态转移函数决定一个新的状态;s0∈S是初始状态,AFSM由此开始接收输入,在内运车作业过程中,初始状态为第一次过磅;F∈S是最终状态集合,AFSM在到达终态后结束,并得到轨迹异常检测的结果;φ是反馈数据,由同一指令下每趟作业经过AFSM处理后到达等待状态得到的反馈数据。
图7是AFSM结构,其中:状态1为第一次过磅状态;状态2为码头或堆场状态;状态3为第二次过磅状态;状态4为目标堆场/码头状态;状态5为等待状态;状态6为异常状态;状态7为成功状态;R为规则;φ为反馈数据。首先根据内运车作业指令获取作业数据,然后通过作业数据信息确定有限状态S、终止状态F,制定状态规则R,确定初始状态s0;接着将轨迹真实状态序列作为输入条件Σ,利用规则R以及轨迹状态内的聚类类簇信息自适应设计状态转移函数δ;最后结合每趟作业状态计算反馈数据φ,并作为状态5(等待状态)转移函数的前置条件,输出终态结果,从而检测出内运车作业轨迹是否异常。
图7 AFSM结构
2.2 规则和反馈的设计及应用
1)作业规则。作业规则的设计结合了港口领域专家经验、内运车作业数据、港口交通实时状态等因素,其目的在于判断内运车作业轨迹真实状态序列中的某些状态是否合法,以提高AFSM对轨迹异常检测的精度。
由于篇幅原因,本文仅列出了AFSM的部分通用规则,以及作业指令编号为LXH99201812191328550、作业货物为智利粉矿的部分卸货的非通用规则,如表1所示。其中:si表示真实状态;S表示真实状态序列集合;Gas(si)表示si处于加油站区域;Light(si)表示si处于红绿灯区域;Canteen(si)表示si处于食堂区域。Ct(si.t)表示si.t处于就餐时间内;Yard(si)表示si处于堆场作业区域;Pier(si)表示si处于码头作业区域;PGRules(si)表示si处于通用规则区域;Traj(si.t)表示获取si时间段内港口所有轨迹信息;Congestion(Traj(si.t))表示si处于拥堵状态;Legal(si)表示si为合法状态。
2)反馈数据。反馈数据的设计是利用同一指令下的每趟作业轨迹真实状态来确定的,其目的在于校验内运车在堆场或码头执行作业时,内运车作业的具体位置是否合法,以提高AFSM对轨迹异常检测的精度。
港口调度人员通过发布作业指令调度内运车执行作业,在同一条作业指令下至少存在一趟以上的作业,且对于每趟作业而言,它的作业流程完全相同,其对应的具体作业区域相近或一致。由于内运车在不同趟数作业的作业时长并不一致,采集的轨迹长度基本不相等,因此本文采用动态时间规整(Dynamic Time Warping,DTW)[15]的方法来对同一指令下不同趟数在堆场或码头的轨迹的真实状态进行相似度分析。
基于DTW的反馈数据算法如算法3所示。其步骤如下,首先计算多趟作业在作业区域之间的相似度,并得到相似度矩阵,然后将每趟和其他趟数的相似度值进行累加,并比较不同趟数得到的相似度值,最后将相似度值最小(相似度最大)的那趟作业区域定为合法作业区域,并将该趟作业与其他趟作业的相似度数据作为反馈数据返回。
算法3基于DTW的反馈数据φ的设计
输入:已抵达AFSM的等待状态下的同一指令下的多趟轨迹真实状态RS。
输出:返回合法趟数φ。
1dtw=[]
#相似度矩阵
2 foriin range(len(RS))
3 forjin range(len(RS))
4 ifi==j
#当前趟数作业的状态转移到5
5dtw.append(0)
6 else
7dtw.append(DTW(RSi,RSj))
#计算作业区域的相似度
8min=sum(dtw0)
#计算当前与其他趟数的相似度之和
9 foriin range(len(dtw))
10 ifmin>sum(dtwi)
11min=sum(dtwi)
12idx=i
13φ=dtwidx
14 returnφ
#选择φ最小的那趟作业区域为标准作业区域
3)作业规则和反馈数据的应用。根据本章开头定义的内运车作业轨迹异常类型,下面将举例分析这些异常类型下作业规则和反馈数据在ASFM中的应用。
(1)未按标准作业流程作业。内运车首先完成第一次过磅,然后驶入码头作业,之后未完成第二次过磅,再次驶入码头作业并完成第二次过磅,最后到达堆场结束作业。该过程并未按照标准的作业流程作业,因此此趟作业存在异常。对应的AFSM会在状态2到状态3之间经过作业规则的判断后,变迁为异常状态。
(2)同一指令下的多趟作业的作业区域不同。在同一指令下,内运车两趟作业在堆场的具体作业区域不同,因此其中存在异常趟数的作业。对应的AFSM会在等待状态经过反馈数据的判断后变迁为异常状态。
(3)在非作业区域驻留超时或作业区域作业超时。内运车完成第一次过磅后驶入码头,并在码头短暂停留,然而在第二次过磅时,远超出作业时长,因此该趟作业存在异常。对应的AFSM会在状态2到状态3间,经过规则的判断,变迁为异常状态。
(4)违法关闭作业终端逃避监管。内运车在经过第一次过磅后便关闭了作业终端系统,导致后续作业轨迹无法上报,因此该趟作业存在异常。对应的AFSM从状态1到状态2间,经过规则判断后变迁为异常状态。
3 实 验
3.1 实验数据
本文采用的轨迹数据集是从重庆某港口中获取的一个月(2018年12月19日00:00:00至2019年01月18日23:59:59)的内运车作业轨迹数据。利用车载移动终端,以8 s/次的采样频率进行数据采集,共采集了1 239条作业指令、7 547趟作业、3 415 835个轨迹点。
3.2 实验结果
(a)候选路段数量对比
在基于上下文的轨迹所属路段判断算法中,本文结合HMMM算法,不仅考虑了前序轨迹点的概率,同时也结合了后序轨迹点的概率。由于堆场之间的距离相近,且GPS易漂移,极易发生在A堆场作业的部分轨迹点漂移到B堆场。图9展示了两者在堆场时的提取状态,(a)是本文算法在该区域的匹配结果,右侧是正确匹配的部分,(b)是HMMM算法在该区域的匹配结果,右侧是错误的匹配部分。
图9 本文算法与HMMM算法局部匹配结果对比
在轨迹真实状态提取中,为了对其进行评估,本文将基于DBSCAN的轨迹真实状态提取、基于规则的轨迹真实状态提取、基于规则和DBSCAN的轨迹真实状态提取进行实验对比。图10是本文随机选取20趟作业轨迹数据下的时间结果,可知基于规则和DBSCAN的轨迹真实状态提取算法能够最大程度有效地提取出内运车作业轨迹的真实状态。
(a)三种方式的真实状态提取数量
为了评估AFSM对内运车作业轨迹异常检测的有效性,本文从两个方面进行实验,一方面基于DTW的反馈数据的计算方式,另一方面是AFSM轨迹异常检测结果。
本文选取了作业指令为LXH99201812190253-431的5趟作业轨迹数据,经DTW相似度计算后,该5趟作业在D1堆场的相似度的堆积柱形图如图11所示,两个具体作业区域的相似度值越高说明其相似度越低。
图11 不同趟数在D1堆场的轨迹相似度堆积结果
可以看出第一趟作业在堆场的具体作业区域与其他四趟在堆场的具体作业区域相似度较低,第四趟作业的堆积值最低,即第四趟作业与其他趟数的相似度较高,因此本文选取第四趟作业的堆场作业区域为该指令下的标准具体作业区域。对于判断两个具体作业区域是否为同一作业区域,需要度量两者的相似度大小,本文经过大量的计算,该相似度度量值取值为1 066,即当两个具体作业区域的相似度小于1 066时,即可认为两个具体作业区域为同一作业区域。
由于人工计算结果集工作量非常大,因此本节实验在数据集中随机选取了50条(45条卸船指令和5条转堆指令)、75条(67条卸船指令和8条转堆指令)、100条(90条卸船指令和10条转堆指令)、125条(112条卸船指令和13条转堆指令)作业指令下的轨迹数据,在经过轨迹真实状态的提取后,将其作为AFSM的输入,将其结果与人工获取结果集进行对比,最终得到的结果如图12所示。
(a)不同规模数据的AFSM检测结果
不同异常类型在不同作业指令数量下的异常趟数,如图13所示,其中:异常1是指未按标准作业流程作业的轨迹异常类型;异常2是指同一指令下的多趟作业的作业区域不同的轨迹异常类型;异常3是指在非作业区域驻留超时或作业区域作业超时的轨迹异常类型;异常4是指违法关闭作业终端逃避监管的异常类型;误报异常是指AFSM错误识别为异常的情况。可以看出,内河港口内运车作业过程中,异常4类型出现的情况较多,这是由于部分内运车司机在作业过程中并没有长时间地打开作业终端,仅在需要的时候开启,用完后就关闭。
图13 不同异常类型的数据量
4 结 语
为了对内河港口内运车辆在进行货物中转的过程中进行有效的监管,本文提出一种轨迹真实状态序列提取方法,并设计了AFSM对内运车作业轨迹数据进行异常检测来判断内运车作业是否存在异常意图。在轨迹真实状态序列提取方法中,采用启发式半径阈值降低了路段候选集大小,提高了本文方法的时间效率;
综合考虑了轨迹的上下文信息,利用轨迹点的观测概率和候选点间形成的状态转移概率得到了轨迹的所属路段,并基于规则和DBSCAN聚类提取轨迹真实状态。在AFSM中,结合了港口领域专家经验、港口交通实时状态,以及每趟作业的实际数据制定了相应规则,并对每趟作业的作业区域进行DTW的相似性分析获取反馈数据,自适应地调整了FSM。最后,基于重庆某港口提供的真实数据集对轨迹真实状态提取方法和AFSM轨迹异常检测模型进行实验。实验表明,本文方法能够精确地提取内运车作业的轨迹真实状态,不仅提取出非作业环节和作业环节的内运车驻留状态,还能够有效提取作业环节中的内运车移动状态,最终在以上方法的基础上,AFSM对内运车作业轨迹的异常检测精度达95%~96%。实验证明了本文方法适用于该港口的内运车作业异常检测。