一种基于分类回归树的无人车汇流决策方法

苏 锑 杨 明 王春香 唐 卫 王 冰

诸如道路临时施工和车道减少等道路瓶颈处,由于被阻断车道中的车辆需要通过汇流来继续行程,导致原本有序的车流产生扰动.根据三相交通流理论[1],被动引发的换道行为必然导致交通流的大幅扰动,交通状态从同步流转变成拥堵流,且拥堵状况将向车流上游扩散,导致交通瘫痪,通行效率急剧下降[2].此外,汇流时的换道行为极易引发车辆事故,带来更大的损失.

在无人车技术及车间通信技术快速发展的背景下,交通控制从人—车—路闭环转变为车—路闭环,提高了车辆协作的效率,提升了安全性和通行效率.根据系统架构,基于无人车的交通流控制可分为集中式和分布式两大类.集中式控制依赖路边的主控电脑,通过车—路通信收集汇流点附近较大范围内车辆的状态信息,再依据这些全局信息对车辆的行为进行决策,并返送回被控车辆执行.Cao等提出的基于滚动优化的汇流控制方法[3],Marinescu等提出的基于空间槽的汇流控制方法[4],Rios-Torres等提出的最优在线交通流控制方法[5]以及Awal等提出的最优汇流策略[6]均基于集中式控制架构.但在实际应用中受现有通信技术的限制,集中式控制所要求的大量和稳定的数据通信往往得不到满足,致使控制效果变差.多车集中控制也使得主控电脑运算负荷巨大.而分布式控制依赖车载传感器及车—车通信获取环境信息,由行车电脑自主决策.这种架构有效减少网络流量及运算负荷,有较高的可实施性. Wang等[7]提出的主动式汇流方法采用了此架构.

在决策算法方面,已有的研究主要采用基于逻辑规则的方法或基于函数模型的最优化算法.前述Wang提出的方法采用了依据逻辑规则评估是否换道.该方法易于实现,有极高的实时性,但其逻辑规则难以描述复杂的车辆交互关系,在车流稍大的情况下汇流效率不高.Rios-Torres,Cao以及国内高校的陈思曼等[8]均提出了通过建立车辆的状态微分方程求解最优化问题来协调车辆的汇流方法.该方法适合于集中式控制,且对汇流点浮动的情况求解过程复杂,算法实时性较差.Kita在文献[9]中提出了基于博弈论的汇流方法,建立每种决策的收益矩阵,评估收益作出决策.该方法虽然适合于分布式控制架构,但其难以获得通行量方面的收益信息,从而难以在通行量方面提升汇流效果.

鉴于基于逻辑规则的方法对问题模型的刻画比较粗糙,控制精准度较差;基于函数模型的决策方式过于依赖有精确参数的物理模型,且其在模型精确性方面往往不如基于概率模型的算法.因此,本文提出了基于优秀决策样本的统计学习方法获得更为丰富和细腻的决策逻辑.

在优秀决策样本采集方面,Li等在文献[10−12]中指出稠密交通流情况下遍历解空间往往无法实现,而可以采用启发式的搜索算法获得车辆决策在某一指标方面的近似最优解.鉴于粒子群算法没有简单有效的措施防止陷入局部最优,蚁群算法计算开销大而本文求解空间维数较高,因此选择启发式的遗传算法,该方法在搜素本文离散解空间的情形下有较高的适用性.

有监督的统计学习算法中,KNN(K-nearest neighbor)算法对参数k敏感,针对本文研究的问题没有相关前期工作可以提供参数选择的经验.而朴素贝叶斯有各个特征相互独立的前设条件,本文选取的车辆环境特征关联性较大,与假设相悖.Weng等[13]曾采用分类回归树模型拟合了人类驾驶员在交通瓶颈处的汇流行为,获得了较高的拟合度.因此,本文选择了约束少、分类速度快和准确性高的分类回归树方法作为汇流决策的模型.并通过对比Wang提出的方法,验证汇流方案的高效性.

