RRT算法简介
聲明：本文為轉載內容非原創，來源會在文末聲明，絕無冒犯之意，只為一時復習之方便，侵權必刪！
感謝原作者寫出如此優秀的博文，讓我對RRT算法有個大致的理解。
對RRT算法感興趣，是因為我對它不僅在二維平面上適用，在高維空間也能使用而感到心動，最近比較忙，下周或者什么時候要要用代碼親自實現一下。
路徑規劃都有哪些方法呢？比較流行的有：圖搜索、勢場法、RRT 等等。?
RRT（快速探索隨機樹） 是一種通用的方法，不管什么機器人類型、不管自由度是多少、不管約束有多復雜都能用。而且它的原理很簡單，這是它在機器人領域流行的主要原因之一。不過它的缺點也很明顯，它得到的路徑一般質量都不是很好，例如可能包含棱角，不夠光滑，通常也遠離最優路徑。
RRT 能在眾多的規劃方法中脫穎而出，它到底厲害在哪里呢？?
天下武功唯快不破，“快”是 RRT 的一大優點。RRT 的思想是快速擴張一群像樹一樣的路徑以探索（填充）空間的大部分區域，伺機找到可行的路徑。之所以選擇“樹”是因為它能夠探索空間。我們知道，陽光幾乎是樹木唯一的能量來源。為了最大程度地利用陽光，樹木要用盡量少的樹枝占據盡量多的空間。當然了，能探索空間的不一定非得是樹，比如Peano曲線也可以做到，而且要多密有多密，如上圖左所示的例子。雖然像Peano曲線這樣的單條連續曲線也能探索空間，但是它太“確定”了。在搜索軌跡的時候我們可不知道出路應該在哪里，如果不在“確定”的搜索方向上，我們怎么找也找不到（找到的概率是0）。這時“隨機”的好處就體現出來了，雖然不知道出路在哪里，但是通過隨機的反復試探還是能碰對的，而且碰對的概率隨著試探次數的增多越來越大，就像買彩票一樣，買的數量越多中獎的概率越大（RRT名字中“隨機”的意思）。可是隨機試探也講究策略，如果我們從樹中隨機取一個點，然后向著隨機的方向生長，那么結果是什么樣的呢？見上圖右。可以看到，同樣是隨機樹，但是這棵樹并沒很好地探索空間，它一直在起點（紅點）附近打轉。這可不好，我們希望樹盡量經濟地、均勻地探索空間，不要過度探索一個地方，更不能漏掉大部分地方。這樣的一棵樹怎么構造呢？?
RRT 的基本步驟是：?
1. 起點作為一顆種子，從它開始生長枝丫；?
2. 在機器人的“構型”空間中，生成一個隨機點?A；?
3. 在樹上找到距離?AA?最近的那個點，記為?B?吧；?
4.?B?朝著?A的方向生長，如果沒有碰到障礙物就把生長后的樹枝和端點添加到樹上，返回 2；?
隨機點一般是均勻分布的，所以沒有障礙物時樹會近似均勻地向各個方向生長，這樣可以快速探索空間（RRT名字中“快速探索”的意思）。當然如果你事先掌握了最有可能發現路徑的區域信息，可以集中兵力重點探索這個區域，這時就不宜用均勻分布了。?
RRT 的一個弱點是難以在有狹窄通道的環境找到路徑。因為狹窄通道面積小，被碰到的概率低，找到路徑需要的時間要看運氣了。下圖展示的例子是 RRT 應對一個人為制作的很短的狹窄通道，有時RRT很快就找到了出路，有時則一直被困在障礙物里面。?
RRT探索空間的能力還是不錯的，例如下圖左所示的例子，障礙物多而且雜亂（借助 Mathematica 本身具有的強大函數庫，實現這個例子所需的所有代碼應該不會超過30行）。還有沒有環境能難住RRT呢？下圖右所示的迷宮對RRT就是個挑戰。這個時候空間被分割得非常嚴重，RRT顯得有些力不從心了，可見隨機策略不是什么時候都有效的。?
“隨機”使得RRT有很強的探索能力。但是成也蕭何敗也蕭何，“隨機”也導致 RRT 很盲目，像個無頭蒼蠅一樣到處亂撞。如果機器人對環境一無所知，那么采用隨機的策略可以接受。可實際情況是，機器人對于它的工作環境多多少少是知道一些的（即使不是完全知道）。我的博客一直強調信息對于機器人的重要性。這些已知的信息就可以用來改進算法。一個改進的辦法就是給它一雙“慧眼”：在勢場法中，勢函數攜帶了障礙物和目標的信息，如果能把這個信息告訴 RRT，讓它在探索空間時有傾向地沿著勢場的方向前進會更好。這樣，RRT 出色的探索能力剛好可以彌補勢場法容易陷入局部極小值的缺點。
將RRT方法用在機械臂上的效果如下圖所示（綠色表示目標狀態）。我設置了4個障礙物（其中一個是大地），這對機械臂是個小小的挑戰。由于我們生活在三維空間，沒辦法看到六維關節空間，所以我把六維關節空間拆成了兩個三維空間，分別對應前三個關節和后三個關節（嚴格來說，六維轉動關節空間不是一個歐式空間，它是個流形，不過這里我們不必糾結這個差別）：?
轉載來源：
基于Mathematica的機器人仿真環境（機械臂篇） - CSDN博客
https://blog.csdn.net/robinvista/article/details/70231205
總結
- 上一篇： SAS入门 新手必看
- 下一篇： Java制作数独小游戏