01引言

自動駕駛的安全驗證是保證系統(tǒng)在給定環(huán)境中正確及安全操作的過程。系統(tǒng)的期望行為通過某些規(guī)范標(biāo)準(zhǔn)來定義，而系統(tǒng)失敗指其行為違反了這些規(guī)定。自動駕駛系統(tǒng)由于其復(fù)雜性可以認為是一個黑盒系統(tǒng)具備難以探知的特性，故難于理論分析和驗證其安全性，而使用暴力遍歷方法在復(fù)雜的環(huán)境中又非常低效。故本文著眼于一個主車行為、環(huán)境、交通參與物的行為交互的情景，介紹一種方使用優(yōu)化算法更高效尋找造成系統(tǒng)被測試系統(tǒng)失敗行為軌跡的方法。

本文的第二部分將對文中討論的問題及用到的符號做出定義，第三部分介紹部分可應(yīng)用于此類問題的優(yōu)化算法，最后一部分使用特定的數(shù)值實驗驗證這些方法。

02模型定義

（一）符號定義

?代表被測試系統(tǒng)、?代表環(huán)境、A代表交通參與物行為，則對于離散的時刻1到t被測試系統(tǒng)根據(jù)對環(huán)境的觀測o_t做出行為a_｛1:t｝=［a_1,...,a_t］；同時將系統(tǒng)的狀態(tài)改變?yōu)閟_｛1:t｝=［s_1,...,s_t］；交通參與物根據(jù)環(huán)境狀態(tài)做出干擾行為x_｛1:t｝=［x_1,...,x_t］。元素間的交互可以由下面的等式描述：

a_t=?(o_1:t),x_t=A(s_1:t),s_t+1,o_t+1=?(a_1:t,x_1:t)

則一個具體場景即一條由不同時刻環(huán)境狀態(tài)、主車行為、參與物行為組成的軌跡。本文中我們假設(shè)環(huán)境和系統(tǒng)（主車）本身不具備不確定性，則干擾車行為是唯一可以影響系統(tǒng)的變量，即環(huán)境狀態(tài)向量s可以表示成干擾行為向量x的函數(shù)，即s=f(x)。系統(tǒng)失敗可以等價于狀態(tài)s=f(x)違反了某些規(guī)定φ。此時具體場景中的軌跡可以完全由x決定。

（二）問題定義

定義損失函數(shù)c(x)滿足系統(tǒng)失敗等價于c(x) ≦? ，則一個滿足c(x) ≦?的擾動軌跡x即為造成系統(tǒng)失敗的一個反例。故可以通過優(yōu)化算法高效索引使c(x)取值最小的擾動軌跡x來尋找反例場景，即falsification任務(wù)

x*=argmin｛c(x)｝。

若想考慮尋找最容易發(fā)生的失敗場景即most-likely failure analysis任務(wù)，可以將x發(fā)生的概率（或似然/log似然函數(shù)）考慮p(x)進損失函數(shù)，例如定義

或

軌跡空間和損失函數(shù)的復(fù)雜性導(dǎo)致上述優(yōu)化問題往往存在維度高、多局部最優(yōu)解、高度非線性、不光滑等問題，進而導(dǎo)致無法通過傳統(tǒng)優(yōu)化算法求解。故能夠適應(yīng)高維空間、跳出局部最優(yōu)的全局非梯度算法更適合黑盒驗證問題。本文剩余部分將以模擬退火算法、遺傳算法以及貝葉斯優(yōu)化為例，介紹這些算法及其應(yīng)用。

03優(yōu)化算法介紹

（一）模擬退火算法

將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。模擬退火算法正是一種借鑒了這種現(xiàn)象的隨機搜索算法。其優(yōu)點是不受維度、光滑性等限制，可以高效收斂到最優(yōu)解，但是模擬退火的一個缺點是對并行計算的支撐較差。該算法的主要過程如下圖所示：

模擬退火算法分為內(nèi)外兩個循環(huán)。內(nèi)循環(huán)每次在當(dāng)前解x附近隨機生成一個新的解x*并按照如下的Metropolis準(zhǔn)則接受這個新解

其中T為本循環(huán)中的溫度。可以看出當(dāng)溫度較高時算法比較容易接受一個更差的解而當(dāng)溫度降低，系統(tǒng)會收斂到附近的最優(yōu)解。

算法內(nèi)循環(huán)為齊次算法，即每次固定指定L次，負責(zé)在當(dāng)前溫度下尋找最優(yōu)解。外循環(huán)負責(zé)降溫過程，可以按照固定的比例指數(shù)下降（基礎(chǔ)策略），也可以根據(jù)外循環(huán)次數(shù)減速下降（例如玻爾茲曼策略和柯西策略）。

（二）遺傳算法

遺傳算法是一種模仿生物自然進化過程尋求全局最優(yōu)解的方法。此方法不受解空間維度、目標(biāo)函數(shù)光滑性等限制，可以很好的支持并行計算并在一定假設(shè)下可以證明收斂到全局最優(yōu)解。其主要過程如下圖所示。

