張培興，邱 彬，朱 冰，趙 健，孫宇航，范天昕

（1. 吉林大學，汽車仿真與控制國家重點實驗室，長春 130022；2. 清華大學，汽車安全與節(jié)能國家重點實驗室，北京 100084；3. 工業(yè)和信息化部裝備工業(yè)發(fā)展中心，北京 100846）

前言

隨著自動駕駛技術的不斷成熟，實現(xiàn)自動駕駛汽車量產(chǎn)上路已具備了一定的技術可行性，然而如何驗證自動駕駛系統(tǒng)的安全性尚未形成統(tǒng)一的共識，這已成為制約自動駕駛汽車量產(chǎn)的重要障礙。

基于場景的測試方法是解決自動駕駛系統(tǒng)安全性驗證難題的重要手段，根據(jù)自動駕駛汽車的開發(fā)過程將測試場景分為功能場景、邏輯場景和具體場景3 個層次。具體場景作為測試過程中直接使用的場景結構，其生成方法已成為當前的研究熱點。在研究初期，從邏輯場景抽樣具體場景的過程多采用遍歷獲取所有組合或蒙特卡洛隨機生成的方式。由于邏輯場景中覆蓋大量的安全具體場景，這類場景對于測試過程而言價值較小，降低了整體的測試效率。為解決這一問題，基于危險場景強化生成的加速測試方法得到越來越多的關注。這類方法主要分為基于概率的方法與基于優(yōu)化的方法兩類?；诟怕实姆椒ㄗ钕扔蒢hao 等提出，其使用重要性采樣的方式建立似然函數(shù)，提升危險場景發(fā)生概率從而提高測試效率；Feng等和Gao等也提出了類似的基于概率的危險場景生成方式?；趦?yōu)化的方法將危險場景看作參數(shù)空間中的最優(yōu)解，尋找危險具體場景的過程可視為參數(shù)優(yōu)化的過程，Zhu等建立了多種優(yōu)化搜索框架。

然而，上述兩類加速方法大多基于串行處理結構，即下一試驗點的生成必須依賴上一試驗結果，這使其無法充分利用并行計算的優(yōu)勢。隨著自動駕駛系統(tǒng)復雜程度的增加和應用范圍的擴大，其須測試的場景數(shù)量呈指數(shù)爆炸的形式，并行的測試手段將成為未來自動駕駛測試的趨勢。一些學者已開始將并行測試手段引入自動駕駛系統(tǒng)測試過程，Andreas 等將快速搜索隨機樹引入并行測試中，百度也正在建立自動駕駛并行測試實驗室，但現(xiàn)有研究大多未考慮危險場景的強化生成，尚未實現(xiàn)并行測試與加速測試的有效融合。

為解決上述方法的不足，本文中將并行測試方法與基于優(yōu)化的危險場景生成框架相融合，提出一種自動駕駛系統(tǒng)并行加速測試方法。該方法分為3層架構：頂層管理層負責子集空間之間底層執(zhí)行單元的流動和子集空間關閉與合并；中層協(xié)調層負責下屬子集空間內底層執(zhí)行單元測試參數(shù)的生成；底層執(zhí)行層負責具體試驗的運行。以前車切入場景為例，對某黑盒自動駕駛算法分別使用并行加速、并行遍歷、單線程加速和單線程遍歷4 種方式進行對比測試，在測試具體場景總數(shù)為4590 的情況下，4 種方式均發(fā)現(xiàn)所有危險場景，其分別耗時1.3、5.7、22.4和96.2 h，證明了本文方法的有效性。

1 并行加速測試架構

隨著自動駕駛系統(tǒng)復雜程度的增加，測試過程須考慮的要素數(shù)量不斷提高，由此導致邏輯場景參數(shù)空間迅速增大，且隨著測試要素種類的增加極易產(chǎn)生維度爆炸現(xiàn)象，傳統(tǒng)矩陣測試的方式在測試效率和測試成本等方面已無法滿足自動駕駛系統(tǒng)的測試需求，基于危險場景強化生成的加速測試方法成為自動駕駛系統(tǒng)安全性驗證的主流。

