英语原文共 25 页

（第1篇）具有安全距离和逼真转弯的最佳船舶导航限制

摘要：我们考虑最佳船舶导航问题，其中目标是在存在受安全距离和转弯半径约束影响的障碍物的情况下找到两个给定坐标之间的最短路径。这些障碍物可能是碎片，岩层，小岛屿，冰块，其他船只，甚至整个海岸线。我们提出了通过8邻接整数点离化和A /算法的利用获得的导航区域的适当加权有向图表示的图论解决方案。我们明确考虑以下三个条件作为转弯半径约束的一部分：（1）船的左右转弯半径不同，（2）船的转速在转弯时减小，（3）船舶需要沿着直线导航一定数量的格子边缘转弯。最后一个约束确保导航区域可以按任何需要离散化解析度。确定最佳（离散）路径后，我们将其平滑以模拟实际导航这艘船。我们在涉及100,000 DWT的冰导航示例中说明了我们的方法商船并通过在完整任务船舶处理中模拟船舶的路径来呈现概念验证模拟器。

第1章 简介

海运是一种主要的运输方式，占世界贸易量的90％左右。截至2011年，全球有超过10万艘海上商船每年运送8000万吨货物（根据联合国，2011年）。随着世界人口的增长和各国对国际商业的参与增加，海运航运作为一种低成本，可接受的风险和环境友好的交通方式继续扩大。在本研究中，我们考虑船舶导航问题，其中目标是在存在障碍物的情况下找到从给定起始点s到终止点t的（时间上）最短路径，其中（1）安全距离和（2） 转弯半径约束。我们将障碍定义为船舶在其航行中需要避免的任何形状或大小的任何区域。这些障碍物可能是碎片，岩层，小岛屿，冰块，其他船只，甚至整个海岸线。我们假设障碍物是静止的，即它们在船舶航行期间不移动或改变形状，并且我们不考虑诸如风，波浪或海流的环境影响。我们的方法涉及导航区域的定向8邻接整数点阵离散化以及在结果图上使用A /算法。

我们研究的一个新方面是有关于我们在考虑的下列因素：三个真实世界的船舶航行现象作为转弯半径约束的一部分：（1）船的左舷（左）和右舷（右）转弯半径不同，（2）船的转速在转弯时减小，（3）船需要在改变路线之前沿直线导航一定数量的格子边缘。第三个约束确保导航区域可以在任何所需的分辨率下离散化。这三个约束将被称为船转弯约束。此外，我们在以下意义上完全参数化转弯半径和安全距离约束：（1）不同（左和右）转弯半径和转速可以根据船舶的特殊特征规定，（2）可以根据障碍物的性质在障碍物水平上确定安全距离。我们的方法的实施需要对基础图进行非平凡的修改，以保持最优性。这些修改包括制作每个顶点的一定数量的副本，定义适当的邻域结构，以及相应地分配边长。确定最佳（离散）路径后，我们将其平滑以模拟船舶的实际（连续）导航。我们在具有100,000 DWT满载条件油轮的全任务船舶操纵模拟器中的冰导航示例中说明了我们的方法，并通过模拟船舶的实际路径提供概念验证。在这里，DWT代表载重吨，这是一个衡量标准油轮可以安全运载多少，包括货物，燃料，新鲜水和乘客。

关于确定性最短的文献存在大量文献路径和船舶导航-连续和离散设置。在大多数情况下，船舶导航的连续空间研究涉及复杂的微分方程和/或具有曲率约束的变化微积分。在存在大量任意形状的障碍物和船转弯约束的情况下，这些类型的方法通常不能很好地扩展。另一方面，现有的离散空间研究在忽略安全距离要求的同时强加了过于简单的转弯约束。据我们所知，我们的文献是文献中的第一项研究对于安全距离和船舵限制，如上所述在图形理论框架中，该框架也允许这些约束的完全参数化。

本文的其余部分安排如下：第2节概述了以前的船舶导航工作（两者都有在连续和离散的环境中）和审查现有的研究轮到限制。第3节正式定义了最佳船舶导航问题。第4节介绍了我们的导航方法详细包括晶格离散化，建模安全距离和转弯限制，以及最佳平滑路径。第5节展示了我们在冰上导航的方法例子和第6节提供了一个完整任务船的输出处理模拟器。摘要，结论和未来方向研究报告见第7节。最后，附录A提供了A /和Dijkstra算法的简要概述。