1 汇流决策寻优

1.1 数学模型

交通流的特性主要由流量、速度和密度来刻画.本文依据流量、平均车速及汇流处速度衰减程度等参数选取多个汇流场景作为样本,进行决策寻优.

本文的微观交通模型中,采用IDM(Intelligent driver model)模型刻画交通流中单个车辆的跟车行为.车辆状态与所处环境之间满足如下关系式

其中,vα,v(α−1)分别表示本车和前车车速,v0表示期望车速,s0表示最短车间距,T表示期望车头时距.车辆自身的加速和减速行为及并入车道后后继车辆的响应均受该模型约束.

本文研究的汇流问题采取决策点与汇流点分离,且汇流点浮动的方式进行汇流.如图1所示,车辆能够在道路瓶颈前L米处提前获知右侧车道即将关闭开始汇流决策,车辆可以在瓶颈前的任意位置选择汇流.汇流车辆的决策依据是周围车辆的位置、速度信息及相对瓶颈点的距离.可能作出的决策为加速调整、减速调整、保持车速或者立即换道.评价车辆汇流决策优劣的依据是瓶颈处的通行效率及汇流引起的车辆碰撞次数.

图1 汇流场景Fig.1 Merging scenario

由于单一车辆决策与瓶颈处通行量之间没有明确的函数关系,所以本文采用对一定数量的车辆实施汇流决策后合成的宏观表现来评价其对通行量的影响.为了合理限制寻优的计算量和耗时,本文截取各个典型汇流场景中的一部分,对该交通流片段中的所有车辆同时进行决策寻优.从而对决策评价的依据演化成为尽可能缩短所有车辆完成汇流所消耗的时间,并且不发生碰撞.

1.2 遗传算法寻优

本文将汇流过程中的决策基于时间片分割,形成一串决策序列,对这一序列采用符号编码,作为遗传算法的染色体,编码示例如图2.决策对应编码如下:

0—保持当前车速

1—减速调整

2—加速调整

3—执行换道

图2 汇流决策时间序Fig.2 Merging decision sequence

根据汇流点可以在一定距离内浮动的特性,本文采用可变有效位的编码方式.即车辆可以选择采用m个时间片来调整位置及速度,在第m+1个时间片中执行汇流.则对应的编码形式是:染色体中前m个基因位是0,1,2组成的随机序列,自第m+1个基因位开始所有后续基因位均用编码3填充.

适应度函数采用如下表达式

其中,tc(V)表示一特定交通片段中所有车辆完成汇流并全部通过瓶颈处所消耗时间.汇流中若发生碰撞适应度直接置零.

本文采用了无放回式随机余数选择算子(Remainder stochastic sampling with replacement, RSSR)[14]作为优胜劣汰的方式.RSSR算子依据个体的适应度值确定其在下一代群体中的生存数目,表达式如下

基于可变有效位染色体编码方式的单点交叉操作如下,以含10个时间片段的决策序列为例:

A染色体的有效交叉点有4个,B染色体的有效交叉点有7个.分别随机选择A、B的交叉点为2和6,截断后拼接.A染色体中的空缺位随机选择0, 1,2填补.B染色体中的冗余位舍去,由A段中的基因位覆盖.交叉结果为:

汇流决策的寻优不具有单调性,因此为防止遗传算法陷入局部最优解,对相似的最优解进行计数ConvergenceCount,当种群连续迭代5次均收敛于同一准最优解fitness(TempBest)时,发生一次大规模变异以更新种群中的基因模式,同时对变异次数用变量OptCount计数.3次大规模变异后,均收敛于相近的准最优值fitness(Best),则将Best作为近似最优决策.算法流程如算法1.

算法1.基于RSSR的遗传算法

2 分类回归树训练

