碼頭作為航運(yùn)的起點(diǎn)和終點(diǎn)，是貿(mào)易與物流的重要樞紐。而碼頭水平運(yùn)輸堆場(chǎng)作業(yè)一直受人為因素影響（貨運(yùn)司機(jī)數(shù)量、司機(jī)疲勞駕駛、人工調(diào)度等）無(wú)法實(shí)現(xiàn)高效協(xié)同自動(dòng)化作業(yè)。

隨著人工智能，5G等技術(shù)的的成熟，實(shí)現(xiàn)碼頭生產(chǎn)自動(dòng)化成為港口未來(lái)發(fā)展的趨勢(shì)。此前華為聯(lián)合天津港口打造了智能水平運(yùn)輸系統(tǒng)，實(shí)現(xiàn)了港口L4級(jí)的自動(dòng)駕駛。

該智能水平運(yùn)輸系統(tǒng)，華為采用了全局路徑規(guī)劃算法，基于車(chē)輛運(yùn)動(dòng)學(xué)特征，可以保障單車(chē)行駛的平順?lè)€(wěn)定，且實(shí)現(xiàn)IGV在路口并行轉(zhuǎn)彎，是多車(chē)協(xié)同駕駛安全高效的前提。

同時(shí)，云端的動(dòng)態(tài)短路徑規(guī)劃，解決了碼頭作業(yè)場(chǎng)景多變、任務(wù)需實(shí)時(shí)調(diào)整的難題，實(shí)現(xiàn)全局效率最優(yōu)。

為了實(shí)現(xiàn)港口的L4級(jí)自動(dòng)駕駛，華為可能用了哪些路徑規(guī)劃算法？

全局路徑規(guī)劃,就是在路網(wǎng)中，搜索到一條最優(yōu)路徑，以便可以到達(dá)目標(biāo)地點(diǎn)。為了實(shí)現(xiàn)這一目標(biāo)，目前使用最廣泛的兩種全局路徑搜索算法：

1.Dijkstra算法

一種用于解決單源最短路徑問(wèn)題的圖算法，該算法可以找到從給定起點(diǎn)到所有其他頂點(diǎn)的最短路徑。Dijkstra算法的基本思想是通過(guò)不斷更新起點(diǎn)到各個(gè)頂點(diǎn)的最短距離來(lái)逐步擴(kuò)展最短路徑的范圍。它維護(hù)一個(gè)距離數(shù)組，記錄起點(diǎn)到各個(gè)頂點(diǎn)的當(dāng)前最短距離，同時(shí)使用一個(gè)集合來(lái)存儲(chǔ)已經(jīng)確定最短路徑的頂點(diǎn)。 算法的步驟如下：

• 初始化距離數(shù)組和集合。將起點(diǎn)的距離設(shè)為0，其他頂點(diǎn)的距離設(shè)為無(wú)窮大，將所有頂點(diǎn)加入集合。

• 從集合中選擇距離起點(diǎn)最近的頂點(diǎn)，將其標(biāo)記為已確定最短路徑。

• 更新與該頂點(diǎn)相鄰頂點(diǎn)的距離。如果經(jīng)過(guò)已確定最短路徑的頂點(diǎn)到達(dá)相鄰頂點(diǎn)的距離更短，則更新距離數(shù)組。

• 重復(fù)步驟2和步驟3，直到集合為空或者所有頂點(diǎn)都被標(biāo)記為已確定最短路徑。

經(jīng)過(guò)該算法，可以得到起點(diǎn)到其他所有頂點(diǎn)的最短路徑以及對(duì)應(yīng)的距離。Dijkstra算法的時(shí)間復(fù)雜度為O(V^2)，其中V是頂點(diǎn)的數(shù)量。在使用優(yōu)先隊(duì)列等數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化后，時(shí)間復(fù)雜度可以降低到O((V+E)logV)，其中E是邊的數(shù)量。

2.A*算法