將加速測試方法與并行計算方式相結合，提出由頂層管理層、中層協(xié)調層、底層執(zhí)行層構成的3 層并行加速測試架構，在充分利用多計算單元優(yōu)勢進行并行計算的前提下，通過危險場景強化生成進一步加速測試進程。加速測試架構如圖1 所示，每層包含若干個計算單元。

圖1 并行加速測試架構

在試驗過程中，首先將邏輯參數(shù)空間的全集空間按照一定的規(guī)律劃分為若干個僅包含參數(shù)空間不同部分內容的子集空間；分配不同計算單元的角色，包括頂、中、底3 層，整個全集空間僅包含一個頂層管理單元，每個子集空間有其各自的中層協(xié)調單元，其余均為底層執(zhí)行單元；將底層執(zhí)行單元平均分配到不同的中層協(xié)調單元下屬的子集空間中進行參數(shù)試驗；隨著試驗的進行，頂層管理單元協(xié)調底層執(zhí)行層中的不同底層執(zhí)行單元在不同子集空間之間進行流動，將量化指標值較差的子集空間中的低效單元轉移到量化指標值較好的子集空間；中層協(xié)調單元計算下屬子集空間內的底層執(zhí)行單元執(zhí)行試驗的具體參數(shù)，并標記下屬子集空間內的低效單元；底層執(zhí)行層由多個并行的計算單元構成，它們可各自獨立地接收中層協(xié)調層發(fā)送來的試驗參數(shù)進行試驗。相比現(xiàn)有方法，由于將邏輯場景參數(shù)空間分區(qū)，可以在宏觀層級保障測試的完備性，更大幾率發(fā)現(xiàn)所有危險場景所在區(qū)域；通過子集空間之間和子集空間內部的底層執(zhí)行單元調度，可以在微觀層級提高危險場景的生成概率，提升測試效率。

架構中涉及的名詞定義如下：

（1）頂層管理單元 負責全集空間層面調度底層執(zhí)行單元流動的計算單元，數(shù)量為1，同時負責子集空間關閉與合并；

（2）中層協(xié)調單元 負責下屬子集空間層級的底層執(zhí)行單元流動的計算單元，其數(shù)量與活躍子集空間數(shù)量相同，同時負責標記子集空間內的低效單元；

（3）底層執(zhí)行單元 接收中層協(xié)調單元發(fā)送的試驗參數(shù)進行仿真試驗的計算單元；

（4）低效單元 測試效率較低，可能被頂層管理單元調配至其它子集空間的底層執(zhí)行單元；

（5）全集空間 邏輯場景參數(shù)空間離散生成的所有具體場景參數(shù)集合空間；

（6）子集空間 將全集空間劃分得到的部分具體場景參數(shù)集合空間；

（7）量化指標 根據(jù)試驗目的所定義的評價指標。

頂層管理單元在一輪迭代過程中的詳細工作內容如下：頂層管理單元首先根據(jù)每個子集空間里的中層協(xié)調單元發(fā)送的子集空間量化指標值確定該空間的流入流出情況，如圖2 中的藍色、橙色方框所示；隨后頂層管理單元會依次計算每個流出子集空間內的每個低效單元是否流出，將確定流出的低效單元進行標記；之后頂層管理單元依次計算流出的低效單元流入的子集空間標號，如圖2 中的箭頭所示；對于沒有探索價值的子集空間，頂層管理單元會將其關閉避免底層執(zhí)行單元流入，如圖2 中的叉號所示。在試驗結束后，頂層管理單元還將臨近的危險位置所在的子集空間進行合并，從而形成完整的危險空間分布，如圖2 中左下方兩個小區(qū)域邊界的虛線所示。

圖2 頂層管理單元工作示意

