01引言

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

x*=argmin｛c(x)｝。

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

或

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

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

（一）模擬退火算法

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

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

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

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

（二）遺傳算法

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

其中：

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

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

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

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

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

變異：在下代個體引入隨機突變來豐富種群的多樣化。一般以較小的概率隨機改變染色體中一個或一部分基因的取值。

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

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

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

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

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

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

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

04

數(shù)值實驗

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

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

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

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

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

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