Extending Obstacle Avoidance Methods through Multiple Parameter-Space Transformations

論文 Robotics

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.4672&rep=rep1&type=pdf

Jose-Luis Blanco, Javier González, Juan-Antonio Fernández-Madrigal University of Malaga, Spain Autonomous Robots(Springer) 2008, IROS2006

Abstract

障害物回避方法は、動的または未知の環境に適している、最新のセンサ読み取り値に従ってリアルタイムでロボットを操縦することによって移動ロボット自律ナビゲーションの問題に取り組む。しかしながら、実時間性能は、ロボットの形状およびその運動学的な制限のいくつかまたはすべてを無視することによって一般的に得られ、それは多くの実用的な状況において劣悪なナビゲーション性能をもたらし得る。本論文では、運動学的に拘束された任意の形状のロボットを、既知の障害物回避方法が適用可能な新しい空間内の自由飛行点にリアルタイムで変換する枠組みを提案する。このフレームワークによる私たちの貢献は2つあります。既存の変換アプローチのほとんどをカバーする一般化された空間変換の定義と、ロボットの動きの決定を最適化するために複数の変換を同時に適用できるリアクティブナビゲーションシステムです。結果として、これらの変換は、ロボットの運動学と互換性のある経路で空間を「サンプリング」することによって、既存の障害物回避方法が周囲の自由空間のより良い検出を実行することを可能にする。実際のロボットを屋内、雑然とした、動的なシナリオでナビゲートした経験から、いくつかの例を用いてこれらの空間変換を設計する方法を説明します。また、我々は同様の状況に直面したときに以前の方法に対する我々のアプローチの利点を実証する実験結果を提供する。

1. Introduction

自律的で安全なナビゲーションは、移動ロボットが研究室を離れてそれらの使用を一般化するために厳密に解決される必要がある問題の一つです。この目的のためには、衝突のない経路が効率的に見つかる可能性がある障害物の空間的表現を考慮することが不可欠です。この問題はロボット業界で広く研究され、伝統的に2つの異なる研究分野につながっています。一方では、既知のシナリオに対して開始点からターゲットまでの最適な経路が計算されるモーションプランニングアプローチがあります。構成空間（C-空間）（Lozano-Pérez1987）は、この範囲の表現としてうまく採用されています。 C-Spaceでは、ロボットは高い次元を犠牲にして単一の点として表されます（たとえば、平面移動ロボットの場合は3次元）。一方、ナビゲーションのアプローチの中には、ナビゲーション中にモーションコマンドをリアルタイムで定期的に計算しなければならない、未知または動的なシナリオを扱うものもあります（計画はありません）。

反応的または障害物回避と呼ばれるこれらのアプローチの下では、ナビゲーター手順は、センサーの読み取り値とモーターの作動との間のマッピングとして便利に見ることができます（Arkin 1998）。 リアクティブメソッドは非常に効率的で単純な実装ですが、それらの多くは、ロボットの点や円による表現、または任意の方向への移動を許可する、つまり運動学的な制限を無視するなど、制限が厳しすぎる仮定に頼るため、実際のアプリケーションでは正しく機能しません。 。 C-Spaceはその複雑さのためにリアクティブメソッドのための適切なスペース表現ではありません、そしてそれはリアルタイム実行を妨げます。それ故、ＣＳｐａｃｅの単純化は特に反応的方法のために提案されている。最後に、上記の2つのアプローチの組み合わせも提案されており（Khatib et al。1997、Lamiraux et al。2004、Quinlan and Khatib 1993）、通常は既知の静的マップに基づいて計画パスの計算を開始し、その後動的に試行します。予期しない障害物との衝突を避けるために変形してください。これらのハイブリッドアプローチは多くの状況でナビゲーション問題を首尾よく解決するが、先験的計画経路がハイブリッド方法によってうまく構築されるために過度の変形を必要とする場合がある純粋に反応的な方法が依然として部分的に既知または非常に動的なシナリオには必要である。本論文はナビゲーション問題への純粋に反応的なアプローチを提示し、したがって運動計画と経路変形に関する以前の研究は直接我々のものと関係がない。より具体的には、ここで取り上げる問題は、平面シナリオにおける運動学的に拘束された任意形状の移動ロボットのリアクティブナビゲーションです。この問題は、障害物を避けながらロボットの運動学的制限を満たしながら、目標位置に近づく動きを見つけることを必要とする。

私たちの主な貢献は、ロボットの周りの空きスペースを検出するためのプロセスにあります。これは、リアクティブナビゲーターが最高の瞬間的なモーター作動を決定するための基礎です。この課題のために、既存の方法は、障害物距離を測定するための単純な経路の特定の族を考慮する（これは自由空間をサンプリングすることと等価である）。パスモデルと呼ぶこれらのパスファミリは、計画されたパスではなく、近くの障害物を考慮に入れるためのアーティファクトと見なされる必要があります。すべての既存の反応的方法は、図１に示すように、ロボットの短期モータ作動の拡張である経路モデルを使用する。任意の方向に動くことができるホロノミックロボットに対しては、直線経路が採用され、非ホロノミックに対しては円弧が考慮される。もの以前の反応的方法で使用されていた直線および円形経路モデルとは別に、他のモデルが運動計画の分野で研究されており、最短経路に関して興味深い結果を得ている（Laumond andSouères1993、Reeds JA and Schepp RA 1990、Souèresand Laumond 1996）。 、Ｖｅｎｄｉｔｔｅｌｌｉら１９９９）。我々のアプローチは、これらの方法のいくつかを初めてリアクティブナビゲーションシステムに統合することを可能にする。

私たちは、以前の反応的方法で使用されていた直線と円形の経路は、記憶のないシステムでロボットがたどることができる無限の経路モデルから2つだけ離れていると主張しています。反応型ナビゲータで使用されるのは、運動学的制約を満たし、かつ反応型コントローラによって記述されることができなければならないため、任意のものにはなり得ない。他の経路モデルを考慮することは、古典的な直線モデルまたは円形モデルのみを使用するよりも自由空間をサンプリングすることがより適切であることは明らかです。私たちは、ロボットが（反応的に）可能な動きを探す図2の例を通してこの問題に焦点を当てました。図2（a）のように障害物をサンプリングするために単一の円形経路モデルを使用する場合、障害物回避方法は多くの良い潜在的な動きを見逃している可能性が非常に高いです。障害物について説明します。対照的に、図２（ｂ）に示されているもののように、多様な経路モデルを使用することは、ロボットに自由空間のより完全な図を提供する。これは私達のアプローチの際立った特徴の一つです：同時に様々な経路モデルを扱う能力。実際の実験で後で論じられるように、これは、より短い経路に従ってより短い時間でナビゲーションを実行するロボットに反映される。さらに、ナビゲーションは動的な障害物や雑然としたシナリオに対してより堅牢に機能します。

キネマティック制限と障害物回避の問題は、パスモデルを使用してキネマティック準拠パスと現実世界の障害物を複雑さの低い空間に変換することで切り離すことができます。これを軌道パラメータ空間（略してTP空間）*と呼びます。この変換は、ロボットの形状と運動学的な制限がすでに変換プロセスに組み込まれているため、ロボットをTPスペースの自由飛行点と見なすことができるように定義されています。私たちは自由空間での飛行ロボットの標準的な方法に変換された空間での障害物回避タスクを委託することができます。この考えは、自我運動学変換（EKT）が具体的なTPSpaceとして提示されている（Minguez and Montano 2006）で発見されました。その作業の中で、ここでの私たちの貢献は2つあります。一方で、私たちはパラメータ化軌道ジェネレータ（PTG）と呼ばれる新しいツールを通して経路モデルの一般化で彼らの仕事を拡張します。変換一方、それぞれが異なるPTGに対応する複数の経路を同時に管理するためのナビゲーションシステムを提案する。このシステムは、（例えば、経路長およびクリアランスに関して）各瞬間において最良の選択肢の動的選択に直面し、それは円形経路のみに依存する従来の方法よりも強力なアプローチをもたらす。まとめると、リアクティブナビゲーションに対する提案された解決策は以下の特徴を提示する。

  • 障害物回避と運動学的制限の問題は（Minguez and Montano 2006）のように切り離されていますが、今では一般化された方法で最適化と異なるロボットとシナリオ間の再利用を容易にします。

  • 以前はホロノミックポイント（または円形）ロボットに制限されていた、よく知られている効率的な反応的方法を、あらゆる形状の非ホロノミックロボットに適用できるようになりました。

  • 円弧以外のパスモデルを使用すると、ロボットは障害物を回避し、運動学的な制限と互換性のある、より幅広い代替動作を見つけることができます。 さらに、多数の経路モデルを同時に使用することができ、各特定の状況に最も適したものを動的に選択することができる。

