针对双向快速扩展随机树（Bidirectional Rapidly-exploring Random Tree, Bi-RRT）算法在结合无人艇进行路径规划时存在规划效率低、偏航角过大、路径不平滑等问题，提出一种改进Bi-RRT的水面无人艇全局路径规划算法。算法中通过构建数学模型将爬山算法融入双树扩展过程，通过邻域搜索和距离最小化准则增强两树扩展时的导向性；引入动态步长和双向距离引导采样策略进一步提高规划效率；采用路径剪枝优化初始路径并约束偏航角度，最后在算法中加入自适应权重的3次B样条函数来平滑路径。仿真结果表明，相比改进前，改进Bi-RRT算法所规划路径的节点数、拐点数、路径长度以及规划时长明显减少，大于65°偏航角数量减少了74.76%。改进后算法效率更高、路径更平滑，可为水面无人艇自主航行提供参考。
To address issues like low efficiency, excessive yaw angles, and uneven paths when combining the bidirectional rapidly-exploring random tree (Bi-RRT) algorithm with unmanned vessel path planning, an enhanced Bi-RRT global path planning algorithm is proposed. The method integrates a mountain climbing algorithm into the two-tree expansion via a mathematical model, improves orientation through neighborhood search and distance minimization, and boosts efficiency with dynamic step sizes and bidirectional distance-guided sampling. Path pruning optimizes the initial route while constraining yaw angles, and an adaptive-weight cubic B-spline function smooths the path. Simulations and real-world tests confirm that the improved algorithm reduces node count, inflection points, path length, and planning time significantly, while cutting excessive yaw angles (>65°) by 74.76%. The refined algorithm enhances efficiency and smoothness, aiding autonomous unmanned vessel navigation.
2025,47(24): 79-86 收稿日期：2025-5-14
DOI：10.3404/j.issn.1672-7649.2025.24.013
分类号：U674；TP18
基金项目：辽宁省教育厅科学研究项目（DL202004）；辽宁省自然科学基金计划项目（2023-BSBA-020）；设施渔业教育部重点实验室（大连海洋大学）资助项目（202320）
作者简介：陈小龙(2001-),男,硕士研究生,研究方向为无人船路径规划
参考文献：
[1] WU Y, WANG T, LIU S. A review of path planning methods for marine autonomous surface vehicles[J]. Journal of Marine Science and Engineering, 2024, 12(5): 833.
[2] 符运来, 王魏, 刘妙男, 等. 基于改进P-RRT*算法的无人船路径规划[J]. 控制工程, 2024, 31(10): 1-8.
[3] 周畅, 于特, 刘佳鹏, 等. 基于快速随机搜索树*与凸优化的船舶路径规划与跟踪算法[J]. 中国舰船研究, 2025, 20(1): 147-161.
ZHOU C, YU T, LIU J P, et al. Ship path planning and tracking based on rapidly exploring random tree star and convex optimization[J]. Chinese Journal of Ship Research, 2025, 20(1): 147-161.
[4] 梅梦磊, 陈顺洪, 菅永坤, 等. 基于双向搜索改进A*算法的无人艇全局路径规划[J]. 舰船科学技术, 2025, 47(5): 97-102.
MEI M L, CHEN S H, JIANG Y K, et al. Global path planning of unmanned vessels based on improved A* algorithm of bidirectional search[J]. Ship Science and Technology, 2025, 47(5): 97-102.
[5] WANG H, YU Y, YUAN Q. Application of dijkstra algorithm in robot path-planning[C]//2011 second international conference on mechanic automation and control engineering. IEEE, 2011.
[6] ZHANG L, TANG Y, HUA C, et al. A new particle swarm optimization algorithm with adaptive inertia weight based on Bayesian techniques[J]. Applied Soft Computing, 2015, 20(8): 138-149.
[7] NOREEN I, KHAN A, HABIB Z. A comparison of RRT, RRT* and RRT*-smart path planning algorithms[J]. International Journal of Computer Science and Network Security, 2016, 16(10): 20-22.
[8] ZHANG R, GUO H, ANDRIUKAITIS D, et al. Intelligent path planning by an improved RRT algorithm with dual grid map[J]. Alexandria Engineering Journal, 2024, 80(8): 91-104.
[9] KUFFNER J J, LAVALLE S M. RRT-connect: An efficient approach to single-query path planning[C]//Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings. IEEE, 2000.
[10] GUO W, TANG G, ZHAO F, et al. Global dynamic path planning algorithm for usv based on improved bidirectional rrt[C]//ISOPE International Ocean and Polar Engineering Conference. ISOPE, 2022: ISOPE- I-22-547.
[11] SUN L, ZHAO Y, ZHANG J. Research on path planning algorithm of unmanned ship in narrow water area[C]// Journal of Physics: Conference Series. IOP Publishing, 2021.
[12] ZHOU Y, LI W, CHENG K, et al. Enhanced USV path planning through integrated Bi-RRT and DWA algorithms considering environmental factors[J]. Journal of Marine Engineering & Technology, 2024, 5(2): 1-17.
[13] 张一帆, 史国友, 徐家晨. 基于人工势场法引导的 Bi-RRT 的水面无人艇路径规划算法[J]. 上海海事大学学报, 2022, 43(4): 16-22.
[14] 黄健堃, 薛钢, 刘延俊, 等. 基于改进Bi-RRT算法的机器鱼路径规划方法[J]. 山东大学学报(工学版), 2024, 54(1): 74-82.
[15] 赵贵祥, 周健, 李云淼, 等. 改进双向快速搜索随机树的无人艇路径规划[J]. 系统工程与电子技术, 2024, 46(4); 1364-1371.
[16] 陈慧敏, 窦培林, 程晨, 等. 基于Bi-RRT和TEB算法的风电水域多目标点路径规划[J]. 船海工程, 2024, 53(4): 130-136.
[17] 刘伊婕, 姜斌, 马亚杰, 等. 无人艇编队避碰路径规划与重规划[J/OL]. 系统工程与电子技术, 2012(3): 1-15.
[18] 刘越, 王天笑, 柴秋月, 等. 基于改进Bi-RRT与动态窗口法的机器人动态路径规划[J]. 实验室研究与探索, 2024, 43(5): 77-83.
[19] KUZNETSOV A, FRONTONI E, ROMEO L, et al. Opti-mizing hill climbing algorithm for S-boxes generation[J]. Electronics, 2023, 12(10): 2338.
[20] JIAN X Y, ZOU T, VARDY A, et al. A hybrid path planning strategy of autonomous underwater vehicles[C]//IEEE/OES Autonomous Underwater Vehicles Symposium (AUV). St. Johns: IEEE, 2020.
[21] 张伟民, 徐森生, 张月. 基于改进A*算法的室内巡检机器人路径规划研究[J]. 机械工程学报, 2024, 60(20): 315-326.
[22] 谢国兵, 贺沩, 胡旺文, 等. 基于不均匀分配信息素及多目标优化的改进蚁群算法在无人船路径规划中的应用研究[J]. 中国舰船研究, 2025, 20(1): 115-124.
XIE G B, HE W, HU W W, et al. Application of an improved ant colony algorithm based on unevenly distributed pheromone and multi-objective optimization in path planning for unmanned surface vehicles[J]. Chinese Journal of Ship Research, 2025, 20(1): 115-124.