是一種基于采樣搜索的粗略路徑規(guī)劃算法，是要在地圖上找到一條從起到到終點(diǎn)的最短路徑。該算法使用了兩種評(píng)估函數(shù)來(lái)決定下一步的移動(dòng)：g(n)表示起點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)，h（n）表示從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的預(yù)估代價(jià)。 A*算法通過(guò)計(jì)算每個(gè)節(jié)點(diǎn)的f(n) = g(n) + h(n)來(lái)選擇下一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展。它使用一個(gè)優(yōu)先級(jí)隊(duì)列來(lái)存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)，并按照f(shuō)(n)的值進(jìn)行排序。在每次迭代中，A算法選擇具有最小f(n)值的節(jié)點(diǎn)進(jìn)行擴(kuò)展。 該算法在搜索過(guò)程中維護(hù)了一個(gè)開(kāi)放列表和一個(gè)關(guān)閉列表。開(kāi)放列表存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)，關(guān)閉列表存儲(chǔ)已經(jīng)擴(kuò)展過(guò)的節(jié)點(diǎn)。在每次迭代中，A*算法將當(dāng)前節(jié)點(diǎn)加入關(guān)閉列表，并將其相鄰的未訪(fǎng)問(wèn)節(jié)點(diǎn)加入開(kāi)放列表。 A*算法在滿(mǎn)足一些條件下能夠保證找到最短路徑。首先，評(píng)估函數(shù)h(n)必須是一致的（即滿(mǎn)足三角不等式），這樣保證了A算法不會(huì)錯(cuò)過(guò)最優(yōu)解。其次，如果h(n)是準(zhǔn)確的，則A*算法能夠找到最短路徑。 總結(jié)來(lái)說(shuō)，A*算法是一種常用的啟發(fā)式搜索算法，適用于解決圖搜索問(wèn)題，并且能夠找到最短路徑。 A*算法是如何搜索并找到一條既短又無(wú)障礙的路徑，非常詳細(xì)的算法原理分享，可以參考這篇文章：路徑規(guī)劃之A*算法

華為在打造L4級(jí)無(wú)人駕駛港口的時(shí)候，除了使用全局路徑規(guī)劃算法來(lái)實(shí)現(xiàn)多車(chē)協(xié)同駕駛之外，還用了局部路徑規(guī)劃算法來(lái)解決碼頭作業(yè)場(chǎng)景多變，任務(wù)實(shí)時(shí)調(diào)整運(yùn)作的難題。

自動(dòng)駕駛常用局部路徑規(guī)劃算法有哪些？

局部路徑規(guī)劃根據(jù)當(dāng)前環(huán)境和目標(biāo)位置，決定如何在局部區(qū)域內(nèi)安全、高效地規(guī)劃出一條路徑。全局路徑規(guī)劃確定了整個(gè)形成的大致路線(xiàn)，而局部路徑規(guī)劃負(fù)責(zé)處理具體的障礙物避讓和路徑調(diào)整。需要借助傳感器實(shí)時(shí)獲得障礙物信息來(lái)響應(yīng)環(huán)境變化。

運(yùn)動(dòng)規(guī)劃的第一步往往采用隨機(jī)采樣算法，走一步看一步，不斷更新行駛軌跡。代表算法有基于采樣的方法：PRM、RRT、Lattice。這類(lèi)算法通過(guò)隨機(jī)采樣的方式在地圖上生成子節(jié)點(diǎn)，并與父節(jié)點(diǎn)相連，若連線(xiàn)與障礙物無(wú)碰撞風(fēng)險(xiǎn)，則擴(kuò)展該子節(jié)點(diǎn)。重復(fù)上述步驟，不斷擴(kuò)展樣本點(diǎn)，直到生成一條連接起點(diǎn)到終點(diǎn)的路徑。

1.PRM算法

一種經(jīng)典的采樣方法，主要包含三個(gè)階段：一是采樣階段、二是碰撞檢測(cè)階段，三是搜索階段。

采樣階段：在地圖空間進(jìn)行均勻的隨機(jī)采樣，也就是對(duì)地圖進(jìn)行系數(shù)采樣，將大地圖簡(jiǎn)化為較少的采樣點(diǎn)

碰撞檢測(cè)階段：剔除落在障礙物上的采樣點(diǎn)，并將剩下的點(diǎn)與其一定距離范圍內(nèi)的點(diǎn)相連，同事剔除穿越障礙物的鏈接，從而構(gòu)成一張無(wú)向圖。

在搜索階段：利用全局路徑規(guī)劃算法章節(jié)介紹的搜索算法（Dijkstra、A*等）在無(wú)向圖中進(jìn)行搜索，從而找出一條起點(diǎn)A到終點(diǎn)B之間的可行路徑。

2.RRT算法

RRT算法是一種對(duì)狀態(tài)空間隨機(jī)采樣的算法，通過(guò)對(duì)采樣點(diǎn)進(jìn)行碰撞檢測(cè)，避免了對(duì)空間的精確建模帶來(lái)的大計(jì)算量，能夠有效地解決高維空間和復(fù)雜的約束的路徑規(guī)劃問(wèn)題?？梢暂p松處理障礙物和差分約束的問(wèn)題，被廣泛應(yīng)用于機(jī)器人路徑規(guī)劃。

3.Lattice算法