為保證空間內部的底層執(zhí)行單元前往較為危險的參數(shù)位置，建立了中層協(xié)調單元以確保子集空間內的危險場景參數(shù)強化生成，整個工作框架如圖3所示。為擴大前期探索自由度，本文中引入了匯聚區(qū)域的概念，匯聚區(qū)域指子集空間內量化指標值超過閾值的參數(shù)點位置（極值點）可以影響的周圍其他參數(shù)的范圍，如圖3 中的陰影區(qū)域所示。中層協(xié)調單元的管理原則如下：匯聚區(qū)域內的底層執(zhí)行單元會根據(jù)極值點的位置和自身最大量化指標值的位置進行移動，而匯聚區(qū)域外的底層執(zhí)行單元僅會根據(jù)自身的最大量化指標值的位置進行移動，如圖3 中的空心箭頭和實心箭頭所示。同時，中層協(xié)調單元會記錄空間內的低效單元，如圖2和圖3中的黃色圓所示。

圖3 中層協(xié)調單元工作示意

2 加速測試模塊構建

2.1 頂層管理模塊

子集空間之間的底層執(zhí)行單元流動分為流入和流出兩部分。在每輪迭代結束后，對于子集空間平均量化指標值低于總體平均量化指標值且不存在活躍危險場景的子集空間，頂層管理單元會調度該子集空間內的低效單元以一定的概率離開當前空間并遷至其他流入空間。流失子集空間內的低效單元離開當前空間的概率p為

式中：p為第個子集空間中低效單元離開該空間的概率；ˉ為第次迭代所有底層執(zhí)行單元量化指標的平均值；g為第次迭代第個子集空間中的平均量化指標值；為當前迭代次數(shù)；為調節(jié)參數(shù)，代表頂層執(zhí)行者的權威程度，該值越大，頂層管理單元的權威程度越大，次級管理者越容易聽從頂層管理單元的調配，該值一般大于10；為預先設計的最大迭代次數(shù)；為頂層管理單元期望分配給每個子集空間的底層執(zhí)行單元數(shù)量，該值一般大于初始分配的底層執(zhí)行單元數(shù)量，代表頂層管理單元期望每個子集空間都有足夠多的底層執(zhí)行單元；n為第個子集空間在第輪迭代時的底層執(zhí)行單元數(shù)量；n為第個子集空間在第輪迭代時剩余的活躍極值點數(shù)量。

當前空間量化指標值越差、底層執(zhí)行單元數(shù)量越多、迭代次數(shù)越大，則該低效單元越易離開。

通過頂層管理模塊的運行，底層執(zhí)行單元會逐步向具有較高探索價值的子集空間富集，進一步強化高危險子集空間內危險場景的生成，提高測試效率。

需要注意的是，一個空間內可能存在多個低效單元，它們在一次迭代中的離開概率是順序計算的，即每個確定離開的低效單元都會改變當前子集空間內的底層執(zhí)行單元數(shù)量從而影響該空間的流失概率；當一個子集空間內的所有底層執(zhí)行單元都流失后，頂層執(zhí)行會將該空間定義為無價值區(qū)，將該空間關閉。

量化指標值較好或有新危險場景產(chǎn)生的空間為流入空間，流入空間的流入概率與該子集空間的底層執(zhí)行單元數(shù)量、新產(chǎn)生的危險場景數(shù)量和量化指標值有關，其流入概率為

式中：為符合輸入條件的子集空間個數(shù)；n*為符合條件的個子集空間在第回合的底層執(zhí)行單元的總個數(shù)；g*為符合條件的個子集空間在第回合的量化指標的總和；l*為符合條件的個子集空間在第回合產(chǎn)生的最大極值點的總數(shù)；a、b、c為調節(jié)參數(shù)，用來調節(jié)3個子項的權重，它們之和為1，隨著迭代的進行，新產(chǎn)生極值點數(shù)量的影響權重c越來越大；、、、分別為a、b的初始和終止系數(shù)。

