基于改進漸進最優的雙向快速擴展隨機樹的移動機器人路徑規劃算法

王坤 曾國輝 魯敦科 黃勃 李曉斌

摘 要：針對帶啟發式的快速擴展隨機樹（RRTConnect）算法路徑生成的隨機性以及漸進最優的雙向快速擴展隨機樹（BRRT*）算法收斂速度的緩慢性，提出了一種基于BRRT*改進的高效路徑規劃算法（EBRRT*）。首先引入一種智能采樣函數，使隨機樹的擴展更具方向性，從而減少尋路時間，并提高路徑的平滑性;其次在BRRT*算法的基礎上，在EBRRT*算法中加入了一種快速擴展策略，使改進后的算法在自由空間中使用RRTConnect算法的擴展方式進行快速擴展，而在障礙物空間則使用改進的漸進最優的快速擴展隨機樹（RRT*）算法進行擴展，在提高擴展效率的同時避免算法陷入局部最優。將EBRRT*算法分別與快速擴展隨機樹（RRT）、RRTConnect、RRT* 和BRRT*算法進行仿真對比，仿真結果表明，改進后的算法在路徑規劃效率及路徑平滑性方面均明顯優于其他算法;且相對于BRRT*算法，其在路徑規劃時間上降低了68.3%，在迭代次數上減少了48.6%。

關鍵詞：移動機器人;路徑規劃;快速擴展隨機樹;帶啟發式的快速擴展隨機樹算法;漸進最優的雙向快速擴展隨機樹算法

中圖分類號：TP242.6

文獻標志碼：A

Abstract： To overcome the randomness of RRTConnect and slow convergence of BRRT*（asymptoticallyoptimal Bidirectional Rapidlyexploring Random Tree） in path generation， an efficient path planning algorithm based on BRRT*， abbreviated as EBRRT*， was proposed. Firstly， an intelligent sampling function was intriduced to achieve more directional expansion of random tree， which could improve the smoothness of path and reduce the seek time. A rapidlyexploring strategy was also added in EBRRT* by which RRTConnect exploration mode was adopted to ensure rapidly expanding in the free space and improved asymptoticallyoptimal Rapidlyexploring Random Tree （RRT*） algorithm was adopted to prevent trapped in local optimum in the obstacle space. Finally， EBRRT* algorithm was compared with Rapidlyexploring Random Tree （RRT）， RRTConnect， RRT* and BRRT* algorithms. The simulation results show that the improved algorithm is superior to other algorithms in the efficiency and smoothness of path planning. It reduced the path planning time by 68.3% and the number of iterations by 48.6% compared with BRRT* algorithm.

英文關鍵詞Key words： mobile robot; path planning; Rapidlyexploring Random Tree （RRT）; RRTConnect algorithm; asymptoticallyoptimal Bidirectional Rapidlyexploring Random Tree （BRRT*） algorithm

0 引言

隨著人工智能等新興領域的不斷崛起，移動機器人的發展速度也獲得飛速提升。目前，諸如家庭、工廠以及醫院等公共場所對移動機器人的需求正在不斷增加，而移動機器人作為生產工具，需要經常從一個位置移動至另一個位置，所以如何規劃出一條即無障礙物又可以最小化消耗的路徑成為了該領域的一項熱門研究。國內外的學者紛紛對此進行了相關的研究，并提出了許多可行的路徑規劃理論及方法， 其中包括蟻群算法[1]、粒子群優化算法[2]、遺傳算法[3]、人工勢場法[4]和A*[5]算法等。這些算法在簡單環境下可以實現快速收斂到最優路徑，但在處理復雜環境及高維空間時一方面收斂速度會急劇下降，另一方面其所生成的路徑并未考慮移動機器人的運動學約束，導致規劃出的路徑并不能被機器人所執行。

為解決高維環境下路徑規劃問題，基于采樣的路徑規劃算法被提出， 其中包括概率路圖法（Probability Roadmap Method， PRM）[6]和快速擴展隨機樹（Rapidlyexploring Random Tree， RRT）算法[7]。PRM算法作為最早的基于采樣的路徑規劃算法，其在路徑搜索的實時性與最優性上可以滿足要求，但仍未考慮到移動機器人的非完整約束[8]，且當環境中存在未知障礙物時會嚴重影響其規劃效率。由于PRM算法存在的不足，LaValle等提出了一種基于采樣的RRT算法，該算法具有概率完備且收斂速度快，可應用在未知障礙物等優點，但其也存在一些缺陷[9-10]：1）由于算法采用隨機采樣狀態空間進行擴展的方式，使得隨機樹的擴展沒有方向性，導致最終生成的路徑并非最優路徑;2）由于算法需要探索整個未知空間，并進行反復迭代以找到一條可行路徑，使得算法在運行中需要消耗大量的內存;3）由于算法的隨機性，導致最終生成的路徑較為粗糙，不適合移動機器人直接采用。

