主動建圖與機器人探索：綜述

標題：Active Mapping and Robot Exploration: A Survey
作者：Iker Lluvia, Elena Lazkano, Ander Ansuategi
機構：Autonomous and Intelligent Systems Unit, Fundación Tekniker, Eibar, Spain 泰克基金會，艾巴爾，西班牙；
University of the Basque Country (UPV/EHU), 20018 Donostia, Gipuzkoa, Spain 巴斯克大學，西班牙

摘要

及時定位與建圖反應了這樣一個問題：在沒有任何先驗資訊的情況，僅基于一個或多個自身傳感器獲得的資料來進行環境建圖，在某些情況下，機器人被人工控制，但是一些系統能夠在建圖程序中自主導航，我們將其稱之為本地及時定位與建圖 native simultaneous localization and mapping，該策略聚焦于主動計算探索環境的軌跡，同時以最小的誤差構建地圖，在本文中，針對那些對室內移動機器人做出的重大相關貢獻，我們對該領域的研究做了全面的回顧，

關鍵詞

mobile robots; mapping; exploration; fronties; next best view; path planning

1. 簡介

對移動機器人導航問題的關注由來已久，該問題被分為三個子問題：環境建圖，定位和軌跡規劃，近幾十年來，這些問題已經發展成為廣泛的研究領域，分別用確定性的方式解決了，但是忽視了機器人感知和運動中的不確定性，在 1990 年代初期，通過開發能夠明確考慮機器人傳感器內在不確定性的演算法，概率機器人顛覆了傳統的導航方法，概率機器人致力于通過概率分布表示不確定性和資訊，并不基于單一的猜測，隨著這些方法的興起，出現了同時定位和映射 (SLAM)，也稱為并發映射和定位 (CML) 的問題：傳感器讀數相對于全域參考系的映射取決于機器人在其中的位置以及由于影響構建地圖程序的累積里程計誤差而導致該機器人姿勢的不確定性，視覺里程計允許使用任何型別的運動提高機器人或車輛的導航精度，來自相機或者慣性傳感器的視覺資訊與車輪運動資訊的結合允許我們解決漂移并且提供了更加精準的定位，然而，建圖誤差與機器人的位姿是相關聯的，因此，這兩個問題應該一起解決，機器人在室內和室外所使用的SLAM技術是不同的，室外環境更加充滿挑戰，因為并沒有特定的限制以及選擇下一個導航點或者終止的準則是完全不同的，此外，室內和室外經典SLAM系統在機器人的個體需求、所提供的傳感器以及形態上個不相同，馬爾可夫、基于卡爾曼濾波和基于例子濾波是用于解決SLAM問題的最常用技術，雖然在靜態環境中SLAM問題被認為已經得到了解決，但是在建圖的程序中，機器人通常被人遙控指引，用這種方法，能夠最小化輪上漂移，確保對環境的全覆寫，一旦地圖可用，集使用隨機規劃技術用于導航，例如部分可觀馬爾可夫程序 Partially Observable Markov Decision Process (POMDPs)，
SLAM 技術的出現推動了巨大的進步，并為機器人開發開辟了新的可能性，但在添加環境動態或增加維度時，性能方面仍然存在相當大的挑戰，然而，遙控機器人建圖是一個高耗時專案，尤其在大型區域中或者機器人的運動受限的情況下，其他方面，諸如在自然災害的救援行動中，由于連通性的不足或者危險狀況，機器人是很難甚至無法被引導，
主動SLAM，在下文中稱之為ASLAM，是主動規劃機器人路徑，同時建圖和在其中定位的任務，ASLAM相比傳統SLAM問題更進一步，因為ASLAM致力于機器人在建圖程序中自主運動，ASLAM能夠簡化橫多應用中的導航系統的設定，因為機器人能夠在沒有人的互動下依靠自己建圖，
據作者所知，目前缺少ASLAM的綜述，僅在某些文獻中作為一個非常特殊的子主題，這是目前作業的主要動機，我們希望對這個復雜問題進行整體描述，同時為相關研究人員提供所需的解決方案的參考，我們主要研究了室內靜態環境中以及單一機器人的任務，使用多個機器人能夠進一步的完善該課題，面向多機器人探索的文獻不在該綜述的范圍內，在提供ASLAM的資訊時，為了讀者的清晰理解和實用性，本文的組織如下：第二部分簡述了問題的歷史發展；第三部分詳述了組成所有ASLAM策略的三個迭代步驟；第四部分詳述了現有文獻中為了提升已有解決方案性能的優化策略；緊接著第五部分，通過所描述的溝通進行位置重訪問行動；關于世界維度的差異，以及計算相關的問題在第六部分進行闡述，第七部分總結了本文所提到的技術路徑之間的不同，第八部分概述了該領域的發展方向以及公開的研究問題，最后，第九部分總結了全文，為未來的研究提供了可行的方案，

2. 歷史回顧

