基于HTN规划和SVM的应急交通管控决策模型

夏小棠,何 鑫

(1.武汉科技大学 城市建设学院,湖北 武汉 430065;2.武汉科技大学 城市更新湖北省工程研究中心,湖北 武汉 430065)

应急交通管控是指在重大公共卫生事件、社会安全事件、工业事故和自然灾害等突发事件应急处置中,对现场及周边进行道路疏导与交通工具管控等维持现场秩序的应急行动,是保障应急救援有序开展和应急资源顺畅调度的基础条件。应急交通管控过程中,现场指挥部需要根据应急态势和现场环境,识别应急管控目标,确定管控力度和管控措施,分析现场应急资源需求和保障措施,制定应急交通管控行动方案,并根据突发事件情景演化动态调整。例如新冠肺炎(COVID-19)疫情爆发后的武汉市封城决策中就包括复杂的应急交通管控问题,由于交通工具成为病毒传播的潜在途径,武汉全市公交、地铁、轮渡、长途客运暂停运营,除特殊车辆外,中心城区实行机动车禁行管理。疫情期间武汉市关闭全部离汉通道,共设置交通管控卡口51个,其中高速公路卡口47个、国省道卡口4个,并为全市1 300多个社区900多万居民提供生活保障和医疗保障。然而,在新冠疫情防控中也出现了部分地区过度采取封闭道路、中断交通等禁止性交通管控措施,不仅给当地群众正常的生产生活带来负面影响,还影响到应急资源保障“最后一公里”的顺畅配送。为解决应急交通管控中暴露出的管控力度不精准、管控措施不合理和应急资源保障不顺畅的问题,提出在层次任务网络(HTN)规划中集成支持向量机(SVM)模型,力图通过智能化选择交通管控方式生成应急交通管控行动方案,包括管控力度和管控措施。

韩善剑等[1]分析了新冠疫情防控不同阶段的交通管控策略和需求特点,总结出实施分区分级交通管控、完善应急交通管控预案和创新智慧交通技术的应急交通管控策略。刘志谦[2]分析了新冠疫情防控暴露出的应急保障不平衡、联防联控待优化等问题,提出了应急通道保障、交通管控闭环等交通应急保障与出行管控对策。代磊磊等[3]就新冠疫情期间交通管控的形式和重点变化问题,对交通管控分级影响因素进行分析,建立交通管控分级触发机制,构建了分级管控体系。龚鹏飞等[4]在分析4种不同应急交通组织措施基础上,以道路交通事故为例进行模拟仿真实验,发现综合采用应急交通组织措施的交通疏导效果显著。贾兴利等[5]通过分析市内道路封闭、客运交通停运和小区人口流动控制3种交通管控措施实施前后的市域疫情传播趋势,揭示了不同交通管控措施对疫情传播的阻断效果。蒋瑶等[6]提出公交专用道复用,通过绿灯延时、红灯早断和速度调节3种信号优先控制策略为应急物资运输车辆提供路径选择。有学者是在应急预案编制的基础上针对疫情防控、交通事故等特定对象设计出优选方案,还有学者是在分别考虑管控分级、管控措施和资源保障的基础上进行仿真实验或模型优化,得到应急交通管控决策方案,但这些决策模型不能同时解决交通管控力度选择和应急保障最后“一公里”问题,难以适应新冠肺炎疫情等重大突发事件中应急交通管控多样性、复杂性和动态变化的特征。因此,需设计出一种全管控级别的应急交通管控决策模型。

HTN规划作为一种人工智能规划,其推理过程可以模拟应急行动方案制定的决策过程[7]能够大幅缩短应急决策时间,提高应急决策效率[8]。HTN规划可分解一组高级复合任务目标,生成可行的行动计划[9],能够处理具有因果关系或时间关系的复杂任务[10],在突发事件应急处置中应用广泛。王喆等[11]设计了战术推理和操作优化过程将HTN规划应用于复合型应急物流配送问题。SANTOFIMIA等[12]考虑到公共交通安全的特点,对层次任务网络规划进行扩展,引入自动监控平台,将其应用于公共交通安全相关的实际问题。吴凤媛等[13]根据海上应急物流的特点,结合智能网络规划,提出了一种更科学的应急规划方法,大幅度提高了海上应急规划的决策效率。HTN规划可以实现完整的应急交通管控决策过程,但在通过各影响因素的取值决定管控力度选择的过程中,可能存在效率低、方案不够合理等问题。商丽媛等[14]通过支持向量机对地震灾害进行分级实验,为突发事件分级提供了科学依据。因此可以考虑引入额外的分类方法,弥补HTN规划在分类问题上的不足。

