復(fù)雜環(huán)境下自動(dòng)駕駛系統(tǒng)軟件虛擬測試與驗(yàn)證方法

胡駿 胡天翼

（1.北京計(jì)算機(jī)應(yīng)用和仿真技術(shù)研究所，北京100854；2.瞬聯(lián)軟件科技（北京）有限公司，北京100102）

主題詞：自主系統(tǒng) 自動(dòng)駕駛 軟件測試 虛擬測試 仿真環(huán)境

0 前言

特斯拉公司CEO馬斯克在幾年前曾經(jīng)預(yù)言：“20年內(nèi)，買無人駕駛汽車會(huì)和過去買馬那么平常?！比缃瘢S著人工智能和自動(dòng)駕駛技術(shù)不斷取得突破，以及各國傳統(tǒng)、新興車企和著名互聯(lián)網(wǎng)公司紛紛重金投入研發(fā)并相繼展示推出不同級(jí)別的自動(dòng)駕駛汽車，讓人們逐漸相信這一預(yù)言在不久的將來會(huì)變成現(xiàn)實(shí)。按照SAE International對(duì)自動(dòng)駕駛技術(shù)的分級(jí)標(biāo)準(zhǔn)[1]，可分為駕駛輔（L1）、部分自動(dòng)化（L2）、有條件自動(dòng)化（L3）、高度自動(dòng)化（L4）和完全自動(dòng)化（L5）5個(gè)級(jí)別。傳統(tǒng)車企多選擇漸進(jìn)的技術(shù)路線，即先開發(fā)駕駛輔助系統(tǒng)，逐漸向高級(jí)自動(dòng)駕駛迭代的技術(shù)路線。當(dāng)前國內(nèi)多數(shù)汽車企業(yè)處于L2級(jí)到L3級(jí)自動(dòng)駕駛過渡的關(guān)鍵階段，而互聯(lián)網(wǎng)企業(yè)更多是采用激進(jìn)的技術(shù)路線，即直接開發(fā)L4級(jí)的自動(dòng)駕駛系統(tǒng)，并積極組織開展在各種路況條件下的樣車測試。

自動(dòng)駕駛系統(tǒng)是一個(gè)復(fù)雜的智能化系統(tǒng)，通過與外部環(huán)境交互處理大量輸入數(shù)據(jù)，涉及傳感器、數(shù)據(jù)融合、態(tài)勢分析、運(yùn)動(dòng)規(guī)劃和機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域的先進(jìn)技術(shù)，由此相互結(jié)合產(chǎn)生的系統(tǒng)具有能夠感知、處理并與其周圍環(huán)境進(jìn)行交互的復(fù)雜軟件系統(tǒng)，由于這類復(fù)雜智能系統(tǒng)要處理海量輸入的時(shí)間相關(guān)數(shù)據(jù)，并同時(shí)與其它系統(tǒng)進(jìn)行交互，受到自動(dòng)駕駛系統(tǒng)自身操控影響，使此類系統(tǒng)的測試與驗(yàn)證面臨極大的挑戰(zhàn)。在實(shí)際路況下的測試是必須要做的基礎(chǔ)測試驗(yàn)證工作，但通過其難以做到充分，除路試道路和環(huán)境條件受限外，需要耗費(fèi)大量人力時(shí)間成本，而且對(duì)于不同路況、天氣、相鄰靜止和運(yùn)動(dòng)實(shí)體的復(fù)雜環(huán)境，特別對(duì)一些突發(fā)狀況難以人工設(shè)置和復(fù)制，導(dǎo)致系統(tǒng)測試與驗(yàn)證不可重復(fù)。因此，必須解決在復(fù)雜環(huán)境下自動(dòng)駕駛系統(tǒng)測試充分性問題，保證事故概率在一個(gè)可接受的水平，也許通過路試能夠達(dá)到95%的可靠性，但最難的仍是從95%提高到99.9999%目標(biāo)[2]。