図３において、我々は古典的なリアクティブナビゲーション方法と我々のアプローチの両方を概略的に表す。図3（a）に示すように、既存の手法ではロボットの運動学的制約と全体としての障害物回避を扱う。我々は、衝突回避から運動学的な制限を、いくつかの異なる変換（ＰＴＧ）を介して抽象化することを提案する。図３（ｂ）に示されるように、複数の変換の存在は、各時間ステップで最も適切な動きのためのある種の選択メカニズムに対する必要性を導入する。この記事の残りの部分は次のように構成されています。セクションＩＩでは、運動学的制限を伴うリアクティブナビゲーションの問題に対処するために、以前の手法で採用されていた異なる空間表現を検討する。セクションIIIでは、TP-Spacesとその根底にある距離 - 障害物測定問題を紹介します。次に、PTGを定義し、実際のナビゲーションシナリオとTPスペースとの間で必要な変換のためにそれらをどのように利用するかを説明します。セクションVでは、実際のロボットの経験から得られた実装の詳細を含む、完全なナビゲーションシステムを紹介します。最後に、いくつかの結果と結論を議論した。

2. Relation with previous works

3. Trajectory Parameter Spaces (TP-Spaces)

4. Parameterized Trajectory Generators (PTGs)

5. The complete reactive navigation system

6. Results and Discussion

Hilbert maps: Scalable continuous occupancy mapping with stochastic gradient descent

論文 Robotics

http://web.it.usyd.edu.au/~framos/Publications_files/HilbertMapsIJRR16Final.pdf

Abstract

今日の膨大な量のデータロボットは、ロボットが動作する空間をモデル化するための高速でスケーラブルな統計的ツールの開発を動機付けています。側面：（１）世界をグリッドセルに先験的に区別することを想定していないため、任意の解像度で地図を提供することができる。 （２）測定値間の空間的関係を自然に捉えるので、外れ値に対してよりロバストであり、より良い汎化性能を有する。ヒルベルトマップと呼ばれるこの手法は、ロジスティック回帰分類器が学習されるヒルベルト空間でデータを射影する高速カーネル近似の計算に基づいています。我々はこのアプローチが各測定がオンラインの方法で学習中に一度だけ処理される効率的な確率的勾配最適化を可能にすることを示す。 3種類の近似で結果を示します。 Nyström;そして新しいスパース射影。また、センサーや位置の誤差によるレーザースキャンの位置の不確かさなど、確率分布を入力として受け入れるようにアプローチを拡張します。この拡張バージョンでは、一般的なベンチマークデータセットを使用して、2次元と3次元で実験が行われました。さらに、同時位置確認およびマッピング中のループ閉鎖前後の軌跡更新など、データの大きな変化を処理するための技術の適応能力の分析も含まれる。

1. Introduction

3次元（3D）空間の物理的性質を表現することは、操作や握りから自律的なナビゲーションまで、ロボット工学の中心です。環境を特徴付ける多くの物理的性質の中で、ロボットが相互作用する必要がある固体物体によって特定の点が占められる可能性は確かに最も重要なものの1つです。占有率のマップを作成する従来の技術は、一定のサイズのセルへの領域の識別に依存し、センサー・モデルまたは尤度関数を適用してセンサー・データ、たとえばレーザースキャンなどの占有データを推定します。あるいはソナー（Elfes、1987、1989）。そのような技術の主な制限の１つは、グリッド内の各セルが互いに独立しており、マップ全体に対する事後計算が各セルに対して別々に実行されるという仮定である。この仮定は、セル間の重要な空間的関係を無視し、セル間に一連の「ギャップ」があるマップにつながります。たとえば、観測されていないセルは、占有される可能性が高いセルの隣にある場合でも、占有される可能性は0.5です。同じ解像度で環境を表現するのに必要なセルの数が、必要な観測の数と同様に指数関数的に増加する3Dマップでは、問題はより深刻になります。マッピングされる領域が比較的小さく、観測の密度が大きい屋内環境では、占有グリッドは一般的に高速でコンパクトな表現を提供するのに十分です。しかしながら、まばらな観測で広い3D屋外領域を表現することは、依然として挑戦的です。 これらの問題のいくつかを解決するための試みとして、Gaussianプロセス占有マップ（GPOM）（O’Callaghan and Ramos、2012; O’Callaghan et al。、2009）が提案されました。アイデアは、位置を占有クラスにマッピングする関数の空間よりも先にガウス過程を使用することです。この方法は連続的であり、すなわち空間の事前の識別を必要とせず、そしてノンパラメトリックである。表現の複雑さは、データポイントの数とともに増大します。最終的なガウス過程分類子モデルは、パラメータ化共分散関数を通して空間的関係を直接捉え、過程の不確実性を自然にコード化する原理的確率的後写像を生成するので、空間表現において得たい多くの利点を有する。主な欠点は、データをより小さな集合に近似または分割することなく、データのサイズに比例して拡大縮小するという計算上の複雑さです。

本稿では、連続稼働率マッピングのより簡単で高速なアプローチを提案します。最近の最適化の進歩（Zhang、2004）と効率的なカーネル近似を利用して、観測を再生カーネルHilbert空間（RKHS）に投影する高次元特徴ベクトルに作用する線形識別モデルで世界の占有特性を表します（ Scholkopf and Smola、2001）。モデルを訓練するための目的関数はパラメータにおいて凸であり、したがって大域的最適値を見つけることができる。さらに、確率的勾配降下法（ＳＧＤ）を用いてモデルを訓練および更新して、計算を観測数とは理論的に無関係にすることができる。我々のアプローチの鍵は、そのドット積が周知の動径基底関数カーネル（ＲＢＦ）に近似する多数の特徴を迅速に生成することである（Scholkopf and Smola、2001）。 RBFカーネルは、物理的世界の複雑さを漸近的に表すことができる無限次元空間への特徴マッピングと見なすことができます。カーネルを近似するための3つの解決策を提示します。 （1）最初のものは最近提案されたRKS（Random Kitchen Sinks）に基づいている（Rahimi and Recht、2008、2009）。 （2）2つ目は、カーネルマシンで非常に人気のあるNystrom近似に基づいています（Williams and Seeger、2000b）。 （3）最後に、疎な特徴を生成し、局所的な情報をよりよく捉える、新しい特徴マッピングを紹介します。また、これらの機能を一般化して、確率分布を入力として受け入れることで、位置確認エラーやセンサーノイズを処理するためのより堅牢な方法を示します。 GPOMとは対照的に、私たちの方法は線形時間で更新することができ、大量のデータでうまくスケーリングできます。それはロボット工学におけるいくつかのタスク、例えば握ることや経路計画などに対処するために使うことができます。このモデルは、環境の占有特性を表す関数を提供します。したがって、把握するための表面の勾配の計算が可能になります。さらに、経路計画の最適化手順にシームレスに統合して、衝突の可能性を最小限に抑えることができます。論文1の技術的貢献は次のとおりです。

  1. ヒルベルトマップ - 大規模データセットに拡張可能で線形時間で更新される新規の連続占有マップ技法。

  2. 局所情報をより良く保存し、より速いＳＧＤ反復をもたらす、新規のスパースヒルベルト空間の特徴３。

  3. 原理的な方法で、測定位置の不確実性に対処するための入力として確率分布を受け取る方法の一般化。

この論文は以下のように構成されています。 SGDによるオンライン学習のための目的関数と最適化については3章で紹介する。ヒルベルトマップ、GPOMの関係と最近の関連学習に関連する機械学習の結果について議論する。 セクション4でこのテクニックの重要な局面。ベンチマークデータセットと比較に関する実験はセクション5に提示されます、そして、将来の仕事のための考えとの結論はセクション6にあります。

2. Hilbert maps

3. Online learning

4. Relationship to other methods

SVMs: 機械学習の文献には、これまでに説明した方法に似たいくつかの分類子があり、それぞれ長所と短所があります。特に、Pegasos（Singer and Srebro、2007）は、高価な2次計画法の最適化が主問題に適用されるSGDに置き換えられた、別のSVM定式化です。著者らは、この方法が強い収束特性を持つトレーニングポイントの数に応じてはるかに優れたスケールになることを示しています。しかしながら、Pegasosは、我々の方法が異なった損失関数を使用していたので、カーネル特徴近似について訓練されていなかった。 SVMと同様に最大マージン損失やヒンジ損失を使用せず、ロジスティック回帰式を選択した主な理由は、ロジスティック回帰で自然に得られた結果の確率論的解釈に関連しています。例を図1に示します。ここでは、2つの方法で作成された同じ連続稼働率マップを示しています。 SVMは確率論的解釈を直接生成しないので、人工確率論的出力は一般にPlatt（1999）の方法を用いて得られる。しかし、図が示すように、これは問題を引き起こします。探検されていない領域、官能的な情報がない状態では、高い確信をもって占有領域または非占有領域に分類されます。逆に、ロジスティック回帰式では、未調査領域は予想どおり50％の確率で占有されます。

