Polar Coordinate-based Differential Evolution for Moving Target Search Using Vision Sensor on Unmanned Aerial Vehicles

あなたは、かくれんぼのハイステークスなゲームをしているところを想像してみてください。しかし、探している相手は逃げ回っており、マップは巨大で、あなたには太陽が眩しすぎるとぼやけてしまう双眼鏡が一対あるだけです。これは、行方不明のハイカーや被災地の生存者を探している捜索救助チームの日常の現実です。科学の世界では、これは「最適探索（optimal search）」として知られています。コンピューターが、貴重な時間を無駄にしないための最善の経路を見つけ出そうとするパズルです。ここでの鍵となる考え方は、「時間は敵である」ということです。長く探し続けるほど、相手の場所は「事実」ではなく「推測」になってしまい、発見は難しくなります。これを解決するために、科学者たちはカメラを備えた「ドローン（飛行ロボット）」を使用しますが、これらのドローンに完璧なルートを飛ばせるようプログラミングすることは非常に困難です。なぜなら、ドローンには物理的な限界があるからです。ドローンは瞬時に旋回することはできず、最大速度が決まっており、永遠に飛び続けることもできません。

この論文は、動くターゲット（迷った人や浮いている生存者など）を狩る方法をドローンに教えるための、巧妙な新しい手法を紹介しています。著者であるベトナムと韓国の研究チームは、「極座標ベースの差分進化法（Polar coordinate-based Differential Evolution、略してPDE）」と呼ばれる新しいアルゴリズムを作成しました。これは、単にドローンにどこへ行くべきかを伝えるだけでなく、目的地に到達するためにどのように体を動かすべきかを教える「超スマートなコーチ」のようなものです。標準的なマップ座標（「右に10メートル、上に5メートル進め」など）を使う代わりに、PDEアルゴリズムはドローンの母国語である「この角度に回転し、この距離を飛べ」という言葉を使います。こうすることで、ドローンは行き止まりに陥ったり、不可能な旋回を試みたりすることを回避できます。研究者たちは、この手法をコンピュータ・シミュレーションと実際のフィールドでの実機ドローンを用いてテストし、特にターゲットが移動しており、探索エリアが広い場合に、PDEが他の人気のある手法よりも速くターゲットを発見できることを明らかにしました。

問題点： 「ゴールデンタイム」との競争

捜索救助においては、「ゴールデンタイム」という概念があります。これは、誰かが行方不明になった直後の短い時間枠であり、生存している状態で発見できる確率が最も高い時間です。時間が経過するにつれて、確率は低下します。なぜでしょうか？ 被災者が移動したり、風に流されたり、地形によって隠れたりする可能性があるからです。伝統的な捜索方法は、地上チームや操縦された航空機に頼ることが多いですが、これらは遅かったり危険を伴ったりすることがあります。ここでドローン（UAV）の登場です。ドローンは危険な地形を素早く飛び越え、人間には見えないものを見ることができます。しかし、ここに落とし穴があります。もしドローンにランダムに飛ぶよう指示すれば、ターゲットを見逃すかもしれません。もし完璧な格子状に飛ぶよう指示すれば、何もない場所を飛ぶことに時間を浪費してしまうかもしれません。目標は、できるだけ早くターゲットを発見できる確率を最大化する「完璧な飛行経路」を見つけることです。

頭脳： ドローンはどう「考える」のか

最適な経路を見つけるために、ドローンはターゲットがどこにいるかを予測できる頭脳を必要とします。著者らは、ターゲットの動きを「マルコフ過程（Markov process）」のようにモデル化しました。簡単に言えば、これはターゲットの次の動きが、1時間前にどこにいたかではなく、今どこにいてどのように動いているかに主に依存するという意味です。これは、川に浮かぶ葉の動きを予測するようなものです。流れの方向を知っていれば、数秒後にどこにいるかを推測できます。

また、ドローンは自分の「目」がどれほど優れているかを知る必要があります。論文では、ターゲットを発見できる確率を計算するために「NVESD」と呼ばれるモデルを使用しています。これは単にターゲットがどれくらい遠くにいるかという問題ではなく、画像の質に関する問題です。太陽が眩しかったり、ターゲットが小さくてぼやけていたりすると、見える確率は低下します。アルゴリズムはこの2つの要素、つまりターゲットが「どこにいる可能性があるか」と、カメラがそれを「見る可能性がどの程度か」を組み合わせ、「信念マップ（belief map）」を作成します。このマップはヒートマップのようなもので、最も明るい場所はターゲットが存在する確率が最も高いことを示しています。

解決策： 極座標のトリック

