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

動(dòng)態(tài)障礙物的自動(dòng)駕駛路徑規(guī)劃是一個(gè)挑戰(zhàn)，因?yàn)樾枰跐M足實(shí)時(shí)約束的同時(shí)執(zhí)行更高維搜索（包括時(shí)間）。作者提出了一種算法-硬件協(xié)同優(yōu)化方法，加速基于高維搜索空間的路徑規(guī)劃。

首先，將節(jié)點(diǎn)和障礙物映射到低維空間并存儲(chǔ)最近的搜索結(jié)果，減少最近鄰搜索和碰撞檢測(cè)的時(shí)間。然后，提出一種用于高效存儲(chǔ)的硬件擴(kuò)展方法。在一個(gè)現(xiàn)代處理器和一個(gè)循環(huán)級(jí)（cycle- level）模擬器的實(shí)驗(yàn)結(jié)果表明，該算法的執(zhí)行時(shí)間顯著縮短。

路徑規(guī)劃的及時(shí)執(zhí)行對(duì)車輛的安全和效率至關(guān)重要。修剪（pruning）是被用來在軟件中加速的方法。針對(duì)RRT、PRM和A*等算法，人們用不同的硬件技術(shù)，包括FPGA或ASIC，還提出了特定于算法的加速器。雖然這些路徑規(guī)劃加速器確實(shí)解決了特定場(chǎng)景中的個(gè)人需求，但不是針對(duì)自動(dòng)駕駛，也不考慮動(dòng)態(tài)障礙。

此外，隨著法規(guī)（regulation）和算法的不斷發(fā)展，選擇和修改加速路徑規(guī)劃算法的靈活性也非常重要。然而，許多現(xiàn)有路徑規(guī)劃加速器一次設(shè)計(jì)只考慮一個(gè)特定的算法，大多數(shù)超參在設(shè)計(jì)/編程時(shí)固化到加速器硬件中。雖然這些硬件化算法在發(fā)布時(shí)表現(xiàn)良好，并在目標(biāo)場(chǎng)景提供良好的性能，但不夠靈活，無法適應(yīng)新的或修改算法。

• 動(dòng)態(tài)障礙物的對(duì)付

自動(dòng)駕駛車輛在2D平面執(zhí)行路徑規(guī)劃。在不同的時(shí)間，障礙物將位于2D平面的不同位置。2D平面的動(dòng)態(tài)障礙物成為一組障礙物，在三維空間的坐標(biāo)可以用（x，y，t）來描述。

可以有效地將帶有動(dòng)態(tài)障礙物的2D規(guī)劃問題視為3D規(guī)劃問題。然而，時(shí)間維度不同于普通的空間維度，這需要對(duì)其進(jìn)行額外約束。由于時(shí)間只沿一個(gè)方向移動(dòng)，對(duì)于路徑P上i<j的任意兩個(gè)節(jié)點(diǎn)（xi，yi，ti）和（xj，yj，tj），必須保證ti<t j。在RRT選擇最近鄰時(shí)，將強(qiáng)制執(zhí)行附加約束。

• 基于軟件的存儲(chǔ)RRT算法

用存儲(chǔ)（memorization）來減少路徑規(guī)劃的總執(zhí)行時(shí)間。在傳統(tǒng)基于采樣的規(guī)劃（比如RRT）中，大部分執(zhí)行時(shí)間都花在尋找最近鄰（NN）以及檢測(cè)會(huì)不會(huì)碰撞。為了加速這些過程，存儲(chǔ)最近訪問的節(jié)點(diǎn)和碰撞狀態(tài)，以便跳過一些類似的查詢。

如圖顯示了整個(gè)方法的流程：基準(zhǔn)（藍(lán)色箭頭）規(guī)劃流程和改進(jìn)（橙色箭頭）規(guī)劃流程。

在基準(zhǔn)RRT，所有迭代執(zhí)行耗時(shí)的最近鄰搜索和碰撞檢測(cè)。然而用一個(gè)名為Morton store的小型數(shù)據(jù)存儲(chǔ)器（以Morton空間歸檔曲線命名）記住基準(zhǔn)最近鄰搜索和碰撞檢測(cè)的關(guān)鍵信息。對(duì)每個(gè)迭代，首先檢查Morton store，以便有機(jī)會(huì)跳過耗時(shí)的基準(zhǔn)NN搜索和碰撞檢測(cè)。