直到1940年代第一個移動機器人出現后到的20年，Shakey，一個能夠推理自身行為的多用途移動機器人才被制造出來，自此以后，開發出了許多用于不同領域的移動機器人，
然而，為了自主地執行任務，需要對機器人進行導航，盡管開發了大量的演算法用于建圖、定位和軌跡規劃，但是移動機器人的導航仍未完全解決，正如簡介中提到的，建圖與定位最初是分開研究的，之后，人們證實了他們兩者之間依賴，這個問題也開始稱為SLAM，然后，基于SLAM的系統廣泛地擴展到替他領域，諸如基于視覺的在線3D重建或者自動駕駛汽車，因為每個領域有用其各自的要求，作為資訊源的傳感器也可能是不同的，盡管其中的大多數歸類為距離傳感器和基于視覺的系統，無論是2D還是3D系統，許多其他的傳感器被配置為主要的資訊來源或者附加的資訊源，例如GPS、輪速里程計、聲納或者IMU，不過，許多研究者選擇雷達或者相機，因為絕大多數的機器人是在GPS缺失的室內環境中運行的，并且其他的傳感器通常精度不夠，許多車輛中加入IMU作為附加傳感器，與其他設備相比較，IMU能夠提供旋轉軸相關的資訊，實際上，一些相機已經內置了IMU，
值得一提的是，在標準SLAM程序中機器人通常是由人引導，為的是確保環境能夠被完整的覆寫，并且環路是閉合的，實際上，在一段長距離的探索階段之后的識別一個已經建立的地圖，被稱之為倍訓檢測，這是SLAM程序中的最主要的問題，倍訓檢測是指利用對已經建圖的區域的檢測來最小化導航中的累積誤差，操作人員也有責任決定機器人的軌跡和終止準則，這些因素直接影響結果地圖的質量，從而影響相應導航的性能，區域漂移的結果是在運動期間累積的，增加了不確定性并且導致了一個不精確的估計，倍訓檢測極大的提高了地圖相對遍歷路徑的準確性，因為倍訓檢測企圖修正機器人位置的誤差，在解決全域定位問題時，識別之前訪問過的位置具有重要的意義，并且能很容易恢復失去定位的機器人，倍訓檢測方法不同于其他，因為他們可能面向特殊的地圖表示，盡管如此，生成的模型通常需要一個優化程序來修正任何錯誤添加的元素，這通常是傳感器噪聲以及移動機器人漂移的結果，這個后處理可以手動，也可以自動完成，
通過開發自動運行探索步驟的方法，地圖探索或者ASLAM假裝克服了之前提到的劣勢以及潛在資源的不協調性，例如，通過在線選擇路徑或者導航子目標自動化機器人導航程序能獲得更加精確的地圖，在最近十年被廣泛研究的探索領域exploration field，為移動機器人提供了巨大的優勢，尤其在惡劣環境中，
主動探索在一些文獻中也被稱為自動 SLAM (automatic SLAM) [34,35]、自主 SLAM (autonomous SLAM) [36-38]、自適應并行建圖與定位(adaptive CML) [4]、SPLAM（同步規劃、定位和建圖Simultaneous Planning, Localization and Mapping）[39] 或機器人探索(robot exploration) [40]，

ASLAM in Different Research Fields

“主動運動選擇”的概念來自兩個研究領域：移動機器人和計算機視覺，在機器人 [41]中，探索是指自主創建未知環境的操作地圖，除了在處理不確定定位的同時生成世界表示外，機器人還必須控制其運動，也就是說，它必須計算目標以及為實作這些目標而采取的動作，同時積極應對意外情況，
在計算機視覺中，問題表現為主動感知 [42]，它被定義為從環境中收集資訊以減少元素周圍不確定性的智能和反饋程序，它被認為是智能的，因為傳感器的狀態會根據傳感策略有目的地改變，應用于移動機器人的主動感知描述了機器人確定指定運動以便更好地了解環境的能力，在定位的背景下，移動傳感器的位置與/或航向，以嘗試搜索減少位置不確定性的路標點，因此，周圍元素的形狀、幾何形狀或外觀不可能是未知的，機器人必須能夠準確地識別它們，這被稱為主動定位，盡管假設已經對環境進行了建圖，但該領域的許多拓展可以延伸到本綜述研究的 ASLAM 問題中 [43-45]，特別值得一提的是張等人的成果 [46]，一方面，他們為微型飛行器提供了一種perception-aware receding horizon planner，允許機器人到指定目的地并同時避開視覺退化區域[47]，另一方面，他們為感知感知規劃定義了一個專用的地圖表示，它比使用點云的標準做法至少快一個數量級 [48,49]，這兩項貢獻都可以推動未知區域建圖的研究朝著正確的方向發展，相比之下，上文所提到的建圖中的主動感知active perception是指在沒有先驗資訊的情況下對環境進行建模并計算實作它所需的動作，因此，這個演算法包括兩個程序，環境本身的重建和傳感器的運動控制，這種方法被稱為主動建圖active mapping，即必須在有限時間內構建未知環境的地圖，優化結果模型的準確性以及為此目需執行的操作，有幾種方法可以估計與特定運動相對應的空間變換，基于概率濾波器的方法 [1,50] 給出了良好的結果，因此最常與那些采用 SfM [17,51] 方法的一起使用， SfM 是一種攝影測量范圍成像技術，用于從 2D 影像序列估計 3D 結構，類似于從立體視覺估計結構，
ASLAM 面臨的一些問題已經被其他研究領域解決了，例如，運行主動視覺為 3D 物件重建選擇下一個最佳傳感器姿勢或獲取場景的完整模型的任務，這被稱為次最佳視圖 Next Best View (NBV)，自 1980 年代以來一直在研究 [52]，或者，面向藝識訓廊的計算幾何computational geometry問題，這個問題首先由 Victor Klee 在 1973 年提出 [53] 作為安全領域中的一個感興趣的問題，區域A的藝識訓廊問題The art gallery
problem是為A找到一個最小基數覆寫視點集P，之所以這樣稱呼是因為將區域A設想為藝識訓廊的平面圖，而P中的點作為位置放置警衛，確保至少一名警衛可以看到藝識訓廊的每個部分，總之，假設系統已經有了環境的數字模型，目標是找到可以看到所有場景的最小位姿集，轉化為計算幾何問題，畫廊對應于一個簡單的多邊形，每個守衛由多邊形中的一個點表示，我們的目標是找到一個最小基數集（守衛），可以在不離開多邊形的情況下通過線段連接，已經做出了許多貢獻來尋找監視設備的最佳位置 [54-58]，
上述所有問題都包括完全覆寫部分未知的環境，在下一節中，詳細解釋了 ASLAM，并討論了它與其他類似概念的區別，

3. ASLAM問題

根據文獻，ASLAM 演算法由三個迭代步驟組成 [59]：位姿識別pose identification、目標選擇goal selection以及導航和檢查navigation and checking， 這些步驟涉及定位、路徑規劃和建圖等經典任務，其關系如 [圖1] 所示，位姿識別步驟識別可能的目的地；最優目標選擇步驟選擇最優目的地；并且，在最后一步，剩余的候選點影響演算法的終止， 可以看出，這三個階段取決于候選視點， 這些候選者只是移動機器人可能的目的地，受到用于管理導航組件的模型的限制， 因此，環境資料的表示方式可能會產生巨大的影響， [附錄A] 總結了環境表示的替代方案， 不熟悉機器人建圖程序的讀者可以參考它以更好地理解本文中進一步描述的技術，

3.1 位姿識別 Pose Identification

