班兵，楊志剛，楊航

MDP及PROLOG在自動(dòng)駕駛中的應(yīng)用

班兵，楊志剛，楊航

（陜西重型汽車有限公司，陜西 西安 710200）

近些年來，自動(dòng)駕駛迎來了新一輪研究熱潮，相關(guān)領(lǐng)域技術(shù)發(fā)展迅速。其中行為決策系統(tǒng)在自動(dòng)駕駛系統(tǒng)框架中占據(jù)重要地位。文章借鑒駕駛員行車過程中視覺行為的注意力分配機(jī)制，通過感興趣區(qū)域推理和馬爾科夫決策的有機(jī)協(xié)作生成駕駛動(dòng)作。最后通過仿真，實(shí)現(xiàn)了簡單場景下的決策指令生成。

行為決策；感興趣區(qū)域；馬爾科夫決策過程

前言

自動(dòng)駕駛汽車是一種通過電腦系統(tǒng)實(shí)現(xiàn)無人駕駛的智能汽車，它的行駛模式更加節(jié)能高效，可以為國家節(jié)省數(shù)千億的交通擁堵成本、交通事故成本以及運(yùn)輸過程中的人力成本。無人駕駛系統(tǒng)整體框架一般由感知、決策、控制三部分組成。其中決策模塊在無人駕駛系統(tǒng)中有著非常重要的作用，不僅保障行車安全，也為路徑規(guī)劃提供指導(dǎo)和限制信息。目前，無人駕駛系統(tǒng)設(shè)計(jì)常用的三類決策算法為基于有限狀態(tài)機(jī)FSM[1]或決策樹[2]的規(guī)則決策算法、馬爾科夫決策和強(qiáng)化學(xué)習(xí)算法、端對(duì)端深度神經(jīng)網(wǎng)絡(luò)決策算法[3]。

規(guī)則決策算法可以將交通規(guī)則知識(shí)和駕駛經(jīng)驗(yàn)知識(shí)編輯成規(guī)則條例，從而實(shí)現(xiàn)行車過程中駕駛動(dòng)作的匹配選擇，其邏輯推理性較強(qiáng)，但卻不能很好地處理駕駛環(huán)境中的不確定因素。馬爾科夫決策將不確定環(huán)境下的駕駛行為決策問題轉(zhuǎn)化成可量化的回報(bào)值計(jì)算，從而選取最優(yōu)動(dòng)作，但其邏輯推理性較弱，且因狀態(tài)空間過大而導(dǎo)致其實(shí)時(shí)性變差，難以滿足在線行為決策系統(tǒng)的需求。因此本文在場景理解的基礎(chǔ)上，基于交通規(guī)則和駕駛經(jīng)驗(yàn)，利用基于規(guī)則的推理機(jī)制得到感興趣區(qū)域，從而使得駕駛動(dòng)作遵守交通規(guī)則的同時(shí)減少馬爾科夫決策過程中概率推理計(jì)算的運(yùn)算量，即保證決策結(jié)果合理性的同時(shí)提升了系統(tǒng)的實(shí)時(shí)性。

1 基于規(guī)則的感興趣區(qū)域生成

人類駕駛員行車過程中對(duì)周圍環(huán)境的注意力分配具有目標(biāo)驅(qū)動(dòng)性，一般情況下，受目標(biāo)地點(diǎn)和全局路徑規(guī)劃的影響，駕駛員的視覺注意力會(huì)選擇性地集中在局部目標(biāo)區(qū)域附近，從而僅提取和理解小范圍區(qū)域內(nèi)的環(huán)境動(dòng)態(tài)信息，而在一定程度上忽略其它區(qū)域的信息。在結(jié)構(gòu)化特征明顯的城市道路工況下，此種目標(biāo)驅(qū)動(dòng)性根據(jù)不同的駕駛?cè)蝿?wù)可以細(xì)化到具體的道路實(shí)體上。如駕駛員在交叉路口進(jìn)行左轉(zhuǎn)彎行駛時(shí)，駕駛員會(huì)將注意力集中在當(dāng)前路段、交叉路口和左轉(zhuǎn)彎目標(biāo)路段，依據(jù)感興趣區(qū)域內(nèi)的實(shí)時(shí)交通動(dòng)態(tài)信息決定下一步的駕駛動(dòng)作。

