--領取《汽車駕駛自動化分級》（GB/T 40429-2021）--
無人駕駛汽車路徑規劃是指在一定的環境模型基礎上，給定無人駕駛汽車起始點和目标點後，按照性能名額規劃出一條無碰撞、能安全到達目标點的有效路徑。
路徑規劃主要包含兩個步驟：建立包含障礙區域與自由區域的環境地圖，以及在環境地圖中選擇合适的路徑搜尋算法，快速實時地搜尋可行駛路徑。路徑規劃結果對車輛行駛起着導航作用。它引導車輛從目前位置行駛到達目标位置。
環境地圖表示方法
根據不同的表示形式，環境地圖表示方法主要分為度量地圖表示法，拓撲地圖表示法等。
度量地圖表示法
度量地圖表示法采用坐标系中的格栅是否被障礙物占據的方式來描述環境特征，分為幾何表示法和空間分解法。
幾何表示法利用包括點、線、多邊形在内的幾何元素來表示環境資訊。相比于其他環境地圖表示方式，幾何特征地圖更為緊湊，有利于位置估計和目辨別别；缺點是環境幾何特征提取困難。幾何特征地圖适合于在環境已知的室内環境提取一些簡單的幾何特征，而室外環境下的幾何特征較難提取。常用的幾何地圖有Voronoi圖、機率路圖等。
幾何表示法
停車場Voronoi圖
空間分解法是把環境分解為類似于格栅的局部單元，根據他們是否被障礙物占據來進行狀态描述。如果格栅單元被障礙物占據，則為障礙格栅；反之，則為自由格栅。空間分解法通常采用基于格栅大小的均勻分解法和遞階分解法。均勻分解法中的格栅大小均勻分布，占據格栅用數值表示。均勻分解法能夠快速直覺地融合傳感器資訊；但是，均勻分解法采用相同大小格栅會導緻存儲空間巨大，大規模環境下路徑規劃計算複雜度高。為了克服均勻分解法中存儲空間巨大的問題，遞階分解法把環境空間分解為大小不同的矩形區域，進而減少模型所占用的記憶體空間。
均勻分解法
四叉樹分解法
均勻格栅地圖是度量地圖路徑規劃中最常用的。它把環境分解為一系列離散的格栅節點。所有格栅節點大小統一，均勻分布。格栅用值占據方式來表示障礙物資訊。例如使用最簡單的二值表示方法，1表示障礙格栅，不可通行；0表示自由格栅。
當用均勻格栅地圖表示環境資訊後，格栅節點之間隻有建立一定的連接配接關系才能保證能從起點搜尋到目标點的有效路徑。
八連接配接方式
拓撲地圖表示法
拓撲地圖模型選用節點表示道路上的特定位置，并用節點與節點間的關系來表示道路間聯系。這種地圖表示方法具有結構簡單、存儲友善、全局連貫性好、規劃效率高、魯棒性強等特點，适合于大規模環境下的道路規劃，但它包含資訊量少，需借助其他傳感器來對道路環境做進一步描述。
路徑規劃算法
目前路徑規劃方法分類大緻如下：
路徑規劃圖
比較常用的路徑規劃算法為基于采樣的路徑規劃算法以及基于搜尋路徑規劃算法。
基于采樣的路徑規劃算法
基于采樣的路徑規劃算法很早便開始用于車輛的路徑規劃中，比較常見的基于采樣的規劃算法有機率圖算法（Probabilistic Road Map， PRM）和快速随機擴充樹算法（Rapidly-exploring Random Tree，RRT）。
機率圖算法是在規劃空間内随機選取N個節點，之後連接配接各節點，并去除與障礙物接觸的連線，由此得到一個可行路徑。顯然，當采樣點太少，或者分布不合理時，PRM算法是不完備的，但可以增加采樣點使該算法達到完備，是以PRM是機率完備但不是最優的。
PRM算法
快速随機擴充樹最初主要用于解決含有運動學限制的路徑規劃問題。由于RRT在狀态空間中采用随機采樣确定擴充節點，不需要預處理，搜尋速度快。是以這種算法作為一種快速搜尋算法在路徑規劃問題中獲得廣泛應用。
RRT算法
基于搜尋的路徑規劃算法
基于搜尋的路徑規劃算法通過搜尋表示環境資訊的環境地圖來獲得最終的路徑。比較有代表性的算法有Dijkstra算法和A算法。
Dijkstra算法是典型的廣度優先搜尋算法。它是一個按路徑長度遞增的次序産生的最短路徑的方法，是求解最短路徑的經典算法之一。Dijkstra算法是一種貪心算法，它在每一步都選擇局部最優解，以産生一個最優解。這也會導緻該算法的時間複雜度較高，在圖規模較大時，該算法的計算速度慢，很難滿足路徑規劃實時性的要求。
A*算法是經典的啟發式搜尋算法，它是由Dijkstra算法改進而來的。其最顯著的特點就是在搜尋過程中增加了啟發函數，通過給定啟發函數來減少搜尋節點，進而提高路徑搜尋效率。研究表明，A*算法搜尋得到的路徑能夠同時滿足實時性和最優性要求。
現實環境遠比這要複雜，良好的規劃必須建立對周邊環境的深刻了解，另外還需要建立大量的數學方程，以及需要考慮障礙物、車道線、路徑曲率、曲率變化率以及車輛速度、加速度等多種因素的影響。
轉載自網絡，文中觀點僅供分享交流，不代表本公衆号立場，如涉及版權等問題，請您告知，我們将及時處理。
-- END --