基于圖模型的自動駕駛推理任務調度

王娟娟 喬 穎 王宏安

1(中國科學院軟件研究所 北京 100190) 2 (中國科學院大學 北京 100049) (wjuanj89@126.com)

基于圖模型的自動駕駛推理任務調度

王娟娟1,2喬 穎1王宏安1

1(中國科學院軟件研究所 北京 100190)2(中國科學院大學 北京 100049) (wjuanj89@126.com)

隨著車載傳感器設備數量的增多，交通設施和城市地標的快速變化、人車混行的復雜路況，對自動駕駛車輛實時反應的能力要求不斷地提高.如何通過帶有安全性保證的調度策略來應對物理環境中源源不斷產生的傳感器實時源事件輸入，如何及時地控制傳動系統來處理源事件并進行推理操作及其響應以規避危險是值得研究的問題.為此，將自動駕駛汽車視為安全攸關系統，提出了一種硬實時推理任務調度方法，首先為自動駕駛的推理過程建立了基于可并行有向無環圖的推理任務模型；其次，提出了自動駕駛推理任務調度算法及其準入算法，保證了所調度的推理任務都能在滿足硬實時約束的情況下完成自動駕駛推理操作及其響應動作.最后，進行了模擬實驗，實驗結果驗證了該調度及其準入控制算法的有效性.實驗結果表明:推理任務調度算法比直接調度算法和模型轉換算法在調度成功率上分別高出9.62%和7.31%，該推理任務準入控制算法比Baruah的準入控制算法在任務集準入率上平均高出7.15%.

自動駕駛；安全攸關；有向無環圖；實時調度；準入控制

具備環境感知、自動變道功能的自動駕駛汽車是集成人工智能技術最顯著的系統之一.隨著云計算、大數據、物聯網的快速發展，已經形成了萬物互聯、海量計算的超融合信息基礎設施，并逐步形成了車聯網[1].目前，已經能夠通過攝像頭、雷達、RFID、GPS等電子設備，實現對車輛、道路、交通環境等信息的采集，在車-路-人-環境-網絡之間進行無線通信和信息交換，并將信息匯集在云端，計算出當前的交通態勢以及不同車輛的最佳行駛路線，并及時匯報路況和安排信號燈周期，實現對人、車、路的智能監控、調度和管理.

但是，集成了眾多人工智能最新研究成果的自動駕駛系統，仍然面臨著諸多關鍵問題的挑戰.即使是經過上百萬公里測試的谷歌汽車，也無法辨別水坑、沒蓋的檢修井[2]；已投產并使用的特斯拉Model S汽車也出現過傷亡事件.目前，雖然自動駕駛的總里程已經超過了1.3億英里[3]，但是大部分的測試路段是路況較為簡單的高速公路，在復雜的人-車混合道路上的測試并不充分.

從本質上看，自動駕駛汽車是集成了傳動系統(包括轉向控制、制動控制、檔位控制、油門控制)、感知系統(例如雷達、攝像頭)和推理系統(如圖像識別、計算機視覺、模式識別、機器學習等)的輪式智能機器人.

自動駕駛汽車是技術高密度產品，能在路面行駛過程中感知當前路況，對周圍環境中的車輛、行人、交通信號、障礙物等進行識別，并根據預設策略進行安全行駛.

自動駕駛汽車經歷了3個發展階段：

1) 專用實驗型車輛橫向/縱向駕駛.在該階段，大多數的自動駕駛車輛都是以規則匹配為智能引擎、以地理信息系統為導航、以視覺傳感器、距離傳感器為路況識別、以自動傳動為行駛控制的實驗型車輛.該類實驗車輛已經可以在行人稀少、路況明確、天氣良好的環境中，進行無人工干預的自動駕駛行駛.如加州大學伯克利分校的PATH項目1997年在7.6英里公路上實現了由8輛車組成的自動駕駛車隊[4].

2) 開放路況半自動駕駛.目前，谷歌汽車、特斯拉、寶馬、奔馳等廠商已經在商用的車型上使用了自動駕駛的系統，能夠在無人干預的情況下進行駕駛.但是由于技術的不完善，仍在每隔一段時間后，提示由人手放在方向盤上進行操作.

3) 開放路況全自動駕駛.在開放路況上進行半自動駕駛的商用汽車，標志了全自動駕駛技術正在逐步成熟；如特斯拉、谷歌汽車等品牌計劃推出可以在開放路況上使用的全自動駕駛汽車.