第一步，采集足夠多的軌跡，提供盡可能多的選擇；第二步計(jì)算每一條軌跡計(jì)算的cost，這個(gè)cost考慮了軌跡的可行性，安全性等因素。第三部，循環(huán)檢測(cè)，在這個(gè)循環(huán)檢測(cè)的過(guò)程中，每次會(huì)先挑選出cost最低的軌跡，對(duì)其進(jìn)行物理限制檢測(cè)和碰撞檢測(cè)。如果挑出來(lái)的軌跡不能同時(shí)通過(guò)這兩個(gè)檢測(cè)，就將其篩除，考察下一條cost最低的軌跡。

局部路徑規(guī)劃算法，除了這些，還有多項(xiàng)式曲線(xiàn)、貝塞爾曲線(xiàn)等方法。可以參照往期分享的常用規(guī)劃算法分享：自動(dòng)駕駛路徑規(guī)劃五大常用算法

為了實(shí)現(xiàn)自動(dòng)駕駛無(wú)人駕駛，這些常用規(guī)劃算法，也是我們自動(dòng)駕駛規(guī)劃算法訓(xùn)練營(yíng)重點(diǎn)學(xué)習(xí)的內(nèi)容，如果你也想在無(wú)人駕駛領(lǐng)域，深研規(guī)劃算法，可以加入我們的訓(xùn)練營(yíng)學(xué)習(xí)！

本訓(xùn)練營(yíng)詳細(xì)介紹了自動(dòng)駕駛系統(tǒng)中規(guī)劃與感知、高精地圖、控制等模塊之間的關(guān)系、數(shù)據(jù)信息流向及數(shù)據(jù)處理，深入講解A*、Lattice等常用規(guī)劃算法原理以及雙環(huán)PID、LQR等控制算法原理，系統(tǒng)梳理了規(guī)劃、控制算法代碼；同時(shí)通過(guò)實(shí)踐演示、學(xué)員練習(xí)，帶領(lǐng)學(xué)員完成路徑規(guī)劃、循跡行駛、借道繞障行駛等仿真場(chǎng)景功能代碼學(xué)習(xí)與實(shí)現(xiàn)。

訓(xùn)練營(yíng)通過(guò)互動(dòng)直播教學(xué)、學(xué)習(xí)群答疑輔導(dǎo)、項(xiàng)目任務(wù)指導(dǎo)，為學(xué)習(xí)者提供靈活的學(xué)習(xí)途徑、創(chuàng)造即時(shí)學(xué)習(xí)的良好氛圍，引導(dǎo)學(xué)習(xí)者養(yǎng)成獨(dú)立思考、學(xué)以致用的良好學(xué)習(xí)習(xí)慣。課程收益

• 學(xué)會(huì)開(kāi)發(fā)環(huán)境配置、開(kāi)發(fā)工具基本使用方法；

• 學(xué)會(huì)基于A*算法的全局路徑規(guī)劃及調(diào)參方法；

• 學(xué)會(huì)基于Lattice算法的局部路徑規(guī)劃及調(diào)參方法；

• 學(xué)會(huì)基于規(guī)劃軌跡實(shí)現(xiàn)車(chē)輛橫、縱向控制及參數(shù)調(diào)試方法；

• 能夠在開(kāi)發(fā)平臺(tái)上實(shí)現(xiàn)循跡行駛、借道繞障行駛仿真功能。

課程大綱

• 自動(dòng)駕駛路徑規(guī)劃概述

• 開(kāi)發(fā)環(huán)境配置、工具鏈及開(kāi)發(fā)平臺(tái)熟悉

• 全局路徑規(guī)劃

• 局部路徑規(guī)劃

• 車(chē)輛橫縱向控制

• 總結(jié)、答疑

  （詳細(xì)課程目錄可以聯(lián)系堂主查看）

面向?qū)ο?/strong>

• 希望從事自動(dòng)駕駛規(guī)劃算法研發(fā)崗位的在校生；

• 希望系統(tǒng)學(xué)習(xí)自動(dòng)駕駛規(guī)劃控制實(shí)際應(yīng)用的在崗研發(fā)工程師；

• 自動(dòng)駕駛相關(guān)產(chǎn)業(yè)產(chǎn)品經(jīng)理、項(xiàng)目經(jīng)理等；

• 希望了解自動(dòng)駕駛規(guī)劃與控制研發(fā)的相關(guān)人士。

咨詢(xún)報(bào)名

學(xué)習(xí)形式：在線(xiàn)直播，

上課地點(diǎn)：班級(jí)群集中上課、互動(dòng)答疑

聯(lián)系人：汽車(chē)學(xué)堂堂主

標(biāo)簽：路徑規(guī)劃L4級(jí)自動(dòng)駕駛全局路徑規(guī)劃局部路徑規(guī)劃