面向不確定性環(huán)境的自動駕駛運(yùn)動規(guī)劃：機(jī)遇與挑戰(zhàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 部分可觀測馬爾可夫決策過程

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

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

2.1 理論介紹

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

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

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

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

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

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

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

2.2 求解方法

2.2.1 離線算法

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

離線算法的優(yōu)勢在于最優(yōu)策略的計(jì)算不占用在線決策的時間，可保證決策的實(shí)時性，但該算法需要處理大范圍信念狀態(tài)空間，求解時間較長，實(shí)用性較低.為了處理這種低效的精確求解問題，有學(xué)者提出可加快運(yùn)算速度的近似方法.基于點(diǎn)的值迭代算法是典型的離線近似算法之一，基本思想是只考慮部分可達(dá)的信念狀態(tài)以減小信念狀態(tài)空間的大小，從而減小運(yùn)算量.考慮到最優(yōu)值函數(shù)是分段線性的，因此部分信念狀態(tài)通常對整體的信念狀態(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 在線算法

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

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

規(guī)劃階段分為搜索樹構(gòu)建和回溯兩步.POMDP構(gòu)建的搜索樹又稱與或樹，由與節(jié)點(diǎn)(AND-Nodes)，或節(jié)點(diǎn)(OR-Nodes)構(gòu)成，一個典型的與或樹如圖3所示.以當(dāng)前信念狀態(tài)b0為根節(jié)點(diǎn)，基于根節(jié)點(diǎn)信念狀態(tài)遍歷所有動作at，得到相應(yīng)的OR-Nodes.基于每個OR-Nodes，考慮所有可能的觀測ot，并更新信念狀態(tài)b，獲取新的信念狀態(tài)節(jié)點(diǎn).以此類推，直到達(dá)到事先設(shè)定的搜索深度，搜索樹構(gòu)建完成.構(gòu)建完成后利用貝爾曼最優(yōu)性原則從葉子節(jié)點(diǎn)開始對搜索樹進(jìn)行回溯，對回溯路徑上各個信念狀態(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ì)算量已大幅降低，并且對動態(tài)環(huán)境中的決策也有較好效果，但依然需要處理龐大的動作空間及觀測空間，影響實(shí)時性.研究者們通常關(guān)注近似算法，在保證一定的決策準(zhǔn)確度的前提下降低運(yùn)算量.

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

分支與邊界裁剪算法的基本思想在于通過對比不同節(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)行樹搜索時，倘若在當(dāng)前信念狀態(tài)b下執(zhí)行動作a獲得的值函數(shù)下界大于執(zhí)行動作a′時獲得的值函數(shù)的上界，那么可認(rèn)為在信念狀態(tài)b下動作a′是次優(yōu)的，因此可將動作a′及其分支進(jìn)行裁剪，降低搜索樹的復(fù)雜度，提高樹搜索效率.

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

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

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

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

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

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

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

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

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

強(qiáng)化學(xué)習(xí)能讓智能體在與環(huán)境的交互中自主學(xué)習(xí)，通過最大化獎勵的方式讓智能體學(xué)會如何決策.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)動規(guī)劃、決策控制等多個領(lǐng)域.在處理不確定性問題的迭代過程中，強(qiáng)化學(xué)習(xí)的目標(biāo)就是使Agent通過最大化累計(jì)獎勵rt學(xué)習(xí)最優(yōu)化策略Π*，獲得觀測到最優(yōu)動作的映射.

大多數(shù)強(qiáng)化學(xué)習(xí)問題都假設(shè)環(huán)境的狀態(tài)在每個時間步長下都是完全可觀測的，針對MDP描述的問題，強(qiáng)化學(xué)習(xí)已有很多經(jīng)典算法.例如：1)基于價值(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)效果.

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

圖4 POMDP決策過程示意圖

POMDP的主要挑戰(zhàn)在于如何通過不完全的觀測推測信念狀態(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)記錄歷史觀測和動作，為智能體提供更多的信息，此方法隱式地包含對信念狀態(tài)的推理，不僅依靠當(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)向量和完全可觀測向量構(gòu)成，而以往的DQN輸入由MDP中的狀態(tài)表述，DBQN通過在輸入中添加信念狀態(tài)以尋找最優(yōu)策略,這使DBQN具有可有效應(yīng)對POMDP場景的能力，并且在Tiger與Rock Sample兩款游戲中都獲得優(yōu)于DQN的效果.

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

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

