路徑規(guī)劃之概率路線(xiàn)圖（PRM）算法

發(fā)布日期：2022/9/3 17:06:05      瀏覽量：

概率路線(xiàn)圖（Probabilistic Roadmaps）

簡(jiǎn)介

概率路線(xiàn)圖（PRM）是基于可用空間和占用空間的給定地圖內(nèi)可能路徑的網(wǎng)絡(luò)圖。概率路線(xiàn)圖法(PRM)將規(guī)劃分為兩個(gè)階段：學(xué)習(xí)階段和查詢(xún)階段。在學(xué)習(xí)階段，建立一個(gè)路線(xiàn)圖QfreeQfree；在查詢(xún)階段，利用搜索算法在路線(xiàn)圖上尋找路徑。

一個(gè)質(zhì)點(diǎn)機(jī)器人在二維歐氏空間的路線(xiàn)圖示例。

（來(lái)源：《Principles of Robot Motion: Theory, Algorithms and Implementations》Fig. 7.3）

PRM這種基于圖搜索的方法，它將連續(xù)空間轉(zhuǎn)換成離散空間，再利用A*等搜索算法在路線(xiàn)圖上尋找路徑，以提高搜索效率。這種方法能用相對(duì)少的隨機(jī)采樣點(diǎn)來(lái)找到一個(gè)解，對(duì)多數(shù)問(wèn)題而言，相對(duì)少的樣本足以覆蓋大部分可行的空間，并且找到路徑的概率為1（隨著采樣數(shù)增加，P（找到一條路徑）指數(shù)的趨向于1）。顯然，當(dāng)采樣點(diǎn)太少，或者分布不合理時(shí)，PRM算法是不完備的，但是隨著采用點(diǎn)的增加，也可以達(dá)到完備。所以PRM是概率完備且不最優(yōu)的。

其建立路線(xiàn)圖的步驟如下：

（來(lái)源：《Principles of Robot Motion: Theory, Algorithms and Implementations》）

一開(kāi)始，圖G=(V,E)G=(V,E)是空的。然后，在配置空間重復(fù)采樣。這時(shí)假定采樣是遵守均勻分布。把不碰到障礙的配置加入到路線(xiàn)圖中。一共采樣ｎｎ次。PRM路徑規(guī)劃器通過(guò)使用空閑空間中的隨機(jī)采樣節(jié)點(diǎn)并將它們彼此連接，在指定地圖的空閑空間中構(gòu)建路線(xiàn)圖。路線(xiàn)圖建立后，用戶(hù)可以在路線(xiàn)圖上查詢(xún)從指定起點(diǎn)到指定終點(diǎn)的路徑。

改進(jìn)算法

• PRM*

參考

1. 《Principles of Robot Motion: Theory, Algorithms and Implementations》7.1.
2. 《Planning Algorithms》， 5.6 Roadmap Methods for Multiple Queries.
3. https://ww2.mathworks.cn/help/robotics/ug/probabilistic-roadmaps-prm.html
4. https://www.cnblogs.com/21207-iHome/p/7209954.html
5. https://blog.csdn.net/DinnerHowe/article/details/80267062
6. Code for Robot Path Planning using Probabilistic Roadmap