帆船赛中迎风航段的随机航线优化

在帆船赛事中，导航员要设计出速度最快的行进路线，然而不稳定的风向给他们的规划带来了挑战。为此，我们设计了一套数学模型，这些模型通过统计分析风向变化，并采用随机优化方法来应对这种不确定性。我们还介绍了一种在2007年美洲杯中开发并投入使用的决策辅助工具，以及它对比赛结果产生的影响。

一、引言

在诸如美洲杯这样的高科技帆船赛事中，为了提升竞赛帆船的性能，数学工具的使用非常广泛。这不仅涉及到帆船的设计问题，比如船体的形状和帆的设计，还包括在风向和天气预测不确定的情况下的航线优化问题。相关研究可以参考Philpott等人2004年、Philpott和Mason 2001年以及Philpott 2005年的著作，还有Parolini和Quarteroni 2005年和Formaggia等人2008年的研究。本文讲述的是由瑞士帆船队Alinghi发起的一个项目，该项目由该队的导航员J. Vila提出，他邀请本文的作者们在2007年美洲杯期间与他们合作。项目的目的是帮助导航员在风力波动的情况下，规划出尽可能快的航线。实际上，帆船的运动依赖于风力的推动，而在特定的时间尺度上，风力是随机变化的。因此，自然而然地，我们会采用随机优化的方法。我们的目标是开发一个可以在他们竞赛帆船上使用的工具。在本文中，我们将描述比赛的组织方式，风力随机性的主要特点，我们如何开发风力波动的统计模型，以及如何构建适合随机优化方法的数学模型。最后，我们将介绍所取得的成果，以及这些成果如何被用来开发一个在Alinghi帆船上实际使用的“决策工具”。我们还会讨论这个工具是如何用于训练、赛前规划，以及在比赛过程中根据风的预测和实际条件提供实时建议和信息的。此外，我们还会提及由此项目激发的更多数学工作。

二、比赛基础

我们关注的帆船比赛是两艘船之间的对决，比赛的起始线与“平均风向”垂直。比赛包括以下几个阶段：首先，船只必须迎风航行至一个浮标，这个浮标被称为顶标；然后绕过这个浮标，接着顺风航行通过一个称为“下风门”的线；之后再次迎风航行至顶标，最后顺风航行通过终点线。由于帆船不能直接迎风航行，它必须采取之字形的航线，交替地向右和向左航行。当风从右侧吹向帆船时，帆船处于右舷受风状态，否则就处于左舷受风状态。从一种受风状态转换到另一种受风状态的动作被称为换舷。 每次换舷都意味着时间的损失，并且会导致帆船向比赛区域的不同部分航行，因此何时以及在何处换舷是导航员需要做出的关键决策。 鉴于风向和风速在时间和空间上以不可预测的方式变化，如下所述，以下基本问题没有简单的答案，并且被确定为项目的关键目标：

1. 船只应该从比赛路线的右侧还是左侧开始？

2. 船只应该在何时换舷？

我们决定将重点放在比赛的第一个迎风阶段，因为水手们认为如果他们能先到达这个标记点，那么他们很可能能够保持领先。因此，我们的目标是以尽可能快的速度将船只带到顶标。

图1 ：展示了帆船比赛的运行方式，包括迎风（upwind）和顺风（downwind）的阶段。图中标注了比赛的各个部分，如起始线、顶标（上风向的浮标）、下风门等。

三、风力

