擴展隨機樹語法

快速擴展隨機樹是一種搜尋結構，通過快速縮短搜尋結構中的結點與隨機選擇點之間期望距離的方式進行增量構造。並且最近在解決軌跡規劃和路徑規劃問題中顯示出良好套用前景。

基本介紹

• 中文名：擴展隨機樹語法
• 外文名：Extend random syntax tree
• 類型：搜尋結構
• 定義：解決不確定環境下的完整性規劃
• 套用：軌跡規劃和路勁規劃
• 套用學科：計算機原理

算法描述

20世紀90年代以來，使用隨機化方法的路徑規划算法逐漸增多，因為這種方法可以適用於不確定環境中的高維度空間，並且也曾被用來解決人工勢場法中的局部極小問題。近年來這方面研究的發展可以快速擴展隨機樹作為代表，其本質上為一種高效的數據結構，可以被用來解決不確定環境下的完整性規劃、非完整性規劃以及運動動力學的問題。

快速擴展隨機樹，簡稱RRT，是一種數據結構和算法，其設計用途是用來有效搜尋高維非凸空間，可套用於路徑規劃、虛擬現實等研究。快速擴展隨機樹採用一種特殊的增量方式進行構造，這種方式能‘迅速縮短一個隨機狀態點與樹的期望距離。快速擴展隨機樹特別適合包括障礙物和微分約束(非完整性或運動動力學)的路徑規劃問題。快速擴展隨機樹可以被視為一種處理非線性系統的技術，產生針對狀態約束的非線性系統的開環軌跡。一棵快速擴展隨機樹其實可被視為一個傾向於搜尋最大Voronoi區域的Monte-Carlo方法。因此，快速擴展隨機樹在套用於路徑規劃方面前景廣闊。

算法

算法如圖1：

圖1

算法實現

快速擴展隨機樹採用Borland公司的C++Builder5.0開發完成。並且為了快速而高效的實現算法，特別採用了C++ STL(Standard Template Library)標準模板庫技術以繼承經典的數據結構和算法，實現軟體復用，降低開發強度。在開發的過程中針對所使用的特殊的數據結構對標準快速擴展隨機樹的局部算法做了相應的改動，使得整個系統的結構更為簡潔和最佳化。