Probabilistic Roadmap

• 別名: PRM, probabilistic roadmap method
• カテゴリ: Planning & manipulation › Motion planning
• タグ: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

ランダムな衝突のないコンフィギュレーションとそれらを結ぶ実行可能な経路からなる再利用可能なグラフを構築し、グラフ探索によって計画の問い合わせに答える、サンプリングベースの動作プランナー。

定義

確率的ロードマップ（Probabilistic Roadmap、PRM）は、1996 年に Kavraki、Švestka、Latombe、Overmars によって提案されたサンプリングベースの動作計画手法である。PRM は要求のたびにコンフィギュレーション空間を一から探索するのではなく、まずロボットの自由空間の連結性を捉えたグラフ、すなわちロードマップを構築し、そのグラフを使って任意の数のスタートからゴールへの問い合わせに答える。

計画は二つのフェーズからなる。構築フェーズでは、プランナーがロボットのコンフィギュレーションをランダムにサンプリングし、衝突のないものをノードとして残し、単純なローカルプランナーで各ノードを近くのノードとつなごうとする。ローカルプランナーは通常、コンフィギュレーション空間内の直線で、細かい間隔で衝突チェックを行う。接続に成功したものがエッジになる。問い合わせフェーズでは、スタートとゴールのコンフィギュレーションをロードマップにつなぎ、Dijkstra 法や A* などのグラフ探索でその中の経路を見つける。

高価なロードマップ構築が一度で済むため、PRM は、環境が静的でロボットが同じ空間で多くの動作を計画しなければならない多重問い合わせ問題に適している。PRM は確率的完全性を持つ。経路が存在するなら、サンプル数が増えるにつれて、ロードマップが経路を含む確率は 1 に近づく。

主な弱点は狭い通路である。一様なランダムサンプルが自由空間の細い領域に入ることはまれなので、実際にはつながっている領域をロードマップがつなげないことがある。これに対処するため、障害物の境界付近でサンプリングするなど、偏りを持たせたサンプリング戦略が開発された。PRM* は、ロードマップが漸近最適になるように接続半径を選ぶ派生手法である。

重要な理由

PRM は、厳密な手法では扱いきれない多自由度のロボットに対して、ランダムサンプリングによって動作計画を実用的にできることを示した。そのロードマップの考え方は、固定された産業用セルのように、ロボットが同じ環境で繰り返し作業する場合には今も有用である。

主な用途

• 固定されたワークセル内のロボットアームの多重問い合わせ動作計画
• 静的な地図上での移動ロボットの経路計画
• ヒューマノイドや双腕ロボットなど高自由度システムの計画
• サンプリングベース計画の教育とベンチマーク

実際の使われ方

チームは通常 OMPL を通じて PRM を使い、アームの計画では MoveIt 経由で使うことが多い。そこでは PRM と PRM* が RRT-Connect のような木ベースのプランナーと並んでいる。ロードマップは保存して再利用できるため、PRM は、アームが同じ治具のまわりで多くの姿勢の間を動く固定されたワークセルに適している。ロードマップはオフラインで構築して実行時に問い合わせ、衝突チェックは物体が動いた可能性のある箇所でだけやり直す。エンジニアはサンプル数と接続半径を調整し、ロードマップ内の連結していない成分に注意する。それは通常、より多くの、あるいはより的を絞ったサンプルが必要な狭い通路があることを示している。

よくある誤解

• PRM は経路が存在すれば必ず見つける — 確率的に完全であるにすぎないため、その保証が成り立つのはサンプル数が無限大の極限においてだけである
• PRM は主に 2D 地図向けである — 主な用途は、アームの関節空間のような高次元のコンフィギュレーション空間である
• ロードマップはいつまでも有効である — 障害物が動いた場合は、影響を受けたエッジを再チェックするか、ロードマップを作り直さなければならない

知っておくべき人

• 動作計画のエンジニア
• 産業用ロボットセルのインテグレータ
• マニピュレーションの研究者
• サンプリングベース計画を学ぶロボティクスの学生

関連技術

• OMPL
• MoveIt
• RRT
• PRM*
• A 探索（A Search）
• コンフィギュレーション空間（Configuration Space）

関連用語

• Motion Planning
• RRT*
• Configuration Space

関連プロジェクト

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

動画

• Modern Robotics, Chapter 10.5: Sampling Methods for Motion Planning (Part 1 of 2): Northwestern Robotics