Learning When to Quit: Meta-Reasoning for Motion Planning

著者: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

ライセンス

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

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

要約

過去のプランナー実行から、エニータイム型モーションプランナー（RRT、PRM、Lazy PRM*）をいつ停止すべきかを学習し、経路の質と計画時間のトレードオフを最大化する。

重要な理由

RRT や PRM で計画するロボットはどれも計画時間の予算を決めなければならず、固定時間や固定の質のしきい値では、時間か経路の質のどちらかが無駄になる。この手法は変更を加えないエニータイムプランナーを包む形をとるため、対象とする環境分布から訓練用の問題が得られる限り、既存の OMPL 型プランナーの上に追加できる。

課題

エニータイム型モーションプランナーは長く動かすほど経路を短くしていくが、解の質と計算時間の関係は十分に特徴付けられておらず、いつ計画をやめて動き始めるべきかが不明確である。プランナーが新たなホモトピー類を見つけたときに短い経路が突然飛躍的に現れるため、その性能プロファイルは非常に滑らかでなく、将来の質を単純にオンラインで外挿することはできない。

提案手法

著者らは、同じ分布から得た過去の計画問題の性能プロファイルから停止方策を学習し、ユーザーが重みを与える効用 U(q, t) = wq − (1 − w)t を最大化する。モデルベースの変種は、離散化した質と時間の上でマルコフ決定過程を学習し、価値反復で解く。2 つのモデルフリーの変種（手作業で設計した特徴に基づくフィードフォワード分類器と、RNN の系列変換モデル）は、事後的に計算したオラクルの停止判断を模倣する。CNN が 2D 作業空間の画像から最適経路長を予測することで、難易度の異なる問題の性能プロファイルを正規化して比較できるようにする。

主な知見

最適な停止時刻は各訓練実行について事後的に計算できるため、方策学習の問題は強化学習ではなく教師あり模倣学習に変わる。
経路の質の正規化には未知の最適経路長が必要であり、2D 作業空間の画像からそれを予測する CNN によって問題間で性能プロファイルを比較できるようになる。一方、質の悪い正規化基準（スタートからゴールへの直線）では効用が大きく下がる。
より豊富な履歴特徴（傾き、平坦さ）を使うとモデルベースの遷移モデルははるかに正確になるが、その推定コストは数秒から 1 日以上に増える。次元の呪いの直接的な例である。
RNN は生の効用系列から時間的特徴を自ら学習し、プランナーと効用の重みの違いを通じて最も安定して良好な結果を出した。

主な結果

CNN による最適経路長予測器の、200 個のホールドアウト作業空間での精度：3 種類の環境分布でそれぞれ 88.21%、96.23%、94.25%。
CNN による正規化を用いた効用は 3 つの環境で 0.58、0.65、0.66 であり、真の最適長を用いた場合の 0.63、0.70、0.67、直線による正規化の 0.39、0.40、0.60 と比較される。
遷移モデルのホールドアウト損失は 1.84（特徴なし）から、(t, q) で 0.22、(t, q, slope) で 0.10 に下がった。一方、推定時間は 0.41 s から 10.64 s、11,933.72 s に増えた。
w = 0.8 の RRT*：オラクルの効用 0.677、RNN 0.670、モデルベース 0.663、分類器 0.658。これに対し固定品質ベースラインは 0.634、固定時間ベースラインは 0.575。
w = 0.8 の PRM*：オラクル 0.718、モデルベース 0.702、RNN 0.698、分類器 0.697、固定品質 0.674、固定時間 0.662。
w = 0.2 では固定品質ベースラインが負になった（RRT で −0.283、PRM で −0.344、Lazy PRM* で −0.367）が、学習手法は正のままだった。

制限事項

CNN による最適解予測器は 2D 作業空間の画像を入力とするため、手法は平面的な作業空間をもつ問題に限られる。ボクセルグリッドや点群による 3D への拡張は提案されているが、実施されていない。
新しい問題は訓練問題と同じ分布から来ると仮定しており、訓練には代表的な問題でのプランナーの長時間の実行が多数必要である。
モデルベース手法への履歴特徴の追加は、大規模な実験では計算上不可能だったため、(q, q_prev, t) のみを用いた。
評価はすべてシミュレーション上で、2D 作業空間内の 3 自由度の剛体ロボットを用いて行われており、実機ロボットでの試験はない。
線形の効用 U(q, t) = wq − (1 − w)t のみが検討されている。

分野への影響

本論文は IROS 2021 認知ロボティクス最優秀論文賞のファイナリストに選ばれ、被引用数は 14 である。コードやデータの公開については記載がない。

概要

エニータイム型のモーションプランナーはロボティクスで広く用いられている。しかし、その解の質と計算時間の関係は十分に理解されておらず、そのため、いつ計画を打ち切って実行を始めるべきかは明確でない。本論文では、エニータイム型のモーションプランニングについて、限られた計算能力のもとで熟考をいつやめるかを決定する問題、いわゆるメタ推論に取り組む。我々は、データ駆動の学習手法として、モデルベースおよびモデルフリーのメタ推論を提案する。これらは異なる環境分布に適用でき、エニータイム型モーションプランナーの選択に依存しない。このフレームワークの一部として、与えられた 2D 作業空間の画像から最適な経路長を予測する、畳み込みニューラルネットワークに基づく最適解予測器を設計する。提案手法の性能を、シミュレーションにおいてベースラインと比較して実験的に評価する。

リンク

arXiv 2103.04374: https://arxiv.org/abs/2103.04374
DOI 10.1109/IROS51168.2021.9636864: https://doi.org/10.1109/IROS51168.2021.9636864
PDF: https://arxiv.org/pdf/2103.04374v1