在上一節自動駕駛實時路徑規划算法簡介（RRT 和Lattice Planner）中介紹了
找到車輛要遵循的最佳幾何路徑有兩個方法：
a） 通過增量採樣或離散幾何結構（即增量搜索）找到最佳的動作序列。
b） 從多個最終狀態中找到最佳操作（即局部搜索）。
增量搜索我們在上一節（點擊閱讀自動駕駛實時路徑規划算法簡介（RRT 和Lattice Planner））介紹了。
接下來我們分享：
局部搜索
實時搜索整個圖（什麼是實時搜索點擊自動駕駛實時路徑規划算法簡介（RRT 和Lattice Planner））並不總是有效的；因此，一些方法使用有限的視界，無論是在時間還是空間上。
在局部搜索級別，用於道路自動駕駛的最流行的技術可能是搜索空間包含某個幾何曲線（例如迴旋曲線或樣條曲線）以及該曲線的幾個橫向位移。然後通過一個代價函數對每個候選路徑進行評估，考慮到距離和時間成本、加速和碰撞檢查。
橫向位移產生的路徑一般可分為兩類：
（i）車輛作用空間的橫向移動
（ii）車輛狀態空間中的橫向位移
下圖展示出了相對比較：
在複雜的動態環境中，橫向移動的軌跡可能無法很好地執行（Gu和Dolan，2012）。因為他不是朝著目標搜索整個狀態空間，這樣會在無限時間範圍內需要大量的計算能力（用於構建狀態空間）。Benenson等人提出的部分運動規劃（Partial Motion Planning-PMP）可以使用。PMP使用短時間範圍與RRT相結合，並利用不可避免碰撞狀態（ICS）的概念（即無法避免碰撞的車輛狀態定義）進行安全檢查。不可避免的碰撞狀態保證不會發生碰撞，但需要對車輛周圍環境有充分的了解（Althoff等人，2011年），而PMP方法通常接近最佳狀態保證（Kushleyev和khachev，2009年）。如下圖所示，如果找到不可避免碰撞狀態（ICS），則搜索替代路徑，並且在每個時刻以RRT方式展開步驟節點。
總之，橫向移動的軌跡和PMP方法都旨在找到適合車輛行駛的最佳下一個動作（就路徑作為一個動作而言）。迂迴軌跡在動作或狀態空間中採樣最終條件，而PMP方法使用RRT在有限的時間範圍內進行規劃。對於車道和道路邊界以及其他交通參與者的運動而言，對狀態空間進行採樣的技術可能會導致平滑和安全的路徑。這與PMP和對動作空間進行採樣的技術相矛盾，這可能導致適應大量障礙物處理的路徑不可行。
參考文獻：
1，Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions -Christos Katrakazas a , Mohammed Quddus a, , Wen-Hua Chen b,1 , Lipika Deka a
2，Partial Motion Planning Framework for ReactivePlanning Within Dynamic Environments
3，Multi-layer occupancy grid mapping for autonomous vehicles navigation
文中部分圖片版權歸其所有
*未經準許嚴禁轉載和摘錄-加入我們的知識星球Vehicle可以下載以上參考資料。
>>>>