針對(duì)自動(dòng)駕駛這類復(fù)雜系統(tǒng)的測試驗(yàn)證，文獻(xiàn)[3]提出了一種新的高度集成的軟件測試模式，即在系統(tǒng)中新加入一個(gè)安全模塊，針對(duì)其中易于出錯(cuò)且難于測試的決策模塊開展離線仿真測試，并根據(jù)已有測試結(jié)果在線提供決策信息，以保證決策模塊輸出結(jié)果的安全性。本文基于上述思想進(jìn)一步探討了在虛擬仿真環(huán)境下開展自動(dòng)駕駛系統(tǒng)軟件測試驗(yàn)證的方法，給出了車載和實(shí)驗(yàn)室仿真測試驗(yàn)證系統(tǒng)的組成結(jié)構(gòu)和相關(guān)實(shí)現(xiàn)方法，以克服目前在實(shí)際路況下測試的局限性，在路試基礎(chǔ)上進(jìn)一步提高軟件測試充分性，從而達(dá)到提高系統(tǒng)安全性和可靠性的目的。

1 虛擬測試驗(yàn)證相關(guān)基本概念

由于在實(shí)際道路上測試自動(dòng)駕駛系統(tǒng)和軟件的不可控因素及測試本身不可重復(fù)，導(dǎo)致考慮在虛擬的仿真環(huán)境下對(duì)系統(tǒng)和軟件進(jìn)行測試。因此，人們自然會(huì)采用能夠模仿實(shí)際道路的測試方式，即基于場景的測試，并且通過該種測試可以完成在現(xiàn)實(shí)世界實(shí)際道路測試無法完成的工作。對(duì)自動(dòng)駕駛系統(tǒng)開展基于場景的測試涉及多類復(fù)雜問題，而這在常規(guī)測試中很難遇到，其中包括：

（1）場景類型：場景類型可以是靜態(tài)、動(dòng)態(tài)或混合型。靜態(tài)場景是預(yù)先設(shè)定好的，即場景中的其他動(dòng)態(tài)實(shí)體與自動(dòng)駕駛系統(tǒng)所在自主系統(tǒng)本身狀態(tài)無關(guān)，而動(dòng)態(tài)場景中的動(dòng)態(tài)實(shí)體會(huì)根據(jù)自主系統(tǒng)行為做出反應(yīng)。

（2）協(xié)同特征:可分為協(xié)同行為和非協(xié)同行為。根據(jù)測試要求可設(shè)置自主系統(tǒng)所在場景處于不允許協(xié)同行為發(fā)生的狀態(tài)，或使場景中其他交通參與者具有協(xié)同行為，這一特征對(duì)系統(tǒng)測試非常重要。

（3）場景描述有效性:對(duì)于測試過程中涉及的復(fù)雜路況及相關(guān)設(shè)施的描述要足夠細(xì)化和精確以滿足測試要求。例如：一些路況可能涉及各類停車場或鄉(xiāng)村土路，如果要測試相應(yīng)路況的自動(dòng)駕駛，需要繪制地圖并產(chǎn)生相應(yīng)場景。

（4）輸入輸出不確定性:一般軟件測試選擇確定的輸入，經(jīng)過系統(tǒng)處理后產(chǎn)生確定的輸出，據(jù)此判定測試結(jié)果的正確性。相反，對(duì)被測自主系統(tǒng)則不具備明確的輸入空間且輸出也不能明確定義。

（5）運(yùn)行時(shí)間成本:基于場景的仿真測試與實(shí)際道路測試同樣需要耗費(fèi)大量的運(yùn)行時(shí)間和成本，因?yàn)榘磮鼍暗募?xì)分通常要仿真上百萬各種相關(guān)或無關(guān)場景。當(dāng)然，在實(shí)際實(shí)施過程中會(huì)重點(diǎn)選擇更為復(fù)雜和危險(xiǎn)的情況開展測試驗(yàn)證，這方面可以參考路試結(jié)果和人們對(duì)復(fù)雜環(huán)境、危險(xiǎn)場景的已有經(jīng)驗(yàn)，以此減少測試場景的數(shù)量。

基于上述原因,為使問題描述的更清晰，需要進(jìn)一步定義自動(dòng)駕駛所在自主系統(tǒng)的狀態(tài)和其它相關(guān)術(shù)語如下：

