基于rrt的運動規(guī)劃算法綜述

1、基于 基于 RRT 的運動規(guī)劃 的運動規(guī)劃算法綜述 算法綜述 1.介紹 介紹 在過去的十多年中， 機器人的運動規(guī)劃問題已經(jīng)收到了大量的關(guān)注， 因為機器人開始成為現(xiàn)代工業(yè)和日常生活的重要組成部分。 最早的運動規(guī)劃的問題只是考慮如何移動一架鋼琴從一個房間到另一個房間而沒有碰撞任何物體。 早期的算法則關(guān)注研究一個最完備的運動規(guī)劃算法（完備性指如果存在這么一條規(guī)劃的路徑，那么算法一定能夠在有限時間找到它） ，例如用一個多邊形表示機器人， 其他的

2、多邊形表示障礙物體， 然后轉(zhuǎn)化為一個代數(shù)問題去求解。但是這些算法遇到了計算的復(fù)雜性問題，他們有一個指數(shù)時間的復(fù)雜度。在 1979 年，Reif 則證明了鋼琴搬運工問題的運動規(guī)劃是一個 PSPACE-hard 問題[1]。所以這種完備的規(guī)劃算法無法應(yīng)用在實際中。 在實際應(yīng)用中的運動規(guī)劃算法有胞分法[2]，勢場法[3]，路徑圖法[4]等。這些算法在參數(shù)設(shè)置的比較好的時候， 可以保證規(guī)劃的完備性， 在復(fù)雜環(huán)境中也可以保證花費的時間上限。然而，

3、這些算法在實際應(yīng)用中有許多缺點。例如在高維空間中這些算法就無法使用， 像胞分法會使得計算量過大。勢場法會陷入局部極小值，導(dǎo)致規(guī)劃失敗[5],[6]。 基于采樣的運動規(guī)劃算法是最近十幾年提出的一種算法，并且已經(jīng)吸引了極大的關(guān)注。概括的講， 基于采樣的運動規(guī)劃算法一般是連接一系列從無障礙的空間中隨機采樣的點， 試圖建立一條從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。 與最完備的運動規(guī)劃算法相反， 基于采樣的方法通過避免在狀態(tài)空間中顯式地構(gòu)造障礙物來提供大量

4、的計算節(jié)省。 即使這些算法沒有實現(xiàn)完整性， 但是它們是概率完備， 這意味著規(guī)劃算法不能返回解的概率隨著樣本的數(shù)量趨近無窮而衰減到零[7]，并且這個下降速率是指數(shù)型的。 快速擴展隨機樹(Rapidly-exploring Random Trees，RRT)算法，是近十幾年得到廣泛發(fā)展與應(yīng)用的基于采樣的運動規(guī)劃算法，它由美國愛荷華州立大學(xué)的 Steven M. LaValle 教授在1998 年提出，他一直從事 RRT 算法的改進和應(yīng)用研究

5、，他的相關(guān)工作奠定了 RRT 算法的基礎(chǔ)。 RRT 算法是一種在多維空間中有效率的規(guī)劃方法。 原始的 RRT 算法是通過一個初始點作為根節(jié)點，通過隨機采樣，增加葉子節(jié)點的方式，生成一個隨機擴展樹，當(dāng)隨機樹中的葉子節(jié)點包含了目標(biāo)點或進入了目標(biāo)區(qū)域， 便可以在隨機樹中找到一條由樹節(jié)點組成的從初始點到目標(biāo)點的路徑。 快速擴展隨機樹（RRT）也是一種數(shù)據(jù)結(jié)構(gòu)和算法，其設(shè)計用途是用來有效搜索高維非凸空間，可應(yīng)用于路徑規(guī)劃、虛擬現(xiàn)實等研究。RRT

6、是一種基于概率采樣的搜索方法，它采用一種特殊的增量方式進行構(gòu)造， 這種方式能迅速縮短一個隨機狀態(tài)點與樹的期望距離。 該方法的特點是能夠快速有效的搜索高維空間， 通過狀態(tài)空間的隨機采樣點， 把搜索導(dǎo)向空白區(qū)域， 從而尋找到一條從起始點到目標(biāo)點的規(guī)劃路徑。 它通過對狀態(tài)空間中的采樣點進行碰撞檢測，避免了對空間的建模，能夠有效的解決高維空間和復(fù)雜約束的路徑規(guī)劃問題。RRT算法適合解決多自由度機器人在復(fù)雜環(huán)境下和動態(tài)環(huán)境中的路徑規(guī)劃問題[8]。

