基于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不僅需要描述應急交通管控的初始情景,還需要描述初始的應急資源分布情況。初始情景由一系列由謂詞邏輯表述的狀態組成。應急資源則包括可重用性資源和消耗性資源?？芍赜眯再Y源是應急處置后可以回收的資源,如交通工具,表示為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規劃的邏輯推理能力,可以保證在應急處置過程中根據現場實際情況選擇出最優的交通管控方式和最優的道路進行應急資源配送,縮短應急決策時間,提高應急救援效率。