GPOM: この作品はまた、GPOM（O'Callaghan and Ramos、2012; O'Callaghan et al。、2009）からのアイデアを借用しています。両方とも連続的に空間を表現しようとしています。どちらも占有率の確率論的解釈を行い、どちらもカーネルを利用して高次元空間のデータポイントを表します。ただし、大きな違いもあります。 GPOMはノンパラメトリックです。すなわち、モデルの複雑さはデータ点の数と共に増大する。近似値がないと、潜在的に大きいグラム行列を反転する必要があるため、GPOMにはO（n3）のコストがかかります。ここで、nはデータポイントの数です。 ＧＰＯＭは、関数空間マッピング入力に先行してガウスプロセスを仮定する。分類出力（事後）を取得するには、シグモイド型の尤度を事前確率と組み合わせて、近似が必要な難解な積分を含む式を作成します。 GPOMは、ガウス過程の予測平均を中心とした点推定値で尤度優先周辺化を解決しますが、これは事後確率の不正確な確率推定値をもたらす可能性があります。 GPOMでは、ベイズ法として、周辺尤度を最大化することでモデルの（ハイパー）パラメータを自動的に取得できます。 GPOMとは対照的に、Hilbertマップはロジスティック回帰分類器に基づいて、はるかに単純な判別モデルに基づいて構築されています。正確な補間を提供することにおける方法の能力の大部分は、ヒルベルト空間埋め込みをＳＧＤの速度で近似する特徴の組み合わせによるものである。ヒルベルト写像はパラメトリックモデルであり、学習と推論の両方の複雑さはデータ点の数とは無関係ですが、むしろ特徴の数mに依存します。現在の形式ではヒルベルト写像は頻繁に使われる手法であり、そのため正則化パラメータの指定が必要です。しかし、実験では、正則化パラメータとカーネルパラメータを簡単に調整でき、値が環境によって大きく変わる必要がないことがわかりました。ヒルベルト写像は、妥当なコストでGPOMに比べて著しい計算上の利点を提供します。ヒルベルト空間近似のためにわずかに劣った補間力。ヒルベルト写像は将来の研究で論じられるように変分ベイズロジスティック回帰式に拡張することができることにも注意してください。表1は、GPOMとHilbertマップの主な違いをまとめたものです。

RKS: ＲＫＳに基づくが、高次元データに対するより優れたスケーラビリティ特性を有する別の種類のカーネル近似が、Ｌｅ ｅｔ ａｌ。 （2013）。著者らは、特徴の計算コストをO（nmd）からO（nm log d）にどのように改善するかを示します。ここで、mは特徴の数、nはサンプルの数、dは入力の次元です。この方法は、式（７）のランダム行列ｓを生成するための高速因数分解スキームに基づいている。この拡張は、コンピュータビジョンなどの高次元データに関する問題では興味深いものですが、3Dの場合、データの次元が多くても3になるため、占有マッピング問題では効果が少なくなります。いくつかの回帰と分類の問題についてRKSとNystromの特徴を比較した興味深い研究がYang et al。に発表されました。 （2012）。著者らは、式（8）の固有スペクトルD ˆの間に大きなギャップがある場合、Nystrom法が印象的な結果を生み出し、RKSを凌駕することを示しています。実験で見るように、これは、Nystrom法が同様の精度を達成するためにはるかに小さな特徴のセットを必要とした占有率マッピング問題で観察されました。ただし、Nystrom法はデータに依存するため、RKSのようにフィーチャを事前計算することはできません。

Additive kernels: コンピュータビジョンでは、いくつかのカーネルは、各次元に独立して適用されるカーネル関数の合計として書くことができる：ｋ（ｘ、ｘ）＝ Ｄ ｄ ＝ １ ｋ（ｘ ｄ、ｘ ｄ）。 これらのカーネルの例には、インターセクション、C、Hellinger、Jensenのいずれかのカーネルが含まれます。 このクラスのカーネルに対して、VedaldiとZisserman（2012）は、カーネルのスペクトル表現が合計で近似されるBochnerの定理の離散版に基づく異なる近似を提案しました。 それらの近似は、物体認識や歩行者認識などの一般的なコンピュータビジョンタスクを同様の精度で大幅にスピードアップしました。 RKSとLe et al。のFastfood近似と同じように。 （2013）、ヒルベルト写像はまた加法的な核で実行されることができます。 しかしながら、そのような近似の主な利点は高次元の問題に取り組むことにあり、それゆえこれらの特徴が占有率の表現のような低次元の問題にもたらす利点は不明である。

5. Experiments

6. Conclusion and future work

この論文は新しい占有マッピング技術、ヒルベルトマップを紹介した。この手法はいくつかの点で占有グリッドマップを改善しますが、特に、空間の離散化、任意の解像度でのマップのレンダリングを必要としません。観測の絶対位置がSLAM手順の一部として部分的に知られているか、または推定される場合に対処するために、我々は観測の空間的位置にわたる確率分布を埋め込むための方法を提案する。この技術は、各データポイントが学習中に一度だけ訪問されるときでさえ強い収束保証が存在するＳＧＤによる効率的な学習を可能にするために、カーネルマシンにおける最近の進歩、特にカーネル近似を探求する。実験結果は、作成されたマップが外れ値の影響を受けにくく、根本的な不確実性を表現する上でより正確であることを示す非常に有望なものです。最良の結果は、Nyströmとスパース機能で達成されました。どちらも誘導点の指定が必要です。これらの誘導点は、グリッド上に配置することも、k-meansなどのクラスタリング手順を使用して自動的に取得することもできます。より多くの観測が捕捉されるにつれてより多くの特徴を追加的に追加すること、またはより高い精度が必要とされる地図の領域内の特徴の数を増加させることは両方ともモデルの適応性を改善するための興味深い将来の方向である。 SGDに基づくオンライントレーニング戦略の重要な利点は、ループクロージャなどのナビゲーション中に大きな軌道修正が行われた後にマップを更新できる速度に関連しています。ループが閉じると、収束するまで更新されたデータに対してSGDを実行して、新しい更新されたマップを作成できます。 この手順を機械学習問題で使用して、シーケンシャルデータ内の非定常性の問題に対処できます（「共分散シフト」としても知られています（Sugiyama et al。、2007））。ヒルベルトマップの利点は、SGDは非常に高速で安価に実行できるため、再トレーニングを効率的に実行できることです。ヒルベルトマップは、ロボットシステム内の連続的な占有表現として多くの用途があります。例えば、それらは能動的な視覚的セグメンテーションおよび触覚的探査を用いて握るための表現を生成するために使用され得る（Bohg et al。、2010）。ヒルベルトマップによって提供される確率論的出力は、追加の観測が必要とされるより高い不確実性を持つ地域に情報を提供することによって探査を導くことができます。経路計画はまた、Ｙａｎｇ ｅｔ ａｌ。 （2013）。 ランダムツリーの高速探索などの一般的な計画アルゴリズムは、占有特性とそれに関連する不確実性を使用して、環境内の安全境界について推論することができます。これは、無人航空機による雑然とした自然環境での計画のために実証されています。ヒルベルト写像上の軌道の機能的最適化に基づく経路計画戦略の開発の可能性もある。連続表現として、ヒルベルト写像はより安全な軌道を見つけようとする最適化アルゴリズム内で直接利用することができる。空間座標に関する占有関数の勾配もまた最適化プロセスをスピードアップするために容易に得ることができる。最後に、最近の結果は、連続占有率マップがモンテカルロ局在化に利用でき、グリッドマップと同等の定式化よりも優れた結果を達成できることを示唆している（Hata et al。、2016）。ヒルベルトマップの連続表現を直接活用する適切な尤度モデルを使用すると、特に不確実性のレベルが高い場合、ローカライズをより堅牢にすることができます。 将来の作業にはいくつかの道があります。まず、占有グリッドマップとオクトマップの両方が特定の機能を備えたヒルベルトマップの特定のケースであることを示すのは簡単です。グリッドの場合、入力点の位置が正方形または立方体のどちらにあるかに応じてフィーチャが0または1として定義されていると、Hilbertマップはgridmaps / Octomapsと同様の出力を生成します。これは、この方法の柔軟性を強調し、より多くの機能開発または非常に異なる特性を有する機能の組み合わせに対する展望を開く。第二に、この方法は、頻度論的手法として定式化され、カーネルと正則化パラメータの手動調整を必要とします。ベイジアン最適化などの最近の技術をこの目的のために使用することができるとしても（Snoek et al。、2012）、もっと原理的な解決策はベイジアン学習課題として問題を定式化することである。残念なことに、これは事後的手法に対する非分析的な解決策につながり、変分法などの近似手法を適用する必要があります。また、目的関数は凸ではなくなり、この場合のSGD収束保証はあまり開発されていません。それにもかかわらず、これはさらなる調査のための興味深い分野のままです。最後に、占有マッピングは、この手法を適用できる他の多くの問題のほんの一例です。オンラインで効率的な方法で移動ロボットによって捕捉されたデータのストリームに基づいて確率的予測を提供することであるアルゴリズムの基本的な考えは、他にも多くの用途がある。例えば、このアルゴリズムは、強化学習において最適な方針を学習するために、またはオンライン物体認識を実行するために使用することができる。

Asymptotically Optimal Sampling-based Kinodynamic Planning

論文 Robotics Robotics-Planning

Yanbo Li, Zakary Littlefield, Kostas E. Bekris IJRR, 2016 https://journals.sagepub.com/doi/abs/10.1177/0278364915614386?journalCode=ijra https://arxiv.org/pdf/1407.2896.pdf

Stable Sparce RRT(SST)に関する論文

Abstract

