Hydra

Hughes (MIT SPARK) 2022 · 論文

一行要約 — 階層的3Dシーングラフ（メッシュ → オブジェクト → 場所 → 部屋 → 建物）をセンサデータから逐次的に構築し、ループクロージャが発生した際にすべての層を同時に最適化する、最初のリアルタイム空間認知システム（Spatial Perception System）。

問題

3Dシーングラフは、複数の抽象度レベルにわたる空間概念をノードとする階層的なグラフとして、強力な高次表現として登場したばかりだったが、既存のシステムはそれらをオフラインで構築していた: Kimeraの3D Dynamic Scene GraphsやArmeniらの手法は数分のバッチ処理を要し、環境全体のESDF（メモリがうまくスケールしない）に依存し、ループクロージャが発生するたびにグラフをゼロから再構築しなければならなかった。ロボット上でこのような「メンタルモデル」をリアルタイムに構築する方法は、著者らの言葉を借りれば未踏の領域だった — シーングラフにとってループクロージャとは何を意味するのかという問いも含めて、というのも軌道を補正するにはメッシュより上のすべての層を一貫して補正する必要があるからである。

手法とアーキテクチャ

層1～3、逐次的に、アクティブウィンドウ内で。 Hydraは、ロボットを中心としたユーザー指定の半径（8m）にVoxbloxのTSDF/ESDFを空間的にウィンドウ化し、メモリを制限する。ウィンドウ内では: marching cubesがメトリック・セマンティックメッシュを抽出しつつゼロクロッシングの「親」ボクセルにラベルを付け、オブジェクトはクラスごとのメッシュ頂点のユークリッドクラスタリング（重心＋バウンディングボックス、重心が別ノードのボックス内に落ちた場合は既存ノードと統合）によって形成される。場所は一般化ボロノイ図（Generalized Voronoi Diagram） — 少なくとも2つの障害物から等距離にあるボクセルであり、ESDFブラシファイア更新の副産物として得られる — から抽出され、逐次的にグラフへとスパース化される（ノードは基底点あるいはコーナーテンプレートが≥4\geq 4個あるボクセルに配置され、辺はフラッドフィルラベリングによって決まり、直線的な辺がGVDから外れる場所で分割される）。これは環境の規模に関わらず一定時間で実行される。

層4: トポロジーからの部屋。 障害物を距離δ\deltaで膨張させるとドアが閉じ、部屋が切断される；各場所ノードはその障害物距離を保持しているため、膨張は場所サブグラフGp{\cal G}_{p}に直接写像される。Hydraは[0.45,1.2][0.45, 1.2]mの範囲で10段階の膨張距離を試し、各刈り込みグラフGp,δ{\cal G}_{p,\delta}の連結成分数を数え、その中央値nrn_{r}を取り、nrn_{r}個の成分を持つ最大のGp,δ⋆{\cal G}_{p,\delta^{\star}}を選び、それらの成分をシードとした貪欲なモジュラリティベースのコミュニティ検出によって残りのノードを割り当てる — バッチESDF処理ではなくミリ秒単位で完了する。

階層的ループクロージャ。 各エージェント（キーフレーム）ノードは記述子の階層を持つ: DBoW2の外観語、近傍オブジェクトラベルのヒストグラム、近傍場所の障害物距離のヒストグラムである。検出はトップダウン（場所 → オブジェクト → 外観）に進み、検証はボトムアップに進む。まず視覚特徴によるRANSAC、視覚が失敗した場合はマッチしたオブジェクトのTEASER++レジストレーションを行う — そのため視点や照明の変化で崩れたマッチも、セマンティックには検証できる場合がある。

シーングラフ最適化。 フロントエンドは全グラフを組み立て、メッシュを制御点にサブサンプリングする（オクトリー頂点クラスタリング）。バックエンドはエンベデッド変形グラフ（エージェント姿勢グラフ + メッシュ制御点 + 場所の最小全域木を層間の辺で接続したもの）を構成し、剛体変換の再定式化を用いて姿勢グラフ最適化として解く。ソルバーはGTSAM内のGNCであり、これは外れ値ループクロージャの除去も担う。残りのメッシュは再補間され、オブジェクトの重心/ボックスが再計算され、重なるノードが統合され（場所は0.4m以内、オブジェクトは同一ラベルかつボックス包含）、部屋が再検出される。部屋の精度はボクセル単位で以下のように評価される

Precision=1∣Re∣∑re∈Remax⁡rg∈Rg∣rg∩re∣∣re∣,Recall=1∣Rg∣∑rg∈Rgmax⁡re∈Re∣re∩rg∣∣rg∣\text{Precision}=\frac{1}{|R_{e}|}\sum_{r_{e}\in R_{e}}\max_{r_{g}\in R_{g}}\frac{|r_{g}\cap r_{e}|}{|r_{e}|},\qquad \text{Recall}=\frac{1}{|R_{g}|}\sum_{r_{g}\in R_{g}}\max_{r_{e}\in R_{e}}\frac{|r_{e}\cap r_{g}|}{|r_{g}|}

速い思考と遅い思考。 Hydraは、フレームレートで動く早期認知処理（特徴追跡、セグメンテーション）、サブ秒単位の中間レベルモジュール（メッシュ、オブジェクト、場所、フロントエンド）、そして遅い高次モジュール（ループクロージャ、バックエンド最適化、部屋検出）を並列化する — すべてCPU上で動作し、2Dセグメンテーションネットワークのみが例外である。

実験結果

SLAMにおける意義

Hydraは、3D Dynamic Scene Graphをオフラインの構築物からリアルタイム空間認知システムへと転換し、そのエンベデッド変形グラフバックエンドは、シーングラフ全体 — メッシュ、場所、オブジェクト、部屋 — を軌道と共同で最適化する最初のアルゴリズムであり、姿勢グラフ最適化を階層的マップへ一般化した。その5層の階層構造は、事実上のSpatial AI表現となり、MIT SPARKエコシステムの基盤となった — Hydra-Multi（マルチロボット）、Clio（タスク駆動のオープンセットグラフ）、Khronos（空間時間的な動態） — であり、ロボットが複数の抽象度レベルで言語指示を受け取れるようにする。

関連ノート