Multi-Resolution POMDP Planning for Multi-Object Search in 3D

作者: Kaiyu Zheng, Yoonchang Sung, George Konidaris, Stefanie Tellex · IROS 2021

授權條款

• 開放取用
• 論文: CC BY 4.0

以下內容皆依據論文全文，依其 CC BY 4.0 授權條款使用；圖表已標示作者。

一句話摘要

將 3D 多物體搜尋建模為 POMDP，並以多個八元樹解析度平行規劃的方式線上求解；在大型模擬空間中勝過不分層的基準方法，並在 Kinova MOVO 上執行。

為何重要

它把 POMDP 物體搜尋從 2D 地圖帶到 3D 搜尋區域，同時讓線上規劃維持在每一步固定的時間內。八元樹信念不必完整建構，遮蔽則透過 UNKNOWN 體素標籤處理，不需要雜物的幾何模型。

問題

家庭機器人必須在有限的截頭錐體形相機視野與遮蔽條件下，於層架上、桌子下和櫥櫃裡找到多個物體。以 POMDP 為基礎的物體搜尋有理論依據，但先前的研究將搜尋空間或機器人的移動能力簡化為 2D，因為在大型 3D 狀態空間上的精確信念難以計算，而大型觀測空間會讓規劃器面臨很高的分支因子。

提出的方法

作者定義了 3D-MOS：一種物件導向的 POMDP，具有 6D 相機姿態，MOVE、LOOK 與 FIND 動作，觀測由視錐內帶標籤的體素組成，並依物體分解。逐體素的觀測模型與八元樹信念可在 O(|V| log |G|) 內完成精確的信念更新，並在 O(log |G|) 內以任意解析度取樣；較粗解析度的抽象 POMDP 各自由 POUCT 平行求解，再執行價值最高的動作（MR-POUCT）。

關鍵見解

• 依物體分解狀態與觀測，使信念空間隨物體數量線性成長，而非指數成長。
• 將每個體素的標籤各自建模，並把被遮蔽或在視野外的體素視為不提供資訊，可縮小規劃用的觀測空間，並把信念更新限制在視野內的體素。
• 將信念儲存在八元樹中、每個節點保存其子節點數值的總和，可在每個解析度得到精確的信念，並以對數時間取樣。
• 在多個解析度上平行規劃並執行最佳動作，能應付單一解析度無法配合的未知物體尺寸與距離。
• 粒子信念（POMCP）在大型觀測空間下會發生粒子匱乏，在此領域中退化為隨機行為。

主要結果

• 在 12 種設定的模擬中（搜尋空間邊長 m ∈ {4, 8, 16, 32}、n ∈ {2, 4, 6} 個物體、每種 40 次試驗），以折扣累積獎勵計，MR-POUCT 在 m = 16 與 m = 32 的所有測試案例中都勝過 Exhaustive 搜尋。
• Exhaustive 搜尋在小空間（m = 4 與 8）表現較好，此時一個視野最多涵蓋網格的 17.2% 與 8.8%；在 m = 32 時，一個視野最多涵蓋 2.6%。
• 每種方法每一步最多有 3.0 s 的規劃時間，總共 120 s 至 480 s（視 m 而定）；POMCP 因粒子匱乏而表現不佳。
• 在 (16, 2, 10) 實例加入感測雜訊時，MR-POUCT 在所有嘗試過的設定下都始終最佳，且在 β < 1 時 β 幾乎沒有影響。內文說 α 有 5 種設定，卻列出六個數值（10、100、500、10³、10⁴、10⁵）。
• 在 Kinova MOVO 上，機器人在約 15 分鐘內，於兩個約 10 m² × 2 m 的區域中找到放置在不同高度的 6 個物體中的 3 個，並在需要看見目標時降低軀幹。
• 抽象觀測模型使用 k = 10 或 k = 40 個蒙地卡羅樣本時，搜尋效能相近；實際採用 k = 10。

限制

• 假設物體彼此獨立可節省計算，但可能捨棄物體之間有用的相依關係；搜尋彼此相關的物體仍是未解決的問題（作者自述）。
• 觀測模型不對物體幾何進行推理，並假設每個物體在規劃解析度下都能放進單一體素（作者自述）。
• 使用的是均勻隨機的 rollout 策略；作者建議在較貼近真實的問題中採用啟發式 rollout，但會犧牲最佳性。
• 在實體機器人上，拓樸地圖中任何視點都未涵蓋的物體被遺漏；作者提出使用更密集的地圖或取樣的 MOVE 目的地。
• 假設物體與障礙物為靜態、機器人狀態可觀測；而且在小型搜尋空間中，單純的窮舉搜尋表現較好。

對領域的影響

它獲得 IROS 2021 最佳 RoboCup 論文獎，被引用 33 次。論文連結了一個專案頁面，內有體積觀測與八元樹信念更新的影片；論文未說明是否釋出程式碼。

摘要

在家庭中運作的機器人必須在層架上、桌子下和櫥櫃裡找到物品。在這類環境中，以 3D 尺度有效率地搜尋，同時應付有限的視野以及搜尋多個物體的複雜性，是至關重要的。有理論依據的物體搜尋方法常以部分可觀測馬可夫決策過程（POMDP）作為計算搜尋策略的基礎框架，但將搜尋空間限制在 2D。本文提出一個在 3D 區域中、以截頭錐體形視野進行多物體搜尋的 POMDP 建模。為有效率地求解此 POMDP，我們提出一種基於線上蒙地卡羅樹搜尋的多解析度規劃演算法。在此方法中，我們設計了一種新穎、以八元樹為基礎的信念表示法，以在不同解析度層級上捕捉目標物體的不確定性，接著在較低解析度下推導出狀態空間與觀測空間大幅縮小的抽象 POMDP。在模擬 3D 領域中的評估顯示，在相同的計算需求下，相較於一組沒有解析度階層的基準方法，我們的方法在較大的實例中能更有效率、更成功地找到物體。我們在一台移動機器人上展示此方法：它藉由移動底座並驅動軀幹，在兩個 10m² × 2m 的區域中尋找放置於不同高度的物體。

連結

• arXiv 2005.02878: https://arxiv.org/abs/2005.02878
• DOI 10.1109/IROS51168.2021.9636737: https://doi.org/10.1109/IROS51168.2021.9636737
• PDF: https://arxiv.org/pdf/2005.02878v4
• 專案頁面: https://zkytony.github.io/3D-MOS/