張曉彤 王嘉誠 何景濤 陳仕韜 鄭南寧

ZHANG Xiaotong1, WANG Jiacheng1, HE Jingtao1, CHEN Shitao1, ZHENG Nanning1

自動(dòng)駕駛系統(tǒng)是指一種可在部分或完全脫離人類駕駛員的情況下實(shí)現(xiàn)車輛安全行駛的自主系統(tǒng)，主要包括環(huán)境感知、路徑規(guī)劃、行為決策、導(dǎo)航控制等主要技術(shù)模塊[1].車輛使用多種車載傳感器獲取車輛自身狀態(tài)和所處環(huán)境信息，并基于傳感器技術(shù)、信號(hào)處理技術(shù)、通訊技術(shù)、自動(dòng)控制技術(shù)、計(jì)算機(jī)技術(shù)、人工智能技術(shù)等多領(lǐng)域技術(shù)對(duì)數(shù)據(jù)做出分析和判斷，最終依據(jù)環(huán)境和自身意圖完成類人的自主決策控制.

由于自動(dòng)駕駛和輔助駕駛技術(shù)不斷發(fā)展和進(jìn)步，汽車工業(yè)正迎來一次智能化浪潮.以車道偏離預(yù)警、車道保持、全速域自適應(yīng)巡航等為代表的一系列輔助駕駛功能，在乘用車上逐漸普及,并被越來越多的消費(fèi)者接受.以輔助駕駛技術(shù)為主的漸進(jìn)式自動(dòng)駕駛路線開始與變革式的完全自動(dòng)駕駛路線在人工智能賽道上出現(xiàn)交匯[2].得益于傳感器、通信等相關(guān)技術(shù)的進(jìn)步，自動(dòng)駕駛領(lǐng)域迎來快速發(fā)展的機(jī)遇，汽車的智能化應(yīng)用也在部分場(chǎng)景展現(xiàn)出更多的可能性.現(xiàn)階段自動(dòng)駕駛技術(shù)大規(guī)模應(yīng)用的主要阻礙是“不確定性”挑戰(zhàn)，特別是動(dòng)態(tài)交通環(huán)境帶來的不確定性幾乎會(huì)影響到相關(guān)算法的每個(gè)階段.

路徑規(guī)劃算法作為銜接多個(gè)技術(shù)模塊的重要環(huán)節(jié)，存在的不確定性問題尤為突出.然而目前大部分自動(dòng)駕駛運(yùn)動(dòng)規(guī)劃的研究工作依然基于確定性假設(shè)，難以處理更動(dòng)態(tài)的不確定性環(huán)境.確定性規(guī)劃雖然有精密的物理模型和動(dòng)力學(xué)模型為其提供良好的先驗(yàn)知識(shí)，但通常僅適用于特定、動(dòng)態(tài)程度較低的場(chǎng)景，在復(fù)雜場(chǎng)景下缺乏實(shí)際應(yīng)用的意義.自動(dòng)駕駛車輛在復(fù)雜擁堵的交通場(chǎng)景下，需要有效地與交通流交互，這要求主體車輛必須預(yù)測(cè)自身行為對(duì)其它車輛行為的影響，得到在未來一段時(shí)間內(nèi)安全的軌跡，即進(jìn)行具有交互性與預(yù)測(cè)性的規(guī)劃.車輛之間的相互作用是一種復(fù)雜和耦合的動(dòng)態(tài)交通狀況，局部偏差會(huì)在車輛間進(jìn)行傳播，極易導(dǎo)致不確定性的快速積累[3].其他交通參與者行為具備靈活性和隨機(jī)性，并有一定的集體特性，目前對(duì)其軌跡預(yù)測(cè)的可靠性仍有待提升.

自動(dòng)駕駛汽車需要具備更通用性的方法建模交通環(huán)境，并實(shí)時(shí)響應(yīng)難以預(yù)測(cè)的狀況，從而保證即使在復(fù)雜的城市情況下，車輛也能做出及時(shí)、安全的響應(yīng).不完整的環(huán)境表示和不確定性會(huì)影響運(yùn)動(dòng)規(guī)劃，因此仍有兩個(gè)因素需要進(jìn)一步深入研究：不確定性環(huán)境的表征和該環(huán)境下的規(guī)劃.本文將不確定性下的自動(dòng)駕駛運(yùn)動(dòng)規(guī)劃算法歸納為兩類.1)部分可觀測(cè)馬爾可夫決策過程(Partially Observable Markov Decision Process，POMDP)，基于當(dāng)前置信狀態(tài)，計(jì)算使未來折扣獎(jiǎng)勵(lì)最大的策略，在車道變更、路口車流、行人交互場(chǎng)景內(nèi)均有良好應(yīng)用.2)概率占用柵格圖(Probability Occupancy Grid Map，POGM)，使用概率表征對(duì)應(yīng)柵格上的占用情況，衡量車流動(dòng)態(tài)變化的可能性，良好表征不確定性情況.本文從問題建模、求解方法、實(shí)際應(yīng)用等方面深入分析這兩種方法，并展望不確定性問題解決方法的未來發(fā)展方向，分析仍存在的挑戰(zhàn).

1 自動(dòng)駕駛系統(tǒng)結(jié)構(gòu)及其不確定性分析

自動(dòng)駕駛系統(tǒng)由環(huán)境感知定位、規(guī)劃決策、執(zhí)行控制子模塊構(gòu)成，結(jié)構(gòu)如圖1所示.環(huán)境感知基于車上的多傳感器系統(tǒng)，從里程計(jì)、慣性測(cè)量單元、雷達(dá)、相機(jī)等傳感器中獲得感知信息并融合，以此表征環(huán)境.多傳感器系統(tǒng)可為后續(xù)的航跡估算和位置估計(jì)提供車輛的運(yùn)動(dòng)信息.建圖結(jié)果作為環(huán)境表示，定位結(jié)果與地圖建立聯(lián)系.在獲得車輛位姿、周圍環(huán)境后，決策規(guī)劃生成多條采樣軌跡并最終選擇安全可行的一條軌跡，計(jì)算得到可行速度和加速度.執(zhí)行控制根據(jù)規(guī)劃得出的軌跡和車輛狀態(tài)進(jìn)行自主駕駛.

圖1 自動(dòng)駕駛系統(tǒng)結(jié)構(gòu)圖

城市環(huán)境中不確定性的因素對(duì)自動(dòng)駕駛系統(tǒng)中的各個(gè)模塊都會(huì)產(chǎn)生影響[4].在定位模塊中，天氣和GPS靈敏度等不確定性因素都會(huì)導(dǎo)致車輛自身位置在世界系下出現(xiàn)觀察誤差.在感知模塊中，傳感器本身固有的不確定性和環(huán)境噪聲都會(huì)導(dǎo)致障礙物位置檢測(cè)不準(zhǔn)確甚至誤檢漏檢，引入碰撞風(fēng)險(xiǎn).感知與定位會(huì)直接影響環(huán)境地圖的構(gòu)建與精度.雷達(dá)同樣存在不確定性，如雷達(dá)單次掃描的結(jié)果可能出現(xiàn)噪聲引起的空間上的誤檢，而兩幀間的信息缺失來源于其固定存在的掃描時(shí)間.通信系統(tǒng)帶來的不確定性會(huì)導(dǎo)致主體車輛與周圍交通參與者及道路智能交通設(shè)施之間的交互具有滯后性和隨機(jī)性，難以精確獲取其他交通參與者的意圖.即使上述不確定性可通過技術(shù)性手段進(jìn)行良好處理，但控制模塊仍受制于運(yùn)動(dòng)模型本身受到微小擾動(dòng)的影響，對(duì)噪聲敏感，難以極短時(shí)間內(nèi)達(dá)到預(yù)期的加速度和速度.

鑒于上述部分模塊存在的不確定性，自動(dòng)駕駛系統(tǒng)中起到承上啟下作用的規(guī)劃模塊需要具備處理上游模塊引入的不確定性的能力，并且規(guī)劃過程中的不確定性與其他交通參與者聯(lián)系最密切，與車輛自身的安全性密不可分.如果不能正確處理好規(guī)劃中的不確定性，可能會(huì)造成違反交通規(guī)則、碰撞等結(jié)果.在面臨突發(fā)危險(xiǎn)時(shí)，規(guī)劃能及時(shí)響應(yīng)，給出一條安全可行的軌跡或及時(shí)的預(yù)警信號(hào)，是保證駕駛員和車輛安全的一道防線.因此，處理規(guī)劃問題中的不確定性，是自動(dòng)駕駛發(fā)展的重要一環(huán).規(guī)劃要能處理其他交通參與者交互引入的不確定性,即在靜態(tài)環(huán)境的基礎(chǔ)上處理動(dòng)態(tài)對(duì)象的時(shí)間、空間、速度、行為等方面的不確定性.

不確定性存在于自動(dòng)駕駛規(guī)劃應(yīng)用的各類場(chǎng)景，下面將從結(jié)構(gòu)化環(huán)境與非結(jié)構(gòu)化環(huán)境中介紹其影響.

結(jié)構(gòu)化環(huán)境下的無保護(hù)左轉(zhuǎn)是自動(dòng)駕駛中一個(gè)亟待解決的難題.即使對(duì)于人類駕駛員而言，左轉(zhuǎn)導(dǎo)致的事故率也是右轉(zhuǎn)導(dǎo)致的事故率的十倍.對(duì)于自動(dòng)駕駛車輛來說，路口缺乏信號(hào)、難以預(yù)測(cè)其它車的意圖、缺乏其它車輛的轉(zhuǎn)向燈信號(hào)等問題導(dǎo)致左轉(zhuǎn)過程的高度不確定性與交互性[5]，具體示意圖如圖2所示.

在非結(jié)構(gòu)化環(huán)境中，多車場(chǎng)景的泊車問題同樣具有極大的挑戰(zhàn)性.隨著城市規(guī)模增大、車輛密度變高，2022年全國汽車保有量達(dá)到3億輛.高峰時(shí)段車輛密度高，鄰近車位停車不規(guī)范，停車場(chǎng)光線暗、空間狹小，由于多車進(jìn)入車位的意圖不明確，難以根據(jù)車輛當(dāng)前速度給出準(zhǔn)確的未來軌跡判斷.并且，其它車輛的運(yùn)動(dòng)多樣化，在低速情況下可能會(huì)出現(xiàn)急剎車、倒車等復(fù)雜運(yùn)動(dòng)軌跡.這些情況都會(huì)導(dǎo)致車輛交互問題復(fù)雜、難以預(yù)測(cè).同樣地，車流具備高度連貫性、集體性，駕駛員駕駛習(xí)慣不盡相同，自身車輛與其它車輛的交互過程中對(duì)其他駕駛員的駕駛習(xí)慣不夠了解，在產(chǎn)生交互時(shí)難以準(zhǔn)確預(yù)測(cè)其他交通參與者的行為變化.確定性規(guī)劃在上述復(fù)雜場(chǎng)景中得出的路徑可能會(huì)隨著場(chǎng)景的動(dòng)態(tài)變化而變得不安全.

但是不確定性規(guī)劃可通過濾波器預(yù)測(cè)其他交通參與者狀態(tài)，使用概率表征可行空間，克服其不確定性引入的碰撞風(fēng)險(xiǎn)，在復(fù)雜環(huán)境中給出盡可能安全可靠的路徑.

2 部分可觀測(cè)馬爾可夫決策過程

