一、需求背景
2021 年 4 月 17 日，在一個(gè) VR/AR 地圖導(dǎo)航相關(guān)的項(xiàng)目中，需要實(shí)現(xiàn)兩地之間的路徑導(dǎo)航，這里路徑搜索使用到了 RRT 算法，由于之前對(duì)這一算法完全不夠了解，對(duì)其進(jìn)行學(xué)習(xí)
二、RRT 算法簡(jiǎn)介
RRT 全稱為：Rapid-exploration Random Tree，意為快速隨機(jī)搜索樹(shù)
三、RRT 算法優(yōu)劣分析
3.1 RRT 算法的優(yōu)勢(shì)
RRT 最大的優(yōu)勢(shì)是快速和隨機(jī)，能夠應(yīng)對(duì)多種復(fù)雜場(chǎng)景
圖 3.1 RRT 算法對(duì)特殊場(chǎng)景的處理
3.2 RRT 算法的不足
RRT 算法不能得到最優(yōu)路徑，如上圖，可以發(fā)現(xiàn)，該條路徑并不是起點(diǎn)和終點(diǎn)的最優(yōu)路徑
RRT 算法對(duì)于狹窄的通道，往往難以突破，需要非常大的時(shí)間開(kāi)銷，這是 RRT 算法較大的瓶頸所在
圖 3.2 RRT 算法對(duì)于狹窄通道的性能瓶頸體現(xiàn)
四、RRT 算法優(yōu)化
4.1 RRT* 算法
RRT* 算法重點(diǎn)對(duì)最優(yōu)路徑進(jìn)行了優(yōu)化。
在新生成的隨機(jī)節(jié)點(diǎn) X(rand) 附近，查找 X(parent)，不再是簡(jiǎn)單的以距離 X(rand) 最近為準(zhǔn)則，而是選擇距離 X(init) 最近為準(zhǔn)則，這樣可以得到比 RRT 算法更加優(yōu)化的路徑
