DEB-RRT:基于动态椭球体采样的改进 RRT 算法

DEB-RRT:An Improved RRT Algorithm Based on Dynamic Ellipsoid Sampling

摘要

针对双向快速扩展随机树算法采样点随机性大、采样点利用率低、算法收敛速度缓慢等问题，本文基于二维和三维环境提出了改进的 DEB-RRT(Dynamic Ellipsoid Bidirectional-Rapidly-Exploring Random Tree) 算法。在保证概率完备性前提下，本文算法依据碰撞检测的失败概率动态控制随机采样点的目标导向性，在获得可行路径解后对其进行路径二次优化处理，使得最终路径更短、转角处更平滑。在 MATLAB 平台上进行算法仿真，结果表明相较于其他传统的路径规划算法，该算法路径搜索时间更短，所得路径长度更短，更具有可行性。

Abstract

To address the problems of the strong randomness of sampling points, low sampling point utilization, and slow convergence of the bidirectional rapidly-exploring random tree (Bi-RRT) algorithm, this paper proposes an improved DEB-RRT (Dynamic Ellipsoid Bidirectional RRT) algorithm applicable to both 2D and 3D environments. While guaranteeing probabilistic completeness, the improved algorithm dynamically adjusts the goal bias of random sampling points based on the collision check failure rate. Once a feasible path is found, a secondary path optimization step is executed to shorten the final path and smooth its sharp corners. Simulations of the algorithm are carried out on the MATLAB platform. The experimental results demonstrate that, compared with conventional path planning algorithms, the proposed method requires less path search time, yields shorter path length, and delivers better overall performance.

关键词

路径规划 / 自适应采样 / 曲线优化处理 / 贪心算法 / 双向 RRT 算法

Key words

path planning / adaptive sampling / curve optimization processing / greedy algorithm / BI-RRT

参考文献

[1] LAVALLE S M, KUFFNER J J. Rapidly random-exploring trees: Progress and prospects[J].Intelligent Robots and Systems, 2001, 20(5):347-400.

[2] KUFFNER J J, LAVALLE S M. RRT-connect: An efficient approach to single-query path planning[C]//IEEE International Conference on Robotics and Automation. San Francisco: IEEE, 2000:995-1001.

[3] WANG J, CHI W, LI C, et al. Neural RRT*: Learning-based optimal path planning[J].IEEE Transactions on Automation Science and Engineering, 2023, 20(3):1645-1656.

[4] ZHANG H, WANG Y, ZHENG J, et al.P-RRT*: Potential-guided RRT* for motion planning in cluttered environments[J].IEEE Transactions on Industrial Electronics, 2023, 70(10):10363-10372.

[5] LI Y, WEI W, ZHANG Y. Q-RRT*: A quick RRT* algorithm based on ancestor optimization and triangular inequality[J].IEEE Robotics and Automation Letters, 2023, 8(5):2845-2852.

[6] WANG J, CHIOU W, HSU M, et al.Neural RRT*: Learning-based optimal path planning[J].IEEE Transactions on Automation Science and Engineering, 2022, 19(2):1168-1181.

[7] 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[J].The International Journal of Robotics Research, 2018, 37(13/14):1542-1559.

[8] WANG X, WEI J, ZHOU X, et al. AEB-RRT*: An adaptive extension bidirectional RRT* algorithm[J].Autonomous Robots, 2022(6):46.

[9] WANG L, GUO Y. Speed adaptive robot trajectory generation based on derivative property of B-Spline curve[J].IEEE Robotics and Automation Letters, 2023, 8(4):1905-1911.

[10] XU Z, XIU Y, ZHAN X, et al. Vision-aided UAV navigation and dynamic obstacle avoidance using gradient-based B-spline trajectory optimization[C]//2023 IEEE International Conference on Robotics and Automation. London, United Kingdom: IEEE， 2023:1905-1911.

[11] HONIG W, PREISS J A, KUMAR V, et al. Trajectory planning for quadrotor swarms[J].IEEE Transactions on Robotics, 2018, 34(4):856-869.

[12] SUN W, SUN P X , DING W, et al. Gradient-based autonomous obstacle avoidance trajectory planning for B-spline UAVs[J].Scientific Reports, 2024, 14(1):14458

[13] 赵卫东, 唐顾杰, 宋江一. 基于改进 JPS 与三次 B 样条插值的路径规划算法 [J].安徽工业大学学报 (自然科学版), 2022, 39(2):189-195.

[14] 刘梦奇, 王维强, 田良宇. 基于 B 样条曲线的无人驾驶车辆 Informed RRT*算法研究 [J].智能计算机与应用, 2022, 12(4):25-29.

[15] 张跃明, 薛奇, 纪姝婷. 满足曲率约束的 B 样条曲线连续路径平滑方法 [J].华中科技大学学报 (自然科学版), 2022, 50(5):59-65,72.

[16] 钱东海, 孙林林, 赵伟. 基于三次 B 样条曲线的叉车型 AGV 路径规划研究 [J].计算机测量与控制, 2022, 30(4):177-181,189.

[17] JEONG I B, LEE S J, KIM J H. Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate[J].Expert Systems with Applications, 2019, 123:82-90.

[18] KARAMAN S, FRAZZOLI E. Incremental Sampling-based algorithms for optimal motion planning[C]//Robotics: Science and Systems (RSS 2010). Zürich, Switzerland：[s.n.],2010.

[19] ZHANG Z, ZHANG J, ZHAO Y. A novel hexagonal grid map model and regenerated heuristic factor based strategy for intelligent manufacturing system's AGV path planning problem solving[J].Computers & Industrial Engineering, 2024,192:110154.

基金资助

国家自然科学基金项目(62076095)