同樣需要注意的是，每個新低效單元的流入都會改變空間的底層執(zhí)行單元數(shù)量，從而須重新計算流入不同空間的概率。

頂層管理還負責結束迭代。為保證沒有危險場景生成時及時停止迭代以提高計算效率，該方法設定的迭代停止條件為不存在活躍極值點，且一定迭代次數(shù)內沒有產(chǎn)生新的極值點。

2.2 中層協(xié)調模塊

中層協(xié)調模塊主要負責子集空間內部的危險場景強化生成，可參考現(xiàn)有優(yōu)化算法，例如模擬退火法和梯度下降法等，考慮到子集空間內參數(shù)并行的需求，參考粒子群優(yōu)化算法計算子集空間內底層執(zhí)行單元的下一次試驗參數(shù)。同時，為保證試驗前期有較強的隨機搜索能力，引入了匯聚區(qū)域的概念。滿足式（6）的點即表示其位于匯聚區(qū)域內，所有符合條件的點即構成了匯聚區(qū)域空間。

匯聚區(qū)域代表區(qū)域內極值（危險場景）影響的區(qū)域，它隨著迭代次數(shù)的增加不斷擴大。

其中：

式中：s為參數(shù)點在第維度與最近活躍極值點的距離；為參數(shù)空間的不同維度；為參數(shù)空間的維度；r為在第維的匯聚區(qū)域軸長；r為第輪迭代的匯聚區(qū)域軸長；為初始的匯聚區(qū)域軸長；為參數(shù)空間不同維度的參數(shù)最大值；為參數(shù)空間不同維度的參數(shù)最小值；為所有底層執(zhí)行單元的數(shù)量。

底層執(zhí)行單元下一回合移動的速度為

下一次參數(shù)的位置為

式中x為第+1 輪迭代中底層執(zhí)行單元的移動位置。

由于參數(shù)空間一般經(jīng)過離散處理，計算得到的點可能不會正好落在離散得到的參數(shù)點的位置處，此時在未試驗的參數(shù)點中找到距離計算得到最近的參數(shù)作為下一次試驗參數(shù)。

對于極值位置處的底層執(zhí)行單元，中層協(xié)調會在未試驗過的參數(shù)點中尋找距離其當前位置最近的參數(shù)點作為其下一步試驗參數(shù)。本文中規(guī)定當這一最近距離大于最初離散步長歐氏距離2 倍時，中層協(xié)調會將其剔除出活躍極值集合。

對于新流入的底層執(zhí)行單元，中層協(xié)調會隨機選擇一個活躍極值，并將其最近的未試驗過的位置作為下一次試驗參數(shù)。

中層協(xié)調還負責標記空間內的低效單元。 空間中第個底層執(zhí)行單元成為低效單元的概率f為

式中：、為調節(jié)參數(shù)，其和為1；為5 輪迭代次數(shù)內所有底層執(zhí)行單元的平均量化指標值；ˉ′為第個底層執(zhí)行單元在該子集空間內5 輪迭代次數(shù)內的平均量化指標值；為該空間內5 輪迭代次數(shù)內底層執(zhí)行單元的平均量化指標值；l為極值標記，若該點在第回合為最大極值，則為0；w為子集空間內第個底層執(zhí)行單元在第輪迭代時的擁擠系數(shù)，若其在上一回合的計算得到的點與未試驗最近點的距離大于最初離散步長歐氏距離的2 倍（計算點周圍的離散參數(shù)點全部被試驗），則該點處為1，否則為0。

為防止低效單元在不同子集空間之間發(fā)生頻繁流動，規(guī)定一個底層執(zhí)行單元在當前空間迭代次數(shù)少于5時不會被標記為低效單元。

2.3 底層執(zhí)行模塊