然而，盡管經過了幾十萬公里或上百萬公里的測試，即使如谷歌和特斯拉這般強大的科技實力，仍無法保證自動駕駛汽車能夠萬無一失地運行.特斯拉在發布全自動駕駛系統后甚至于又進行了相應的降級[3]，將其變更回半自動的駕駛系統.這種情況的出現，主要是由于3方面原因：

1) 路況感知信息不完整.由于路況復雜性過大，汽車作為具有高度復雜性、智能化的自動控制系統，在運行過程中各種傳感器、網絡、傳動設備等有發生故障的可能；自動駕駛系統很可能無法完整得到所有“正確”的信息.例如2016年7月特斯拉Model S在美國弗羅里達州的傷亡事件中，由于其車載傳感器未能準確識別出一輛白色貨車，導致2輛車發生了碰撞.針對自動駕駛系統中傳感器感知不完全可靠的問題，國內外已經進行了一系列研究[5-8].其中，北京大學馬連韜等人[8]為路網數據的潛在錯誤提出了容錯性方案，利用相同車輛及相同路段在誤差上存在的內在關聯，對缺失數據進行補全；并充分考慮到不同質量傳感器對環境友好性評估的影響，確定了基于端設備質量加權的評估計算策略，獲得了良好的效果.

2) 路況感知信息沖突.由于車聯網的逐步部署，自動駕駛系統的信息來源包括了車載傳感器(如攝像、雷達等)和通過地理信息系統獲取到的駕駛路線，通過網絡傳遞的信息有可能與車載傳感器的信息相互沖突.例如高樓林立的街道，通過偏差的GPS定位信息獲取到的街景導航地圖與車載攝像頭、雷達獲取到的信息并不一致；道路臨時施工封閉，根據原有的道路信息就無法正確實現導航；在路況良好、車輛高速行駛的情況下，出現行人橫穿馬路的突發事件等等.國內外也已經對路況感知信息沖突的問題開展了相關研究[9-12].其中，中國科學院計算技術研究所的陳浩等人[12]為路況感知信息中出現的高沖突信息提出了DSIT的處理沖突方法，通過邏輯運算的證據組合，能較好地適應高沖突信息間的融合.

Fig. 1 Architecture of auto-driving cars圖1 自動駕駛汽車的總體架構

3) 道路復雜性過大.在道路上可能會出現大量不可預知的事件，并且對這些事件進行安全處理的時限不同.比如，高速公路上突然有鹿、牛等動物橫穿；在人流密集的地方拐彎時突然出現行人；在高速路行駛時前方出現深坑.理論上，自動駕駛嚴格應該可以應對任何道路狀況.但是隨著車載傳感器設備的數量增多，城市地標和交通設施的快速變化、人車混行的復雜路況，對自動駕駛車輛實時反應的能力要求不斷地提高；而車載硬件的計算資源能力受限，這給自動駕駛車輛在實時性上提出了嚴峻挑戰.車輛自動駕駛過程中信息處理的資源需求是不一樣的.車輛在正常駕駛的過程中，僅需比較平滑地處理相應的路況事件即可；但在突發事件的應急反應過程中，其處理時間短至秒級，包括了計算應急措施時間和采取應急措施時間，大量車載多模傳感器所產生的數據沒能得到及時推理操作及其相應指令輸出.自動駕駛汽車的計算資源是有限的，車內的傳動裝置、剎車裝置和轉向裝置都需要時間進行反應，如果不通過帶有安全性保證的調度策略來應對物理環境中源源不斷產生的傳感器實時源事件輸入，就無法及時地控制傳動系統來處理源事件以規避危險，而導致災難性的后果.如特斯拉Model S在2016年1月的傷亡事件中，由于前車緊急避讓，導致特斯拉躲避前車時撞上了道路清掃車.可以看出，自動駕駛汽車是安全攸關的，其進行自動駕駛的智能系統必須在一定的時間期限內完成對物理異常情況的推理操作及其響應；如何保證自動駕駛機動裝置能在硬實時約束下完成對大量車載多模傳感器所產生數據的及時推理操作及其相應指令輸出是個值得研究的問題.