自主系統(tǒng)狀態(tài)：自動(dòng)駕駛所在自主系統(tǒng)的狀態(tài)，包括系統(tǒng)位置、方向和其它外部所需參數(shù)及與時(shí)間周期性相關(guān)的內(nèi)部參數(shù)或初始設(shè)置信息，例如：運(yùn)動(dòng)規(guī)劃所需各類參數(shù)和信息，仿真測試過程中系統(tǒng)狀態(tài)要以適當(dāng)方式存儲(chǔ)。

態(tài)勢：態(tài)勢被定義為自主系統(tǒng)與其他所有交通參與者當(dāng)前（瞬間）的狀態(tài)，其中包括環(huán)境中的靜態(tài)部分，例如：自主系統(tǒng)所在道路和氣象條件等。

情景：態(tài)勢在一定時(shí)間間隔出現(xiàn)狀態(tài)變化的情況，將這種時(shí)間連續(xù)變化的態(tài)勢稱作情景。

場景：按照特定目的和時(shí)間間隔產(chǎn)生一系列情景形成場景。上述態(tài)勢、情景和場景的時(shí)間關(guān)系可由圖1(a)表示，圖1(b)是一個(gè)自動(dòng)駕駛汽車并入一汽車隊(duì)列的場景。在仿真測試中，場景就是自主系統(tǒng)或者說自動(dòng)駕駛系統(tǒng)測試的用例，簡單的場景由其中相關(guān)路網(wǎng)和靜態(tài)、動(dòng)態(tài)實(shí)體組成。

圖1 按照特定目的和時(shí)間間隔創(chuàng)建一系列場景

靜態(tài)和動(dòng)態(tài)實(shí)體：相對(duì)靜態(tài)實(shí)體在場景中不隨時(shí)間改變其位置或狀態(tài)，例如：路邊停放的汽車，動(dòng)態(tài)實(shí)體通常是隨時(shí)間不斷改變其位置或狀態(tài)，包括運(yùn)動(dòng)中的汽車（連續(xù)變化）和交通信號(hào)燈（離散變化）。

協(xié)同和非協(xié)同行為：在仿真測試中，動(dòng)態(tài)實(shí)體可以對(duì)其他相關(guān)實(shí)體的運(yùn)動(dòng)做出反應(yīng)則稱其為具有協(xié)同行為，例如：協(xié)同的汽車會(huì)為要加入隊(duì)列的車輛讓出位置，這類實(shí)體可以預(yù)先估計(jì)其他交通參與者的意圖并做出友好的反應(yīng)。相反，非協(xié)同行為是指動(dòng)態(tài)實(shí)體只在為避免碰撞而做出反應(yīng)而不會(huì)允許“加塞”。

態(tài)勢相似性：態(tài)勢相似是指當(dāng)自主系統(tǒng)狀態(tài)及其與所處環(huán)境中的特征元素（道路及其標(biāo)識(shí)、靜態(tài)實(shí)體等）的關(guān)系相似，其它動(dòng)態(tài)實(shí)體也有相同的狀態(tài)，所謂相似性是其特征參數(shù)和相互關(guān)系在預(yù)先設(shè)定的范圍內(nèi)。

測試驗(yàn)證空間：所有可能的態(tài)勢和由此導(dǎo)出的各種情景按相互關(guān)系組成的場景集合被稱為測試驗(yàn)證空間。顯然，對(duì)于復(fù)雜情況測試驗(yàn)證空間中各種態(tài)勢和情景組合出的場景數(shù)量是非常龐大的，但通過列舉是可以完全被覆蓋。

由上述定義可以進(jìn)一步區(qū)分靜態(tài)場景和動(dòng)態(tài)場景，即當(dāng)場景中的動(dòng)態(tài)實(shí)體是按照預(yù)先設(shè)定的運(yùn)動(dòng)軌跡運(yùn)動(dòng)，不考慮其他交通參與者（包括自主系統(tǒng)本身）的情況則屬于靜態(tài)場景，在這種情況下可認(rèn)為是對(duì)自主系統(tǒng)的開環(huán)測試模式；而動(dòng)態(tài)實(shí)體考慮其他交通參與者并采取協(xié)同或非協(xié)同行為則屬于動(dòng)態(tài)場景，這時(shí)其運(yùn)動(dòng)軌跡可以根據(jù)道路和起點(diǎn)到終點(diǎn)的情況及其他交通參與者狀態(tài)實(shí)時(shí)計(jì)算，比如采用某種結(jié)構(gòu)化的駕駛模型，上述動(dòng)態(tài)場景可被認(rèn)為是一種閉環(huán)系統(tǒng)測試模式。當(dāng)然，由此可以導(dǎo)出混合場景。