为解决上述问题,提出HTN规划和支持向量机相结合的方法,建立应急交通管控决策框架,包括SVM决策模块和HTN规划模块。根据应急交通管控的特点、外部环境、资源需求等,确定管控目标,形成HTN规划的初始任务网络;根据历史数据提取出相应的高关联性特征参数,通过SVM模型得到合适的管控力度,并扩展HTN规划的方法集,进一步生成应急行动方案。

1 基本框架

应急决策是在不确定条件下对意外事态进行精准研判并制定应急行动方案以实现对突发事件进行有效控制的决策情景。突发事件的应急处置过程中,为了防止突发事件的持续扩散,使应急救援行动顺利展开,需要对处置现场及其周边区域进行交通管控,确保救援车辆的顺畅通行。合适的交通管控方式和切实可行的应急行动方案,将会缩短应急决策时间,提高应急救援效率。笔者提出基于HTN和SVM的应急交通管控决策模型,基本框架如图1所示。

图1 应急交通管控决策框架

应急交通管控的决策过程,主要包括应急交通管控目标和方式的确定及应急行动方案的生成。通过信息编码、拓展方法将SVM决策模块和HTN规划模块连结起来,共同组成了应急交通管控决策框架。整个框架包括两个部分:①SVM决策模块。突发事件发生后,根据应急交通管控的特点、外部环境、资源需求等,确定应急处置的管控目标。将实际现场数据输入到SVM模型中,根据输出结果即可得到相应的应急交通管控力度。其中,SVM模型是通过对历史数据提取关联性较高的特征参数经过训练、测试得到的。②HTN规划模块。将SVM决策模块生成的应急交通管控目标和管控力度输入到HTN规划模块,再利用SHOP2规划器进一步生成应急行动方案。其中,应急交通管控目标将被编码为初始任务网络,包括应急资源的需求任务和救援车辆的最优路径选择任务;管控力度将被编码为任务分解方法,可以把对应的任务分解至可以直接执行的管控措施。

2 应急交通管控SVM模型

2.1 管控力度的响应特征

应急交通管控涉及诸多因素,包括风险等级、周边应急通道数量、应急保障优先级、人口密度和道路交通流情况。基于这些因素,通过分析历史数据,将管控力度划分为4个等级,分别为红色、橙色、黄色、蓝色,并设置各等级对应的响应条件及管控措施,如表1所示。

表1 应急交通管控方式

从响应条件中提取出4个特征,分别为道路数量、人口密度、车流量、风险等级,各个特征具体内容如下:①道路数量,指突发事件现场的周边区域内道路总数量,包括主干道、辅路和匝道,道路越多数量,说明现场及周边越重要;②人口密度,指该区域内常住人口数量与区域面积的比值,突发事件后果的扩散与人口密度有一定的关系,同时人口密度也影响着现场周边区域的管控;③车流量,指现场周边区域内所有道路的车流量信息,车流量的大小影响着突发事件后果的扩散,车流量大代表着流动性大,扩散风险就越大,进而影响交通管控方式;④风险等级,突发事件等级分为低、中、高3级,1代表低风险、2代表中风险、3代表高风险,风险等级由政府部门及相关组织确定。将4个特征作为突发事件现场数据的4个维度来选择管控力度,则应急交通管控决策中的管控力度选择可以被看作是基于4维数据的多分类问题。

2.2 管控力度的多分类问题

多分类问题描述:给定含N个样本的训练集X={(x1,y1),(x2,y2),…,(xN,yN)},找到决策函数y=f(x)用于预测新数据的类别。其中,xn1为K维特征向量,xn1∈RK,yn1为类标签,yn1∈{1,2,…,M},n1=1,2,…,N。通常解决多分类问题的思路是“拆解法”,即将多分类问题拆分为多个二分类问题,为每个二分类问题训练一个分类器,预测时对每个分类器的结果进行集成,即可得到多分类结果。