然而目前國內外還缺少針對該問題的相關研究，為此，本文提出了一種自動駕駛硬實時推理任務調度機制.在自動駕駛汽車發現異常事件時，該機制首先盡可能綜合感知當前全面的路況，對自動駕駛智能推理操作所需的硬實時約束進行定義，如以當前路況所需車輛傳動系統的操作序列和碰撞預期時間為參考,為自動駕駛推理任務制定截止期；而后基于可并行的有向無環圖定義自動駕駛推理任務模型，并盡量在調度中利用該任務模型的結構、通過其在多處理器上的并行計算，給出這些推理任務進行調度的策略，再通過準入控制算法保證所有進入車載計算系統的推理任務都在其截止期之前完成，使這些推理任務滿足自動駕駛安全攸關系統的硬實時約束，從而保證了自動駕駛的安全性.本文對自動駕駛推理任務的調度算法和準入控制的算法進行了實驗，結果表明：該推理任務調度算法的調度成功率比直接調度算法和模型轉換算法的分別高出9.62%和7.31%，其準入控制算法比Baruah的準入控制算法在任務集準入率上平均高出7.15%.

1 自動駕駛汽車的結構及其推理系統

1.1自動駕駛汽車的總體結構

圖1展示了自動駕駛汽車的總體架構模型.自動駕駛汽車主要包括3種系統：

1) 感知系統.感知系統是自動駕駛汽車的“眼睛和耳朵”，如果不能準確地識別和感知周圍環境，那么，路況的認知、駕駛策略和車輛控制都無從談起.目前，車輛感知系統主要包括攝像頭、毫米波雷達、超聲波雷達、激光雷達等傳感器，獲取測量周圍車輛車速、探測周圍障礙物等路況信息，并將這些信息傳遞給推理系統.

2) 推理系統.推理系統是自動駕駛汽車的“大腦”.當推理系統接收到路況信息后，將根據已有的規則庫對路況進行識別和判斷，通過智能推理來決定是否要執行轉向、換擋、加/減速、剎車等行為.

3) 傳動系統.傳動系統是自動駕駛汽車的“四肢”.當傳動系統接收到自動駕駛的響應動作指令后，會執行相應的轉向、制動、加/減油門、換擋等操作.

因此，自動駕駛汽車安全行駛的核心問題是推理系統在當前路況發生改變時，如何通過感知系統接收的路況信息，從知識庫中進行相應的規則匹配推理，并給出響應動作指令來指導傳動系統，在其截止期到達前完成所有的響應動作.

1.2自動駕駛推理系統

圖2展示了自動駕駛推理系統結構，其主要流程包括5個步驟：

1) 傳感信息獲取.自動駕駛汽車擁有大量需要計算的信息，如通過車載傳感器獲取當前的車況和路況，通過網絡傳輸獲取當前的實時街景和路徑規劃.

2) 信息融合和預處理.自動駕駛汽車獲取到的信息是大量的、復雜的和異構的.因此，需要通過信息融合技術，進行相互印證和整合，提取出必要的、可靠的和準確的信息.

3) 判斷當前路況.在感知到當前路況后，需要判斷當前汽車是處于正常行駛狀態或應急處理狀態.正常行駛是指路況條件較好，車況正常的前提下，僅需保持規定速度和車道即可.應急處理是指在突發情況下，需要進行緊急剎車、轉向燈操作，以避免人員傷亡和經濟損失.應急處理狀況需通過應急規則推理引擎，最終將輸出截止期內可行的安全操作序列，并作用于傳動系統.

4) 規則推理和調度.應急規則推理引擎先根據規則庫，將傳感信息轉化為連續的事件流，通過時間滑動窗口進行過濾，去除不必要的路況信息.其次，基于自動駕駛推理任務準入控制算法安排進行車載計算系統的推理任務，并根據自動駕駛推理任務調度算法對已準入的推理任務進行調度，給出推理任務的安全操作序列，來保證所有自動駕駛推理任務均在其截止期之前完成推理操作及其響應動作.

5) 在傳動系統中執行安全操作序列.

為了保證自動駕駛的安全性，本文將在第2節中基于可并行的有向無環圖來定義自動駕駛推理任務模型，在第3節中基于該任務模型通過分析現有調度算法的問題并給出改進的調度算法及其對應的準入控制算法，并在第4節中通過實驗對提出算法的有效性進行驗證.

Fig. 2 Auto-driving reasoning system圖2 自動駕駛推理系統

2 自動駕駛推理任務模型