2 自動(dòng)駕駛系統(tǒng)虛擬測試組成結(jié)構(gòu)

自動(dòng)駕駛系統(tǒng)一般包括采集、感知、通訊、數(shù)據(jù)庫、人機(jī)接口（HMI）和決策模塊，以及控制、執(zhí)行機(jī)構(gòu)模塊，如圖2所示。除采集部分直接根據(jù)不同傳感器采集的數(shù)據(jù)經(jīng)處理后輸出到感知模塊外，自動(dòng)駕駛系統(tǒng)核心的決策模塊要使用其它模塊的輸出結(jié)果，然后將其決策信息發(fā)送給控制模塊，最后由執(zhí)行機(jī)構(gòu)控制執(zhí)行完成自動(dòng)駕駛?cè)蝿?wù)。

針對(duì)自動(dòng)駕駛這類復(fù)雜系統(tǒng)的測試驗(yàn)證，文獻(xiàn)[3]提出了一種新的高度集成的軟件測試模式，即在系統(tǒng)中新加入一個(gè)安全模塊（圖2中虛線部分），針對(duì)其中易于出錯(cuò)且難于測試的決策模塊開展離線仿真測試，并根據(jù)已有測試結(jié)果在線提供決策信息，以保證決策模塊輸出結(jié)果的安全性。在自動(dòng)駕駛過程中，其決策模塊可以向安全模塊詢問當(dāng)前態(tài)勢和規(guī)劃的機(jī)動(dòng)方式是否合理，后者會(huì)使用測試驗(yàn)證數(shù)據(jù)庫信息判斷當(dāng)前態(tài)勢是否經(jīng)過驗(yàn)證，且與當(dāng)前態(tài)勢臨近的后續(xù)區(qū)域的驗(yàn)證也能得到充分覆蓋，據(jù)此信息通知決策模塊相關(guān)處理操作安全或建議新的決策，即改變現(xiàn)有決策使其納入到經(jīng)過驗(yàn)證的區(qū)域部分。

本文基于這一思想進(jìn)一步提出虛擬測試與驗(yàn)證系統(tǒng)的組成結(jié)構(gòu)，分為車載仿真測試系統(tǒng)和實(shí)驗(yàn)室仿真測試開發(fā)系統(tǒng)兩部分，見圖2中替換原有安全模塊的部分，其中車載測試系統(tǒng)面向自控駕駛實(shí)際應(yīng)用，包括在線給出駕駛策略建議和離線仿真測試，其中具體功能如下：

（1）態(tài)勢搜索：包括相似度分析、態(tài)勢更新存儲(chǔ)、決策結(jié)果接收；

（2）任務(wù)調(diào)度：包括場景/模型選擇、驗(yàn)證集合生成、駕駛策略提??；

（3）仿真測試：包括仿真測試執(zhí)行、監(jiān)控和測試結(jié)果存儲(chǔ)；

（4）通訊接口：包括與HMI通訊接口和與測試開發(fā)通訊接口。

而測試開發(fā)系統(tǒng)則是面向仿真測試開發(fā)和測試與驗(yàn)證，包括場景/模型建立、仿真測試驗(yàn)證和結(jié)果分析，其中具體功能如下：

（1）場景生成：包括電子地圖、靜態(tài)/動(dòng)態(tài)實(shí)體、2D/3D場景生成和場景數(shù)據(jù)庫；

（2）模型建立：包括環(huán)境模型（道路、天氣和各類交通參與者模型）、自主系統(tǒng)模型（傳感器、自動(dòng)駕駛智能控制系統(tǒng)相關(guān)模塊、車輛動(dòng)力學(xué)和運(yùn)動(dòng)學(xué)模型及駕駛員模擬器）和模型庫；

（3）仿真測試：包括仿真測試執(zhí)行、過程監(jiān)控和測試結(jié)果記錄及測試驗(yàn)證數(shù)據(jù)庫；