部分可觀測(cè)的馬爾可夫決策過程(POMDP)為不確定性環(huán)境中自動(dòng)駕駛的決策和運(yùn)動(dòng)規(guī)劃提供一種經(jīng)典有效的建模方式.POMDP基于當(dāng)前置信狀態(tài)，計(jì)算使未來折扣獎(jiǎng)勵(lì)最大的策略，在特定場(chǎng)景下表現(xiàn)穩(wěn)定，能有效處理非機(jī)動(dòng)車、行人等意圖難以預(yù)測(cè)的交通參與者參與的場(chǎng)景，在變革式自動(dòng)駕駛系統(tǒng)中應(yīng)用廣泛.

然而，隨著問題規(guī)模的增大，POMDP規(guī)劃問題的觀測(cè)空間、狀態(tài)空間，甚至動(dòng)作空間不斷膨脹，計(jì)算復(fù)雜度呈指數(shù)級(jí)增長，限制POMDP的求解，稱為維度災(zāi)難[6-7].同時(shí)，迭代深度的增加導(dǎo)致搜索樹的廣度呈指數(shù)增加，稱為歷史災(zāi)難[8].目前主流的POMDP求解算法通過采樣、模擬等方式降低求解的復(fù)雜度，以便在可接受的時(shí)間內(nèi)獲得較準(zhǔn)確的近似解.

2.1 理論介紹

POMDP為解決自動(dòng)駕駛車輛在不確定性環(huán)境中規(guī)劃決策問題的建模提供一個(gè)數(shù)學(xué)框架.POMDP通常用一個(gè)八元組表示〈S,A,Ω,T,O,R,γ,b0〉.S表示狀態(tài)空間.A表示動(dòng)作空間.Ω表示觀測(cè)空間.T表示狀態(tài)轉(zhuǎn)移模型，

T(s,a,s′)∶=P(s′|s,a)，

表示在狀態(tài)s(s∈S)下執(zhí)行動(dòng)作為a(a∈A)，得到下一時(shí)刻的狀態(tài)為s′(s′∈S)的概率.在自動(dòng)駕駛系統(tǒng)中，下一時(shí)刻的狀態(tài)s′通常還需要考慮交通參與者的運(yùn)動(dòng)學(xué)模型.O表示觀測(cè)模型，

O(o′,s′,a)∶=P(o′|s′,a)，

表示采取動(dòng)作a、系統(tǒng)狀態(tài)轉(zhuǎn)移為s′時(shí)，獲得觀測(cè)為o′(o′∈Ω)的概率.值得注意的是，觀測(cè)信息是POMDP在馬爾可夫決策過程(Markov Decision Pro-cess，MDP)的基礎(chǔ)上新增的信息量，目的是通過觀測(cè)信息預(yù)測(cè)環(huán)境的隱藏狀態(tài).考慮到環(huán)境的不確定性，決策主體無法通過傳感器準(zhǔn)確獲取全部的系統(tǒng)狀態(tài)，這種部分可觀測(cè)性也是POMDP的特點(diǎn)之一.因此，決策主體需要利用現(xiàn)有的不完全觀測(cè)量推測(cè)真實(shí)的環(huán)境狀態(tài)量.R表示獎(jiǎng)勵(lì)模型，R(s,a)表示在狀態(tài)s采取動(dòng)作a獲得的即時(shí)獎(jiǎng)勵(lì).人們一般根據(jù)如下3個(gè)指標(biāo)對(duì)自動(dòng)駕駛的運(yùn)動(dòng)規(guī)劃效果進(jìn)行衡量：安全性、有效性、舒適性[9-11].安全性主要取決于自動(dòng)駕駛車輛與動(dòng)態(tài)障礙物、靜態(tài)障礙物是否保持在安全距離內(nèi).安全是自動(dòng)駕駛的第一要?jiǎng)?wù)，因此POMDP對(duì)非安全性行為賦予巨大懲罰.有效性體現(xiàn)運(yùn)動(dòng)規(guī)劃的實(shí)際效果，由自動(dòng)駕駛車輛到達(dá)目標(biāo)位置耗時(shí)或車輛在行駛過程中的平均速度決定.有效性是自動(dòng)駕駛運(yùn)動(dòng)規(guī)劃追求的目標(biāo)，因此POMDP對(duì)違背有效性的自動(dòng)駕駛行為進(jìn)行較大的懲罰.舒適性通常由軌跡的平均曲率及自動(dòng)駕駛車輛的減速次數(shù)決定.通過懲罰違反舒適性準(zhǔn)則的行為，自動(dòng)駕駛車輛在保證安全有效行駛的前提下可為乘客提供良好的乘坐體驗(yàn).γ表示折扣系數(shù)，決定未來決策對(duì)當(dāng)前狀態(tài)的影響程度.一般情況下γ<1，表示隨著決策過程的不斷迭代，未來決策收益對(duì)當(dāng)前決策的影響逐漸減小.b0表示初始信念狀態(tài)，即初始時(shí)刻環(huán)境中不確定性狀態(tài)的概率分布.

考慮到環(huán)境狀態(tài)的部分可觀測(cè)性，POMDP引出信念狀態(tài)的概念，用于表示當(dāng)前時(shí)刻環(huán)境各種可能狀態(tài)的概率分布.自動(dòng)駕駛系統(tǒng)中的不確定性可大體分為兩類：1)系統(tǒng)硬件自身帶來的不確定性，包括感知和控制的不確定性；2)其他交通參與者行為意圖的不確定性.針對(duì)第1種不確定性，POMDP通常引入高斯噪聲進(jìn)行不確定性建模.針對(duì)第2種不確定性，POMDP通常將不同交通參與者的行為意圖建模成不可觀測(cè)的離散狀態(tài)，如運(yùn)動(dòng)軌跡、速度、加速度、道路保持、換道等，并對(duì)每種不可觀測(cè)狀態(tài)賦予概率，模擬意圖行為的不確定性.

將問題建模成POMDP的最終目的是獲取在當(dāng)前狀態(tài)下的最優(yōu)策略π*.π*可表示為一個(gè)動(dòng)作序列(a1,a2,…，an)，其中n表示所需的決策次數(shù).策略的優(yōu)劣取決于動(dòng)作序列獲得的未來折扣收益，貝爾曼最優(yōu)性準(zhǔn)則常被用于對(duì)當(dāng)前信念狀態(tài)的最優(yōu)值進(jìn)行更新.

2.2 求解方法

2.2.1 離線算法

離線算法在離線情況下完成模型求解，與決策主體的在線決策過程是分離的.離線求解算法可計(jì)算決策體每種信念狀態(tài)下的最優(yōu)策略.在決策主體進(jìn)行決策時(shí)，只需要根據(jù)當(dāng)前信念狀態(tài)查詢得到最優(yōu)動(dòng)作并執(zhí)行即可.

離線算法的優(yōu)勢(shì)在于最優(yōu)策略的計(jì)算不占用在線決策的時(shí)間，可保證決策的實(shí)時(shí)性，但該算法需要處理大范圍信念狀態(tài)空間，求解時(shí)間較長，實(shí)用性較低.為了處理這種低效的精確求解問題，有學(xué)者提出可加快運(yùn)算速度的近似方法.基于點(diǎn)的值迭代算法是典型的離線近似算法之一，基本思想是只考慮部分可達(dá)的信念狀態(tài)以減小信念狀態(tài)空間的大小，從而減小運(yùn)算量.考慮到最優(yōu)值函數(shù)是分段線性的，因此部分信念狀態(tài)通常對(duì)整體的信念狀態(tài)空間具有較好的模擬[12].在基于點(diǎn)的值迭代的思想基礎(chǔ)上學(xué)者們提出一系列相關(guān)的算法，如PBVI(Point-Based Value Iteration)[8]、Perseus[13]、HSVI(Heuristic Search Value Iteration)[14]等.

2.2.2 在線算法

離線算法只能針對(duì)靜態(tài)的環(huán)境模型進(jìn)行處理，而對(duì)環(huán)境中的動(dòng)態(tài)因素缺乏處理能力.

不同于離線算法計(jì)算每種信念狀態(tài)下的最優(yōu)策略，在線算法只考慮當(dāng)前所處的信念狀態(tài)及從當(dāng)前信念狀態(tài)可達(dá)的其它信念狀態(tài).在線算法分為兩個(gè)階段：規(guī)劃階段(策略計(jì)算)和執(zhí)行階段.整個(gè)決策過程中規(guī)劃與執(zhí)行交替進(jìn)行.

規(guī)劃階段分為搜索樹構(gòu)建和回溯兩步.POMDP構(gòu)建的搜索樹又稱與或樹，由與節(jié)點(diǎn)(AND-Nodes)，或節(jié)點(diǎn)(OR-Nodes)構(gòu)成，一個(gè)典型的與或樹如圖3所示.以當(dāng)前信念狀態(tài)b0為根節(jié)點(diǎn)，基于根節(jié)點(diǎn)信念狀態(tài)遍歷所有動(dòng)作at，得到相應(yīng)的OR-Nodes.基于每個(gè)OR-Nodes，考慮所有可能的觀測(cè)ot，并更新信念狀態(tài)b，獲取新的信念狀態(tài)節(jié)點(diǎn).以此類推，直到達(dá)到事先設(shè)定的搜索深度，搜索樹構(gòu)建完成.構(gòu)建完成后利用貝爾曼最優(yōu)性原則從葉子節(jié)點(diǎn)開始對(duì)搜索樹進(jìn)行回溯，對(duì)回溯路徑上各個(gè)信念狀態(tài)節(jié)點(diǎn)的最優(yōu)值進(jìn)行更新.葉子節(jié)點(diǎn)的最優(yōu)值可采用離線算法[15-17]或蒙特卡洛模擬(Monte-Carlo Simulation，MCS)的方式進(jìn)行計(jì)算[18-20].

圖3 POMDP搜索樹示意圖[9]

盡管相比離線算法，一般的在線算法計(jì)算量已大幅降低，并且對(duì)動(dòng)態(tài)環(huán)境中的決策也有較好效果，但依然需要處理龐大的動(dòng)作空間及觀測(cè)空間，影響實(shí)時(shí)性.研究者們通常關(guān)注近似算法，在保證一定的決策準(zhǔn)確度的前提下降低運(yùn)算量.

在線近似算法主要分為3類：分支與邊界裁剪算法[21]、啟發(fā)式算法[22-24]、基于蒙特卡洛模擬的算法.

分支與邊界裁剪算法的基本思想在于通過對(duì)比不同節(jié)點(diǎn)最優(yōu)值函數(shù)的下界和上界，將已知次優(yōu)的樹分支進(jìn)行裁剪，避免進(jìn)行不必要的拓展.首先，采用離線算法計(jì)算葉子節(jié)點(diǎn)值的上界(MDP[25]，QMDP-net[26]，F(xiàn)IB(Fast Informed Bound)[27])與下界[28].然后，利用貝爾曼最優(yōu)性準(zhǔn)則，通過反向回溯更新搜索樹內(nèi)部節(jié)點(diǎn)邊界值.

在進(jìn)行樹搜索時(shí)，倘若在當(dāng)前信念狀態(tài)b下執(zhí)行動(dòng)作a獲得的值函數(shù)下界大于執(zhí)行動(dòng)作a′時(shí)獲得的值函數(shù)的上界，那么可認(rèn)為在信念狀態(tài)b下動(dòng)作a′是次優(yōu)的，因此可將動(dòng)作a′及其分支進(jìn)行裁剪，降低搜索樹的復(fù)雜度，提高樹搜索效率.

