確率的ロードマップ

確率的ロードマップ[ ^1]プランナーはロボット工学における動作計画アルゴリズムであり、衝突を回避しながらロボットの開始構成と目標構成の間の経路を決定する問題を解決します。

PRM の基本的な考え方は、ロボットの構成空間からランダムなサンプルを取得し、それらが自由空間内にあるかどうかをテストし、ローカル プランナーを使用してこれらの構成を他の近くの構成に接続しようとすることです。開始構成と目標構成が追加され、結果のグラフにグラフ検索アルゴリズムが適用され、開始構成と目標構成間のパスが決定されます。

確率的ロードマップ プランナーは、構築フェーズとクエリ フェーズの 2 つのフェーズで構成されます。構築フェーズでは、環境内で実行できる動作を近似したロードマップ (グラフ) が構築されます。まず、ランダム構成が作成されます。次に、いくつかの近傍 (通常はk 個の最近傍または事前に決定された距離未満のすべての近傍) に接続されます。ロードマップが十分に密になるまで、構成と接続がグラフに追加されます。クエリ フェーズでは、開始構成と目標構成がグラフに接続され、ダイクストラの最短パスクエリによってパスが取得されます。

自由空間の形状に関する比較的弱い条件が与えられれば、PRM は確率的に完全であることが証明できます。つまり、サンプルされたポイントの数が無制限に増加すると、アルゴリズムがパス (存在する場合) を見つけられない確率は 0 に近づきます。収束率は自由空間の特定の可視性プロパティに依存します。可視性はローカル プランナーによって決定されます。大まかに言えば、各ポイントが空間の大部分を「見る」ことができ、また空間の各サブセットの大部分がその補集合の大部分を「見る」ことができる場合、プランナーはパスをすばやく見つけます。

PRM法の発明者はLydia E. Kavrakiです。^{[2] [3]}基本的なPRM法には多くのバリエーションがあり、中には非常に洗練されたものもあり、より高速なパフォーマンスを実現するためにサンプリング戦略と接続戦略を変えています。議論については、 Geraerts & Overmars (2002) ^{[4]を参照してください。}