分类回归树 (Classi fi cation and regression tree,CART)是一种有监督的统计学习方法.以损失函数最小化为目标对数据层层分类,建立决策树模型.分类决策树由于其对训练集容量要求较少、分类速度快和预测准确度高等特点适用于本文研究的问题.本文根据流量、平均车速和拥堵状况选取了50种典型的汇流场景在软件中仿真实现,采用第一节描述的寻优方法获取最优汇流决策.记录每个时间片中每台车周围的环境特征和对应的决策,作为标记的数据集训练分类决策树.

2.1 特征描述

车辆对环境的感知程度依赖于传感器的配置,测量范围及测量精度.无人车通常配备了GPS、惯导和雷达等定位及测距传感器,能够较为准确地获得车辆的绝对位置和相对位置.专用短程通信技术(Dedicated short range communication,DSRC)能够实现高速移动物体间短距通信,因此通过车载单元(On board unit,OBU)车辆间能够交换自身的状态信息,借助路侧单元(Road side unit,RSU)车辆能获悉更远范围内的路况信息.

参照现有技术条件,首先选取决策车辆本身相对于瓶颈处的位置及车速作为基本的特征信息,该信息可由RSU提供.其次选择车辆碰撞危险评估指标TTC(Time to collision).TTC表示若本车保持当前车速行驶,与前车的碰撞预计在多长时间后发生,其表达式如下:

如图3所示,汇流车辆与当前车道前驱车辆以及相邻车道前、后驱车辆的TTC均纳入对环境的评估指标.

此外,Pei在文献[15]曾指出,交通流密度是影响汇流点位置的重要因素.因此,本文还选取了本车与周围车辆的相对位置关系,作为当前局部交通流密度的评估.TTC及车辆相对位置关系均可以通过车载传感器及车间通信实时获得.环境特征变量在表1中详述.

图3 环境特征描述示例Fig.3 Environment feature description

表1 环境特征变量描述Table 1 Environment feature description

2.2 训练算法

分类回归树将所有训练数据集作为根节点,采用递归分割的方法选择特征向量中合适的变量及分割值对节点中的样本进行二分.经过分割的节点派生出两个子节点,循环往复直至满足分割的终止条件.最终生成树形结构的分割结果,叶子结点表示决策结果,从根节点到叶子结点路径上的分割特征及分割阈值表示作出该决策对应的环境条件.常用的节点分割算法有信息增益率法、基尼指数法和卡方分布检验法等.相比于基尼指数法和卡方分布检验法,信息熵增益法需要更长时间达到峰值,有更苛刻的划分标准.由于本文针对的特征向量维数不高,不会因为苛刻的分割条件而使计算时间过长,因此本文先对特征离散化,再选用信息增益率作为节点分割的标准.信息增益率计算方式如下:

式(7)表达了信息熵的计算方式,P(Ci)表示属于Ci决策的样本概率.式(8)中,IG(Ft,Gap)表示以环境特征Ft及对应的阈值Gap分割该节点中的样本所产生的信息熵增益.P(＜Ft,Gap)和P(＞Ft,Gap)分别表示节点样本二分后,两个子集各自所占父节点样本的比例.式(9)描述了信息增益比的计算方式.

节点分割会在满足以下三个条件中任意一个的情况下终止:1)节点中的样本数小于预设的阈值;2)节点的信息熵小于阈值;3)生成决策树的深度达到了最大深度.

决策树存在的过拟合问题可以通过剪枝有效防止.悲观剪枝法在实践中有效性较高,本文选择了该方法作为剪枝方式.悲观剪枝通过增加经验性的惩罚因子代替测试集来计算内部节点的误差率.通过比较内部结点与该节点派生的叶子节点的误差率决定是否剪枝.算法流程如算法2.

算法2.分类回归树算法

该算法采用栈结构和循环,将分裂得到的子节点压入栈中,在下次循环中取一栈元素,即子节点判断其是否需要再二分.其中,isLeaf表示是否满足终止条件.

3 实验结果与分析

