技術要約：Edge to Edge: 多ロボットシステムのためのフローに着想を得たスケジューリング・プランナー

問題提起

本論文は、多数のロボットが障害物の多い環境を一方の側（ソース）から反対の側（シンク）へと横断させる際の調整という課題に取り組んでいる。従来のマルチロボット経路計画は、多くの場合、点対点のナビゲーションや静的なマルチエージェント経路探索（MAPF）に焦点を当てているが、これらの手法はロボットの密度が高い場合、混雑、デッドロック、および横断時間の非効率化を招きやすい。既存のフロントエンド・プランナーは、単純な点対点の接続や、グリッドベースのMAPFアルゴリズム（A*やCBSの変種など）に依存していることが多く、それらはロボット間の相互作用を無視しているか、あるいは動的なリアルタイム実行に適さない硬直した経路を生成してしまう。さらに、多くのフローベースの最適化手法は計算負荷が高く、オフラインでの使用を想定しており、個々のロボットに対してリアルタイムで実行可能な軌跡を生成する能力を欠いている。

核心となる目的は、経路長、迂回、および待機時間のバランスを取りつつ、ロボットが混雑した空間を集合的に流れるシナリオにおいて、メイクスパン（最後のロボットが目的地に到達する時刻）を最小化することである。

手法

著者らは、既存のバックエンド衝突回避アルゴリズム（具体的にはORCA）と互換性のあるフロントエンド・モジュールとして機能する、**フローに着想を得たスケジューリング・プランナー（Flow-Inspired Scheduling Planner）**を提案している。このフレームワークは、主に3つのステージで構成される。

1. ネットワーク構築

グリッドマップとフローネットワークの間の溝を埋めるため、著者らは環境を2つの補完的な表現に分解する。

• 隣接ネットワーク（Adjacency Network）: Boustrophedon細胞分解（Boustrophedon Cellular Decomposition）を用いて、マップをセルに分割する。セル間の境界をサンプリングして「Pos（位置）」を作成し、それらを「Node（ノード）」にグループ化する。エッジは隣接するセル間のノードを接続し、潜在的な移動経路を表すグラフ $G=\{V, L\}$ を形成する。
• 混雑マップ（Congestion Map）: 環境をさらに均一なサブリージョンに分割し、容量を推定する。各リージョンの容量は、その面積とロボットの安全半径に基づいて計算され、過大評価を防ぐための冗長係数を考慮している。この分離により、容量の二重計上を避けた、共有された空間制約の精密なモデリングが可能になる。

2. フロー・プランナーの構成要素

プランナーは、以下の3つのシーケンシャルなモジュールをリアルタイムで実行する。

• パスセット探索（Path Set Search）: すべての可能な経路を列挙することは計算量的に不可能であるため、有望な候補パスのサブセットを特定する。ロボットの現在位置付近とターゲットゴール付近の境界ノードを特定し、次にダイクストラ法を用いて、これらの特定の入口と出口を接続するパスを見つける。この「スタートから出口へ、入口から目的地へ」という戦略は、決定の質を維持しながら探索空間を縮小させる。
• パスノード選択（Path Node Selection）: パス選択を混合整数計画問題（MIP）として定式化する。候補パスを2つのコストに基づいて評価する。
  • 待ち行列コスト ($f_{Que}$): 混雑マップに対するパスの初期セグメントを分析することで、将来の混雑を予測する。ロボットの数が容量を超えるリージョンへと導くパスに対してペナルティを与え、平方のオーバーロード項を用いることで、混雑を強く抑制する。
  • 走行コスト ($f_{run}$): 過度な経路長に対してペナルティを与える。
    最適化器は、これら両方のコストの合計を最小化するように全ロボットのパスセットを選択し、迂回と待機時間のバランスを効果的に取る。
