基于改進RRT算法的窄通道路徑規劃

白利征 閻鑫 齊少璞 趙守智

摘 ? 要：RRT算法是一種經典的路徑規劃算法，但對于存在窄通道的環境，其執行速度較低。本文進行了一些改進，先縮小物體找到粗略路徑，再采用雙橋測試識別路徑附近的窄通道區域，增加其中的采樣密度，并采用動態步長，使采樣步長隨區域和碰撞情況自適應調整，提高了窄通道環境中RRT算法的運行效率。

關鍵詞：快速擴展隨機樹 ?窄通道 ?動態步長 ?雙橋測試法

中圖分類號：TP24 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1674-098X（2019）11（b）-0027-02

快速擴展隨機樹（rapidly exploring random tree，簡稱RRT）算法是由美國愛荷華州立大學的Steven Lavalle教授在1998年提出的[1]，在路徑規劃中已經獲得廣泛應用。但在有窄通道的復雜環境中，由于障礙物之間距離狹小，落在窄通道中的采樣點相對較少，經典的RRT算法將難以找到路徑。

為解決窄通道環境路徑規劃的難題，國內外已有大量研究。例如Hsu D等人提出了一種橋測試法，首先正態分布生成兩個點，若這兩個點都位于障礙物中，則檢測它們的中點位置，若中點位于自由空間中則認為其處于窄通道中，通過大量的橋測試確定通道的形狀以便對其補充采樣[2]，這種方法缺點是容易把障礙物的拐角和凹陷誤認為是窄通道。PARK B提出了一種自適應環境的采樣方法，首先把環境劃分為大小不一的若干區域，不同區域間采樣點數目一致，提取障礙物的邊界點，根據邊界信息移動采樣點使其分布于窄通道中[3]。但這些研究往往對環境的全部狀態空間進行采樣，存在效率較低、難以增加有效采樣點的問題。

1 ?針對窄通道問題改進的RRT算法

若要提高窄通道環境中的采樣質量，需先識別出環境中的窄通道區域，本文參照文獻[4]中的星形試驗法，采用正交的雙橋對采樣點進行測試，從而使采樣點分布在窄通道中，盡可能不陷入環境中的拐角和凹陷區域。

傳統的單橋測試法需執行3次碰撞檢測，雙橋測試法需執行5次碰撞檢測，而且窄通道區域在環境中的占比很小，如果直接對環境整體采樣進行雙橋測試，那么需要進行巨量的碰撞計算，才能識別出窄通道內的點。可以先將物體等比例縮小，用RRT算法查找出多條可行路徑，把路徑節點列入集合R中，在R中逐點對原物體進行碰撞檢測，將無碰撞的點置入集合F中，再使用雙橋法對F逐點進行測試，提取出窄通道內的節點置入集合Z中。

然后對原物體進行RRT路徑規劃，以一定概率偏向Z中的點和目標位置點采樣，由于復雜環境中窄通道區域常和開闊區域并存，在算法執行中應將環境分為若干區域，設置步長隨所在區域動態調整。可先大致劃分區域，在不同區域設置初始步長，再計算該步長下，F中節點在向外拓展時與障礙物的碰撞概率，根據“開闊區域采用較大步長、窄通道附近區域采用較小步長，不同區域內F中節點在向外拓展時與障礙物的碰撞概率大致相同”的原則調整區域劃分和步長。對于某些障礙物較多、邊界復雜的區域，可設置步長為隨機數，當物體在拓展新節點與障礙物發生碰撞時，以隨機的小步長沿采樣點方向生成新的節點，再進行碰撞檢測，如此可增加障礙物附近的采樣概率。

2 ?仿真分析

由于窄通道環境中RRT尋路耗時很長，限于硬件配置，本文設置了圖1所示的簡單窄通道環境進行仿真實驗，長方形物體共有二維平面的移動加旋轉3個自由度，碰撞檢測算法采用基于分離軸檢測的凸多面體碰撞算法[5]。

為對比RRT算法改進前后的性能，設定了不同的采樣和步長調整策略，各自執行20次RRT算法，得到不同策略對應的執行用時（見表1）。

經典RRT算法只是偏向目標點采樣，由于落在窄通道中的采樣點很少，所以算法運行時間很長。改進后的RRT算法在識別出窄通道區域后，以一定概率偏向目標點和通道點采樣，增加了窄通道內的采樣密度，拓展節點時步長隨區域調整，由于從開闊區域進入窄通道時對物體位姿約束很強，進入窄通道的過程往往耗時較長，該區域拓展節點發生碰撞時采用隨機小步長再次嘗試拓展，可以增加障礙物附近的采樣，加速從開闊區域進入窄通道的過程。綜合利用偏向窄通道的采樣和動態步長調整策略，如表1所示，可使RRT算法的規劃速度提高很多。

3 ?結語

針對有窄通道的環境路徑規劃速度過慢的問題，本文在應用RRT算法時進行了一些簡單的改進，主要從識別窄通道和采樣步長兩方面，增加窄通道及附近區域的采樣密度，仿真實驗表明，改進后RRT算法的運行時間能縮小很多。但參數設置時還需大量人為調整，例如橋測試的線段長度、不同區域的采樣步長值等等。希望未來能結合圖像識別手段，自動設置相關參數，使之擁有更好的環境適應能力。

參考文獻

[1] LAVALLE S. Rapidly-exploring random trees： a new tool for path planning[Z]. Research Report， 1998： 293-308.

[2] HSU D，JIANG T，REIF J，et al.The bridge test for sampling narrow passages with probabilistic roadmap planners[C]// Proc of IEEE International Conference on Robotics and Automation. New York： IEEE Press，2003： 4420-4426.

[3] PARK B，CHUNG W K. Adaptive node sampling method for probabilistic roadmap planners[C]/ / Proc of IEEE / RSJ International Conference on Intelligent Robots and Systems. Piscataway，NJ： IEEE Press，2009： 4399-4405.

[4] 鐘建冬， 蘇劍波. 基于概率路標的機器人狹窄通道路徑規劃[J]. 控制與決策， 2010， 25（12）：1831-1836.

[5] 張應中， 范超， 羅曉芳. 凸多面體連續碰撞檢測的運動軌跡分離軸算法[J]. 計算機輔助設計與圖形學學報， 2013（1）：7-14.