規(guī)模有限的Morton store的運(yùn)作如下。

先計(jì)算樹節(jié)點(diǎn)坐標(biāo) Xn =（Xn，yn，tn）以及障礙物 Xo =（x，y，t）的Morton codes Mn 和 Mo。Morton code將點(diǎn)（x，y，t）從3D空間ooo投影到1D曲線，同時(shí)保持空間位置（32位整數(shù)）。Morton codes Mn 和 Mo 是64位數(shù)，用作相應(yīng)節(jié)點(diǎn)和障礙物的標(biāo)記。為調(diào)整投影粒度，屏蔽Morton codes的k個(gè)最低有效位

其RRT算法偽代碼如下：

這個(gè)解決方案必須對(duì)每段（segment）路徑執(zhí)行精確的碰撞檢測(cè)，以確保安全（無碰撞）。與使用Morton store進(jìn)行精確碰撞檢測(cè)節(jié)省的時(shí)間相比，該解決方案檢查開銷可以忽略不計(jì)。算法時(shí)間復(fù)雜度為O（N *（α * logN + β * logL）），其中N是樹中的節(jié)點(diǎn)數(shù)，L是障礙物數(shù)，α、β是第8行和第12行的概率（0<α，β≤ 1） 。對(duì)于不用Morton store的正常RRT算法，α，β = 1。

• 硬件輔助的存儲(chǔ)RRT算法

基于軟件的Morton store算法跳過耗時(shí)的基準(zhǔn)NN搜索和碰撞檢測(cè)，顯著減少執(zhí)行時(shí)間，并且可以通過硬件輔助存儲(chǔ)進(jìn)一步加速。由于Morton codes的計(jì)算和匹配按順序在軟件中迭代所有Morton codes，因此可能需要多條指令。為了估計(jì)Morton store需要多少動(dòng)態(tài)指令，用Valgrind來計(jì)算Morton store查找和更新的動(dòng)態(tài)指令數(shù)。

如圖顯示了不同地圖邊長度、時(shí)間步長和動(dòng)態(tài)障礙物數(shù)量的不同測(cè)試用例結(jié)果。

平均而言，與Morton store相關(guān)的動(dòng)態(tài)指令計(jì)數(shù)占動(dòng)態(tài)指令總數(shù)的20%，最壞的情況下可能占動(dòng)態(tài)指令總數(shù)的45%以上。然而，通過硬件輔助存儲(chǔ)，動(dòng)態(tài)指令計(jì)數(shù)可以顯著減少?？梢灾苯釉谟布褂肅AM（content-addressable memory ）進(jìn)行Morton store查找和更新，減少動(dòng)態(tài)指令計(jì)數(shù)和相應(yīng)的執(zhí)行時(shí)間。

基于硬件的Morton store由一個(gè)全關(guān)聯(lián)的CAM實(shí)現(xiàn)，memoryline大小為64字節(jié)，可以維護(hù)RRT節(jié)點(diǎn)的8個(gè)8字節(jié)地址。由于這些節(jié)點(diǎn)是在堆棧上分配的，因此設(shè)置中MSB始終為0，并且地址的最高有效8位指示是否存在碰撞。

如圖顯示在CAM中實(shí)現(xiàn)硬件Morton store的示例。

其中tagstore保存Morton codes，每行包含狀態(tài)（碰撞/無碰撞）信息以及節(jié)點(diǎn)地址。對(duì)于碰撞狀態(tài)，在一個(gè)memoryline的所有狀態(tài)中，只要有一個(gè)狀態(tài)指示碰撞，則輸出是碰撞。

如圖所示是Morton store的架構(gòu)：CAM直接連接到CPU。

一旦命中（hit）后，將處理提取碰撞狀態(tài)或節(jié)點(diǎn)地址相應(yīng)的memoryline。如果未讀?。╮ead miss），在Morton store中不會(huì)修改任何內(nèi)容。當(dāng)未寫入（write miss）時(shí)，最舊的參考memoryline被逐出。

為了在軟件中訪問此CAM并為不同的規(guī)劃算法提供靈活性，定義了以下指令集架構(gòu)（ISA）擴(kuò)展。morton-update、morton-col和morton-nn，如下表。

