拓?fù)涞貓D及拓?fù)鋵?dǎo)航

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

2010 年代以來，伴隨著深度學(xué)習(xí)的蓬勃發(fā)展，基于學(xué)習(xí)（learning-based）的導(dǎo)航方法逐漸得到了廣泛的應(yīng)用，成為機器人在復(fù)雜三維環(huán)境中學(xué)習(xí)導(dǎo)航的有效途徑。

基于深度學(xué)習(xí)的導(dǎo)航方法主要可以劃分為三類：1）純粹反應(yīng)性的（reactive），例如基于深度強化學(xué)習(xí)的目標(biāo)驅(qū)動導(dǎo)航；2）基于非結(jié)構(gòu)化通用記憶的，例如LSTM（Long Short-Term Memory，長短期記憶）；3）基于特定于導(dǎo)航場景的結(jié)構(gòu)化記憶的，例如度量地圖（metric map）。

n  度量地圖：

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

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

n  拓?fù)涞貓D：

事實上，動物和人類主要依賴的便是基于地標(biāo)的導(dǎo)航策略，這一策略以對環(huán)境的定性拓?fù)渲R為基礎(chǔ)，即環(huán)境的拓?fù)涞貓D（topological map）

作為另一類基于結(jié)構(gòu)化記憶的主流導(dǎo)航方法，拓?fù)鋵?dǎo)航基于拓?fù)鋵W(xué)的原理，使用節(jié)點和邊的連接關(guān)系來描述環(huán)境，構(gòu)建拓?fù)涞貓D。

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

相比于度量地圖，基于拓?fù)涞貓D的導(dǎo)航具有許多優(yōu)勢，包括：

1）地圖的簡潔性：拓?fù)涞貓D通過表示環(huán)境中的關(guān)鍵點和它們之間的連接來簡化了地圖表示。相較于度量地圖，拓?fù)涞貓D通常較小，更容易存儲和處理。

2）抽象級別：拓?fù)涞貓D提供了一種對環(huán)境進行高層次抽象的方法，這使得機器人能夠更好地理解環(huán)境中的結(jié)構(gòu)和關(guān)系。這種抽象級別有助于機器人規(guī)劃路徑和避免障礙物。

3）地圖更新和維護：拓?fù)涞貓D中的節(jié)點和邊可以輕松地添加、刪除或更新，這使得地圖的維護和更新變得相對容易。這對于機器人在動態(tài)環(huán)境中導(dǎo)航尤為重要。

4）可擴展性：拓?fù)涞貓D可以輕松地擴展以包含更多的節(jié)點和邊，使其能夠適應(yīng)不斷變化的環(huán)境。此外，拓?fù)涞貓D可以與其他地圖類型（如度量地圖）結(jié)合使用，以提供更豐富的導(dǎo)航信息。

5）魯棒性：拓?fù)涞貓D對于環(huán)境中的變化具有較好的魯棒性，因為它們只關(guān)注關(guān)鍵點之間的連接關(guān)系。這使得機器人能夠在環(huán)境中的部分變化或不精 確的傳感器數(shù)據(jù)的情況下繼續(xù)進行導(dǎo)航。

6）路徑規(guī)劃和優(yōu)化：基于拓?fù)涞貓D的導(dǎo)航可以利用圖搜索算法（如A* 算法）來快速找到從起點到終點的最優(yōu)路徑。通過優(yōu)化這些算法，可以提高路徑規(guī)劃的速度和效率。

7）多機器人協(xié)作：拓?fù)涞貓D為多機器人系統(tǒng)提供了有效的通信和協(xié)作機制。機器人可以共享地圖信息，并通過拓?fù)涞貓D來協(xié)同規(guī)劃路徑和任務(wù)分配。

n  拓?fù)鋵?dǎo)航-感知相似性

拓?fù)鋵?dǎo)航關(guān)注于如何構(gòu)建環(huán)境的拓?fù)涞貓D作為一種空間記憶的表征形式，以利用環(huán)境中的拓?fù)鋷缀涡畔⑦M行導(dǎo)航。一般地，在拓?fù)涞貓D中，節(jié)點代表環(huán)境中的某一空間位置，有時還會存儲該位置的觀測信息；而節(jié)點之間的邊則反映了節(jié)點所代表的空間位置間的鄰接關(guān)系（或者說機器人在空間位置間的可達性），節(jié)點之間有邊相連，代表空間位置相鄰，反之則代表空間位置不相鄰。當(dāng)前拓?fù)鋵?dǎo)航領(lǐng)域的研究，一方面研究拓?fù)涞貓D（拓?fù)溆洃洠?gòu)建的問題，另一方面研究基于感知信息的拓?fù)涠ㄎ坏膯栴}，并常與路點預(yù)測、底層局部控制等相結(jié)合。

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

感知相似性與這些功能的實現(xiàn)息息相關(guān)：1）拓?fù)涔?jié)點定位。通過判斷機器人當(dāng)前位置觀測與拓?fù)溆洃浿泄?jié)點的相似性，可將機器人當(dāng)前位置定位到拓?fù)鋱D的最鄰近節(jié)點中。2）拓?fù)涞貓D構(gòu)建。感知相似，則節(jié)點融合；感知不相似，則節(jié)點遠離。從而將機器人探索軌跡所形成的連續(xù)觀測序列稀疏化，把環(huán)境抽象為離散的拓?fù)涞貓D。

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

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

§  基于深度學(xué)習(xí)的方法則是使用卷積神經(jīng)網(wǎng)絡(luò)（CNN）或循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN） 等深度學(xué)習(xí)模型來直接學(xué)習(xí)圖像、視頻等數(shù)據(jù)的嵌入向量（embedding），并使用這些向量計算相似度。這種方法的優(yōu)點是能夠自動學(xué)習(xí)特征表示，適用于處理復(fù)雜的場景和大規(guī)模數(shù)據(jù)，但是需要大量的標(biāo)注數(shù)據(jù)和計算資源。

感知相似性研究工作中基于深度學(xué)習(xí)的方法也被稱作深度度量學(xué)習(xí)（Deep Metric Learning，DML）方法。深度度量學(xué)習(xí)的目標(biāo)是學(xué)習(xí)一個能夠表征特征嵌入空間的函數(shù)（通過深度神經(jīng)網(wǎng)絡(luò)實現(xiàn)），使其能夠?qū)⒏呔S視覺數(shù)據(jù)（image pixels）映射到低維特征嵌入向量（feature embedding vector），再通過計算嵌入向量之間的距離，來衡量不同圖像間的相似程度。

基于感知相似性的拓?fù)涞貓D在線構(gòu)建

把觀測間的空間幾何信息融入到深度度量學(xué)習(xí)框架中，使得深度網(wǎng)絡(luò)能夠?qū)W習(xí)到一種有效的深度特征空間，其輸出的嵌入特征之間的距離既能表征觀測圖像本身的相似性，又能反映其在環(huán)境中的空間位置關(guān)系，從而實現(xiàn)拓?fù)涔?jié)點定位的效果；

有機結(jié)合機器人當(dāng)前觀測和拓?fù)溆洃?，在拓?fù)溆洃浿卸ㄎ粰C器人當(dāng)前位置，并融合相似節(jié)點、分離不相似節(jié)點，實現(xiàn)機器人在探索環(huán)境過程中在線生成并更新拓?fù)涞貓D，從而構(gòu)建精 確度高、信息冗余度低的環(huán)境拓?fù)涞貓D。