本文的目標是將自動駕駛應急操作規則推理和決策框架抽象為具有硬實時約束條件的推理過程，并建立相應的模型和求解，以提升自動駕駛過程的安全性.可并行的有向無環圖(directed acyclic graph, DAG)用于任務建模，可在調度中利用該結構的特點使推理任務在多處理器上實現并行計算且減少推理操作的重復執行，從而提高自動駕駛推理任務調度成功的可能性.為此，本節基于可并行的有向無環圖，給出自動駕駛推理任務模型，如圖3所示，實時推理任務τi可形式化地表示成({τi,j|1≤j≤ni},Gi,Di,Ti)，其中：

1) 偏序圖Gi.該有向圖定義了ni個子任務τi,j之間的偏序關系(每個子任務定義了自動駕駛的一個推理操作，不同的子任務可在多處理器上并行或串行執行)，決定了τi的執行流.

2) 相對截止期Di.τi從就緒到執行完所允許的最大時間間隔，其值為車載傳感器根據車速、制動距離、轉向速度等參數所計算出來的值.

3) 周期或最小到達間隔Ti.τi不同實例就緒時間的間隔，反映了自動駕駛推理任務到達的不同情況.

Fig. 3 Reasoning task model圖3 推理任務模型

偏序圖Gi中，若有邊從子任務τi,u指向子任務τi,v，則τi,u是τi,v的直接前驅，τi,v是τi,u的直接后繼.preddirect(τi,j)和succdirect(τi,j)分別是τi,j的直接前驅和直接后繼集合.若有路徑從子任務τi,u可達子任務τi,v，則τi,u是τi,v的前驅，τi,v是τi,u的后繼.pred(τi,j)和succ(τi,j)分別是τi,j的所有前驅和所有后繼的集合.沒有前驅的子任務稱為源任務，沒有后繼的子任務稱為終任務.

1) 就緒時間ri,j.若τi,j是源任務，ri,j是τi,j實例到達系統的時間(即被系統檢測到的時間)；否則，ri,j是Gi中τi,j所有的直接前驅結點都完成的時刻：即ri,j=max(fi,k)，τi,k=preddirect(τi,j)；

2) 執行時間Ci,j.通過最壞執行時間分析技術(worst-cast execution time analysis)預定義的τi,j所需執行的時間長度，則時刻t的剩余執行時間Ci,j(t)是Ci,j減去到時刻t為止累積的已執行時間.

表1列出了每個任務?τi(i≥1)及其對應的子任務τi,j(j∈{1,2,…,ni})在調度中可以用到的參數：

1) 開始時間si和si,j.τi和τi,j開始執行的時間；

2) 完成時間fi和fi,j.τi和τi,j執行結束的時間，即fi=min{t|Ci(t)=0}，fi,j=min{t|Ci,j(t)=0}；

3) 響應時間Ri.τi從就緒到完成的時間長度，Ri=fi-ri，Ri≤Di；

4) 絕對截止期di和di,j.τi和τi,j允許的最晚完成時刻，di=ri+Di，fi≤di；

5) 若τi所有的子任務τi,j都在其絕對截止期之前完成，則τi被成功調度.

Table 1 Parameters of Reasoning Tasks and Sub -Tasks表1 推理任務及子任務的調度參數

若任意實時推理任務集τ不能同時滿足2個條件，則τ將不能在m個執行速度為1的處理器上被任何算法調度成功：

m個執行速度為1的處理器在長度為Lt的時間段上所提供的系統容量最多不超過m×Lt個執行單元；然而，當U(τ)>m時，τ的總處理需求已超過m×Lt，無論用什么調度算法，這些處理器都已過載，因此，不能成功調度τ.

2) 對τ中任意的τi，其偏序圖Gi中關鍵路徑的長度Ccrii都不超過τi的相對截止期Di，即?τi(τi∈τ):Ccrii≤Di.

若Ccrii>Di，無論用什么調度算法，τi的執行都會超出其相對截止期，則τ被調度失敗.

3 自動駕駛推理任務調度方法

第2節的實時推理任務模型是基于可并行的有向無環圖，我們將這種任務簡稱為并行DAG任務，這類任務在多處理器上調度的難度表現為2點：

1) 一個推理任務被激活時，只有源任務被激活，其余的子任務在其所有直接前驅都完成時才被激活；即這些子任務的激活是隨著不同調度策略下其前驅執行情況的不同而動態變化的.在實時推理任務集被調度的過程中，調度器只知道當前時刻已經激活的子任務，卻無法預先得知所有子任務全部的調度信息.