駕駛行為決策系統(tǒng)中駕駛動(dòng)作的生成是建立在對(duì)駕駛場景充分理解的基礎(chǔ)上的，而駕駛場景本體模型是場景描述的依據(jù)，因此在考慮駕駛場景信息層次性和關(guān)聯(lián)性的基礎(chǔ)上，建立無人駕駛車輛的本體概念模型。

本體模型包括實(shí)體類別定義及屬性描述。在給定駕駛場景相關(guān)實(shí)體類別的定義之后，實(shí)體的狀態(tài)信息及與其它實(shí)體的聯(lián)系通過數(shù)據(jù)屬性和關(guān)系屬性來描述。根據(jù)上述駕駛場景本體模型，可實(shí)現(xiàn)對(duì)自動(dòng)駕駛車輛周圍環(huán)境中靜態(tài)實(shí)體、動(dòng)態(tài)實(shí)體的狀態(tài)信息和相互間關(guān)系的充分描述，從而為進(jìn)一步的邏輯推理做好準(zhǔn)備。

感興趣區(qū)域生成規(guī)則中，車輛在路上狀態(tài)下（非路口區(qū)域）行駛，當(dāng)前車道為最右側(cè)車道時(shí)的規(guī)則可描述為：

eoi(V,L):-egoVehicle(V),currentRoadState(V,”onRoad”),isOnLane(V,X),isRightMost(X,ture),findLeftLane(V,Y),append([X],[Y],L).

車輛V當(dāng)前道路狀態(tài)為在路上，車輛V在車道X上，車道X是最右側(cè)車道，車道X的左側(cè)車道為車道Y，因此車輛V的感興趣區(qū)域?yàn)楫?dāng)前車道和左側(cè)車道。

Prolog是一種基于謂詞演算的高效率聲明式程序設(shè)計(jì)語言，是面向非數(shù)值計(jì)算的描述性語言，在符號(hào)處理和推理方面具有極大的優(yōu)勢，Prolog推理的基礎(chǔ)是由一系列事實(shí)和事先編輯好的規(guī)則構(gòu)成的數(shù)據(jù)庫。對(duì)于提出的問題，推理機(jī)基于數(shù)據(jù)庫自動(dòng)進(jìn)行逆向演繹推理，并得出結(jié)果。

駕駛行為決策系統(tǒng)具體實(shí)現(xiàn)時(shí)，主體框架由C++編程實(shí)現(xiàn)，推理系統(tǒng)由Prolog動(dòng)態(tài)鏈接庫進(jìn)行調(diào)用，從而實(shí)現(xiàn)雙方信息交互[4]。在求解當(dāng)前行駛狀態(tài)下的感興趣區(qū)域時(shí)，首先將描述當(dāng)前場景的事實(shí)及事先離線編輯好的規(guī)則通過輸入函數(shù)輸入到數(shù)據(jù)庫，然后通過推理機(jī)得到問題求解答案。

2 馬爾科夫決策過程駕駛動(dòng)作生成

2.1 馬爾科夫決策過程簡介

馬爾科夫決策過程（MDP）是描述智能體（Agent）與環(huán)境之間相互作用的一種模型，可以看作是一個(gè)受控的馬爾科夫過程，用來處理動(dòng)態(tài)環(huán)境下不確定的序列式?jīng)Q策問題[5]。

其基本決策過程如下：首先，遍歷動(dòng)作集合中的所有動(dòng)作，每一個(gè)動(dòng)作在當(dāng)前狀態(tài)下通過轉(zhuǎn)移函數(shù)計(jì)算得到下一刻狀態(tài)，由每一個(gè)動(dòng)作及其對(duì)應(yīng)的下一個(gè)狀態(tài)通過回報(bào)函數(shù)的計(jì)算得到一個(gè)立即回報(bào)值，計(jì)算動(dòng)作值函數(shù)。然后將下一個(gè)狀態(tài)當(dāng)做當(dāng)前狀態(tài)，重復(fù)迭代上述步驟，更新動(dòng)作值函數(shù)，直到到達(dá)一定的迭代次數(shù)或到達(dá)局部目標(biāo)點(diǎn)，最后通過最優(yōu)動(dòng)作值函數(shù)推算出最優(yōu)動(dòng)作，并輸出給局部路徑規(guī)劃。

