英语原文共 8 页

一种用于海港领域水面无人艇监控的实时路径规划与避障的三层框架结构

摘 要

近年来，无人驾驶工具在水下和海洋领域的应用正在显著增加。自动驾驶工具(如水下潜航器和滑翔机)或远程操作的(如水下机器人)目前用于执行许多不同的水下任务，例如检查水下管道，在水下天然气或石油平台上执行维护、干预工作，收集环境或海洋数据，对遗址进行调查。随着水下潜航器，水面无人艇(USV)的发展，也见证了来自机器人社区日益增长的兴趣，特别是为了执行监视目标的任务，例如在港口或其他“关键”站点进行巡逻、维护和防御入侵者。配备有摄像机或声纳等传感器的自动化船舶所带来的潜在好处非常明显，因为它们可用于快速识别未知雷达轨道的威胁程度，而不会使任何操作人员面临潜在的威胁。然而，与水下情况不同的是，USV必须面临避开其他船只的问题，因为在大多数情况下，其他船只都是有人驾驶的。这是非常重要的一点，特别是在这类应用中，自动化船只必须迅速向可能的威胁移动，同时避开在海港地区正常作业的所有其他船只。不幸的是，在目前的技术水平上，仍然缺乏一种可靠的方法来避开其他船只，也没有有效和准确的障碍探测传感器。本文研究的USV用于安全应用的情况下在一个港口制定一个解决方案，可以实现实时避障，在危险情况下可以在尽可能快地达到其目标的同时，保证其他船只的安全。提出的解决方案是基于三层的分层体系结构:第一层计算全局已知的先验路径，考虑静态障碍；第二层是利用运动障碍物的运动学数据以局部最优的方式修改这条路径(在某些假设条件下)；而最后一层是被动地避免当这些数据不可用时的障碍。

本文的主要内容如下：

第一部分介绍了国内外的研究现状；第二部分将讨论对静态障碍物避让的第一层架构和方法；第三部分将重点介绍移动障碍物和所提出的避让算法，同时也给出了关于整体架构可实现性能的许多不同的详细仿真结果。最后，结论部分还将指出一些有待研究的问题和未来的工作方向。

一、绪论

在港口保护的场景中，人们希望监视港口的交通，以便发现并最终拦截可能对保护区内的敏感目标构成威胁的入侵者。为了达到这个目的，很明显，这个区域必须被某种传感器覆盖，以便发现这种入侵者。通常，这需要通过正确定位雷达周围的被保护区域，但也有雷达覆盖不全的情况，这就解释了为什么需要配备适当的传感器(红外、相机、声纳等)的水面无人艇(USVs)。巡逻的USV可以很好地填补雷达没有覆盖区域的空白。使用USV的另一个原因是，它们增强了整个系统识别和分类轨道的能力，因为它们可以配备摄像头，可以接近未分类的船只。最后不得不提的是，他们可以拦截可能的威胁。

同样显而易见的是，在有人驾驶的其他船只的区域内作业，必须特别注意这种无人驾驶船只行驶的安全。一方面，需要保证该地区的安全，防止可能的威胁，因此需要快速拦截他们。另一方面要确保不伤害在该地区移动的任何其他友军目标。根据最近对Caccia^[1]的一项调查，在目前的技术水平下，USV的避障仍然缺乏可靠的方法和有效且准确的障碍物探测传感器。

麻省理工学院海洋工程系已在这方面进行了工作，特别是关于《道路规则》(1972年《防止海上碰撞国际规则》- COLREGS^[2])的执行情况。他们使用四艘kayak scout(用于海洋和海底测试的水面舰艇)^[3]，在基于行为的控制框架中测试了一种新的多目标优化方法——区间规划^[4]，在基于行为的控制框架^[5][6]实现（或接近）所谓的符合COLREGS标准的系统。

另一项有趣的工作是由圣地亚哥的空间和海战系统中心进行的^[7][8]。在他们的工作中，他们提出了路径规划和避障问题的两层递阶方法。因此，该规划器被分为两部分：考虑避障(OA)规划器(对路径进行远区域决策)和反应性OA规划器(对之前定义的路径进行近区域更改)。审慎的OA规划师使用来自图表服务器和雷达服务器的信息。它构建了一个二维(2D)的障碍图，本质上是一个占用网格，通过将环境划分为一个离散网格，并为每个单元位置分配一个值，表示被一个障碍物占用或不占用的概率。图中充满了来自图表服务器的固定障碍物，然后使用A*算法^[9]找到问题的解决方案。反应性OA规划器使用一种基于行为的公共环境模型方法，即每个避碰行为都为使船舶转弯的行为投票，而跟随行为的路径则为使船舶保持在计划路径上的行为投票。