在对抗赛中，帆船的行为受到许多因素的影响，比如其设计、建造材料以及船员的体重，但风力和海况也扮演着重要的角色。在这两个因素中，风力占据主导地位，部分原因是它在短距离和时间内变化更大，但主要是因为它是帆船的动力来源。风力是一个三维的物理现象，它会随时间和空间变化。风力模型在天气预报和气候学中有着悠久的传统。在天气预报领域，重点是预测大风速度和风暴可能的未来路径。在气候学中，人们感兴趣的是盛行风的长期模式、风暴的发生以及极端风力。最近，风力发电的潜力激发了对风力模型的新一轮兴趣，例如风力发电厂的最佳布局、风力发电机的能量产量预测等问题已经得到了广泛的研究。另一方面，由于机动船的广泛使用，用于帆船比赛的风力预测迅速下降。此外，由于时间和地理尺度的相关性（分别大约是半小时左右和6乘6公里），帆船对抗赛的需求与这些其他领域的需求有所不同。 如今，所有的风力模型都包含一个重要的随机组成部分，因为即使基于详细的气象条件的短期预测也不是完全可靠的 。风力传统上是通过指南针上的风向来描述的，风速则可以通过一个二维向量方便地表示。因此，在二维空间和时间的每个点上，风力通过其方向和速度来表征。方向是以相对于北的角度来测量的，我们使用的习惯是顺时针方向测量角度，所以如果0°的风来自北方，那么90°的风就来自东方。图2中的第一个图表显示了2005年春末在西班牙瓦伦西亚附近一个特定地点测量的5小时期间的风向。图表非常不规则，但我们可以看到风向从大约110°开始，1小时后转向大约90°，然后在下午晚些时候又转回到大约120°。正如图2中的第二个图表所示，风速也表现出类似的特点。这两个图表都表明，风力变化包含三个主要组成部分：

图2 ：显示了在西班牙瓦伦西亚一个特定地点测量的5小时期间的风向和风速。左侧图表展示了风向的变化，右侧图表展示了风速的变化。这两个图表展示了风力在短时间尺度上的高频变化。

1. 高频变化。这是非常短时间尺度上的变化，只有几秒钟。由于风是湍流的，很难准确测量。用于测量风的仪器相当简单。例如，风向是通过风向标来测量的，风向标位于船的桅杆上，即使船锚定了，也会受到波浪的影响，因此任何单独的测量都存在很大的不确定性。图2中存在的一些变化可能是真实的，但大多数是测量误差。这些高频变化可以通过平滑处理来减少，我们通过取大约一些连续测量值的中位数来实现这一点。

2. 中频变化。这是几分钟时间尺度上的变化。数学模型捕捉这些波动非常重要，因为它们显著影响船只的运动。我们将通过一个随机过程来模拟这些变化，其参数将从历史风数据中估计得出。

3. 低频变化。这是几小时期间的变化，比如风从北慢慢转向东北。这是一种趋势，也需要从数据中估计得出。

在平滑高频变化后，风向和风速的典型样本路径如图3所示。这些图表覆盖了20分钟的期间，这是一个迎风段的典型持续时间。我们注意到，几度的变化对船来说很重要，风速1到2节变化也很重要。

图3 ：展示了经过高频变化平滑处理后的风向（γ）和真风速（TWS）在20分钟期间的变化。这些图表覆盖了迎风段的典型持续时间，展示了风向和风速的中频和低频变化。

关于赛场上风力条件的很重要的一点是，船上的水手们能够获得哪些信息。船上的水手们可以利用船上的仪器和他们的视觉观察。在比赛开始前最多5分钟，水手们可以与他们的气象团队进行沟通，这个团队由位于岸边以及分布在整个比赛路线上的气象学家组成：他们试图在通信中断前提供最新的天气信息。在比赛过程中， 对风力突发变化的目测观察可能很重要，但我们主要关注的是如图3所示的风力情况 。

四、船只建模

帆船是一个非常复杂的系统。在以往的美洲杯比赛中使用的典型单体帆船“美洲级”重量达到24吨，长度25米，桅杆高度35米，船员17人。大多数数学建模工作旨在确定船体的最佳形状，或者船体下的球状物，以及帆的形状（参见，例如，Parolini和Quarteroni，2005年；Formaggia等人，2008年）。虽然有关这些船只的动力学有一些信息，这些信息描述了帆船如何加速和减速，例如在换舷时，但幸运的是，我们的问题中最需要的信息是关于帆船的运动学，即其在稳态运动期间的速度。在我们的模型中，帆船由一组曲线来描述，这些曲线被称为船极（也参见Philpott，2005年）。

图4 ：展示了帆船的船极（boat polars），这是一组曲线，用于描述在不同风速和风向相对角度下船只的速度。图中假设风从顶部吹来，船只的速度由原点到与风速标记的曲线相交的点的距离给出。

