8.3 移动圆盘
(Moving a Disk)

现在我们开始研究运动规划算法，其目标是找到任何一条路径，如果存在的话，不一定是最短路径。我们将分三个复杂度递增的阶段进行: 移动圆盘、 平移凸多边形(8.4 节)、 带旋转的线段移动(8.5 节)。只有在最后一节中，我们才会考虑多种不同的方法。

假设机器人 \(R\) 是一个以 \(s\) 为圆心的圆盘，目标是移动到以 \(t\) 为圆心的位置，且在运动过程中不与任何障碍物发生碰撞。 如前所述，障碍物是不相交的多边形。图 8.4(a) 所示的路径不是一条可行路径，因为机器人太宽，无法通过所示的通道。 有一种很好用的视角可以直观地看出这条路径为何不可行，而且这种视角也可以很好地推广到更复杂的情形。设 \(r\) 是移动圆盘 \(R\) 上的一个参考点，比如它的圆心。 \(r\) 不能过于靠近任何特定的多边形 \(P\)。实际上，\(r\) 与 \(P\) 之间的距离不能小于圆盘半径 \(\rho\)。这启发我们考虑一个"膨胀(expanded)"的障碍物 \(P^+\)， 它被向外扩大了 \(\rho\)，方便我们分析点 \(r\) 的运动。实际上，我们将机器人缩小为一个点，并将障碍物扩大 \(\rho\)，就可以将问题简化为在障碍物之间移动一个点。

对于任何给定的 \(P\)，膨胀的 \(P^+\) 是什么样子的呢? 其边界可以通过追踪圆盘沿 \(P\) 的边界移动时 \(r\) 的轨迹来获得，即 \(\partial P\)。如图 8.4(b) 所示。 显然，如果 \(r\) 保持在 \(P^+\) 之外，那么 \(R\) 就不会与 \(P\) 相交。如果 \(r\) 在 \(P^+\) 内部，那么 \(R\) 必然与 \(P\) 相交。 图 8.4(b) 清楚地表明，(a) 中的路径是不可能的，因为膨胀后的障碍物在通道中重叠了。

我们对 \(P^+\) 的描述有些模糊。我们可以利用两个点集的"闵可夫斯基和(Minkowski sum)"的概念来更加精确的表述它。

8.3.1. 闵可夫斯基和 (Minkowski Sum)

设 \(A, B\) 为平面上的两个点集。若建立一个坐标系，则这些点可以被视为该坐标系下的向量。我们以最自然的方式定义 \(A\) 与 \(B\) 的和: \(A \oplus B = \{x + y \mid x \in A, \ y \in B\}\)，其中 \(x + y\) 是两点的向量和。这被称为 \(A\) 与 \(B\) 的闵可夫斯基和(Minkowski Sum)。

若考虑点 \(x\) 与集合 \(B\) 的闵可夫斯基和 \(x \oplus B = \{x + y \mid y \in B\}\)，理解这个抽象概念的含义要稍微容易一点。 这实际上是将 \(B\) 按向量 \(x\) 平移后的副本，因为 \(B\) 中的每个点 \(y\) 都移动了 \(x\)。 所以 \(A \oplus B = \bigcup_{x \in A}(x \oplus B)\) 是 \(B\) 的一系列副本的并集，对于每个 \(x \in A\) 都有一个对应的副本。 现在假设 \(A\) 是一个多边形 \(P\)，而 \(B\) 是一个以原点为中心的圆盘 \(R\)。那么 \(P \oplus R\) 可以看作是很多个 \(R\) 的副本， 这些副本分别对于所有 \(x \in P\) 都平移了 \(x\)。由于 \(R\) 以原点为中心，\(x \oplus R\) 将以 \(x\) 为中心。 因此，\(P \oplus R\) 相当于在 \(P\) 的每一点上放置一个以该点为中心的 \(R\) 的副本。现在应该清楚的是，\(P \oplus R\) 正是扩张区域 \(P^+\)。

让我们来看看图 8.4(b) 中三角形障碍物的扩张情况。当 \(x\) 为顶点时，在三角形的每个顶点处放置一个 \(R\) 的副本。 当 \(x\) 位于边上时，则生成连接这些顶点处圆盘的切线。对于三角形内部的 \(x\)，\(x \oplus R\) 位于 \(P^+\) 内部。

8.3.2. 概念性算法 (Conceptual Algorithm)

我们现在回到在多边形障碍物之间移动圆盘的问题。我们将概述一个概念算法，但不提供细节。

首先，通过构建与圆盘 \(R\) 的闵可夫斯基和(Minkowski sum)，膨胀每个障碍物按圆盘 \(R\)。我们尚未描述如何通过算法构建这些扩张后的障碍物。 这个问题我们留到到下一节讨论。其次，求出这些扩张后障碍物的并集。同样，我们不会讨论如何做到这一点，这并非易事。 如果目的地 \(t\) 与起点 \(s\) 位于平面的不同“连通分量”中，那么就不存在一条从 \(s\) 到 \(t\) 的可行路径。 如果它们位于同一个连通分量中，那么存在一条路径。我们可以通过修改可见图(visibility graph)以包含圆的相关边来找到最短路径。 这里不再进一步描述该算法，但它可以在 \(O(n^2 \log n)\) 时间内完成(Chew 1985)。