底層執(zhí)行層是在試驗過程中負責執(zhí)行具體仿真試驗的多個計算單元構成的集合，計算單元可由不同測試軟件構成。本文中選擇Matlab、PreScan 和CarSim 聯(lián)合仿真作為底層執(zhí)行單元，Matlab 作為頂層管理單元和中層協(xié)調單元的算法承載平臺，如圖4 所示。Matlab 在承載算法的同時，其UDP 模塊還負責頂層管理層、中層協(xié)調層與底層執(zhí)行層之間的數(shù)據(jù)通信；PreScan 提供仿真場景環(huán)境和傳感器模型，同時控制仿真測試的自動進行；CarSim負責提供高精度車輛動力學模型。

圖4 計算單元軟件詳情

3 測試試驗與結果分析

為評定所提出的并行加速測試方法在自動駕駛系統(tǒng)測試過程中的實用價值，使用并行加速、并行遍歷、單線程加速、單線程遍歷4 種方式對某黑盒自動駕駛算法在前車切入場景中的安全性進行測試，量化指標選擇測試過程中的最大碰撞時間的倒數(shù)。

以HighD數(shù)據(jù)集中的前車切入邏輯場景為例，參照現(xiàn)有場景要素選擇方法。本次試驗選擇切入后本車速度、切入后前車與本車距離和切入后前車速度v作為場景參數(shù)，它們的參數(shù)空間分別為［14 m/s，38 m/s］、［5 m，55 m］、［18.5 m/s，45.5 m/s］。速度間隔取3 m/s，距離間隔取1 m，共得到4590個具體場景參數(shù)。

為說明并行加速方法的有效性，且考慮測試過程中的設備成本，并行與單線程測試過程中的底層執(zhí)行單元并未選擇相同的配置。單線程測試過程中，選擇的主機參數(shù)為：CPU i99900k、GPU RTX 2080ti、內存32GB；并行測試過程中，選擇的主機參數(shù)為：CPU i56500、GPU GTX 1060、內存16GB。

4 種方法均發(fā)現(xiàn)了所有危險情況，危險結果如圖5 所示（圖中不同坐標軸代表邏輯場景參數(shù)類型，空心圓代表測試過的危險情況具體場景參數(shù)位置）。

圖5 前車切入測試場景危險結果

參照SHRP2 中關于碰撞危害等級的定義：嚴重碰撞、一般碰撞、輕度碰撞和接近碰撞，文中將接近碰撞及以上危害等級的場景均視為危險情況，篩選的具體參數(shù)選擇碰撞時間（time to collision，TTC），其閾值根據(jù)現(xiàn)有數(shù)據(jù)統(tǒng)計情況選擇1.5 s。

4 種方法的測試過程如表1 所示。從表中可以看出，并行加速測試方法耗時并沒有完全與單線程方法形成底層執(zhí)行單元的倍數(shù)關系，首先是因為并行測試主機配置相比單線程測試較低，其次是多線程之間的通信延遲和不同測試情況下的等待。本文設定的測試時長為30 s，當發(fā)生碰撞時試驗直接彈出，由于在并行的情況下本文的方法會等待所有底層執(zhí)行單元都完成當輪迭代后再進行下一步參數(shù)計算，這在一定程度上降低了算法的測試效率。不過根據(jù)4 種方法測試結果看出，雖然并行測試使用的主機配置較弱，但本文提出的方法充分顯示了多單元并行計算的優(yōu)勢，加速自動駕駛仿真測試流程。

表1 4種方法測試過程

4 結論

針對自動駕駛系統(tǒng)加速測試需求，將并行測試方法與危險場景強化生成框架相結合，提出一種自動駕駛系統(tǒng)并行加速測試方法，建立了3 層架構，頂層管理和中層協(xié)調分別負責全集空間和子集空間內的場景尋優(yōu)，底層執(zhí)行層負責具體仿真試驗。將該方法與并行遍歷、單線程加速、單線程遍歷3 種方法進行對比。結果表明，本文提出的并行加速測試方法可有效、快速地搜索出危險具體場景參數(shù)，加速自動駕駛系統(tǒng)測試流程，提高測試效率。