7、與其他的隨機路徑規(guī)劃方法相比，RRT 算法更適用于非完整約束和多自由度的系統(tǒng)中[9]。 相比于最原始的 RRT 算法的一些缺點，又提出了許多改進的 RRT 算法，例如： （1）基于概率 P 的 RRT 為了加快隨機樹到達(dá)目標(biāo)點的速度，簡單的改進方法是：在隨機樹每次的生長過程中，根據(jù)隨機概率 （0.0 到 1.0 的隨機值 p） 來選擇生長方向是目標(biāo)點還是隨機點。 2001 年， LaValle定義 定義 2.7 路徑長度（ 路徑長度（p

8、ath cost）定義𝑝𝑐: ∑𝐶𝑓𝑟𝑒𝑒 → 𝑅>0為一條路徑的非負(fù)長度?！?#119862;𝑓𝑟𝑒𝑒表示所有自由空間中的路徑集合。 2.3 運動規(guī)劃的基本定義 運動規(guī)劃的基本定義 用 C-空間的思路，運動規(guī)劃問題在概念上變得非常簡單：任務(wù)

9、是在中尋找一條從起始位姿到目標(biāo)位姿的路徑。運動規(guī)劃問題的示意圖如圖 2.1 所示,圖中整個水滴表示位姿空間𝐶 = 𝐶 𝑓𝑟𝑒𝑒 ? 𝐶𝑜𝑏𝑠. 圖 2.1 運動規(guī)劃示意圖 有了上述概念，C-空間中的運動規(guī)劃問題可描述如下： （1）定義一個工作空間 W； （2）定義 W 中的障礙物

10、區(qū)域 O 和機器人 A； （3）所有可能的機器人位姿構(gòu)成 C-空間，并且劃分為 Cobs 和 Cfree； （4）指定機器人初始位姿 qinit 和目標(biāo)目標(biāo)位姿 qgoal； （5）可行規(guī)劃（Feasible planning）一個完整的算法必須計算一條連續(xù)的路徑τ: [0,1] →𝐶 𝑓𝑟𝑒𝑒，使得τ(0) = 𝑞𝑖

11、9899;𝑖𝑡，τ(1) = 𝑞𝑔𝑜𝑎𝑙或者正確報告這樣的路徑不存在。 （6）最優(yōu)規(guī)劃（Optimal planning）在所有的可行的規(guī)劃的路徑里面花費代價最少的一條路徑𝑚𝑖𝑛𝜏∈∑𝐶𝑓𝑟𝑒

12、9890;𝑝𝑐(𝜏)，或者報告這樣的路徑不存在。 3.算法 算法 在介紹 RRT 算法之前，先說明一下路徑的表示方法。我們用一個有向圖來表示路徑 G=（V,E） ，那么一條可行的路徑就是一個頂點的序列(𝑣1 , 𝑣2 , 𝑣3 , … , 𝑣𝑛),𝑣1 = 𝑞𝑖&

13、#119899;𝑖𝑡 , 𝑣𝑛 =𝑞𝑔𝑜𝑎𝑙.同時(𝑣𝑖 , 𝑣𝑖+1) ∈ 𝐸, 1 ≤ 𝑖 ≤ 𝑛 ? 1表示邊。 這樣子問題就變成了使用采樣到的點來擴展圖 G，使之能找到一條從初

14、始節(jié)點到達(dá)目標(biāo)節(jié)點的路徑。 3.1 原始的 原始的 RRT 算法 算法 算法 1：RRT 算法主體部分 1. 𝑉 ← {𝑞𝑖𝑛𝑖𝑡};𝐸 ← ?; 𝑖 ← 0; 2. 𝐰𝐡𝐢𝐥𝐞 𝑖 < 𝑁 &

15、#119837;𝐨 3. 𝐺 ← (𝑉, 𝐸); 4. 𝑞𝑟𝑎𝑛𝑑 ← Sample(𝑖); 𝑖 ← 𝑖 + 1; 5. (𝑉, 𝐸) ← Extend(⻒