機器人根據所給的區域環境地圖，能夠識別出一系列目的地，理論上來講，應當評估所有的物理可達目的地，因為他們是潛在的資訊增益，并且因此任何目的地都能用于優化視點，然后，在實際中，評估計算的復雜性隨著搜索空間的增加而爆炸性地增加[39,60,61]，因此，某些濾波器能夠減少候選者的數量以及問題的復雜性[62,63]，一些位姿會被舍棄，比如已經被測驗過的、已建圖點周圍的或者未知空間中太遠的位姿，
最簡單的方法是在已有的SLAM系統中設定隨機目的地直到遇見一個確定條件，這種情況下，ASLAM與SLAM沒有差別，然后研究者們設計了更加復雜的演算法用于主動建圖，
邊界frontier在探索和建圖問題中是一個重要的概念[40,64,65]，邊界就是已知區域與未探索區域之間的界限，例如，地圖中在已知自由區域和未知區域之間的點，邊界點都位于以建圖區域中，并且機器人很有可能到達這些邊界點，此外，邊界點確保了與其相鄰的未知區域能夠被覆寫，因此，邊界代表的是可達點的優化集合，[圖2]表示了地圖中所有識別出的邊界，
可以通過應用計算機視覺技術（例如邊緣檢測或區域提取）來搜索邊界 [66]，然而，絕大多數方法使用基于廣度優先搜索 Breadth-First Search (BFS) [67-69] 的演算法找到這些點，并將這些邊界聚類以提高效率，因為相鄰的邊界點可以簡化探索結果，該結果與地圖的顆粒度正相關，通常，使用 k 均值演算法來進行聚類 [70-73]，此外一些作者提出了其他替代方法，例如基于直方圖的方法 [74]，

3.2 優化目標選擇

一旦確定了一組潛在目的地，就需要估計每個目的地的成本cost和收益gain，成本表示達到實際目標所需的，例如實際位置和目標姿勢之間的距離，增益對應于導航到選定目標之前和之后地圖提供的資訊之間的差異，資訊通常是指發現的點的數量，通常，增益和成本是產生稱為效用值的函式的變數 [75]，效用utility可作為比較探索軌跡的指標 [76,77]，理想情況下，為了計算給定動作的效用，機器人應該推理機器人姿勢和地圖的后驗演化，同時考慮未來（可控）動作和未來（未知）測量，然而，分析計算這個聯合概率通常在計算上是難以處理的 [78-80]，因此，其需要近似處理[78,81]，

3.3 導航與檢查

機器人導航到選定的最佳目的地，并在運動期間或達到目標時更新地圖，更新地圖意味著收集未知資料以及改善已采集地圖的質量或糾正舊的或錯誤的資訊，最初，導航是使用傳統技術執行的，例如 A* [82]，完全獨立于機器人探索，然而，一些研究人員建議采用這些軌跡作為自主建圖的目的，如第 4.2 節和第 5 節所述，此外，機器人必須檢查探索程序是否必須繼續，如需繼續進行探索，則運行姿勢識別步驟，并執行另一次迭代，
在探索未知環境時，可能總會有潛在的建圖或精度改進區域，從而將系統推向無限回圈，為了在有限的時間內執行自主建圖，定義了終止標準，當滿足該標準時，該程序將被視為完成 [39,83]，許多基于邊界的探索系統中，當地圖中不存在邊界目標時，探索程序就結束了 [78,84,85]，其他專案選擇了更直接的解決方案，例如行進的距離、經過的時間或捕獲的幀數，然而，這些條件與所構建模型的質量或完整性無關，它們的有效性高度依賴于最佳候選選擇器，Kriegel 爾等人 [86] 提出了一種 3D 重建系統，其中終止標準是預定義的最大掃描次數，該值是基于對場景質量和完成率的估計而設定的，并且由于不同物件的特定屬性，它對于每個區域都是唯一的，因此，存在特定于環境的停止條件，
與難以跨系統比較的資訊理論指標相比，來自最佳實驗設計理論 (TOED) [87] 的不確定性指標作為停止標準似乎更有發展前景，

4. 優化物件

改進第 3 節中描述的步驟（姿勢識別、最佳目標選擇以及導航和檢查）可以減少完成程式所需的時間、縮短行進距離或提高生成的地圖的保真度 [88-90]，主動建圖方法中的一個相關點是它是否嘗試計算最佳探索視點 [91]，或者另外計算到達該視點的最佳軌跡 [78]，此外，每次處理所有當前可用的地圖以找到可能的目的地，由于可用地圖的擴大，此程序需要越來越多的時間，為了解決這一限制，可以在地圖更新時計算最佳姿勢，并且可以在到達實際位置之前設定新的目的地 [92]，或者這些決定可以推遲到機器人達到導航目標并等待下一個[93]，此外，大多數演算法在運動規劃時關注區域的覆寫[94]，但其中一些演算法也考慮了建圖的質量[95]，
大多數基于邊界的探索方法僅優化導航目標，他們找到聚集在一起的邊界，然后導航到邊界，雖然重點是邊界提取、聚類或優先級策略，但導航技術通常完全獨立于機器人探索，基于采樣的 ASLAM 方法作為基于邊界的探索演算法的替代方案而出現，這些技術隨機生成機器人狀態并計算最大化導航程序中收集的資訊的路徑[96]，此外，近年來的許多策略不僅試圖找到探索的最佳姿勢，而且還試圖找到更有效地環境建圖最佳軌跡，這兩點將在本節后面深入討論，

4.1 位姿優化方法

