作者：魚骨??

1. 筆者感悟

本文介紹了一種名為OASIS（Optimal Arrangements for Sensing in SLAM）的新方法，該方法旨在優(yōu)化移動機器人在SLAM任務(wù)中的傳感器布置。本文指出了當(dāng)前存在的研究問題，即目前缺乏關(guān)于如何在移動機器人上安裝傳感器的理論框架。OASIS方法是一種優(yōu)化設(shè)計任何建圖或?qū)Ш较到y(tǒng)的方法，該系統(tǒng)將來自多個傳感器的獨立測量數(shù)據(jù)進行融合。這里也推薦「3D視覺工坊」新課程深度剖析面向機器人領(lǐng)域的3D激光SLAM技術(shù)原理、代碼與實戰(zhàn)》。

OASIS方法的三個關(guān)鍵組成部分是：

設(shè)計空間：由一組有限的候選傳感器安裝位置組成，用于優(yōu)化傳感器布置。

基于E-最優(yōu)性的可計算的客觀函數(shù)：使用地標(biāo)為基礎(chǔ)的SLAM中舒爾補的Fisher信息矩陣的最小特征值作為評估定位精度的信息理論度量。

高效的優(yōu)化方法：將貪婪傳感器選擇與基于凸松弛的計算相結(jié)合，以驗證最優(yōu)性的上界，從而從候選傳感器安裝位置集合中提取高質(zhì)量的解決方案。

本文進一步介紹了如何模擬和優(yōu)化傳感器布置。作者提到，如果機器人預(yù)計在多個環(huán)境中采取各種軌跡，可以模擬大量異構(gòu)的場景，以找到在平均情況下表現(xiàn)良好的傳感器布置。此外，如果機器人受限于在固定環(huán)境中特定路徑上操作（例如倉庫作業(yè)），也可以使用OASIS方法找到適合其特定需求的布置方式。

OASIS方法的優(yōu)點是：

能夠直接獲取到機器人底盤機械約束導(dǎo)致的傳感器位置有限的情況；

避免了在離散（傳感器選擇）和連續(xù)（傳感器位置）變量上進行聯(lián)合優(yōu)化的需求；

采用了快速近似的組合優(yōu)化算法，可以從候選傳感器位置集合中高效地獲取高質(zhì)量解決方案。

本文還介紹了如何建模給定傳感器布置的SLAM性能，并提出了度量定位精度的信息論度量方法。作者給出了相應(yīng)的公式，并解釋了度量方法的原理。

最后，本文還通過實驗評估了該方法的有效性。實驗結(jié)果表明，該方法在實踐中非常有效，可以快速得到比最優(yōu)模型高1-2%的傳感器布置方案。

總之，本文使用了一種名為OASIS的方法來優(yōu)化移動機器人上傳感器的布置。該方法采用了特定的三個關(guān)鍵組成部分，并通過建模和優(yōu)化來提高SLAM任務(wù)的效率和精度。本文提出的方法在實驗中表現(xiàn)出色，并具有實際應(yīng)用的潛力。

圖1：OASIS的流程圖。對于每個姿勢，傳感器能夠觀測到一部分地標(biāo)。OASIS的目標(biāo)是最大化聯(lián)合Fisher信息矩陣的最小特征值，該矩陣由各個傳感器的子矩陣構(gòu)成。在這個例子中，傳感器“預(yù)算”要求我們只能從三個可選傳感器中選出兩個。最后，需要注意的是，表示傳感器選擇的離散二進制變量被松弛為凸集合。

2. 論文摘要

移動機器人外部傳感器的數(shù)量和位置對其感知能力有重要影響。設(shè)計新的機器人平臺時，研究人員和從業(yè)者往往會參考現(xiàn)有的配置或使用簡單的啟發(fā)式方法(如視野覆蓋率)來確定傳感器的位置。然而，這一關(guān)鍵的移動機器人感知問題目前還缺乏明確的理論指導(dǎo)。本文以同時定位與建圖(SLAM)為背景，從信息理論角度探討了移動機器人傳感器布局問題。我們把傳感器布局問題建模為一個基于E優(yōu)化準(zhǔn)則的最優(yōu)子集選擇問題。由于一般的子集選擇問題是NP困難的，我們提出了一種結(jié)合貪婪算法和快速凸松弛技術(shù)的有效方法，可以在實踐中找到可證明最優(yōu)的傳感器設(shè)計。