Hausknecht等[40]將POMDP問題中的歷史觀測信息由RNN記錄下來，提出DRQN(Deep RecurrentQ-Network)，適用于無模型的POMDP場景.DRQN網(wǎng)絡(luò)結(jié)構(gòu)如圖6所示.DRQN最小限度修改原DQN網(wǎng)絡(luò)結(jié)構(gòu)，僅僅將DQN中第1個全連接層換成相同大小的長短期記憶網(wǎng)絡(luò)(Long Short-Term Memory，LSTM)層[41].相比RNN，LSTM結(jié)構(gòu)儲存更多的歷史信息，使網(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)僅包含歷史的觀測(ot,ot-1,ot-2…)，也應(yīng)包含歷史的動作信息(at,at-1,at-2，…)，這樣有助于更好地推斷當(dāng)前的信念狀態(tài).不同之處在于DDRQN分別輸入歷史動作序列和歷史觀測序列進(jìn)行解耦，而ADQRN將歷史觀測和歷史動作組合成觀測-動作對輸入，體現(xiàn)時序條件下歷史觀測與歷史動作的相關(guān)信息.提供歷史動作信息的DDRQN和ADRQN更有助于智能體學(xué)習(xí)最優(yōu)策略Π*.實(shí)驗(yàn)證實(shí)，在Pong、Frostbite、Asteroids等游戲中，提供歷史動作信息的DDRQN和ADRQN表現(xiàn)更優(yōu)，驗(yàn)證在RNN中包含更多的有效歷史信息有助于智能體在POMDP場景中更好地學(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)對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)換為兩個密切相關(guān)的序列蒙特卡羅過程(Sequential Monte Carlo，SMC)，通過蒙特卡洛濾波直接規(guī)劃一個近似的信念以明確表示信念分布，并且按策略訓(xùn)練的方法訓(xùn)練信念狀態(tài)表述濾波器.Singh 等[47]提出SWB(Structured World Belief)，通過SMC推斷為在POMDP環(huán)境中提供以對象為中心的結(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)對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的觀測模型整合，并且在DeepMind的視覺-運(yùn)動控制任務(wù)[50]中取得較優(yōu)效果.

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

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

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

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

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

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

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

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

Luo等[10]提出PORCA(Pedestrian Optimal Reci-procal Collision Avoidance)，用于預(yù)測行人的運(yùn)動軌跡.PORCA引入更復(fù)雜的行人運(yùn)動模型，根據(jù)行人意圖及行人之間、行人與車輛之間的交互，對行人短期運(yùn)動軌跡進(jìn)行準(zhǔn)確預(yù)測.然而，兩層處理架構(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)自動駕駛車輛在密集人群中的運(yùn)動與導(dǎo)航.為了模擬復(fù)雜駕駛行為，LeTS-Drive構(gòu)建一個二維聯(lián)合動作空間，同時考慮車的前輪轉(zhuǎn)角與加速度.在搜索樹構(gòu)建過程中，基于HyP-DESPOT(Hybrid Parallel DESPOT)[56]，LeTS-Drive使用預(yù)先訓(xùn)練好的策略與值網(wǎng)絡(luò)引導(dǎo)動作的選擇，進(jìn)一步加速搜索樹構(gòu)建效率.然而，神經(jīng)網(wǎng)絡(luò)的復(fù)雜性影響在線搜索的效率，因此需要更有效的策略和價值函數(shù)表示.當(dāng)網(wǎng)絡(luò)學(xué)習(xí)的策略難以推廣到不同的地圖與主體車輛行為上時，需要進(jìn)一步拓展模型的訓(xùn)練環(huán)境.

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

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

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

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

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

圖9 視野受限的路口車輛

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

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

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

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

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

圖10 超車示意圖

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

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

3 概率占用柵格圖

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

3.1 理論基礎(chǔ)

概率占用柵格圖作為一種環(huán)境表征方法，表示形式如圖11所示.雖然POGM從柵格地圖發(fā)展而來，但是比僅有占用/空閑兩種狀態(tài)的柵格地圖，概率的表示形式更適用于碰撞風(fēng)險的衡量.因此，POGM具備環(huán)境表征抽象性、碰撞風(fēng)險更優(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ù)解釋為占用信息時，不可避免地引入未知部分和誤差導(dǎo)致的不確定性.未知部分的產(chǎn)生是由于靠前障礙物的遮擋，導(dǎo)致障礙物后的區(qū)域不能被感知到，誤差來自噪聲和不精確的姿態(tài)估計(jì)[70].

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

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

更新過程如下：

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

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

3.2 求解方法

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