根据以上思路,对于管控力度选择的多分类问题只需要找到合适的拆分策略与二分类方法。经典的拆分策略有3种:①“一对一”,是指在任意两类样本之间设计一个分类器,则包含K类样本的训练集需要设计K(K-1)/2个分类器,当预测一个未知样本的类别时,最终的预测结果通过投票产生,即被预测的最多的类别为最终分类结果;②“一对多”,是指依次将某个类的样本作为正样本,其他类别的样本作为负样本,此时K个样本需训练出K个分类器,预测时选择置信度最大的类别作为分类结果。③“多对多”,是指每次将若干个类作为正类,若干个其他类作为反类,常用的技术是纠错输出码,在预测时将预测标记与各个类别的编码进行比较,返回距离最小的类别作为预测结果。其中,“一对一”策略的训练时间少,在类别较多时,容易出现分类器个数较大进而导致存储开销和测试时间较大,但是本文管控力度的选择是一个4分类问题,总分类器的个数为6个,代价较小;“一对多”策略在类别较少时,存储开销和测试时间少,但是训练集的正、反类比例存在偏置;“多对多”策略的正、反类构造需要特殊设计,不同的拆解方式会导致模型具有不同的效果。经对比分析,“一对一”拆分策略适合解决本文管控力度选择的多分类问题。

2.3 管控力度的SVM模型

支持向量机(support vector machine,SVM)是一种基于统计学习理论和结构风险最小化准则的数据分类、回归分析模型[15],在机器学习、模式识别、计算机视觉、工业工程应用等领域得到广泛应用[16]。统计学习理论避免了模型受训练集大小的影响,结构风险最小化准则避免了模型的过学习问题,同时SVM学习问题可以表示为凸优化问题,能保证找到全局最优解而非局部最优解。SVM作为一种优秀的二分类模型,还可以通过拆分策略扩展到多分类,其中LibSVM中的多分类方法也包括“一对一”拆分策略。SVM二分类模型的基本思想是求解能够正确划分样本空间且几何间隔最大的分离超平面[17],如式(1)所示。

(1)

s.t.yi(wTφ(x)+b)≥1-ζi,ζi≥0

(2)

式中:w∈RK,b∈RK;x={xi}为样本向量,i=1,2,…,n2;y∈{-1,1}n2为类别向量;wTφ(x)+b=0为超平面;函数φ表示将样本向量x隐式映射到更高的维空间中;C为控制当样本被错误分类时惩罚的强度;ζi为超平面不能使样本数据完全分离时样本距离其正确边界的距离。找到合适的w和b使得sign(wTφ(x)+b)给出的预测对于大多数样本是正确的,即找到最好的划分超平面,同时将该问题转化为找到样本空间里的最大间隔。

在约束最优化问题中,通常利用拉格朗日对偶性将原始问题转换成对偶问题,通过求解对偶问题得到原始问题的解。SVM原始问题式(1)的对偶问题可表示为:

L(α)=min(αTQα)/2-eTα

(3)

s.t.yTα=0,0≤αi≤C

(4)

式中:αi为对偶系数,以C为上界;e为全为1的向量;Q为一个n3×n3阶的正定矩阵,Qjj′≡yjyj′K(xj,xj′),K(xj,xj′)=φ(xj)Tφ(xj′)为核函数,j=1,2,…,n3,j′=1,2,…,n3。

拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子,可将有d个变量与k个约束条件的最优化问题转化为具有d+k个变量的无约束优化问题求解。通过拉格朗日乘子法即可得到以下模型:

(5)

3 应急交通管控HTN规划

3.1 HTN规划问题描述

应急交通管控的HTN规划问题描述为4元组:P=(S0,T,D),其中S0为问题的初始状态,T为初始任务网络,D=(O,M)为HTN的规划领域,O为动作集合,M为方法集合。

(1)初始状态S0。初始状态S0不仅需要描述应急交通管控的初始情景,还需要描述初始的应急资源分布情况。初始情景由一系列由谓词逻辑表述的状态组成。应急资源则包括可重用性资源和消耗性资源。可重用性资源是应急处置后可以回收的资源,如交通工具,表示为R_1={R_id,R_type,R_loc,R_res},其中R_id表示可重用性资源序号;R_type表示资源类型;R_loc表示资源位置变化;R_res表示该资源与其他资源的关联信息;消耗性资源是应急处置中不断消耗的资源,如食品、药品,表示为R_2={R_id,R_type,R_loc},其中R_id表示资源序号;R_type表示资源类型;R_loc表示资源位置变化。