サンプリングベースのアルゴリズムは、高次元の運動計画のための実用的な解決策と見なされています。最近の進歩はランダム幾何学的グラフ理論を利用して、これらの方法で漸近的最適性もどのように達成できるかを示しています。ダイナミクスを含むシステムでこの望ましい特性を実現するには、基礎となる動的システムの状態空間で2点境界値問題（BVP）を解く必要があります。しかしながら、実用的ではないにしても、ロボットの様々な重要な動的モデルまたは物理的にシミュレートされたモデルに対してBVPソルバーを生成することは困難です。したがって、BVPソルバーにアクセスせずにシステムを計画する際に最適性の保証を達成することさえ可能であるかどうかという、オープンな課題がありました。この作業は、上記の問題を解決し、インクリメンタルサンプリングベースのプランナーを使用して新しい厳密なフレームワークを導入することによって、キノダイナミック計画の漸近的最適性を達成する方法について説明します。この分析の結果、STABLE_SPARSE_RRT（SST）とSST *の2つの新しい方法が得られます。これらはそれぞれ漸近的に最適に近いものと最適です。これらの技法は、スパースなサンプルのセットのみを維持しながら、高速で高品質のパスに収束することが示されているため、計算効率がよくなります。プランナーの優れた性能は、動的システムベンチマークと物理的にシミュレートされたロボットを使用した実験結果によって確認されます。

1.Introduction

Kinodynamic Planning: 多くの興味深いロボットにとって、根本的なダイナミクスを考えると、衝突のない経路を実行可能な経路に適応させることは困難です。このクラスのロボットには、高速の地上移動体（Likhachev＆Ferguson（2009））、固定翼飛行機のような無人航空機（Richter et al。（2013））、またはバランスや移動を含む動力を備えた多関節ロボットが含まれます。システム（Kuindersma et al。（2014））。原則として、それらの構成の二次導関数（例えば、加速度、トルク）によって制御され、ドリフトを示すほとんどのロボットは、それらの制御性を考慮して軌道計画のための分離アプローチによって扱うことができない（Laumond et al。（1998）、Choset）。他（２００５））。このような課題を解決するために、基底システムの状態空間内で衝突のない実行可能な軌跡を直接探索することを含む、キノダイナミクス計画のアイデアが提案されました（Donald et al。（1993））。これは、より高次元の空間を検索し、ダイナミクスから生じる基礎となる流れを尊重することを含むため、キネマティックパスプランニングよりも難しい問題です。その重要性を考えると、しかし、それはロボット工学界で多くの注目を集めています。この研究の焦点は、キノダイナミクスの課題に対する人気のあるサンプリングベースのモーションプランナーの特性にある（Kavrakiら（1996）、LaValle＆Kuffner（2001a）、Hsuら（2002）、Karaman＆Frazzoli（2011）。 ）

Sampling-based Motion Planning: サンプリングベースのアプローチは、比較的高次元の運動計画の課題に対する実行可能な経路を迅速に見つけるための実用的な解決策であることが示されている（Kavrakiら（1996）、LaValle＆Kuffner（2001a）、Hsuら（2002））。最初の一般的な方法論である確率論的ロードマップ法（PRM）（Kavraki et al。（1996））は、キネマティックシステムの構成空間を前処理して次の目的に使用できるロードマップを生成することに焦点を当てていました。 すぐに複数の質問に答えます。 RRT-Extend（LaValle＆Kuffner（2001a））やEST（Hsu et al。（2002））などのツリーベースの亜種は、キノダイナミクスの問題への対処に焦点を当てていました。これらすべての方法について、提供される保証は確率的完全性、すなわち、もし存在する場合に解を見つける確率が1に収束するまで緩和される（Kavrakiら（1998）、Hsuら（1998）、Ladd＆Kavraki（ 2004））。モーションプランニングの難しさと次元性の呪いを考えると、これはコミュニティの十分な目的と見なされていました。しかし最近になって、焦点は実現可能な解決策の提供から高品質の解決策の達成へと移ってきた。マイルストーンは、サンプリングベースのアルゴリズムが漸近的に最適である条件の識別です。これらの条件は、ランダムな幾何学的グラフの結果に基づく基礎となるロードマップの接続性に関連しています（Karaman＆Frazzoli（2011））。この一連の作業は、PRM やRRT のような運動計画のための漸近的に最適なアルゴリズムを提供した（Karaman＆Frazzoli（2010））。

Lack of a BVP Solution: 運動計画ロードマップの生成に対する要求は、ステアリング機能の存在である。この関数は、障害物がない場合の2つの状態間の最適経路を返します。動的システムの場合、ステアリング機能は2点境界値問題（BVP）の解に対応します。この問題に取り組むことは、微分方程式を解くことに対応し、同時に特定の境界条件も満たします。しかし、多くの興味深い動的システムに対してBVP解を作成することは容易ではありません。そのため、漸近的に最適なPRM を含むロードマッププランナーをキノダイナミクス計画に使用することはできません。残念なことに、RRT は、木のデータ構造を生成するとしても、基礎となるロードマップを推論するため、ステアリング機能も必要です。場合によっては、線形化されたダイナミクスのバージョンを計画する（Webb＆van Den Berg（2013））か、BVP問題に数値近似を使用するだけで十分ですが、このアプローチは一般的な解決策ではありません。さらに、システムが物理エンジンを使用してシミュレートされる、重要なクラスの計画上の課題には簡単には対処できません。この状況では、計画プロセスに利用可能なプリミティブは、物理エンジンを使用したダイナミクスの順方向伝播です。したがって、運動計画コミュニティにとっての未解決の問題は、ダイナミクスの順方向伝播モデルへのアクセスのみを考慮して最適性を達成することさえ可能であるかどうかであった。

Summary of Contribution: 本稿では、キノダイナミクス計画のさまざまな課題に対するツリーデータ構造を構築するインクリメンタルサンプリングベースのアルゴリズムの特性を分析するための新しい方法を紹介します。 この分析は、計画者がシステムのダイナミクスの順方向伝播モデルにしかアクセスできない場合に、漸近的最適性を達成できる条件を提供します。 その推論は、Chowの条件が成り立つ非ホロノミックシステムの確率的完全性と漸近的最適性を論じるためのキノダイナミックシステムのアクセシビリティ特性と確率論に基づいており、BVP解の必要性を排除します。 これらの結果に基づいて、キノダイナミックプランニングのための一連のサンプリングベースのプランナーが検討されます。 a）NAIVE_RANDOM_TREEと呼ばれる、ツリーデータ構造をランダムに拡張するESTの単純化：漸近的に最適であるが高品質のパスへの良好な収束がないため実用的ではないことが示されています。

b）RRT-BestNear（Urmson＆Simmons（2003））と呼ばれるRRTの既存のバリエーションにインスパイアされたアプローチで、パスコストの良い到達可能な状態の伝播を促進します。漸近的に最適に近いことが示されています。高品質のパスへの実用的な収束率が、RRTのそれよりも高い反復あたりのコストがあります。

c）提案アルゴリズムSTABLE_SPARSE_RRT（SST）とSTABLE_SPARSE-RRT （SST ）。これらはBestNear選択プロセスを使用します。それらは、格納されているノードの数を少なくするために剪定操作を適用します。それらは、それぞれ漸近的な近最適性と最適性を達成することができます。それらはまた、高品質の経路への良好な収束率を有する。 SSTは、枝刈り操作が与えられた場合の最適以下のRRTと比較して、反復あたりのコストを削減しました。これにより、最近傍の検索が高速化されます。

キネマティックポイントシステムに対して提案されているSSTの性能の説明図を図1に示します。これは、RRT *との比較が可能な場合の単純な課題です。これは、RRTが通常、最適なクラスの同位体クラスのパスを返さないという問題です。 SSTは、スパースデータ構造を維持しながら、これを実行できます。図２は、ＲＲＴに対する振り子システムの位相空間の探索におけるＳＳＴの様々な構成要素の性能を説明している。振り子システムにステアリング機能を利用する方法はありません。効率的なRRTと漸近的に最適なRRTに関するSSTとSSTの望ましい特性の要約は表1にあります。

Paper Overview: 次のセクションでは、文献とこの論文の相対的な貢献についてのより包括的なレビューを提供します。それから、セクション3は公式に考慮された問題と提案されたアルゴリズムのための望ましい特性が成り立つ一連の仮定を特定します。セクション4では、キノダイナミックプランニングの文脈で漸近的な最適性と効率を達成するために、サンプリングベースのアルゴリズムをどのように適応させる必要があるかをまず概説します。この概要に基づいて、SSTとSST の説明、および付随する最近傍データ構造を提供します。これにより、ノードを削除してスパースツリーを実現できます。 RRT との比較が可能なキネマティックシステムを含む一連のシステムでのシミュレーション結果と、興味深いダイナミクスのベンチマークがセクション5で利用可能です。 6.物理的にシミュレートされたシステムも同じセクションで検討されています。最後に、この論文は第7節での議論で終わります。

2.Background