基于采樣的方法以快速擴(kuò)展隨機(jī)樹(Rapidly-Exploring Random Trees，RRT)及其各類優(yōu)化變種方法為典型代表.自RRT提出后，常應(yīng)用于解決非凸高維空間的快速搜索、靜態(tài)障礙物和差分運(yùn)動約束問題，并且作為局部規(guī)劃時可考慮更大范圍內(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ī)劃，同時也可在樹擴(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)確的距離對RRT探索能力的影響,計(jì)算樹中節(jié)點(diǎn)的可達(dá)集，當(dāng)采樣點(diǎn)到節(jié)點(diǎn)的距離大于采樣點(diǎn)到該節(jié)點(diǎn)可達(dá)集的距離時，該節(jié)點(diǎn)才有可能被選中進(jìn)行擴(kuò)展.

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

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

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

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

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

上述的基于采樣的方法往往難以在有限迭代中得到最優(yōu)路徑，而基于搜索的方法發(fā)展已較成熟，具有解析完備性和解析最優(yōu)性.Koenig等[79]提出一種增量算法，用于推廣具有任意邊插入、邊刪除和邊長度變化的圖中的最短路徑問題.Stentz等[80]提出Dstar，在部分已知的環(huán)境中實(shí)現(xiàn)最佳、有效的重新規(guī)劃，當(dāng)檢測到地圖中的變化時，不是重新計(jì)算整個地圖的最佳路徑，而是檢查一組減少的單元，并逐步更新到最佳路徑.這里的增量利用以前計(jì)劃的結(jié)果生成新的規(guī)劃結(jié)果，可加快速度.然而，在可用時間內(nèi)找到絕對最優(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*雖然選擇半徑會發(fā)生改變，但其對不同的環(huán)境取決于總的點(diǎn)數(shù)，不具有場景間的區(qū)分度.3D重建后的相機(jī)在弱光條件下容易產(chǎn)生偽影.對于這種情況，障礙物會出現(xiàn)位置上的不確定性，容易導(dǎo)致多檢、誤檢.這種感知導(dǎo)致的不確定性環(huán)境表征給障礙物碰撞風(fēng)險的衡量帶來極大的不確定性[83].

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

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

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

因?yàn)镻OGM本身的概率特性，因此也常用機(jī)會約束規(guī)劃處理此類問題.機(jī)會約束用于衡量障礙物碰撞概率，求解方法在運(yùn)動規(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ù)測特征的地圖也為未知的不確定性環(huán)境中的運(yùn)動規(guī)劃提供有力工具，克服對未觀察到的環(huán)境結(jié)構(gòu)進(jìn)行推理的能力有限的問題[89-91].Wang等[92]使用自監(jiān)督學(xué)習(xí)方法，通過模擬導(dǎo)航軌跡增強(qiáng)數(shù)據(jù)，將預(yù)測推廣到3D占用柵格圖，保證安全高效的規(guī)劃.

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

其中，φ(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ū)域會生成更少的初始軌跡，在行駛過程中切換軌跡的偏差更小.

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

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

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

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

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

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

POGM的另一優(yōu)勢是對于結(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)境中，可使用占用柵格圖表征車位對不同車輛的“吸引力”系數(shù)，提出一個機(jī)會約束優(yōu)化問題，最小化掃描區(qū)域的成本，同時滿足路徑的人流量密度的概率約束[103].

圖13 停車場的車輛不確定示意圖

Souza等[104]提出OEG(Occupancy-Elevation Grid)，表示二維水平柵格上的三維環(huán)境，其中每個單元包含占用概率值、高度及方差，對應(yīng)于映射位置.該占用柵格表達(dá)使用緊湊的結(jié)構(gòu)表示3D信息，更適用于處理意外情況和與環(huán)境交互.另一種方法是將障礙物儲存為柵格圖形式并分為四類：非孤立障礙物占據(jù)的柵格，空閑柵格，僅存在孤立障礙物的柵格，與上述三類不同但存在于傳感器觀測的障礙物與自身間連線上的柵格.通過對比連續(xù)兩幀間柵格的異同，利用迭代最近點(diǎn)(Iterative Closest Point，IPC)預(yù)測其當(dāng)前障礙物的真實(shí)占用概率情況.占用柵格圖的優(yōu)勢還包括對于在當(dāng)前建模下無法規(guī)劃路徑的情況，可進(jìn)行二次觀測[97].類似于移動智能機(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í)環(huán)境的相似程度.與傳統(tǒng)的規(guī)劃方法類似，POMDP和POGM也需要精確的模型對規(guī)劃進(jìn)行支持，但是對于絕大多數(shù)場景，POMDP中的獎勵函數(shù)、狀態(tài)、觀察都是來源于經(jīng)驗(yàn)或假設(shè).事實(shí)上，這類模型參數(shù)具有極大的不確定性.模仿學(xué)習(xí)、表示學(xué)習(xí)、多機(jī)器人強(qiáng)化學(xué)習(xí)、時間抽象及貝葉斯強(qiáng)化學(xué)習(xí)(Bayesian Reinforcement Learning，BRL)等技術(shù)可應(yīng)用于解決模型的不確定性.例如，BRL可將未知參數(shù)視為附加的狀態(tài)變量，在定義未知參數(shù)的先驗(yàn)知識后，求解最佳收集參數(shù)信息的策略[108].因此，未來的主流解決方法研究集中在學(xué)習(xí)類方法.

