MDP及PROLOG在自動駕駛中的應用

班兵，楊志剛，楊航

MDP及PROLOG在自動駕駛中的應用

班兵，楊志剛，楊航

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

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

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

前言

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

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

1 基于規則的感興趣區域生成

人類駕駛員行車過程中對周圍環境的注意力分配具有目標驅動性，一般情況下，受目標地點和全局路徑規劃的影響，駕駛員的視覺注意力會選擇性地集中在局部目標區域附近，從而僅提取和理解小范圍區域內的環境動態信息，而在一定程度上忽略其它區域的信息。在結構化特征明顯的城市道路工況下，此種目標驅動性根據不同的駕駛任務可以細化到具體的道路實體上。如駕駛員在交叉路口進行左轉彎行駛時，駕駛員會將注意力集中在當前路段、交叉路口和左轉彎目標路段，依據感興趣區域內的實時交通動態信息決定下一步的駕駛動作。

駕駛行為決策系統中駕駛動作的生成是建立在對駕駛場景充分理解的基礎上的，而駕駛場景本體模型是場景描述的依據，因此在考慮駕駛場景信息層次性和關聯性的基礎上，建立無人駕駛車輛的本體概念模型。

本體模型包括實體類別定義及屬性描述。在給定駕駛場景相關實體類別的定義之后，實體的狀態信息及與其它實體的聯系通過數據屬性和關系屬性來描述。根據上述駕駛場景本體模型，可實現對自動駕駛車輛周圍環境中靜態實體、動態實體的狀態信息和相互間關系的充分描述，從而為進一步的邏輯推理做好準備。

感興趣區域生成規則中，車輛在路上狀態下（非路口區域）行駛，當前車道為最右側車道時的規則可描述為：

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

車輛V當前道路狀態為在路上，車輛V在車道X上，車道X是最右側車道，車道X的左側車道為車道Y，因此車輛V的感興趣區域為當前車道和左側車道。

Prolog是一種基于謂詞演算的高效率聲明式程序設計語言，是面向非數值計算的描述性語言，在符號處理和推理方面具有極大的優勢，Prolog推理的基礎是由一系列事實和事先編輯好的規則構成的數據庫。對于提出的問題，推理機基于數據庫自動進行逆向演繹推理，并得出結果。

駕駛行為決策系統具體實現時，主體框架由C++編程實現，推理系統由Prolog動態鏈接庫進行調用，從而實現雙方信息交互[4]。在求解當前行駛狀態下的感興趣區域時，首先將描述當前場景的事實及事先離線編輯好的規則通過輸入函數輸入到數據庫，然后通過推理機得到問題求解答案。

2 馬爾科夫決策過程駕駛動作生成

2.1 馬爾科夫決策過程簡介

馬爾科夫決策過程（MDP）是描述智能體（Agent）與環境之間相互作用的一種模型，可以看作是一個受控的馬爾科夫過程，用來處理動態環境下不確定的序列式決策問題[5]。

其基本決策過程如下：首先，遍歷動作集合中的所有動作，每一個動作在當前狀態下通過轉移函數計算得到下一刻狀態，由每一個動作及其對應的下一個狀態通過回報函數的計算得到一個立即回報值，計算動作值函數。然后將下一個狀態當做當前狀態，重復迭代上述步驟，更新動作值函數，直到到達一定的迭代次數或到達局部目標點，最后通過最優動作值函數推算出最優動作，并輸出給局部路徑規劃。

2.2 MDP模型求解核心函數

（1）狀態空間

狀態空間包括自動駕駛車輛感興趣區域內動態實體的所有可能描述信息，本文將狀態空間定義為無人車及周圍其它車輛的空間存在狀態：

其中N為它車個數。對于自動駕駛車輛自身，主要關注其在感興趣區域中的位置坐標（xego，yego）、速度vego和航向角θego，而對于周圍車輛，除了關注其位置、速度和航向角之外，還要關注其駕駛意圖bi：

駕駛行為決策過程中，迭代過程的結束需要一個終止狀態sterm來判斷，本文選取下述兩種情況作為結束標志：無人車與靜、動態障礙物發生碰撞或無人車到達目標位置。當到達終止狀態時，馬爾科夫過程不再進行迭代，當前感興趣區域內的決策過程結束，等待感興趣區域的更新。

（2）動作空間

動作空間主要用于定義無人車所有可能選擇的駕駛動作，包括橫向和縱向駕駛動作指令。為方便車輛底盤控制系統理解上層駕駛指令，動作空間需對抽象動作指令進行參數化表示，保證車輛狀態按照決策輸出進行調整響應。

表1 駕駛動作參數化表示對應關系

（3）轉移函數

狀態轉移函數用StateTransition表示，是對輸入的狀態Si和動作a進行計算，得到Δt后的下一時刻自動駕駛車輛所在的狀態Si+1。

對于無人駕駛車輛，認為無人駕駛車輛的自身狀態信息是準確的，進而其轉移模型由下面車輛運動學模型唯一確定：

