本研究は、ロボット群（MAPFエージェント）と、制御不能な動的エージェント（UA）が混在する共有環境における、実行遅延と衝突問題に対処するためのフレームワークである。従来のMAPF研究は、遅延発生時の完全性の維持に主眼を置いていたが、本研究はUAの時空間的な移動パターンを事前に学習し、中央集権的な経路計画に組み込むことで、環境情報を活用した解の品質向上を目指している。具体的には、環境のトポロジーや社会的規範から生じるフローを「Maps of Dynamics (MoDs)」として符号化し、エージェントの行動とUAの期待移動を一致させるガイダンス手法を導入している。これにより、UAとの接触自体を未然に防ぐことを目的としている。
本研究の主な貢献は、UAの統計的な移動パターンを探索ベースのMAPFアルゴリズムにシームレスに統合するFA-MAPFフレームワークの提案である。第一に、UAの速度と方向を連続的なマルチモーダル分布として扱うCircular-Linear Flow Field (CLiFF) Mapを導入し、Semi-Wrapped Gaussian Mixture Models (SWGMMs) を用いてその分布を表現する手法を確立した。第二に、学習されたフロー情報をエッジコストに反映させるフローコスト関数 $C_{\text{flow}}$ を定義し、既存の $\epsilon$-suboptimalなMAPFアルゴリズム（ECBS等）と組み合わせることで、劣最適性の範囲を理論的に保証した。第三に、シミュレーションおよび実世界の人間移動データを用いた広範な実験により、スループットを維持しながらUAとの衝突を最大55%削減できることを実証した。
FA-MAPFは、グラフ $G=(V, E)$ 上で、エージェントの行動 $a$ と地点 $v$ におけるUAの移動分布 $\text{MoD}$ との整合性を評価する。UAの運動パターンは、方向 $\theta \in [-\pi, \pi)$ と速度 $s \in [0, \infty)$ を持つ $\text{SWGMM}_v$ としてモデル化され、フローコストは以下の式で計算される：
$$C_{\text{flow}}(v, a, \text{MoD}) = -\log \left( \frac{1}{N_v} \sum_{i=1}^{N_v} \exp \left( -\frac{1}{2} (\theta_a - \mu_i)^T \Sigma_i^{-1} (\theta_a - \mu_i) \right) \right)$$
ここで、エッジの重み $w(v, u, a)$ は、ステップコスト $c_{\text{step}}$ とフローコストにスケーリング係数 $\lambda$ を乗じたものの和 $w(v, u, a) = c_{\text{step}}(v, u, a) + \lambda C_{\text{flow}}(v, a, \text{MoD})$ として更新される。エージェントの速度は $v_{\text{agent}} = 1$ と仮定され、待機行動については他の移動行動の平均角度を用いて計算を行う。この手法は、ECBSのようなアルゴリズムと組み合わせることで、フローコストが $0 < C_{\text{flow}} \le C_{\text{max}}$ の範囲にあるとき、解のコストが元の最適解 $C^*$ に対して $(1 + \epsilon \frac{C_{\text{max}}}{c_{\text{min}}})$ の範囲に収まることが保証される。
評価は、2つの異なる実験設定で行われた。第1実験では、Sternらのベンチマークマップを用い、サブオプティマリティ係数 $w=1.1$ のEECBSを使用して、MAPFエージェント数に対する解決率と平均実行時間を検証した。第2実験では、Lifelong MAPF設定において、高レベルソルバーにRHCR（ECBS使用、$w=1.1$）、低レベルソルバーにSIPPを用いたFA-RHCRの性能を評価した。指標には、1イテレーションあたりの平均解決時間、スループット、およびUAとの衝突回数（ユークリッド距離が $r_{MAPF} + r_{UA} = 1\text{m}$ 未満となる頻度）を用いた。実験環境は Intel i7-12700K CPU、32GB RAM であり、マップには8種類のベンチマークおよび実世界の人間移動データを含むATCデータセットが使用された。
実験結果により、FA-MAPFはUAとの衝突を最大55%一貫して削減できることが示されたが、これには計算時間の増加というトレードオフが存在する。実行時間の増加は、ガイダンスグラフにおける非一様な遷移コストが低レベル探索におけるノード展開数を増加させることに起因する。また、マップの構造によって効果が異なり、`den312d`のような部屋状の構造ではフローの誘導が強く働くが、迷路のような環境では回避スペースの不足により効果が限定的となる。実世界のATCショッピングモールデータや倉庫のハイウェイパターンにおいても有効性が確認された。一方で、UAが最短経路を無制限に選択し、明確なフローパターンが形成されない環境では、衝突削減の効果が得られないという限界も明らかになった。
本研究では、制御不能な動的エージェントが存在する共有環境において、ロボット群の衝突を軽減するための新しいフレームワークである Flow-Aware Multi-Agent Path Finding (FA-MAPF) を提案している。従来の MAPF 研究は遅延発生時の完全性の維持に主眼が置かれていたが、FA-MAPF は制御不能なエージェントの学習された移動パターンを中央集権的な MAPF アルゴリズムに統合することで、環境情報を活用した解の品質向上を図る。評価は、シミュレーションによる動的エージェントを用いた多様なベンチマークマップ、および記録された人間の軌跡を用いた実世界のマップを用いて行われた。実験結果により、FA-MAPF はタスクの効率性を損なうことなく、制御不能なエージェントとの衝突を最大 55% 一貫して削減できることが示された。
本研究は、制御不能な動的エージェントが存在する共有環境において、中央集権的なマルチエージェント経路計画（MAPF）の実行遅延を軽減するための「Flow-Aware Multi-Agent Path Finding (FA-MAPF)」を提案している。提案手法は、環境のトポロジーや社会的規範から生じる時空間的な移動パターンを符号化したMaps of Dynamics (MoDs) を活用し、動的エージェントのマルチモーダルな確率分布を探索ベースのMAPFアルゴリズムに統合するものである。具体的には、エージェントの可能な行動と動的エージェントの局所的な期待移動を一致させるコスト関数を用いてエッジの重みを計算するガイダンス手法を採用しており、事後的な再計画や能動的な検知を必要とせずに、計画段階で暗黙的にフローを考慮する。評価実験では、既存のMAPFベンチマークおよび実世界のデータセットを用い、Lifelong MAPF設定における実行時間、スループット、および制御不能なエージェントとの衝突回数を指標として検証を行っている。実験結果は、スループットをほぼ維持しつつ、実行時間の増加と制御不能なエージェントとの衝突回数の減少との間に明確なトレードオフが存在することを示している。
本セクションでは、提案手法であるFA-MAPFの基礎となるMAPF、Dynamicsのマップ（MoD）、およびGuidanceの概念を定義している。MAPFは、頂点と辺からなる無向グラフ $G=(V, E)$、エージェントの集合 $\mathcal{A}$、および各エージェントの開始頂点 $s_i$ と目標頂点 $g_i$ によって定義され、各エージェントは各タイムステップで移動または待機（$v_{t+1} = v_t$）のいずれかのアクションを選択する。FA-MAPFは、制御不能なエージェントとの衝突を回避するために、Circular-Linear Flow Field (CLiFF) MapというMoDを利用し、局所的な運動パターンを速度 $\mathbf{v} = (\theta, s)$ 上の連続的なマルチモーダル分布としてモデル化する。この分布は、方向 $\theta \in [-\pi, \pi)$ と速度 $s \in [0, \infty)$ を扱い、Semi-Wrapped Gaussian Mixture Models (SWGMMs) を用いて、複数の Semi-Wrapped Normal Distributions (SWNDs) $\mathcal{N}_{sw}(\mathbf{v} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, w)$ の加重和 $\sum_{k \in \mathcal{K}} \pi_k \mathcal{N}_{sw}(\mathbf{v} | \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k, w_k)$ として表現される。FA-MAPFは、これらの学習された運動パターンをGuidance Graph $\mathcal{G}_g = (V, E, \mathbf{w})$ のエッジコスト $w_{uv}$ に統合することで、制御不能なエージェントとの相互作用を最小化するように計画プロセスを誘導する。既存のRobust MAPFが実行遅延に対する回復力（resilience）を高めることに焦点を当てているのに対し、本手法は遅延の原因となる制御不能なエージェントとの接触自体を減らすことを目的としており、両者は補完的な関係にある。
本セクションでは、制御不能なエージェント（UA）の学習された運動パターンを考慮してMAPF問題を解く手法であるFA-MAPFを提案している。FA-MAPFは、観測されたUAの軌跡データから構築されたMotion Distribution Map (MoD) を用い、エージェントの行動 $a$ とその地点におけるSWGMM（$\text{SWGMM}_v$）との整合性を評価するフローコスト $C_{\text{flow}}(v, a, \text{MoD})$ を定義する。具体的には、マハラノビス距離をガウス混合モデルへ拡張した式 $C_{\text{flow}}(v, a, \text{MoD}) = -\log \left( \frac{1}{N_v} \sum_{i=1}^{N_v} \exp \left( -\frac{1}{2} (\theta_a - \mu_i)^T \Sigma_i^{-1} (\theta_a - \mu_i) \right) \right)$ を用いて計算され、エッジの重みは $w(v, u, a) = c_{\text{step}}(v, u, a) + \lambda C_{\text{flow}}(v, a, \text{MoD})$ と更新される。実装上、エージェントの速度は一定（$v_{\text{agent}} = 1$）と仮定され、待機行動については他の移動行動の平均角度を用いることで計算を可能にしている。本手法は、ECBSのような完全かつ（劣）最適なMAPFアルゴリズムと組み合わせることで、その性質を継承する。さらに、フローコストが $0 < C_{\text{flow}} \le C_{\text{max}}$ の範囲にある場合、$\epsilon$-bounded suboptimalなアルゴリズムが返す解のコストは、元のコスト関数における最適解のコスト $C^*$ に対して $(1 + \epsilon \frac{C_{\text{max}}}{c_{\text{min}}})$ の範囲で劣最適性が保証されることがLemma 1により示されている。
本評価では、制御不能なエージェント（UA）との衝突回避能力、計算実行時間、およびタスク効率への影響を検証するため、2つの実験を行っている。第1実験では、Sternらによるベンチマークマップを用い、サブオプティマリティ係数 $w=1.1$ のEECBSを用いて、MAPFエージェント数に対する解決率（5秒以内の制限時間内での25シナリオ中の割合）と平均実行時間を評価している。第2実験では、高レベルソルバーにRHCR（ECBS使用、$w=1.1$）、低レベルソルバーにSIPPを用いたLifelong MAPF問題を対象とし、FA-RHCR（flow-aware版）の性能を、1イテレーションあたりの平均解決時間、スループット（タイムステップあたりの完了タスク数）、およびUAとの衝突回数（MAPFエージェントとUAのユークリッド距離が半径の和 $r_{MAPF} + r_{UA} = 1\text{m}$ 未満となる頻度）によって評価する。UAの挙動は、開始・目標地点の選定方法に基づき、random、directed、speedの3タイプが定義されており、これらはMoD（Movement of Distribution）の有効性に影響を与える。実験環境はIntel i7-12700K CPU、32GB RAMであり、マップには8種類のベンチマークおよび実世界の人間移動データを含むATCデータセットが使用されている。
実験1では、EECBSを用いたスケーラビリティ評価において、FA-MAPFはフローコストを考慮しない手法と比較して計算効率が低下するものの、マップの構造に依存する特性を持つことが示された。具体的には、`den312d`や`ht_chantry`のような部屋状の構造を持つマップでは、フローの誘導効果が強く働く一方で、迷路のような環境では回避スペースの不足により効果が限定的となる。実験2のRHCRを用いた評価では、FA-MAPFは実行時間の増加と引き換えに、UA（Unplanned Agent）との衝突を最大55%削減することに成功している。この実行時間の増加は、ガイダンスグラフにおける非一様な遷移コストが低レベル探索におけるノード展開数を増加させることに起因する。また、実世界のデータ（ATCショッピングモール）を用いた検証や、倉庫環境におけるハイウェイパターン（一方通行のフロー）の適用においても、FA-MAPFは衝突を大幅に低減できることが確認された。一方で、UAが最短経路を無制限に選択し明確なフローパターンが形成されない環境では、衝突削減の効果は得られないという限界も示されている。
本研究では、制御不能なエージェントの移動パターンに関する統計的な学習情報を中央集権的なMAPFに組み込む手法として、Flow-Aware MAPF (FA-MAPF) を提案している。評価実験の結果、FA-MAPFは制御不能なエージェントとの衝突を大幅に減少させ、局所的な経路修正のための低レベルな衝突回避メカニズムへの依存度を低減できることが示された。今後の研究方向として、PIBTやLaCAMといった大規模MAPFアルゴリズムへのフロー認識の統合、制御不能なエージェントとの衝突が協調マルチロボットシステムの効率指標に与える影響の調査、およびFA-MAPFを時変的な動的マップ（Maps of Dynamics）へと拡張することが挙げられている。本研究は、マルチロボットシステムを、外部からの妨害がない完全制御空間から、より困難でインタラクティブな環境へと移行させるための基礎を築くものである。