第一次探索嘗試可以歸功于 Yamauchi [64]，他提出了一種基于網格單元圖中邊界的方法，如第 3.1 節所述，任何與未知單元相鄰的空閑單元都被視為邊界單元，這些單元被分組到邊界區域，機器人嘗試導航到最近的可訪問的、未訪問的邊界，路徑規劃器使用網格圖上的深度優先搜索來計算從機器人當前單元格到包含目標位置的單元格的最短無障礙路徑，通過移動到新的區域，移動機器人可以將其地圖擴展到新的區域，直到探索完整個環境，這種策略取得了巨大的成功，許多研究人員已經開發出基于邊界的探索方法，
Dornhege等人 [97] 通過引入空隙(void)的概念，將 Yamauchi 基于 2D 邊界的探索方法擴展到 3D 環境中，空隙是未知的 3D 單元塊，他們致力于解決為移動機器人平臺攜帶的 3D 傳感器選擇 NBV 配置的問題，此時平臺正在搜索未知 3D 空間中的物件，但機器人平臺靜止不動，一方面，邊界單元通過聯合查找演算法union-find algorithm 進行聚類，形成邊界簇集，另一方面，空單元集包含位于累積點云凸包內的所有未知單元，表示為八叉樹地圖，使用能力圖 capability maps移除傳感器無法到達的位置，能力圖是包括有關機器人可以完成的可能運動的資訊的表示[98]，可到達的邊界單元直接按將被發現的空隙空間的體積排序，然后 NBV 規劃器確定傳感器的配置，從中可以觀察到最大的空隙空間量，在計算出一定數量的有效位姿后，計算停止，
朱等人[99] 將傳統的基于前沿的探索擴展到 3D，并在微型飛行器 (MAV) 上的ROS框架 [100] 中運行他們的演算法，正在探索的環境的 3D 地圖是從兩個連續的點云增量構建的，由具有空閑、未知和占用單元的八叉樹表示（參見附錄 A），他們將連續的單元分成幾個簇，并選擇它們的幾何中心單元作為這個候選邊界的代表，在存在多個候選邊界單元的情況下，最佳目標邊界由考慮新資訊增益和移動到它的成本的標準確定，
雖然大多數探索開發作業都基于自由空間邊界，但 Senarthane 和 Wang [101] 提出了一種基于表面邊界概念的 3D 環境探索策略，他們將 3D 占據柵格地圖中的表面邊界體素voxel定義為建圖表面的邊界體素，其中體素的六個面中的至少一個面是邊界，也就是說體素是暴露在未建圖空間中的，因此，邊界體素是擴展到建圖表面的幾何邊界上的傳統邊界，然后，他們遵循從 3D 占據柵格地圖中找到邊界代表的通用做法，生成有效的視圖配置并根據效用標準選擇最佳視圖，結果表明，生成表面邊界比生成基于自由空間的邊界的計算成本更低，
通常，常見的方法將機器人引導到邊界進行探索，即它們主動搜索已知空間和未知空間之間的區域，將其設定為導航目標候選者，或者，一些研究人員展示了間接結合其他技術 [63,84] 發現邊界的作品，例如，Dai等人 [84] 提出了一種基于邊界和基于采樣的策略之間的混合探索方法，作者使用邊界確定探索應重點關注的區域，然后對候選視圖進行采樣，避免將單個體素聚類為更大的邊界，從而降低相關的計算成本，Ravankar等人 [85] 為無人機配備了用于 9 DoF 位置估計的 IMU、用于高度控制的氣壓計以及用作 RGBD 相機和 2D LIDAR 傳感器的 Microsoft Kinect，然后，擴展卡爾曼濾波器 (EKF) 用于將所有傳感器資料融合為單個導航資訊，以控制速度、方向和位置以及傳感器誤差偏差， Ravankar 等人作業的主要貢獻在于測驗是否可以使用低成本的 RGBD 傳感器進行映射和探索，也就是說，Yamauchi 的 [64] 邊界檢測用于探索，GMapping [102,103] 用于建圖和定位，DWA [104] 用于導航和空間對齊 [105] 將 3D 收集的資料轉換為稠密的 3D 地圖，

4.2 軌跡優化

