Stigmergic Skeleton Fields: A Bio-Inspired Framework for Decentralized Multi-Robot Navigation via Localized Incremental Re-Skeletonization

技術要約：スティグマジー・スケルトン・フィールド (SSF)

問題提起
動的な環境におけるマルチロボットのナビゲーションには、迅速な再計画が可能なほどコンパクトでありながら、自己組織的な協調をサポートできるほど豊かな表現形式が必要である。従来のアプローチは、トレードオフに直面している。A*、RRT*、D* Liteなどで用いられる細粒度の占有格子（Occupancy Grid）は、高い経路忠実度を提供するが、特にマルチエージェント・システムにスケールアップする場合、高い計算コストとメモリ使用量に悩まされる。逆に、トポロジカル・スケルトン（中央軸やボロノイ図）は探索空間を大幅に削減するが、動的な修復や混雑を考慮した協調メカニズムを欠くことが多い。さらに、グリッド上でのアントコロニー最適化（ACO）のような既存のバイオインスパイアード手法は、解像度とともにスケーラビリティが低下し、Conflict-Based Search (CBS) のような中央集権的なマルチエージェント経路探索（MAPF）アルゴリズムは、エージェント数が増加するにつれて計算が困難になる。本論文は、トポロジカルグラフの効率性と、スティグマジーによる協調の適応性を組み合わせ、動的な障害物を（全再計算を行うことなく）処理できる分散型フレームワークの必要性に取り組んでいる。

手法
著者らは、中央軸スケルトングラフと、アントコロニー型のフェロモン場を結合し、さらに局所的増分再スケルトン化 (Localized Incremental Re-skeletonization: LIR) によって拡張されたスティグマジー・スケルトン・フィールド (SSF) フレームワークを提案している。

1. スケルトングラフの抽出: 環境（二値占有格子）は、1次元の中央軸スケルトングラフ $G=(V, E)$ に削減される。ノードは分岐点と端点を表し、エッジはユークリッド長と最小クリアランスを保持するスケルトン枝を表す。これにより、探索空間は $O(n)$ の格子セルから $O(S)$ のスケルトンピクセルへと削減される（ここで $S \ll n$）。
2. スティグマジー・フェロモン場と混雑考慮型コスト: ロボットは、グラフのエッジ上にある共有フェロモン場 $\tau_{uv}$ を介して間接的に相互作用する。ロボットにとっての経路コスト $w_{uv}$ は、以下の要素によって変調される：
   • フェロモンレベル: 他者が使用した経路を推奨する（正のフィードバック）。
   • クリアランス: より広い通路に報酬を与える。
   • 混雑ペナルティ: 重要な追加要素であり、瞬時の使用率 $u_{uv}$ が閾値 $\kappa$ を超えた場合にコストが増加する。これにより、複数のロボットが同じ狭いボトルネックに集中することを防ぐ。これは、独立した最短経路計画においてよく見られる失敗モードである。
3. 局所的増分再スケルトン化 (LIR): 動的な障害物が出現または消失した場合、LIRはグラフ全体を再構築することを回避する。代わりに、以下の手順を実行する：
   • 変化の周囲に（マージン $p$ でパディングされた）局所的なバウンディングボックスを特定する。
   • このボックス内のみで中央軸と局所的なトポロジを再計算する。
   • 新しい局所サブグラフをグローバルグラフに接合し、影響を受けていない領域のフェロモン状態を保持する。
   • 理論的解析（定理1）によれば、パディングが最大の中央軸応答半径を超えている限り、パディングされたボックス外のスケルトンは全再計算の結果と同一であることを保証している。

主な貢献

• スティグマジーとトポロジーの統合: 固定されたボロノイ分割にACOを適用する先行研究（例：海洋サンプリングのためのXiongら）とは異なり、SSFはフェロモン力学を動的な中央軸スケルトンと結合させている。
• LIRアルゴリズム: 環境の変化に対して、トポロジカル構造をその場で修復するための正式な手続きを提供し、グローバルな再計算なしに妥当性を確保する。
• 混雑考慮型ルーティング: エッジの飽和をペナルティ化するように設計された特定のコスト関数（式1）により、明示的なロボット間通信なしに分散型の協調を可能にする。
• 厳格なベースライン比較: 本論文は、SSFを7つのベースライン（静的スケルトンDijkstra、生グリッドACO、RRT*、A*、Theta*、PRM*、およびスケルトン制限付きCBS）と比較評価している。また、アルゴリズムの速度とグラフサイズの効果を分離するために、粗視化されたグリッド上でLIRとD* Liteを比較する制御実験も含まれている。

結果

• 経路品質 vs 効率: SSFは、経路長において静的スケルトンDijkstraベースラインの3～8%以内の誤差（オフィスや混雑した環境において統計的に有意）で一致しつつ、混雑回避機能を追加している。
• 動的な再計画速度:
  • LIRは、最大1000x1000セルのマップにおいて、完全な再スケルトン化よりも最大1桁速い。
  • LIRは、フル解像度のグリッドにおけるD* Liteよりも30～200倍高速である。
  • 重要なニュアンス: グラフのノード数がスケルトンと同程度になるように粗視化されたグリッドを用いた制御実験では、D* Liteの方がLIR（35ms）よりも高速（3ms）であった。しかし、その粗視化グリッドは、狭い通路を保守的にブロックした結果、スケルトンの経路よりもほぼ2倍長い経路を生成した。論文は、LIRの利点は単なるグラフサイズではなく、経路の忠実度を犠牲にすることなく小さなグラフを実現できるスケルトンの能力にあると結論付けている。
• スケーラビリティ:
  • ロボット数: ロボット数を5台から100台に増やしても、1台あたりの計画時間はわずか1.4倍しか増加しない。
  • メモリ: スケルトングラフは、同等の8連結グリッドグラフと比較して、メモリフットプリント（ピークRSS）を約14倍削減する。
  • 動的障害物: LIRは、障害物の出現と除去の両方を、ほぼ線形かつ対称的なコストで処理できる。
• マルチエージェント性能: 少数のエージェント（$N \le 4$）の場合、スケルトン制限付きCBSはSSFと一致する最適解を見つける。より多くのエージェントの場合、CBSは制限時間内に終了できないが、SSFはすべてのインスタンスを5ms未満で解決する。
• ハードウェア検証ステップ: 著者らは、シミュレーション内でSSF経路を実行するために、ローカルセンシングを備えた連続差動駆動コントローラを実装した。これは物理的検証への一歩を示しているが、実際のハードウェアへのデプロイは行われていない。

意義と主張
本論文は、SSFが最短経路のための普遍的な解決策（グリッドベースのA*/Theta*の方が短い経路を見つける）でも、あるいは決定論的な小規模チームの協調（$N \le 4$ ではCBSが優れている）のためのものでもないことを控えめに主張している。むしろ、その意義は、動的な環境における実用的で分散型の、混雑を考慮したマルチロボット協調フレームワークを提供することにある。

著者らは、コアとなる貢献は、混雑考慮型のフェロモン場と局所的修復メカニズム（LIR）の組み合わせであることを強調している。彼らは、D* Liteに対する速度の優位性が部分的にスケルトンのグラフサイズの小ささに起因していることを明示しているが、その独自の価値は、手動でグリッドを粗視化する際に生じる経路品質の低下を招くことなく、適応的にこの小さなサイズを実現できるスケルトンの能力にあるとしている。本研究はシミュレーションベースであり、将来の展開のためにROS 2パッケージが提供されている。また、センサーノイズ、位置推定誤差、および分散通信に関する物理的な検証が、次の必要なステップであることを認めている。