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

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

前言

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

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

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

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

1 并行加速測試架構(gòu)

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

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

圖1 并行加速測試架構(gòu)

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

架構(gòu)中涉及的名詞定義如下：

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

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

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

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

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

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

（7）量化指標(biāo) 根據(jù)試驗(yàn)?zāi)康乃x的評價(jià)指標(biāo)。

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

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

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

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

2 加速測試模塊構(gòu)建

2.1 頂層管理模塊

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

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

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

通過頂層管理模塊的運(yùn)行，底層執(zhí)行單元會逐步向具有較高探索價(jià)值的子集空間富集，進(jìn)一步強(qiáng)化高危險(xiǎn)子集空間內(nèi)危險(xiǎn)場景的生成，提高測試效率。

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

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

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

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

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

2.2 中層協(xié)調(diào)模塊

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

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

其中：

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

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

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

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

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

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

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

中層協(xié)調(diào)還負(fù)責(zé)標(biāo)記空間內(nèi)的低效單元。 空間中第個(gè)底層執(zhí)行單元成為低效單元的概率f為

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

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

2.3 底層執(zhí)行模塊

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

圖4 計(jì)算單元軟件詳情

3 測試試驗(yàn)與結(jié)果分析

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

以HighD數(shù)據(jù)集中的前車切入邏輯場景為例，參照現(xiàn)有場景要素選擇方法。本次試驗(yà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個(gè)具體場景參數(shù)。

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

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

圖5 前車切入測試場景危險(xiǎn)結(jié)果

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

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

表1 4種方法測試過程

4 結(jié)論

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