拓撲地圖及拓撲導航

機器人學中的傳統導航方法，通過利用在給定地圖中定位、軌跡規劃以及運動控制等途徑讓機器人完成導航任務，如SLAM（Simultaneous Localization And Mapping：同步定位與建圖）。然而，SLAM 方法存在許多局限性。例如，在特定的情況下，SLAM 方法需要耗費很大精力來獲得一張幾何上非常精 確的環境地圖。這往往需要與高精度的計量學或全球導航衛星系統傳感器相結合，并且需要專家級的地圖修改和參數調整，實際應用成本較為高昂。

2010 年代以來，伴隨著深度學習的蓬勃發展，基于學習（learning-based）的導航方法逐漸得到了廣泛的應用，成為機器人在復雜三維環境中學習導航的有效途徑。

基于深度學習的導航方法主要可以劃分為三類：1）純粹反應性的（reactive），例如基于深度強化學習的目標驅動導航；2）基于非結構化通用記憶的，例如LSTM（Long Short-Term Memory，長短期記憶）；3）基于特定于導航場景的結構化記憶的，例如度量地圖（metric map）。

n  度量地圖：

度量地圖是指以數學度量方式描述環境的地圖，通常使用二維或三維網格地圖來表示。度量地圖通常包含環境中的物體、障礙物、地形等信息，以及機器人的位姿信息。機器人在使用度量地圖進行導航時，通常采用自我定位（self-localization）方法來確定自身的位置和方向，然后使用路徑規劃算法（如A* 算法、Dijkstra 算法等）來尋找從當前位置到目標位置的最短路徑。機器人在移動過程中，會不斷更新自身的位置和方向，并根據更新后的信息重新規劃路徑，以保證能夠到達目標位置。

度量地圖的優點是能夠提供精 確的環境信息，能夠在機器人移動時實時更新，且適用于多種導航算法。然而，度量地圖也有一些缺點，比如它需要較大的存儲空間和計算資源，且對環境變化敏感，需要不斷更新地圖信息。

n  拓撲地圖：

事實上，動物和人類主要依賴的便是基于地標的導航策略，這一策略以對環境的定性拓撲知識為基礎，即環境的拓撲地圖（topological map）

作為另一類基于結構化記憶的主流導航方法，拓撲導航基于拓撲學的原理，使用節點和邊的連接關系來描述環境，構建拓撲地圖。

拓撲地圖是一種抽象化的地圖表示方法，它不需要記錄精 確的物理坐標和尺寸，只需記錄節點以及節點之間的拓撲關系。在拓撲地圖中，節點代表環境中的關鍵位置，即地標，例如房間、門、走廊等，而邊代表節點之間的鄰接關系，例如門連接兩個房間、走廊連接兩個節點等。在基于拓撲地圖的機器人導航中，機器人通過特定的傳感器獲取環境信息，并將這一信息與拓撲地圖進行匹配，以確定自身所處的位置。完成定位后，再利用拓撲地圖上的節點和邊計算到達目標位置的最短路徑，并根據特定的控制算法沿著路徑移動。

相比于度量地圖，基于拓撲地圖的導航具有許多優勢，包括：

1）地圖的簡潔性：拓撲地圖通過表示環境中的關鍵點和它們之間的連接來簡化了地圖表示。相較于度量地圖，拓撲地圖通常較小，更容易存儲和處理。

2）抽象級別：拓撲地圖提供了一種對環境進行高層次抽象的方法，這使得機器人能夠更好地理解環境中的結構和關系。這種抽象級別有助于機器人規劃路徑和避免障礙物。

3）地圖更新和維護：拓撲地圖中的節點和邊可以輕松地添加、刪除或更新，這使得地圖的維護和更新變得相對容易。這對于機器人在動態環境中導航尤為重要。

4）可擴展性：拓撲地圖可以輕松地擴展以包含更多的節點和邊，使其能夠適應不斷變化的環境。此外，拓撲地圖可以與其他地圖類型（如度量地圖）結合使用，以提供更豐富的導航信息。