對于RRT算法存在的不足，國內外學者對其作了一定程度的改進，其中國外較為典型的改進有帶啟發式的快速擴展隨機樹（RRTConnect）算法[11]、漸進最優的快速擴展隨機樹（asymptoticallyoptimal Rapidlyexploring Random Tree， RRT*）算法[12]、漸進最優的雙向快速擴展隨機樹（asymptoticallyoptimal Bidirectional Rapidlyexploring Random Tree， BRRT*）算法[13]和IBRRT*（Intelligent Bidirectional RRT*）算法[14]。RRTConnect算法由Kuffner等[11]于2000年提出，該算法通過并行生成兩棵隨機樹的方式來提高尋找路徑的速度。RRT*算法由Karaman等于2010年提出，該算法的提出很好地解決了RRT算法生成路徑非最優問題，但由于在探索中計算量的增加，使其路徑生成效率大幅降低[15]。Jordan等通過借鑒RRTConnect算法思想，于2013年提出了雙向擴展的RRT*算法，即BRRT*，同時通過改進RRTConnect算法的連接函數，從而保證算法所連接的兩棵樹可以生成一條最優路徑。Qureshi等[14]于2015年提出了IBRRT*算法，在BRRT*算法中引入一種智能樣本插入函數，從而提高算法收斂到最優路徑的速度。國內對RRT算法的研究較少，目前較早的研究為康亮等[16]于2010年提出了一種將RRT算法與滾動窗口相結合的改進算法，該算法克服了RRT算法只能在環境已知的條件下進行路徑規劃的限制;馮楠[17]于2014年提出一種改進RRTConCon的算法，提高了RRT算法的穩定性，使其更易朝著目標點擴展;潘思宇等[18]于2017年提出一種RRT*的改進算法，引入一種節點啟發式采樣函數，提高路徑規劃的速度與質量。

本文主要針對BRRT*算法采樣的隨機性和擴展方式的緩慢性，提出一種基于BRRT*的改進算法EBRRT*（Efficient Bidirectional RRT*），該算法引入智能采樣函數代替原始算法中的隨機采樣函數，通過在起始點與目標點之間采樣最優固定點作為兩棵樹的目標點，使隨機樹在擴展中具有方向性，同時使用快速擴展策略，將隨機樹的擴展分成兩個階段：當探索無障礙物空間時，算法采用RRTConnect算法的策略進行快速擴展;當檢測到擴展方向有障礙物時，算法啟動改進后的RRT*進行擴展，從而保證算法不會陷入局部最優。通過仿真實驗驗證了改進后的算法在有效性、實時性和優越性上具有明顯優勢。

4 結語

本文以BRRT*算法為基礎，通過將原始算法中的隨機采樣函數替換為智能采樣函數，并考慮RRTConnect算法的擴展方式從而引入快速擴展策略，使算法的擴展更高效，生成路徑更平滑。通過對改進后的算法在不同地圖中進行仿真，其結果表明改進后的算法在路徑生成速度、迭代次數及平滑性上相較于其他算法具有明顯優勢。不過改進后的算法仍存在一些不足之處，比如在擴展方式切換時路徑會出現較大彎曲，下一步將嘗試在擴展中加入平滑處理函數，使擴展方式改變時路徑銜接更平滑。

參考文獻 （References）

[1] DORIGO M， GAMBARELLA L M. Ant colony system： a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 53-66.

[2] 韓明，劉教民，吳朔媚，等. 粒子群優化的移動機器人路徑規劃算法[J]. 計算機應用， 2017， 37（8）： 2258-2263.（HAN M， LIU J M， WU S M， et al. Path planning algorithm of mobile robot based on particle swarm optimization[J]. Journal of Computer Applications， 2017， 37（8）： 2258-2263.）

[3] OZDIKIA O. Genetic algorithm with random coordinates for route planning on a 3D terrain[C]// Proceedings of the 2011 5th International Conference on Genetic and Evolutionary Computing. Washington， DC： IEEE Computer Society， 2011： 146-149.

[4] CHEN T B， ZHANG Q. Robot motion planning based on improved artificial potential field[C]// Proceedings of the 2013 3rd International Conference on Computer Science and Network Technology. Piscataway， NJ： IEEE， 2013： 1208-1211.