不同于分支與邊界搜索算法，啟發(fā)式算法通過啟發(fā)式信息選取最具有潛力的分支進(jìn)行搜索，實(shí)現(xiàn)通過擴(kuò)展更少的節(jié)點(diǎn)以獲取一個(gè)更好的決策的目的.在啟發(fā)式算法中，每個(gè)葉子節(jié)點(diǎn)存儲(chǔ)一個(gè)啟發(fā)值，該啟發(fā)值表示該葉子節(jié)點(diǎn)被擴(kuò)展的價(jià)值.與此同時(shí)，搜索樹的內(nèi)部節(jié)點(diǎn)存儲(chǔ)當(dāng)前樹分支內(nèi)具有最優(yōu)啟發(fā)值節(jié)點(diǎn)的索引及最優(yōu)值.在每次迭代過程中選取啟發(fā)值最大的節(jié)點(diǎn)進(jìn)行擴(kuò)展(一般擴(kuò)展一層)，再采用動(dòng)態(tài)規(guī)劃算法，對(duì)拓展節(jié)點(diǎn)的祖先節(jié)點(diǎn)進(jìn)行啟發(fā)值更新.

基于此基本框架，學(xué)者們相繼提出各種啟發(fā)式算法，如Satia and Lave[29]、BI-POMDP(Bounded, Incremental POMDP)[30]、AEMS(Anytime Error Minimi-zation Search)[31]、HSVI等.這些算法主要的不同之處在于啟發(fā)函數(shù)的設(shè)計(jì).啟發(fā)函數(shù)設(shè)計(jì)的合理性影響樹搜索的效率，從而進(jìn)一步影響整個(gè)算法的求解速度.

一般的求解算法通常需要對(duì)POMDP問題進(jìn)行準(zhǔn)確建模，通過建立的模型對(duì)信念狀態(tài)進(jìn)行前向模擬以計(jì)算未來折扣獎(jiǎng)勵(lì).然而，建模實(shí)際問題極具挑戰(zhàn)性，模型的準(zhǔn)確性對(duì)決策性能影響較大.研究者們尋求一種更簡(jiǎn)單的方法評(píng)估當(dāng)前策略的優(yōu)劣，即蒙特卡洛方法，使用大量隨機(jī)事件逼近真實(shí)情況.在蒙特卡洛模擬的過程中，系統(tǒng)的狀態(tài)轉(zhuǎn)移模型、觀測(cè)模型及獎(jiǎng)勵(lì)模型被統(tǒng)一建模成黑盒.

盡管蒙特卡洛模擬可近似估計(jì)某個(gè)狀態(tài)的好壞，但大規(guī)模的模擬過程需要消耗大量時(shí)間，因此模擬所有狀態(tài)不具備可行性.蒙特卡洛樹搜索選擇最具有潛力與價(jià)值的節(jié)點(diǎn)進(jìn)行蒙特卡洛模擬，從而使搜索樹在較好的策略上進(jìn)行擴(kuò)展.蒙特卡洛樹搜索算法主要包含4步：選擇、擴(kuò)展、仿真、反向傳播.部分可觀測(cè)的蒙特卡洛規(guī)劃(Partially Observable Monte-Carlo Planning，POMCP)交替進(jìn)行蒙特卡洛樹搜索和信念狀態(tài)更新的過程.

POMCP通過對(duì)信念狀態(tài)空間的采樣避免POMDP的維度災(zāi)難，通過黑盒進(jìn)行狀態(tài)轉(zhuǎn)移和觀測(cè)模擬以避免POMDP的歷史災(zāi)難.然而，POMCP有時(shí)表現(xiàn)過于貪婪，并且在最壞情況下的表現(xiàn)極其糟糕[32].

DESPOT(Determined Sparse Partially Observable Tree)在POMCP上進(jìn)行進(jìn)一步的改進(jìn)與優(yōu)化.與PO-MCP類似，DESPOT通過對(duì)狀態(tài)的采樣及前向仿真模擬避免決策過程中的維度災(zāi)難與歷史災(zāi)難.DES-POT將信念狀態(tài)采樣數(shù)限定在一個(gè)較小的值，并將采樣獲取的狀態(tài)稱為場(chǎng)景(Scenarios).

前向模擬生成的軌跡數(shù)主要受到動(dòng)作空間大小的影響，與觀測(cè)空間無關(guān).DESPOT限制采樣場(chǎng)景數(shù)，在較小的動(dòng)作空間內(nèi)生成稀疏搜索樹.在稀疏搜索樹構(gòu)建完成后，與POMCP類似，DESPOT循環(huán)進(jìn)行樹搜索、節(jié)點(diǎn)擴(kuò)展與仿真，最后再向根節(jié)點(diǎn)回溯.

離線算法與在線算法的優(yōu)缺點(diǎn)對(duì)比如表1所示.

表1 離線方法與在線方法優(yōu)缺點(diǎn)對(duì)比

2.2.3 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)能讓智能體在與環(huán)境的交互中自主學(xué)習(xí)，通過最大化獎(jiǎng)勵(lì)的方式讓智能體學(xué)會(huì)如何決策.Mnih等[33]使用的深度強(qiáng)化學(xué)習(xí)技術(shù)DQN(DeepQ-Network)結(jié)合深度學(xué)習(xí)極強(qiáng)的感知能力和強(qiáng)化學(xué)習(xí)自主學(xué)習(xí)、決策的能力，更廣泛地應(yīng)用于如運(yùn)動(dòng)規(guī)劃、決策控制等多個(gè)領(lǐng)域.在處理不確定性問題的迭代過程中，強(qiáng)化學(xué)習(xí)的目標(biāo)就是使Agent通過最大化累計(jì)獎(jiǎng)勵(lì)rt學(xué)習(xí)最優(yōu)化策略Π*，獲得觀測(cè)到最優(yōu)動(dòng)作的映射.

大多數(shù)強(qiáng)化學(xué)習(xí)問題都假設(shè)環(huán)境的狀態(tài)在每個(gè)時(shí)間步長下都是完全可觀測(cè)的，針對(duì)MDP描述的問題，強(qiáng)化學(xué)習(xí)已有很多經(jīng)典算法.例如：1)基于價(jià)值(Value-Base)的算法，Dueling DQN[34]、DoubleQ-Learning[35]、Rainbow[36]等;2)基于策略梯度(Policy-Base)的算法，Actor-Critic[37]、DDPG(Deep Deter-ministic Policy Gradient)[38]等，都取得較優(yōu)效果.

但是對(duì)于現(xiàn)實(shí)環(huán)境來說，智能體一般由其搭載的傳感器感知環(huán)境，在每個(gè)狀態(tài)st下，智能體由其傳感器獲得觀測(cè)ot.然而，由于傳感器的誤差、遮擋、噪聲等不確定性因素，觀測(cè)ot無法代替狀態(tài)st給出使智能體獲得做出決策的所有環(huán)境信息.在這種情況下，應(yīng)考慮POMDP.POMDP決策過程如圖4所示.POMDP是在MDP上增加觀測(cè)空間Ω、觀測(cè)模型O和信念b，讓智能體通過不完全觀測(cè)的數(shù)據(jù)ot推測(cè)真實(shí)狀態(tài)st.

圖4 POMDP決策過程示意圖

POMDP的主要挑戰(zhàn)在于如何通過不完全的觀測(cè)推測(cè)信念狀態(tài)，有效的信念狀態(tài)是獲取POMDP最優(yōu)策略的基礎(chǔ).

為了減小信念狀態(tài)與真實(shí)狀態(tài)之間的誤差，目前有兩種主流的做法：1)通過循環(huán)神經(jīng)網(wǎng)絡(luò)(Recur-rent Neural Network，RNN)記錄歷史觀測(cè)和動(dòng)作，為智能體提供更多的信息，此方法隱式地包含對(duì)信念狀態(tài)的推理，不僅依靠當(dāng)前觀測(cè)選取動(dòng)作，可有效處理部分POMDP問題.但是這種隱式包含給RNN帶來沉重負(fù)擔(dān)，可解釋性較弱，難以在復(fù)雜的任務(wù)中獲取有效的最優(yōu)策略.2)在強(qiáng)化學(xué)習(xí)架構(gòu)中引入模型以推理信念狀態(tài)，使POMDP問題可轉(zhuǎn)換為MDP問題進(jìn)行訓(xùn)練，從而獲得最優(yōu)策略Π*.

在強(qiáng)化學(xué)習(xí)中引入信念狀態(tài)作為輸入的一部分的思想在文獻(xiàn)[39]中被提出，并且深度信念Q網(wǎng)絡(luò)(Deep Belief-StateQ-Networks, DBQN)也被提出.DBQN大致沿用DQN的總體構(gòu)架，通過Q-Learning的方式更新網(wǎng)絡(luò)權(quán)重參數(shù)，損失函數(shù)為：

DBQN網(wǎng)絡(luò)結(jié)構(gòu)如圖5所示.網(wǎng)絡(luò)的輸入層由智能體的信念狀態(tài)向量和完全可觀測(cè)向量構(gòu)成，而以往的DQN輸入由MDP中的狀態(tài)表述，DBQN通過在輸入中添加信念狀態(tài)以尋找最優(yōu)策略,這使DBQN具有可有效應(yīng)對(duì)POMDP場(chǎng)景的能力，并且在Tiger與Rock Sample兩款游戲中都獲得優(yōu)于DQN的效果.

圖5 DBQN網(wǎng)絡(luò)結(jié)構(gòu)圖[39]

DBQN的不足之處在于每次在執(zhí)行動(dòng)作之前，當(dāng)前的信念狀態(tài)需要被計(jì)算后輸入網(wǎng)絡(luò)中，而當(dāng)前的信念狀態(tài)又沒有具體的推理模型，因此DBQN只能滿足有模型(T，O已知)的POMDP問題.

Hausknecht等[40]將POMDP問題中的歷史觀測(cè)信息由RNN記錄下來，提出DRQN(Deep RecurrentQ-Network)，適用于無模型的POMDP場(chǎng)景.DRQN網(wǎng)絡(luò)結(jié)構(gòu)如圖6所示.DRQN最小限度修改原DQN網(wǎng)絡(luò)結(jié)構(gòu)，僅僅將DQN中第1個(gè)全連接層換成相同大小的長短期記憶網(wǎng)絡(luò)(Long Short-Term Memory，LSTM)層[41].相比RNN，LSTM結(jié)構(gòu)儲(chǔ)存更多的歷史信息，使網(wǎng)絡(luò)隱式推理更準(zhǔn)確的信念狀態(tài).

圖6 DRQN網(wǎng)絡(luò)結(jié)構(gòu)圖[40]

繼承DRQN的思想，F(xiàn)oerster等[42]提出DDRQN(Deep Distributed RecurrentQ-Network).Zhu等[43]提出ADRQN(Action-Specific Deep RecurrentQ-Net-work).DDRQN和ADRQN都認(rèn)為循環(huán)網(wǎng)絡(luò)中記錄的信息不應(yīng)僅包含歷史的觀測(cè)(ot,ot-1,ot-2…)，也應(yīng)包含歷史的動(dòng)作信息(at,at-1,at-2，…)，這樣有助于更好地推斷當(dāng)前的信念狀態(tài).不同之處在于DDRQN分別輸入歷史動(dòng)作序列和歷史觀測(cè)序列進(jìn)行解耦，而ADQRN將歷史觀測(cè)和歷史動(dòng)作組合成觀測(cè)-動(dòng)作對(duì)輸入，體現(xiàn)時(shí)序條件下歷史觀測(cè)與歷史動(dòng)作的相關(guān)信息.提供歷史動(dòng)作信息的DDRQN和ADRQN更有助于智能體學(xué)習(xí)最優(yōu)策略Π*.實(shí)驗(yàn)證實(shí)，在Pong、Frostbite、Asteroids等游戲中，提供歷史動(dòng)作信息的DDRQN和ADRQN表現(xiàn)更優(yōu)，驗(yàn)證在RNN中包含更多的有效歷史信息有助于智能體在POMDP場(chǎng)景中更好地學(xué)習(xí)最優(yōu)策略Π*.