使用 Receding Horizo??n (RH) 策略快速探索隨機樹 (RRT) [106] 是眾所周知的基于采樣的邊界替代方案，之的所以這樣命名這些策略，是因為預測范圍不斷向前移動，同時以同樣的方式發現環境并更新地圖， RRT 通常用于預測控制模型中的路徑規劃 [107-109]，但它們也成功應用于 ASLAM 演算法， RRT 顯示出向未知區域增長的趨勢，使其成為被動檢測探索邊界的理想選擇，由于這種自然的探索行為，RRT 規劃器的樹的葉子是必須分析的潛在邊界點，它們可以被視為有效探索軌跡本身的點，
Bircher 等人提出的規劃器 [83] 采用后視地平線下一個最佳視圖 (RH-NBV) 方案，其中為在線計算的隨機樹找到最佳分支，其質量取決于可以探索的未建圖空間的數量，當樹的節點數大于公差值tolerance value時認為探索已解決，而具有最高增益的節點的增益歸零，在該作業的擴展中 [110]，Bircher 等人提出了另一種基于采樣的后退地平線路徑規劃范式，它不僅解決體積探索，而且還解決了自主檢查的問題，所呈現的規劃器的目標是根據目標函式生成覆寫未知體積或檢查表面的路徑，使用的環境表示仍是八叉樹，具有自由、占用和未知空間， Umari 和 Mukhopadhyay [62] 利用 RRT 向未知區域增長并被動檢測邊界，盡管如此，樹并不是用來定義機器人軌跡本身，而是用來搜索邊界點，它獨立于機器人運動，在此基礎上，作者將探索策略分為三個模塊：基于RRT的邊界檢測器模塊、濾波器模塊和機器人任務分配模塊，檢測出第一個邊界點，并將它們傳遞給濾波器模塊，濾波器模塊使用均值漂移 [111] 聚類演算法對這些點進行聚類并存盤它們，在這一步中，無效的和舊的邊界點也被洗掉，最后一個模塊，即任務分配模塊，接收聚類的邊界點并將它們分配給機器人進行探索，此外，這項作業的另一個新穎之處是使用多棵樹獨立生長來加速搜索程序，
Papachristos等人 [112] 提出了一種具有不確定性的探索和制圖規劃策略，該策略采用后退地平線、兩步規劃范式，該方法計算用于探索未知空間的優化視點序列，并選擇其第一個視點進行訪問，然而，與上面所述的作業相反，這個新方法的路徑是通過第二個規劃層計算的，該層旨在優化機器人的概率建圖行為并最小化根的置信度不確定性，在這方面，在 Papachristos 等人最近的一項作業中 [113] 提出了兩種專注于自主未知區域探索的演算法，“后視地平線下一個最佳視圖規劃器”（nbvplanner）和“定位不確定性后視地平線探索和映射規劃器”（rhemplanner），他們在占據柵格地圖表示的環境中使用 RH-NBV 規劃器（命名為 nbvplanner），該地圖劃分為立方體，可以標記為空閑、已占用和未建圖，如果直接視線 Line of Sight(LoS) 未穿過占用空間并與傳感器模型編譯，則單元格標記為未建圖，在許多其他情況下，體積資料是使用八叉樹存盤的，然后，從機器人空間增量構建幾何 RRT，其節點根據未建圖的體積和路徑成本收集資訊增益值，優先選擇較短的路徑，它的邊由無碰撞路徑給出，為了應對機器人定位中的不確定性，他們提出了一種“定位不確定性后退地平線探索和映射規劃器”（rhemplanner），它復制 nbvplanner 中完成的步驟，直到確定了最大化探索增益的有限步驟路徑，然后，在第二階段，計算到達該視點的新路徑，這種替代軌跡確保保持低定位不確定性置信，整個程序被迭代重復，視覺慣性里程計框架用于提高方法的魯棒性和準確性，它還支持定位不確定性感知規劃，因為發生置信度傳播，以便采樣路徑包含機器人狀態和對應于最新跟蹤特征的地標的預期值和協方差估計，對于每個路徑段，推匯出預期的 IMU 軌跡并將其用于機器人置信預測，通過以視覺慣性里程計的 EKF 方式運行狀態傳播步驟，這些演算法在實際場景中進行了測驗 [114]，此外，代碼和實驗資料集均已發布，以進行系統的比較分析，
考慮到 RH-NVB 規劃和經典邊界檢測規劃的優點，Selin 等人 [63] 建議將這兩種技術結合起來，他們使用邊界檢測方法進行全域探索，使用 RH-NBV 規劃進行區域探索，假設使用 RH-NBV 規劃器的智能體有效地探索附近的環境，但當目標很遠時，它通常得分很低，因此，傾向于過早地終止探索，當 RH-NBV 規劃器探索其附近環境中的一切時，它會快取來自先前 RRT 的具有高潛力資訊的節點，并將它們視為規劃目標，進而執行邊界探索行為，此外，潛在的資訊增益函式與探索的未建圖區域成正比， Faria 等人采用與前面幾行中討論的方法完全不同的策略 [115] 提出將前沿探索與 Lazy Theta* 路徑規劃演算法相結合， Theta* 是 A* 的一種變體，它沿著網格邊緣傳播資訊而不限制在網格邊緣的路徑 [116,117]，同樣，Lazy Theta* 是 Theta* 的變體，它使用惰性求值對每個擴展頂點僅執行一次視線檢查 [118]，他們使用任意角度路徑規劃 [119] 來減少計算和視線檢查的次數，此外，該演算法已成功應用于自主多旋翼平臺[120]，這項作業的另一個相關方面是他們完全放棄了常規網格思維方式，充分利用稀疏網格的空間聚類，無論采用何種技術，大多數 ASLAM 方法的核心思想是賦予機器人在未知環境中自主構建地圖的能力，因此，機器人能夠導航到熟悉的位置，但是，沒有地圖就無法完成這項任務，鄧等人 [121] 更進一步，提出了在不需要事先擁有地圖的情況下實作目標的想法，他們專注于在基于視覺的導航程序中跟蹤故障避免，并提出了一個框架，用于規劃和遍歷移動機器人朝向目標并穿過未知環境的路徑，

5. 位置重訪

在不斷探索未知區域時，機器人定位的不確定性以及由傳感設備的噪聲和缺乏可靠參考造成了地圖相對于真實環境的誤差累積，在某種程度上，無論是顯式還是隱式搜索邊界點，大多數 ASLAM 方法都可以將機器人引導到尚未訪問過的區域，他們的決策函式的目標只是最小化可訪問邊界的數量，即機器人可以導航的點以及可以收集未知區域資訊的地方，盡管如此，這些探索演算法最大化覆寫但無視定位漂移的累積效應，這可能導致地圖不準確，出于這個原因，許多作業都認為 ASLAM 系統的導航策略應該通過平衡探索行動和地點重訪行動來減少不確定性 [122,123]，地方重訪主題也稱為倍訓檢測loop closure，它也來自 SLAM，
在這種情況下，González-Ba?os 和 Latombe [124] 提出了一種演算法，該演算法不使用邊界，而是構建連接連續安全區域的地圖，這些安全區域是保證沒有障礙物的最大區域，同樣的地圖也用于規劃安全運動，安全區域用于估計未來測量與當前部分構建的地圖之間的重疊，并檢查此重疊是否滿足對齊演算法的要求，最后，這些區域使 NBV 演算法能夠根據每個新候選位置的資訊增益估計，選擇最有可能探索大面積環境的位置，原則上，當所有區域安全區域的聯合邊界不包含自由曲線時，映射程序結束，在實踐中，當每條剩余自由曲線的長度小于指定閾值時，演算法停止，因為它更適合處理包含許多小幾何特征的復雜環境，
Stachniss 等人 [125] 提出了一種用于主動倍訓檢測的 2D 方法，旨在應對連續探索程序中不完善的控制和感知，他們將用于定位和建圖的 Rao-Blackwellized 粒子濾波器與通過主動倍訓檢測擴展的基于邊界的探索技術相結合，關鍵概念是迫使機器人再次遍歷先前訪問過的回圈，以減少姿勢估計中的不確定性并獲得更準確的地圖，在 Carlone 等人提出的 2D ASLAM 演算法中 [78]，使用 Kullback-Leibler 散度 [126] 評估基于粒子的 SLAM 后驗近似，以在探索和地點重訪之間做出決定，該指標用于估計來自計算 NBV 的策略的預期資訊，候選目標包括邊界目標和軌跡目標，它們允許機器人在過濾器不確定性變高時重新訪問地點，盡管如此，與之前提到的演算法一樣，如果地圖上不存在邊界，則認為探索已完成，策略的預期資訊是特定運動命令后的預期地圖資訊與當前地圖資訊之間的差值，將訪問單元格的數量理解為地圖資訊，即占用概率不等于0.5的單元格，預期資訊增益是軌跡中每個姿勢的資訊增益之和，由其距離歸一化，Valencia等 [127] 結合 SLAM 技術介紹了相對于經典探索方法對已知區域重訪的改進，他們提出了一種與位姿 SLAM [128] 集成的主動探索策略，這是 SLAM 的一種變體，其中僅估計機器人軌跡，并且使用地標來生成機器人姿勢之間的相對約束，在位姿 SLAM 中，機器人位姿先前的概率估計存盤為精確的稀疏圖 [129]，此外，Active Pose SLAM 方法評估探索和地點重訪序列的效用，并選擇最小化整體地圖和路徑熵的方法，該方法最小化熵而不是最大化覆寫范圍，因為只有那些熵度量低于閾值的軌跡被選為安全的探索路線，此外，還有導航目標，通過檢測倍訓來減少不確定性，請注意，在評估地圖上的資訊增益時，只會計算非常粗略的先驗地圖估計，