（4）結(jié)果分析：包括測試結(jié)果分析、模型驗(yàn)證分析、模型調(diào)整和更新、車載測試場景/模型/測試結(jié)果更新。

測試開發(fā)系統(tǒng)是自動(dòng)駕駛系統(tǒng)設(shè)計(jì)開發(fā)和測試驗(yàn)證的重要手段，從設(shè)計(jì)階段智能控制算法的研究到后續(xù)軟件開發(fā)，可利用先期建立的全數(shù)字或軟件在回路（Safety Integration Level,SIL）仿真測試系統(tǒng)，到后期進(jìn)一步建立用于實(shí)驗(yàn)室自動(dòng)駕駛系統(tǒng)驗(yàn)證的半實(shí)物（Hardware In Loop,HIL）和車在回路（Vehicle In Loop,VIL)仿真測試系統(tǒng)均能夠發(fā)揮重要作用

圖2 自動(dòng)駕駛系統(tǒng)及虛擬測試驗(yàn)證組成結(jié)構(gòu)

該系統(tǒng)要為車載測試系統(tǒng)提供能夠滿足所需場景下的仿真模型和測試驗(yàn)證結(jié)果，同時(shí)依據(jù)車載測試系統(tǒng)實(shí)際路試產(chǎn)生的場景和測試結(jié)果，對(duì)已有模型進(jìn)行驗(yàn)證分析并更新車載測試場景/模型/測試結(jié)果。

車載測試系統(tǒng)與自動(dòng)駕駛系統(tǒng)軟硬件緊密相關(guān)，需要處理大量實(shí)時(shí)性要求很高的數(shù)據(jù)，其中包括在線接收當(dāng)前態(tài)勢并進(jìn)行相似度分析，依據(jù)對(duì)應(yīng)測試驗(yàn)證結(jié)果給出駕駛策略建議或?qū)ξ丛械膽B(tài)勢更新存儲(chǔ)；另一方面，在離線情況下對(duì)新的場景開展仿真測試驗(yàn)證，并適時(shí)采用有線或無線通訊方式與實(shí)驗(yàn)室測試開發(fā)系統(tǒng)交換信息?？梢钥闯觯瑢?shí)驗(yàn)室和車載兩套系統(tǒng)面向系統(tǒng)測試驗(yàn)證和實(shí)際應(yīng)用各有側(cè)重、相互支持，使測試驗(yàn)證的準(zhǔn)確性和充分性不斷迭代提升，以滿足自動(dòng)駕駛系統(tǒng)從L2提高到L5的測試驗(yàn)證需求。

3 自動(dòng)駕駛系統(tǒng)虛擬測試與驗(yàn)證方法

為在虛擬環(huán)境下測試自主系統(tǒng)或自動(dòng)駕駛系統(tǒng)，基于前述虛擬測試與驗(yàn)證相關(guān)基本概念需要進(jìn)一步給出系統(tǒng)測試與驗(yàn)證的基本方法，本文未涉及自主系統(tǒng)模型建立相關(guān)傳統(tǒng)方法，其相關(guān)方法介紹可參考文獻(xiàn)[4]。

3.1 基于場景的測試與驗(yàn)證空間

自主系統(tǒng)所在場景可以描述為它在所處交通路網(wǎng)中按運(yùn)動(dòng)規(guī)劃的軌跡移動(dòng)并不斷改變狀態(tài)，其它相關(guān)動(dòng)態(tài)實(shí)體也在路網(wǎng)中可以按照協(xié)同或非協(xié)同行為移動(dòng)，可以用時(shí)空狀態(tài)網(wǎng)格（Spatiotemporal State Lattices)來表征這種狀態(tài)轉(zhuǎn)換，圖中的結(jié)點(diǎn)表示（位置，時(shí)間）數(shù)據(jù)元組，其結(jié)點(diǎn)到結(jié)點(diǎn)線段表明線路和狀態(tài)變化，為簡化描述用（距離，時(shí)間）二維STSLs舉例說明，見圖3用于表征基于場景的測試驗(yàn)證空間時(shí)空狀態(tài)網(wǎng)格。圖中節(jié)點(diǎn)劃分取決于靜態(tài)場景中路網(wǎng)和靜態(tài)實(shí)體，并保證其具有足夠高精度地圖的支持，而通過結(jié)點(diǎn)的實(shí)際線路是由自主系統(tǒng)的運(yùn)動(dòng)規(guī)劃計(jì)算出或者由其他交通參與者的駕駛模型確定。圖中網(wǎng)格時(shí)間和距離步長大小要根據(jù)運(yùn)動(dòng)規(guī)劃是全局規(guī)劃或局部規(guī)劃的要求確定。

