RRT：
實現(xiàn)：給定一個node_start, node_goal,隨機選擇一個node_rand，在node_list列表里選擇一個離node_random最近的點設(shè)置為node_nearest，然后沿著node_nearest朝node_random走step_length距離，找到一個node_new, 將其加入node_list。
重復(fù)上述過程直到找到一個node_new接近node_goal,然后再在得到的node_list中找到從node_start到最后一個node_new的列表就構(gòu)成了path。
優(yōu)勢：速度較快，概率完備
劣勢：通常不是最優(yōu)路徑

https://blog.csdn.net/u013528298/article/details/80546175

RRT*：
實現(xiàn)原理于RRT，基本相同，但是RRT的最優(yōu)化的版本。
1 不同：RRT會記錄每個頂點相對于其父頂點移動的距離。 這稱為頂點的cost()。 在圖中找到最近的節(jié)點后，將檢查距新節(jié)點固定半徑內(nèi)的頂點鄰域。 如果找到比近端節(jié)點更便宜的 cost() 節(jié)點，則更便宜的節(jié)點替換近端節(jié)點。
2 不同：RRT樹的重新布線，當新的頂點連接到更便宜的節(jié)點后，再次檢查新節(jié)點固定半徑內(nèi)的頂點，如果將其連接到新的頂點后（即將新的節(jié)點當作父節(jié)點）會使得其cost降低，則將新節(jié)點當作此節(jié)點的父節(jié)點連接上去。

Dijkstra：
實現(xiàn)：從綠色start開始對每個柵格進行遍歷，即對每個柵格的cost進行更新，一直迭代遍歷到黃色的goal為止，然后從goal再反向查找start即得最優(yōu)路徑。

優(yōu)勢：簡單
劣勢：環(huán)境太大的話，算法復(fù)雜度較高
https://www.guyuehome.com/5652
https://www.guyuehome.com/33665

A*算法：
實現(xiàn)：相對于Dijkstra算法，增加了每個節(jié)點到目標點的啟發(fā)函數(shù)，根據(jù)啟發(fā)函數(shù)構(gòu)建最小代價的節(jié)點。
優(yōu)勢：相對Dijkstra算法較快
劣勢：當目標較多的時候，會帶入大量重復(fù)數(shù)據(jù)和復(fù)雜的估價函數(shù)

A*算法和Dijkstra算法的比較：
Dijkstra算法計算源點到其他所有點的最短路徑長度，A關(guān)注點到點的最短路徑
Dijkstra算法的實質(zhì)是廣度優(yōu)先搜索，是一種發(fā)散式的搜索，所以空間復(fù)雜度和時間復(fù)雜度都比較高。對路徑上的當前點，A算法不但記錄其到源點的代價，還計算當前點到目標點的期望代價，是一種啟發(fā)式算法，也可以認為是一種深度優(yōu)先的算法。

PRM算法：
相較于Dijkstra算法，PRM只是采樣了一個地圖中的一堆點，來進行A*等搜索算法的路徑搜索。
優(yōu)勢：算得比較快
劣勢：概率不完備

總結(jié)

以上是生活随笔為你收集整理的RRT，RRT*，A*，Dijkstra，PRM算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。