然而，对于移动障碍，Canny和Reif^[10]表明，在有移动障碍物存在的情况下，具有有界速度的平面中的点的运动规划是一个非确定性多项式（NP-hard）；Aggarwal和Fujimura^[11]表明，通过添加第三维时间和绘制坐标位置可以找到更优的解。沿着三维（3D）结构的移动障碍，这个想法在我们的碰撞检查例程的实现中被采用。

为了处理移动障碍物，在[7]，[8]中，作者创建了一个投影障碍物区域(POA)，这是一个移动障碍物在未来可能占据的区域：从3D到2D的转换。然后，他们通过计算两个物体在各自路径上的最小距离，来确定移动的障碍物在某一特定时刻将构成的最大威胁(当障碍物位于距离USV最近的位置时)。然后该区域被保存到占用网格中，规划可以像只有静态障碍一样进行。从三个维度到两个维度的截断意味着一个解决方案可以在几秒钟内找到，但是不能保证解决方案是最优的或总是完全可以接受的。为此，仍然需要一个非常快的反应性避障系统，使反应系统的工作变得更容易，但是会增加避碰的可能性。这与在^{[12 ]}中所做的非常相似。

我们的方法侧重于为紧急情况争取最短的时间求取路径，因此特别强调设法设计最佳的避碰策略。为了使这个问题易于处理，已经做了一些合理的假设。因此，本文的主要贡献是如何计算全局路径的局部最优修正以避免碰撞。

所提出的路径规划器的结构是一个三层的结构。第一层负责该区域中的静态障碍物，第二层利用移动障碍物的运动学信息以最佳方式对路径进行局部修改，而最后一层反应性地应对非常短期的避碰状况。第一、二层侧重于规划，可以在船上或在远程控制站上执行，这取决于必要的运动学数据在船舶上可用，而最后一层是纯粹的反应，直接在UVS中实现的。显然，前两层的目标是确保最后一层必须尽可能地发挥作用。

论文的内容如下：第二节，解释第一层，考虑到静态障碍；紧接着的第三节，介绍了局部最优避碰算法；第四节总结了得出的一些结论，并对今后的工作进行了展望。

二、第一层：静态障碍

如前一节所述，这一层的目标是在空间中规划一条与已知的静态障碍物无碰撞的路径，如海岸、岛屿、港口等。它还可以考虑用户决定禁止导航的区域。这个问题在机器人文献中是众所周知的，并且在这一层中已经使用了可视图方法。

可视图法是一种在文献中既定的技术，其可追溯于文献中^[13]。它定义了一个障碍物是多边形，而机器人是空间中的一个点。为了找到无碰撞路径，需要用以下方式进行：构造可视图VG（N，L），其中N包括V，S，G。V是障碍物顶点集合，S和G是起始点和目标点。L是一组边（n_i，n_j），n_i，n_j。N在n_i和n_j之间存在不与任何障碍相交的直线。可视图法的一个例子在图2可以看到。

图2 可视图的一个例子：S是起点，G是目标点，粗线是计划路径

此时，为了找到无碰撞路径，可以应用S和G之间的任何图形遍历方法，并且所得到的轨迹不会交叉任何障碍物，尽管该解决方案有时可以包含某些障碍物的边缘。在实际情况下，点式机器人的假设不正确，这意味着会发生碰撞。为了克服这个问题，代表真实障碍的多边形必须大于它们，这样，给定机器人的任何方向，如果机器人位于多边形的任何边缘，就不会发生碰撞。

为了使用可视图法，工作区域内的障碍物必须转化为多边形。用户必须选择在空间中的点作为多边形的候选顶点，然后程序自动确定哪些点被连接，利用什么是海，什么不是的信息。这个过程的输出可以在图3中看到。

结果图是通过众所周知的Dijkstra算法^[14]求解的。这个操作的结果是，对于每个目标顶点，一个数组包含每个顶点的下一个要访问的顶点，以便最佳地到达目标。这种结构最小化了保持所有结果路径可用所需的内存量。注意，这个操作的代价是O(n²)，单位是顶点的数量，在启动时只执行一次。

（a） （b）

图3 （a）红点是候选顶点；（b）可视图化结果

为了找到两个点（S，G）/N之间的通用问题的解决方案，必须以下列方式进行：找到直接连接到S和G的所有顶点，然后最小化下面的表达式。