Planning Trajectories: 実際のロボットの軌道計画は、動力学（例えば、摩擦、重力、力の限界）を考慮に入れることを必要とする。それは分離されたアプローチ（Bobrow et al。1985、Shiller＆Dubowsky 1991）または直接計画によって達成することができます。後者の方法は動的システムの状態空間を直接探索する。駆動不足の非ホロノミックシステム、特に小時間ローカル制御可能（STLC）ではないシステムには、直接計画アプローチが好ましい。 ここでの焦点は、STLCではなく、ローカルで短時間でアクセス可能なシステムにあります（Chow 1940/1941）。直接計画のための関連文献では、以下の方法論が検討されています。

  • 最適制御を適用することができる（Brockett 1982、Lewis＆Syrmos 1995）が、単純なシステムしか扱えない。代数解は主に2次元点質量システムに利用できます（O’Dunlaing 1987、Canny et al。1991）。

  • 数値最適化（Fernandes et al。1993、Betts 1998、Ostrowski et al。2000）を使用することはできますが、それは大域的な軌道に対しては費用がかかり、また極小値を被ります。非常に動的な問題はまだ挑戦的ですが、この方向に沿って進歩がありました（Zucker et al。2013、Schulman et al。2014）。

  • 微分平坦度を利用するアプローチは、それらが高次元の運動学的なものであるかのように動的システムを計画することを可能にする（Fliess et al。1995）。クワッドローターなどの興味深いロボット（Sreenath et al。2013）はこの方法で扱うことができますが、固定翼飛行機などの他のシステムはこのアプローチには適していません。

  • 検索ベースの方法は、状態空間の離散化上の経路を計算しますが、解像度に指数関数的に依存します（Sahar＆Hollerbach 1985、Shiller＆Dubowsky 1988、Barraquand＆Latombe 1993）。それらはまた、力学系を含む研究の活発な分野に対応する（Likhachev＆Ferguson 2009）。

多項式時間検索ベースの近似フレームワークは、「キノダイナミック」計画の概念を導入し、それを動的点質量について解き（Donald et al。1993）、それからそれをより複雑なシステムに拡張した（Heinzinger et al。1989、Donald）。 ＆Xavier 1995）この研究は、キノダイナミックプランニングのためのサンプリングベースのアルゴリズムに影響を与えました。

Sampling-based Planners: これらのアルゴリズムは、計算上困難な構成空間の障害を明示的に表すことを避けます。それらは代わりに頂点をサンプリングし、それらを衝突のない状態空間内のローカルパスと接続して、グラフデータ構造をもたらします。最初の一般的なサンプリングベースのアルゴリズムである確率的ロードマップ法（PRM）（Kavraki et al。1996）は、ランダムサンプリングを使用してロードマップを事前計算し、次にそれを使用して複数のクエリに回答します。 RRT-Connectは木を返し、個々の質問に素早く答えることに焦点を当てています（Kuffner＆Lavalle 2000）。双方向ツリーの変種はパフォーマンスの向上を実現します（Sanchez＆Latombe 2001）。これらの解決法はすべて、障害物を無視して2つの状態をローカルパスに接続するステアリング機能を必要とします。対称性を持つシステムでは、2つの状態間のギャップを埋めるための数値的方法を使用して双方向ツリーを接続することが可能です（Cheng et al。2004、Lamiraux et al。2004）。ステアリング機能を必要としない２つのサンプリングベースの方法は、ＲＲＴ拡張（ＬａＶａｌｌｅ＆Ｋｕｆｆｎｅｒ ２００１ａ）および拡張空間木（ＥＳＴ）である（Ｈｓｕら、２００２）。それらはダイナミクスを時間的に先に伝播するだけであり、障害物の配置に関係なく状態空間を均等かつ迅速に探索することを目的としています。上記のすべての方法について、確率論的完全性はある条件下で議論される可能性がある（Kavrakiら（1998）、Hsuら（1998）、Ladd＆Kavraki（2004））。これらのアプローチの変種は、失敗したノード拡張の割合を減らすこと（Cheng＆LaValle 2001）、または適応状態空間細分割を適用することによってメトリック依存性を減らすことを目的としています（Ladd＆Kavraki 2005b）。ヒューリスティック（Bekris＆Kavraki 2008）、ローカル到達可能性情報（Shkolnik et al。2009）、力学を局所的に線形化してメトリックを計算する（Glassman＆Tedrake 2010）、バランスをとるためのコストやバイアスを学習する人もいます。探査（Li＆Bekris 2010、2011）、またはグリッドベースの離散化を利用する（Plaku et al。2010、¹Sucan＆Kavraki 2012）。そのようなツリーベースの方法は、様々な興味深いドメインに適用されてきた（Frazzoliら2002、Branickら2006、Zuckerら2007）。 RRTは迅速に解決策を返すのに効果的ですが、次善の解決策に収束します（Nechushtan et al。2010）。

From Probabilistic Completeness to Asymptotic Optimality: 経路品質を改善するためにヒューリスティックを採用しているが（暫定的に最適ではない）、いくつかのRRTの亜種（Ferguson＆Stentz 2006）。 PRM やRRT などのロードマップベースのアプローチが漸近的最適性を達成できることを厳密に示すために、ランダムグラフ理論を利用することによって重要な進歩が達成されました（Karaman＆Frazzoli 2011）。要件は、ステアリング関数を使用して、ノードの総数の関数として、少なくとも対数の近傍との接続について、各新しいサンプルをテストする必要があることです。 RRT のいつでも（Karaman et al。2011）およびlazy（Alterovitz et al。2011）変種も提案されています。現在の研究を鼓舞するスパースロードマップを使用して漸近的に最適に近いことを提供する技術もある（Marble＆Bekris 2011、2013、Dobsonら2012、Dobson＆Bekris 2014、Wangら2013、Shaharabaniら2013）。 。スパースツリーは、フィードバックベースのモーションプランニングのコンテキストで表示されます（Tedrake 2009）。もう1つの作業は、パフォーマンスを向上させるためのLazy PRM アプローチに従っています（Janson＆Pavone 2013）。システムの到達可能領域の控えめな見積もりを構築することができます（Karaman＆Frazzoli 2013）。この到達可能領域は、ダイナミクスの下で適切なメトリックを定義するのに役立ち、ここで説明されているアルゴリズムと組み合わせて使用​​できます。高品質のパスを返すことに焦点を当てている上記の方法はすべて、BVPソルバーを必要とします。

Towards Asymptotic Optimality for Dynamical Systems: RRT *の変形では、ステアリング機能なしで解を改善するために、図3に示す「射撃」アプローチを利用します（Jeon et al。2011）。ノードｂから短い距離内でノードａから状態ｂ０へ伝播し、ｂ０へのコストがより小さい場合、ｂは枝刈りされ、ａからｂ０への辺が追加される。 bのサブツリーはb0から再伝播されます。衝突が発生すると、ノードが枝刈りされる可能性があります。この方法は漸近的最適性を証明することは証明できません。 bとb0の間のギャップを減らすための数値的方法と統合することができます。ここに提示された方法は形式的な保証を達成します。 「射撃」の変形と比較して改善された計算性能が実験結果に示されている。 最近の研究では、線形または線形化可能なダイナミクスを持つシステムのローカルプランナーを提供しています（Webb＆van Den Berg 2013、Goretkin et al。2013）。厳密なステアリング機能の使用を回避することに対する最近の努力もある（Jeon et al。2013）。本論文のアルゴリズムは線形力学をもつシステムを超えて適用可能であるが、そのようなシステムに対して効率的な漸近的に最適に近いソルバーを提供するために上記の方法と組み合わせることもできる。

Closely Related Contributions: ここに提示された作品の初期のバージョンは以前に現れました。当初、提案されたアルゴリズムのより単純なバージョンが提案され、Sparse-RRTと呼ばれていました（Littlefield et al。2013）。この方法では良好な実験的性能が達成されたが、望ましい性質を正式に主張することは不可能であった。これは、フォローアップ研究におけるSTABLE_SPARSE_RRT（SST）とSST *の開発を動機づけた（Li et al。2014）。これらの方法は、キノダイナミックプランニングに対して漸近的（ほぼ）最適性を正式に達成する。この論文で拡張された分析を紹介したのは、同じ論文です。著者によるこれらの初期の努力を与えられて、この論文は以下の貢献を提供します：

・4.1節でステアリング機能を持たないサンプリングベースのプランナを用いた漸近的（近）最適性の一般的枠組みについて述べる。 SSTとSST *アルゴリズムは、このフレームワークの効率的な実装に対応しています。

•提案したアルゴリズムの枝刈り操作をサポートするように特別に設計された最近傍データ構造について、4.4節で初めて説明します。実装 性能を向上させるSSTおよびSST *の説明にガイドラインが導入されています（セクション4.2および7）。

•セクション5では、軌跡の継続時間ではなく一般的な費用関数の特性を議論することによって分析を拡張します。それはまた、以前の研究から欠けていた必要な証拠すべてを提供します。

•固定翼航空機の動的モデルのシミュレーションを含む追加の実験がセクション6で提供されています。最近傍データ構造がモーションプランナーに与える影響の評価もあります。

同時に行われた研究もあり（Papadopoulos et al。2014）、これは同様のアルゴリズムを提示し、それらがキノダイナミクス計画のために高品質の軌跡を返すことを実験的に主張している。それは、ＥＳＴの単純化、すなわちＮＡＩＶＥ＿ＲＡＮＤＯＭ＿ＴＲＥＥアプローチが漸近的に最適であるという主張を支持するための異なる方法を提供する。しかしながら、スパース表現を達成する効率的で実用的な方法の漸近的近最適特性は主張しておらず、対応するアルゴリズムの収束速度についても研究しておらず、また最近傍データ構造のようなそれらの実装のための効率的なツールも提供していない。ここで説明します。