实验平台为开源交通仿真软件(Simulation of urban mobility,SUMO).SUMO为德国宇航局开发的面向城市智能交通研究的仿真软件,可以自定义车辆数学模型、道路结构、交通流特性以及各种交通设施.此外,SUMO具有较为完备的仿真结果报告,例如平均旅行时间、排放和道路的平均通行量等.Wegener等开发了基于TCP的客户端—服务器模式的TraCI[16],开辟接口实现对SUMO中仿真元素在线干预.本实验中的所有汇流实验均在SUMO中通过TraCI接口实现实时控制.

3.1 分类回归树训练结果

在配置为Intel Core i7 4770,主频3.4GHz, RAM 4GB电脑上对50个汇流场景进行近80小时的寻优,最终获得了2311条样本.由于一段完整的汇流过程中,用于速度调整的策略远多于最终执行换道的策略,因此2311条样本中仅有200条有关换道决策的样本.这种不平衡数据集会严重影响分类决策树的训练效果.Batista等在论文中提出处理机器学习中不平衡数据集的方法[17]主要有过采样和欠采样.相比欠采样,过采样容易引起过拟合的问题,因此本文选择随机欠采样,减少与换道决策无关的样本,最终选用了636条样本训练分类决策树.训练终止条件为叶子节点至少包含10个样本,决策树的最大深度为9,最小信息熵为0.8.

决策树训练结果如图4所示,包含48个叶子节点,其中12个决策结果为保持车速,11为加速决策,16个为减速决策,9个为换道决策.离道路瓶颈的距离是影响决策的首要因素,车辆距道路瓶颈较近时,更倾向于作出换道决策,距瓶颈较远时,则更倾向于作出加减速等调整决策,这也符合人们的常识:距离瓶颈越近,越迫切的执行换道.当车辆处于低速状态更易作出决策,而高速状态则需要更多地考察环境信息来作出决策.TTC是影响决策最多的因素,过小或过大的TTC均导致调整决策,合适的TTC才导致换道决策.

3.2 仿真验证

图4 分类决策树结构Fig.4 Classi fi cation and regression tree

本节将比较基于分类回归树的汇流方法(CART)和同样基于分布式控制架构下,Wang提出的基于到达优先的汇流方法(PV).鉴于基于概率模型的CART方法较基于逻辑规则的PV方法有较大优势,本文还引入Awal提出的基于瓶颈点附近全局车辆信息的汇流方法(Optimal merging strategy, OMS)作为对标实验,比较基于局部信息方法与基于全局信息汇流方法的差距.此外,本文还设计仿真实验考察了分类回归树方法在有定位误差干扰情况下的汇流效率.

验证实验和对比实验均在SUMO中实现.汇流场景中设置了4000m的双车道与1000m的单车道交汇于Dm(0,0),产生了一个由车道数减少引起的汇流场景.图5为道路瓶颈处的仿真截图.仿真车辆最大速度为33.3m/s,最大加速度为4m/s2,最大减速度为−2m/s2,车辆依据泊松分布随机插入在双车道的左端D0(−4000,0),出发速度为30m/s左右.车辆在道路瓶颈前500mDr(−500,0)获悉即将发生汇流,开始执行换道决策算法.车间通信有效距离是300m,因此仿真过程中,车辆能收集周围300m内车辆的位置和速度信息,并作出决策.实验中分别在Dr和Dm设置感应线圈,用于检测进出汇流区域的车流.

图5 SUMO仿真环境Fig.5 SUMO simulation environment

本文选取了车辆平均等待时间、通行量和下游平均车速作为汇流效果的评测依据.

平均等待时间指所有车辆车速低于0.5m/s的时间累积均值.通常是由于道路瓶颈处产生拥堵而使车辆停车等待.本文选取了上游双车道流量1200veh/h、1800veh/h和2400veh/h,3种车流密度及符合恒定和泊松分布的两种车流特性针对上述3种汇流方案进行实验,仿真运行1200s,统计结果如表2.

表2 平均等待时间比较Table 2 Mean waiting time comparison

在不同车流量及不同的车流特性情况下,基于分类回归树的汇流方案相较于PV方法都具有明显优势,且其平均等待时间与基于全局信息方法相近.