3. 最優(yōu)傳感器布置模型

本節(jié)介紹了如何將最優(yōu)傳感器布置問題形式化為一個含有二進制變量的整數(shù)規(guī)劃(IP)問題。

A. 傳感器布置空間的參數(shù)化

給定機器人底盤的模型，傳統(tǒng)方法是先確定要使用哪些類型和數(shù)量的傳感器，再確定它們在機器人上的安裝位置。但是，這種方法會導(dǎo)致一個非常困難的非凸問題，需要同時優(yōu)化(離散的)傳感器選擇變量和(連續(xù)的)傳感器姿勢變量。

我們提出了一種不同的方法，將傳感器布置問題看作是一個子集選擇問題。具體而言，我們假設(shè)我們給出的S集合有限地枚舉了所有可能的傳感器安裝位置(即，在機器人底盤上安裝特定傳感器的特定姿勢的決定)。那么，設(shè)計一個傳感器布置就等于從S中選擇一個特定傳感器安裝位置的子集。

B. 給定傳感器布置的SLAM性能模型

本小節(jié)介紹了如何根據(jù)傳感器布置來評估SLAM的性能。

設(shè)想我們的移動機器人在一個最初未知的環(huán)境中導(dǎo)航，環(huán)境中包含個可唯一識別的特征。在機器人探索時，它在一系列姿勢中移動，同時從其機載傳感器收集測量。設(shè)為中的所有候選傳感器安裝位置生成的完整測量集合。我們假設(shè)每個測量都是從已知的傳感器模型獨立采樣的，形式為：

現(xiàn)在考慮我們機器人在候選傳感器布置下的SLAM性能。不失一般性，設(shè)，我們可以給中的候選項標(biāo)號1，...，，然后用的二進制向量標(biāo)識每個的子集，其中定義為：

類似地，設(shè)為將每個分配給生成第個測量的傳感器安裝位置的標(biāo)簽的函數(shù)。使用這些符號，我們可以將傳感器布置下機器人可用的數(shù)據(jù)聯(lián)合似然參數(shù)化為：

相應(yīng)的，我們機器人在傳感器布置下要求解的SLAM最大似然估計的具體為：

C. Fisher信息和Cramer-Rao下界

Cramer-Rao下界(CRLB)為任何無偏最大似然估計器的可實現(xiàn)協(xié)方差提供了一個(在Loewner順序意義下的)下確界：

其中右側(cè)的矩陣是Fisher信息矩陣(FIM)：

對于SLAM似然度(3)，CRLB的形式為：

注意測量在(1)中的條件獨立性意味著是布置中包含的每個單個觀測貢獻的信息矩陣之和。等價地，寫作：

對于由傳感器生成的所有測量的信息矩陣之和，則等式(7)等價于：

也就是說：傳感器布置下SLAM估計問題(4)的FIM僅僅是中包含的每個單個傳感器提供的信息之和。

D. 傳感器布置的性能準(zhǔn)則

CRLB意味著如果我們想從(4)中恢復(fù)一個“小”的不確定性的SLAM估計，我們必須選擇一個傳感器布置，使對應(yīng)的FIM 盡可能“大”。

為此，我們提出使用E優(yōu)化準(zhǔn)則作為優(yōu)化傳感器布置設(shè)計的性能度量。簡而言之，這種方法要求最大化的最小特征值。與更常見的D優(yōu)化(最大化的行列式對數(shù))相比，E優(yōu)化的優(yōu)勢在于后者取決于的全部譜，而前者僅需要單個最小特征值；即使對非常大的矩陣，這個量也可以非常高效地計算。此外，由于下確界了的譜，最大化這個量可以解釋為最大化對數(shù)行列式本身的下確界。