圖3 用于表征基于場景的測試驗(yàn)證空間時(shí)空狀態(tài)網(wǎng)格

特別需要說明，時(shí)空狀態(tài)網(wǎng)格分的越細(xì)精度越高，導(dǎo)出的不同線路的場景數(shù)量會(huì)急劇增加，所有可能的線路組成的場景構(gòu)成了測試驗(yàn)證空間。圖3中給出了圖1(b)自動(dòng)駕駛汽車并入汽車隊(duì)列（第2和第3輛車之間）場景的一種情況。

3.2 測試場景的參數(shù)化

通過上述對(duì)基于場景的測試驗(yàn)證空間的說明，可以進(jìn)一步對(duì)靜態(tài)和動(dòng)態(tài)場景進(jìn)行參數(shù)化，并以此構(gòu)造所需的場景測試用例，即對(duì)場景及其實(shí)體特征進(jìn)行定義，表1～3分別給出道路、天氣和靜態(tài)實(shí)體的特征屬性，表中的參數(shù)和相關(guān)數(shù)值只是作為一種參考。其中，考慮天氣因素是由于天氣效應(yīng)直接會(huì)影響到自主系統(tǒng)傳感器的測量，表中Φ、θ代表球坐標(biāo)系下的方位角和高低角，靜態(tài)實(shí)體位置由直角坐標(biāo)X、Y和指向角Φ表示。

表1 道路參數(shù)化特征屬性

表2 天氣效應(yīng)參數(shù)化特征屬性

表3 靜態(tài)實(shí)體參數(shù)化特征屬性

由于動(dòng)態(tài)實(shí)體的參數(shù)化需要考慮時(shí)間因素，因此更為復(fù)雜。這里只以圖1(b)自動(dòng)駕駛汽車并入汽車隊(duì)列（第二和第三輛車之間）場景的一種情況為例，給出相關(guān)第二輛（前車）、第三輛（后車）和自主系統(tǒng)車輛的動(dòng)態(tài)實(shí)體參數(shù)化特征屬性。

表4 動(dòng)態(tài)實(shí)體參數(shù)化特征屬性

表中的參數(shù)對(duì)應(yīng)的坐標(biāo)系是原點(diǎn)在兩條道路之間與第3輛車中心平行的位置，X軸與道路垂直的直角坐標(biāo)系，時(shí)間零點(diǎn)取在自動(dòng)駕駛汽車并入汽車隊(duì)列前的時(shí)刻。顯然，自動(dòng)駕駛汽車并入汽車隊(duì)列的其他可能性還有很多種情況，例如從第3輛或后續(xù)車并入，前述時(shí)空狀態(tài)網(wǎng)格（圖3）清晰顯示了這種動(dòng)態(tài)實(shí)體參數(shù)變化的態(tài)勢，由此將相關(guān)網(wǎng)格點(diǎn)作為動(dòng)態(tài)實(shí)體在其路徑空間-時(shí)間上的可能取值，則可得到表4不同的動(dòng)態(tài)實(shí)體參數(shù)化特征屬性。對(duì)于如何測試所述各類可能的情況或場景，則要依靠下面介紹的組合交互測試方法。

3.3 組合交互測試方法

通過上述對(duì)測試驗(yàn)證所需場景的參數(shù)化，使后續(xù)工作集中在如何選擇相應(yīng)參數(shù)并產(chǎn)生合理和更具實(shí)際應(yīng)用價(jià)值場景的方法上。組合交互測試（Combinatorial Interaction Testing）方法是針對(duì)軟件系統(tǒng)中多個(gè)因素（參數(shù)）及它們之間相互作用的情況所采取的一種科學(xué)有效的測試方法，旨在使用盡可能少的測試用例達(dá)到較高的錯(cuò)誤檢測效果。