2.2 MDP模型求解核心函數(shù)

（1）狀態(tài)空間

狀態(tài)空間包括自動(dòng)駕駛車輛感興趣區(qū)域內(nèi)動(dòng)態(tài)實(shí)體的所有可能描述信息，本文將狀態(tài)空間定義為無人車及周圍其它車輛的空間存在狀態(tài)：

其中N為它車個(gè)數(shù)。對(duì)于自動(dòng)駕駛車輛自身，主要關(guān)注其在感興趣區(qū)域中的位置坐標(biāo)（xego，yego）、速度vego和航向角θego，而對(duì)于周圍車輛，除了關(guān)注其位置、速度和航向角之外，還要關(guān)注其駕駛意圖bi：

駕駛行為決策過程中，迭代過程的結(jié)束需要一個(gè)終止?fàn)顟B(tài)sterm來判斷，本文選取下述兩種情況作為結(jié)束標(biāo)志：無人車與靜、動(dòng)態(tài)障礙物發(fā)生碰撞或無人車到達(dá)目標(biāo)位置。當(dāng)?shù)竭_(dá)終止?fàn)顟B(tài)時(shí)，馬爾科夫過程不再進(jìn)行迭代，當(dāng)前感興趣區(qū)域內(nèi)的決策過程結(jié)束，等待感興趣區(qū)域的更新。

（2）動(dòng)作空間

動(dòng)作空間主要用于定義無人車所有可能選擇的駕駛動(dòng)作，包括橫向和縱向駕駛動(dòng)作指令。為方便車輛底盤控制系統(tǒng)理解上層駕駛指令，動(dòng)作空間需對(duì)抽象動(dòng)作指令進(jìn)行參數(shù)化表示，保證車輛狀態(tài)按照決策輸出進(jìn)行調(diào)整響應(yīng)。

表1 駕駛動(dòng)作參數(shù)化表示對(duì)應(yīng)關(guān)系

（3）轉(zhuǎn)移函數(shù)

狀態(tài)轉(zhuǎn)移函數(shù)用StateTransition表示，是對(duì)輸入的狀態(tài)Si和動(dòng)作a進(jìn)行計(jì)算，得到Δt后的下一時(shí)刻自動(dòng)駕駛車輛所在的狀態(tài)Si+1。

對(duì)于無人駕駛車輛，認(rèn)為無人駕駛車輛的自身狀態(tài)信息是準(zhǔn)確的，進(jìn)而其轉(zhuǎn)移模型由下面車輛運(yùn)動(dòng)學(xué)模型唯一確定：

對(duì)于ROI內(nèi)其它車輛，根據(jù)駕駛意圖預(yù)測得到的預(yù)測軌跡進(jìn)行計(jì)算。

（4）回報(bào)函數(shù)

回報(bào)函數(shù)用getReward表示，是對(duì)自主駕駛?cè)蝿?wù)完成程度的定量評(píng)估，通常根據(jù)安全性、舒適度、任務(wù)完成度和任務(wù)完成效率多個(gè)目標(biāo)屬性進(jìn)行定義，從而得到此狀態(tài)和動(dòng)作的評(píng)價(jià)，即：

其中，安全性是無人車關(guān)注的第一要素，必須保證無人車不和周圍車輛發(fā)生碰撞事故。若駕駛動(dòng)作a執(zhí)行后發(fā)生碰撞則得到負(fù)的回報(bào)值，用來懲罰動(dòng)作a，否則回報(bào)值為正，認(rèn)為執(zhí)行動(dòng)作a后的狀態(tài)安全。

駕駛行為決策結(jié)果還需保證行車過程中的穩(wěn)定性，避免車輛控制動(dòng)作頻繁的切換，以保證乘坐時(shí)的舒適性，當(dāng)有橫向動(dòng)作或縱向加減速時(shí)得到負(fù)的回報(bào)值。

