Probabilistic Roadmap (PRM)

Probabilistic Roadmap (PRM) は、フリー スペースと占有スペースに基づく、指定したマップ内で取り得るパスのネットワーク グラフです。mobileRobotPRM オブジェクトはノードをランダムに生成し、PRM アルゴリズムのパラメーターに基づいてこれらのノード間に接続を作成します。ノードは、Map に指定されている障害物の位置に基づき、指定された ConnectionDistance で接続されます。ノード数 NumNodes をカスタマイズして、マップの複雑度と、最も効率的なパスを探す必要性に応じて調整することができます。PRM アルゴリズムは接続されたノードのネットワークを使用して、開始位置から終了位置まで障害物のないパスを探します。環境を通るパスを効果的に計画するには、NumNodes プロパティと ConnectionDistance プロパティを調整します。

mobileRobotPRM クラスの作成または更新を行うと、ノード位置がランダムに生成されるため、複数回の反復の間で最終パスに影響する場合があります。このノード選択は、最初に Map を指定したとき、パラメーターを変更したとき、または update を呼び出したときに発生します。同じノード配置で一貫した結果を得るには、rng を使用して、乱数発生の状態を保存してください。rng を使用した例については、接続距離の調整を参照してください。

ノード数の調整

mobileRobotPRM オブジェクトの NumNodes プロパティを使用して、アルゴリズムを調整します。NumNodes は、マップに配置する点 (ノード) の数を指定します。アルゴリズムはこの点を使用してロードマップを生成します。アルゴリズムは、ConnectionDistance プロパティを距離のしきい値として使用して、点と点の間の直接パスをブロックする障害物のないすべての点同士を接続します。

ノードの数を増やすと、実行可能なパスが増え、パスの効率が上がる場合があります。しかし、複雑度が増すと計算時間が長くなります。マップの良好なカバレッジを得るためには、大量のノードが必要になる場合があります。ノードの配置はランダムなので、マップの一部の領域には、マップの残りに接続するために十分なノードがない場合があります。この例では、ロードマップ内に多数のノードと少数のノードを作成します。

マップ ファイルを logical 行列 simpleMaps として読み込み、占有グリッドを作成します。

load exampleMaps.mat
map = binaryOccupancyMap(simpleMap,2);

50 個のノードがあるシンプルなロードマップを作成します。

prmSimple = mobileRobotPRM(map,50);
show(prmSimple)

250 個のノードがある密なロードマップを作成します。

prmComplex = mobileRobotPRM(map,250);
show(prmComplex)

追加のノードによって複雑度は増しますが、パスを改善するためのオプションがより多く得られます。これら 2 つのマップを基に、PRM アルゴリズムを使用してパスを計算し、効果を確認できます。

シンプルなパスを計算します。

startLocation = [2 1];
endLocation = [12 10];
path = findpath(prmSimple,startLocation,endLocation);
show(prmSimple)

複雑なパスを計算します。

path = findpath(prmComplex, startLocation, endLocation);
show(prmComplex)

ノードを増やすと直接パスが増えますが、実行可能なパスを探すための計算時間が長くなります。点がランダムに配置されているので、パスは必ずしも直接的または効率的であるとは限りません。少数のノードを使用した場合、図示したよりもパスが悪くなることがあります。場合によっては、完全なパスが見つからなくなる可能性もあります。

接続距離の調整

PRM オブジェクトの ConnectionDistance プロパティを使用してアルゴリズムを調整します。ConnectionDistance は、ロードマップ内で接続されている点の上限しきい値です。各ノードは、この接続距離の範囲内で、障害物が間に存在しないすべてのノードに接続されます。接続距離を短くすることで、接続の数を制限し、計算時間を削減してマップを単純化できます。しかし、距離を短くすると、障害物がまったく存在しないパスを見つけるために使用可能なパスの数が制限されます。単純なマップで作業する場合、接続距離を長く、ノード数を少なくすると、効率を向上させることができます。障害物の多い複雑なマップでは、ノード数を増やして接続距離を短くすると、解が見つかる可能性が高くなります。

マップを logical 行列 simpleMap として読み込み、占有グリッドを作成します。

load exampleMaps.mat
map = binaryOccupancyMap(simpleMap,2);

100 個のノードをもつロードマップを作成し、パスを計算します。既定の ConnectionDistance は inf に設定されています。関数 rng を使用して、乱数発生設定を保存します。保存した設定によって、同じ点を再現し、ConnectionDistance の変更による影響を確認することができます。

rngState = rng;
prm = mobileRobotPRM(map,100);
startLocation = [2 1];
endLocation = [12 10];
path = findpath(prm,startLocation,endLocation);
show(prm)

PRM で同じノードを使用するには、乱数発生設定を再度読み込みます。ConnectionDistance を 2 m まで短くします。計算されたパスを表示します。

rng(rngState);
prm.ConnectionDistance = 2;
path = findpath(prm,startLocation,endLocation);
show(prm)

PRM の作成または更新

mobileRobotPRM オブジェクトを使用してプロパティを変更するときには、新しい関数呼び出しを行うたびに、オブジェクトによってロードマップの点と接続の再計算がトリガーされます。マップの再計算は計算量が多くなることがあるため、同じロードマップを再利用できます。そのためには、異なる開始位置と終了位置を指定して findpath を呼び出します。

マップ simpleMap を .mat ファイルから logical 行列として読み込んで、占有グリッドを作成します。

load('exampleMaps.mat')
map = binaryOccupancyMap(simpleMap,2);

ロードマップを作成します。ノードはランダムに配置されるため、ノードと接続の表示は下図と異なる場合があります。

prm = mobileRobotPRM(map,100);
show(prm)

update を呼び出すかパラメーターを変更して、ノードと接続を更新します。

update(prm)
show(prm)

PRM アルゴリズムがノード配置を再計算して、新しいノードのネットワークを生成します。

参照

[1] Kavraki, L.E., P. Svestka, J.-C. Latombe, and M.H. Overmars. "Probabilistic roadmaps for path planning in high-dimensional configuration spaces," IEEE Transactions on Robotics and Automation. Vol. 12, No. 4, Aug 1996 pp. 566—580.

参考

mobileRobotPRM | findpath