• 指令morton-update獲取節(jié)點(diǎn)的坐標(biāo)及其碰撞狀態(tài)，并在morton store中更新此信息。

• 指令morton-col獲取節(jié)點(diǎn)的坐標(biāo)，在CAM中查找，并確定是否存在碰撞。

• 指令morton-nn通過查找具有相同morton codes的記錄，在morton store中查找近似最近鄰的內(nèi)存地址。

注：這項(xiàng)工作設(shè)定這些指令加速RRT。然而，也可以用于其他基于采樣規(guī)劃算法，如PRM。

• 合成測(cè)試用例

對(duì)于合成測(cè)試用例，采取一個(gè)正方形地圖，其中動(dòng)態(tài)障礙物運(yùn)行。綜合測(cè)試用例由三個(gè)參數(shù)表征，即動(dòng)態(tài)障礙物的數(shù)量、方形地圖的邊長度和時(shí)間步數(shù)。求解路徑應(yīng)從（0,0）開始，目標(biāo)是（l，l），其中l(wèi)是方形地圖的邊長度。

在這個(gè)模擬周期的開始和結(jié)束，隨機(jī)生成障礙物的開始和結(jié)束位置。對(duì)障礙物的中間位置進(jìn)行線性插值。如圖顯示：是帶5個(gè)動(dòng)態(tài)障礙物、邊長度為100和20個(gè)時(shí)間步的測(cè)試用例，從（0,0）到（100100）的解決方案路徑以藍(lán)色標(biāo)記。

模擬12種配置，地圖邊長為{100，200}，時(shí)間步長為{10，100}，障礙物數(shù)量為{5，10，20}。比較基準(zhǔn)RRT和Morton store軟件RRT（sw-Morton）的總執(zhí)行時(shí)間。對(duì)于每個(gè)配置，隨機(jī)生成10個(gè)不同的測(cè)試用例。由于該算法是隨機(jī)的，對(duì)于每個(gè)測(cè)試用例，重復(fù)實(shí)驗(yàn)10次，并顯示平均執(zhí)行時(shí)間。

如圖顯示執(zhí)行時(shí)間的對(duì)比：

與基準(zhǔn)RRT算法相比，基于軟件Morton store的RRT路徑規(guī)劃平均減少了51%的執(zhí)行時(shí)間。

• 硬件評(píng)估

提出的硬件輔助方法使用CAM快速查找和更新最近訪問的樹節(jié)點(diǎn)，進(jìn)行最近鄰搜索和碰撞檢測(cè)。用GEM5模擬器（開源系統(tǒng)和處理器模擬器）評(píng)估這種基于硬件的Morton store的RRT算法性能。模擬器配置如下表所示：

實(shí)現(xiàn)了HW Morton store和一個(gè)CPU與HW Morton store store之間的自定義端口，以便在GEM5中進(jìn)行查找和更新。

與軟件評(píng)估中使用的12種配置相同，如圖顯示基準(zhǔn)RRT、基于軟件Morton store的RRT（sw-Morton）和基于硬件Morton store的RRT（hw-Morton）的執(zhí)行時(shí)間。

與基準(zhǔn)RRT相比，基于軟件Morton store的RRT性能平均提高了2.28倍，基于硬件Morton store的RRT性能平均提高了8倍。對(duì)于最佳配置，軟件和硬件Morton Store的性能分別提高6.74倍和56.3倍。

如圖顯示基準(zhǔn)RRT、基于軟件Morton store的RRT和基于硬件Morton store的 RRT解決方案路徑長度。

軟件Morton store和硬件Morton store的平均RRT解決方案長度分別是基準(zhǔn)RRT解決方案的1.42倍和1.65倍。這是因?yàn)镾W或HW Morton store只能找到近似的最近鄰，而不是精確的最近鄰。因此，解決方案路徑可能比基準(zhǔn)波動(dòng)更大。

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

• 在Commonroad基準(zhǔn)數(shù)據(jù)集的評(píng)估

為了證明所提方法在現(xiàn)實(shí)場(chǎng)景中的有效性，用一個(gè)示例（USA\U US101-20\U 1\U T\U 1），如下圖所示：其中包含Commonroad基準(zhǔn)（“Commonroad: Composable benchmarks for motion planning on roads”. IEEE IV‘2017）的動(dòng)態(tài)障礙物，其場(chǎng)景記錄部分來自真實(shí)交通。

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