任務(wù)完成度評(píng)價(jià)是為了使無人駕駛車輛行駛趨向目標(biāo)點(diǎn)，使其能夠完成駕駛?cè)蝿?wù)。執(zhí)行動(dòng)作后，若抵達(dá)當(dāng)前感興趣區(qū)域內(nèi)的局部目標(biāo)點(diǎn)時(shí)，給予正的回報(bào)值，以引導(dǎo)車輛向目標(biāo)位置行駛。任務(wù)完成效率評(píng)價(jià)是為了使無人駕駛車輛能夠以更高效的速度到達(dá)任務(wù)目標(biāo)點(diǎn)，也就是速度越大，相應(yīng)的獎(jiǎng)賞回報(bào)值也是越大的。但同時(shí)需要遵守交通規(guī)則，也就是行駛速度需在當(dāng)前ROI內(nèi)公路規(guī)定的最高限速vmax以內(nèi)，當(dāng)條件允許，無人駕駛車輛會(huì)以vmax的速度行駛。

（5）動(dòng)作值函數(shù)

動(dòng)作值函數(shù)是一個(gè)遞歸函數(shù)，用Qstar表示，首先檢測當(dāng)前狀態(tài)是否到達(dá)終止?fàn)顟B(tài)send，若到達(dá)則結(jié)束遞歸，然后判斷當(dāng)前迭代次數(shù)是否到達(dá)T，若到達(dá)則結(jié)束遞歸，否則對(duì)所有可能的動(dòng)作a進(jìn)行循環(huán)計(jì)算。

在輸入狀態(tài)Si和動(dòng)作a下，通過轉(zhuǎn)移函數(shù)StateTransition計(jì)算出自動(dòng)駕駛車輛下一刻會(huì)轉(zhuǎn)移到狀態(tài)Si+1，判斷狀態(tài)Si+1是否超出ROIbound范圍，若超出范圍進(jìn)行剪枝的操作，即直接返回，不進(jìn)行值函數(shù)的計(jì)算，也不計(jì)入可執(zhí)行動(dòng)作的數(shù)目，不超出則通過getReward函數(shù)計(jì)算狀態(tài)Si+1的即時(shí)回報(bào)值Reward。

接著通過下式計(jì)算所有動(dòng)作A的動(dòng)作值函數(shù)Q（s,a），其中Q（s',a'）通過Qstar函數(shù)進(jìn)行遞歸迭代計(jì)算。

其中，γ為折扣因子，并且0<γ<1，折扣因子保證了總收益的收斂性；R為回報(bào)函數(shù)。

（6）MDP函數(shù)

MDP決策算法函數(shù)根據(jù)輸入的狀態(tài)S、感興趣區(qū)域ROI信息進(jìn)行迭代計(jì)算，生成最優(yōu)動(dòng)作。首先對(duì)輸入的ROI信息進(jìn)行處理變?yōu)镽OIbound限制，包括ROI位置坐標(biāo)（x,y）的邊界、ROI所在車道的限速vmax，航向角θ的范圍限制（取決于自動(dòng)駕駛車輛的轉(zhuǎn)向性能）。

然后檢測當(dāng)前狀態(tài)是否到達(dá)終止?fàn)顟B(tài)sterm，若到達(dá)，則終止循環(huán)，等待感興趣區(qū)域更新，否則對(duì)所有可能的動(dòng)作a進(jìn)行動(dòng)作值函數(shù)計(jì)算。

最后通過下式可以求得最優(yōu)狀態(tài)值函數(shù)V*，也就獲得最優(yōu)動(dòng)作a*并作為決策動(dòng)作返回。

2.3 MDP核心算法實(shí)現(xiàn)流程

在自動(dòng)駕駛系統(tǒng)輸入行駛?cè)蝿?wù)后，根據(jù)邏輯推理機(jī)、感知系統(tǒng)、它車駕駛意圖預(yù)測模塊實(shí)時(shí)傳回的數(shù)據(jù)信息，初始化感興趣區(qū)域和當(dāng)前狀態(tài)。感興趣區(qū)域信息包括ROI區(qū)域坐標(biāo)、ROI區(qū)域內(nèi)車道數(shù)量、ROI區(qū)域內(nèi)的車速限制和ROI內(nèi)的局部目標(biāo)點(diǎn)sobj，當(dāng)前狀態(tài)包括自動(dòng)駕駛車輛和ROI內(nèi)它車的位置（x，y）、速度v和航向角θ。然后開始并每隔Δt調(diào)用一次MDP決策生成函數(shù)進(jìn)行最優(yōu)駕駛動(dòng)作的生成，并輸出到局部路徑規(guī)劃，直到到達(dá)終止?fàn)顟B(tài)sterm。

圖1 MDP核心算法實(shí)現(xiàn)流程