3.Problem Setup

4.Algorithms

5.Analysis

6.Experimental Evaluation

7.Discussion and conclusion

最近、サンプリングベースの運動計画における焦点は、関連する方法の計算効率のバランスをとりながら、最適性保証を提供することに移った。動力学を有するシステムに対してこの目的を達成するためには、一般的に特殊なステアリング機能の生成が必要とされてきた。この研究は、完全にランダムな選択／増殖手順が、キノダイナミックシステムについて合理的な仮定の下で症状の最適性を達成することができることを示している。しかしながら、同じ方法は、高品質の解決策を見つけるための収束速度が非常に遅いので、時間の経過とともに経路改善を提供する方法の収束速度に主に焦点を合わせるべきであることを示している。

これらの問題に取り組むために、この研究は漸近的に最適なサンプリングベースの運動計画のための新しいフレームワークを提案しました。これまでの研究からの出発点は、最優先選択戦略とプルーニングプロセスの利用です。これにより、高品質のソリューションとスパースなデータ構造への素早い収束が可能になります。実験および分析結果は、このフレームワークの具体的な実施、すなわちＳＳＴアプローチの実行時間およびスペース要件が効率的であるが最適とは言えないＲＲＴのそれよりも優れていることを示している。このパフォーマンスの向上は、物理的にシミュレートされたシステムの場合を含む、さまざまなシナリオで見られます。

Parameter Selection: ＳＳＴの２つのパラメータ、すなわちδｓおよびδＢＮは、アルゴリズムの性能に直接影響を与える。 δｓ半径は、剪定ＳＳＴがどれだけ実行するかを制御するので、このパラメータが狭すぎる通路を通る経路を発見しないようにアルゴリズムを導き得るので、このパラメータを高く設定し過ぎないことが必要である。実際には、δｓは所与の問題事例から望まれる経路のクリアランスと同じ大きさにすることができる。目標に近いサンプルの生成を可能にするために、この値を目標領域の半径よりも小さくなるように選択することもまた有用である。ツリーデータ構造を適切に拡張できるようにするには、パラメータδBNをδsより大きくする必要があります。 δBNの値が大きすぎると、ルートに近いノードが繰り返し選択されるため、状態空間の探索が不十分になります。全体として、状態空間サイズ、δＢＮ、およびδｓ間のバランスは、良好な性能を達成するために維持されなければならない。 ＳＳＴ ＊手法は、δｓおよびδＢＮに対してかなり任意の大きな値を使用して探索を開始することを可能にし、それはその後時間とともに自動的に減少する。

Finite-time Properties: SSTは比較的小さいデータ構造を維持し、限られたスペースでは有限サイズのデータ​​構造になるため、論じることができる有限時間特性を考慮することは興味深いです（Dobson＆Bekris 2013）。これは、証人セットSが空きスペースをカバーできる割合に大きく依存します。この最初のカバレッジの後、既存のパスの品質を調べることが可能かもしれません。

Planning under Uncertainty: ステアリング機能の要件を取り除くことで、SSTはステアリング機能を構成するのが難しい他の問題にも適用できます。これらの分野の1つは、計画が確信空間で実行される不確実性の下での計画です。この領域で2つの確率分布を結ぶステアリング関数を計算することは困難ですが、順方向伝播は対応する信念を更新できます。この領域にSSTを適用する際のいくつかの課題は、最良の最初の操作と枝刈り操作、および問題の次元の増加のために適切な距離メトリックを計算することを伴います。この論文で述べられている方法との関連で、Earth Moverの距離に基づく適切な関数が不確実性の下で計画を立てる際の効率的な解決策につながることができることが示されました。 2015）。これは結局、キノダイナミクスおよび非prehenile操作（例えば、押したり、投げたり、引っ張ったりなど）のような重大な不確実性を含む重要な問題へのそのような解決策の適用を導くことができる。

Feedback-based Motion Planning: 別の拡張は、フィードバックベースの運動計画、および計算された軌道が動的に安定していると主張する能力に関する。 現在の研究は、サンプリングベースのキノダイナミックプランニングにおける文献の大部分に従っており、名目上の軌跡のみを提供しており、フィードバックベースの計画または方針は提供していない。 ＬＱＲ木に関する研究のように、フィードバックベースの運動計画の文脈においてサンプリングを利用する研究がある（Ｔｅｄｒａｋｅ ２００９）。 それにもかかわらず、現実的で比較的高次元の動的ロボットシステムに関しては、フィードバックベースの解決策の最適性について議論することは通常困難であった。 このように、興味深い研究の方向性は、フィードバックに基づく計画の中でそのような保証を提供することが可能になる条件を特定することです。

Real-world Experiments and Applications: 大きなダイナミクスを持つ実際のシステム、特に積極的な操縦を行う航空システムや物理エンジンを使用してモデル化されたシステムに対するアプローチの有効性を評価することも重要です。 例えば、将来の惑星探査ミッションはより有能なローバーを巻き込むかもしれません。 彼らは潜在的に短期間の弾道の軌跡を取得し、低重力環境で高速で移動する機能を持つことになります。 このように、ダイナミクスについての推論は計画プロセスの間により重要になります。 ＳＳＴは、経路長、エネルギー消費量、または搭載されているセンサペイロードの感度に関して経路を最適化するために、この分野において有用であり得る。

Locomotion and Dexterous Manipulation: ＳＳＴが使用され得る他の潜在的な研究分野には、移動および器用な操作が含まれる。これらの課題は、物体間の接触のモデルを使用した計画、および移動システムの平衡化またはマニピュレータのための握りの安定性などの物理的考察を含む。摩擦と質量の効果をモデル化するために物理エンジンを使用することは、ここでは役に立ちます。上で実証されたように、ＳＳＴは、物理エンジンが使用されるときに経時的に改善する制御シーケンスを提供する。それにもかかわらず、連絡先の存在は、現在提示されている分析では扱われていない重要な複雑さをもたらします。特に、提供された結果の一般化を複雑にする2つの重要な仮定があります。 liveはd次元ユークリッド空間の滑らかな部分集合です。これらの仮定は、剛体力学およびスティックスリップ摩擦のモデルを考慮することを可能にしません。これらは、移動および器用な操作の有用な理想化です。このような系はジャンプ不連続性を示し、一般に式１の形の表現では表すことができない。局所的なユークリッドではない空間における課題に対処することが可能であるかどうかという問題もある。 接触制約によって生成された多様体を研究することは興味深いでしょう。そのような多様体は代数多様体であり得、それは滑らかである必要はない。さらに、そのような多様体は、指の歩行や移動の問題が実際には一次元の多様なものには存在しないが、より高次元の周囲状態空間における層状集合には存在しないので、異なる次元であり得る。これらの問題は、器用な操作および移動システムの適切なモデルに対して漸近的最適性保証を示す一般的なサンプリングベースのアルゴリズムを提供する方向へのさらなる研究を動機付ける。

Reference * Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning * SST/SST* オリジナル？ * http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=2FAD588F202C3D5D8AD7212A61199037?doi=10.1.1.711.8659&rep=rep1&type=pdf * 2014 WAFR

地図表現の動向調査まとめ

Robotics Mapping

Occupancy Grid

  • Occupancy grids: A probabilistic framework for robot perception and navigation
  • Occupancy Grid Models for Robot Mapping in Changing Environments
    • AAAI2012

Continuous Occupancy Map

Gaussian process occupancy map

  • Gaussian process occupancy maps
    • IJRR, 2012
  • Gaussian process occupancy maps for dynamic environments
    • Springer Tracts Advanced Robotics 2015

Hilbert Map

  • Hilbert maps: Scalable continuous occupancy mapping with stochastic gradient descent
  • Bayesian hilbert maps for dynamic continuous occupancy mapping
    • CoRL2017
  • Dynamic Hilbert Maps:Real-Time Occupancy Predictions in Changing Environments
    • Vitor Guizilini, Ransalu Senanayake and Fabio Ramos
    • ICRA2019
    • University of Sydney
  • Fast Stochastic Functional Path Planning in Occupancy Maps
    • Gilad Francis, Lionel Ott and Fabio Ramos
    • ICRA2019
    • University of Sydney

Point Cloud

  • Generalized icp
    • RSS2009
  • Sparse iterative closest point
    • Computer Graphics Forum, 2013
  • A review of point cloud registration algorithms for mobile robotics
    • Foundations and Trends in Robotics, 2015
  • Speeding up Iterative Closest Point Using Stochastic Gradient Descent
    • ICRA2019

未分類

  • Online Continuous Mapping using Gaussian Process Implicit Surfaces
    • Bhoram Lee, Clark Zhang, Zonghao Huang and Daniel D. Lee
    • ICRA2019
    • University of Pennsylvania

Using Local Experiences for Global Motion Planning

論文 ICRA2019 Robotics Robotics-Planning

