帶硬體輔助儲存的自動駕駛路徑規劃加速方法

語言: CN / TW / HK

arXiv上2022年5月5日上傳的論文“Accelerating Path Planning for Autonomous Driving with Hardware-assisted Memorization“,作者來自Cornell大學。

動態障礙物的自動駕駛路徑規劃是一個挑戰,因為需要在滿足實時約束的同時執行更高維搜尋(包括時間)。作者提出了一種演算法-硬體協同優化方法,加速基於高維搜尋空間的路徑規劃。首先,將節點和障礙物對映到低維空間並存儲最近的搜尋結果,減少最近鄰搜尋和碰撞檢測的時間。然後,提出一種用於高效儲存的硬體擴充套件方法。在一個現代處理器和一個迴圈級(cycle- level)模擬器的實驗結果表明,該演算法的執行時間顯著縮短。

路徑規劃的及時執行對車輛的安全和效率至關重要。修剪(pruning)是被用來在軟體中加速的方法。針對RRT、PRM和A*等演算法,人們用不同的硬體技術,包括FPGA或ASIC,還提出了特定於演算法的加速器。雖然這些路徑規劃加速器確實解決了特定場景中的個人需求,但不是針對自動駕駛,也不考慮動態障礙。

此外,隨著法規(regulation)和演算法的不斷髮展,選擇和修改加速路徑規劃演算法的靈活性也非常重要。然而,許多現有路徑規劃加速器一次設計只考慮一個特定的演算法,大多數超參在設計/程式設計時固化到加速器硬體中。雖然這些硬體化演算法在釋出時表現良好,並在目標場景提供良好的效能,但不夠靈活,無法適應新的或修改演算法。

  • 動態障礙物的對付

自動駕駛車輛在2D平面執行路徑規劃。在不同的時間,障礙物將位於2D平面的不同位置。2D平面的動態障礙物成為一組障礙物,在三維空間的座標可以用(x,y,t)來描述。

可以有效地將帶有動態障礙物的2D規劃問題視為3D規劃問題。然而,時間維度不同於普通的空間維度,這需要對其進行額外約束。由於時間只沿一個方向移動,對於路徑P上i<j的任意兩個節點(xi,yi,ti)和(xj,yj,tj),必須保證ti<t j。在RRT選擇最近鄰時,將強制執行附加約束。

  • 基於軟體的儲存RRT演算法

儲存(memorization) 來減少路徑規劃的總執行時間。在傳統 基於取樣的規劃 (比如RRT)中,大部分執行時間都花在尋找最近鄰(NN)以及檢測會不會碰撞。為了加速這些過程,儲存最近訪問的節點和碰撞狀態,以便跳過一些類似的查詢。

如圖顯示了整個方法的流程:基準(藍色箭頭)規劃流程和改進(橙色箭頭)規劃流程。

在基準RRT,所有迭代執行耗時的最近鄰搜尋和碰撞檢測。然而用一個名為Morton store的小型資料儲存器(以Morton空間歸檔曲線命名)記住基準最近鄰搜尋和碰撞檢測的關鍵資訊。對每個迭代,首先檢查Morton store,以便有機會跳過耗時的基準NN搜尋和碰撞檢測。

規模有限的Morton store的運作如下。

先計算樹節點座標 Xn =(Xn,yn,tn)以及障礙物 Xo =(x,y,t)的Morton codes Mn 和 Mo。Morton code將點(x,y,t)從3D空間ooo投影到1D曲線,同時保持空間位置(32位整數)。Morton codes Mn 和 Mo 是64位數,用作相應節點和障礙物的標記。為調整投影粒度,遮蔽Morton codes的k個最低有效位

其RRT演算法虛擬碼如下:

這個解決方案必須對每段(segment)路徑執行精確的碰撞檢測,以確保安全(無碰撞)。與使用Morton store進行精確碰撞檢測節省的時間相比,該解決方案檢查開銷可以忽略不計。演算法時間複雜度為O(N *(α * logN + β * logL)),其中N是樹中的節點數,L是障礙物數,α、β是第8行和第12行的概率(0<α,β≤ 1) 。對於不用Morton store的正常RRT演算法,α,β = 1。

  • 硬體輔助的儲存RRT演算法

基於軟體的Morton store演算法跳過耗時的基準NN搜尋和碰撞檢測,顯著減少執行時間,並且可以通過硬體輔助儲存進一步加速。由於Morton codes的計算和匹配按順序在軟體中迭代所有Morton codes,因此可能需要多條指令。為了估計Morton store需要多少動態指令,用Valgrind來計算Morton store查詢和更新的動態指令數。

如圖顯示了不同地圖邊長度、時間步長和動態障礙物數量的不同測試用例結果。

平均而言,與Morton store相關的動態指令計數佔動態指令總數的20%,最壞的情況下可能佔動態指令總數的45%以上。然而,通過硬體輔助儲存,動態指令計數可以顯著減少。可以直接在硬體使用CAM(content-addressable memory )進行Morton store查詢和更新,減少動態指令計數和相應的執行時間。

