01引言

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

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

02模型定義

（一）符號定義

?代表被測試系統、?代表環境、A代表交通參與物行為，則對于離散的時刻1到t被測試系統根據對環境的觀測o_t做出行為a_｛1:t｝=［a_1,...,a_t］；同時將系統的狀態改變為s_｛1:t｝=［s_1,...,s_t］；交通參與物根據環境狀態做出干擾行為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)

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

（二）問題定義

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

x*=argmin｛c(x)｝。

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

或

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

03優化算法介紹

（一）模擬退火算法

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

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

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

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

（二）遺傳算法

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

其中：

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

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

適應度：與損失函數關聯，評價個體優秀程度的非負函數。

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

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

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

（三）貝葉斯優化

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

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

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

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

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

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

04

數值實驗

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

具體的目標函數為

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

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

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

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