ICRA2019 http://www.kavrakilab.org/publications/chamzas2019using-local-experiences-for-global-motion-planning.pdf

サンプリング手法の一つ。

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

この研究では、ワークスペースの分解に基づく新しいサンプリングバイアスフレームワークを提案しました。 単純な幾何学的プリミティブのみを検討しましたが、検討した方法では解決できなかった、または効率的に解決できなかった問題を解決しました。 我々は我々の結果を予備的なものと考えているが、我々はこの作業が運動計画問題に経験を適用するための新しい方法を開くと信じている。 今後の作業には、一般的でより効果的に任意のワークスペースを分解できる、より複雑なプリミティブの使用が含まれる可能性があります。 最後に、データベースのサイズが大きくなるにつれて、効率的なリアルタイム検索アルゴリズムを使用する必要があります。

Planning 研究アカデミアまとめ

Robotics Robotics-Planning

RICE大学, Kavraki Lab

New Mexico大学, TAPIA LAB

Sydney大学, Fabio Ramos's Lab

  • http://www-personal.usyd.edu.au/~framos/Home.html?iframe=true&width=80%&height=80%
  • Professor Fabio Ramos
  • 近年連続空間表現に着目して様々な手法を提案している
  • Gaussian process occupancy maps, IJRR2012(Journal)
  • Hilbert maps: scalable continuous occupancy mapping with stochastic gradient descent(IJRR2016)
  • 機械学習 x ロボティクスが専門
  • 近年伸びていて注目度が高い
  • ICRA2019では5件採択
    • Fast Stochastic Functional Path Planning in Occupancy Maps
    • Dynamic Hilbert Maps: Real-Time Occupancy Predictions in Changing Environments
    • Continuous Occupancy Map Fusion with Fast Bayesian Hilbert Maps
    • Balancing Global Exploration and Local-Connectivity Exploitation with Rapidly-Exploring Random Disjointed-Trees
    • Speeding up Iterative Closest Point Using Stochastic Gradient Descent

Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater Vehicles

論文 ICRA2019 Robotics Robotics-Planning

論文情報

Abstract

水中ロボットは複雑な流体力を受けます。これらの力は車両の動きを定義するので、軌道を計画するときにそれらを考慮することが重要です。ただし、ロボットの搭載コンピュータでダイナミクスを考慮したモーションプランニングを実行することは、利用可能な計算リソースが限られているため困難です。本論文では、自律型水中機（AUV）のための効率的な運動計画の枠組みを提示した。疎結合の多層計画設計を導入することによって、私たちのフレームワークはオンライン計画のために計画時間を十分に短くしながら動的に実行可能な軌跡を生成することができます。まず、低次元投影空間で動作するファストパスプランナーは、 スタートからゴール設定までのリードパス。次に、先頭経路を使用して、すべての動的制約を考慮に入れた、2番目のモーションプランナーのサンプリングをバイアスします。さらに、有限の地平線までの最終軌道のみを生成することによって計算資源を節約するオンライン計画のための戦略を提案する。有限アプローチ戦略と多層アプローチを併用することで、2番目の計画担当者のサンプリングは、質の高いソリューションが見つかる可能性が高い地域に焦点を合わせ、計画期間を大幅に短縮します。強力な安全性保証を提供するために、私たちのフレームワークは避けられない衝突状態（ICS）の保守的な近似も取り入れています。最後に、本物の水中ロボットを使ってシミュレーションと実験を行い、私たちのフレームワークの能力を実証します。

メモ： 課題の概要として、マリンロボットでは流体を考慮した軌道計画が必要だが、ロボットに搭載されたコンピュータでそれを考慮した軌道計画は計算が重すぎて難しい

1. Introduction

他の多くのアプリケーションの中で、自律型水中ビークル（AUV）は今日ロボットの探査と検査を行うために使用されています[1]、[2]、[3]。 ロボットが障害物の近くをナビゲートし、高い精度が要求されるような作業のためには、車両の動的な制約と安全性を考慮してロボットの軌道を慎重に計画することが重要です。 同時に、ロボット位置特定および利用可能であれば環境の地図は通常、任務が始まる前にすべての軌道を計画するのに十分に正確ではない。 そのような状況では、任務の一部は搭載コンピュータを使ってオンラインで計画されなければならないでしょう。 この研究では、この特定の問題に焦点を当てています。オンライン計画に適したアルゴリズムを作成することに特に関心があります。 オンラインロボット軌道を生成するために様々な戦略が提案されてきた。 任務中に事前計画された軌道に関する偏差が小さいと予想される場合、潜在的な場などの反応的アルゴリズムで十分である可能性があります[4]。 あるいは、オンライン幾何学的経路プランナを使用することができる。 例えば、Dubinsのパスは過去に水中で使用されてきました[5]。 ビークルのダイナミクスを考慮する必要がある場合、state-latticeはビークルの可能な操作を制限しますが、実行可能な軌道をオンラインで計画するための便利なフレームワークを提供します[6]。 最後に、サンプリングベースのキノダイナミックプランナーを使用することも可能ですが、多くの場合、このアプローチはオンライン計画には遅すぎます。 計算をスピードアップするために、何人かの作者は多層計画ソリューション(multilayered planning solutions)[7]を提案しました。 セクションIIでは、制約を伴う運動計画および多層計画における最新技術を概説する。 本稿では、車両の動的モデルを考慮し、提供されたモデルに従って実現可能な軌道を生成し、そして車両の全ダイナミックレンジを利用する新しい運動計画の枠組みを提示した。運動学的に実現可能な経路（漸近的最適探索ランダムツリー（RRT *）プランナを使用して生成された[8]）を使用して動的に実現可能かつ安全な軌道の探索にバイアスをかける（生成）安定したsparse-RRT（SST）プランナを使う、[9]。結果のセクションで示されているように、SSTプランナーは複雑なダイナミクスを伴うオンライン計画には遅すぎる可能性があるため、私たちの多層フレームワークは計画計算を高速化してオンライン計画に適したものにします。不可避衝突状態（ICS）の概念を使用することによっても、強力な安全性保証が課されます。著者の知る限りでは、この作業は、計画時間の短縮を目的として、SSTプランナーとRRT *パスプランナーを組み合わせたモーションプランニングフレームワークを初めて提供するものです。さらに、安全コンティンジェンシーマヌーバが自律型水中ビークルに適用されるのも初めてです。多層計画方式は困難なシナリオにおける水中航法のための実用的で効率的な方式であることがシミュレーションと実験を通して示された。アルゴリズムの詳細はセクションIIIで見つけることができます、そして次にセクションIVとVはSparus II AUV（図1を見ます）と結論を使っている結果を提示します。

メモ： 論文のアプローチのポイントは、RRTとSSTの組み合わせ・軽量化。 RRTでおおよそのパスを決定し、SSTでsuboptimalな軌跡を生成する 従来手法としてSSTと比較して計算コストが良いと示している

2. Related Work

このセクションでは、幾何学的アプローチから始めて、state latticesのプランニング、キノダイナミックプランニング、そして最後に多層モーションプランニングまで、水中ロボットのモーションプランニングに関する関連作業を概説します。それはまた我々の要求に従って我々の水中運動計画問題への全ての方法の適用可能性を分析する：我々は漸近的最適性を持つ速いキノダイナミック運動プランナーが欲しい。 Hernandezら[5]は、水中ロボット用のオンラインの幾何学的経路計画の枠組みを提示しており、これはDubins経路によるロボットの軌道を近似している。リン等 [10]はまた、航空機用のDubinsパスも使用しました。代替案として、スプラインは、コナーズらによる運動計画においても使用されてきた。 [11]。しかしながら、幾何学的経路プランナが使用されるとき、ゼロ誤差で経路をたどることはほとんど不可能である。例えば、Ｄｕｂｉｎｓ経路は区間ごとに角速度の急激な変化を示し、それは無限の角加速度が可能なシステムによってのみ達成可能である。この作業における私たちの目的は、この制限を克服することです。

計画段階での車両のダイナミクス水中ロボット工学に関連するもう1つの作業は、state latticesで計画することです。state latticesを使用するとき、動き計画問題は、グラフの頂点および辺が事前計算された動きプリミティブの縮小されたセットに従って生成される無制限グラフ探索として解決される。状態格子は幾何学的なものでもよく、あるいはビークルダイナミクスも含むものでもよい。我々の水中計画問題に関連する例はPivtoraiko et al。に見いだすことができる。 ［１２］、Ｌｉｋｈａｃｈｅｆ ｅｔ ａｌ。 ［６］、およびＨｅｎｔ ｅｔ ａｌ。 [13]、[14]。しかしながら、ロボットの実際の能力のいくつかが失われるので、より少ない一連の動作を使用することは望ましくない可能性がある。我々は我々の水中ビークルの全ダイナミックレンジを使用したいので、state latticesは我々の用途には適していない。 あるいは、状態空間を制限しない、利用可能な多くのキノダイナミックモーションプランナーがあります。それらのほとんどは漸近的最適性保証を提供しないが、それらのうちのいくつかはより長い計算時間を犠牲にして提供する。漸近的最適高速探索ランダムツリー（ＲＲＴ ＊）のキノダイナミックバージョンが、Ｗｅｂｂ ｅｔ ａｌ。 [15]。それらは、状態の任意のペアを最適に接続する固定最終状態自由最終時間コントローラを使用します。彼らの方法の不利な点は、それが線形力学をもつシステムのために設計されていることです。ダイナミクスが線形ではない場合、いくつかの仮定の下でそれらのアプローチはシステムを線形化することによってまだ使用することができます。しかし、このアプローチは、水中ロボットには非常に非線形なダイナミクスがあるため、適していません。ハウザー他。 [16]は、実行可能なキノダイナミックプランナーから漸近的最適性を得るための方法を提案しました。彼らは状態変数をコストで増大させ、それから計画問題は反復的に解決され、その解決策は各反復でより良いコストを持たなければならないと主張する。この方法は漸近的な最適性を保証しますが、計算効率があまり良くないため、オンライン計画には使用できません。最後に、Liらによる安定スパースRRT（SST）プランナ。 [9]は、経路のコストに従って、動きをアクティブと非アクティブの2つのカテゴリに分割するツリーベースのモーションプランナーです。最終的には最良の動きが木に残り、最も効率の悪いものが消え、漸近的最適性も保証されます。

