FutureMapping 2

Davison 2019 · 論文

一行要約 — FutureMappingのチュートリアル形式の続編。Spatial AIの中核となる分散アルゴリズムとして、因子グラフ上のガウス信念伝播を展開し、情報形式のメッセージパッシング方程式を完全に導出し、コード付きで表面再構成と段階的SLAMシミュレーション上で実証する。

問題

FutureMapping 1はビジョンを論じたが、本論文はそのアルゴリズム的な実質を提供する。標準的なSLAMバックエンド(g2o、GTSAM、Ceres)は、集中的な大域解法によって因子グラフの推論を解いており、実プロダクトの制約下で動作するスマートなロボットやデバイスが必要とする分散的・段階的で常時稼働する推定、あるいは記憶と計算が数千のコアに分散した新興のグラフプロセッサとの相性が悪い。本論文は、GBPがこの未来にとって「適切な性質」を持つと論じる:完全に局所的な計算と記憶、任意のメッセージスケジュール、そしてグラフの動的な変更の容易さである。

手法とアーキテクチャ

GBPは、すべてのメッセージと信念がガウス分布であるループのある信念伝播であり、情報形式 η=Λμ\eta = \Lambda\mu(情報ベクトルと精度行列)で保持される。これはランク不足の制約なし変数を扱えるようにし、ガウス分布の積を単純なパラメータの加算にする。測定値zs\mathbf{z}_sをモデルhs\mathbf{h}_sと測定精度Λs\Lambda_sで符号化する因子は

fs(xs)=Kexp⁡(−12(zs−hs(xs))⊤Λs(zs−hs(xs))).f_s(\mathbf{x}_s) = K \exp\left( -\tfrac{1}{2} (\mathbf{z}_s - \mathbf{h}_s(\mathbf{x}_s))^{\top} \Lambda_s (\mathbf{z}_s - \mathbf{h}_s(\mathbf{x}_s)) \right).

線形化。 非線形因子はヤコビアンJs\mathrm{J}_sを用いて、アンカーx0\mathbf{x}_0周りの局所ガウス分布に変換される。

ηs=Js⊤Λs(Jsx0+zs−hs(x0)),Λs′=Js⊤ΛsJs,\eta_s = \mathrm{J}_s^{\top}\Lambda_s\left( \mathrm{J}_s\mathbf{x}_0 + \mathbf{z}_s - \mathbf{h}_s(\mathbf{x}_0) \right), \qquad \Lambda_s' = \mathrm{J}_s^{\top}\Lambda_s\mathrm{J}_s,

これはまさにGauss-Newtonステップの構成要素であるが、因子ごとに局所的に保持され、望むだけ頻繁に(あるいは稀に)再線形化できる。

変数から因子へのメッセージは、他のすべての入力メッセージの単純な和である:ηms=∑lηml\eta_{ms} = \sum_{l} \eta_{ml}およびΛms=∑lΛml\Lambda_{ms} = \sum_{l} \Lambda_{ml}、対象因子fsf_sを除くxm\mathbf{x}_mの隣接ノード全体にわたる。因子から変数へのメッセージは、入力メッセージを分割された因子パラメータに加算(条件付け)し、出力変数が先頭になるよう並べ替え、標準的な情報形式のシューア補完によって残りを消去する。

ηMα=ηα−ΛαβΛββ−1ηβ,ΛMα=Λαα−ΛαβΛββ−1Λβα.\eta_{M\alpha} = \eta_\alpha - \Lambda_{\alpha\beta}\Lambda_{\beta\beta}^{-1}\eta_\beta, \qquad \Lambda_{M\alpha} = \Lambda_{\alpha\alpha} - \Lambda_{\alpha\beta}\Lambda_{\beta\beta}^{-1}\Lambda_{\beta\alpha}.

最も高コストな局所演算は小さな行列の逆行列Λββ−1\Lambda_{\beta\beta}^{-1}であり — 単項/二項因子の場合、その次元は多くても1つの変数の次元にとどまる。木(チェーン)グラフではGBPは各方向に1回のスイープで厳密に解ける;SLAMのようなループを持つグラフでは良い近似に反復収束し、著者らは収束が「メッセージスケジューリングに驚くほど依存しない」ことを発見した — これが各ノードが独自のコアやデバイス上で稼働できる性質である。

ロバスト因子。 M推定器は純粋に局所的な計算で組み込まれる:因子のマハラノビス距離MsM_sを評価し、これが閾値NσN_\sigma(Huberの二次から線形への遷移)を超える場合、そのメッセージパスにおいて因子のηs\eta_sとΛs′\Lambda_s'を次式で再スケールする。

kR=2NσMs−Nσ2Ms2,k_R = \frac{2N_\sigma}{M_s} - \frac{N_\sigma^2}{M_s^2},

これにより、メッセージは等価なエネルギーを持つガウス分布の精度を伝える(閾値を超えた領域で定数となるカーネルはkR=Nσ2/Ms2k_R = N_\sigma^2/M_s^2を用いる)。これは「遅延データアソシエーション」を実現する:因子のインライア/アウトライア状態は、証拠が蓄積するにつれて変化し続けうる。

コード付きの実例:補間された高さ測定とペアワイズ平滑化因子を用いた1次元表面再構成(ループのないチェーン、厳密に解ける);2次元制約グラフ;そしてオドメトリとランドマーク因子を伴う対話的な段階的2D SLAMシミュレーション(bpslam.py)であり、ロボットが変数と因子を追加していく中でメッセージパッシングは単に継続する — ループクロージャの際でも一括再解法は不要である。事前分布、弱いアンカー、動的に編集された因子強度は、グラフを通じて自動的に伝播する。

実験結果

本論文はチュートリアルであり、その評価はシミュレーションによる定性的なものである:段階的SLAMシミュレーションにおけるGBPの推定は、バッチ解法と整合しており、ループクロージャを含む動的に変化するグラフに余裕をもって対応する;50回に1回の測定が大きな誤差で汚染され、すべての測定にHuber因子を適用した場合、GBPは局所的かつ遅延的にアウトライアを検出する — 誤った測定は、より良い仮説を支持する十分な証拠が蓄積されるまで、しばしばずっと後になって特定される。収束後に因子の精度を変更すると、大域的な調整なしに迅速に伝播する。完全な導出とシミュレーション図については論文を参照。

SLAMにおける意義

本論文はSLAM研究者にとってGBPの標準的でわかりやすい入門であり、実際の高速化(GraphcoreのIPU上のバンドル調整)と分散マルチロボット推論(DANCeRS)を実証した後続研究を触発した。その中核的な約束 — 集中型ソルバーなしの因子グラフSLAM — は、マルチロボットシステムや、将来のARデバイスに搭載されることになる大規模並列ハードウェアに直接関わってくる。

関連ノート