这样一个例子如图4所示。在这张图中，风被假设从顶部吹来。对于给定的风速（6、10、16、20或30节），以及相对于风向的给定方位角α，船只的速度由从原点到与风速标记的曲线相交的点的距离给出。如果船只试图过于直接地迎风航行，那么这个速度就是零。图5左侧的图表显示了一个单一的船极曲线。请注意，如果目标是尽可能快地迎风航行，那么应该选择相对于风向的角度，该角度最大化了对垂直轴的投影。

图5 ：左侧图表展示了一个船极曲线，显示了不同风速下船只的速度。右侧图表展示了迎风航行的最佳角度αopt，这是船只应该选择的角度，以最大化对垂直轴的投影。

水手们都非常清楚这样一种角度的存在。最佳角度αopt取决于特定的帆船和风速。它可能从小风中普通帆船的大约45°变化到大风中竞赛帆船的大约30°。存在最佳角度αopt的一个重要后果是，在恒定风向下，帆船最优的航行方向总是与图6中所示的两条航线平行。这两条航线穿过顶标，与风向成±αopt的角度。在恒定风向下，帆船的最优轨迹简单地说就是沿着最初的航线（左舷或右舷，取决于它最初的航线）航行到航线上，然后换舷一次，直接航行到顶标。从图6中通过点B的水平线上的任何一点出发，船只到达顶标A的时间将是相同的。航行超过航线是没有优势的（尽管如果船只已经在航线之外，那么最佳的航线就是直接朝顶标航行）。

图6 ：展示了两条角度为αopt的laylines（航线），这两条线穿过顶标，用于指导船只在恒定风向下的最优轨迹。

在恒定风和迎风航段中，很容易确定哪艘帆船领先：只需将船只的正交投影到与风向平行的轴上，一艘船相对于另一艘船的领先距离与这两个投影之间的距离成比例。 在变化风中这种方法是不适用的 。

从上面的讨论中，我们可以理解在风向不恒定时，起始时选择向比赛场地的右侧或左侧行进的问题为什么如此重要。的确，想象两艘相同的船Y1和Y2从起跑线的中心B开始，风直接从顶标吹下来。Y1船向左行驶，Y2船向右行驶，两艘船都以相对于风向的±αopt角度航行，如图7所示。几分钟后，两艘船仍然并驾齐驱，分别位于图7中显示的点A1和B1。现在假设风向突然改变，开始从西北方向吹来，与之前的风向成θ<0的角度。在此之后，我们必须使用新风的轴线来确定哪艘船领先，从图7可以清楚地看出Y1现在远远领先于Y2。

图7 ：展示了在风向变化一次的情况下，两艘船的路径。这个图表说明了风向变化对船只位置的影响，以及为什么预测风向变化和使用随机优化是有用的。

如果风保持恒定直到两艘船到达顶标，那么Y1将在A2处换舷，Y2将在B2处换舷，Y1将首先到达顶标，而在那一刻，Y2将处于图7中显示的B3位置。 这个简单的例子展示了风向变化的影响，这就是为什么通常会想办法来预测它们，以及为什么随机优化可能是有用的。

风速的变化也很重要：风速越高，船只的速度就越高，尽管这种关系不是线性的。此外，最佳角度αopt取决于风速，所以风速会影响船只的航线。这给出了想要在比赛场地的特定一侧开始的另一个原因：预计那一侧会有更高的风速。结果表明，这很难预测，我们在这里不会讨论这个问题。最后一个关键问题是模拟船只换舷。原则上，在换舷过程中，船只沿着一条曲线路径航行，开始时减速，然后再加速 。恢复到稳态所需的时间大约是30秒，这与20分钟的比赛时间相比是小的 。 关键问题是换舷过程中损失的时间。这取决于风速，从大风中的大约4秒到小风中的大约9秒不等。 也就是说，在恒定大风中，一艘额外换舷的船只会比没有换舷的船只晚到顶标4秒。在我们的模型中，我们将考虑换舷是瞬间的，并我们将在航行时间中加上一个换舷罚时，以考虑换舷过程中损失的时间。这个罚时取决于风速（见表1）。

表1：作为风速函数的换舷罚时

五、 一个完全离散的模型

在前一节中，我们了解到在恒定风中：