(2)初始任务网络T。初始任务网络T=(t1,t2,…,tL),包含若干子任务,如应急救援任务,依次将子任务分解,直至任务网络中不包含非原子任务,即可得到规划方案。tl=(tl_id,tl_type,tl_start,tl_end,tl_description),tl_id表示任务名称;tl_type表示任务类型;tl_start和tl_end 表示任务的起止时间;tl_description表示任务的描述信息。

(3)规划领域D。规划领域D=(O,M),O={o1,o2,…,oJ}为动作集合,如o1(transport,r_1,start,end,loc_from,loc_to),transport表示o1是运输动作;r_1表示执行该动作所需要的交通工具;start表示该动作的开始时间;end表示该动作的结束时间;loc_from表示该动作执行前交通工具所在地点;loc_to表示该动作执行后交通工具所在地点。M={m1,m2,…,mk}为方法集合,使用方法可将复杂的任务分解至原子任务,如m1(rescue,(t_control,r_need,r_handle))表示将应急救援任务rescue分解为t_control、r_need、r_handle 3个子任务,t_control表示交通管控;r_need表示资源分析;r_handle表示资源处置。

3.2 OTD算法

SHOP2是使用有序任务分解算法(OTD)求解HTN规划的规划器[18]。OTD算法的基本原理是按任务网络中子任务的先后顺序依次进行分解,分解过程基于当前系统的状态,为后续任务分解和规划生成提供了准确的系统状态信息,减少了规划生成中的不确定信息,提高了求解效率[19]。将SHOP2规划器应用于应急交通管控HTN规划,OTD部分算法流程如图2所示,在将初始任务应急救援分解为交通管控、资源分析、资源处置3个子任务后,先分解交通管控子任务得到管控力度和管控措施两个子任务,直至分解为原子任务,再依次分解资源分析、资源处置两个子任务,最终通过回溯得到完整的应急行动方案。

图2 OTD部分算法流程

3.3 HTN规划流程

基于HTN规划分解交通管控子任务得到管控力度的过程中,需要判断各影响因素是否在红、橙、黄、蓝4个管控力度的取值范围内。由于各管控力度的取值范围很难界定,会导致管控力度的选择不准确,影响应急处置效率。因此,在OTD算法的基础上,利用SVM模型的分类结果对HTN规划的任务分解方法进行扩展,得到应急交通管控的HTN规划算法。当突发事件应急处置需要交通管控时,根据历史经验和相关数据利用SVM模型识别出合理的管控力度,规划器进一步根据该问题的初始任务和应急资源需求,调用任务分解方法,生成应急行动方案。

基于应急交通管控的HTN规划算法流程如图3所示,具体步骤为:①利用交通管控目标来确定HTN规划的初始任务网络并利用从SVM模块得到的管控力度扩展方法集,然后执行OTD(S,T,D),对任务列表T进行判断,若为空列表,则生成行动方案,同时跳转到步骤④,否则继续执行步骤②。②从任务列表T选择第一个任务t。如果t是原子任务,在领域D中找到适用于当前状态S的动作o,若存在动作o,则将当前状态S替换为执行o后的状态,将任务列表T替换为删除任务t后的新列表,然后将操作o加入到行动方案中,同时返回OTD(S,T,D);若不存在操作o,则返回失败。如果t不是原子任务,则继续执行步骤③。③从D=(O,M)中找到方法m分解任务t,并将产生的新任务列表设为T,删除任务t后,返回OTD(S,T,D),直至任务列表T中的任务全部被分解为原子任务。④按照算法依次进行规划,返回行动方案,即为所求应急行动规划;若在规划过程中,没有从D=(O,M)找到合适的操作o和方法m,则算法返回失败结果。

图3 HTN规划流程

4 算例分析

4.1 算例简介

为了验证基于HTN和SVM的应急交通管控决策模型的可行性,以新冠肺炎疫情防控为实验背景,假设某地区出现新冠肺炎感染病例,通过该模型实现应急交通管控方式选择和应急物资保障“最后一公里”。某地区A小区周边地理信息如图4所示,包括各道路、C医院和应急物资储备点B1、B2。各路段距离如表2所示。