我們還注意到，在許多SLAM應(yīng)用中，我們主要關(guān)注機器人姿態(tài)估計；特征位置估計只在支持準(zhǔn)確的機器人定位的程度上才有趣。在這種情況下，我們主要關(guān)注的是最小化，即姿態(tài)估計的邊緣協(xié)方差。鑒于(5)和2×2塊矩陣逆公式，與此相關(guān)的CRLB形式是：

這里的Schur(I)表示相對于特征變量的廣義舒爾補。因此，我們使用以下目標(biāo)函數(shù)：

E. 最優(yōu)傳感器布置

我們現(xiàn)在準(zhǔn)備好形式化最優(yōu)傳感器布置問題了。給定候選傳感器安裝位置的集合，環(huán)境和機器人軌跡的一個實例，以及要選擇的傳感器數(shù)量，我們的任務(wù)是找到中的基數(shù)子集，以最大化目標(biāo)函數(shù)(11)：

問題1(最優(yōu)傳感器布置)。

4. 快速近似算法

問題1的全局最優(yōu)解往往是NP難解的，所以通常無法在多項式時間內(nèi)得到。我們的算法結(jié)合了IV-A節(jié)描述的簡單貪婪策略和IV-B節(jié)提出的凸松弛技術(shù)。在這一節(jié)中，為了簡化符號，我們不再顯式地寫出和(因為它們不是優(yōu)化變量)。

A. 貪婪最大化

顧名思義，貪婪集合最大化算法通過迭代構(gòu)建解集，在每次迭代中，都添加使目標(biāo)函數(shù)的邊際收益最大化的元素。當(dāng)目標(biāo)函數(shù)是規(guī)范化單調(diào)子模函數(shù)時，貪婪解 保證滿足

其中是(12)的全局最大值。不幸的是，雖然單調(diào)且規(guī)范化，但只滿足近似子模性。

B. 凸松弛

我們將Problem 1中的(非凸)二進制約束松弛為(凸)布爾約束：

問題2(問題1的布爾松弛)。

觀察到如果是凹函數(shù)，那么(14)是一個凸優(yōu)化問題。因此，問題2的計算可行性取決于我們的目標(biāo)函數(shù)的凹性。幸運的是，下面的命題(在附錄中證明)說明E優(yōu)化性能準(zhǔn)則確實是凹的。

命題1(的凹性)。在域上定義的函數(shù)是凹的。

于是問題2在使用E優(yōu)化準(zhǔn)則(11)時是一個凸優(yōu)化問題，因此可以使用標(biāo)準(zhǔn)的凸優(yōu)化方法全局最優(yōu)解決。我們因此建議使用Frank-Wolfe方法求解問題2。

讓我們考慮問題1和2的最優(yōu)值比較。由于問題2是問題1的松弛，其最優(yōu)值為問題1的最優(yōu)值提供了一個上確界。另一方面，對于問題1中的任何可行的，我們顯然有。這些不等式一起意味著：

對問題1中的任何可行的，有

(15)式的重要性在于，它使我們能夠使用問題2的最優(yōu)值來給定問題1中任何可行解的次優(yōu)性。特別是，正如我們將在第V節(jié)中看到的，這將提供一種實用的方法來驗證問題1的候選解的(全局)最優(yōu)性。

C. OASIS算法

算法1

算法1概述了OASIS的整個過程。簡單來說，我們的方法是先用順序貪婪集合最大化算法得到問題1的一個可行解，再用Frank-Wolfe算法求解凸松弛問題2，得到問題2的最優(yōu)值上界，然后利用(15)式給出的次優(yōu)性界限。這種簡單的方法能夠在實際中有效地找到傳感器布置問題(12)的可驗證最優(yōu)解。這里也推薦「3D視覺工坊」新課程深度剖析面向機器人領(lǐng)域的3D激光SLAM技術(shù)原理、代碼與實戰(zhàn)》。