第2種方法根據(jù)具體模型推理更新信念狀態(tài)，更具有可解釋性，但是總體性能較強(qiáng)依賴于推理模型的性能，整體結(jié)構(gòu)更復(fù)雜.Igl 等[44]提出DVRL(Deep Variational Reinforcement Learning)，基于AESMC(Auto-Encoding Sequential Monte Carlo)[45]的ELBO(Evidence Lower Bound)近似方法將歸納偏差合并到策略網(wǎng)絡(luò)結(jié)構(gòu)中.整體框架使用Actor-Critic架構(gòu)，利用學(xué)習(xí)的模型推斷信念狀態(tài),應(yīng)對(duì)POMDP環(huán)境.信念更新函數(shù)為：

實(shí)驗(yàn)表明，DVRL優(yōu)于DRQN、ADRQN等基于RNN表述信念狀態(tài)的方法.此外，Wang等[46]提出DualSMC(Dual Sequential Monte Carlo)，將POMDP濾波和規(guī)劃問題轉(zhuǎn)換為兩個(gè)密切相關(guān)的序列蒙特卡羅過程(Sequential Monte Carlo，SMC)，通過蒙特卡洛濾波直接規(guī)劃一個(gè)近似的信念以明確表示信念分布，并且按策略訓(xùn)練的方法訓(xùn)練信念狀態(tài)表述濾波器.Singh 等[47]提出SWB(Structured World Belief)，通過SMC推斷為在POMDP環(huán)境中提供以對(duì)象為中心的結(jié)構(gòu)化世界信念，幫助智能體學(xué)習(xí)最優(yōu)策略.Chen等[48]提出FORBES(Flow-Based Recurrent Belief State Model)，將標(biāo)準(zhǔn)化流[49]納入變分推理過程，學(xué)習(xí)POMDP的一般連續(xù)信念狀態(tài)，應(yīng)對(duì)POMDP環(huán)境，又將FORBES應(yīng)用于POMDP強(qiáng)化學(xué)習(xí)模型，采用Actor-Critic架構(gòu)學(xué)習(xí)最優(yōu)策略，使用POMDP提供的信念狀態(tài)進(jìn)行最優(yōu)策略學(xué)習(xí)，避免類似RNN的觀測(cè)模型整合，并且在DeepMind的視覺-運(yùn)動(dòng)控制任務(wù)[50]中取得較優(yōu)效果.

2.3 不確定性下的應(yīng)用場(chǎng)景

POMDP為自動(dòng)駕駛環(huán)境中不確定性因素的建模提供一種科學(xué)有效的方式.隨著相關(guān)求解算法的不斷發(fā)展與優(yōu)化，POMDP在自動(dòng)駕駛汽車的運(yùn)動(dòng)規(guī)劃中發(fā)揮越來越重要的作用，應(yīng)用于多個(gè)場(chǎng)景.

2.3.1 行人交互環(huán)境

行人作為城市道路環(huán)境的重要組成部分，具有隨機(jī)性和集體特征，給運(yùn)動(dòng)規(guī)劃場(chǎng)景帶來大量的不確定性.

人群環(huán)境的運(yùn)動(dòng)規(guī)劃問題需要處理的主要不確定因素是行人的意圖.行人意圖決定下一時(shí)刻行人的運(yùn)動(dòng)軌跡，這對(duì)車輛運(yùn)動(dòng)規(guī)劃來說十分重要.一般情況下，人群中運(yùn)動(dòng)規(guī)劃問題主要被處理為局部動(dòng)態(tài)避障問題，如社會(huì)力(Social Force)算法[51-53].該算法構(gòu)建目標(biāo)點(diǎn)對(duì)車輛的引力及行人對(duì)車輛的斥力，通過虛擬力的方式引導(dǎo)車輛運(yùn)動(dòng).然而這種方法容易陷入局部最優(yōu)，并且在密集的人群中很難規(guī)劃一條完全無碰撞的路徑，容易導(dǎo)致穿梭在人群中的車輛頻繁剎停，難以實(shí)現(xiàn)安全并快速的通行.

Bai等[9]設(shè)計(jì)一個(gè)兩層的架構(gòu)，處理人群環(huán)境中自動(dòng)駕駛的決策與運(yùn)動(dòng)規(guī)劃問題.上層采用Hybrid A*[54]進(jìn)行路徑規(guī)劃，并采用純追蹤算法[55]計(jì)算車的前輪轉(zhuǎn)角.底層采用POMDP進(jìn)行速度規(guī)劃，輸出車輛的加速度.POMDP中將行人的意圖作為不可觀測(cè)量，建模為一個(gè)目標(biāo)位置，并采用貝葉斯規(guī)則對(duì)該信念狀態(tài)進(jìn)行更新.最后，采用DESPOT進(jìn)行模型求解，整個(gè)決策過程以一個(gè)接近實(shí)時(shí)的頻率運(yùn)行.實(shí)驗(yàn)表明，該方案在簡(jiǎn)單特定的行人運(yùn)動(dòng)場(chǎng)景中具有不錯(cuò)效果.

文獻(xiàn)[9]方法在人群中的運(yùn)動(dòng)規(guī)劃結(jié)果如圖7所示.(a)中行人意圖穿越車輛預(yù)測(cè)路線，車輛減速.(b)中盡管在車輛預(yù)測(cè)路線附近依然有行人，但是行人意圖往遠(yuǎn)離車輛預(yù)測(cè)路線的方向運(yùn)動(dòng)，此時(shí)車輛加速.相比傳統(tǒng)的反應(yīng)式避障方法，這種考慮行人不確定性的POMDP具有更小的危險(xiǎn)性(Risk)、通過時(shí)間(Time)和總加速度(Total Acceleration)，即在安全性、有效性及舒適性三個(gè)指標(biāo)上都具有較大的優(yōu)勢(shì).但在行人狀態(tài)轉(zhuǎn)移模型構(gòu)建過程中，模型僅簡(jiǎn)單假設(shè)行人向目標(biāo)位置沿直線運(yùn)動(dòng)，導(dǎo)致難以處理行人的復(fù)雜運(yùn)動(dòng)場(chǎng)景.

(a)行人軌跡與車輛軌跡相交

Luo等[10]提出PORCA(Pedestrian Optimal Reci-procal Collision Avoidance)，用于預(yù)測(cè)行人的運(yùn)動(dòng)軌跡.PORCA引入更復(fù)雜的行人運(yùn)動(dòng)模型，根據(jù)行人意圖及行人之間、行人與車輛之間的交互，對(duì)行人短期運(yùn)動(dòng)軌跡進(jìn)行準(zhǔn)確預(yù)測(cè).然而，兩層處理架構(gòu)解耦前輪轉(zhuǎn)角與車輛加速度控制，不利于模擬真實(shí)環(huán)境中的復(fù)雜駕駛行為.

Cai等[11]提出LeTS-Drive(Driving in a Crowd by Learning from Tree Search)，結(jié)合POMDP與深度學(xué)習(xí)，實(shí)現(xiàn)自動(dòng)駕駛車輛在密集人群中的運(yùn)動(dòng)與導(dǎo)航.為了模擬復(fù)雜駕駛行為，LeTS-Drive構(gòu)建一個(gè)二維聯(lián)合動(dòng)作空間，同時(shí)考慮車的前輪轉(zhuǎn)角與加速度.在搜索樹構(gòu)建過程中，基于HyP-DESPOT(Hybrid Parallel DESPOT)[56]，LeTS-Drive使用預(yù)先訓(xùn)練好的策略與值網(wǎng)絡(luò)引導(dǎo)動(dòng)作的選擇，進(jìn)一步加速搜索樹構(gòu)建效率.然而，神經(jīng)網(wǎng)絡(luò)的復(fù)雜性影響在線搜索的效率，因此需要更有效的策略和價(jià)值函數(shù)表示.當(dāng)網(wǎng)絡(luò)學(xué)習(xí)的策略難以推廣到不同的地圖與主體車輛行為上時(shí)，需要進(jìn)一步拓展模型的訓(xùn)練環(huán)境.

2.3.2 路口車輛交互環(huán)境

城市道路無交通信號(hào)燈的交叉路口是自動(dòng)駕駛中一個(gè)典型的不確定性場(chǎng)景.考慮到?jīng)]有交通信號(hào)燈的規(guī)則約束，路口中其它車輛的行為變得復(fù)雜、難以預(yù)測(cè)，這對(duì)交通路口的安全且快速通行造成很大的挑戰(zhàn)，具體如圖8所示.

圖8 無交通信號(hào)燈的交叉路口下的運(yùn)動(dòng)規(guī)劃

Bouton等[57]使用POMDP對(duì)通過無交通信號(hào)燈路口的自動(dòng)駕駛車輛進(jìn)行速度規(guī)劃.路口中其它車輛的不確定性行為被建模成兩類：恒定速度(Con-stant Velocity)與恒定加速度(Constant Acceleration).模型采用IMM(Interacting Multiple Model)進(jìn)行信念狀態(tài)更新，采用POMCP進(jìn)行求解.將POMCP的求解結(jié)果分別與一種簡(jiǎn)單的啟發(fā)式策略TTC(Time to Collision)[57]和一種隨機(jī)策略進(jìn)行對(duì)比，對(duì)比結(jié)果可知，自動(dòng)駕駛車輛在無交通信號(hào)燈的十字路口進(jìn)行左轉(zhuǎn)或右轉(zhuǎn)時(shí)，POMCP在保證極高的通過率(Success Rate)和極低的碰撞率(Collision Rate)的前提下,具有最短的通過時(shí)間(Time to Cross).

由于交叉路口結(jié)構(gòu)的特殊性，車輛的視線常受到路口中其它車輛的遮擋，從而產(chǎn)生視野盲區(qū)，如圖9所示.

圖9 視野受限的路口車輛

視野盲區(qū)的潛在障礙物存在嚴(yán)重的安全隱患，是一個(gè)不容忽視的因素.Lin等[58]基于POMDP對(duì)存在遮擋的交叉路口的決策過程進(jìn)行建模，將其它車輛不同運(yùn)動(dòng)軌跡的概率分布作為信念狀態(tài)，采用貝葉斯規(guī)則進(jìn)行信念狀態(tài)追蹤.同時(shí)，為了應(yīng)對(duì)視野盲區(qū)存在的潛在風(fēng)險(xiǎn)，引入虛擬障礙物的概念，模擬在盲區(qū)中可能出現(xiàn)的其它車輛，大幅提升決策的安全性與可靠性.類似地，Hubmann等[59]利用信念狀態(tài)，低維表示可能被遮擋的隱藏車輛，并包含這些車輛的未知路線及在這些路線上的概率，最終構(gòu)成一個(gè)其它車輛的可達(dá)區(qū)域集合.

Pruekprasert 等[60]提出基于意圖感知的無交通信號(hào)路口的自動(dòng)駕駛，交通參與者的意圖劃分為兩類：縱向意圖(剎車與停止)和橫向意圖(預(yù)測(cè)軌跡集合).模型采用動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)(Dynamic Bayesian Network，DBN)進(jìn)行意圖追蹤，并采用DESPOT進(jìn)行模型求解.實(shí)驗(yàn)表明此模型使車輛在路口具有較好的通過性，同時(shí)可應(yīng)對(duì)路口中有車輛、行人等多種異構(gòu)智能體的情形.

