モーションプランニング

低次元問題は、構成空間の上にグリッドをオーバーレイするグリッドベースのアルゴリズム、またはCfreeの形状と接続性を計算する幾何学的アルゴリズムで解決することができます。

複雑な制約の下での高次元システムの正確な運動計画は計算上困難である。 ポテンシャル場アルゴリズムは効率的ですが、局所的な最小値の餌食になります（例外は高調波ポテンシャル場です）。 サンプリングベースのアルゴリズムは、局所最小値の問題を回避し、多くの問題を非常に迅速に解決します。彼らはパスが存在しないと判断することはできませんが、より多くの時間が費やされるにつれてゼロに減少する失敗の確率を持っています。

サンプリングベースのアルゴリズムは、現在、高次元空間における運動計画のための最先端と考えられており、数十または数百の次元（ロボットマニピュレータ、生物学的分子、アニメーション化されたデジタルキャラクター、脚付きロボット）を有する問題に適用されている。

オブジェクト操作（飛行物体を捕捉するための）のための運動計画並列アルゴリズム（A1-A2）があります。

グリッドベースの検索編集

グリッドベースのアプローチは、構成空間上にグリッドをオーバーレイし、各構成がグリッドポイントで識別されると仮定します。 各グリッドポイントで、ロボットは、それらの間の線がCfree内に完全に含まれている限り、隣接するグリッドポイントに移動することができます（これは これは一連のアクションを離散化し、検索アルゴリズム（A*など）を使用して開始から目標までのパスを検索します。

これらの方法では、グリッドの解像度を設定する必要があります。 検索はより粗いグリッドで高速ですが、アルゴリズムはCfreeの狭い部分を通るパスを見つけることができません。 さらに，格子上の点の数は配置空間次元で指数関数的に増加し，高次元問題には不適切である。

従来のグリッドベースのアプローチでは、見出しの変更が指定されたベース角度の倍数に制限されるパスが生成され、多くの場合、最適ではないパスが 任意角度パス計画のアプローチでは、グリッドエッジにパスを制約することなく、グリッドエッジに沿って情報を伝播することにより、短いパスを見つけます(短いパスを見つけるために)。

グリッドベースのアプローチでは、例えば、ロボットの構成空間に関する知識が変化したり、パス追従中に構成空間自体が変化したりするときに、繰り返し検索する必要があることがよくあります。 増分ヒューリスティック検索アルゴリズムは、以前の同様のパス計画問題の経験を使用して、現在のものの検索を高速化することにより、高速に再

間隔ベースの検索edit

これらのアプローチは、グリッドではなく構成空間全体を覆う舗装を生成することを除いて、グリッドベースの検索アプローチに似ています。 舗装は、X−≤Cfree≤X+となるような箱で作られた二つの部分舗装X−、X+に分解されます。 Cfreeを特徴付けることは、集合反転問題を解くための量である。 したがって、区間解析は、保証された囲いを持つためにcfreeを線形不等式で記述できない場合に使用することができます。

ロボットはX−内で自由に移動することができ、X+外に出ることはできません。 両方のサブパヴィングに対して、隣接グラフが構築され、DijkstraやA*などのアルゴリズムを使用してパスを見つけることができます。 パスがX−で実行可能な場合、Cfreeでも実行可能です。 ある初期設定から目標までのパスがX+に存在しない場合、Cfreeには実現可能なパスが存在しないことが保証されます。 グリッドベースのアプローチについては，生成されるボックスの数が構成空間の次元に対して指数関数的に増加するという事実のために，区間アプローチは高次元問題には不適切である。

図は、二つの自由度を持つフックが二つの水平の小さなセグメントを避けて左から右に移動しなければならない右の三つの図によって提供されています。

区間解析を用いた部分値による分解はまた，連結成分の数を数えるなどのＣｆｒｅｅのトポロジーを特徴付けることを可能にする。

幾何学的アルゴリズム

多角形の障害物間の点ロボット

• 可視性グラフ
• セル分解

障害物間のオブジェクトの翻訳

