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

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

1.案例導(dǎo)入

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

2.基本概念

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

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

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

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

通?？蓪⒙肪W(wǎng)上的路由尋徑任務(wù)抽象成一個(gè)在帶權(quán)有向圖上的最短路徑搜索問題。

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

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

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

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

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

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

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

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

根據(jù)與局部路徑上離散點(diǎn)的空間關(guān)系，曲線擬合方法可分為兩種：點(diǎn)點(diǎn)通過法：指擬合曲線通過運(yùn)動(dòng)規(guī)劃算法輸出的所有離散路徑點(diǎn)，進(jìn)而根據(jù)擬合所得曲線方程以足夠小的步長(zhǎng)通過插值獲取相鄰離散點(diǎn)之間若干個(gè)數(shù)據(jù)點(diǎn)的坐標(biāo)，并用直線連接。平均通過法:指擬合曲線不通過上層運(yùn)動(dòng)規(guī)劃模塊輸出的所有離散路徑點(diǎn)，而是最小化擬合曲線與離散路徑點(diǎn)之間的距離，使得擬合曲線的走勢(shì)反映了這些路徑點(diǎn)的變化趨勢(shì)。第1講智能汽車路徑規(guī)劃基本概念2.基本概念想要進(jìn)行路徑規(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)建拓?fù)浞鸥穹ㄗ杂煽臻g法Voronoi圖法可視圖法常用方法第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建下面先來介紹靜態(tài)環(huán)境地圖的構(gòu)造方法。行駛環(huán)境地圖構(gòu)建方法主要分為兩類：1、動(dòng)態(tài)環(huán)境建圖（前沿性研究）2、靜態(tài)環(huán)境建圖（發(fā)展相對(duì)成熟，主要介紹）第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建一、拓?fù)浞ɑ舅枷耄航稻S

拓?fù)浞▽⒅悄芷囁幁h(huán)境用圖形來表示，不同的地點(diǎn)用點(diǎn)表示，不同點(diǎn)的相鄰可達(dá)性用弧來表示。1、先將車輛所處整體空間劃分為具有拓?fù)涮卣饕恢碌淖涌臻g；2、再分析各個(gè)子空間之間的連通性，據(jù)此建立拓?fù)渚W(wǎng)絡(luò)；3、智能汽車在此拓?fù)渚W(wǎng)絡(luò)上尋找起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)拓?fù)渎窂剑?、最后將拓?fù)渚W(wǎng)絡(luò)中的最優(yōu)路徑還原至實(shí)際幾何路徑。第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建難點(diǎn)：建立合適的拓?fù)淇臻g優(yōu)點(diǎn)：能夠確保找到無碰撞路徑第1講智能汽車路徑規(guī)劃基本概念3.地圖構(gòu)建二、柵格法

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

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

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

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

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

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