（1）

其中C_a,b是从a到b的代价；集合(2)是P直接连接到S，集合(3)是Q直接连接到G。

（2）

（3）

是Dijkstra的算法输出。最优路径是S、 、G。

通过使用该技术，在线上必须进行的唯一操作是确定图上的哪些点连接到S和G，在可视图的顶点数量上具有O（n）的成本。

这个过程的结果是船舶必须跟随一组路径点以达到目标。图4示出了计划路径的示例。

图4 路径规划的例子：黄色代表当前的片段，绿色片段是已经计划好的下一个片段

三、避障轨迹算法

从现在起，在一个USV的情况下，其既需要到达由集中控制站给予的一个目标，又要处理固定传感器的信息，也就是说，船的位置和瞬时速度（从现在开始的雷达轨迹）被考虑。可以适当地利用该信息来修改USV的本地路径，以避让移动目标。

A.边界框

为了继续，让我们定义一个轨道的边界框的概念，即矩形，它定义了USV应该避免的区域，以保证与移动物体的安全距离。

图5 一个轨道的边界框，带有突出显示的航迹方向

（4）

其中（x_c，y_c）是边界框的中心，L是长度，W是的宽度，alpha;是航迹方向。

B.一个简单的避碰算法

避免与此边界框碰撞的简单算法是将起始位置S（USV实际位置）和本地目标G集成到由边界框的四个边构成的图中，通过添加从S或G开始的边，并结束于不与任何边相交的边界框的顶点之一。然后，该解将是从S到G的任何路径，这可以通过任何图遍历算法来获得，例如Dijkstra算法。图6出示了这种算法的一个实例。

图6 一个简单的避碰算法的例子，该图被建立，然后用A*算法遍历以获得最短路径

这种方法可以很容易地扩展到多个障碍：对于每个障碍跟踪建立边界框，然后添加任何从一个边界框顶点到另一个边界框顶点的连线，从S和G再到边界框上的顶点，从S到G然后消除交叉边缘与原来的边界框。这种操作的结果一定是遍历的结果图。如图7所示。

很容易看出，这种算法具有较大的次最优性，因为它没有考虑轨迹或USV的任何运动学特性。可能在某些情况下根本不需要偏离当前航向，但无论如何，该算法都会偏离当前航向。

图7 多个轨迹和遍历结果图

C.局部最优避碰

图8 截距问题的图式化

为了使问题易于处理，假定USV以固定的速度移动，并且该速度高于任何目标的速度。这是一个限制性的假设，但也是直观的，因为就安全相关的应用进行讨论，不难想象，在紧急情况下USV可以以很高的速度移动（比如拦截未知的雷达轨道）。此外，假设USV是最快的，而障碍物的边界框不相交，那么减速（因此改变速度）并让障碍物移开并不比以最大速度避让障碍物的选择更好。此外，目标的速度被假定为常数。显然，目标越远这个假设就越不可靠，该算法只适用于与USV相当接近的目标，因此只适用于局部情况。

为了解释这个算法，让我们从下面的子问题开始：在空间给定一个点，以固定的航向和速度移动，航向角theta;多大，如果存在，这样另一个点以固定速度能拦截吗?

两点的运动方程是：

（5）

（6）

其中下标1表示必须计算其航向的船舶，而2表示移动目标。在0时刻，前者是在（0，0），后者是（L，H）。图8图解了这个问题。可以如下计算：

（7）

变量域

（8）

（a） （b）

图9 只有可视的顶点给出不与边界框（蓝色）相交的轨迹；其他顶点给出不可行轨迹（红色）

（9）

方程（8）是为了能够找到一个角度而必须满足的约束。正如可以看到的，如果V1＞V2总是存在一个解，而在另一种情况下，取决于问题的初始条件，即角度k，可以有一个解或不存在解。

如果L＝0，则可以计算截距或等效的必要时间。

（10）

（11）

通过（5）将t=，可以很容易地计算出截取点的位置。

（12）

（13）

必须指出，问题（5）可以有第二个解决方案。

服从相同的约束（8）。然而，对于大多数情况下（总是如果V1＞V2），该解将导致t＜0，因此是不可行的解。

现在让我们再考虑一下移动目标及其边界框问题。对于每个顶点，现在可以计算截距的角度theta;。可以证明，只有0时刻上的可见顶点将给出与边界框不相交的角度。图9在静态情况下显示了这一点，并且在任何时间都可以有两个或三个可见顶点。

资料编号：[4997]