• ミンコフスキー和

建物の外への道を見つける

• 最も遠いレイトレース

現在の位置の周りの光線の束が壁に当たっていると仮定すると、ロボットはドアが識別されない限り、最長の光線の方向に移動します。 このようなアルゴリズムは、建物からの緊急出口のモデル化に使用されました。

人工ポテンシャルフィールド編集

一つのアプローチは、目標への誘引と障害物からの反発を組み合わせたポテンシャルフィールド内のポイントとしてロボットの構成を扱うことである。 結果の軌跡がパスとして出力されます。 このアプローチは，軌道がほとんど計算されずに生成されるという利点を有する。 しかし、それらは潜在的な場の局所的な最小値に閉じ込められ、経路を見つけることができないか、または最適でない経路を見つけることができる。 人工ポテンシャル場は静電ポテンシャル場（ロボットを点電荷のように扱う）と同様の連続方程式として扱うことができ、場を通る運動は一連の言語的規則を用いて離散化することができる。ナビゲーション関数または確率的ナビゲーション関数は、目標点以外の最小点を持たないという品質を有する人工ポテンシャル関数の一種である。

サンプリングベースのアルゴリズム編集

サンプリングベースのアルゴリズムは、サンプリングされた構成のロードマップで構成空間を表します。基本的なアルゴリズムは、CでN個の構成をサンプリングし、マイルストーンとして使用するCfreeでそれらを保持します。 次に、線分PQが完全にCfree内にある場合、二つのマイルストーンPとQを接続するロードマップが構築されます。 ここでも、衝突検出は、Cfreeへの包含をテストするために使用されます。 SとGを接続するパスを見つけるために、それらがロードマップに追加されます。 ロードマップ内のパスがSとGをリンクしている場合、プランナーは成功し、そのパスを返します。 そうでない場合、理由は決定的ではありません。Cfreeにパスがないか、プランナーが十分なマイルストーンをサンプリングしませんでした。

これらのアルゴリズムは、組み合わせアルゴリズムとは異なり、それらの実行時間はCの次元に（明示的に）指数関数的に依存しないため、高次元配置空間 それらは確率的に完全であり、より多くの時間が費やされるにつれて解が生成される確率が1に近づくことを意味する。 しかし、解決策が存在しないかどうかを判断することはできません。

Cfreeの基本的な可視性条件を考えると、構成数Nが高くなるにつれて、上記のアルゴリズムが解を見つける確率は指数関数的に1に近づくことが証明されている。 可視性はCの次元に明示的に依存しない;”よい”可視性の高次元空間または”悪い”可視性の低次元空間を持つことは可能である。 サンプルベースの方法の実験的成功は、最も一般的に見られる空間が良好な可視性を有することを示唆している。

この基本的なスキームには多くの変種があります:

• 一般的には、すべてのペアではなく、近くのマイルストーンのペア間のセグメントのみをテストする方がはるかに高速です。
• 不均一なサンプリング分布は、ロードマップの接続性を向上させる領域により多くのマイルストーンを配置しようとします。
• 準ランダムサンプルは、通常、擬似ランダムサンプルよりも構成空間の被覆が優れていますが、最近の研究では、ランダム性の源の効果はサンプリング分布の効果と比較して最小限であると主張しています。
• は、いくつかの局所提案分布を持つ方向性マルコフ連鎖モンテカルロランダムウォークを実行することにより、局所サンプリングを採用しています。
• カーブした目の光景を許可することにより、特定の問題を解決するために必要なマイルストーンの数を大幅に減らすことができます（例えば、二つのマイルストー
• 一つまたはいくつかの計画クエリだけが必要な場合、スペース全体のロードマップを常に構築する必要はありません。 この場合は、通常、ツリー成長バリアントの方が高速です(単一クエリ計画)。 ロードマップは、同じスペースで多くのクエリを実行する場合にも役立ちます(マルチクエリ計画)

注目すべきアルゴリズムのリスト編集

• A*
• D*
• 急速に探索するランダムツリー
• 確率ロードマップ