對(duì)于一個(gè)具有k個(gè)參數(shù)的待測系統(tǒng)，如果每個(gè)參數(shù)有n個(gè)取值，則完全測試需要n的k次方個(gè)測試用例，而采用t維組合測試，即其中任意t個(gè)參數(shù)的所有取值組合至少被一個(gè)測試用例覆蓋，也稱為t維組合覆蓋測試，由此生成的測試用例數(shù)比枚舉的方法大幅度減少，實(shí)踐證明其所需要的測試用例數(shù)是按照k的對(duì)數(shù)而不是指數(shù)增長。目前，常用的組合測試方法分為兩大類，即各種貪心算法和啟發(fā)式搜索算法[5-6]，上述方法也很容易推廣到處理具有約束的條件的組合測試方法，可見參考文獻(xiàn)[7]。

在組合測試中，測試用例集合被表示成組合覆蓋矩陣或混合覆蓋矩陣，矩陣中的每一行對(duì)應(yīng)待測系統(tǒng)中的一個(gè)測試用例，每一列代表系統(tǒng)的一個(gè)參數(shù)的不同取值。貪心算法的思想是從空矩陣開始，逐行或逐列擴(kuò)展覆蓋矩陣直到所有t維組合均被覆蓋。常用IPO（In-Parameter-Order）算法就是首先按成對(duì)組合覆蓋測試構(gòu)造前兩個(gè)參數(shù)的所有組合形成一個(gè)初始矩陣，然后按矩陣水平和垂直方向進(jìn)行二維擴(kuò)展，逐步增加參數(shù)列以盡可能覆蓋更多的t維元組，如果仍有t維元組未覆蓋，則進(jìn)一步增加新的測試用例行。啟發(fā)式搜索算法屬于搜索最優(yōu)化問題，在計(jì)算效率上不如前者。

本文以場景中動(dòng)態(tài)實(shí)體的運(yùn)動(dòng)規(guī)劃為例，重點(diǎn)說明使用組合測試方法解決多車運(yùn)動(dòng)軌跡的場景生成，并結(jié)合回溯算法處理車與車之間軌跡約束問題。此處仍以圖3給出的場景說明應(yīng)用過程，假設(shè)前車已有行車路線形成組合覆蓋矩陣CA的一個(gè)結(jié)點(diǎn)（列）或稱為路徑-時(shí)間元組，在此基礎(chǔ)上通過水平擴(kuò)展增加屬于后車的結(jié)點(diǎn)，由其軌跡規(guī)劃根據(jù)前車軌跡產(chǎn)生的相關(guān)約束條件確定當(dāng)前軌跡，但從測試角度可以通過簡單的網(wǎng)格路徑搜索和模式匹配方法（Brute force method）[8]計(jì)算出所有可能的軌跡。在理想的情況下，最好前車只有一條軌跡線路，由此產(chǎn)生了約束條件區(qū)域并給后車所屬新元組規(guī)劃出相應(yīng)軌跡線路。如果無法獲得后車軌跡，則前車的軌跡需要重新計(jì)算，然后重復(fù)計(jì)算后車的軌跡線路，重復(fù)此過程直到能夠獲取最終解決方案。當(dāng)然，上述過程可以推廣到n個(gè)車輛的情況，如圖4所示。

圖4 n個(gè)動(dòng)態(tài)實(shí)體運(yùn)動(dòng)規(guī)劃的組合測試用例生成

圖4 中實(shí)心圓代表已覆蓋的軌跡，圓環(huán)代表當(dāng)前可行軌跡，而圓圈是尚未經(jīng)過測試的未覆蓋軌跡。由此可知，參數(shù)組合僅包括部分動(dòng)態(tài)實(shí)體而不是全部的情況下，即使得到了相應(yīng)軌跡線路的組合場景，回溯算法仍需要繼續(xù)尋求包括其它動(dòng)態(tài)實(shí)體的組合場景，這實(shí)際上是一個(gè)逐步由局部到全局場景的組合過程。為使動(dòng)態(tài)實(shí)體的軌跡規(guī)劃更接近于真實(shí)情況，可采用文獻(xiàn)[9]中提出的軌跡規(guī)劃預(yù)測模型，它能很好模仿人的駕駛行為產(chǎn)生的軌跡線路。

3.4 測試與驗(yàn)證自動(dòng)化