Fig. 4 Incomparability of model transformation scheduling and direct scheduling圖4 模型轉換方法和直接調度方法的不可兼容性

2) 調度過程中推理任務的DAG結構在多處理器上的不同并行程度會產生不同的完成時間，即任務的完成時間具有不可預測性，給調度帶來不確定性，對可調度性的分析是個挑戰.

多處理器上帶偏序約束的(如DAG偏序約束)可搶占任務調度已被Ullman[13]證明是NP-Hard問題.那么，多處理器實時推理任務調度也是NP-Hard，即能判定實時推理任務集可調度性的多項式級或是擬多項式級的調度算法不存在.因此，本節主要是尋求對實時推理任務的有效近似調度算法而非最優算法.

把推理任務整體作為調度算法的輸入，將其當成普通任務來考慮調度策略，只在執行推理任務時保證其子任務間的時序約束的調度方法，稱其為直接調度方法.這種方法簡單易行、復雜度較低，但沒在調度中根據推理任務模型的結構特點給出有意義的指導，只是消極地在推理任務執行時才去滿足其子任務的時序約束，使調度失去了靈活性；當推理任務的最壞執行時間超過其相對截止期時，這種方法無法適用，通用性較差.

已有研究者對并行DAG任務提出了模型轉換的調度思想，這類調度的特點是通過計算所有子任務的局部偏差和局部截止期，把推理任務轉換成獨立的任務進行等價調度.如Saifullah等人提出了任務分解[14]調度算法，把任務的松弛時間按一定策略分配給所有的子任務后，為子任務分配局部偏差和局部截止期，把DAG任務分解轉成獨立的串行任務進行等價調度.而Qamhieh等人則提出了任務延展[15]調度算法，把任務中的部分可并行子任務按一定策略延展至其截止期(即把關鍵路徑所在的路徑延展至該任務的利用率到1為止)后，為剩余的子任務分配局部偏差和局部截止期，把DAG任務轉成獨立的串行任務進行等價調度.Qamhieh等人也對比了任務延展調度算法和任務分解調度算法的可調度性，結果表明任務延展調度算法始終優于任務分解調度算法.

但是，對并行DAG任務的模型轉換調度使DAG任務丟失了部分模型特性(即轉換后的任務可調度，原并行DAG任務也可調度；但反之不成立)，轉換后的任務模型不如原DAG任務模型通用.而且，文獻[16]通過2個調度的例子證明了模型轉換調度方法和直接調度方法是不可兼容的：如圖4(a)是一個用模型轉換調度方法可調度而用直接調度方法不可調度的例子，如圖4(b)是一個用直接調度方法可調度而用模型轉換調度方法不可調度的例子.

從圖4(c)和(d)調度失敗的例子可以看出，直接調度算法和模型轉換調度算法調度失敗的原因都是調度過程中沒有根據當時處理器的空閑情況靈活地調整任務DAG結構的并行執行程度.反過來看就是調度算法要通過為DAG任務分配不同的并行程度來決定處理器在不同時刻的空閑時間情況.

若一個時間單元在2個或多個處理器上都是空閑的(不妨設同一時間單元上空閑的處理器個數為k)，則稱該時間單元為并行空閑時間單元，其并行度為k.處理器的空閑時間預留不當是因為沒有成功做到3點：

1) 盡可能不多留處理器的空閑時間；

2) 在不得不留出處理器的空閑時間時，盡可能不保留并行的空閑時間；

3) 已經出現的并行空閑時間盡可能讓活動任務及時占用執行.

因此，本節算法的優化目標是使得并行空閑時間單元總數盡可能少而且并行空閑時間單元的并行度也盡可能小.這里，我們用任務比例公平和近似執行速率的思想，先給出優化問題的形式化描述及其優化目標和相應的約束條件，再提出一個有效的近似算法來趨近優化目標.

任務比例公平和近似執行速率的思想可有效地避免貪婪算法引起的處理器空閑時間預留不當問題,并為后續優化目標減少計算規模做準備，因此，先在多處理器上劃分時間片，再計算并保證各個時間片內每個活動推理任務的局部工作量，具體分為3步：