動態環境

雖然大多數演算法都假設環境是靜態的，但 Trivun 等人 [82] 開發了一個 2D ASLAM 系統來對動態室內環境進行建圖，該演算法使用Fast SLAM [130]，以及 Rao-Blackwellized 粒子濾波器，用于定位和映射，而 A* 搜索演算法 [131] 與動態視窗方法dynamic window approach (DWA) [104] 結合用于導航，在探索程序中，機器人首先掃描全域占用矩陣中的間隙，并檢測與機器人位置和距離傳感器范圍內在幾度內正交的區域，在該組之外產生的區域被標記為隱藏區域，在邊緣邊界之前總是要考慮在內，因為它們更接近并且通常探索成本更低，當有多個隱藏區域時，演算法會選擇最接近的一個，如果系統無法完全對一個隱藏區域建圖，則可以訪問該區域兩次，第一次，演算法將該區域按優先順序設定為最后一個，并將其標記為已訪問，如果再次訪問它，但仍未完全建圖，則更新代價地圖costmap，以便演算法不再檢測該間隙，如果沒有隱藏區域，邊緣邊界是唯一可供探索的候選者，目標是使機器人方向向量與邊緣正交，使傳感器覆寫盡可能多的區域，最后，計算每個候選的不確定性的總和，并選擇具有最高值的邊緣邊界間隙，當全域代價圖中沒有間隙時，程式結束，
Mammolo [132] 也研究了動態環境的問題，更具體地說，其作業提出了一種適用于靜態環境的 ASLAM 演算法，并為擁擠的環境提供了擴展，雖然它本身沒有引入探索或路徑規劃的新技術，但作為 Yamauchi [64] 提出的經典邊界方法的實作，用于探索，效用函式基于由Carrillo等人[133]開發的香農和 Rényi 熵， Mammolo 假設一個靜態環境，其中唯一的動態物件是人類，他們實作了一種演算法，可以過濾二維范圍資料中的移動人物，以便 ASLAM 系統可以使用靜態、可靠的資料完成任務，在擁擠環境中的實驗還不夠詳盡，但它們確實表明將該過濾器集成到 ASLAM 系統中可以提高性能，

6. 資料維度與計算成本

雖然大多數的2D探索演算法在2000年前被開發，但是伴隨著3D傳感器的出現（比如RGB-D系統，3D距離傳感器以及其他），3D建圖成為可能，3D環境重建提供了許多有趣的上線文資訊，并且擴展了機器人的應用，例如空中機器人的自動導航，其中3D資訊至關重要，圖三展示了一個機器人實驗室的3D建圖示例，

十年之后，3D ASLAM開始變得可行，并且因此被研究，然而，巨大的計算量要求高性能的機器和高效的存盤管理，以確保運行的一段時間，
2D系統能夠滿足很多應用的需求，但是3D系統額外識別了許多資訊變數，并且賦予了機器人新的能力：能夠建立3D真實模型，用于仿真的；所要求的體積資訊，比如用于移動的控制，或者協作任務；探索在不同高度的障礙物可以管理斜坡、臺階、溝渠等困難的負面障礙物，使得導航更加靈活和安全，誠然，這些增強功能帶來了更多的復雜性，但由于 2D ASLAM 的蓬勃發展，已經開發出更高效的演算法，并且硬體組件的計算能力已大大提高，另外，3D資料管理是無人機的關鍵需求，無人機是當今用于檢查、監視、建圖和3D建模專案的重要資料來源，相比于地面導航平臺的花費成本，他們更加輕量和便宜，除此之外，3D ASLAM的專案使得飛行器毫無疑問地成為一個好的選擇，由于他們的6自由度確保了探索系統能夠從幾乎所有視覺的點觀察區域，另外，他們的飛行能力和獨立于地面允許一個更加高效的路徑規劃，此外，演算法必須在通常沒有尖端技術規格的機器上運行，因此效率尤為重要，
Surmann首創了3D建圖方法，文獻[137]中，他們提出了一個自動系統，用于測量和數字化3D室內環境，但是，機器人的導航卻維持在2D地面平面，他們將其開發為三個模塊，第一個模塊記錄了3D掃描和機器人的重定位使用一個迭代最近點演算法的增速變體，在第二個模塊中，NBV 規劃器根據獲取的 3D 資料計算下一個標稱姿勢，同時避開障礙物，第三個模塊是一個倍訓檢測馬達控制器，基于里程計指引移動機器人到一定的位姿，同時避免和動態障礙物碰撞，探索候選者最初是隨機生成的姿勢，這些姿勢基于以下因素減少：評估的資訊增益值，由與邊界線相交的數量決定；到當前位置的距離；和當前位置的角度，如果候選視角點的集合為空，探索終止，Surmann使用一個快速基于八叉樹可視化方法來進行3D數字化，但是機器人的導航是在2D地圖中進行的，在某些情況下，這一不同會導致不一致，基于地圖的2D探索系統可能標記為空閑空間全域，會被3D系統能夠檢測為一個不能夠導航通過的地區，例如，導航障礙物（定義為地平面以下的障礙物，例如向下的臺階、溝或者懸崖）不應該存在，在系統僅考慮2D資訊執行一個探索程式的環境中，
影響計算需求的另一個問題，即記憶體需求，是無法運行任何離線探索程序的，機器人的動作是在運動程序中計算的，與傳統SLAM相反，機器人的完整路徑在運行時是未知的，因此這是最終地圖的大小，為了解決這些限制，Feder在文章[4]中展示了成果，初始化新特征到地圖中，匹配這些特征的測量，并且使用一個延時最近相鄰資料關聯策略洗掉過時的特征，他們引入了一種在未知環境中為任意數量的特征執行自適應 SLAM 的方法，它基于選擇動作，在給定當前傳感器測量值和地圖/機器人狀態的情況下，將最大化在下一次測量中獲得的資訊， 該技術面向區域自適應映射和導航，因為在每個周期，只考慮機器人的下一個動作， 隨著計算成本的大幅增長，它可以通過在擴展的時間范圍內進行預測來全域公式化，
自動地建立一個精確的全部室內環境的3D表示是行不通，因為基于環境大小和地圖的解析度問題復雜性會呈指數增長，此外，也可能沒有必要繪制整個區域，因為機器人的操作空間可以小得多且明顯有限，所以，能夠獨立地對特殊房間和區域建圖的系統在很多情況下都能引起興趣，Maurovic [89]利用單一的全域導航方法實作了一種區域與全域建圖的組合，他們將2D和3D探索組合到了一個周期方法中，能夠跟蹤大尺度環境中的三維資訊以尋找未探索區域，探索的開始利用了僅2D測量，并且隨后，機器人沿著跳躍邊界直到檢測到封閉空間，比如一個房間，這個時候，方法轉換成3D探索，其考慮激光點掃描儀捕獲的整個3D環境資訊，3D探索演算法致力于將檢測房間作為大環境的一個小的單位，當房間被探索后，3D探索程序終止并且繼續使用2D探索策略探索，回到第一步，對于單獨房間的3D房間探索，使用Blaer and Allen的演算法[135]，它需要預先獲取一個2D環境地圖，然后指導探索朝向更多的不可見區域，這些區域通過在傳感器高度及其視場FOV中的不可見體素的數量確定，
相比之下，為了解決上述 MAV 的計算和記憶體限制，Shen 等人[139] 提出了一種基于隨機微分方程的探索演算法，該演算法僅考慮當前地圖中已知的占用空間，避免了自由和未知空間的顯式表示， 他們根據隨機微分方程的演化來確定進一步探索的區域，該方程用牛頓動力學模擬粒子系統的膨脹，

