一種基于分類回歸樹的無人車匯流決策方法

蘇 銻 楊 明 王春香 唐 衛 王 冰

諸如道路臨時施工和車道減少等道路瓶頸處,由于被阻斷車道中的車輛需要通過匯流來繼續行程,導致原本有序的車流產生擾動.根據三相交通流理論[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