對于ROI內其它車輛，根據駕駛意圖預測得到的預測軌跡進行計算。

（4）回報函數

回報函數用getReward表示，是對自主駕駛任務完成程度的定量評估，通常根據安全性、舒適度、任務完成度和任務完成效率多個目標屬性進行定義，從而得到此狀態和動作的評價，即：

其中，安全性是無人車關注的第一要素，必須保證無人車不和周圍車輛發生碰撞事故。若駕駛動作a執行后發生碰撞則得到負的回報值，用來懲罰動作a，否則回報值為正，認為執行動作a后的狀態安全。

駕駛行為決策結果還需保證行車過程中的穩定性，避免車輛控制動作頻繁的切換，以保證乘坐時的舒適性，當有橫向動作或縱向加減速時得到負的回報值。

任務完成度評價是為了使無人駕駛車輛行駛趨向目標點，使其能夠完成駕駛任務。執行動作后，若抵達當前感興趣區域內的局部目標點時，給予正的回報值，以引導車輛向目標位置行駛。任務完成效率評價是為了使無人駕駛車輛能夠以更高效的速度到達任務目標點，也就是速度越大，相應的獎賞回報值也是越大的。但同時需要遵守交通規則，也就是行駛速度需在當前ROI內公路規定的最高限速vmax以內，當條件允許，無人駕駛車輛會以vmax的速度行駛。

（5）動作值函數

動作值函數是一個遞歸函數，用Qstar表示，首先檢測當前狀態是否到達終止狀態send，若到達則結束遞歸，然后判斷當前迭代次數是否到達T，若到達則結束遞歸，否則對所有可能的動作a進行循環計算。

在輸入狀態Si和動作a下，通過轉移函數StateTransition計算出自動駕駛車輛下一刻會轉移到狀態Si+1，判斷狀態Si+1是否超出ROIbound范圍，若超出范圍進行剪枝的操作，即直接返回，不進行值函數的計算，也不計入可執行動作的數目，不超出則通過getReward函數計算狀態Si+1的即時回報值Reward。

接著通過下式計算所有動作A的動作值函數Q（s,a），其中Q（s',a'）通過Qstar函數進行遞歸迭代計算。

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

（6）MDP函數

MDP決策算法函數根據輸入的狀態S、感興趣區域ROI信息進行迭代計算，生成最優動作。首先對輸入的ROI信息進行處理變為ROIbound限制，包括ROI位置坐標（x,y）的邊界、ROI所在車道的限速vmax，航向角θ的范圍限制（取決于自動駕駛車輛的轉向性能）。

然后檢測當前狀態是否到達終止狀態sterm，若到達，則終止循環，等待感興趣區域更新，否則對所有可能的動作a進行動作值函數計算。

最后通過下式可以求得最優狀態值函數V*，也就獲得最優動作a*并作為決策動作返回。

2.3 MDP核心算法實現流程

在自動駕駛系統輸入行駛任務后，根據邏輯推理機、感知系統、它車駕駛意圖預測模塊實時傳回的數據信息，初始化感興趣區域和當前狀態。感興趣區域信息包括ROI區域坐標、ROI區域內車道數量、ROI區域內的車速限制和ROI內的局部目標點sobj，當前狀態包括自動駕駛車輛和ROI內它車的位置（x，y）、速度v和航向角θ。然后開始并每隔Δt調用一次MDP決策生成函數進行最優駕駛動作的生成，并輸出到局部路徑規劃，直到到達終止狀態sterm。

圖1 MDP核心算法實現流程

在每一次MDP決策之前，需要根據屬性ROIat對在ROI內可能的動作進行篩選，以減少不必要的迭代計算時間。即當ROIat為在路口，橫向動作只可能是轉向動作：左轉、直行、右轉；當為在路上，橫向動作只可能是換道動作：左換道、車道保持、右換道。

在每一次MDP決策之后，執行生成的駕駛動作a*之后，根據邏輯推理機和感知系統實時的信息反饋，更新ROI信息和狀態S，作為下一次動作生成的輸入參數。

3 仿真結果

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

圖2 仿真場景

圖3 感興趣區域生成

圖4 決策路徑及速度

圖5 橫、縱向決策指令

4 總結與展望

（1）通過感興趣區域推理和馬爾科夫決策的有機協作可實現簡單交通場景下駕駛動作的生成。

（2）在復雜交通場景決策中，本文決策算法的實時性仍有改進提升的空間，構建高效快速的MDP計算模型或結合自動駕駛的任務特點對決策算法進行改進將是非常有價值的研究課題。

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

[2] 杜明博.基于人類駕駛行為的無人駕駛車輛行為決策與運動規劃方法研究[D].合肥:中國科學技術大學, 2016.

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

[4] 武桂鑫,許爍.C ++ 與Prolog 雙向數據交換實現混合控制架構下機器人任務規劃[J].計算機應用,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-）男，中級工程師，就職于陜西重型汽車有限公司，從事整車性能及控制策略開發工作。