2.3.3 車道變更環(huán)境

車道變更往往發(fā)生在前方車輛速度較低，但占據(jù)整個(gè)車道，影響自身車輛行駛的情況下.該場(chǎng)景中的不確定性因素主要體現(xiàn)在周圍車輛意圖的不確定性.周圍車輛意圖極大影響車道變更的可行性與安全性.

Meghjani等[61]基于POMDP，提出基于道路上下文信息及意圖理解的運(yùn)動(dòng)規(guī)劃算法，算法中信念狀態(tài)由車道保持、左換道和右換道這3種意圖的概率分布表示，并訓(xùn)練一個(gè)LSTM網(wǎng)絡(luò)，幫助信念狀態(tài)的更新.被超車輛的未來軌跡根據(jù)其歷史軌跡、道路上下文信息及車輛意圖進(jìn)行預(yù)測(cè).算法采用DESP-OT進(jìn)行求解，輸出當(dāng)前最優(yōu)的換道動(dòng)作.超車示意圖如圖10所示，(a)中主體車輛試圖左換道超越前方慢速車輛，(b)中前方車輛左換道以阻止主體車輛超車，(c)中主體車輛察覺左側(cè)車道阻塞且前方無車輛，試圖回到中間車道繼續(xù)高速行駛，(d)中背景車輛未發(fā)現(xiàn)主體車道的超車意向，回到中間車道慢速行駛，主體車輛成功左換道超車.在換道場(chǎng)景中，考慮其他交通參與者意圖的POMDP換道成功率達(dá)到100%，同時(shí)在換道過程中耗時(shí)最短.

圖10 超車示意圖

Ulbrich 等[62]基于自身所處車道及左右2側(cè)車道中所有車輛運(yùn)動(dòng)的動(dòng)態(tài)表示，利用2個(gè)信號(hào)處理網(wǎng)絡(luò)分別判斷車道是否具備變更可能的網(wǎng)絡(luò)和判斷變更車道是否有益，輸出到POMDP中進(jìn)行決策.研究者將所有隨機(jī)變量聚合為特定感興趣區(qū)域的一個(gè)度量，使用模糊邏輯規(guī)則描述過程.Mentasti 等[63]在MDP中嵌入連續(xù)狀態(tài)分層貝葉斯轉(zhuǎn)移模型.通過求解MDP，可自動(dòng)導(dǎo)出雙車道公路場(chǎng)景中自動(dòng)駕駛汽車與多輛其它汽車的決策.另一種方法是采用混合可觀測(cè)的馬爾可夫決策過程對(duì)超車場(chǎng)景進(jìn)行建模，考慮測(cè)量和行動(dòng)的不確定性，優(yōu)化超車決策，為雙向道路超車問題提供解決方案.

在未來的研究中，需要評(píng)估更多情況，如跟車行為.在多車道上行駛時(shí)，加速/減速動(dòng)作需要擴(kuò)展為變道動(dòng)作.由于系統(tǒng)使用低級(jí)狀態(tài)空間，因此不需要為這些任務(wù)定義新的模型或符號(hào)狀態(tài).可針對(duì)所有可控道路用戶的集中POMDP規(guī)劃和聯(lián)合行動(dòng),實(shí)現(xiàn)多輛自動(dòng)駕駛車輛的協(xié)同駕駛.在部分可觀測(cè)的不確定性環(huán)境中運(yùn)行的自主代理通常需要同時(shí)優(yōu)化預(yù)期性能和限制違反安全約束的風(fēng)險(xiǎn).這兩個(gè)問題可同時(shí)建模為CC-POMDP(Chance-Constrained POMDP)[64]，約束條件尤為重要.SSC(Unified Spatio-Temporal Semantic Corridor)[65]將約束分為硬約束和可松弛約束，硬約束用于保證安全性，如碰撞距離，可松弛約束用于保證舒適性和類人程度，如換道所需要的時(shí)間.對(duì)于人類駕駛員，面臨交通規(guī)則與危險(xiǎn)環(huán)境的沖突，通過直覺推理可做出規(guī)避風(fēng)險(xiǎn)的判斷，而對(duì)于自動(dòng)駕駛車輛，對(duì)于多個(gè)相悖的約束，往往會(huì)導(dǎo)致缺乏可行空間，在無法進(jìn)行規(guī)劃的情況下即使急停也難以保證安全，尤其是在上述車流密集的復(fù)雜環(huán)境內(nèi).因此，適當(dāng)?shù)厮沙诓糠旨s束可有效應(yīng)對(duì)極端不確定性環(huán)境內(nèi)的安全性問題.

3 概率占用柵格圖

概率占用柵格圖(POGM)常用于表示從感知得到的環(huán)境信息和描述可行空間.利用感知信息表征真實(shí)世界的過程會(huì)引入不確定性，該過程可建模為估計(jì)理論問題.POGM本身能提供明確編碼的空間信息和相關(guān)不確定性，導(dǎo)出確定性體素模型或更高級(jí)別的幾何表示[66].環(huán)境表示的適用性直接影響規(guī)劃獲取相關(guān)信息的難易程度，POGM包含的不確定性信息容易處理，因此自動(dòng)駕駛規(guī)劃任務(wù)在占用柵格圖框架內(nèi)可高效完成.占用柵格圖具有多種表達(dá)形式，常見的有二值化表達(dá)形式，一個(gè)網(wǎng)格僅有占用(Occupied)與空閑(Free)兩種狀態(tài).這種表示會(huì)損失大量信息，不利于不確定性環(huán)境下的規(guī)劃決策過程.

3.1 理論基礎(chǔ)

概率占用柵格圖作為一種環(huán)境表征方法，表示形式如圖11所示.雖然POGM從柵格地圖發(fā)展而來，但是比僅有占用/空閑兩種狀態(tài)的柵格地圖，概率的表示形式更適用于碰撞風(fēng)險(xiǎn)的衡量.因此，POGM具備環(huán)境表征抽象性、碰撞風(fēng)險(xiǎn)更優(yōu)性的特征.多傳感器融合是當(dāng)今環(huán)境感知的主流形式，模型獲取不同維度、不同角度的感知信息以表示環(huán)境.多傳感器采集的數(shù)據(jù)融合后形成一種統(tǒng)一的緊湊型表征模型，用于表達(dá)當(dāng)前的行駛環(huán)境[67-68].

圖11 POGM表示形式

基于貝葉斯濾波的占用柵格模型與其相關(guān)的改進(jìn)模型是一種典型的緊湊型表征模型.Elfes等[69]將傳感器信息解釋為柵格單元值以構(gòu)建占用柵格.當(dāng)將傳感器數(shù)據(jù)解釋為占用信息時(shí)，不可避免地引入未知部分和誤差導(dǎo)致的不確定性.未知部分的產(chǎn)生是由于靠前障礙物的遮擋，導(dǎo)致障礙物后的區(qū)域不能被感知到，誤差來自噪聲和不精確的姿態(tài)估計(jì)[70].

POGM包含對(duì)應(yīng)柵格的占用率.對(duì)于一個(gè)柵格，s=1表示對(duì)應(yīng)柵格為占用狀態(tài)，否則，s=0表示空閑狀態(tài)，p(s=1)和p(s=0)分別表示該柵格處于占用或空閑狀態(tài)的概率，二者之和為1.因此，可用一個(gè)值同時(shí)表示出二者，即兩者比值表示該點(diǎn)狀態(tài)：

為了更方便的表示，對(duì)于每個(gè)點(diǎn)，一旦得到一個(gè)測(cè)量值(Measurement)z，需要利用貝葉斯法則進(jìn)行一次狀態(tài)更新.更新前狀態(tài)為Odd(s)，更新后

更新過程如下：

以此分離測(cè)量值，前者稱為測(cè)量值的模型，記為lomeas.

這兩種表示均為定值.這種表示使用概率的形式，描述感知過程中的不確定性，可更好地解決連續(xù)時(shí)刻內(nèi)出現(xiàn)的沖突結(jié)果，更新規(guī)則簡(jiǎn)單.在這種描述下，lofree越大，looccu越小，則該柵格為空閑狀態(tài)的置信度越高.

3.2 求解方法

構(gòu)建好POGM后，在其上的求解方法同常規(guī)柵格圖類似，可分為4類：基于采樣的方法、基于搜索的方法、插值曲線法、數(shù)值優(yōu)化方法.基于采樣的方法是在空間內(nèi)采樣得到可行路徑點(diǎn).基于搜索的方法是對(duì)網(wǎng)格節(jié)點(diǎn)進(jìn)行搜索，得到可行的節(jié)點(diǎn)連接方式.插值曲線法在已知路徑錨點(diǎn)間以螺線、多項(xiàng)式曲線的軌跡形式進(jìn)行平滑連接，得到符合車輛行駛動(dòng)力學(xué)約束和運(yùn)動(dòng)學(xué)約束的平滑曲線.數(shù)值優(yōu)化方法設(shè)定合適的目標(biāo)函數(shù)，近似/精確求解該優(yōu)化問題，得到目標(biāo)軌跡.Tsardoulias等[71]提出若干指標(biāo)，對(duì)比后得出空間采樣方法最適合POGM.

基于采樣的方法以快速擴(kuò)展隨機(jī)樹(Rapidly-Exploring Random Trees，RRT)及其各類優(yōu)化變種方法為典型代表.自RRT提出后，常應(yīng)用于解決非凸高維空間的快速搜索、靜態(tài)障礙物和差分運(yùn)動(dòng)約束問題，并且作為局部規(guī)劃時(shí)可考慮更大范圍內(nèi)的障礙物.

RRT通常認(rèn)為在可行空間內(nèi)，所有節(jié)點(diǎn)可達(dá)，所以在全部節(jié)點(diǎn)中進(jìn)行隨機(jī)采樣.基于樣條的RRT*(Optimal RRT)通過B樣條曲線擴(kuò)展隨機(jī)樹[72]，在可實(shí)現(xiàn)有約束情況下進(jìn)行規(guī)劃，同時(shí)也可在樹擴(kuò)展階段檢查碰撞，判斷角加速度是否可達(dá)，其中擴(kuò)展階段檢查碰撞的范圍大小rball隨著節(jié)點(diǎn)數(shù)量的增加而縮小.具體算法步驟如下所示.

算法基于樣條的RRT*算法[72]

輸入RRT樹，初始節(jié)點(diǎn)

輸出符合漸進(jìn)最優(yōu)性的路徑

初始化RRT樹

Whilexnew與終點(diǎn)距離大于距離限制 do

Whilexnew的鄰近節(jié)點(diǎn)非空 do

在設(shè)定的環(huán)境內(nèi)部產(chǎn)生隨機(jī)點(diǎn)xnew

建立隨機(jī)點(diǎn)的周圍的最近鄰節(jié)點(diǎn)xnearest

End while

將延伸節(jié)點(diǎn)加入xnew

Ifxnew與xnearest無碰撞 then

xnew周圍半徑為rball的邊界內(nèi)的節(jié)點(diǎn)存入Xnear

Forxnear∈Xneardo

xnew=xnearest

cmin=cost(xnearest)+cost(xnew,xnearest)

If(xnew,xnearest)無碰撞且可行且

cost(xnear)+cost(xnew,xnear)

xmin=xnear

cmin=cost(xnear)+cost(xnew,xnear)

End if

End for

Forxnear∈Xneardo

If(xnew,xnear)安全可行且

cost(xnew)+cost(xnew,xnear)

xparent=parent(xnear)

End if

End for

End if

Ifxnew與終點(diǎn)距離小于距離限制 then

return RRT樹

End if

End while