图4 A小区周边地理信息

4.2 SVM模型训练

在建立完整的应急交通管控决策模型之前,需要根据交通管控历史数据训练出SVM模型,用来解决交通管控多分类问题。根据各省市新冠肺炎疫情工作指挥部发出的工作通告,获取该地区新冠肺炎疫情的风险等级和交通管控措施,通过管控措施确定管控力度。同时,根据各省市政府数据开放平台提供的相关数据,获取与通告时间相对应的该地区的人口密度、道路数量、车流量日统计数据,共选取样本数据40个,按8∶2的比例分为训练集和验证集。由于4个特征的性质不同,具有不同的量纲和数量级,人口密度和车流量之间的水平也相差较大,而SVM模型需要计算距离,如果直接使用原始数据,可能会突出数值较高的特征在分类中的作用,因此需要对原始数据做标准化处理来保证结果的可靠性。使用Z-Score标准化对数据训练集数据标准化,数据预处理之后,需要进行SVM核函数的选择、惩罚系数C和核函数系数的确定。使用Python并借助sklearn框架进行编程,拆分策略选择“一对一”,核函数选择RBF核函数。经过多次实验,设置惩罚系数C为1,核函数系数为0.25,最终SVM模型的准确率为92.5 %,可以使用该模型来确定应急交通管控中的管控力度。验证集数据如表3所示。

表3 验证集数据

4.3 算例结果及分析

若A小区内新冠肺炎确诊病例增加,风险等级从中风险上调至高风险,该小区及周边区域的道路数量、人口密度、车流量、风险等级数分别为10、1、100、3。经相关部门统计,现需要调配指定车辆紧急配送应急资源,包括口罩、防护服、食品药品、医护人员,疫情防控指挥部决定对该小区及周边区域实施交通管控,保障应急资源配送,并制定具体的应急行动方案。

根据所提出的应急交通管控决策模型,将该管控目标输入到HTN规划中,同时将A小区样本数据与训练集数据的均值、标准差做标准化处理,输入到训练完毕的SVM模型中,最终得到管控力度为红色等级,相应的应急行动方案如表4所示。即A小区风险等级发生变化后,为保障应急行动的顺利展开,应当对A小区及周边区域进行红色管控,执行相应的管控措施。具体的管控措施为交通管控期间,应急物资调运车辆需在指定道路上“点对点”通行,各车辆只能从应急物资储备点或医院往返A小区;普通车辆在主干道和支路的速度分别为40 km/h、30 km/h,救护车在主干道和支路的速度分别为50 km/h、40 km/h;每条道路路口设置交通管控卡口,各卡口的通行证检查时间为5 min。应急救援物资“最后一公里”配送行动按照表4中的应急行动方案有序进行。

表4 应急行动方案

采用已完成行动的个数与总行动个数的比值表征救援任务完成度,则应急行动方案的救援时间和救援任务完成度如图5所示。由图5可知,没有智能化选择交通管控方式的行动方案需要137.5 min,而执行通过应急交通管控模型产生的行动方案需要124 min,应急救援行动效率提高10 %。实验结果证明选择合理的交通管控方式,可以有效完成突发事件中的应急处置工作,保证救援行动顺利进行。

图5 救援时间和任务完成度

5 结论

(1)提出HTN规划和SVM相结合的应急交通管控决策模型,用以解决突发事件应急处置过程中交通管控力度选择和应急资源保障“最后一公里”问题。对于应急交通管理问题,通过分析其情景、环境、资源需求等,建立SVM模型,并集成到HTN规划方法中。将SVM模型得出的管控力度扩展到HTN方法集中,不仅利用了SVM在分析管控方面的优势,也提高了HTN规划在数据处理方面的能力。以新冠肺炎疫情防控为背景设计出算例,发现执行应急交通管控模型后应急救援行动效率显著提高,验证了该方法的可行性。

(2)基于HTN规划和SVM的应急交通管控决策模型充分发挥了SVM的分类识别能力和HTN规划的逻辑推理能力,可以保证在应急处置过程中根据现场实际情况选择出最优的交通管控方式和最优的道路进行应急资源配送,缩短应急决策时间,提高应急救援效率。