Dynamic Decentralized 3D Urban Coverage and Patrol with UAVs

技術要約：UAVによる動的な分散型3D都市部カバレッジおよびパトロール

問題の定式化
本論文は、自然災害または人為的災害（火災、洪水、地震など）が発生した後の3D都市環境において、協調的な周期的カバレッジおよびパトロールを行うための無人航空機（UAV）スウォームの調整という課題に取り組んでいる。環境は、右柱状体として表される建物の一群としてモデル化されており、目的は、物体検出のための特定の画像品質制約を満たしながら、すべての垂直なファサード（外壁）と屋根の表面をカバーすることである。

主な制約および仮定は以下の通りである：

• 限られたリソース： エージェントの数は連続的なカバレッジを提供するには不十分であるため、システムは「周期的」なカバレッジを提供しなければならない。
• 3Dの複雑性： エージェントは障害物（建物自体）を回避しながら航行し、ファサードと屋根の両方を視認するためにカメラのチルト（ピッチ）を管理する必要がある。
• システム要件： 解決策は、分散型（中央制御なし）であり、スケーラブルで、エージェントの故障に対して堅牢であり、動的な変化に適応でき、かつ限定的な通信帯域幅および通信範囲（断続的な接続性）で動作可能でなければならない。
• 目的： 最大の「アイドルタイム（空き時間）」（$i_v$）を最小化すること。これは、建物の表面上の特定のビューポイントへの連続した訪問間の時間間隔と定義される。

手法
著者らは、問題を「ビューポイント生成」、「タスク生成」、「タスク割り当て」、「パトロール戦略」の4つの異なるステージに分解する、モジュール化された分散型フレームワークを提案している。

1. ビューポイント生成：
   建物の3D表面（ファサードおよび屋根）を、ビューポイント（$V$）の集合へと離散化する。各ビューポイントは、特定の3D位置と方位を表し、物体検出のための最適な解像度を確保するための特定の距離（$c_d$）において、カメラの視野（FOV）に一致する矩形領域をキャプチャできる場所である。

2. タスク生成：
   単一の建物に関連付けられたビューポイントを接続し、閉じた経路（$H_j$）を形成する。この経路生成は、3D巡回セールスマン問題（TSP）としてモデル化されている。最適解を見つけるためのNP困難な複雑さを避けるため、著者らは、最適解の1.5倍以内の経路長を保証するヒューリスティックであるクリストフィード法を採用している。経路は、3D可視グラフを用いた障害物回避（例：建物の中を飛行しないこと）を考慮している。各建物は、定義された容量（$c_j$：サポート可能なエージェント数）を持つ「タスク」を構成する。

3. タスク割り当て：
   エージェントは、コンセンサスに基づくバンドル・アプローチ（CBBA）とその拡張であるコンセンサスに基づくグルーピング・アルゴリズム（CBGA）を用いて、タスク（建物）に割り当てられる。このオークションベースの分散型手法では、エージェントはスコア関数に基づいてタスクに入札する。スコアは、建物までの距離の二乗と優先度因子（$p_j$）を考慮しており、ヘテロジニアスなタスク処理（例：高重要度の建物の優先、または動的な追跡タスクのためのエージェントの再割り当て）を可能にする。これにより、完全な接続グラフを必要とせずに、スケーラビリティとフォールトトレランスを確保する。

4. パトロール戦略：
   閉じた経路に割り当てられた後、エージェントは最小限の分散型パトロール戦略を実行する。

• 移動： エージェントは最も近いビューポイントから経路に入り、ランダムな方向（時計回りまたは反時計回り）に移動する。
• 相互作用： エージェントは、通信範囲内にいる場合にのみ、ローカルな状態情報（位置、現在のビューポイント指数、最後にサービスを受けたビューポイント、および方向）を交換する。
• 「バウンシング（跳ね返り）」メカニズム： エージェントが出会ったとき（同じビューポイントにいるか、互いにすれ違うとき）、特定のルールを適用して方向を反転させる（「バウンス」する）。
  • 2つのエージェントが同じビューポイントに向かって逆方向に移動している場合、より近い方のエージェントがそのビューポイントをサービスして反転し、遠い方のエージェントは直ちに反転する。
  • 同じ方向に移動している場合、追い越しを防ぐために、遠い方のエージェントが反転する。
  • エージェントが互いの最後にサービスを受けたビューポイントを通過した場合、両者が反転する。
• 創発的行動： この局所的な相互作用は、エージェントが経路を動的に分割するという創発的な振動をもたらす。システムは経路の等分を目指すのではなく、すべてのビューポイントが定期的に訪問されることを保証する。

主な貢献

• モジュール化されたフレームワーク： 本論文は、カバレッジ経路計画とパトロール戦略を分離する構造化されたアプローチを導入しており、個々のコンポーネントを独立して最適化または修正することを可能にしている。
• 最小限のパトロール戦略： 連続的な外周を分割するためにグローバルなコンセンサスや複雑な調整に依存する従来の作品とは異なり、本手法は単純な局所ルール（「バウンシング」）を使用して、離散的な3D閉経路上の周期的カバレッジを実現する。
• 3D離散化： 本手法は、カメラのチルトと障害物回避を考慮した、ファサードと屋根の両方のためのビューポイント生成を通じて、都市環境の3D特性を明示的に扱う。
• リソース効率： この戦略は、計算および通信のオーバーヘッドを最小限に抑えており、断続的な接続性を持つ環境で動作するリソース制約のあるプラットフォームに適している。

シミュレーション結果
著者らは、7つの建物と401個のビューポイントを含むシナリオを用いたスウォーム研究シミュレータを使用して、フレームワークを検証した。

• セットアップ： 100台のUAVを7つの建物に割り当てた。エージェントは2 m/sで移動し、各ビューポイントで3秒間停止した。
• パフォーマンス： システムはリアルタイムで動作した（割り当て/パトロールのロジックは1 Hz、UAVのダイナミクスは10 Hz）。クリストフィード法は建物あたり平均3 msを要し、パトロールアルゴリズムはエージェントあたり2 ms未満であった。
• カバレッジ： 10回の実験実行（各1800秒）にわたり、スウォームはすべてのビューポイントの完全なカバレッジを正常に達成した。
• アイドルタイム： ビューポイントの最大アイドルタイムは制限されており、時間の経過とともに収束した。結果は、最小限の戦略が効果的にアイドルタイムの上限を制約し、グローバルな調整なしに周期的カバレッジを確保することを示した。

意義と主張
本論文は、単純な局所ルールから導かれる創発的行動を活用することで、マルチエージェント3D都市部カバレッジ問題を成功裏に解決したと主張している。その意義はトレードオフにある。すなわち、システムは、高いスケーラビリティ、堅牢性、および動的で通信制約のある環境における適応性を達成するために、経路の等分（グローバルなコンセンサスを必要とするもの）の最適性を犠牲にしている。著者らは、この最小限の戦略が、通信信号が限定的または散発的である可能性があり、個々のエージェントが故障したり失われたりしても機能し続けなければならない災害対応シナリオに特に適していると断言している。今後の課題として、ヘテロジニアスなカメラや複雑な遮蔽物を扱うためのビューポイント生成の改善が挙げられているが、現在の貢献は、構造化された3D都市環境における分散型パトロールメカニズムの実現可能性に焦点を当てている。