7. ASLAM演算法總結

我們對前幾節中介紹的方法在表 1 中進行分組， 對于每項作業，使用的機器人、收集資訊的傳感器、世界的表示方式、貢獻的核心概念、優化目標以及執行測驗的平臺進行了總結歸納， 優化串列示該方法是否找到了用于探索的最優位姿、軌跡或兩者，此外，演算法的性能在很大程度上取決于所使用的硬體和所建圖環境，

8. 發展展望

雖然很多演算法致力于解決建圖的一致性與覆寫率，但是這些演算法往往不能夠保證場景的建圖質量和完整性，在3D重建領域的一些研究或許對解決上述ASLAM中的問題有多幫助，例如，Calli et al[142]提出了一種基于極值尋優控制extremun seeking control（ESC）主動視覺策略，該策略不需要周圍環境的先驗模型，雖然它專注于非結構化環境中物體識別和抓取的視點優化，但連續 ESC 演算法解決了當目標函式、其梯度和最優值未知時的目標值優化問題[143]，因此，它可以用于優化 ASLAM 方法中的效用函式，
將語意資訊應用到ASLAM中是最新的一個研究路線[144]，通過物體間語意屬性的區別而不是幾何物體，機器人能夠很好的理解其周圍的場景，這個功能極大的提升的傳統SLAM，并且在探索未知環境時具有很強的實用性，文獻[148]將目標識別系統集成到服務機器人的場景的SLAM，在導航程序中主動建圖，并且在程序中加入了目標檢測系統，文獻[149]將語意資訊添加到目標SLAM系統中，但是他們主動優化機器人的運動，用來減少對目標物件的觀測不確定性，同時提高其位姿估計的精度，他們提出了一種目標驅動object-driven 主動探索策略，其考慮了目標觀測的完整性以及位姿優化的不確定性，該策略顯著提高了目標地圖的準確性，
深度強化學習是另一條研究方向，因為它在許多領域都取得了有希望的結果，而且 ASLAM 模型適合它給出回應的問題型別 [150-155]，盡管在 ASLAM 領域尚未發布很多機器學習方法，但近年來的提案引起來研究者的關注 [156-160]，正如在第 2 節中提到的，監視和探索方法的不同之處在于，在前者中，環境是從一開始就知道的，而后者必須去發現它，然而，它們有一些相似之處，一次改進可以影響兩個研究方向，例如，Ly 和 Tsai [161] 提出了一種基于可見性的探索、重建和監視的貪婪和監督學習方法，給定一組先前訪問過的點，他們計算累積可見性和邊界，他們訓練了一個卷積神經網路，該網路可以為一大類障礙物學習幾何先驗，從而提高運行時的效率，然后，他們通過在這對輸入上應用經過訓練的神經網路來近似增益函式，并根據 [83] 選擇下一個點，重復這個程序，直到沒有邊界或遮擋，雖然它主要專注于監視，但它也通過僅使用觀察作為輸入來學習函式的引數來解決探索問題，

開放研究問題

ASLAM 還遠未成為可以在幾乎任何環境中有效使用的已解決問題， 雖然在家庭和工業場景中運行SLAM的產品很多，但都沒有提供無需人工干預自主創建地圖的功能， 還有一些問題需要解決，
在任何狀態下，機器人都有可能根據接收到的輸入執行多個動作， 因此，預見每個單獨行動的影響的能力是決策程序中的一個關鍵點 [162]， 此外，每個動作都應該對建圖程序做出貢獻，它可能會改變后續動作的貢獻， 在對未知環境建圖的程序中優化該函式，其中目標模型和構建它所需的時間是未知的，該問題仍在研究中， 盡管預測動作對未來的影響的程序的計算成本是巨大的，但是通過使用頻譜技術 [163] 和深度學習 [164] 取得了一些進展，
何時完成建圖程序是另一個需要解決的重要問題， 目前使用的許多終止標準，例如掃描次數、經過的時間、行進的距離等幾乎不依賴于正在建模的環境，因此通常基于反復試驗設定， 在建圖的某個時刻，過多的資訊只會導致相互矛盾的結果，并且可能會由于多次錯誤的倍訓而最終處于不可恢復的狀態， 如果該方法側重于覆寫率，則可能更容易正確決定何時可以認為程序已完成，但隨著結果表示所需質量的提高，這會變得更加復雜， 探索和開發之間的平衡在整個程序中具有巨大的影響，
通常，在經典 SLAM 程序中創建的地圖需要一個后處理步驟，其中洗掉錯誤添加的元素， 通常，這種添加不是演算法本身的錯誤， 移除的元素通常是在日常使用中改變了位置和方向的物體（例如椅子），但不是動態的， 也就是說，這些提煉動作都是基于人類的經驗，而機器人還沒有這些知識， 一旦地圖步驟被認為完成，當機器人自動開始導航任務時，需要讓 ASLAM 系統能夠在創建地圖的同時做出這些決定并避免后處理的必要性， 語意資訊處理在該領域顯示出一些有希望的結果 [165]，