平均通行量指道路瓶颈点下游一道路截面中,单位时间内通过车的数量,它直观反映了汇流效率.图 6和图 7分别描述上游双车道总流量为1400veh/h和2600veh/h时,下游的平均通行量.

小流量状况下,0∼200s内3种方法的汇流效果并无差异.200s后,汇流效果产生了差异,PV最终稳定在1050veh/h左右,而CART与OMS稳定时性能几乎一致,能够保持道路瓶颈点上游及下游流量近乎一致,有效防止了拥堵现象.

大流量状况下,0∼400s内3种方法的汇流效果并无差异.之后,汇流效果同样产生差异.PV最终稳定在1400veh/h左右,造成严重的拥堵现象. CART方法的稳定流量相较于OMS方法并没有悬殊的差异,在大流量情况下仍然能够有效抑制拥堵产生.由此实验对比可见,本文方法与基于全局信息的汇流方法在汇流效率方面有着很强的可比性,且其控制架构在应用过程中有着明显优势.

图8描述了恒定车流下,汇流点上游的平均车速.PV明显由于拥堵造成车流平均速度急剧下降,而基于决策树和基于全局信息的方法仍能够保持较高的车速,实现车流的持续高效通行.

图6 平均流量1400veh/h下游平均流量Fig.6 1400veh/h,mean fl ow

图7 平均流量2600veh/h下游平均流量Fig.7 2600veh/h,mean fl ow

图8 汇流点上游平均速度Fig.8 Mean velocity of upstream

本文方法对环境描述的准确程度依赖于车辆传感器的测量精度.车速测量通常采用编码器,该传感器能准确反映车辆的瞬时速度,但车辆定位所依靠的全球定位系统(Global positioning system,GPS)和惯性导航系统(Inertial navigation system,INS)等却存在较大误差,因此设置定位误差干扰下的仿真实验,考察分本方法汇流效率所受影响.

基于连续运行卫星定位服务参考站(Continuously operating reference stations,CORS)的定位结果与惯导融合后能够将定位误差控制在1∼2m范围内.其定位误差呈现为一段段的系统误差叠加上白噪声.模拟一段定位误差,其最小值为±1m,沿时间轴递增的高次函数再叠加上均值为0.3m方差为0.5m2的白噪声.分别对上游双车道流量为1400veh/h和2600veh/h情况下进行实验.

如图9所示,稀疏交通流情形下,定位误差并未对汇流效果产生负面影响.

图9 平均流量1400veh/h定位误差对汇流效果影响Fig.9 In fl uence of positioning error on merging eきciency,mean fl ow 1400veh/h

如图10所示,稠密交通流情形下,定位误差使得通行效率下降了约15%,但较前述PV方法仍有极大的优势.由于本文方法所依赖的环境特征描述均基于车辆间的相对位置,因此可以采用基于车间通信信号强度的相对定位方法来较准由GPS和INS求得的相对位置,以提高车辆间相对定位的精度,避免由定位误差产生的通行效率下降.

4 结论

本文通过决策树的方法,大量学习优秀汇流案例中的决策方法,使得车辆能够不仅根据临近车道的局部交通状况做出决策,还能根据本车道局部交通状况做出更为灵活的调整,作出使群体最优的决策.实验表明,本文所提出的汇流方法确实能够尽可能降低汇流行为对车流的扰动,即使通行量较大的情形下也能够保证较高的汇流效率,缩短了车辆的平均旅行时间.与基于全局信息的方法相比,不仅在通行效率方面可以与之媲美,而且在控制架构的实施效力方面有极大的优势.因此,基于分类回归树的汇流方法是一种通行量及可实施性均优的决策方式.此外,本文还验证了实际应用中传感器误差对本方法的影响.虽然会使汇流效率略微下降,但不影响其相对其他分布式汇流方法的汇流效率优势.至于通信时延及丢包等对汇流效果的影响更为复杂和多变,由于篇幅限制会在未来工作中进一步完善.