第2章 预先工作综述

在许多实际应用中，这是一项具有挑战性但又至关重要的任是找到轮式车辆，飞机和轮船的最短路径在不同的地形下受到各种操作限制。因此，路径规划问题和确定性最短路径。一般来说已经进行了广泛的研究; 特别是在运输科学，运筹学，人工智能和机器人技术领域。可以说，最常用的最短文献中的路径方法是Dijkstra算法（Dijkstra，1959）和A /算法（Hart等，1968,1972）。

杜宾斯的车（杜宾斯，1957年）就是前进的一个例子具有最大转角的轮式车辆。（注意这一回合角度是相对于车辆的当前方向而言a最大转弯角度约束可以转换为等效最小转弯半径约束。）Dubins的路径规划问题汽车主要是在非完整的背景下研究的路径规划（Bicchi等，1996）。这些类型问题通常被建模为偏微分方程系统在连续空间中并通过数值方法求解。然而，解决方案方法通常不会有效难以融入现实世界的物理约束（Takei等人，2010）。快速探索随机树（RRT）方法LaValle（1998）是Dubins的一种有效的连续空间算法可以应对各种环境限制的汽车。但是，RRT方法获得的路径不是必然是最优的，因为它是基于随机航路点的生成在导航过程中（Yang和Sukkarieh，2008）。据我们所知，目前还没有可用的非完整性可用于应用RRT方法的模型船舶导航。此外，结合不对称左和右转限制以及转入期间的速度降低RRT似乎相当困难。

在有障碍物的情况下进行船舶航行本质上是连续的-空间问题。但是，纳入现实的操作连续环境中的约束是一项具有挑战性的任务。因此，此前对该课题的研究主要集中在以各种方式对导航区域进行离散化。一个主要的离散化方法的优点是它允许使用完善和极其丰富的图形机制理论和网络流程。例如，法格霍特的工作等。（2000）关于船舶导航利用可见性图离散化图解仅在解决方案中部分构建提高效率的过程。 Lee等人的研究。（2002年），另一方面，使用预先指定的方式点进行离散化并采用改进的深度优先搜索算法。两者都没有这些研究考虑了任何转弯或安全距离限制。

关于船舶的转弯限制，将它们纳入船舶连续设定需要非线性机动方程（Fang et al。，2005; Bhattacharyya and Haddara，2006; Bakolas and Tsiotras，2011）并且一般都很困难（Hilten和Wolkenfelt，2000）。在图形理论设置中，通用最大转弯角度文献中的约束似乎局限于对称单边提前转弯限制。但是，这种限制意味着导航区域的分辨率基本上是决定性的通过转弯半径，反过来，消除了任何可能性使用更精细的分辨率来提高准确性。这些单边提前转弯约束以各种方式建模，例如（1）顶点复制（Caldwell，1961; Boroujerdi和Uhlmann，1998; Clossey等，2001; Soler等，2007; Albiach等人，2008），（2）修改Dijkstra算法（Solka等，1995; Gutierrez和Medaglia，2008），以及（3）转型原图（Villeneuve和Desaulniers，2005; Royset等，2009; Perugia等，2011; Geisberger等，2011;美高科技和Soler，2011; Pugliese和Guerriero，2012）。比较顶点复制方法和改进的Dijkstra算法道路网络可以在Vanhove和Fack（2012）中找到。我们的方法论是基于顶点复制技术的地方我们将每个顶点分成由船的方向标记的副本来自以及旅行的距离。因此，立即导航历史被纳入当前位置，其中反过来，可以实现定义的船转弯约束在第1节。

与我们密切相关的研究领域是任务规划军用飞机和无人机的航线（Zabarankin等，2002; Bartlett等，2005）。其中一些研究也是如此考虑最小转弯半径限制（Szczerba等，2000;Royset等，2009; Zabarankin等，2006; 爱迪生和志摩，2011）。然而，这种任务计划研究并不容易适用于船舶导航问题与飞机和飞行器有很大不同他们的技术和操作限制。特别是，空中任务规划研究往往考虑到有限的燃料储存限制，从根本上改变了结构潜在的问题，并使其计算难以处理的（Royset et al。，2009）。另一方面，这种燃料船舶导航中通常不存在容量限制。