3) 推理任務τi的松弛度Li初始化為其偏序圖Gi的路徑松弛時間Sli：Li=Sli=Di-Ccrii.那么，在每個TSj內，若Li≠0，所有的任務需優先滿足LWi,j.

我們把自動駕駛推理任務調度問題描述為：將不同任務看成帶各自顏色的棋子，把多處理器看成可填入棋子的棋盤，空白格子是處理器的空閑時間.棋盤矩陣行數是處理器個數m，時間片TSj上的棋盤矩陣列數是p，在TSj內要分配LWi,j的任務個數是q.令tjs≤r≤tje,1≤t≤m,若棋盤矩陣r行l列的單元格沒有填入棋子，則Pr,l=0，Sr,l,k=0(1≤k≤q).若棋盤矩陣r行l列的單元格填入棋子i(1≤i≤q)，則Pr,l=i(表示該單元格對應的處理器單元是由τi來占用執行)，Sr,l,i=1，Sr,l,k=0(1≤k≤q且k≠i).

優化目標：每個時間片TSj內分配的任務需滿足max(min(Ml))，Ml=count(Sr,l≠0)，即每一列填入棋子的單元格個數滿足其最小值最大，以最大化利用車載處理器的計算能力.

約束條件：

2)ri,q=max(fi,p),?τi,p∈preddirect(τi,q)(子任務的時序約束).

根據上述的優化目標和約束條件，我們給出如下的近似算法思想：設定推理任務初始的并行程度，再調整部分任務的執行序列以趨近優化目標.也就是，初始狀態盡可能并行地占用處理器，再在調度中動態調整，不斷將并行的空閑時間單元減少或將其并行度降低，從而不斷接近優化目標.這里不求每個時間片都局部最優，只需滿足時間片上的局部工作量即可.該近似算法的核心步驟有3步：

1) 計算推理任務τi的松弛度Li，先按其初始值即其最佳執行時間(最大并行度，上限是m)的情況來調度，后隨著任務執行或被調整(即錯開延后來減少并行度)而重新計算Li.

2) 任務的Li越小，優先級越高.按優先級高低給任務先后分配TSj上的LWi,j.

3) 推理任務按照工作保留式(work-conserving)調度來占用多處理器.先按照第2步執行，若不滿足所有任務的LWi,j，則選取Li≠0且優先級最低的任務使其錯開地延后(使其可并行子任務部分串行化)，重復這個過程直至滿足所有任務的LWi,j.調整后的任務需滿足Li≥0，以使所有任務完成LWi,j的執行.

為保證上述近似算法的安全性，實時推理任務其準入控制的算法思想是：對加入新任務后的任務集，計算任務τk的最壞響應時間；若該任務集中所有任務的最壞響應時間都小于相對截止期，則準入新任務；否則，拒絕新任務.

借鑒Baker所提出的問題窗口分析方法[17],可得

4 實驗與結果

本節基于自動駕駛推理任務模型，隨機生成推理任務的測試集，分別用直接調度算法(direct scheduling, DS)、模型轉換算法(model transformation, MT)和第3節的推理任務調度算法(RS)進行調度，對比其任務的調度成功率；用第3節的準入控制算法(RS-AC)以及Baruah[18]對多處理器DAG任務的準入控制算法對這些測試集分別進行準入，對比兩者準入能力的高低.

4.1度量標準

調度成功率為

SuccRatio=SuccNum/TaskNum，

其中，SuccNum是測試集中成功被調度的任務個數,TaskNum是測試集中的任務個數.

任務集準入率為

AcRatio=AcTsNum/TasksetNum，

其中，AcTsNum是成功被調度的測試集個數(測試集中的所有任務均被準入),TasksetNum是隨機產生的測試集個數.

4.2數據集

4.3實驗結果

本節將對比隨機的任務測試集在其負載①遞增的情況下,3種調度算法的調度成功率和2種準入控制算法的任務集準入率，如圖5和圖6所示.

調度成功率的變化曲線如圖5所示，這里比較的是在每個任務集負載下生成的任務集通過直接調度算法(記作DS)、模型轉換算法(記作MT)和第3節的推理任務調度算法(記作RS)成功調度的任務比例.圖5中DS和MT曲線的對比表明了直接調度算法和模型轉換算法是不兼容的，RS曲線始終位于DS和MT曲線的上方，可以看出第3節的推理任務調度算法優于直接調度算法和模型轉換算法，且調度成功率平均分別比這兩者高出9.62%和7.31%.這是因為本文提出的推理任務調度算法在調度過程中不斷調整任務并行程度以逼近優化目標，因此，它比直接調度算法和模型轉換算法出現處理器空閑時間預留不當的幾率要小得多.

