DANCeRS

Patwardhan 2025 · 論文

一行要約 — DANCeRSは、ガウス信念伝播(Gaussian Belief Propagation)をロボット群における分散合意形成に適用する手法である。ロボットたちは、中央サーバーを持たず、ファクターグラフ上での純粋にローカルなピアツーピアのメッセージパッシングを通じて、連続的な決定(フォーメーションの姿勢)や離散的な決定(N候補からの最善選択)といった共有の決定に合意する。

問題

ロボット群は、形状形成から集団的意思決定に至るさまざまな課題に対して、協調的な集団行動を必要とする。既存の手法は「離散的および連続的な決定空間における合意形成を別個の問題として扱うことが多く」、それぞれに専用のアルゴリズム(一方はbest-of-N投票やオピニオンダイナミクス、他方は近傍平均化やmean-shift)を用いている。DANCeRSは、単一の分散推論フレームワークによって両方の領域での合意形成を実現できるか、それも群の現実的な制約――ローカルのみの通信、動的なグラフ位相、群のサイズに対するスケーラビリティ――を守りながら実現できるかを問う。

手法とアーキテクチャ

$N$台のロボット(通信半径 $r_C$)からなる群は動的な無向グラフを形成し、問題全体は1つのファクターグラフとして表現される。結合分布はこのグラフ上で次のように因数分解される。

$$p(\mathbf{X})=\prod_{s}f_{s}(\mathbf{X}_{s}), \qquad f_{s}(\mathbf{X}_{s})\propto e^{-\frac{1}{2}\mathbf{r}^{\top}\boldsymbol{\Lambda}_{s}\mathbf{r}}, \qquad \mathbf{r}=\mathbf{z}_{s}-\mathbf{h}_{s}(\mathbf{X}_{s}),$$

信念は情報形式($\boldsymbol{\Lambda}=\boldsymbol{\Sigma}^{-1}$、$\boldsymbol{\eta}=\boldsymbol{\Lambda}\boldsymbol{\mu}$)で保持される。GBP推論は、ファクターから変数へのメッセージ、変数の信念更新、変数からファクターへのメッセージという1回のループであり、すべて厳密に近傍間のみで行われる。非ユークリッドな状態については、メッセージはExp/Logを介して現在の信念の接空間へマッピングされ、また戻される。これにより、変数は $\mathbb{R}^{M}, SO(2), SO(3), SE(2), SE(3)$ 上に存在できる。

各ロボットは2層のファクターグラフスタックを実行する。

• グローバル合意層 — ロボット $i$ は共有パラメータ $\chi$ に対する自身の解釈 ${}^{\mathcal{G}}X_{i}$ を保持する。事前分布ファクター $h_{p}={}^{\mathcal{G}}X_{i}\ominus{}^{\mathcal{G}}x_{i}^{0}$ を持ち、通信範囲内の各近傍 $j$ ごとに、明示的な交渉ファクター

$$h_{c}\left({}^{\mathcal{G}}X_{i},{}^{\mathcal{G}}X_{j}\right)={}^{\mathcal{G}}X_{i}\ominus{}^{\mathcal{G}}X_{j}=\mathrm{Log}\left({}^{\mathcal{G}}X_{j}^{-1}\cdot{}^{\mathcal{G}}X_{i}\right)$$

を持つ。GBPの変数はメモリを持たないため、各ロボットは時間的に連結された $W$ 個のコピーからなるスライディングウィンドウを保持する。最も古いものが削除されると、その周辺分布が新たな事前分布となる。これにより、あるロボットがグループから離脱しても、共分散は弱まりつつも交渉された平均値は保持される。

• 連続的合意としての離散的決定 — $N_D$ 個の選択肢に対して、$\mathcal{M}=\mathbb{R}^{1}$ とし、決定を読み出す際にのみ量子化を行う: $\gamma(x)=\lfloor N_{D}\cdot x\rfloor$、$\gamma^{-1}(k)=k/N_{D}$。交渉自体はガウス的かつ連続のままである。
• パス計画層 — ある時間ホライズンにわたる状態 $[x,y,\theta,\dot{x},\dot{y},\dot{\theta}]^{\top}$ を扱う。新たに非ホロノミックな一輪車モデルのファクター $h_{u}=\dot{x}\cos\theta-\dot{y}\sin\theta$(これを0に駆動し、速度を進行方向と一致させる)と、平滑化されたロボット間衝突ファクター $h_{r}=\exp(-|\mathbf{x}_{k,i}-\mathbf{x}_{k,j}|/d_{min})$ を導入する。形状形成では、目標位置はフォーメーション上の点に対するKD木最近傍探索によって選ばれ、近傍が通信範囲を離れると減衰する「占有重み付け」で補強される。

実験結果

• 連続合意(形状形成): 収束は、ロボット間の平均偏差が位置で0.1 m未満、方位で0.01 rad未満となることと定義される。100×100 mのアリーナでの50回の試行において、DANCeRSはSun et al. 2023のmean-shift合意ベースラインよりも(メッセージパッシングの反復回数において)1桁高速に収束し、収束速度は $r_C$、ロボット数 $N_R$、ウィンドウ $W$ の増加とともに加速する。また、単一の連結成分に限定されるmean-shift法では実現できない、非連結な形状(’!’、‘wifi’、笑顔マーク)の形成も可能である。
• 離散合意: エントロピーベース(ECA)および確率論的(PCA)の合意ベースラインと比較すると、$r_C=6$ mでECAは全く収束しなかった。より大きな $r_C$ では、DANCeRSは $N_R$ が増加してもほぼ一定の反復回数で済んだ。パラメータスイープの結果、合意ファクター強度の好ましい上限として $\sigma_{c}=0.5/N_{D}$ が支持される。
• 情報を持つロボット($N_R=500$、$r_C=6$ m):単一のシードロボット($\zeta=0.002$)を用いた場合、DANCeRSは80%の試行でシードの決定に収束し、$\zeta\geq0.01$では100%に達した。これに対し、PCAは $\zeta=0.002$–$0.05$ で9%→94%、ECAは常に0%であった。
• コスト: ロボット間の各メッセージは $n$ 次元ベクトルと $n\times n$ の対称共分散行列であり、形状形成では $n=3$、離散合意では $n=1$ である――低電力デバイスでも十分に軽量である。

SLAMにおける意義

群スケールでの協調SLAMは、DANCeRSが対象とする問題そのものに直面する。集中型のマップサーバーは帯域幅と信頼性のボトルネックとなり、分散オプティマイザは非同期性とローカルのみの通信に耐えなければならない。GBP方式の合意形成が、リー群上の変数に対しても、動的なグラフの下でも群全体にわたって機能することを示したことで、ファクターグラフのメッセージパッシングが分散的な推定・マッピング・プランニング・協調のための共通機構となるというビジョン――グラフプロセッサ上でBAを解くのと同じ計算――を後押ししている。

関連ノート

• FutureMapping 2
• BA on Graph Processor
• Factor graph
• Kimera-Multi
• Swarm-SLAM
• Centralized vs Decentralized