在每一次MDP決策之前，需要根據(jù)屬性ROIat對(duì)在ROI內(nèi)可能的動(dòng)作進(jìn)行篩選，以減少不必要的迭代計(jì)算時(shí)間。即當(dāng)ROIat為在路口，橫向動(dòng)作只可能是轉(zhuǎn)向動(dòng)作：左轉(zhuǎn)、直行、右轉(zhuǎn)；當(dāng)為在路上，橫向動(dòng)作只可能是換道動(dòng)作：左換道、車道保持、右換道。

在每一次MDP決策之后，執(zhí)行生成的駕駛動(dòng)作a*之后，根據(jù)邏輯推理機(jī)和感知系統(tǒng)實(shí)時(shí)的信息反饋，更新ROI信息和狀態(tài)S，作為下一次動(dòng)作生成的輸入?yún)?shù)。

3 仿真結(jié)果

仿真場景設(shè)置為：當(dāng)前路段為同向3車道，本車處于最右側(cè)車道。本車前方存在一緩慢行駛的它車。根據(jù)離線設(shè)置的規(guī)則庫進(jìn)行邏輯推理，生成當(dāng)前的感興趣區(qū)域及其屬性信息。然后通過馬爾科夫決策過程生成駕駛動(dòng)作指令，由圖4、圖5可知，橫向動(dòng)作為左換道后車道保持，縱向動(dòng)作依次為為加速、勻速、停車，實(shí)現(xiàn)了簡單場景的決策。

圖2 仿真場景

圖3 感興趣區(qū)域生成

圖4 決策路徑及速度

圖5 橫、縱向決策指令

4 總結(jié)與展望

（1）通過感興趣區(qū)域推理和馬爾科夫決策的有機(jī)協(xié)作可實(shí)現(xiàn)簡單交通場景下駕駛動(dòng)作的生成。

（2）在復(fù)雜交通場景決策中，本文決策算法的實(shí)時(shí)性仍有改進(jìn)提升的空間，構(gòu)建高效快速的MDP計(jì)算模型或結(jié)合自動(dòng)駕駛的任務(wù)特點(diǎn)對(duì)決策算法進(jìn)行改進(jìn)將是非常有價(jià)值的研究課題。

[1] 熊光明,李勇,王詩源. 基于有限狀態(tài)機(jī)的智能車輛交叉口行為預(yù)測與控制[J].北京理工大學(xué)學(xué)報(bào),2015,35(1):34-38.

[2] 杜明博.基于人類駕駛行為的無人駕駛車輛行為決策與運(yùn)動(dòng)規(guī)劃方法研究[D].合肥:中國科學(xué)技術(shù)大學(xué), 2016.

[3] 熊璐,康宇宸等.無人駕駛車輛行為決策系統(tǒng)研究[J].汽車技術(shù), 2018.

[4] 武桂鑫,許爍.C ++ 與Prolog 雙向數(shù)據(jù)交換實(shí)現(xiàn)混合控制架構(gòu)下機(jī)器人任務(wù)規(guī)劃[J].計(jì)算機(jī)應(yīng)用,2015.

[5] Sebastian Brechtel, Probabilistic MDP-Behavior Planning for Cars[J]. 2011 14th International IEEE Conference on Intelligent Transporta -tion Systems Washington, DC, USA. October 5-7, 2011.

Application of MDP and PROLOG in autopilot

Ban Bing, Yang Zhigang, Yang Hang

( Shaanxi heavy truck Co., Ltd., Shaanxi Xi'an 710200 )

In recent years, a new wave of research upsurge on autonomous driving has emerged, and technology of related fields have developed rapidly. The behavior decision-making system plays an important role in the framework of autonomous driving system. In this paper, the attention distribution mechanism of drivers' visual behavior during driving is used for reference, and driving actions are generated through the organic cooperation of region of interest reasoning and markov decision making. Finally, the decision-making instruction generation under simple scenes is realized through simulation.

Behavior decision-making; Region of interest; Markov decision making

U469.7

B

1671-7988(2019)24-37-04

U469.7

B

1671-7988(2019)24-37-04

10.16638/j.cnki.1671-7988.2019.24.012

班兵（1986.03-）男，中級(jí)工程師，就職于陜西重型汽車有限公司，從事整車性能及控制策略開發(fā)工作。