摘 要：为增强 RRT* 路径规划算法的目标导向性和收敛速度，提出一种目标区域偏置扩展的移动机器人 RRT* 路径规划算法。该算法首先根据目标区域偏置扩展方法快速规划出一条初始路径，然后通过椭圆子集采样和节点约束策略来限制采样空间的大小和扩展节点的数量，再利用路径修正方法得出一条平滑路径。在简单和复杂两种地图环境下与 RRT*、InformedRRT*、RRT*-FN 算法进行比较分析，研究结果显示，该算法具有较强的目标导向性和快速收敛性。
关键词：路径规划；RRT*；目标区域偏置扩展；节点约束策略
DOI:10.19850/j.cnki.2096-4706.2022.19.002
基金项目：国家自然科学基金（61861008，62161007，62061010）；广西壮族自治区基金会（AA19182007，AA19254029，AA20302022，AB21196041）
中图分类号：TP242 文献标识码：A 文章编号：2096-4706（2022）19-0007-06
RRT* Path Planning Algorithm of Goal Region Biasing Extension
YI Chi 1, WU Jianhui 1,2
(1.Hunan Institute of Science and Technology, Yueyang 414006, China; 2.Guilin University of Electronic Technology, Guilin 541004, China)
Abstract: To improve the goal orientation and convergence speed of the RRT* path planning algorithm, this paper proposes the mobile robots RRT* path planning algorithm of goal region biasing expansion. This algorithm quickly plans an initial path according to the goal region biasing expansion method firstly, then limits the size of the sampling space and the number of expansion nodes by ellipse subset sampling and node constraint strategy, and uses the path correction method to get a smooth path. It compares and analyzes the proposed algorithm with the RRT*, Informed-RRT*, and RRT*-FN algorithm in both the simple and complex map environments. The research results show that this algorithm has stronger goal orientation and fast convergence.
Keywords: path planning; RRT*; goal region biasing extension; node constraint strategy
参考文献：
[1] 徐小强，王明勇，冒燕 . 基于改进人工势场法的移动机器人路径规划 [J]. 计算机应用，2020，40（12）：3508-3512.
[2] LUO Q，WANG H B，ZHENG Y，et al.Research on Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm [J]. Neural Computing and Applications，2020，32（6）：1555-1566.
[3] LIU J H，YANG J G，LIU H P，et al.An Improved Ant Colony Algorithm for Robot Path Planning [J].Soft Computing，2017， 21（19）：5829-5839.
[4] ZHANG L，ZHANG Y J，LI Y F.Mobile Robot Path Planning Based on Improved Localized Particle Swarm Optimization [J]. IEEE Sensors Journal，2020，21（5）：6962-6972.
[5] 胡章芳，冯淳一，罗元 . 改进粒子群优化算法的移动机器人路径规划 [J]. 计算机应用研究，2021，38（10）：3089-3092.
[6] 孙波，姜平，周根荣，等 . 改进遗传算法在移动机器人路径规划中的应用 [J]. 计算机工程与应用，2019，55（17）：162- 168.
[7] LIU Q H，ZHAO L J，TAN Z B，et al.Global Path Planning for Autonomous Vehicles in Off-Road Environment Via an A-Star Algorithm [J].Int. J. of Vehicle Autonomous Systems，2017，13（4）： 330-339.
[8] WANG J K，MENG M Q H.Optimal Path Planning Using Generalized Voronoi Graph and Multiple Potential Functions [J].IEEE Transactions on Industrial Electronics，2020：1-1.
[9] LAVALLE S M，KUFFNER J J.Rapidly-Exploring Random Trees：Progress and Prospects [J].Algorithmic and Computational Robotics：New Directions，2001，5：293-308.
[10] TAHERI E，FERDOWSI M H，DANESH M.Fuzzy Greedy RRT Path Planning Algorithm in a Complex Configuration Space [J]. International Journal of Control，Automation and Systems，2018，16（6）： 3026-3035.
[11] FRANCIS A，FAUST A，CHIANG H T L，et al.LongRange Indoor Navigation with PRM-RL [J].IEEE Transactions on Robotics，2020，36（4）：1115-1134.
[12] KARAMAN S，FRAZZOLI E.Sampling-Based Algorithms for Optimal Motion Planning [J].The International Journal of Robotics Research，2011，30（7）：846-894.
[13] GAMMELL J D，SRINIVASA S S，BARFOOT T D.Informed RRT：Optimal Sampling-Based Path Planning Focused Via Direct Sampling of an Admissible Ellipsoidal Heuristic [C]//2014 IEEE/RSJ International Conference on Intelligent Robots and Systems.Chicago： IEEE，2014：2997-3004.
[14] KIM M C，SONG J B.Informed RRT* with Improved Converging Rate by Adopting Wrapping Procedure [J].Intelligent Service Robotics，2018，11（1）：53-60.
[15] MASHAYEKHI R，IDRIS M Y I，ANISI M H，et al.Informed RRT*-Connect：An Asymptotically Optimal Single-Query Path Planning Method [J].IEEE Access，2020，8：19842-19852.
[16] ISLAM F，NASIR J，MALIK U，et al.RRT*-Smart：Rapid Convergence Implementation of RRT* towards Optimal Solution [C]//2012 IEEE International Conference on Mechatronics and Automation.Chengdu：IEEE，2012：1651-1656.
[17] ADIYATOV O，VAROL H A.Rapidly-Exploring Random Tree Based Memory Efficient Motion Planning [C]//2013 IEEE International Conference on Mechatronics and Automation.Takamatsu： IEEE，2013：354-359.
[18] MOSES D B，GANESAN A.Goal Directed Approach to Autonomous Motion Planning for Unmanned Vehicles [J].Defence Science Journal，2016，67（1）：45.
[19] 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 and Applications （IJACSA），2016，7（11）：97-107.
[20] 刘建宇，范平清 . 基于改进的 RRT*-connect 算法机械臂路径规划 [J]. 计算机工程与应用，2021，57（6）：274-278.
作者简介：易驰（1997—），男，汉族，湖南岳阳人，硕士研究生在读，研究方向：移动机器人路径规划；伍建辉（1984—），男，汉族，湖南汨罗人，讲师，硕士研究生导师，博士，研究方向：决策和优化、卫星导航。