基於硬體的Morton store由一個全關聯的CAM實現,memoryline大小為64位元組,可以維護RRT節點的8個8位元組地址。由於這些節點是在堆疊上分配的,因此設定中MSB始終為0,並且地址的最高有效8位指示是否存在碰撞。

如圖顯示在CAM中實現硬體Morton store的示例。

其中tagstore儲存Morton codes,每行包含狀態(碰撞/無碰撞)資訊以及節點地址。對於碰撞狀態,在一個memoryline的所有狀態中,只要有一個狀態指示碰撞,則輸出是碰撞。

如圖所示是Morton store的架構:CAM直接連線到CPU。

一旦命中(hit)後,將處理提取碰撞狀態或節點地址相應的memoryline。如果未讀取(read miss),在Morton store中不會修改任何內容。當未寫入(write miss)時,最舊的參考memoryline被逐出。

為了在軟體中訪問此CAM併為不同的規劃演算法提供靈活性,定義了以下指令集架構(ISA)擴充套件。morton-update、morton-col和morton-nn,如下表。

  • 指令morton-update獲取節點的座標及其碰撞狀態,並在morton store中更新此資訊。
  • 指令morton-col獲取節點的座標,在CAM中查詢,並確定是否存在碰撞。
  • 指令morton-nn通過查詢具有相同morton codes的記錄,在morton store中查詢近似最近鄰的記憶體地址。

注:這項工作設定這些指令加速RRT。然而,也可以用於其他基於取樣規劃演算法,如PRM。

  • 合成測試用例

對於合成測試用例,採取一個正方形地圖,其中動態障礙物執行。綜合測試用例由三個引數表徵,即動態障礙物的數量、方形地圖的邊長度和時間步數。求解路徑應從(0,0)開始,目標是(l,l),其中l是方形地圖的邊長度。在這個模擬週期的開始和結束,隨機生成障礙物的開始和結束位置。對障礙物的中間位置進行線性插值。如圖顯示:是帶5個動態障礙物、邊長度為100和20個時間步的測試用例,從(0,0)到(100100)的解決方案路徑以藍色標記。

障礙物的數量決定了路徑規劃問題的難度。一般來說,障礙物越多,找到安全路徑所需的時間就越多,路徑的長度也可能更長,因為障礙物佔用的空間越大。地圖的邊長度和時間步數主要增加路徑規劃的執行時間。另一方面,更長的邊和更多的時間步長將提供更精確的解決方案,求解路徑上有更多的中間點。

  • 軟體效能評估

評估PC電腦上基於軟體的Morton store,該桌上型電腦有Intel i7-6700 CPU 3.40G和2133M的16GB DDR4記憶體。基準RRT演算法用C++實現。基準最近鄰搜尋基於kd-tree。用libmorton進行Morton code計算。

模擬12種配置,地圖邊長為{100,200},時間步長為{10,100},障礙物數量為{5,10,20}。比較基準RRT和Morton store軟體RRT(sw-Morton)的總執行時間。對於每個配置,隨機生成10個不同的測試用例。由於該演算法是隨機的,對於每個測試用例,重複實驗10次,並顯示平均執行時間。

如圖顯示執行時間的對比:

與基準RRT演算法相比,基於軟體Morton store的RRT路徑規劃平均減少了51%的執行時間。

  • 硬體評估

提出的硬體輔助方法使用CAM快速查詢和更新最近訪問的樹節點,進行最近鄰搜尋和碰撞檢測。用GEM5模擬器(開源系統和處理器模擬器)評估這種基於硬體的Morton store的RRT演算法效能。模擬器配置如下表所示:

實現了HW Morton store和一個CPU與HW Morton store store之間的自定義埠,以便在GEM5中進行查詢和更新。

與軟體評估中使用的12種配置相同,如圖顯示基準RRT、基於軟體Morton store的RRT(sw-Morton)和基於硬體Morton store的RRT(hw-Morton)的執行時間。

與基準RRT相比,基於軟體Morton store的RRT效能平均提高了2.28倍,基於硬體Morton store的RRT效能平均提高了8倍。對於最佳配置,軟體和硬體Morton Store的效能分別提高6.74倍和56.3倍。

如圖顯示基準RRT、基於軟體Morton store的RRT和基於硬體Morton store的 RRT解決方案路徑長度。

軟體Morton store和硬體Morton store的平均RRT解決方案長度分別是基準RRT解決方案的1.42倍和1.65倍。這是因為SW或HW Morton store只能找到近似的最近鄰,而不是精確的最近鄰。因此,解決方案路徑可能比基準波動更大。

如下右圖所示,在地圖位置(80,80)附近,基於硬體的Morton store給出的路徑在到達(100,100)之前來回移動。與下左圖所示的基線解決方案相比,這增加了解決方案的長度。這樣的路徑可以使用細化演算法(refinement)來減少總長度。

  • 在Commonroad基準資料集的評估

為了證明所提方法在現實場景中的有效性,用一個示例(USA\U US101-20\U 1\U T\U 1),如下圖所示:其中包含Commonroad基準(“ Commonroad: Composable benchmarks for motion planning on roads ”. IEEE IV‘ 2017)的動態障礙物,其場景記錄部分來自真實交通。

執行時間和解決方案路徑長度如圖所示,這證實了減少執行時間的有效性。