[5] LIN M， YUAN K， SHI C， et al. Path planning of mobile robot based on improved A* algorithm[C]// Proceedings of the 2017 29th Chinese Control and Decision Conference. Piscataway， NJ： IEEE， 2017： 3570-3576.

[6] KAVRAKI L E， SVESTKA P， LATOMBE J C， et al. Probabilistic roadmaps for path planning in highdimensional configuration spaces [J]. IEEE Transactions on Robotics and Automation， 1996， 12（4）： 566-580.

[7] LAVALLE S M， KUFFNER J J. Randomized Kinodynamic planning [C]// Proceedings of the 1999 IEEE International Conference on Robotics and Automation. Piscataway， NJ： IEEE， 1999： 473-479.

[8] 宋金澤，戴斌，單恩忠，等. 一種改進的RRT路徑規劃算法[J]. 電子學報， 2010， 38（Z1）： 225-228.（SONG J Z， DAI B， SHAN E Z， et al. An improved RRT path planning algorithm[J]. Acta Electronica Sinica， 2010， 38（Z1）： 225-228.）

[9] GAMMELL J D， SRINIVASA S S， BARFOOT T D. Informed RRT*： optimal samplingbased path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]// Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway， NJ： IEEE， 2014： 2997-3004.

[10] DOSHI A A， POSTULA A J， FLETCHER A， et al. Development of microUAV with integrated motion planning for opencut mining surveillance [J]. Microprocessors and Microsystems， 2015， 39（8）： 829-835.

[11]KUFFNER J J， LAVALLE S M. RRTconnect： an efficient approach to singlequery path planning[C]// Proceedings of the 2000 IEEE International Conference on Robotics and Automation. Piscataway， NJ： IEEE， 2000： 995-1001.

莫棟成，劉國棟. 改進的RRTConnect雙足機器人路徑規劃算法[J].計算機應用， 2013， 33（8）： 2289-2292.（MO D C， LIU G D. Improved RRTConnect path planning algorithm for biped robot [J]. Journal of Computer Applications， 2013， 33（8）： 2289-2292.）

[12] KARAMAN S， FRAZZOLI E. Samplingbased algorithms for optimal motion planning[J]. The International Journal of Robotics Research， 2011， 30（7）： 846-894.

[13] JORDAN M， PEREZ A. Optimal bidirectional rapidlyexploring random trees [EB/OL].[2018-03-20]. https：//dspace.mit.edu/bitstream/handle/1721.1/79884/MITCSAILTR-2013021.pdf.

[14] QURESHI A H， AYAZ Y. Intelligent bidirectional rapidlyexploring random trees for optimal motion planning in complex cluttered environments*[J]. Robotics and Autonomous Systems， 2015， 68： 1-11.

[15] OLZHAS A， HUSEYIN A V. A novel RRT*based algorithm for motion planning in dynamic environments[C]// Proceedings of the 2017 IEEE International Conference on Mechatronics and Automation. Piscataway， NJ： IEEE， 2017： 1416-1421.

[16] 康亮，趙春霞，郭劍輝. 基于模糊滾動RRT算法的移動機器人路徑規劃[J]. 南京理工大學學報（自然科學版）， 2010， 34（5）： 642-648. （KANG L， ZHAO C X， GUO J H. Path planning based on fuzzy rolling rapidlyexploring random tree for mobile robot[J]. Journal of Nanjing University of Science and Technology （Natural Science）， 2010， 34（5）： 642-648.

[17] 馮楠. 自主移動機器人路徑規劃的RRT算法研究[D]. 大連： 大連理工大學， 2014. （FENG N. Research on RRT algorithm of path planning for autonomous mobile robot[D]. Dalian： Dalian University of Technology， 2014.

[18] 潘思宇，徐向榮. 基于改進RRT*的移動機器人運動規劃算法[J]. 山西大學學報（自然科學版）， 2017， 40（2）： 244-254.（PAN S Y， XU X R. Improved RRT*based motion planning algorithm for mobile robot [J]. Journal of Shanxi University （Natural Science Edition）， 2017， 40（2）： 224-254.）

[19] ZAID T， AHMED H Q， YASAR A， et al. Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments[J]. Robotics and Autonomous Systems， 2018， 108： 13-27.

[20] NOREEN I， KHAN A， HABIB Z. Optimal path planning using RRT* based approaches： a survey and future directions[J]. International Journal of Advanced Computer Science & Application， 2016， 7（11）： 97-107.

[21] IRAM N， AMNA K， HYEJEONG R， et al. Optimal path planning in cluttered environment using RRT*AB[J]. Intelligent Service Robotics， 2017， 11（1）： 41-52.