• 当处于航线内时，船只总是应该以相对于风向的±αopt角度航行；

• 换舷涉及到时间罚时；
  

• 风是变化的。

本节我们提出了一个简单的完全离散的数学模型，该模型依然能够捕捉到这些主要特征。我们首先设想在比赛场地上有一组等距的水平线，这些线通过ΔX米间隔，第一条线通过顶标。我们还假设风速是恒定的，风向是一个在两个状态±γ之间切换的两状态马尔可夫链。风向的转变恰好发生在船只位于这些水平线上的时刻。我们还假设在风向转变之间，风向是恒定的，船只以±αopt角度，不换舷地前进到下一条水平线。然后风可能转变或不转变，观察到新的风向，船只决定是否换舷。如果船只在风向转变之间触及到航线，那么它可以换舷以保持在航线上（这种特殊操作被称为沿航线换舷），然后船只继续前进到下一条水平线。这个过程一直重复，直到船只到达顶标。

图8 ：展示了选择角度γ的方法，这个角度用于确定船只在风向变化时的最优航线。

这个模型并不十分令人满意，因为船只在水平线上可能的位置数量可能会随着距离顶标的距离呈指数增长。然而，对于某些角度γ的选择，这个数量会呈线性增长。实际上，观察图8，我们看到如果我们选择γ，使得：

并设定ΔY = (1/3)tan(γ + αopt)，那么一艘左舷受风的船只当风向为−γ时，其y坐标将增加2ΔY单位；当风向为+γ时，增加3ΔY单位。一个满足上述等式的γ0角度是 γ0 = arcsin(sin(2αopt)/5)/2，对于αopt = 30°来说，这个角度非常接近5°。选择γ = γ0时，船只能访问的节点如图9所示。注意，船只总是以±αopt角度相对于风向航行，除了一种情况：如果船只在外侧航线上，例如外侧左舷航线，对应风向为+γ，当风向转变为−γ时，船只发现自己处于当前风的航线外（这是一个不利的情况）；在这种情况下，我们假设船只直接朝顶标航行，速度为Ve ≥ Vopt。

图9 ：展示了在满足特定条件时，船只可以航行的节点，这些节点构成了一个离散的比赛场地模型。

我们现在可以将问题表述为一个马尔可夫随机控制问题，其中风是一个两状态马尔可夫链，风向变化一步之后的概率为p ∈ ]0, 1[。船只的有限状态空间由图9中的节点集合构成。在每一步，都有一个有限的允许动作集合：继续航行、换舷，以及对于靠近航线的节点，可以执行沿航线换舷并跟随外侧航线。每个动作的一步成本（从一个节点到下一个节点的航行时间）是使用速度Vopt、Ve以及简单的三角考虑（如果相关的话，包括换舷罚时）来计算的。最后，我们假设船只的目标是最小化其到达顶标的预期航行时间。为了计算最优策略，让T(w，h，x，y)表示从位置(h, x, y)出发，在当前风向为w时的最小预期航行时间。显然，在顶标处，我们有T(w，h，0， 0) = 0。现在让 t w , h , x , y , o 表示一步成本，即从位置(h, x, y)到下一个节点的航行时间，如果风向为w并且选择了动作o。我们使用贝尔曼方程和归纳法来计算所有(w, h, x, y)的T(w，h，x，y)，如下所示（参见，例如，Puterman, 1994, Chapter 4或Cairoli和Dalang, 1996）。对于所有的w，对于x = 1, 2,…, N，对于所有在x线上的位置(h, x, y)和所有动作o：

并设定

在这些公式中，~y表示船只在x - 1线上达到的新位置，假设它从位置(h, x, y)开始，风向为w，船只选择了动作o，~h表示新位置的受风状态。当x = 1时，这个位置是~y = (0， 0)，所以此时T(±w，~h，x - 1，~y) = 0。对于x = 1, 2,…, N，T(±w，~h，x - 1，~y)在前一步已经计算过。然后，位置(h, x, y)在风向w下的最优动作Oopt是：

如果有多个动作满足这个等式，我们通过给动作集合设置优先级来选择其中一个。实现上述算法的数值计算是相当直接的。