Time Optimal Ergodic Search

著者: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023

ライセンス

オープンアクセス
論文: CC BY 4.0

以下の内容はすべて、論文のライセンス（CC BY 4.0）に従い論文全文に基づいています。図は著者のクレジットを付けて掲載しています。

要約

エルゴード指標に対する上限 γ のもとで探索時間を最小化する。1 つのパラメータでカバレッジの徹底さを決め、最適化器が軌道の所要時間を選ぶ。

重要な理由

捜索救助や調査飛行において、オペレータは所要時間を推測する代わりに、掃引がどれだけ徹底的であるべきかを指定し、それを満たす最速の軌道を得られる。速度制限や障害物バリアなどの制約も同じ最適化に含まれ、計画された時間は実際のクアッドロータでも 1.5 s 以内で再現された。

課題

エルゴード探索は、各領域に滞在する時間がその領域の情報量に比例するような連続軌道を計画するが、既存手法では計画ホライズンを事前に固定するため、ユーザは探索の徹底さと時間とをトレードオフできない。エルゴード指標を最小化しつつ時間を最小化するのは不良設定問題である。軌道が完全にエルゴード的になるのは時間が無限大に近づくときだけだからである。

提案手法

エルゴード指標を最短時間問題の中の不等式制約 E ≤ γ とすることで、γ がカバレッジの粗さ・細かさを決め、終端時刻 tf は決定変数となる。著者らは「拡張エルゴード状態」を用いて Pontryagin の最大原理により局所最適性条件を証明し、実際には N 個のノット点（Δt = tf/N）上での直接転写と独自の拡張ラグランジュ法ソルバによって問題を解く。障害物は離散的な制御バリア関数の制約で扱う。

主な知見

エルゴード性を目的関数ではなく上限として扱うことで、最短時間探索が良設定問題になる。γ → 0 とすると最適時間は際限なく増大し、エルゴード理論と一致する
4 つのピークをもつ情報マップ上で γ を 2 桁下げる（0.1 から 0.001）と、最適時間はおよそ倍になった（9.86 s から 19.59 s）が、粗い計画でもすべてのピークを訪れていた
時間で正規化した制御入力の大きさは、軌道がカバレッジと時間とをトレードオフしなければならない γ の範囲の中ほどで、両端よりも大きくなる
滑らかな初期推定（線形補間）では一貫した解が得られる。ノイズを含む、あるいはランダムな初期軌道では、エルゴード性は同等だが時間の長い局所最小に陥る

主な結果

2 次元の質点による一様カバレッジ：γ を変えると 5–10 s の軌道が得られ、そのカバレッジはホライズン固定の 10 s のエルゴード軌道（E = 0.007）に相当する
非一様な情報マップ：最適時間は γ = 0.1 で 9.86 s、γ = 0.001 で 19.59 s
γ = 0.05 での感度：初期 tf を 4 から 8 s まで変えると最適時間は 4.97 ± 0.23 s、ノット点数 N を 50 から 600 まで変えると 5.45 ± 0.39 s
制御バリア関数を用いた障害物の多い 2 次元環境：最適時間は γ = 0.2 での 7.79 s から γ = 0.002 での 11.85 s までで、バリア制約によって軌道はすべての障害物から離れて保たれた
γ = 0.1、0.05、0.01 でのドローン実験：実際の飛行時間は最適化された時間と 1.5 s 以内の差だった。図 1 の軌道は障害物の多い領域を 13.5 s でカバーする
ソルバは、ランダムな楕円体障害物の間を飛ぶ非線形の 3 次元航空機モデルについても一様カバレッジ軌道を生成した

制限事項

著者らは、エルゴード指標が強い非線形性と非凸性をもつため、解は局所最適にすぎないと述べている
著者らは Pontryagin の最適性条件が長いホライズンでは数値的に不安定であることを見出しており、そのため実用上のソルバは直接転写法である
計画はオフラインで、障害物は既知である。著者らは、未知の障害物や環境の不確かさを伴うリアルタイム計画を今後の課題として挙げている
結果は初期軌道と N に依存する。γ が非常に小さく、必要な時間が非常に大きくなる場合、ソルバは解を返さなくなる
著者らは、計算コストが探査空間の次元とともに増大することを指摘している

分野への影響

RSS 2023 Best Paper Award を受賞。著者らは github.com/ialab-yale/time_optimal_ergodic_search でコードを公開し、マルチメディアのデモページも用意している。

概要

時間と探索の徹底さとのバランスを取れるロボットは、捜索救助などの用途において一刻を争う支援を提供できる可能性がある。エルゴード的カバレッジに基づく探索手法の近年の進展により、ロボットは決められた時間内にある領域を完全に探査・探索できるようになった。しかし、自律的なエルゴード探索の質に対して時間を最適化することは、まだ示されていない。本論文では、高速かつ適応的なロボットの探索・探査のために、時間最適エルゴード探索問題の解を検討する。この問題を、エルゴード不等式制約付きの最短時間問題として定式化する。その上限が探索の粒度と時間とを調整し、バランスを取る。問題の解は Pontryagin の最適性条件を用いて解析的に示し、直接転写による最適化手法で数値的に実証する。シミュレーションと、障害物の多い環境でのドローン実験において、時間最適なエルゴード探索軌道を生成する本手法の有効性を示す。障害物回避が本定式化に容易に組み込めることを示し、最適化された時間に対するパラメータ依存性と、探索における軌道の感度を調べるアブレーション研究を行う。

リンク

arXiv 2305.11643: https://arxiv.org/abs/2305.11643
PDF: https://arxiv.org/pdf/2305.11643v1
コード: https://github.com/ialab-yale/time_optimal_ergodic_search
プロジェクトページ: https://sites.google.com/view/time-optimal-ergodic-search