智能汽車測控技術(shù) 課件 第9章-第一講 智能汽車路徑規(guī)劃基本概念 1

智能汽車測控技術(shù)第1講智能汽車路徑規(guī)劃基本概念

1.案例導(dǎo)入

當(dāng)面對復(fù)雜的地圖時，我們可以通過思考判斷找到合適的路徑，那么智能汽車在行駛時，又怎么樣尋找一條最優(yōu)路徑呢?第1講智能汽車路徑規(guī)劃基本概念

2.基本概念

智能汽車行駛中，“路徑規(guī)劃”這一模塊起到了什么作用呢？

路徑規(guī)劃模塊承接上層感知預(yù)測結(jié)果、建圖和定位結(jié)果、網(wǎng)聯(lián)通信信息，依次完成路由尋徑（Routing）、行為決策（BehavioralDecision）、動作規(guī)劃（MotionPlanning）三類任務(wù)，并將規(guī)劃輸出的運動軌跡傳送至車輛運動控制模塊，供其完成軌跡跟蹤和車輛控制。第1講智能汽車路徑規(guī)劃基本概念2.基本概念路由尋徑：作用：是在道路網(wǎng)絡(luò)層面上指導(dǎo)智能汽車規(guī)劃控制模塊

選擇一條最優(yōu)（時間最短、距離最短等）行駛路

徑，從而實現(xiàn)從出行起點到達出行終點的目標(biāo)。第1講智能汽車路徑規(guī)劃基本概念2.基本概念實現(xiàn)：

通常可將路網(wǎng)上的路由尋徑任務(wù)抽象成一個在帶權(quán)有向圖上的最短路徑搜索問題。

通過在道路上進行分散“撒點”對智能汽車可能經(jīng)過的道路抽樣經(jīng)點與點之間由有向帶權(quán)的邊連接，邊的權(quán)值代表智能汽車從一個點行駛到另一個點的潛在代價通過算法進行路徑搜索問題求解（A*、Dijkstra）第1講智能汽車路徑規(guī)劃基本概念2.基本概念行為決策：作用:獲得路由尋徑模塊確定智能汽車在路網(wǎng)上的行駛路線后，根據(jù)具體任務(wù)不同，輸出多種不同指令。車道跟車遇到交通燈避讓行人路口會車第1講智能汽車路徑規(guī)劃基本概念2.基本概念智能汽車需要在匯聚多源多類信息的基礎(chǔ)上做出行為決策，這些信息主要包括：（1）路由尋徑結(jié)果：智能汽車為了到達目的地所需進入的目標(biāo)車道；（2）車輛當(dāng)前自身狀態(tài)：自車位置、速度、朝向、所處車道、路徑尋由結(jié)果指向的后續(xù)目標(biāo)車道等；（3）歷史決策信息：上個周期的車輛行為決策結(jié)果，如跟車、停車、轉(zhuǎn)彎、換道等；（4）周邊障礙物信息：車輛周邊一定距離范圍內(nèi)的動靜態(tài)障礙物信息，例如道路及附屬設(shè)施，臨近機動車和非機動車的速度、位置、方向角、短時行駛意圖和軌跡；（5）周邊交通標(biāo)識和交通規(guī)則：例如道路限速、標(biāo)志標(biāo)線、前方路口信號燈等。第1講智能汽車路徑規(guī)劃基本概念2.基本概念

智能汽車所處理的信息類型復(fù)雜多樣，且駕駛場景復(fù)雜多變，因此行為決策需依賴的理論方法通常高度復(fù)雜Junior行為決策系統(tǒng)第1講智能汽車路徑規(guī)劃基本概念2.基本概念運動規(guī)劃：作用：在基于特定環(huán)境地圖在一個較小時空區(qū)域

內(nèi)為智能汽車規(guī)劃一條滿足車輛動力學(xué)、

安全性、舒適性等約束的無碰撞路徑。

此模塊需要具備對上層全局路徑規(guī)劃結(jié)果的跟蹤能力，以及對行為決策結(jié)果的執(zhí)行和反饋能力。第1講智能汽車路徑規(guī)劃基本概念2.基本概念

由于行為決策模塊和運動規(guī)劃模塊的任務(wù)緊密聯(lián)系，所以在智能汽車系統(tǒng)設(shè)計時，二者通常共享感知、通信與定位信息。第1講智能汽車路徑規(guī)劃基本概念2.基本概念路徑平滑：

車輛實際運行軌跡總表現(xiàn)為類似螺旋線的平滑曲線，而運動規(guī)劃模塊輸出的通常為由離散點構(gòu)成的局部路徑折線，怎么辦？

通常需要將路徑折線進一步優(yōu)化為二維平面上的時空曲線，即曲線擬合方法，常見的擬合方法包括B樣條曲線法、QP算法等。第1講智能汽車路徑規(guī)劃基本概念2.基本概念

