目次
はじめに
今回の記事では、
ロボットのパスプランニングの代表的なアルゴリズムの一つである。
Probabilistic Road Map (PRM) plannerについて概要と、
Pythonによるサンプルコードを紹介したいと思います。
PRM planner
PRM plannerでは下記のステップでパスを生成します。
1. Configuration Space (C-Space)の作成
PRMではまず初めに、ロボットの大きさと
周辺環境のマップからC-Spaceを作成します。
Configuration Spaceとは、Motion Planningにおいて、
ロボットの大きさや形状の分だけ、
障害物を膨張させ、ロボットを質点モデルとした時の、
衝突回避空間と、障害物空間を示した空間のことです。
2. C-Space内にランダムにサンプリングする
コースのノードとなる点をC-Space内に
ランダムにサンプリングします。
この点はコースのPRM Plannerにおける
ノード点になります。
通常はある指定された点数分だけサンプリングし、
C-Space内において、
衝突しない場所にサンプリングされる必要があります。
また、スタート地点とゴール地点の両方の点も、
このサンプリング点に含まれる必要があります。
3. 隣接点を接続する
サンプリングされた点を隣接点同士接続し、
グラフ構造を生成します。
このステップでは、ある指定された数だけ、
近傍点からエッジを生成する方法と、
ある指定された範囲内の点をすべてエッジで結ぶ方法があります。
また、これらのエッジはC-Spaceにおいて、
衝突しないことを確認する必要があります。
4. ダイクストラ法による最短距離探索
最後にPRM Plannerではダイクストラ法を使うことで、
前のステップで生成されたグラフ構造の中で、
最短距離のコースを探索します。
ダイクストラ法に関しては、
下記を参照ください。
以上がPRM Plannerの代表的なコース生成方法です。
Pythonサンプルコード
下記のGitHubリポジトリに
PRM plannerのサンプルコードを公開しています。
上記のコードを実行すると、
下記のアニメーションのように、
PRM plannerを使って経路探索を実施する
シミュレーションを実施することができます。
このアニメーションにおいて、
青い点はサンプリングされた点であり、
シアンのバツ印はダイクストラ法によって探索された点、
そして、最後の赤い線は
PRM Plannerによって探索されたパスです。
参考資料
MyEnigma Supporters
もしこの記事が参考になり、
ブログをサポートしたいと思われた方は、
こちらからよろしくお願いします。