• 位置割り当て（Position Allocation）: ノードのシーケンスが決定されると、プランナーは各ノードに特定の「Pos」座標を割り当てる。ヒューリスティックな強欲（greedy）アルゴリズムが使用される。最初のノードについては、クラスター化を防ぐためにユークリッド距離と現在の位置占有率のバランスを取る。後続のノードについては、スムーズな遷移を確保するために、前の位置に最も近い利用可能な位置を選択する。

3. 実行

生成された離散的なパスは、衝突回避のためのORCAを使用するバックエンド・コントローラーに渡され、安全を確保しながら軌跡が実行される。プランナーは、動的な変化に適応するため、定期的に（例：シミュレーション内で2秒ごと）実行される。

主な貢献

1. フローに着想を得たスケジューリング: 環境をフローベースのネットワーク構造に分解し、混雑レベルに基づいてロボットをパスにリアルタイムで割り当てることを可能にする、新しいフロントエンド・プランナー。
2. リアルタイムの効率性: 網羅的な探索を避け、疎なネットワーク抽象化を利用することで、大規模なシステム（最大500台のロボット）をサポートする高い計算効率を実現する。
3. 混雑を考慮した最適化: リージョンの容量を明示的にモデル化し、将来の混雑を予測することで、メイクスパンを最小化するために迂回と待機時間のバランスを取ることができる。
4. 検証: 様々なマップタイプ（森林、迷路、障害物、廊下）およびロボット密度（10〜500台）にわたる広範なシミュレーション、および10台のドローンを用いた実世界の飛行テストを通じて、フレームワークを検証している。

実験結果

• 小規模（10〜100台のロボット）: 提案された「Flow」手法は、A*、ECBS、P-SIPP、TVMAを含むベースラインを一貫してメイクスパンにおいて上回った。ロボットの密度が増加するにつれて特に優位性が示され、最高のMAPFベースラインと比較してメイクスパンを約5〜9%削減した。
• 大規模（100〜500台のロボット）: 大規模なシナリオにおいて、Flow手法は最先端のMAPFアルゴリズム（CBSH2-RTC、LNS2）および混雑考慮型手法（CMPP）を大幅に上回った。ベースラインに対して4〜15%のメイクスパン改善を達成した。特筆すべきは、LNS2は混雑を軽減したが、しばしば過度な迂回を招いたのに対し、Flow手法は混雑回避と経路長のバランスをより良く取っていた点である。
• 計算時間: Flowプランナーは優れたスケーラビリティを示した。500台のロボットに対して、平均プランニング時間は1秒未満（約0.9秒）であったが、オフラインのMAPF手法は、はるかに長い時間を要するか、あるいはスケールすることに失敗することが多かった。
• 実世界テスト: 障害物の多い限定された環境における10台のDJI Telloドローンの飛行テストにより、本手法の実用的な実現可能性が確認された。システムは、衝突やデッドロックなしに、すべてのドローンを一方の側から他方へとナビゲートすることに成功した。
• 密度分析: Flowアルゴリズムは、他の手法と比較して、ピーク時のロボット密度および「待機状態」にあるロボットの数を低く維持しており、これは利用可能な空間をより効率的に活用していることを示している。

重要性と主張

本論文は、この研究が、複雑な環境における方向性を持ったマルチロボット横断に特化した、リアルタイムのフロー着想型スケジューリング・プランナーに寄与することを主張している。その重要性は、標準的な点対点プランナーでは見落とされがちな、集団的に環境を横断（エッジ・トゥ・エッジ）するための協調動作という、倉庫物流や都市配送において一般的なシナリオに対処している点にある。

著者らは、本手法はバックエンドの衝突回避を置き換えるものではなく、むしろフロントエンドの計画段階を強化するものであることを強調している。ネットワークフローの原理を活用して混雑を未然に管理することで、システムはよりスムーズで高速な集合的横断を実現する。論文では、現在の手法は一方向のフロー（ソースからシンクへ）に最適化されており、全方向または多方向のフローをサポートするようにフレームワークを拡張することが今後の研究課題であると謙虚に述べている。