Fig. 5 Comparison of DS,MT,and RS圖5 DS，MT和RS調度成功率對比

任務集準入率的變化曲線如圖6所示，第3節的準入控制算法(RS-AC)與Baruah的準入控制算法成功準入并調度測試集的數目隨著任務負載的遞增而逐漸減少.圖6中RS-AC曲線始終位于Baruah曲線的上方，表明了本文的推理任務準入控制算法比Baruah的準入控制算法的準入能力更強，任務集準入率平均高出7.15%.

Fig. 6 Comparison of Baruah and RS-AC圖6 Baruah和RS-AC準入任務率對比

從實驗結果可以看出，通過為自動駕駛系統引入硬實時推理任務調度機制，基于可并行的有向無環圖定義自動駕駛推理任務模型，并在調度中利用該任務模型的結構根據當前車載處理器的空閑情況靈活安排推理任務的并行計算，且以準入控制算法保證所有進入車載計算系統的推理任務都能在其截止期之前完成，從而提升了自動駕駛時應急避險的安全性.

5 總 結

本文提出了一種自動駕駛硬實時推理任務調度機制，用于在路況發生變化時，自動駕駛汽車可以盡可能綜合當前路況，給出滿足硬實時約束的自動駕駛智能推理操作及其響應指令序列.針對自動駕駛推理安全操作序列求解問題，本文首先基于可并行的有向無環圖定義了自動駕駛的推理任務模型，接著分析了自動駕駛推理任務調度所面臨的挑戰，并給出了自動駕駛推理任務調度問題的形式化定義、優化目標以及約束條件，再通過近似算法解決了該問題，也提出了相應的準入控制算法.最后，通過實驗結果驗證自動駕駛推理任務調度模型及其求解算法有效地提升了自動駕駛的安全性.在下一步工作中我們將結合自動駕駛中傳感器對路況的感知不完全可靠和可能存在相互沖突信息的情況以及自動駕駛技術中出現的新方法細化本文的推理任務模型，并在此基礎上，探索新的自動駕駛推理任務調度方法.

[1] Liu Xiaoyang, Wu Minyou. Vehicular CPS: An application of IoT in vehicular networks[J]. Journal of Computer Applications, 2012, 32(4): 900-904 (in Chinese) (劉小洋, 伍民友. 車聯網: 物聯網在城市交通網絡中的應用[J]. 計算機應用, 2012, 32(4): 900-904)

[2] Lee G. Major limitations hidden in Google automatic driving vehicles[J]. China Incubator, 2014, 16(8): 14-15 (in Chinese)(李·戈梅斯. 谷歌自動駕駛汽車隱藏著一些重大的局限[J]. 科技創業, 2014, 16(8): 14-15)

[3] Parkin S, Li Yumeng. The paradox of automatic driving vehicle[J]. China Civil and Commercial, 2016, 12(8): 82-83 (in Chinese) (Simon Parkin, 李雨蒙. 自動駕駛汽車面臨的悖論[J]. 中國民商, 2016, 12(8): 82-83)

[4] Chen Xiaobo. Challenges and prospects for the development of automatic driving[J]. Integrated Transportation, 2016, 17(11): 9-13 (in Chinese) (陳曉博. 發展自動駕駛汽車的挑戰和前景展望[J]. 綜合運輸, 2016, 17(11): 9-13)

[5] Rohani M, Gingras D, Vigneron V, et al. A new decentralized Bayesian approach for cooperative vehicle localization based on fusion of GPS and VANET based inter-vehicle distance measurement[J]. IEEE Intelligent Transportation Systems Magazine, 2015, 7(2): 85-95

[6] Hostettler R, Djuric＇ P M. Vehicle tracking based on fusion of magnetometer and accelerometer sensor measurements with particle filtering[J]. IEEE Trans on Vehicular Technology, 2015, 64(11): 4917-4928

[7] Boada B L, Boada M J L, Diaz V. Vehicle sideslip angle measurement based on sensor data fusion using an integrated ANFIS and an unscented kalman filter algorithm[J]. Mechanical Systems & Signal Processing, 2016, 72(3): 832-845