根據(jù)與局部路徑上離散點的空間關(guān)系，曲線擬合方法可分為兩種：點點通過法：指擬合曲線通過運動規(guī)劃算法輸出的所有離散路徑點，進而根據(jù)擬合所得曲線方程以足夠小的步長通過插值獲取相鄰離散點之間若干個數(shù)據(jù)點的坐標(biāo)，并用直線連接。平均通過法:指擬合曲線不通過上層運動規(guī)劃模塊輸出的所有離散路徑點，而是最小化擬合曲線與離散路徑點之間的距離，使得擬合曲線的走勢反映了這些路徑點的變化趨勢。第1講智能汽車路徑規(guī)劃基本概念2.基本概念想要進行路徑規(guī)劃，都需要什么呢？常用路徑規(guī)劃算法基于圖搜索的路徑規(guī)劃基于采樣的路徑規(guī)劃基于人工智能的路徑規(guī)劃添加標(biāo)題深度/廣度優(yōu)先搜索DijkstraA*RRTRRT*蟻群算法遺傳算法1、路徑規(guī)劃算法第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建2、靜態(tài)環(huán)境地圖構(gòu)建拓撲法柵格法自由空間法Voronoi圖法可視圖法常用方法第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建下面先來介紹靜態(tài)環(huán)境地圖的構(gòu)造方法。行駛環(huán)境地圖構(gòu)建方法主要分為兩類：1、動態(tài)環(huán)境建圖（前沿性研究）2、靜態(tài)環(huán)境建圖（發(fā)展相對成熟，主要介紹）第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建一、拓撲法基本思想：降維

拓撲法將智能汽車所處環(huán)境用圖形來表示，不同的地點用點表示，不同點的相鄰可達性用弧來表示。1、先將車輛所處整體空間劃分為具有拓撲特征一致的子空間；2、再分析各個子空間之間的連通性，據(jù)此建立拓撲網(wǎng)絡(luò)；3、智能汽車在此拓撲網(wǎng)絡(luò)上尋找起始點到目標(biāo)點的最優(yōu)拓撲路徑；4、最后將拓撲網(wǎng)絡(luò)中的最優(yōu)路徑還原至實際幾何路徑。第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建難點：建立合適的拓撲空間優(yōu)點：能夠確保找到無碰撞路徑第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建二、柵格法

柵格法是用大小相等的柵格將智能汽車行駛區(qū)域劃分為柵格地圖，應(yīng)用柵格對障礙物的位置進行標(biāo)記，進而由這些柵格構(gòu)成一個連通圖，依據(jù)障礙物柵格位置，在此圖上尋找一條從起始柵格到目標(biāo)柵格無碰撞的最優(yōu)路徑。關(guān)鍵：采用不同的編碼形式標(biāo)記柵格中是

否存在障礙物第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建步驟：第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建01柵格法精確柵格法：將車輛行駛空間分解成多個形狀不一的單元，這些柵格的組合與行駛空間精確相等02近似柵格法（概率柵格法）：似柵格法所采用的柵格均為固定形狀，通常為矩形梯形柵格分解示意圖：第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建三、可視圖法可視圖法：將智能汽車看成一個點，車輛、目標(biāo)點和多邊形障礙物各頂點之間組合連接，確保這些直線連接線均不與障礙物相交，從而形成一張圖，即可視圖

目標(biāo)點與多邊形頂點的連線不可穿過障礙物，這些直線即為所有可能路徑，即直線是“可視的”。第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建路徑規(guī)劃任務(wù)搜索從起點到目標(biāo)點經(jīng)過這些可視直線的最短距離問題優(yōu)點：直觀簡單缺點：如果障礙物之間間距過小，就有可能使得汽車與障礙物產(chǎn)生接觸，而如果過分縮小模擬車輛的尺寸，則會增加最優(yōu)化路徑求解的時間。第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建四、Voronoi圖法

與可視圖類似，Voronoi圖也是一種圍繞靜態(tài)障礙物建圖的方法

Voronoi圖由直線段和拋物線段構(gòu)成，其中直線段由兩個障礙物的頂點或兩個障礙物的邊定義而成，直線段上所有點必須距離障礙物的頂點或障礙物的邊相等，另外拋物線段由一個障礙物的頂點和一個障礙物的邊定義生成，拋物線段要求與障礙物頂點和障礙物的邊有相同距離。第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建優(yōu)點：實時性好、生成路徑比較遠離障礙、路徑比較平滑。缺點：不能保證路徑最優(yōu)。障礙物環(huán)境中的Voronoi圖第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建五、自由空間法

自由空間法是采用預(yù)先定義的如廣義錐形和凸多邊形等基本形狀模擬車輛及其行駛環(huán)境中的障礙物，進而分割車輛行駛空間并將其表示為連通圖，然后通過搜索連通圖來進行路徑規(guī)劃。1、首先選擇某個障礙物為研究對象，從其中一個頂點出發(fā)，將該頂點與其他障礙物的頂點相連；2、在所有連線當(dāng)中，將穿過障礙物的連線去掉，同時去掉多余的連接線，在所有的連線中，挑選能使得連