5. 評估

本文通過貪婪算法和凸優(yōu)化方法進行了實驗評估，并從信息論標(biāo)準(zhǔn)和SLAM性能兩個方面進行了結(jié)果呈現(xiàn)。在貪婪算法的實驗結(jié)果中，通過可視化展示了優(yōu)化結(jié)果的圖像，從圖中可以看出在不同情況下相機位置的偏好。而凸優(yōu)化方法的實驗結(jié)果中，作者通過圖表等方式展示了優(yōu)化結(jié)果與最優(yōu)值之間的接近程度。實驗結(jié)果表明，本文提出的OASIS方法在實踐中非常有效，并能夠得到接近于最優(yōu)值的傳感器布局。需要注意的是，雖然目前的實驗重點是對視覺SLAM任務(wù)的相機選擇，但作者將在未來的工作中探索更廣泛的傳感器配置設(shè)計，包括異構(gòu)傳感器集和更多的設(shè)計約束。

圖2：實驗結(jié)果I：在合成數(shù)據(jù)集上對最佳相機布置的定量結(jié)果。通過對優(yōu)化目標(biāo)函數(shù)的中位數(shù)優(yōu)化分?jǐn)?shù)和從最優(yōu)相機選擇的圖計算出的位姿估計的平均一二乘誤差（RMSE）與地面實況的比較，展示了OASIS算法的效果。圖(c)展示了貪婪優(yōu)化和凸松弛解在k-max舍入前后的目標(biāo)分?jǐn)?shù)。貪婪優(yōu)化得到了接近最優(yōu)解的解，如與未舍入的凸松弛方法的分?jǐn)?shù)的接近程度所示，凸松弛方法給出了最優(yōu)值的上界，特別是對于來說。（d）展示了貪婪優(yōu)化和凸松弛方法的運行時間比較。貪婪方法的時間復(fù)雜度隨著相機數(shù)量的增加而線性增長，而對凸松弛方法影響不大。

圖3：實驗結(jié)果II：(a)用于合成數(shù)據(jù)收集的設(shè)置。一個模擬的類似房間的環(huán)境包含墻壁上的地標(biāo)和從頂視圖顯示的隨機樣本軌跡。(b-d)圓形、前向和橫向運動的基準(zhǔn)算法的定量結(jié)果。

圖4：實驗結(jié)果III。貪婪最優(yōu)選擇在多個實驗中的可視化，疊加在候選池（a）上，其在線性陣列配置和（b）無論是在平移方向還是方向上都是定期間隔的地方。更深/更暗的顏色表示選擇的頻率更高。(c)顯示評分與SLAM姿勢估計的RMSE之間的相反關(guān)系，對于貪婪優(yōu)化和凸松弛方法都是如此。因此，E-優(yōu)化改善了SLAM性能。(b)貪婪優(yōu)化與凸松弛方法的運行時間比較。貪婪方法的時間復(fù)雜度與相機數(shù)量呈線性增長，而對于凸松弛方法影響不大。

6. 結(jié)論

在本文中，我們提出了OASIS方法，用于優(yōu)化地在一個用于執(zhí)行SLAM的移動機器人上布置傳感器。我們的方法將設(shè)計任務(wù)形式化為在一個可計算的E-最優(yōu)性性能度量下的最優(yōu)子集選擇問題。雖然子集選擇問題在一般情況下是NP難解的，但我們也開發(fā)了一種快速的近似優(yōu)化方案，它結(jié)合了貪婪的傳感器選擇和基于凸松弛的事后次優(yōu)性界限。我們的實驗評估表明，OASIS方法在實踐中非常有效，能夠高效地恢復(fù)傳感器布置，其與最優(yōu)值相差1-2%。雖然我們目前的實驗主要集中在視覺SLAM任務(wù)的相機選擇上，但在未來的工作中，我們將探索更廣泛類別的傳感器裝置的設(shè)計，包括異構(gòu)傳感器集合和比基數(shù)更豐富的設(shè)計約束。

編輯：黃飛