刘渐道 张英俊 朱飞祥
摘要：为解决多障碍物环境下水面无人艇（unmanned surface vehicle， USV）多任务点路径规划问题，提出一种基于改进的快速探索随机树（rapidly-exploring random tree， RRT）的路径规划算法。在分析USV运动数学模型和经典RRT算法的基础上，将USV的运动数学模型融合到RRT算法中，预报两个任务点之间的路径曲线和距离;针对RRT算法随机性的特点，设计RRT路径优化算法，删除冗余路径点，得到优化路径;最后利用改进遗传算法，确定多任务点的访问顺序，生成多任务点路径，节省USV巡航路径距离。仿真结果证明，在多任务点及多障碍物存在的条件下，该方法能够确定一条合理的路径，具有一定的实际意义。
关键词：
水面无人艇（USV）; 多任务点路径规划; 快速探索随机树（RRT）; 运动学约束
中图分类号：
U675.79 文献标志码：
A
Abstract：
In order to solve the problem of multi-task point path planning for unmanned surface vehicles （USVs） in the multi-obstacle environment， a path planning algorithm based on the improved rapidly-exploring random tree （RRT） is proposed. Based on the analysis of USV’s motion mathematical model and the classical RRT algorithm， the USV’s motion mathematical model is integrated into the RRT algorithm， and the path curve and distance between two task points are forecasted. According to the randomness of RRT algorithm， an RRT path optimization algorithm is designed to delete the redundant path points so as to get an optimized path. Finally， the improved genetic algorithm is used to determine the access sequence of multi-task points and generate the multi-task point path， which can save the USV cruise path distance. The simulation result shows that the proposed method can determine a reasonable path under the condition of multi-task points and multiple obstacles， and has a certain practical significance.
Key words：
unmanned surface vehicle （USV）; multi-task point path planning; rapidly-exploring random tree （RRT）; kinematical constraint
0 引 言
水面無人艇（unmanned surface vehicle， USV）是一种具有自主感知环境、规划路径、智能航行及自主避障能力的小型船艇，在水文探测、海域巡逻、军事作战等方面有广泛的应用。USV路径规划就是根据任务要求在一定的条件下按照安全性、经济性原则自动规划从起点到终点的无障碍路径[1]。路径规划是实现自主航行必须解决的问题，是USV领域的研究热点。
现有的路径规划算法主要包括Dijkstra算法、A *算法等启发式搜索算法和遗传算法、粒子群算法、萤火虫算法、神经网络算法等智能仿生优化算法[2]。随博文等[3]提出一种改进的平滑A *算法，改进折线转弯为圆弧，使路径更加平滑安全;范云生等[4]基于电子海图采用栅格法建立环境模型，利用改进的遗传算法进行全局路径快速搜索，规划出的路径具有一定的合理性和有效性。快速探索随机树（rapidly-exploring random tree， RRT）算法在路径规划领域得到了广泛的研究，针对RRT算法产生了很多改进。最早采用的是单棵树的搜索方式，研究人员提出偏向RRT、双向RRT、RRT*等搜索算法以进一步提高搜索效率。欧阳子路等[5]将双向RRT算法与速度障碍法相结合，得到了基于改进双向-RRT的USV自动避碰算法，使算法搜索树延伸失败次数减少，规划的路径更短、更平滑;杨左华等[6]提出一种基于新的线段定理和RRT*的算法，并通过与现有算法避障规划的比较说明该算法的有效性;庄佳园等[7]设计了一种基于改进RRT算法的局部路径规划方法，引入限定转角和距离启发信息，改进生长点和探索点的选择，提高了算法的速度;曹凯等[8]提出基于概率P双向RRT算法的移动机器人路径规划，所提算法在复杂环境中有着良好的收敛效果;徐娜等[9]将移动机器人的非完整约束条件与RRT算法相结合，实验表明该算法能有效解决存在非完整约束的机器人运动规划问题;宋金泽等[10]将非完整约束条件与双向多步扩展RRT算法相结合，用B样条曲线拟合控制点生成平滑路径，验证了算法的有效性。文献[11]的RRT算法考虑了无人艇的操纵特性，与本文的区别在于采用的RRT算法不同，而且没有对规划后的路径进行优化。在多任务点路径规划方面：文献[12]针对有障碍区域的多无人机多目标点路径规划问题，建立多约束优化模型，应用遗传算法进行求解;文献[13]针对机器人遍历多个目标点的路径规划问题，提出基于改进的粒子群算法与蚁群算法结合的路径规划方法，并在真实环境中验证其有效性;文献[14]基于电子海图数据建立环境模型，通过A *算法进行无人艇多任务点路径规划（未考虑无人艇的运动学约束），采用蚁群算法确定路径点的访问顺序。
随着研究的逐步深入，路径规划问题取得了丰硕的研究成果，但是也凸显出一些亟待解决的问题。例如，USV路径规划不仅要在空间内找到一条无碰撞路径，还应考虑USV的运动学约束，否则规划出的路径有可能在实际应用中不可行。RRT算法是基于采样的规划算法，适合处理含有运动学约束的路径规划问题。对于多任务点的路径规划，还应考虑任务点的访问顺序，减少航行距离。因此，本研究提出改进经典RRT算法，将其与USV运动学约束相结合，生成含有运动学约束的可执行路径曲线并确定任务点间距离，采用改进遗传算法优化多任务点的访问顺序，减少巡航距离。
1 USV运动模型及环境模型
1.1 USV运动数学模型
2.5 多任务点访问顺序求解
为解决多任务点的路径规划问题，将目标点的选择规划作为旅行商问题（traveling salesman problem， TSP）的一个分支。蚁群算法、模拟退火算法、遗传算法等都是目前求解TSP的有效方法。有些学者尝试结合两种或多种算法以克服各种算法的缺点。遗传算法的基本流程：首先对个体进行编码，生成初始种群;接着开始进化过程，用适应度函数判断个体优劣，优秀的个体将获得更多的选择、交叉和变异的机会;不断进行上述操作，直到满足迭代终止条件，得到最优解。本文采用改進的遗传算法求解多任务点的访问顺序，使USV遍历所有任务点后航程最短。方法如下：
（1）个体编码。应用路径表示法进行个体编码，个体即为任务点。如（T1，T2，…，Tn）表示从T1出发，依次经过任务点T2，T3，…，Tn-1，最后到达Tn。
（2）种群初始化。假定种群规模为N，其中0.8N个初始个体随机产生，0.2N个初始个体由贪心算法生成。首先随机选取一个任务点作为第一个基因，接着从余下的任务点中确定与第一访问点最近的访问点作为第二个基因，再从余下的任务点中找到距离第二访问点最近的点，以此类推，直到完成n个任务点的遍历。采用贪心算法[16]生成的个体在种群中的占比不大，不会影响种群多样性，但能提高种群的质量，有助于加快寻优速度。
（3）适应度函数选取。目标函数为个体路径总长度，取目标函数的倒数作为适应度函数。
（4）算子选择。采用轮盘赌和最佳保留策略选择算子。在保留最佳个体的同时引入新个体，提高算法收敛全局最优的可能性。
（5）算子交叉。采用两点交叉方法，在两个个体编码中设置两个交叉点，对两点间的基因进行互换。之后进行基因冲突检测，根据两组交换的基因建立映射关系，冲突基因经过映射，形成子代无冲突基因编码个体。
（6）算子变异。采用倒位变异算子[17]，在父个体中随机选取两个任务点并标记，使这两个任务点之间的基因倒序排列，并将两个标记的任务点相邻排列，产生一个新个体。
3 仿真实验
为测试USV多路径点路径规划算法的有效性，构建环境模型仿真验证。USV的任务点共11个，起始点坐标为（20 m，20 m），各任务点的坐标见图10。
利用第2.4节的改进遗传算法，确定多任务点访问顺序。每个个体采用11个路径点编码，初始种群大小设置为N=100，其中80个个体随机产生，20个个体采用贪心算法生成，迭代次数n=1 000。算法经过选择、交叉和变异操作，逐渐收敛，最终确定最优个体值为672，该个体路径点顺序为1→11→10→3→2→4→5→6→7→8→9。因此USV的最佳巡航距离为672 m。
在确定好各路径点间距离和访问顺序的基础上，规划出USV最佳巡航路径，见图11。该路径满足USV的运动学约束且巡航距离最短。
4 结 论
本文提出一种水面无人艇（USV）多任务点路径规划方法。首先建立了一种融合USV运动学约束的快速探索随机树（RRT）算法，将USV的运动状态信息融入算法，规划两个任务点之间满足USV运动学约束的路径，并得到两个任务点之间的距离。其次提出RRT优化路径算法，针对RRT算法的随机性特点，删减一些不必要的路径点，在一定程度上缩短路径长度，且避免过多的转向次数。最后通过改进遗传算法确定多个任务点的访问顺序，获得最短巡航距离，节约巡航成本。
参考文献：
[1] 张树凯， 刘正江， 蔡垚， 等. 无人船艇航线自动生成研究现状及展望[J]. 中国航海， 2019， 42（3）：
6-11.
[2] 于振中， 李强， 樊启高. 智能仿生算法在移动机器人路径规划优化中的应用综述[J]. 计算机应用研究， 2019， 36（11）：
3210-3219. DOI：
10.19734/j.issn.1001-3695.2018.07.0483.
[3] 随博文， 黄志坚. 基于改进A *算法的水面无人艇路径规划[J]. 舰船科学技术， 2019， 41（12）：
162-166. DOI：
10.3404/j.issn.1672-7649.2019.12.031.
[4] 范云生， 赵永生， 石林龙， 等. 基于电子海图栅格化的无人水面艇全局路径规划[J]. 中国航海， 2017， 40（1）：
47-52， 113.
[5] 欧阳子路， 王鸿东， 王检耀， 等. 基于改进Bi-RRT的无人水面艇自动避碰算法[J]. 中国舰船研究， 2019， 14（6）：
8-14. DOI：
10.19693/j.issn.1673-3185.01450.
[6] 杨左华， 王玉龙， 戚爱春. 基于改进RRT*算法的无人艇全局避障规划[J]. 舰船科学技术， 2019， 41（12）：
167-172. DOI：
10.3404/j.issn.1672-7649.2019.12.032.
[7] 庄佳园， 张磊， 孙寒冰， 等. 应用改进随机树算法的无人艇局部路径规划[J]. 哈尔滨工业大学学报， 2015， 47（1）：
112-117. DOI：
10.11918/j.issn.0367-6234.2015.01.017.
[8] 曹凯， 高佳佳， 李昂. 基于RRT优化算法的移动机器人路径规划[J]. 兵工自动化， 2018， 37（9）：
74-79. DOI：
10.7690/bgzdh.2018.09.019.
[9] 徐娜， 陈雄， 孔庆生， 等. 非完整约束下的机器人运动规划算法[J]. 机器人， 2011， 33（6）：
666-672. DOI：
10.3724/SP.J.1218.2011.00666.
[10] 宋金泽， 戴斌， 单恩忠， 等. 一种改进的RRT路径规划算法[J]. 电子学报， 2010， 38（2A）：
225-228.
[11] LOE A G. Collision avoidance for unmanned surface vehicles[D]. Trondheim：
Norwegian University of Science and Technology， 2008.
[12] 肖春晖， 邹媛媛， 李少远. 有障碍区域的多无人机多目标点路径规划[J]. 空间控制技术与应用， 2019， 45（4）：
46-52. DOI：
10.3969/j.issn.1674-1579.2019.04.006.
[13] 蒲兴成， 李俊杰， 吴慧超， 等. 基于改进粒子群算法的移动机器人多目标点路径规划[J]. 智能系统学报， 2017， 12（3）：
301-309. DOI：
10.11992/tis.201606046.
[14] WANG Yanlong， YU Xuemin， LIANG Xu. Design and implementation of global path planning system for unmanned surface vehicle among multiple task points[J]. International Journal of Vehicle Autonomous Systems， 2018， 14（1）：
82-105.
[15] 蒲红红， 黄海滨. 无人水面航行器全局路径规划方法研究[J]. 海洋科学， 2018， 42（1）：
93-105. DOI：
10.11759/hykx20171011008.
[16] 蒋然. 改进遗传算法在TSP問题中的应用[J]. 软件导刊， 2016， 15（12）：
127-129. DOI：
10.11907/rjdk.162168.
[17] 谢胜利， 唐敏， 董金祥. 求解TSP问题的一种改进的遗传算法[J]. 计算机工程与应用， 2002（8）：
58-60， 245.
（编辑 贾裙平）