5）魯棒性：拓撲地圖對于環境中的變化具有較好的魯棒性，因為它們只關注關鍵點之間的連接關系。這使得機器人能夠在環境中的部分變化或不精 確的傳感器數據的情況下繼續進行導航。

6）路徑規劃和優化：基于拓撲地圖的導航可以利用圖搜索算法（如A* 算法）來快速找到從起點到終點的最優路徑。通過優化這些算法，可以提高路徑規劃的速度和效率。

7）多機器人協作：拓撲地圖為多機器人系統提供了有效的通信和協作機制。機器人可以共享地圖信息，并通過拓撲地圖來協同規劃路徑和任務分配。

n  拓撲導航-感知相似性

拓撲導航關注于如何構建環境的拓撲地圖作為一種空間記憶的表征形式，以利用環境中的拓撲幾何信息進行導航。一般地，在拓撲地圖中，節點代表環境中的某一空間位置，有時還會存儲該位置的觀測信息；而節點之間的邊則反映了節點所代表的空間位置間的鄰接關系（或者說機器人在空間位置間的可達性），節點之間有邊相連，代表空間位置相鄰，反之則代表空間位置不相鄰。當前拓撲導航領域的研究，一方面研究拓撲地圖（拓撲記憶）構建的問題，另一方面研究基于感知信息的拓撲定位的問題，并常與路點預測、底層局部控制等相結合。

在拓撲導航中，定位模塊主要基于感知相似性（perceptual similarity）來構建定位網絡（或檢索網絡）。由此可知，感知相似性是拓撲導航系統的核心。感知相似性能夠衡量不同視覺觀測之間的相似程度，進而反映視覺觀測所處地點在空間位置上的關系。相似程度越高，代表越接近；相似程度越低，代表越遠離。這一邏輯與動物和人類的直覺相契合。

感知相似性與這些功能的實現息息相關：1）拓撲節點定位。通過判斷機器人當前位置觀測與拓撲記憶中節點的相似性，可將機器人當前位置定位到拓撲圖的最鄰近節點中。2）拓撲地圖構建。感知相似，則節點融合；感知不相似，則節點遠離。從而將機器人探索軌跡所形成的連續觀測序列稀疏化，把環境抽象為離散的拓撲地圖。

計算機視覺領域感知相似性的研究可以分為兩個方向：基于特征提取的方法和基于深度學習的方法。

§  基于特征提取的方法通常使用傳統的計算機視覺算法（如SIFT、HOG等）來提取圖像的局部特征，并將這些特征映射到低維空間中。在低維空間中，可以使用歐氏距離、余弦相似度度量方式來計算相似性。這種方法的優點是具有良好的可解釋性、計算效率高，但往往在處理復雜場景和大規模數據時表現不佳。

§  基于深度學習的方法則是使用卷積神經網絡（CNN）或循環神經網絡（RNN） 等深度學習模型來直接學習圖像、視頻等數據的嵌入向量（embedding），并使用這些向量計算相似度。這種方法的優點是能夠自動學習特征表示，適用于處理復雜的場景和大規模數據，但是需要大量的標注數據和計算資源。

感知相似性研究工作中基于深度學習的方法也被稱作深度度量學習（Deep Metric Learning，DML）方法。深度度量學習的目標是學習一個能夠表征特征嵌入空間的函數（通過深度神經網絡實現），使其能夠將高維視覺數據（image pixels）映射到低維特征嵌入向量（feature embedding vector），再通過計算嵌入向量之間的距離，來衡量不同圖像間的相似程度。

基于感知相似性的拓撲地圖在線構建

把觀測間的空間幾何信息融入到深度度量學習框架中，使得深度網絡能夠學習到一種有效的深度特征空間，其輸出的嵌入特征之間的距離既能表征觀測圖像本身的相似性，又能反映其在環境中的空間位置關系，從而實現拓撲節點定位的效果；

有機結合機器人當前觀測和拓撲記憶，在拓撲記憶中定位機器人當前位置，并融合相似節點、分離不相似節點，實現機器人在探索環境過程中在線生成并更新拓撲地圖，從而構建精 確度高、信息冗余度低的環境拓撲地圖。