Reachability Guided RRT[73]可消除不準(zhǔn)確的距離對(duì)RRT探索能力的影響,計(jì)算樹中節(jié)點(diǎn)的可達(dá)集，當(dāng)采樣點(diǎn)到節(jié)點(diǎn)的距離大于采樣點(diǎn)到該節(jié)點(diǎn)可達(dá)集的距離時(shí)，該節(jié)點(diǎn)才有可能被選中進(jìn)行擴(kuò)展.

RRT還有許多其它優(yōu)化，如Anytime[74]，整體思想是將樹的生長方向引導(dǎo)到障礙物稀疏的區(qū)域，仍是在空間中進(jìn)行采樣.Risk-RRT(Risk RRT)[75]利用動(dòng)態(tài)障礙物的未來軌跡預(yù)測(cè)，并將其以高斯分布的形式表征在柵格圖上，將預(yù)測(cè)與規(guī)劃進(jìn)行集成，即先得到障礙物的預(yù)測(cè)軌跡，并在一定半徑內(nèi)根據(jù)高斯分布得到對(duì)應(yīng)柵格的占用率，以碰撞風(fēng)險(xiǎn)為導(dǎo)向，結(jié)合規(guī)劃方法與動(dòng)態(tài)環(huán)境的感知和預(yù)測(cè)的概率碰撞風(fēng)險(xiǎn)函數(shù)，即在擴(kuò)展結(jié)點(diǎn)時(shí)考慮Risk是否符合滿足閾值.考慮到動(dòng)態(tài)障礙物間的相互作用，在對(duì)應(yīng)柵格上不能直接進(jìn)行概率上的疊加，而又難以獲取聯(lián)合概率密度分布.Bi-Risk-RRT(Bidirectional Risk-RRT)[76]在第一階段，兩棵樹相互生長.在第二階段，反向樹生成啟發(fā)式軌跡，正向樹根據(jù)啟發(fā)式采樣分布增長.Bi-Risk-RRT比Risk-RRT運(yùn)算速度更快，敏感性更低，最大線速度對(duì)軌跡長度變化的相關(guān)程度也更低.而且，啟發(fā)式方法比嘗試求解TBVP(Two-Point Boun-dary Value Problem)的樹-樹連接方法更魯棒.

與之不同的是，動(dòng)態(tài)窗口法(Dynamic Window Approach, DWA)在速度空間內(nèi)采樣.DWA中采樣多組速度(v,w)，并模擬這些速度在一定時(shí)間內(nèi)的運(yùn)動(dòng)軌跡.通過評(píng)價(jià)函數(shù)對(duì)這些軌跡進(jìn)行評(píng)價(jià)，選取最優(yōu)軌跡對(duì)應(yīng)的(v,w)驅(qū)動(dòng)車輛運(yùn)動(dòng).在非結(jié)構(gòu)化環(huán)境中，通常采取DWA與全局規(guī)劃(如A*)結(jié)合，應(yīng)對(duì)自動(dòng)泊車的復(fù)雜場(chǎng)景.

除了常見的城市道路交通環(huán)境，自動(dòng)駕駛還可應(yīng)用于取代危險(xiǎn)環(huán)境中工作的駕駛?cè)藛T，如災(zāi)后的救援車輛.援建車輛需要在不確定性高、障礙物多、情況復(fù)雜的環(huán)境中導(dǎo)航到指定點(diǎn)停車.Yang等[77]提出使用A*與DWA的單步停車策略，即車頭向內(nèi)停入車位，和兩步停車策略，即先到達(dá)某個(gè)中間節(jié)點(diǎn)，再通過倒車的方式，車頭向外停入車位.具體如圖12所示.

(a)單步停車 (b)多步停車

Pan等[78]提出D2WA(″Dynamic″ DWA),可應(yīng)對(duì)動(dòng)態(tài)的不確定性環(huán)境，與動(dòng)態(tài)障礙物相關(guān)的代價(jià)函數(shù)的權(quán)重根據(jù)不同的障礙物狀態(tài)進(jìn)行動(dòng)態(tài)調(diào)整，可避免不必要的避碰，提高運(yùn)動(dòng)規(guī)劃者對(duì)動(dòng)態(tài)障礙物的可預(yù)測(cè)性.

上述的基于采樣的方法往往難以在有限迭代中得到最優(yōu)路徑，而基于搜索的方法發(fā)展已較成熟，具有解析完備性和解析最優(yōu)性.Koenig等[79]提出一種增量算法，用于推廣具有任意邊插入、邊刪除和邊長度變化的圖中的最短路徑問題.Stentz等[80]提出Dstar，在部分已知的環(huán)境中實(shí)現(xiàn)最佳、有效的重新規(guī)劃，當(dāng)檢測(cè)到地圖中的變化時(shí)，不是重新計(jì)算整個(gè)地圖的最佳路徑，而是檢查一組減少的單元，并逐步更新到最佳路徑.這里的增量利用以前計(jì)劃的結(jié)果生成新的規(guī)劃結(jié)果，可加快速度.然而，在可用時(shí)間內(nèi)找到絕對(duì)最優(yōu)的路徑是不可能的.

由于占用柵格圖維數(shù)較低，所以網(wǎng)格節(jié)點(diǎn)數(shù)較多，運(yùn)算效率較低.預(yù)處理占用柵格圖使其變得更稀疏，可有效改善這種情況.研究者們通常采用k-PRM[81]和PRM*[82]進(jìn)行降采樣.這兩種方法都是通過節(jié)點(diǎn)自身的鄰居關(guān)系降低節(jié)點(diǎn)數(shù)目.k-PRM僅取決于自身所在節(jié)點(diǎn)和設(shè)置的視窗大小，PRM*雖然選擇半徑會(huì)發(fā)生改變，但其對(duì)不同的環(huán)境取決于總的點(diǎn)數(shù)，不具有場(chǎng)景間的區(qū)分度.3D重建后的相機(jī)在弱光條件下容易產(chǎn)生偽影.對(duì)于這種情況，障礙物會(huì)出現(xiàn)位置上的不確定性，容易導(dǎo)致多檢、誤檢.這種感知導(dǎo)致的不確定性環(huán)境表征給障礙物碰撞風(fēng)險(xiǎn)的衡量帶來極大的不確定性[83].

Saroya等[84]提出GNG(Growing Neural Gas)，擁有比PRM*更快的速度，利用同源特征影響采樣過程，使其朝著難以通過的區(qū)域增長，確保通過狹窄通道的路線圖的連通性.GNG引入的抽樣方法之一是通過POGM直接得到映射概率分布，另一抽樣方法根據(jù)同源特征位置創(chuàng)建高斯混合分布以得到映射概率分布.

Ok等[85]提出Voronoi不確定性場(chǎng)，以便在不確定性情況下進(jìn)行路徑規(guī)劃.考慮環(huán)境中觀察的障礙物的不確定性，并根據(jù)它們與自身的距離及其位置不確定性分配排斥力.來自Voronoi節(jié)點(diǎn)的吸引力和來自不確定性偏向勢(shì)場(chǎng)的排斥力形成Voronoi不確定性場(chǎng)(Voronoi Uncertainty Fields, VUF).

McLeod等[86]基于RAMP(Real-Time Adaptive Motion Planning)框架，隨機(jī)初始化一組軌跡，使用多目標(biāo)評(píng)價(jià)函數(shù)確定最佳軌跡.當(dāng)智能體沿著軌跡移動(dòng)時(shí)，同時(shí)更新當(dāng)前位置到終點(diǎn)的軌跡集，并從中選擇最優(yōu)的軌跡，以此適應(yīng)新感知的行駛環(huán)境的變化.RAMP框架并行處理軌跡集的更新、代價(jià)函數(shù)的最優(yōu)計(jì)算、控制智能體沿軌跡移動(dòng)三個(gè)過程，使用的代價(jià)函數(shù)合并真實(shí)數(shù)據(jù)和概率數(shù)據(jù)，評(píng)價(jià)智能體在環(huán)境中未見區(qū)域的軌跡，提高實(shí)時(shí)執(zhí)行的能力.

因?yàn)镻OGM本身的概率特性，因此也常用機(jī)會(huì)約束規(guī)劃處理此類問題.機(jī)會(huì)約束用于衡量障礙物碰撞概率，求解方法在運(yùn)動(dòng)規(guī)劃中通常轉(zhuǎn)化為確定性進(jìn)行求解.

3.3 具體應(yīng)用

POGM的構(gòu)建與建圖方法密不可分，Jiménez等[87]優(yōu)化從雷達(dá)點(diǎn)云得到占用率的建圖方法.Sun等[88]利用語義信息及地形，使用多張小的POGM拼接而成，保證POGM的分辨率.并且，具備預(yù)測(cè)特征的地圖也為未知的不確定性環(huán)境中的運(yùn)動(dòng)規(guī)劃提供有力工具，克服對(duì)未觀察到的環(huán)境結(jié)構(gòu)進(jìn)行推理的能力有限的問題[89-91].Wang等[92]使用自監(jiān)督學(xué)習(xí)方法，通過模擬導(dǎo)航軌跡增強(qiáng)數(shù)據(jù)，將預(yù)測(cè)推廣到3D占用柵格圖，保證安全高效的規(guī)劃.

McLeod等[86]利用過去的經(jīng)驗(yàn)，基于Hilbert Maps框架，從深度信息中學(xué)習(xí)以預(yù)測(cè)概率占用柵格圖的占用率.該方法將深度數(shù)據(jù)投影到由近似核函數(shù)定義的高維希爾伯特空間中，然后在該高維空間中學(xué)習(xí)線性邏輯回歸模型，結(jié)果是一個(gè)sigmoid似然判別模型，可預(yù)測(cè)歐幾里得空間中某點(diǎn)被占用的概率.單個(gè)柵格未被占用的概率為：

其中，φ(x)表示位置x的特征向量，w表示學(xué)習(xí)的參數(shù)向量.

文獻(xiàn)[86]方法可結(jié)合學(xué)習(xí)到的信息和真實(shí)的障礙物感知信息，為那些被遮擋的環(huán)境區(qū)域提供有用的信息，得到POGM，為智能體提供RAMP框架下更優(yōu)的初始軌跡.相比原始的確定性RAMP框架，文獻(xiàn)[86]方法在高占用率區(qū)域會(huì)生成更少的初始軌跡，在行駛過程中切換軌跡的偏差更小.

運(yùn)動(dòng)規(guī)劃的目標(biāo)是找到一個(gè)軌跡，使某些代價(jià)函數(shù)最小化，滿足運(yùn)動(dòng)學(xué)約束，并避免碰撞.POGM用于確保規(guī)劃得出的軌跡沒有碰撞.然而，多數(shù)規(guī)劃方法都假設(shè)初始狀態(tài)是完全已知的，但由于傳感器噪聲的存在，在現(xiàn)實(shí)世界中往往無法給出完全確定的狀態(tài).

為了解決此類問題，可用高斯概率分布描述不確定性，使用更大的膨脹體積近似對(duì)象，在此基礎(chǔ)上快速執(zhí)行碰撞檢測(cè)[93].但是，擴(kuò)大的邊界體積通常會(huì)對(duì)碰撞概率夸大估計(jì).因此，在復(fù)雜的環(huán)境中導(dǎo)航，這種表示方法往往會(huì)導(dǎo)致可行空間縮小，規(guī)劃可能會(huì)因此得到次優(yōu)方案.