[8] Ma Liantao, Wang Yasha, Peng Guangju, et al. Evaluation of GPS-environment friendliness of roads based on bus trajectory data[J]. Journal of Computer Research and Development, 2016, 53(12): 2694-2707 (in Chinese)(馬連韜, 王亞沙, 彭廣舉, 等. 基于公交車軌跡數據的道路GPS環境友好性評估[J]. 計算機研究與發展, 2016, 53(12): 2694-2707)

[9] Vanderhaegen F. A rule-based support system for dissonance discovery and control applied to car driving[J]. Expert Systems with Applications, 2016, 65(3): 361-371

[10] Almodfer R, Xiong S, Fang Z, et al. Quantitative analysis of lane-based pedestrian-vehicle conflict at a non-signalized marked crosswalk[J]. Transportation Research Part of Traffic Psychology & Behaviour, 2016, 42(5): 468-478

[11] Morando A, Victor T, Dozza M. Drivers anticipate lead-vehicle conflicts during automated longitudinal control: Sensory cues capture driver attention and promote appropriate and timely responses[J]. Accident Analysis & Prevention, 2016, 97(6): 206-219

[12] Chen Hao, Wang Rui, Sun Rongli, et al. DSlT: An evidence reasoning method for information fusion in wireless sensor networks[J]. Journal of Computer Research and Development, 2015, 52(4): 972-982 (in Chinese)(陳浩, 王睿, 孫榮麗, 等. DSlT: 面向傳感網信息融合的證據推理方法[J]. 計算機研究與發展, 2015, 52(4): 972-982)

[13] Baruah S, Bonifaci V, Marchettispaccamela A, et al. A generalized parallel task model for recurrent real-time processes[C] //Proc of the 33rd IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 2012: 63-72

[14] Saifullah A, Agrawal K, Lu C, et al. Multi-core real-time scheduling for generalized parallel task models[C] //Proc of the 32nd IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 2011: 217-226

[15] Qamhieh M, George L, Midonnet S. A stretching algorithm for parallel real-time DAG tasks on multiprocessor systems[C] //Proc of the 22nd Int Conf on Real-Time Networks and Systems. New York: ACM, 2014: 13-22

[16] Qamhieh M, Midonnet S. Simulation-based evaluations of DAG scheduling in hard real-time multiprocessor systems[J]. ACM SIGAPP Applied Computing Review, 2015, 14(4): 27-39

[17] Baker T P. Multiprocessor EDF and deadline monotonic schedulability analysis[C] //Proc of the 24th IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 2003: 120-129

[18] Baruah S. Improved multiprocessor global schedulability analysis of sporadic DAG task systems[C] //Proc of the 26th Euromicro Conf on Real-Time Systems. Piscataway, NJ: IEEE, 2014: 97-105

Graph-BasedAuto-DrivingReasoningTaskScheduling

Wang Juanjuan1,2, Qiao Ying1, and Wang Hongan1

1(InstituteofSoftware,ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)

With the increase of vehicle mounted sensors, the rapid change of urban landmarks and traffic facilities as well as the complex traffic conditions of vehicles and pedestrians, the demand for real-time auto-driving response capability is continuously becoming urgent. How to provide safety guarantee for auto-driving systems by handling the continuing events from sensors and accomplishing the reasoning process via scheduling strategies is worth studying. In this paper, a hard real-time scheduling method of reasoning tasks for automatic driving system is proposed, including a task model based on parallel directed acyclic graphs with hard deadlines, a scheduling algorithm and admission control algorithm to ensure the reasoning operations and reactions within their hard real-time constraints. The experimental results show that our proposed method can effectively increase the success ratio of auto-driving reasoning tasks by average 9.62% and 7.31% compared with the direct scheduling algorithm and model transformation scheduling algorithm; and has also higher admission control capability by average 7.15% compared with the algorithm proposed by Baruah, which is promising to be applied in the auto-driving system for the security concern.

auto-driving; safety-critical; directed acyclic graph; real-time scheduling; admission control

Wang Juanjuan, born in 1989. PhD candidate. Her main research interests include real-time intelligence and real-time scheduling.

Qiao Ying, born in 1973. PhD, professor. Her main research interests include real-time intelligence and real-time scheduling.

Wang Hongan, born in 1963. PhD, professor and PhD supervisor. His main research interests include real-time intelligence, real-time scheduling and human-computer interaction.

2017-03-21；

：2017-05-12

TP391