4.1 POMDP與POGM的結(jié)合

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

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

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

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

4.2 多智能體協(xié)同

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

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

DEC-POMDP面臨和POMDP同樣的問題，計(jì)算量大，狀態(tài)描述、策略表達(dá)、狀態(tài)、觀測轉(zhuǎn)移的形式都難以確定.相比POMDP隨著決策周期指數(shù)級增長的運(yùn)算量，DEC-POMDP面臨著雙指數(shù)級的運(yùn)算量增加[107].巨大的運(yùn)算量造成的時間開銷已不足以滿足自動駕駛安全性的要求，對于碰撞不能采取及時的制動措施.分組有限空間離線規(guī)劃算法能在DEC-POMDP中取得較好效果，從整體上，算法運(yùn)行時間也可得到一定降低.但該算法僅適用于小規(guī)模的有限空間的問題，對于大規(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].多智能體間的通信需要考慮通信對象選擇，如果要保證所有智能體產(chǎn)生的消息都不被遺漏，就可能會引入許多無用的信息，影響通信效率，增大通信成本.特別是對于擁擠路口，智能體數(shù)量較多，不確定性較高，對于這些冗余信息的處理容易導(dǎo)致不安全的導(dǎo)航結(jié)果.分層通信和將通信對象的選擇視為任務(wù)的端到端方法可提升通信效果.基于協(xié)作學(xué)習(xí)的MARL結(jié)合多智能體學(xué)習(xí)的思想與強(qiáng)化學(xué)習(xí)，通?？煞譃榛谥档姆椒╗117]和Actor-Critic網(wǎng)絡(luò)[118].前者對于較復(fù)雜的環(huán)境，無法較好地處理非平穩(wěn)環(huán)境，后者通過中心化學(xué)習(xí)評論家，在較好處理算法可擴(kuò)展性問題的同時，擁有較好的抗環(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ā)時給出安全的可行路徑.模仿學(xué)習(xí)能通過大量數(shù)據(jù)，端到端地實(shí)現(xiàn)從感知輸入到直接輸出規(guī)劃結(jié)果.這種學(xué)習(xí)形式更符合人類思維，有利于在不確定性環(huán)境中實(shí)現(xiàn)類人駕駛.對于模仿學(xué)習(xí)而言，完全信賴專家系統(tǒng)，高度依賴數(shù)據(jù)集的規(guī)模與質(zhì)量.模仿學(xué)習(xí)僅學(xué)習(xí)可行策略，對不可行策略沒有試錯過程，缺乏在極端環(huán)境下的處理能力[120-121].因此，隨著大數(shù)據(jù)的應(yīng)用與分布式運(yùn)算等計(jì)算方法的發(fā)展，將場景內(nèi)全部車輛的感知信息作為單車傳感增強(qiáng)，學(xué)習(xí)協(xié)作感知的自動駕駛策略，可在結(jié)構(gòu)化環(huán)境與非結(jié)構(gòu)化環(huán)境下均獲得較優(yōu)的導(dǎo)航效果.

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

4.3 面臨的挑戰(zhàn)

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

本文展望兩種未來解決規(guī)劃決策問題的方法，可有效克服上述缺陷，加快規(guī)劃速度，提升對周圍環(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è)智能體總開始于零知識狀態(tài).目前自動駕駛技術(shù)通常需要結(jié)合專家建議，但是對于數(shù)據(jù)集的質(zhì)量和規(guī)模要求較高.協(xié)同學(xué)習(xí)依賴車聯(lián)網(wǎng)間的通信，對通信技術(shù)要求較高，往往只能解決緩慢變化的環(huán)境.

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

5 結(jié)束語

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