為了處理不確定性環(huán)境下的碰撞檢測(cè)問題，通常將自動(dòng)駕駛汽車與障礙物的位置使用具有無界概率分布形式的隨機(jī)變量描述風(fēng)險(xiǎn)感知運(yùn)動(dòng)規(guī)劃算法[94]，適用于最小化碰撞概率，這里的不確定性碰撞可能是車輛和障礙物定位不精確、車輛自身或動(dòng)態(tài)障礙物的動(dòng)力學(xué)模型不準(zhǔn)確，甚至可能是噪聲干擾導(dǎo)致的碰撞.因此在文獻(xiàn)[95]中提出風(fēng)險(xiǎn)感知成本函數(shù)，將高斯過程(Gaussian Process, GP)后驗(yàn)的風(fēng)險(xiǎn)度量轉(zhuǎn)換為用于規(guī)劃的成本函數(shù).基于采樣的在線運(yùn)動(dòng)規(guī)劃算法中風(fēng)險(xiǎn)函數(shù)的應(yīng)用可考慮到軌跡長度、平滑度、與障礙物的距離.利用概率柵格圖處理多傳感器融合后信息，進(jìn)行車道占用概率判斷，綜合車道內(nèi)的占用概率，表征車道的可行性，并利用貝葉斯網(wǎng)絡(luò)在圖上進(jìn)行輔助換道決策[68,96-97].Artuedo等[98]創(chuàng)建感知柵格，并將地圖信息和道路限制添加到柵格中，可區(qū)分自由的可導(dǎo)航空間或非可導(dǎo)航空間，以及使用車對(duì)車通信獲得的動(dòng)態(tài)障礙物速度.柵格圖可將車道信息、動(dòng)靜態(tài)障礙物信息集成到通用表達(dá)里.

Lau等[99]將柵格圖轉(zhuǎn)化為距離圖，初始狀態(tài)下空閑柵格距離障礙物的歐幾里得距離為正無窮.因?yàn)橛羞吔绾驼系K物的存在，減小內(nèi)部未被占用柵格與最近障礙物點(diǎn)的距離，即從障礙物柵格開始，逐步向外擴(kuò)散更新，計(jì)算新的最近障礙物坐標(biāo)與距離，距離越近顏色越深.當(dāng)所有柵格都被更新后，距離圖建立完成.由于障礙物的消失，其附近的柵格中保存的最近障礙物距離被更新為無窮，此類柵格的狀態(tài)更新是一個(gè)距離增大(Raise)的過程.類似地，因?yàn)樾碌恼系K物出現(xiàn)，周圍的柵格保存的最近障礙物距離被重新計(jì)算，所以這些柵格的狀態(tài)更新是一個(gè)距離減小(Lower)的過程.當(dāng)Raise和Lower的過程相遇，Lower處理過的柵格不會(huì)受影響，但對(duì)于Raise處理過的柵格，要考慮新出現(xiàn)的障礙物對(duì)其的影響，需重新計(jì)算最近障礙物的距離，所以Raise過程結(jié)束，轉(zhuǎn)變?yōu)長ower過程.當(dāng)兩類過程不再更新時(shí)，新的距離圖更新結(jié)束.該更新過程與GVD(Generalized Voro-noi Diagrams)的更新同步進(jìn)行，但其只更新障礙物附近的柵格，不更新靜態(tài)障礙物或固有邊界，避免遍歷全部柵格，所以這是一個(gè)增量更新的過程，訪問柵格較少，實(shí)時(shí)性較好.

Lüzow等[100]設(shè)計(jì)可微分框架，規(guī)劃可行的軌跡，使碰撞風(fēng)險(xiǎn)最小化.將柵格圖作為深度卷積神經(jīng)網(wǎng)絡(luò)的輸入，可對(duì)交通參與者的交互進(jìn)行隱式建模.通過給定的初始密度分布集中隨機(jī)采樣初始狀態(tài)，并使用分箱方法在占用圖上為每個(gè)預(yù)測(cè)障礙物位置分配相應(yīng)的單元，對(duì)落入同一單元的所有樣本的密度取平均值，最后歸一化占用率.

Banfi等[101]研究占用地圖不確定性對(duì)全局路徑規(guī)劃的影響，并提出直接考慮地圖不確定性的方法.當(dāng)若干個(gè)障礙物阻塞路徑時(shí)，可得到相比確定性規(guī)劃更可靠的路徑，驗(yàn)證在路徑規(guī)劃過程中關(guān)于障礙物不確定存在推理的有用性.由于使用概率占用網(wǎng)格圖表示包含噪聲的環(huán)境，傳統(tǒng)的確定性規(guī)劃在占用概率上使用硬閾值以聲明一個(gè)單元是一個(gè)障礙，并相應(yīng)規(guī)劃一條路徑，同時(shí)將未知空間視為空閑空間.該不確定性規(guī)劃器規(guī)劃兩個(gè)不同的路徑假設(shè)，再將它們的初始軌跡段合并為一個(gè)以“次優(yōu)視圖”姿態(tài)結(jié)束的單一軌跡段.隨后選擇其中一個(gè)假設(shè)，或在沖突即將發(fā)生時(shí)選擇一個(gè)全新的假設(shè).

POGM的另一優(yōu)勢(shì)是對(duì)于結(jié)構(gòu)化環(huán)境和非結(jié)構(gòu)化環(huán)境都具有良好的表征形式.在擁擠的泊車環(huán)境中通常使用占用柵格圖表征半結(jié)構(gòu)化環(huán)境[102].泊車環(huán)境既包含結(jié)構(gòu)化的車位信息，其行駛策略(前進(jìn)或倒車)又具有非結(jié)構(gòu)性.在如圖13的復(fù)雜泊車環(huán)境中，可使用占用柵格圖表征車位對(duì)不同車輛的“吸引力”系數(shù)，提出一個(gè)機(jī)會(huì)約束優(yōu)化問題，最小化掃描區(qū)域的成本，同時(shí)滿足路徑的人流量密度的概率約束[103].

圖13 停車場(chǎng)的車輛不確定示意圖

Souza等[104]提出OEG(Occupancy-Elevation Grid)，表示二維水平柵格上的三維環(huán)境，其中每個(gè)單元包含占用概率值、高度及方差，對(duì)應(yīng)于映射位置.該占用柵格表達(dá)使用緊湊的結(jié)構(gòu)表示3D信息，更適用于處理意外情況和與環(huán)境交互.另一種方法是將障礙物儲(chǔ)存為柵格圖形式并分為四類：非孤立障礙物占據(jù)的柵格，空閑柵格，僅存在孤立障礙物的柵格，與上述三類不同但存在于傳感器觀測(cè)的障礙物與自身間連線上的柵格.通過對(duì)比連續(xù)兩幀間柵格的異同，利用迭代最近點(diǎn)(Iterative Closest Point，IPC)預(yù)測(cè)其當(dāng)前障礙物的真實(shí)占用概率情況.占用柵格圖的優(yōu)勢(shì)還包括對(duì)于在當(dāng)前建模下無法規(guī)劃路徑的情況，可進(jìn)行二次觀測(cè)[97].類似于移動(dòng)智能機(jī)器人的優(yōu)化蟻群算法，其中信息素濃度的更新可類比于占用柵格圖的更新[105].若仍無法得到可行的安全路徑，則從安全脫困的角度規(guī)劃，克服陷入局部極小值的情況.

4 不確定性問題研究展望

盡管POMDP與POGM提供解決規(guī)劃過程中不確定性問題的途徑，但關(guān)于不確定性問題的研究仍存在如下兩方面的不足.一方面，不確定性問題因?yàn)槠渥陨淼母呔S表示容易陷入維度陷阱，傳統(tǒng)表示方法又難以概括不確定性問題的多樣性與通用性.另一方面，不確定性環(huán)境下的規(guī)劃需要足夠魯棒的模型[106-107].

規(guī)劃結(jié)構(gòu)的可靠性不僅取決于安全性，同時(shí)也取決于模型與真實(shí)環(huán)境的相似程度.與傳統(tǒng)的規(guī)劃方法類似，POMDP和POGM也需要精確的模型對(duì)規(guī)劃進(jìn)行支持，但是對(duì)于絕大多數(shù)場(chǎng)景，POMDP中的獎(jiǎng)勵(lì)函數(shù)、狀態(tài)、觀察都是來源于經(jīng)驗(yàn)或假設(shè).事實(shí)上，這類模型參數(shù)具有極大的不確定性.模仿學(xué)習(xí)、表示學(xué)習(xí)、多機(jī)器人強(qiáng)化學(xué)習(xí)、時(shí)間抽象及貝葉斯強(qiáng)化學(xué)習(xí)(Bayesian Reinforcement Learning，BRL)等技術(shù)可應(yīng)用于解決模型的不確定性.例如，BRL可將未知參數(shù)視為附加的狀態(tài)變量，在定義未知參數(shù)的先驗(yàn)知識(shí)后，求解最佳收集參數(shù)信息的策略[108].因此，未來的主流解決方法研究集中在學(xué)習(xí)類方法.

4.1 POMDP與POGM的結(jié)合

一個(gè)解決不確定性問題的融合性思路是結(jié)合POMDP與POGM，將POGM視為機(jī)會(huì)約束的一部分.機(jī)會(huì)約束的增加可以將風(fēng)險(xiǎn)的概念引入不確定性問題.絕大多數(shù)規(guī)劃將重點(diǎn)放在避免碰撞上，視碰撞為一種機(jī)會(huì)約束.相比觀測(cè)的期望，多數(shù)研究者將機(jī)會(huì)約束表示為概率性的，使用概率信念相關(guān)約束支持風(fēng)險(xiǎn)規(guī)避算子，如CVaR(Conditional Value at Risk)[109].對(duì)于絕大多數(shù)POMDP問題而言，表達(dá)概率風(fēng)險(xiǎn)規(guī)避約束的形式很重要.Zhitnikov等[110]將傳統(tǒng)的機(jī)會(huì)約束POMDP擴(kuò)展到信念MDP的水平，并提出PCSS和CCSS，解決具有挑戰(zhàn)性的連續(xù)域和可能的非參數(shù)設(shè)置中的兩個(gè)公式.

機(jī)會(huì)約束可通過下述兩種方法進(jìn)行評(píng)估:1)假設(shè)高斯分布狀態(tài)變量上的線性約束，并將機(jī)會(huì)約束轉(zhuǎn)換為狀態(tài)均值上的約束，2)通過蒙特卡洛模擬評(píng)估約束.方法2)可處理非高斯分布和非線性約束，但計(jì)算量很大.Aoude等[96]在實(shí)驗(yàn)中證實(shí)概率約束在避免碰撞方面比傳統(tǒng)的機(jī)會(huì)約束公式更具優(yōu)勢(shì).

POGM通常需要降采樣以降低網(wǎng)格節(jié)點(diǎn)數(shù)，加快運(yùn)算速度.但目前的降采樣方法往往以隨機(jī)的形式進(jìn)行，可能會(huì)忽略關(guān)鍵的環(huán)境信息.在未來的研究工作中，可結(jié)合環(huán)境屬性、降采樣、環(huán)境預(yù)測(cè)[111].環(huán)境屬性包含語義信息、連通情況、總節(jié)點(diǎn)數(shù)等，和占用柵格圖的抽象性具備一致性.換言之，當(dāng)前研究者們致力于將不確定性環(huán)境轉(zhuǎn)化為更適合人工智能理解和計(jì)算機(jī)處理的抽象表征[112].

目前求解方法研究雖然已取得一定進(jìn)展，但是大部分還是在處理離散空間，不適用于處理決策規(guī)劃問題.對(duì)于連續(xù)空間且規(guī)模較大的問題，多使用強(qiáng)化學(xué)習(xí)的方法進(jìn)行問題求解[113].雖然強(qiáng)化學(xué)習(xí)缺乏置信度，難以在真實(shí)環(huán)境下應(yīng)用與推廣，但其解決規(guī)劃決策問題是未來主流的發(fā)展趨勢(shì)，且從安全性和可靠性上考慮，未來仍需繼續(xù)研究.

