·344. 智能系统学报 第10卷 到达目标的最优或次最优路径（无障碍物路径）。 1)目标：1个远程静态路径点。 根据对环境的获知程度，路径规划分为全局路径规 2)障碍物：视一定范围内的水面船舶为运动障 划和局部路径规划，在线路径规划是一种局部路径 碍物，通过传感器获得其速度、航向和位置。 规划，因为部分环境是未知的。 3)USV运动模型：包含运动学和动力学，应用 无人水面机器人在海洋中在线路径规划的特点 其在仿真中可实时模拟USV的运动状态。 是：1)海洋环境具有动态、突发性、不可预测性。2) 4)假设条件：因为船体本身具有的惯性比较 USV具有6个自由度、偏航、前进、横移，也会出现 大，所以假设极短的规划时间△1内，障碍物保持匀 横倾、纵倾，体积小、速度快、灵活性高、瞬时的失误 速运动，即USV相对运动障碍物的速度改变量等于 可能造成无法弥补的损失等运动特性。3)USV预 USV自身的速度改变量。 先定义好的航线和驾驶规则。常用的在线路径规划 由此，在线路径规划的任务即是在每个规划时 算法采用局部避障算法结合全局规划算法，如障碍 间间隔搜索出最优的速度矢量增量，使其既能遵守 物边界追踪结合融入A·搜索算法[山。然而这种方 COLREGs规则躲避运动的障碍物，同时能搜索到达 法并没有考虑国际海上避碰规则公约(convention 目标的全局最优或次最优（无碰撞）的优化路径。 on the international regulations for preventing collisions 1.2融入COLREGs规则的改进速度避障法 at sea,COLREGs)I。COLREGs指出了当存在碰 基于线性速度障碍物LV-Obstacle的一阶算法 撞的危险时，应该采取的避碰行为。当USV与其他 原理在文献[7]有详细的说明，本文在此基础上进 船舶相遇时，其导航算法必须遵守COLREGs,才能 行改进，提出基于COLREGs规则避障的改进速度 安全躲避其他船舶，这样其他船舶上的驾驶人就能 避障算法。速度避障法二维原理图如图1所示。将 预测它所采取的安全行为。许多学者提出了遵守 USV缩小为一个点U,障碍物膨胀为一个圆，圆心为 COLREGs的导航方法，如模糊逻辑[)、区间优化4)。 点O,两者速度矢量分别为"。和v。。相对速度为 然而这些算法对多个COLREGs规则的应用不是很 vuo=vu-vo。USV与障碍物中心的连线为Lo,相 好，而且在实时性需求方面并不能达到理想。Yo- 对速度'o与Lo的夹角为yo,USV与障碍物圆的 shiaki等[s)将COLREGs规定的可行速度区与速 2条交线分别为UN和UM,相对速度'o与UN和 度障碍区同时作为约束条件，以交叉检测的碰撞 UM的夹角分别为△yio和△yto,相对速度"o延长 时间和下个路径点的期望速度作为代价函数，在 线与障碍物圆的最短交点为D。 速度-航向(-0)空间搜索最好的速度矢量。这 种方法能快速有效地避开障碍物，然而他们也指出， 使用的速度避障法只是一种局部规划器，要想实现 远程距离的路径规划必须加人全局规划器。COL D 0 REGs本身就包含有避碰行动信息，与速度避障法 能非常好的融合，同时使速度避障法更好地运用于 M USV与船舶会遇的避碰行动中，使避碰行动完全合 理合法。祖迪等[采用MLP(mixed-integer linear programming)进行移动机器人的路径规划，将移动 机器人的本体动力学和速度避障法角度约束结合， 取得比较好的效果。 图1速度避障法二维原理图 Fig.1 Schematics of velocity obstacle 本文对USV在动态环境下进行在线路径规划 进行研究，采用基于速度避障法的局部规划器规避 1.2.1相关定义 障碍，基于MLP的全局规划器实现距离时间的优 1)膨胀半径：R=V,/y,碰撞半径等于会遇船 化，使规划的路径既能遵守COLREGs规则，安全地 舶的安全距离。安全距离取决于相对速度和转向 避开障碍，同时获得全局路径优化。 率，见文献[8]。 1 改进速度避障法 2)避碰区(collision cone,CC): 1.1问题描述 Co={"o1Lo∩0≠⑦] 本文研究的USV在线路径规划问题如下： 即所有导致USV与障碍物碰撞的相对速度'o,它 本质为相对速度的速度集。到达目标的最优或次最优路径（无障碍物路径）。 根据对环境的获知程度，路径规划分为全局路径规 划和局部路径规划，在线路径规划是一种局部路径 规划，因为部分环境是未知的。 无人水面机器人在海洋中在线路径规划的特点 是：１）海洋环境具有动态、突发性、不可预测性。 ２） ＵＳＶ 具有 ６ 个自由度、偏航、前进、横移，也会出现 横倾、纵倾，体积小、速度快、灵活性高、瞬时的失误 可能造成无法弥补的损失等运动特性。 ３） ＵＳＶ 预 先定义好的航线和驾驶规则。 常用的在线路径规划 算法采用局部避障算法结合全局规划算法，如障碍 物边界追踪结合融入 Ａ ∗ 搜索算法［１］ 。 然而这种方 法并没有考虑国际海上避碰规则公约（ ｃｏｎｖｅｎｔｉｏｎ ｏｎ ｔｈｅ ｉｎｔｅｒｎａｔｉｏｎａｌ ｒｅｇｕｌａｔｉｏｎｓ ｆｏｒ ｐｒｅｖｅｎｔｉｎｇ ｃｏｌｌｉｓｉｏｎｓ ａｔ ｓｅａ， ＣＯＬＲＥＧｓ） ［２］ 。 ＣＯＬＲＥＧｓ 指出了当存在碰 撞的危险时，应该采取的避碰行为。 当 ＵＳＶ 与其他 船舶相遇时，其导航算法必须遵守 ＣＯＬＲＥＧｓ，才能 安全躲避其他船舶，这样其他船舶上的驾驶人就能 预测它所采取的安全行为。 许多学者提出了遵守 ＣＯＬＲＥＧｓ 的导航方法，如模糊逻辑［３］ 、区间优化［４］ 。 然而这些算法对多个 ＣＯＬＲＥＧｓ 规则的应用不是很 好，而且在实时性需求方面并不能达到理想。 Ｙｏ⁃ ｓｈｉａｋｉ 等［ ５］ 将 ＣＯＬＲＥＧｓ 规定的可行速度区与速 度障碍区同时作为约束条件，以交叉检测的碰撞 时间和下个路径点的期望速度作为代价函数，在 速度－航向（ ｖ⁃θ ） 空间搜索最好的速度矢量。 这 种方法能快速有效地避开障碍物，然而他们也指出， 使用的速度避障法只是一种局部规划器，要想实现 远程距离的路径规划必须加入全局规划器。 ＣＯＬ⁃ ＲＥＧｓ 本身就包含有避碰行动信息，与速度避障法 能非常好的融合，同时使速度避障法更好地运用于 ＵＳＶ 与船舶会遇的避碰行动中，使避碰行动完全合 理合法。 祖迪等［６］ 采用 ＭＩＬＰ （ ｍｉｘｅｄ⁃ｉｎｔｅｇｅｒ ｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ）进行移动机器人的路径规划，将移动 机器人的本体动力学和速度避障法角度约束结合， 取得比较好的效果。 本文对 ＵＳＶ 在动态环境下进行在线路径规划 进行研究，采用基于速度避障法的局部规划器规避 障碍，基于 ＭＩＬＰ 的全局规划器实现距离时间的优 化，使规划的路径既能遵守 ＣＯＬＲＥＧｓ 规则，安全地 避开障碍，同时获得全局路径优化。 １ 改进速度避障法 １．１ 问题描述 本文研究的 ＵＳＶ 在线路径规划问题如下： １）目标：１ 个远程静态路径点。 ２）障碍物：视一定范围内的水面船舶为运动障 碍物，通过传感器获得其速度、航向和位置。 ３）ＵＳＶ 运动模型：包含运动学和动力学，应用 其在仿真中可实时模拟 ＵＳＶ 的运动状态。 ４）假设条件：因为船体本身具有的惯性比较 大，所以假设极短的规划时间 Δｔ 内，障碍物保持匀 速运动，即 ＵＳＶ 相对运动障碍物的速度改变量等于 ＵＳＶ 自身的速度改变量。 由此，在线路径规划的任务即是在每个规划时 间间隔搜索出最优的速度矢量增量，使其既能遵守 ＣＯＬＲＥＧｓ 规则躲避运动的障碍物，同时能搜索到达 目标的全局最优或次最优（无碰撞）的优化路径。 １．２ 融入 ＣＯＬＲＥＧｓ 规则的改进速度避障法 基于线性速度障碍物 ＬＶ⁃Ｏｂｓｔａｃｌｅ 的一阶算法 原理在文献［７］有详细的说明，本文在此基础上进 行改进，提出基于 ＣＯＬＲＥＧｓ 规则避障的改进速度 避障算法。 速度避障法二维原理图如图 １ 所示。 将 ＵＳＶ 缩小为一个点 Ｕ，障碍物膨胀为一个圆，圆心为 点 Ｏ，两者速度矢量分别为 ｖＵ 和 ｖＯ 。 相对速度为 ｖＵＯ ＝ ｖＵ － ｖＯ 。 ＵＳＶ 与障碍物中心的连线为 ＬＵＯ ，相 对速度 ｖＵＯ 与 ＬＵＯ 的夹角为 γ ＵＯ ，ＵＳＶ 与障碍物圆的 ２ 条交线分别为 ＵＮ 和 ＵＭ ，相对速度 ｖＵＯ 与 ＵＮ 和 ＵＭ 的夹角分别为 Δγ Ｒ ＵＯ 和 Δγ Ｌ ＵＯ ，相对速度 ｖＵＯ 延长 线与障碍物圆的最短交点为 Ｄ。 图 １ 速度避障法二维原理图 Ｆｉｇ． １ Ｓｃｈｅｍａｔｉｃｓ ｏｆ ｖｅｌｏｃｉｔｙ ｏｂｓｔａｃｌｅ １．２．１ 相关定义 １）膨胀半径： Ｒ ＝ Ｖｒ ／ γ ，碰撞半径等于会遇船 舶的安全距离。 安全距离取决于相对速度和转向 率，见文献［８］。 ２）避碰区（ｃｏｌｌｉｓｉｏｎ ｃｏｎｅ， ＣＣ）： ＣＵＯ ＝ ｛ｖＵＯ ｜ ＬＤＯ ∩ Ｏ ≠ ∅｝ 即所有导致 ＵＳＶ 与障碍物碰撞的相对速度 ｖＵＯ ，它 本质为相对速度的速度集。 ·３４４· 智 能 系 统 学 报 第 １０ 卷