基于雙采樣點的雙向RRT路徑規劃算法

閆明亮 侯光華

摘要：傳統快速擴展隨機樹（RRT）算法在生成采樣點時采用隨機擴展的策略，導致路徑的生長無方向性且路徑規劃速度較慢。針對此問題，在采樣點選取策略上采用雙采樣點的方法，同時隨機生成2個采樣點，并選取其中距離目標點較近的點作為最終采樣點，可使路徑的生長在一定程度上具有方向性，提高路徑規劃的效率。仿真試驗中，與傳統RRT和雙向RRT路徑規劃算法進行對比分析，驗證了算法的有效性。

關鍵詞：快速擴展隨機樹；雙向RRT路徑規劃；雙采樣點

中圖分類號：TP301.6文獻標志碼：A文章編號：1008-1739（2019）15-55-4

0引言

路徑規劃是指在某種環境內，按照一定的評價標準，如路徑最短或規劃時間最少等，尋找一條從起始點到目標點的無碰撞路徑[1]。

目前，一種傳統的路徑規劃算法是基于采樣的快速擴展隨機樹[2]算法。但由于在RRT的擴展過程中，采樣點的選取使用全局的均勻隨機采樣策略[3]，導致路徑搜索效率低[4]。由此提出了雙向RRT（Bi-RRT）算法，從起始點和目標點同時生成2棵RRT并進行相向擴展，加速了算法的收斂速度[5]。但節點的擴展方式仍使用在全局環境中進行均勻隨機采樣的策略，缺乏目標導向性，降低了路徑規劃效率[6]。

為解決上述方法出現的問題，提出一種基于雙采樣點的雙向RRT路徑規劃（DBi-RRT）算法，該算法在隨機點采樣策略上使用雙采樣點方法對隨機點進行采樣，減少過多無用節點擴展的同時使得隨機樹的生長具有方向性。

1雙采樣點的雙向RRT算法

1.1算……