4.2 多智能體協(xié)同

相比規(guī)則庫和解空間有限的傳統(tǒng)規(guī)劃算法，研究者更青睞靈活性更高的協(xié)同類算法.協(xié)同類算法能有效克服單個(gè)車輛感知范圍有限、在極端情況下難以處理的問題[114].

多智能體決策系統(tǒng)(Multi-agent Decision Sys-tem，MADS)通常是指多個(gè)智能體聯(lián)合起來的決策系統(tǒng)，系統(tǒng)中的每個(gè)智能體都是一個(gè)獨(dú)立決策個(gè)體，通過從環(huán)境中獲得的信息進(jìn)行聯(lián)合決策.這同車聯(lián)網(wǎng)具有緊密的聯(lián)系，V2V(Vehicle-to-Vehicle)有助于精確感知現(xiàn)實(shí)世界，快速分析傳感數(shù)據(jù).每輛車都可對(duì)環(huán)境獨(dú)立施以一個(gè)動(dòng)作，整個(gè)系統(tǒng)的狀態(tài)受到所有車輛聯(lián)合動(dòng)作的影響，因此每輛車的決策過程都需要考慮其它車輛可能采取的動(dòng)作，以及這個(gè)可能采取的動(dòng)作對(duì)車輛的影響.每輛車單獨(dú)決策的不確定性包括感知信息延遲、動(dòng)作執(zhí)行不完整等.如果加入多車協(xié)作，引入的不確定性會(huì)讓規(guī)劃過程變得更復(fù)雜.隨著車聯(lián)網(wǎng)技術(shù)的發(fā)展，V2X(Vehicle to Every-thing)、V2V逐步完善，對(duì)于這種多智能體系統(tǒng)的決策過程，也可通過DEC-POMDP(Decentralized POM-DP)解決.DEC-POMDP的優(yōu)勢(shì)是為多智能體合作任務(wù)提供概率框架，可對(duì)結(jié)果、環(huán)境信息和通信方面不確定性問題進(jìn)行建模.因?yàn)镈EC-POMDP利用所有智能體的聯(lián)合動(dòng)作,從一個(gè)狀態(tài)過渡到下一個(gè)狀態(tài)，可為決策建模提供完整依據(jù).DEC-POMDP的求解方法同POMDP類似，區(qū)別在于將狀態(tài)、動(dòng)作、信念和觀察均使用聯(lián)合取代.在任意決策周期內(nèi)，系統(tǒng)根據(jù)所有車輛的聯(lián)合動(dòng)作轉(zhuǎn)移到下一個(gè)狀態(tài)，同時(shí)系統(tǒng)進(jìn)入下一個(gè)決策周期.

DEC-POMDP面臨和POMDP同樣的問題，計(jì)算量大，狀態(tài)描述、策略表達(dá)、狀態(tài)、觀測(cè)轉(zhuǎn)移的形式都難以確定.相比POMDP隨著決策周期指數(shù)級(jí)增長的運(yùn)算量，DEC-POMDP面臨著雙指數(shù)級(jí)的運(yùn)算量增加[107].巨大的運(yùn)算量造成的時(shí)間開銷已不足以滿足自動(dòng)駕駛安全性的要求，對(duì)于碰撞不能采取及時(shí)的制動(dòng)措施.分組有限空間離線規(guī)劃算法能在DEC-POMDP中取得較好效果，從整體上，算法運(yùn)行時(shí)間也可得到一定降低.但該算法僅適用于小規(guī)模的有限空間的問題，對(duì)于大規(guī)模DEC-POMDP問題沒有幫助[115-116].

強(qiáng)化學(xué)習(xí)的引入為求解DEC-POMDP問題提供可能，但目前基于溝通學(xué)習(xí)的MARL(Multi-agent Reinforcement Learning)需要假設(shè)代理間顯式存在信息交互，該通信往往需要預(yù)先進(jìn)行訓(xùn)練[117].多智能體間的通信需要考慮通信對(duì)象選擇，如果要保證所有智能體產(chǎn)生的消息都不被遺漏，就可能會(huì)引入許多無用的信息，影響通信效率，增大通信成本.特別是對(duì)于擁擠路口，智能體數(shù)量較多，不確定性較高，對(duì)于這些冗余信息的處理容易導(dǎo)致不安全的導(dǎo)航結(jié)果.分層通信和將通信對(duì)象的選擇視為任務(wù)的端到端方法可提升通信效果.基于協(xié)作學(xué)習(xí)的MARL結(jié)合多智能體學(xué)習(xí)的思想與強(qiáng)化學(xué)習(xí)，通?？煞譃榛谥档姆椒╗117]和Actor-Critic網(wǎng)絡(luò)[118].前者對(duì)于較復(fù)雜的環(huán)境，無法較好地處理非平穩(wěn)環(huán)境，后者通過中心化學(xué)習(xí)評(píng)論家，在較好處理算法可擴(kuò)展性問題的同時(shí)，擁有較好的抗環(huán)境非平穩(wěn)能力.

除了多智能體的協(xié)同強(qiáng)化學(xué)習(xí)，協(xié)同模仿學(xué)習(xí)也獲得研究者的青睞.協(xié)同模仿學(xué)習(xí)有利于提升單獨(dú)車輛的感知能力.COOPERNAUT[119]利用跨車輛感知進(jìn)行基于視覺的協(xié)作駕駛，共享車聯(lián)網(wǎng)中的全部車輛獲取的感知信息.協(xié)同駕駛可擴(kuò)大主體車輛的感知范圍，并傳遞其它車輛的意圖和路徑規(guī)劃結(jié)果，有助于在事故頻發(fā)時(shí)給出安全的可行路徑.模仿學(xué)習(xí)能通過大量數(shù)據(jù)，端到端地實(shí)現(xiàn)從感知輸入到直接輸出規(guī)劃結(jié)果.這種學(xué)習(xí)形式更符合人類思維，有利于在不確定性環(huán)境中實(shí)現(xiàn)類人駕駛.對(duì)于模仿學(xué)習(xí)而言，完全信賴專家系統(tǒng)，高度依賴數(shù)據(jù)集的規(guī)模與質(zhì)量.模仿學(xué)習(xí)僅學(xué)習(xí)可行策略，對(duì)不可行策略沒有試錯(cuò)過程，缺乏在極端環(huán)境下的處理能力[120-121].因此，隨著大數(shù)據(jù)的應(yīng)用與分布式運(yùn)算等計(jì)算方法的發(fā)展，將場(chǎng)景內(nèi)全部車輛的感知信息作為單車傳感增強(qiáng)，學(xué)習(xí)協(xié)作感知的自動(dòng)駕駛策略，可在結(jié)構(gòu)化環(huán)境與非結(jié)構(gòu)化環(huán)境下均獲得較優(yōu)的導(dǎo)航效果.

對(duì)于多智能體系統(tǒng)，不僅需要考慮協(xié)作，也需要考慮對(duì)抗.隨著網(wǎng)聯(lián)汽車發(fā)展，必須考慮保護(hù)性的對(duì)抗行為.系統(tǒng)內(nèi)對(duì)抗惡意個(gè)體產(chǎn)生的對(duì)抗或許不享有共同的獎(jiǎng)勵(lì)，同樣會(huì)引入不確定性，這對(duì)車聯(lián)網(wǎng)中隱私安全保護(hù)提出更高要求.

4.3 面臨的挑戰(zhàn)

傳統(tǒng)的規(guī)劃方法對(duì)于不確定性問題的研究十分匱乏.主流的POMDP面臨建模不夠準(zhǔn)確、計(jì)算耗時(shí)、不滿足規(guī)劃實(shí)時(shí)性的問題.概率占用圖對(duì)于感知的不確定性具有較好的處理能力，但是難以解決誤檢問題.基于柵格圖的部分規(guī)劃算法可能會(huì)導(dǎo)致車輛受困：蟻群算法在局部極小值點(diǎn)上不能采取下一步行動(dòng)；人工勢(shì)場(chǎng)方法落入斥力與引力相等的節(jié)點(diǎn)，都難以得到未來路徑.學(xué)習(xí)類的方法難以推行的一大阻礙是信任問題.事實(shí)上，自動(dòng)駕駛是不容錯(cuò)的人工智能系統(tǒng)，無論是數(shù)據(jù)獲取過程，還是實(shí)驗(yàn)測(cè)試過程，都難以在真正的車輛行駛環(huán)境下進(jìn)行.不確定性會(huì)增大真實(shí)環(huán)境與虛擬環(huán)境的區(qū)別，降低駕駛員對(duì)自動(dòng)駕駛決策的信任水平.

本文展望兩種未來解決規(guī)劃決策問題的方法，可有效克服上述缺陷，加快規(guī)劃速度，提升對(duì)周圍環(huán)境的感知能力.但結(jié)合POMDP和POGM的方法得出的結(jié)果通常是離散的加速度域和速度域.不確定性問題求解的有限解空間難以涵蓋所有情況，可能因?yàn)樗俣入x散而導(dǎo)致在真實(shí)情況下可行的速度矢量在解空間之外.雖然多智能體協(xié)同的方法雖然能通過共享目標(biāo)和狀態(tài)，增大感知視野進(jìn)行多智能體系統(tǒng)的規(guī)劃，但其運(yùn)算量較大，收斂到良好解的速度較慢，并且假設(shè)智能體總開始于零知識(shí)狀態(tài).目前自動(dòng)駕駛技術(shù)通常需要結(jié)合專家建議，但是對(duì)于數(shù)據(jù)集的質(zhì)量和規(guī)模要求較高.協(xié)同學(xué)習(xí)依賴車聯(lián)網(wǎng)間的通信，對(duì)通信技術(shù)要求較高，往往只能解決緩慢變化的環(huán)境.

盡管目前自動(dòng)駕駛還面臨許多方面的問題，但人工智能技術(shù)將持續(xù)全面融合認(rèn)知科學(xué)、心理學(xué)、生物學(xué)、社會(huì)學(xué)等多學(xué)科，推動(dòng)自動(dòng)駕駛應(yīng)用與發(fā)展.研究者希望能在不確定性環(huán)境下的規(guī)劃問題中具有更好的建模與求解方法，為自動(dòng)駕駛的發(fā)展提供可能.

5 結(jié)束語

本文介紹不確定性環(huán)境下自動(dòng)駕駛的規(guī)劃過程.首先介紹不確定性問題的表示，并介紹解決該問題的必要性與難點(diǎn)，從理論基礎(chǔ)、求解方法及具體應(yīng)用三方面介紹兩種主流的解決規(guī)劃過程中的不確定性問題的方法.最后深入分析當(dāng)下該領(lǐng)域的發(fā)展現(xiàn)狀與面臨的挑戰(zhàn)，針對(duì)高效性、可靠性、交互性等多方面對(duì)未來的研究方向進(jìn)行展望.縱覽近年自動(dòng)駕駛的成果可看出，自動(dòng)駕駛正朝向類人、可靠、智能的方向發(fā)展.不確定性問題是自動(dòng)駕駛發(fā)展必須克服的一道難關(guān)，應(yīng)從定位、感知、地圖、規(guī)劃、控制各環(huán)節(jié)應(yīng)對(duì)這種不確定性，共同構(gòu)成安全可靠、應(yīng)用場(chǎng)景廣泛的自動(dòng)駕駛系統(tǒng).