01引言

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

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

02模型定義

（一）符號(hào)定義

?代表被測(cè)試系統(tǒng)、?代表環(huán)境、A代表交通參與物行為，則對(duì)于離散的時(shí)刻1到t被測(cè)試系統(tǒng)根據(jù)對(duì)環(huán)境的觀測(cè)o_t做出行為a_｛1:t｝=［a_1,...,a_t］；同時(shí)將系統(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)

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

（二）問題定義

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

x*=argmin｛c(x)｝。

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

或

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

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

（一）模擬退火算法

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

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

其中T為本循環(huán)中的溫度?？梢钥闯霎?dāng)溫度較高時(shí)算法比較容易接受一個(gè)更差的解而當(dāng)溫度降低，系統(tǒng)會(huì)收斂到附近的最優(yōu)解。

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

（二）遺傳算法

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

其中：

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

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

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

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

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

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

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

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

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

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

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

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

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

04

數(shù)值實(shí)驗(yàn)

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

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

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

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

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

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