MyEnigma

とあるエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

Probabilistic Road Map(PRM) plannerによる経路生成とPythonサンプルコード

PRM

目次

はじめに

今回の記事では、

ロボットのパスプランニングの代表的なアルゴリズムの一つである。

Probabilistic Road Map (PRM) plannerについて概要と、

Pythonによるサンプルコードを紹介したいと思います。

 

PRM planner

PRM plannerでは下記のステップでパスを生成します。

1. Configuration Space (C-Space)の作成

PRMではまず初めに、ロボットの大きさと

周辺環境のマップからC-Spaceを作成します。

 

Configuration Spaceとは、Motion Planningにおいて、

ロボットの大きさや形状の分だけ、

障害物を膨張させ、ロボットを質点モデルとした時の、

衝突回避空間と、障害物空間を示した空間のことです。

f:id:meison_amsl:20171219065741p:plain

 

2. C-Space内にランダムにサンプリングする

コースのノードとなる点をC-Space内に

ランダムにサンプリングします。

 

この点はコースのPRM Plannerにおける

ノード点になります。

 

通常はある指定された点数分だけサンプリングし、

C-Space内において、

衝突しない場所にサンプリングされる必要があります。

また、スタート地点とゴール地点の両方の点も、

このサンプリング点に含まれる必要があります。

3. 隣接点を接続する

サンプリングされた点を隣接点同士接続し、

グラフ構造を生成します。

 

このステップでは、ある指定された数だけ、

近傍点からエッジを生成する方法と、

ある指定された範囲内の点をすべてエッジで結ぶ方法があります。

 

また、これらのエッジはC-Spaceにおいて、

衝突しないことを確認する必要があります。

4. ダイクストラ法による最短距離探索

最後にPRM Plannerではダイクストラ法を使うことで、

前のステップで生成されたグラフ構造の中で、

最短距離のコースを探索します。

 

ダイクストラ法に関しては、

下記を参照ください。

myenigma.hatenablog.com

 

以上がPRM Plannerの代表的なコース生成方法です。  

Pythonサンプルコード

下記のGitHubリポジトリに

PRM plannerのサンプルコードを公開しています。

github.com

 

上記のコードを実行すると、

下記のアニメーションのように、

PRM plannerを使って経路探索を実施する

シミュレーションを実施することができます。

PRM

このアニメーションにおいて、

青い点はサンプリングされた点であり、

シアンのバツ印はダイクストラ法によって探索された点、

そして、最後の赤い線は

PRM Plannerによって探索されたパスです。

参考資料

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

myenigma.hatenablog.com

 

MyEnigma Supporters

もしこの記事が参考になり、

ブログをサポートしたいと思われた方は、

こちらからよろしくお願いします。

myenigma.hatenablog.com