類似于車載導(dǎo)航系統(tǒng)的情況，通過實(shí)驗(yàn)室仿真測試開發(fā)系統(tǒng)可以針對(duì)實(shí)際場景開展虛擬測試與驗(yàn)證，并將測試與驗(yàn)證結(jié)果傳輸給車載測試系統(tǒng)，以便在自動(dòng)駕駛過程中提供安全決策信息。對(duì)于行車過程中車載測試系統(tǒng)當(dāng)前未經(jīng)過測試與驗(yàn)證覆蓋的部分區(qū)域和態(tài)勢，通常情況下會(huì)自動(dòng)保存并及時(shí)傳輸給實(shí)驗(yàn)室開展測試與驗(yàn)證，然后再由其統(tǒng)一發(fā)布更新車載測試系統(tǒng)信息。在理想情況下，上述未經(jīng)測試與驗(yàn)證部分區(qū)域態(tài)勢可以直接由本車車載測試系統(tǒng)利用已有加載的仿真測試資源（典型道路、場景和相關(guān)仿真模型）在空閑時(shí)自動(dòng)開展測試與驗(yàn)證工作，所謂“空閑”是指車輛未在行駛過程中但仍處在加電狀態(tài)，例如：車輛處在停駛的充電過程中。實(shí)際上，類似仿真測試與驗(yàn)證需要耗費(fèi)大量時(shí)間和計(jì)算資源，如果所有自動(dòng)駕駛車輛均能夠按此執(zhí)行，并將結(jié)果自動(dòng)傳輸給實(shí)驗(yàn)室測試開發(fā)系統(tǒng)進(jìn)一步綜合和測試與驗(yàn)證并發(fā)布，那么這樣一種自動(dòng)化處理方式是極為合理，而且利用前述的虛擬測試與驗(yàn)證方法可以實(shí)現(xiàn)其自動(dòng)化過程。

特別指出，自動(dòng)駕駛系統(tǒng)實(shí)際路試的結(jié)果對(duì)虛擬測試與驗(yàn)證也是非常重要，通過其驗(yàn)證數(shù)據(jù)可以對(duì)典型道路、場景和相關(guān)仿真模型進(jìn)行驗(yàn)證和更新，以彌補(bǔ)虛擬測試與驗(yàn)證由于簡化對(duì)結(jié)果帶來的影響。同樣，實(shí)際路試結(jié)果也是測試與驗(yàn)證空間中被覆蓋的組成部分，兩種測試與驗(yàn)證方式缺一不可且相輔相成[10]。隨著自動(dòng)駕駛級(jí)別的不斷提高（L2～L5），虛擬測試與驗(yàn)證結(jié)果在測試與驗(yàn)證空間被覆蓋的比重將占有絕對(duì)的優(yōu)勢。

4 結(jié)論

本文探討了針對(duì)復(fù)雜環(huán)境下自動(dòng)駕駛系統(tǒng)和軟件的虛擬測試驗(yàn)證方法，給出了車載和實(shí)驗(yàn)室仿真測試驗(yàn)證系統(tǒng)的組成結(jié)構(gòu)和相關(guān)實(shí)現(xiàn)方法，為進(jìn)一步基于實(shí)際系統(tǒng)開展研究和系統(tǒng)開發(fā)打下了良好基礎(chǔ)。對(duì)于建立實(shí)驗(yàn)室條件下的虛擬測試驗(yàn)證系統(tǒng)，目前應(yīng)該已具備成熟的基礎(chǔ)條件；而對(duì)于車載測試系統(tǒng)必須要結(jié)合實(shí)際自動(dòng)駕駛系統(tǒng)及其軟硬件資源開展設(shè)計(jì)開發(fā)工作，并進(jìn)一步解決其中涉及的海量態(tài)勢信息的存儲(chǔ)、態(tài)勢相似性判別、大規(guī)?；旌蠄鼍暗臏y試驗(yàn)證方法及其自動(dòng)化等。相信在未來，隨著自動(dòng)駕駛系統(tǒng)逐步進(jìn)入實(shí)用階段，車載虛擬測試系統(tǒng)也可以像當(dāng)今的車載導(dǎo)航一樣應(yīng)運(yùn)而生并得到普及。