理解しやすい単純な言葉遣いで、rrt がどのように機能するかを説明できる人はいますか? サイトとウィキペディアの説明を読みました。
私が見たいのは、rrt の短い実装、または次のことの完全な説明です。
rrt が中心付近で非常に密に成長するのではなく、外側に成長するのはなぜですか? 単純なランダム ツリーとの違いは何ですか?
到達しようとする次の新しい頂点はどのように選択されますか?
ダウンロードできる Motion Strategy Library があることは知っていますが、その逆ではなく、コードを詳しく調べる前にアイデアを理解したいと思います。
最も単純な RRT アルゴリズムは、実装が非常に簡単であるため、非常に成功しています。次の場合、事態は複雑になる傾向があります。
擬似コード
基本的なアルゴリズムは次のようになります。
空の検索ツリーから始める
検索ツリーに最初の場所 (構成) を追加します
検索ツリーが目標に達していない間 (そして時間切れになっていない場合)
3.1. 場所を選択 (構成), q_r, (いくつかのサンプリング戦略を使用)
3.2. そのランダムな点に最も近い検索ツリーの頂点を見つけ、q_n
3.3. 衝突せずにリンクできる場合は、q_nとの間のツリーにエッジ (パス) を追加してみてください。q_r
その説明で十分ですが、この分野でしばらく作業した後、 Steven LaValle の本「Planning Algorithms」のRRT/RDT に関する図 5.16の疑似コードが本当に好きです。
ツリー構造
ツリーが (ほとんどの場合) 検索空間全体をカバーすることになる理由は、サンプリング戦略の組み合わせによるものであり、常にツリー内の最も近いポイントから接続しようとします。この効果は、ボロノイ バイアスの減少として説明されます。
サンプリング戦略
接続しようとする次の頂点をどこに配置するかの選択は、サンプリングの問題です。検索の次元が低い単純なケースでは、一様ランダム配置 (または目標に偏った一様ランダム配置) が適切に機能します。高次元の問題、またはモーションが非常に複雑な場合 (ジョイントに位置、速度、および加速度がある場合)、または構成を制御するのが難しい場合、RRT のサンプリング戦略はまだ未解決の研究領域です。
ライブラリ
実装に行き詰まっている場合は、MSL ライブラリが出発点として適していますが、2003 年以降は積極的にメンテナンスされていません。より最新のライブラリは、Open Motion Planning Library (OMPL)です。また、優れた衝突検出ライブラリも必要です。
計画の用語とアドバイス
用語の観点からは、RRT に関する (初期の) 出版物に見られる図の多くは 2 次元 (2 次元の点を結ぶツリー) であるにもかかわらず、これが絶対的に最も単純なケースであることを理解するのは難しいことです。 .
通常、複雑な物理的状況を説明するには、数学的に厳密な方法が必要です。これの良い例は、n リンケージを持つロボット アームの計画です。このようなアームの端を記述するには、最小限のn関節角度が必要です。位置を記述するためのこの最小パラメーターのセットは、構成(または一部の出版物の状態) です。多くの場合、単一の構成が示されますq
実現可能なすべての可能な構成 (またはそのサブセット) の組み合わせは、構成空間(または状態空間) を構成します。これは、平面内のポイントの境界のない 2D 平面のように単純な場合もあれば、他のパラメーターの範囲の信じられないほど複雑な組み合わせの場合もあります。