图10 平均流量2600veh/h定位误差对汇流效果影响Fig.10 In fl uence of positioning error on merging eきciency,mean fl ow 2600veh/h

1 Kerner B S.Experimental features of self-organization in traきc fl ow.Physical Review Letters,1998,81(17):3797−3800

2 Krauß S.Microscopic Modeling of Traきc Flow:Investigation of Collision Free Vehicle Dynamics[Ph.D.dissertation], University of Cologne,Germany,1998

3 Cao W J,Muka M,Kawabe T,Nishira H,Fujiki N.Merging trajectory generation for vehicle on a motor way using receding horizon control framework consideration of its applications.In:Proceedings of the 2014 IEEE Conference on Control Applications(CCA).Juan Les Antibes,France: IEEE,2014.2127−2134

4 Marinescu D,ˇCurn J,Bouroche M,Cahill V.On-ramp traffic merging using cooperative intelligent vehicles:a slotbased approach.In:Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems (ITSC).Anchorage,AK,USA:IEEE,2012.900−906

5 Rios-Torres J,Malikopoulos A,Pisu P.Online optimal control of connected vehicles for eきcient traきc fl ow at merging roads.In:Proceedings of the 18th International Conference on Intelligent Transportation Systems(ITSC).Las Palmas, Spain:IEEE,2015.2432−2437

6 Awal T,Kulik L,Ramamohanrao K.Optimal traきc merging strategy for communication-and sensor-enabled vehicles.In:Proceedings of the 16th International IEEE Conference on Published of the Intelligent Transportation Systems-(ITSC).The Hague,Netherlands:IEEE,2013.

7 Wang Z Y,Kulik L,Ramamohanarao K.Proactive traきc merging strategies for sensor-enabled cars.In:Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks.New York,NY,USA:ACM,2007.39−48

8 Chen Si-Man,Meng Xian-Shi,Ma Jun.Study on the model and simulation for con fl uence avoidance at ramp intersection.Agricultural Equipment and Vehicle Engineering, 2016,54(2):44−50 (陈思曼,孟宪实,马钧.匝道口智能车合流避撞模型及仿真研究.农业装备与车辆工程,2016,54(2):44−50)

9 Kita H.A merging-giveway interaction model of cars in a merging section:a game theoretic analysis.Transportation Research Part A:Policy and Practice,1999,33(3−4):305−312

10 Li L,Wen D,Yao D Y.A survey of traきc control with vehicular communications.IEEE Transactions on Intelligent Transportation Systems,2014,15(1):425−432

11 Li L,Wang F Y,Zhang Y.Cooperative driving at lane closures.In:Proceedings of the 2007 IEEE Intelligent Vehicles Symposium.Istanbul,Turkey:IEEE,2007.1156−1161

12 Li L,Wang F Y.Cooperative driving at blind crossings using intervehicle communication.IEEE Transactions on Vehicular Technology,2006,55(6):1712−1724

13 Weng J X,Xue S,Yan X D.Modeling vehicle merging behavior in work zone merging areas during the merging implementation period.IEEE Transactions on Intelligent Transportation Systems,2016,17(4):917−925

14 Brindle A.Genetic Algorithms for Function Optimization [Ph.D.dissertation],University of Alberta,Canada,1981.

15 Pei Y L,Dai L L.Study on intelligent lane merge control system for freeway work zones.In:Proceedings of the 2007 Intelligent Transportation Systems Conference.Seattle,WA, USA:IEEE,2007.586−591

16 Wegener A,Pi´orkowski M,Raya M,Hellbr¨uck H,Fischer S,Hubaux J P.TraCI:an interface for coupling road traきc and network simulators.In:Proceedings of the 11th Communications and Networking Simulation Symposium.New York,NY,USA:ACM,2008.155−163

17 Batista G E A P A,Prati R C,Monard M C.A study of the behavior of several methods for balancing machine learning training data.ACM Sigkdd Explorations Newsletter,2004, 6(1):20−29