Using Local Experiences for Global Motion Planning
サンプリング手法の一つ。
Abstract
サンプリングベースのプランナーは、ロボット操作、ナビゲーション、さらにはタンパク質モデリングなど、実世界の多くのアプリケーションで効果的です。ただし、重要な領域をサンプリングするのが難しい環境では、衝突のないパスを生成するのは困難です。事前の情報がない場合、サンプリングベースのプランナーは一様にまたは発見的に探索することを余儀なくされ、これはパフォーマンスの低下につながる可能性があります。パフォーマンスを向上させる1つの方法は、環境に関する事前知識を使用して、サンプリング戦略を当面の問題に適応させることです。この作品では、ワークスペースをローカルプリミティブに分解し、これらのプリミティブによるローカルエクスペリエンスをローカルサンプラーの形で記憶し、それらをデータベースに格納します。私たちは与えられた状況に関連した地元の経験を検索することによって効率的なグローバルサンプラーを総合します。私たちの方法は、ローカルプリミティブを共有する多様な環境間で効果的に知識を伝達し、パフォーマンスを劇的にスピードアップします。私たちの結果は、解法時間に関して、最先端のアプローチと比較して2つの伝統的に挑戦的な高次元問題における数桁の改善を示しています。
1. Introduction
動作計画は、ロボット工学の多くの分野で欠くことのできない部分です。自律的に動作するロボットは、複雑な環境でさまざまな運動計画を作成する必要があります。これは、特に作業および運動計画の文脈において当てはまります[1]。積み重ねブロックのような単一のタスクでさえ、何千回もモーションプランナに問い合わせる必要があるかもしれません。人間はロボットが現在苦労している動きを即座に実行することができます。人間レベルの行動を達成するためには、高速オンラインモーションプランニングが不可欠です。サンプリングベースのプランナーが広く成功しているのは、少数のサンプルで高次元空間の接続性を近似できることにあります[2]。 ただし、多くの場合、接続に必要な領域は、情報のないサンプラーによってサンプリングされることはほとんどありません。これは、狭い通過問題[3]、[4]、[5]として知られており、多くのシナリオでサンプリングベースのプランナのパフォーマンスを大きく制限します。狭い箇所を含む問題を解決するための可能なアプローチの中には、経験に基づく計画の新しい分野があります[6]、[7]、[8]。ロボットが動作中に同じような作業空間に出くわすのはよくあることですが、結果的に同じような動作計画が作成されます。そのようなケースは、ロボットが赤缶をつかみ、それを一番上の棚に置く必要がある図1で見ることができます。この場合、同様のシナリオに関する事前知識がモーションプランニングプロセスを促進する可能性があります。サンプリングを興味深い領域に偏らせることによって[7]、あるいは古い解を検索して再利用することによって[6]、経験ベースの方法は、同様の問題から得られた知識を他のものに移そうとします。残念なことに、ワークスペースの小さな変更は可能な解決策に劇的な影響を及ぼし、場合によっては一般化を難しくします[9]、[10]。
このホワイトペーパーでは、病理学的なケースであっても構成空間の接続性を発見するのに役立つ、サンプリングベースのプランナーのためのサンプリング戦略を提示します。このサンプリング戦略では、ワークスペースをローカルプリミティブに分解します。私たちの方法の主な洞察は、ロボットとプリミティブによって定義された構成空間で重要なサンプルを生成することを学ぶことがグローバルワークスペースの構成空間を近似するのを助けるということです。このアプローチは、以前に使用されたワークスペースプリミティブまたはそれらに非常に類似したプリミティブを含む新しい環境に一般化できます。この作品では、単純な幾何学的特徴を持つ問題に焦点を当てながら、現代のサンプリングベースのモーションプランナーでは実際には解決できなかった問題のクラスを解決します。また、分解の概念が複雑な形状を持つ非構造化環境に適用されるかどうかという問題を提起し、以前はサンプリングベースのモーションプランナーの手が届かなかった問題に取り組んでいます。この論文の貢献は3つあります。まず、ワークスペースをローカルプリミティブに分解することを提案し、ローカルプリミティブのみを含むワークスペースにおける運動計画問題を解決します。このステップの結果は、ローカルプリミティブの構成空間の困難な領域にサンプルを生成するローカルサンプラーの推定です。これらのローカルサンプラーのパラメータはデータベースに保存されています。次に、これらのローカルサンプラーに基づいてグローバルサンプリング戦略を合成する方法を示します。第三に、我々はそれが既存の方法を大幅に改善する2つの挑戦的な環境における我々のアプローチの有効性を示す。
2. Background
サンプリングベースのプランナは、高次元の問題に対応できることから、ロボット工学で広く採用されています。 ２つの主なカテゴリは、マルチクエリ問題に対するグラフベースのアプローチ（例えばＰＲＭ ［１１］）とシングルクエリ問題に対するツリーベースの（例えばＲＲＴ ［１２］、ＥＳＴ ［１３］）である。一般に運動計画はPSPACE完全である[14]、[15]が、サンプリングアルゴリズムは非常によく機能する。しかしながら、困難な環境（例えば、狭い通路を有する事例）では、サンプリングは計画の遂行においてますます重要な役割を果たす。しかしながら、低膨張領域でより多くのサンプルを生成するために非一様サンプラーを使用すること[13]がこの問題を軽減できることは理論的に理解されています。多くのアプローチはリジェクションサンプリングを使用します。この場合、サンプルはBridge-Sampling [3]やGaussian-Sampling [16]などの特定の幾何学的テストに合格した場合にのみ受け入れられます。他のアプローチは、内側軸サンプリング[17]や障害物ベースサンプリング[5]のような難しい領域を推測しようとします。これらの手法は最終的に狭い通路の近くまたは内部でサンプルを生成するが、それらは依然として計算上高価な全体の構成空間を考慮する。それにもかかわらず、結果として得られるグラフは通常、均一サンプリングによって生成されたものよりはるかに小さいです。
我々の方法と同様の最近のアプローチは、サンプリングを偏らせるために、問題に関して取得した情報を利用することを試みる。強化学習は、構成サンプルに変換されたワークスペースの重要な領域を推論するために[18]によって使用されました。 [7]の作者は、条件付き変分自動エンコーダ（CVAE）と呼ばれる生成モデルを利用しています。これは、ワークスペースの記述を前提として、「興味深い」領域にあるサンプルの作成を学習します。サンプリングバイアス方式には、変更を加えずに多くのサンプリングベースのプランナで使用できるという利点があります。ただし、どちらの方法も、ワークスペース機能を使用して構成スペース内の重要なサンプルを推論するモデルに依存しています。 [18]では、個別のワークスペースセルがエンドエフェクタのインバースキネマティクスを介してコンフィギュレーションにマッピングされました。 [7]では、ニューラルネットワークを使用してこれらのサンプルを推論しました。我々の実験は、複雑な配置空間では、これらのモデルが配置空間の重要な領域で一貫してサンプルを生成しないことを示した。オンライン適応サンプリング方法では、衝突チェック情報を使用して、実行時に構成スペースのどの領域が重要かを推測します。ユーティリティガイドによるサンプリング[19]は、ロードマップのエントロピーに基づいて最大の情報利得を持つサンプルを選択します。 [20]の作者は、サンプリング問題を自由サンプルと衝突サンプルの間の分類として定式化しています。 Toggle-PRM [21]は、構成空間と障害物空間の2つのロードマップを作成し、狭い通路でサンプルを推論しようとします。これらの方法は、運動計画アルゴリズムの状態に基づいてサンプリングをオンラインで適応させるが、この知識を異なる計画クエリ間で転送することはしない。それどころか、提案された方法は、以前の計画クエリに基づいてサンプラにバイアスをかける。したがって、オンライン適応サンプリングは、提案されたサンプリングバイアスと並行して使用することができる。これらの方法に直交するのはデータベースアプローチです。サンプリングを修正する代わりに、これらの方法は離散的な経路またはグラフをデータベースに格納することによって以前の経験を活用する。この情報は後で検索され、新しい運動学的制約を満たすために修復／変換される。これらの方法は、サンプリングにバイアスをかけることと比較してハードコーディングされた経験として考えることができます。
[22]の作者は、エントリとクエリの開始目標設定の近さに基づいてクエリされたパスのライブラリを使用しました。これらの発見的方法に基づいて有効なパスが検索できなかった場合、無効な部分を修復するためにBIRRT [12]が使用されました。このアイデアは[6]で拡張され、冗長性を排除してパスを格納するためにグラフが使用されました。実行時間を大幅に改善することはできますが、前述の方法では変更にうまく対応できず、主に不変の環境では結果が改善されます。これは、エクスペリエンス表現にワークスペースを明示的に含めないために起こります。ワークスペース情報を明示的に使用するデータベースアプローチには、[23]障害物ロードマップの小さなデータベースを作成することが含まれます。 [24]によって提案された軌道予測はタスク空間に生成されたパスを保存し、実行中にIKを使用しながら軌道のコストを最適化することによってそれらを構成空間に変換します。これらの方法は異なる環境に対処することができるが[23]は自由飛行ロボットに対してのみ作用し、[24]はサンプリングベースの計画者の確率的保証を欠く軌道最適化計画者と共に作用する。この作品では、バイアスサンプラーをデータベースと統合することによって、両方の長所を組み合わせています。これは、ワークスペースをローカルプリミティブに分解し、各ローカルプリミティブについて効率的なローカルサンプラのパラメータをデータベースに格納することによって達成される。バイアスサンプラーは、ワークスペースに大きな変更があった場合にコストのかかる修復を必要とする可能性があるデータベース方法によって引き起こされる、完全なパスへのハードコミットメントを回避する「ソフトな方法」で事前知識を使用します。他方、データベース方式は、複雑なパラメトリックモデルの必要性を回避して、ローカルサンプラのローカルプリミティブへの即時マッピングを可能にする。さらに、データベースには、単純に新しいエントリを追加することによってその経験を段階的に改善するという固有の機能があります。前述のサンプリングバイアス手法は再訓練される必要があるだろう。
メモ マルチクエリ、シングルクエリとは
3. Method overview
4. Reducing the database
5. Experiments
6. Conclusion
この研究では、ワークスペースの分解に基づく新しいサンプリングバイアスフレームワークを提案しました。 単純な幾何学的プリミティブのみを検討しましたが、検討した方法では解決できなかった、または効率的に解決できなかった問題を解決しました。 我々は我々の結果を予備的なものと考えているが、我々はこの作業が運動計画問題に経験を適用するための新しい方法を開くと信じている。 今後の作業には、一般的でより効果的に任意のワークスペースを分解できる、より複雑なプリミティブの使用が含まれる可能性があります。 最後に、データベースのサイズが大きくなるにつれて、効率的なリアルタイム検索アルゴリズムを使用する必要があります。
