在水面无人艇全局避障规划领域，RRT*算法及其改进方法规划的路径长度过长、转折过多，并且规划路径紧靠障碍物，不利于水面无人艇的安全行驶。针对此问题，本文提出一种新的基于线段定理和RRT*算法（Line segment theorem-RRT*）的LT-RRT*算法。该算法对环境地图进行预处理，标示出障碍物周围危险区域，为无人艇与障碍物之间留出安全距离。再根据终点采样概率选取采样点，改善RRT*算法由于全局采样引起的路径不稳定性。最后根据线段定理重新选取新节点和附近节点的父节点，跳过中间节点连接树节点，减少路径折点，最终生成相对平滑的避障路径。在相同环境下，将改进算法与现有算法避障规划效果进行比较分析，结果表明了LT-RRT*算法的有效性。
In the global obstacle avoidance planning of unmanned surface vehicles, RRT* algorithm and other improved methods are applied to planning path. However, there are some shortcomings when these algorithms are used to deal with path planning, such as slow convergence, too long path, too much turning points in the path and too close to obstacles. To solve these problems, a new path planning algorithm based on the line segment theorem and RRT* algorithm, abbreviated as LT-RRT*, is proposed in this paper. Firstly, the environmental map's pre-treatment marks the dangerous area around the obstacles and leaves a safe distance between the unmanned surface vehicle and obstacles. Then, one selects sampling points according to the goal-point-sampling probability, which can avoid the instability induced by the global sampling of RRT* algorithm. Finally, according to the line segment theorem, one can select the parent node for the new node and nearby nodes. Since this process skips the intermediate node, it can reduce both turning points in the path and the path's cost, and finally generate a relatively smooth obstacle avoidance path. In the same environments, the improved algorithm is compared with existing algorithms for obstacle avoidance planning. The results show the effectiveness of the LT-RRT* algorithm.
2019,41(12): 167-172 收稿日期：2019-09-25
DOI：10.3404/j.issn.1672-7649.2019.12.032
分类号：U674.91
基金项目：国家自然科学基金资助项目（61873335，61833011）；上海市东方学者特聘教授资助项目；江苏省青蓝工程中青年学术带头人资助项目；江苏省自然科学基金项目（BK20161361）
作者简介：杨左华(1994-),女,硕士研究生,研究方向为路径规划算法
参考文献：
[1] CAMPBELL S, NAEEM W, IRWIN G W. A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance manoeuvres[J]. Annual Reviews in Control, 2012, 36(2): 267–283
[2] LIU Zhixiang, ZHANG Youmin, YU Xiang, et al. Unmanned surface vehicles: An overview of developments and challenges[J]. Annual Reviews in Control, 2016, 41: 71–93
[3] 庄佳园, 张磊, 孙寒冰, 等. 应用改进随机树算法的无人艇局部路径规划[J]. 哈尔滨工业大学学报, 2015, 47(1): 112–117 ZHUANG Jiayuan, ZHANG Lei, SUN Hanbing, et al. Improved rapidly-exploring random tree algorithm application[J]. Journal of Harbin Institute of Technology, 2015, 47(1): 112–117
[4] TAHIR Z, QURESHI A H, AYAZ Y, et al. Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments[J]. Robotics and Autonomous Systems, 2018, 108: 13–27
[5] JANSON L, ICHTER B, PAVONE M. Deterministic sampling-based motion planning: optimality, complexity, and performance[J]. International Journal of Robotics Research, 2018, 37(1): 46–61
[6] LAVALLE S M. Rapidly-exploring random trees: a new tool for path planning[D]. USA: Computer Science Department, Iowa State University, 1998.
[7] 潘思宇, 徐向荣. 基于改进RRT*的移动机器人运动规划算法[J]. 山西大学学报(自然科学版), 2017, 40(2): 244–254 PAN Si-yu, XU Xiang-rong. Improved RRT*-based motion planning algorithm for mobile robot[J]. Journal of Shanxi University (Nat. Sci. Ed.), 2017, 40(2): 244–254
[8] ADIYATOV O, VAROL H A. A novel RRT*-based algorithm for motion planning in dynamic environments [C]// IEEE International Conference on Mechatronics and Automation, Takamatsu, Japan: IEEE, 2017: 1416–1421.
[9] LAVALLE S M, KUFFNER J J. RRT-Connect: An efficient approach to single-query path planning [C]// IEEE International Conference on Robotics and Automation. San Francisco, CA, USA: IEEE, 2002.
[10] 张亚琨, 高泽东, 曹杰, 等. 多采样寻优的双向RRT路径规划算法[J]. 计算机仿真, 2019, 36(2): 319–324 ZHANG Ya-kun, GAO Ze-dong, CAO Jie, et al. Bidirectional RRT path planning algorithm with multiple sampling optimization[J]. Computer Simulation, 2019, 36(2): 319–324
[11] 王坤, 曾国辉, 鲁敦科, 等. 基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法[J]. 计算机应用, 2019, 39(5): 1312–1317 WANG Kun, ZENG Guo-hui, LU Dun-ke, et al. Path planning of mobile robot based on improved B-RRT* algorithm[J]. Journal of Computer Applications, 2019, 39(5): 1312–1317
[12] LIN Na, ZHANG Ya-lun. An adaptive RRT based on dynamic step for UAVs route planning [C]// Proceedings of the 5th IEEE Software Engineering and Service Science, [S. I.]: IEEE, 2014: 1111–1114.
[13] 李洋, 徐达, 周诚. 基于自适应步长RRT的双机器人协同路径规划[J]. 农业机械学报, 2019, 50(3): 358–367 LI Yang, XU Da, ZHOU Cheng. Cooperation path planning of dual-robot based on self-adaptive stepsize RRT[J]. Transactions of the Chinese Society for Agricultural Machinery, 2019, 50(3): 358–367
[14] 龙建全, 梁艳阳. 多路口环境下RRT的最优路径规划[J/OL]. 计算机工程与应用, 2019. (2019-04-02) [2019-08-02]. http://kns.cnki.net/kcms/detail/11.2127.TP.20190401.1530.002.html. LONG Jian-quan, LIANG Yan-yang. Optimal path planning of RRT in multi-intersection environment[J/OL]. Computer Engineering and Applications, 2019. (2019-04-02) [2019-08-02]. http://kns.cnki.net/kcms/detail/11.2127.TP.20190401.1530.002.html.
[15] 王素琴, 王飞, 袁建平, 等. 基于双向RRT算法的管线路径规划及建模仿真[J]. 太原理工大学学报, 2018, 49(6): 839–845 WANG Su-qing, WANG Fei, YUAN Jian-ping, et al. Pipeline route planning and simulation based on bidirectional RRT algorithm[J]. Journal of Taiyuan University of Technology, 2018, 49(6): 839–845
[16] 程向红, 祁艺. 基于栅格法的室内指示路径规划算法[J]. 中国惯性技术学报, 2018, 26(2): 102–106+133 CHENG Xiang-hong, QI yi. Indoor indicator path planning algorithm based on grid method[J]. Journal of Chinese Inertial Technology, 2018, 26(2): 102–106+133
[17] DANIEL K, NASH A, KOENIG S, et al. Theta*: Any-angle path planning on grids[J]. Journal of Artificial Intelligence Research, 2010, 39: 533–579