其中：

初始化：一般在解空間中隨機選取一定數(shù)量的樣本作為初代種群；

編碼：將解空間轉(zhuǎn)化為編碼空間，以便于遺傳算進行的過程，轉(zhuǎn)換后解空間中任一點可以轉(zhuǎn)化為一個染色體。常見的編碼方式包括二進制、格雷碼、實數(shù)、符號等編碼方式；

適應(yīng)度：與損失函數(shù)關(guān)聯(lián)，評價個體優(yōu)秀程度的非負函數(shù)。

選擇--根據(jù)適應(yīng)度從種群中選取比較優(yōu)秀的樣本來生產(chǎn)下一代個體的過程，常見的選擇算子包括輪盤賭、隨機遍歷抽樣、排序、錦標(biāo)賽等；

交叉：通過合并“父母”雙方染色體生成下代個體的過程。一般可采用交換父母雙方染色體中基因片段的方法，對于排列組合優(yōu)化問題可以采用匹配交叉、順序交叉等方法。

變異：在下代個體引入隨機突變來豐富種群的多樣化。一般以較小的概率隨機改變?nèi)旧w中一個或一部分基因的取值。

（三）貝葉斯優(yōu)化

貝葉斯優(yōu)化適應(yīng)黑盒函數(shù)計算復(fù)雜并缺少先驗知識的情況，同時其允許黑盒系統(tǒng)的輸出值存在獨立噪聲是前面算法不具備的。貝葉斯優(yōu)化一般采用高斯過程作為代理模型，估計黑盒系統(tǒng)在未觀測點取值的分布代替估計其取值。具體來說

1、已知黑盒系統(tǒng)在已有觀察點x?:?=[x?,x?,...x?]上取值y?:?=[y?,y?,...y?]，同時假設(shè)此系統(tǒng)取值的先驗分布為N(μ?(x?:?),Σ?(x?:?,x?:?))，其中μ?和Σ?分別為期望向量函數(shù)和核函數(shù)（協(xié)方差矩陣函數(shù)）。

2、假設(shè)黑盒系統(tǒng)在未觀測點x的取值y在x?:?條件下的后驗分布服從正態(tài)分布N(μ(x),σ2(x))，則

常常令期望向量經(jīng)常的μ?=0，而常見的核函數(shù)有高斯核（徑向基）、Matern核函數(shù)、有理二次核等，也可以對不同核函數(shù)做線性和生成新的核函數(shù)。在確定使用的代理模型（超參數(shù)設(shè)置）后，貝葉斯優(yōu)化按照下面的流程尋找黑盒系統(tǒng)的最優(yōu)值：

其中采集函數(shù)即判斷如何選取新觀測點的函數(shù)，常見的采集函數(shù)有最小化期望、最大化標(biāo)準(zhǔn)差、最小的置信區(qū)間下界、最大下降概率、最大下降期望等策略。

需要注意的是基礎(chǔ)的貝葉斯算法不適應(yīng)維度很高的情況，這時可以采用信賴域思想構(gòu)建局部代理模型并配合基于Thomption采樣的采集函數(shù)來克服高維問題。

04

數(shù)值實驗

為了方便說明，我們使用一個已知結(jié)果的顯性函數(shù)代替仿真來說明。Generalized Schwefel's Problem是一個經(jīng)典的多峰函數(shù)，使用傳統(tǒng)算法求解往往會陷入局部最優(yōu)。下面以此函數(shù)為例，驗證上面介紹算法的效果。

具體的目標(biāo)函數(shù)為

其中取值范圍x?∈[-500,500]。當(dāng)d=2時即2維圖像如下：

通過圖像可以輕松看出此函數(shù)屬于多峰函數(shù)且在原點不可導(dǎo)，其理論最優(yōu)解當(dāng)前僅當(dāng)全部x?=420.9687。在30維空間中目標(biāo)函數(shù)的最小值f*=12569.5，下面將測試不同算法的效果并與梯度算法或隨機索引對比

通過上面的圖片展示，模擬退火算法、遺傳算法、貝葉斯優(yōu)化算法均可以收斂到全局最優(yōu)解，而基于梯度的算法或隨機索引很難在可接受的時間內(nèi)尋找到全局最優(yōu)解。其中模擬退火算法收斂速度最快，單考慮到其對并行能力的欠缺，往往所需時間更長?；谥眯庞虻呢惾~斯算法收斂所需的目標(biāo)函數(shù)計算次數(shù)低于遺傳算法，但隨著觀測樣本越來越多，高斯過程回歸的擬合所花費的時間越來越長，故此方法更適合目標(biāo)函數(shù)計算成本非常高的情況。

賽目科技自主研發(fā)的空間分析工具SGOPRO內(nèi)置敏感性分析、可靠性分析及臨界魯棒性分析模塊，可對測試空間進行降維，準(zhǔn)確預(yù)估測試車輛或系統(tǒng)的失敗概率。