9. 總結

本文回顧了移動機器人領域的 ASLAM 技術， 大多數研究方法假設系統在室內靜態環境中運行，地面和空中機器人分別是 2D 和 3D ASLAM 系統的主要執行平臺， 也有一些研究作業試圖解決其他場景中的問題，例如在水下環境中，
對于基于 2D 地圖的技術，基于邊界的方法是最常用的方法，在標準演算法中，機器人只是導航到最佳邊界點，移動機器人在移動時獲取資訊并增加定位漂移，許多方法添加了約束以確保定位的不確定性較低或系統始終導航到最佳邊界視點，然而，這些演算法一直非常依賴于所使用的傳感器和地圖表示，相比之下，對于 3D 資料，基于滾動優化的系統receding horizon-based system能夠起到更好的作用，它們考慮了整個路徑上的資訊增益，并且很容易適應不同傳感器，此外，與計算成本高昂的邊界點聚類方法相比，計算復雜度較低，這使得該類演算法能夠應用于更大規模的環境，但是，RH-NBV 方法可能會陷入區域最小值，關于世界表示，占用網格圖占主導地位，特別是基于八叉樹的結構，包含深度學習模型和語意資料結構的作業正在不斷發展，它們可能會大大改進 ASLAM 程式，但目前還沒有足夠的文獻來得出明確的結論，
為了比較不同方法之間的優缺點，必須確保文獻代碼的可復現，確保在具體環境中使用機器人平臺執行不同的方法，并測量效率、建圖完成度和準確性等指標，
可以得出結論，ASLAM 主題在短短幾年內發展如此迅速，未來仍然可以為移動機器人導航領域提供更多幫助，

附錄A：世界表示

ASLAM中的環境表示與傳統的SLAM系統并沒有不同，如圖A1所示，許多作業解釋了不同建立機器人可讀形式的幾何模型的方法，IEEE地圖資料表示研討會開發了一套規范標準來表示用于機器人導航的地圖，
主要的兩種地圖表示方法有：拓撲地圖topological和度量metric地圖，
拓撲圖與圖graph類似，只考慮位置及其之間的相對關系，將環境表示為一系列用邊連接的節點（位置），兩個節點之間的邊被標記為兩個姿態的相對位置的概率分布，以它們的相互測量為條件，基于這種簡化的世界表示，能夠輕松建立大型擴展地圖，并且提供路徑規劃所需要的所有資訊，
或者，在度量地圖中，目標是通過精確坐標定位的，它們提供了應用地圖繪制或導航演算法所需的所有資訊，但地圖大小與作業區域的大小成正比，這本身就使得對大區域進行建模（特別是與 3D 映射相關）的成本很高，通常有三種度量地圖的表示：基于路標的地圖landmark-based maps、占據柵格地圖occupancy grid maps和幾何地圖geometric maps，
基于路標的地圖表示，又稱之為基于特征的feature-based表示，識別并且保持某些特殊點的位姿，這種表示必須滿足路標對于機器人感知系統是唯一且可識別的，這些路標可以是點、線、角點，甚至是3D建圖中的面，形成場景的稀疏表示，路標不僅僅是原始的測量資料，比如復雜的描述子discriptor，它更是與每個測量建立相關的資料關聯，
與之相反，占據柵格地圖利用網格單元grid cell來描述環境資訊，每一個網格單元存盤這它所覆寫的區域的資訊，通常存放的是一個單一變數，用來表示該出是否為障礙物的概率值，網格單元可以包含2D或者3D的資訊，存在一種2.5D地圖表示，它并不是純粹的3D占據柵格地圖，而是在擴展2D網格單元地圖中增加了高度值，柵格地圖由常規柵格或者稀疏柵格構成，常規柵格將連續空間離散化為相同大小的單元格，類似于樹狀法，常規柵格中，八叉樹編碼器是最值得一提的，八叉樹是一種分層的8元樹結構，能夠在制定的解析度下表示任何形狀的物件，由于其高效性，它被廣泛用于需要 3D 資料存盤的系統中，因為表示和操作所需的記憶體大小僅取決于物件表面積，
代價地圖costmap一個被廣泛應用于柵格地圖的概念，代價地圖表示的穿越不同地圖區域的困難程度，代價地圖利用占據柵格地圖和抽象值的的形式來表示，該抽象值不代表任何對環境的測量，因為代價本身是通過對比靜態地圖、區域障礙物資訊和膨脹準則得到的，
幾何地圖也能夠被認為是一種離散地圖，在幾何地圖中，所有被傳感器檢測到的物件通過簡化后的幾何外形來表示，例如圓和多邊形，該方法能夠在不損失太多資訊的條件下高效地表示環境資訊，但是這會影響軌跡的計算以及資料的整體管理，因此，在實際中應用中，很少有人采用這種方法，大多采用占據柵格地圖，
采用，諸如資訊權重變數這種用于主動建圖的附加資訊，也為設計ASLAM演算法提供了很多的可能性，ASLAM演算法會因為所采用的建圖方法不同而有很大的差異，但是最顯著的區別還是在于其面向2D還是3D，或者兩者的混合[165]，

標籤：其他

上一篇：Adaptive AUTOSAR 學習筆記 7 - 應用設計和 Manifest

下一篇：Adaptive AUTOSAR 學習筆記 8 - 干貨小結：背景、技術、特征、架構、方法論和 Manifest