編者按：在自適應搜索問題中，經常會需要機器人在很強的背景干擾情況下定位目標位置。在本文中，伯克利的研究人員提出了一種通用的自適應感知方法AdaSearch，能快速定位目標點。以下是論智對該成果的編譯。

在機器學習的很多任務中，常見的有根據固定、預先收集好的數據集回答問題。但是在一些應用中，我們沒有先驗數據，必須自己收集回答問題所需要的數據，例如在環境污染監控和人口普查過程中常出現這種情況。自己收集數據則要求我們將注意力放在最相關的信息源上，但是想確定哪些信息源會得到有用的結果則是很困難的。另外，當實體收集數據時（例如機器人、衛星或人類），我們必須對測量方法進行規劃，盡量減少智能體隨時間移動所造成的成本增加。我們將這種抽象的問題稱為“具身自適應感知（embodied adaptive sensing）”。

針對這一問題，我們提出了新的解決方法，其中機器人必須穿越它所在的環境后確定位置或目標物體。自適應感知涵蓋了機器人研究中的很多問題，例如快速定位污染物或放射性資源的泄漏、在搜救中找尋被困者。在這些情況下，設計一種能盡快返回正確結果的感知軌跡是很重要的。

本文我們以放射物泄漏問題（RSS）為例，無人機需要確定環境中k-最大的放射性輻射源，k是用戶定義的參數。RSS是自適應感知問題中非常有趣的案例，因為其中會遇到多種復雜的背景噪聲（放射源周圍有很多放射性物質）。

于是，我們提出了AdaSearch，這是一種用于通用自適應感知問題的連續消除式的框架，我們在放射源尋找的環境下測試它。AdaSearch在環境中的每一點都能將泄漏率控制在置信區間中。利用這些置信區間，算法經過迭代確定了一系列可能泄漏點，最終選出唯一的一個，清除掉其他的。

將具身搜索看作多重假設的測試場景

傳統上，機器人領域將具身搜索（embodied search）看作持續的運動計劃問題，其中機器人必須平衡環境探索和對高效軌跡的選擇。這就催生了既可以進行路線優化，又可以進行環境探索的方法，可以用滾動時域控制（receding horizon control）進行優化。而我們通過假設檢驗測試，將該問題看作序列最佳動作定義。

在假設檢驗測試中，它的目標是在多種分散問題上得出結論。給定智能體一系列測量動作N，每個都能根據固定分布生成觀察結果。

智能體的目標是學習這些N個觀察分布中的預指定特征。例如，我們以向新客戶展示產品A或產品B為例，記錄他們對該產品的評價，從而表示統計學中的A/B測試。這里的N=2，因為只有兩個動作：展示A和展示B。而我們要研究的目標特征就是哪個產品更受歡迎。根據我們收集到的偏好信息，對這些樣本以及置信區間進行跟蹤記錄，分別用置信下限和上限對產品進行定義。隨著收集的評價越多，我們對每個產品的偏好估計就越準確。最終可以用一個結論來定義B比A更受歡迎：如果B的置信下限比A的置信上限還要高，那么我們可以認為B比A更受歡迎。

而在環境感知的情況下，每個動作都要從一定位置和方向讀取傳感器。通常來說，智能體的目標是確定哪個方向能測量出最多的觀測信號，或者哪一系列的k動作能得到最大的平均觀測。為了這一目標，智能體可能會按順序選擇動作，通過此前的觀察選擇信息量更多的動作。

乍一看，序列最佳動作確定可能對移動的具身感知智能體來說太抽象了。智能體完全可以不考慮潛在成本隨機選擇動作。但是，抽象的動作確定是非常強大的。通過精準的統計語言實現具身搜索問題，我們提出了與每種感知動作非常相關，且置信度很高的觀察方法，確定了未來要做的一系列動作。

我們提出的AdaSearch用序列最佳動作定義得到的置信區間和全局軌跡規劃，實現了漸進最優的測量復雜度，并能有效的分攤運動成本。

放射源尋找

為了驗證它的效果，我們會用AdaSearch尋找放射性元素唯一一個泄漏點。我們將環境模擬成一個平面網格，如下所示。其中的紅點是放射性元素集中的區域。但是定位這一點非常難，因為傳感器會被其他紫色的點（背景輻射）干擾。信息的收集由配有傳感器的無人機進行，目標就是設計一個路線，我們能通過傳感器收集來的觀測信息，盡快定位放射點的位置。

AdaSearch

我們的AdaSearch算法結合了全局收斂計劃和自適應感知。在無人機第一次通過網格時，會先均勻地收集環境信息。

第一次觀察后，我們能取消一些明顯不合適的區域。如果在平均值周圍的置信上限小于任何區間的最大下限，該點則會被消除，表示該點不是目標區域。

在下一次探索，AdaSearch會更仔細地搜索剩余點，直到找到目標。

Baseline

我們將AdaSearch和經過相同案例訓練的信息最大化方法——InfoMax進行比較。但不幸的是，對于大型空間的搜索，實時計算無法支持路線規劃或者參數化。這可能導致算法變得非常貪婪，會花大量時間找尋錯誤的原因。

為了區分我們的置信區間所帶來的影響和全局規劃啟發法，我們用簡單的全局規劃方法——NaiveSearch作為第二種baseline。這種方法統一地對網格采樣，在每個單元格上都花費同樣時間。

結果

我們在64×64米的網格上，用4米的分辨率實現了三種算法，模擬了放射性源尋找的實例。結果我們觀察到，AdaSearch通常比NaiveSearch和InfoMax更快完成。隨著不斷增加背景輻射的水平，NaiveSearch的運行時間越來越慢，但AdaSearch的變化卻不大。