この研究は多層計画アプローチを提示しているので、多層運動計画に関する文献を検討することもまた重要である。 Sequeira等。 [17]は水中ビークルのための2層経路計画アプローチを提案しました。彼らの提案では、幾何学的ハイレベルプランナー（HLP）は開始コンフィギュレーションから一連の連続したウェイポイントを計算します。そして、ローレベルプランナー（LLP）は、ウェイポイント間の車両構成を生成するための潜在的なフィールドテクニックを実装します。あるいは、Ａｒｉｎａｇａ ｅｔ ａｌ。 [18]は2層パスプランナーも提案しました。彼らのグローバルプランナは最小のコストで経路クラスを見つけるために接続性グラフを使い、そして幾何学的なローカルモーションプランニングステップで、2つの構成を結ぶ滑らかな経路が計算されます。しかしながら、両方のアプローチは、車両の動力学を考慮に入れていない。

パルミエリ他[19]は、急速に探索するランダムツリー（RRT）プランナの探索にバイアスをかけるためのリードパスを生成するためのtheta*パスプランナの使用を提案した。ただし、2番目の計画者はRRTであるため、漸近的最適性保証は提供されません。ハーバート他。 [20]は、単純化されたダイナミクスを使って軌道を計画する運動計画アルゴリズムを提案しました。彼らのアプローチでは、生成された軌跡は実際のロボット軌道の近似それから、追跡と安全制御装置は、最悪の外乱に依存する限界誤差でおおよその軌道をたどるために使用されます。しかし、これは、特に水流を考慮して計画するときに、最悪の場合の擾乱についてすべての経路を衝突チェックする必要があることを意味します。

最後に、Plaku等。 （[21]、[22]、そしてその後の[7]）は、2つのパスプランナーが密接に統合されている多層アプローチを提示しました。最初の計画者は、リードを計算します。リードは、開始状態と目標状態に関連付けられた領域で開始および終了する一連の分解領域として定義されています。彼らの作品では、リードはスタートからゴールまで行くために訪れるセルの大まかなスケッチとして理解することができます。その後、このリードは2番目の計画担当者に渡されます。第２の立案者が所与の誘導内に軌跡を見つけられない場合、第１の立案者が代替の誘導を再計算するために実行される。彼らの提案では、最初のプランナーは離散検索を使用し、2番目のプランナーはサンプリングベースのモーションプランナーです。しかしながら、提案されたプランナの組み合わせは漸近的最適性を保証するものではなく、離散的なプランナは高次元性を伴う問題において遅くなる可能性がある。

3. MULTILAYERED PATH PLANNING WITH DYNAMIC CONSTRAINTS

4. Results

提案された運動計画フレームワークをテストするために、Sparus II AUVが使用されています（図1、[25]を参照）。 部分的なホバリング能力を持つ魚雷型のロボットです。 揺れ、ロールおよびピッチ自由度（DOF）は作動しませんが、サージ、ヒーブおよびヨー自由度（DOF）は作動します。 2つの異なるシナリオが使用されています。 最初のシナリオは、スペインのジローナにあるSt. Feliu de Gu´xolsの港の外にある一連の防波堤コンクリートブロック（図1を参照）で構成されています。 各ブロックは12×12メートルの範囲にわたり、ブロック間の距離は5メートルです。 狭い通路と水流のため、モーションプランニングアルゴリズムをテストするのは困難なシナリオです。 2番目のシナリオは、St Feliuの海岸崖と大きな岩の間の峡谷に似た、長さ100メートルの狭い通路です（図6を参照）。

A. Simulated results

提案されたフレームワークに対してSSTプランナーのパフォーマンスと均一サンプリングを比較しました。それぞれ90秒間の100回の実験が行われました。図４は、計画時間の関数としての（式（２）からの）経路コストの箱ひげ図を表す。同じ量の計画時間が経過した後、私たちのフレームワークによって提供されるソリューションのコストはSSTプランナーだけの場合よりも低く、特に最初の段階ではオンライン計画にとって特に興味深いことがわかります。図5は、10秒後の両方の場合における計画ツリーの進化をグラフで示したものです。フレームワークはすでに最適に近い解に収束していますが、SSTプランナーは調査する必要がある面積が大きいため、すべての場合で収束しているわけではありません。この実験はオフライン計画として分類することができます。これは、マップが既知であり、最初の構成から目的の構成までの軌跡を計算するために1回の計画の反復しか実行されないためです。私たちが行った2番目の模擬実験は、複雑で構造化されていないシナリオでオンラインで計画することです。このシミュレーションの目的は、実際の実験の前にオンライン計画のためのフレームワークをテストすることでした。図６は、環境およびロボットの軌道の上面図を示す。ロボットの軌道は滑らかで、ロボットは障害物に決して近づきません。ロボットの速度は常に最大許容速度0.3 m / sに近づいていました。私たちの運動計画の枠組みはシステムの力学を考慮に入れるので、運動計画段階で水流の影響を導入することは可能です。これは、動的方程式の減衰項内の水に対する車両の相対速度を考慮することによって達成される（式（５）を参照）。私たちが行った3番目の模擬実験は、水流を無視することとそれらを考慮に入れることの違いを示しています。図7は、目標が2つの防波堤ブロックの間にあるが横方向の水流があるという単純なシナリオでの計画軌道と実際のロボット軌道を示しています。運動計画段階で考慮する。この実験では、北方向に0.4 m / sの一様な流れが考慮されていますが、フレームワークは時間/状態のパラメータ化可能な水流に対応できます。

B. Experimental results

図8は、Sparus II AUVを使用した実際の水中実験を示しています。 実験は防波堤ブロックを横断して自律的にオンライン計画を行っていた。 ロボットには、最大10メートルの範囲までの外因性データを捕捉する機械的走査プロファイリングソナーが装備されていました。 マップは実験中に徐々に作成され、再計画は5秒ごとに行われました。 すべての実験は2.0 mの深さで行われ、要求された速度は0.3 m / sの最大許容速度に近く、狭い旋回では減少するだけでした。 提案されたフレームワークはすべての実験でゴールへの安全な道筋を計算することができたので、任務中にロボットを安全な状態にするための偶発的な操作は実行されませんでした。

5. Conclusion

本論文では、限られた量の計算資源でさえ、水中の乗り物の動的制約と安全性を考慮に入れた軌道を生成する新しい運動計画の枠組みを提示した。著者の知る限りでは、この研究は、安定スパースRRT（SST）プランナーと漸近的最適高速探索ランダムツリー（RRT *）モーションプランナーを組み合わせることを目的としたモーションプランニングフレームワークを初めて提示します。計画時間を短縮します。さらに、安全コンティンジェンシーマヌーバが水中ビークルに適用されるのも初めてです。以前の貢献に加えて、この作品はまた提案された計画の枠組みを評価するための実験データを含みます。 シミュレーションでは、SSTプランナーを単独で実行した場合よりもパフォーマンスが大幅に向上し、コンバージェンス率が向上しています。これは、オンライン計画を実行する際に特に重要です。実際の実験は、計画した軌道が実際の水中ロボットに適していることを示し、そして提案したフレームワークが私たちの計算予算内で動作でき、初めてSparus IIによる軌道計画のための動的モデルの使用を可能にした。 AUV最後に、このフレームワークは他のロボットにも容易に適応させることができます。それらの動的モデルのみが使用されるからです。それは柔軟であり、水流のような擾乱は容易に考慮に入れることができる。前述の考慮事項のために、私たちはこの仕事が運動計画共同体の他の部分に関連しているかもしれないと信じる。

次に調べること

  • state lattices plannerの特性。なぜ選ばなかったのか
  • [9] stable sparce RRT Planner(SST)
  • Multilayered Motion Planning (優先度順)
    • [7] Region-guided and sampling-based tree search for motion planning with dynamics
    • [21] Discrete search leading continuous exploration for kinodynamic motion planning
    • [22] Motion planning with dynamics by a synergistic combination of layers of planning,
    • [17] A two level approach for underwater path planning
    • [18] A motion planning method for an AUV