第3章 最优的船舶导航问题

在本章中，我们正式定义了最佳船舶导航存在障碍时的问题，或简称OSN问题。不失一般性，我们假设导航区域是长方形。另外，我们只考虑多边形障碍物。由于多边形，这不应被视为限制近似可用于表示任何几何形状任何准确度（Wu和Leou，1993）。 我们也假设这些多边形作为自交叉多边形是非自相交的很容易转变成非自相交的没有改变障碍物的几何形状多边形表示。尽管如此，我们允许非凸和重叠多边形。术语多边形和障碍物应该是在本工作的其余部分中使用同义词。表1中的表示法描述我们的船舶导航模型。在模型中，一英里指到一海里，相当于1.151（陆地）里程或1.852公里。船的速度用结表示，有一个代表每小时一海里速度的结果。

表1 表征我们的船舶导航模型的符号

对于任何障碍物p 2 P，其缓冲区Bp被定义为该区域其边界由距离dp米的点组成从障碍物边界的最近点开始。在我们的模型中，我们要求船舶不进入任何缓冲区障碍，我们称之为安全距离约束。船离开了右转弯直径分别定义l*cl和l*cr其中“船”的垂直长度（LBP）以米为单位。LBP是指沿着水线的船长从杆的前表面到后表面船尾柱。这种用于指定船舶转弯半径的方法是典型的在海上航行（美国航运局，2006年）。该船舶在任何一点（相对于其当前方向）的转弯角度被约束为受曲率的上限具有相应左转和右转直径的圆。

然后将最优船舶导航（OSN）问题定义为如下：给定导航区域A内的一组障碍物P，a起点s和目的地点t，找到时间最短的具有直线（非转弯）速度k，转弯速度的船舶的路径k0，LBP-左转系数cl和右转系数cr subject安全距离和船转弯限制。请注意，由于减少转弯速度，时间最短的路径可能会有所不同比欧几里德距离最短的路径。

第4章 方法

在本节中，我们首先介绍一种计算算法每个障碍物周围的安全缓冲区。然后我们描述我们的格子离散化并解释船转的实施限制。接下来，我们将说明最佳（离散）路径可以平滑以模拟实际（连续）导航这艘船。

4.1 安全距离限制

如前所述，本研究假定（多边形）导航区域内的障碍物是静态的。事实上，然而，由于环境条件如风，冰块或锚泊船等障碍物可能会略微移动，波浪或海流。这些条件发生意外变化也可能导致船舶计划航线出现一定偏差。另外，可能是障碍物附近不安全的情况由于障碍的性质。例如，水下冰山的一些部分有时对近船很危险导航。由于这些原因，即使假设有障碍为了保持静止，我们允许在每个障碍物周围设置缓冲区。这些区域被定义为边界为的区域由距离最近的dp米的点组成指向障碍物p的边界。

图1 缓冲区多边形计算算法

我们计算缓冲区的方法基于定义每对边缘的一系列均匀间隔的顶点在原始多边形中，安全距离约束是满意。该过程的结果是另一个满足的多边形所有点的安全距离约束，我们称之为缓冲区多边形，用Bp表示障碍物p。步角由d表示，用于确定要定义的顶点的数量对于每对边缘。步进角d取3度我们的实施。作为一个例子，假设之间的角度障碍物的一对边缘是120度，这意味着这些边缘的法向矢量之间的角度是60度。对于得到的缓冲区多边形，我们定义均匀间隔60/3 =总共20个顶点，对应于该边缘对。

提供图1中的缓冲区多边形计算算法的伪代码如图2所示，是两个例子。 在剩下的这份手稿，我们只会关注缓冲区多边形正如这艘船在航行中需要避免的那样缓冲区的实际障碍。

图2 缓冲区多边形计算的两个插图

4.2 格子离散化分析

如前所述，确定最短路径连续设置中

资料编号：[5003]