この論文の核心となる革新は、ドローンの飛行経路をどのように計画するかという点にあります。ほとんどのコンピュータ・アルゴリズムは、グラフ用紙の格子のような「デカルト座標（直交座標）」を使用します（xとyの値）。これは数学的には機能しますが、ドローンにとっては最悪です。もしドローンが飛行中に旋回する必要がある場合、デカルト座標のアルゴリズムは、ドローンが瞬時に円を描いて回転したり、エンジンの許容範囲を超える速度で飛行したりすることを要求する経路を計算してしまうかもしれません。それは、車に最小旋回半径を考慮せずに「北に5メートル、東に5メートル進め」と命じるようなものです。

著者らは代わりに「極座標（Polar coordinates）」を使用することを提案しました。座標（x, y）へ行けと言う代わりに、アルゴリズムはドローンに「この距離（$\rho$）を、この角度（$\psi$）で飛べ」と指示します。これはドローンの実際の動きに一致しています。この方法を使用することで、アルゴリズムは自然にドローンの物理的限界を尊重します。最初からそれらの制限に基づいた数学的構造になっているため、鋭すぎる旋回や速すぎる速度を提案することはありません。

彼らはこのアイデアを「差分進化法（Differential Evolution, DE）」アルゴリズムの中に組み込みました。DEは、探検家チームのように機能する「群知能（swarm intelligence）」の一種です。霧がかった山脈で最も高い峰を探しているハイカーのグループを想像してみてください。彼らは地図の全容を知りませんが、情報を共有しています。もし一人のハイカーが高い地点を見つけた場合、他のハイカーはそのエリアに向かって移動しますが、同時に、さらに高いものを見つけられるかどうかを確認するために、少し異なる方向も試します。「差分（Differential）」の部分は、二人のハイカーがどこにいるかの違いを見て、次にどちらの方向にジャンプすべきかを決定することを意味します。

著者らは、この群知能を極座標システムと組み合わせました。彼らはこれをPDEと呼んでいます。シミュレーションにおいて、この仮想ドローンのチームは、標準的な手法を使用するチームよりもはるかに効率的に探索エリアを探索しました。

結果： シミュレーションと実機飛行

研究者らは、600m x 600mの小規模なエリアから2000m x 2000mの広大なゾーンまで、6つの異なるシナリオでPDEアルゴリズムをテストしました。PDEを、粒子群最適化（PSO）、遺伝的アルゴリズム（GA）、および標準的な差分進化法（DE）などの他の有名なアルゴリズムと比較しました。

コンピュータ・シミュレーションにおいて、PDEは一貫して高い確率で、かつより速くターゲットを発見しました。例えば、あるシナリオでは、PDEは約0.529の検出確率を達成しましたが、標準的なDEアルゴリズムは0.410しか達成できませんでした。論文では、標準的なDEはしばしば「局所最適解（local optima）」に「トラップ（捕獲）」される、つまり良い場所は見つけたものの、ループに陥ってしまい、最高の場所を見つけることができないと指摘されています。PDEは、その極座標のおかげで、これらのループから脱出し、グローバルな最適経路を見つけることに長けていました。

彼らはコンピュータ上のゲームだけで終わらせませんでした。理論をテストするために、実際のフィールドに実機の3DR Soloドローンを持ち込みました。ドローンにはPDE経路がプログラムされ、80m x 80mのエリアの上空を飛行しました。ターゲットとなる人物は、秒速1.5mの速度で歩きました。ドローンはアルゴリズムによって生成された経路に従い、実際に飛行した経路は計画と非常によく一致していました。ドローンはターゲットが予想されるエリアの上空を正常に飛行し、カメラは人物を捉えました。著者らは、実世界のテストは成功したものの、ターゲットが予測通りに正確に動くことに依存していたと述べています。実際の災害現場ではもっと混沌としていますが、このテストは、アルゴリズムが実際にドローンが飛行可能な経路を生成することを証明しました。

なぜ重要なのか

この論文は、ドローンの言語（極座標）を話し、スマートなチームベースの探索戦略を用いることで、捜索救助活動をより効果的にできることを示唆しています。PDEアルゴリズムは単に経路を見つけるだけでなく、ドローンの限界を尊重しながら、救助のチャンスを最大化する「実行可能な」経路を見つけ出します。著者らは、単独のドローンはバッテリー寿命によりカバーできる範囲が限られていることを認めていますが、この手法が将来、協力して働くドローンの艦隊（フリート）の基礎となり得ることを示唆しています。現時点では、これは、一分一秒を争う場面において、私たちの空飛ぶロボットをより賢く、より速く、より役に立つものにするための重要な一歩です。