8.5 移动梯子
(Moving a Ladder)
我们所考虑的最复杂的刚体机器人运动规划问题是，在多边形障碍物之间移动一个线段形状的机器人。这个线段通常被称为梯子(ladder)，有时也称为杆(rod)。 与前面的章节不同，这里我们允许旋转，这会使问题变得复杂。
旋转赋予梯子第三个运动自由度，两个平移自由度和一个旋转自由度。这意味着无法将这个问题的一般实例，像前两节那样，转化为二维平面上点的运动问题。因为二维点只有两个自由度。 然而，任何梯子问题都可以简化为一个三维障碍空间中点机器人的运动规划问题。最早由 Lozano-Pérez & Wesley(1979) 提出了这一巧妙思路。我们将用图 8.10(a) 所示的简单例子来解释它。 梯子 \(L\) 最初是水平的。我们希望它沿着图(a)所示的路径移动。但它只能通过旋转来做到这一点。图(b)按照上一节所述， 通过水平梯子与障碍物的闵可夫斯基和(Minkowski sum)来膨胀障碍物。\(C\) 膨大到与 \(A\) 和 \(B\) 重叠，这清楚地表明 \(L\) 如果不旋转就无法通过该通道。 图(c)显示了当梯子旋转 \(30°\) 后膨胀的障碍物，图(d)的梯子旋转了 \(60°\)。在图(d) 中，\(A\) 和 \(C\) 之间的垂直通道已经打开，而 \(A\) 和 \(B\) 之间的水平通道则关闭了。 这些图表明，梯子可以先以很少的旋转或者不旋转，在 \(A\) 和 \(B\) 之间移动，然后在垂直移动之前逆时针旋转 \(60°\) 或更多，从而沿着图(a)的路径移动。
现在想象一下，将所有可能的旋转角度 \(\theta\) 对应的膨胀障碍物堆叠在一起，如图 8.11 所示。该空间中的每个点 \((x, y, \theta)\) 代表梯子参考点的一个位置。 它所在的平面代表旋转角度 \(\theta\)。这样我们就实现了前面所说的，将二维平面上梯子的移动问题转化为三维空间中点的运动问题。 这个三维空间被称为机器人的构型空间 (configuration space)。
从图 8.11 中可能看不出来，实际上这些障碍物并不是多面体。在每个 \(\theta\) 平面上它们是多边形的，但它们沿 \(\theta\) 方向扭曲，产生复杂的形状。 参考点可以自由移动的空间被称为自由空间(free space)。如果你站在这个空间的起始位置 \(s\)，你会看到一个墙壁扭曲的巨大洞穴。 当且仅当 \(t\) 与 \(s\) 位于自由空间的同一连通分量中时，才存在一条可行路径。
显然，梯子并没有什么特殊之处。我们也可以使用同样的技术，创建任意多边形机器人在多边形障碍之间的构型空间。 事实上，这一基本思想可以扩展到三维机器人和障碍物，甚至关节机器人。
构建构型空间，并在其中找到路径，是一项极具挑战的任务。但其重要性促使人们开展了深入的研究，这些构型空间确实已被构建，有时甚至在高达六维空间， 然后用于机器人导航的路径规划。Lozano-Pérez(1983) 进行了一般性的讨论，Brost(1991) 描绘了各种构型空间的精美图像。
现在，我们将概述两种在构型空间中寻找自有路径来解决运动规划问题的不同方法。虽然这两种方法都非常通用，但我们只讨论移动梯子的情况。
8.5.1. 单元分解 (Cell Decomposition)
为解决运动规划问题而发明的第一个通用方法是单元分解(cell decomposition)法，该方法由 Schwartz 和 Sharir 在著名的五篇系列论文 —— 钢琴搬运工(piano movers)中提出。 这些论文讨论了各种各样的运动规划问题，都可以用多项式时间算法来解决，具体的复杂度取决于问题的细节。在此，我将根据 Leven & Sharir(1987) 的描述，简要概述应用于梯子问题的方法。
单元的定义 (Definition of a Cell)
单元分解方法的本质是将复杂的构型空间划分为有限个性质良好的"单元(cells)"，并通过寻找单元之间的路径来确定空间中的一条路径。
如图 8.12 所示的环境。它由两个三角形障碍物和一堵有界的(开放)多边形墙组成。梯子 \(L\) 水平放置，其参考点在左侧箭头处。 目前，我们只考虑 \(L\) 的一种特定朝向，即图中所示的水平朝向。单元是指相应构型空间中自由空间内的一个连通区域。 由于我们固定了梯子的朝向，构型空间就是一个平面，而自由空间则通过梯子对障碍物进行闵可夫斯基和(Minkowski sum)膨胀操作后剩余的部分。 为精确定义单元划分，我们像图中那样为每个障碍物边分配一个标签。我们使用标号 \(\infty\) 来表示右侧无限远处的边。 假设我们将梯子的参考点放在某一点 \(x\) 处，且该点不与任何顶点处于同一水平线上。 那么，将 \(L\) 水平向前(向左)移动，最终会导致它撞上某条障碍物边，向后(向右)移动也是如此。 我们将点 \(x\) 标记为这对标签的组合。单元就是所有具有相同"向前/向后"标签对的自由空间点的集合。
在图 8.12 中，单元 \(A\) 的标签组合是 (3, 2)，单元 \(B\) 的是 (3, 8)，单元 \(C\) 的是 (1, 9)，不存在标签组合为 (3, 6) 的单元，因为在那两条边之间没有自由点。
连通图 \(G_\theta\)
在单元分解方法中，单元结构是用一个图来表示的，即连通图\(G_\theta\)。下标表示该图刻画了梯子处于特定方向 \(\theta\) 时的结构。 \(G_\theta\) 的节点就是这些单元。如果两个单元互相接触，或者更准确地说，若它们的边界共用一段长度非零的线段，则相应的两个节点之间由一条边连接。 因此，\(G_\theta\) 类似于第1章(1.2.3节)和第4章( 4.4节)中讨论的对偶图。 对应于图8.12中各单元的 \(G_0\) 如图8.14(a)所示。注意，\(G_0\) 是不连通的：在 \(G_0\) 中，单元 \(A\) 和 \(C\) 之间没有路径。
这个图的重要性在于，单元内部的运动规划是十分简单的，因此图中的路径可以很容易地转换为梯子的路径。 此外，只有当图中这些单元之间存在路径时，梯子才能从一个单元移动到另一个单元。
临界方位 (Critical Orientations)
现在，我们采用类似于此前"平面堆叠"的思想引入旋转。如果我们稍微旋转一下梯子，图 8.12 中障碍物的连通图通常不会发生变化。虽然所有的单元的形状都会变化，但它们仍然存在并维持着原有的邻接关系。 但是当旋转角度超过某个临界方位 \(\theta^*\) 时，\(G_{\theta^*}\) 的组合结构将不同于 \(G_0\) 的组合结构。
图 8.12 所示的 \(\theta = 0\) 就是一个临界的方向，因为此时存在平行于 \(L\) 的障碍物边。因此，若将 \(L\) 绕其参考点逆时针稍微旋转将产生 \((7, 8)\) 和 \((4, \infty)\) 单元。 若进一步旋转至与障碍物边 \(e_9\) 对齐的方位，会导致单元 \(C\) 消失，因为此时不再有点具有标签 \((1, 9)\)。 该方位下的单元分解如图 8.13 所示，其对应的连通图如图 8.14(b) 所示。
读者或许已经猜到，临界方位均涉及梯子与障碍物边或两个障碍物顶点的对齐。因此，最多有 \(O(n^2)\) 个临界方位。
连通图 \(G\) (Connectivity Graph)
现在的思路是构建一个宏大的连通图 \(G\)，它整合了所有 \(G_\theta\) 图中的信息。我们将单元的定义进行扩展，使其表示三维构型空间中的区域，同一区域内所有点都具有相同的(前向/后向)标签对。 这相当于将固定朝向的单元沿 \(\theta\) 方向堆叠在一起。因此，图 8.12 中单元 \(A\) 内的点与图 8.13 中单元 \(A'\) 内的点位于同一个三维单元中。 每个不同的三维单元都是 \(G\) 的一个节点，同样地，如果两个单元接触，即它们共享一段面积非零的边界，则对应的两个节点由一条边连接。
图 \(G\) 可以通过构建 \(G_0\)、初始化 \(G \leftarrow G_0\)，然后按排序顺序遍历所有临界方位，在此过程中修改 \(G_\theta\) 并将相应的变化整合到 \(G\) 中来构造。 此处不深入具体细节，详细参见 Leven & Sharir(1987)，但读者应该能看出构建 \(G\) 是可行的。
同样，在由 \(G\) 的节点所代表的单个单元内部进行运动规划并不困难，在相接触的单元之间移动也很容易。例如，可以从单元内部移动到其边界，然后沿边界移动到与相邻单元共享的区域。 这样，运动规划问题被转化为一个图论问题: 寻找一条从包含起点 \(s\) 的单元对应的节点，到包含终点 \(t\) 的单元对应的节点的路径。 如果 \(G\) 中不存在这样的路径，那么梯子就没有可行的路径。如果 \(G\) 中存在路径，它可以作为规划梯子运动的指引。
8.5.2 收缩 (Retraction)
解决运动规划问题，还有一种截然不同但同样具有普适性的技术，即由 Ó’Dúnlaing & Yap(1985) 提出的收缩法(retraction method)。 这里，我们简述其在移动梯子问题上的应用思路，细节请参阅文献 Ó’Dúnlaing, Sharir & Yap(1986), Ó’Dúnlaing, Sharir & Yap(1987)。
维诺图 (Voronoi Diagram)
收缩算法的本质是为梯子构建一个"维诺图"，然后将起点 \(s\) 和终点 \(t\) "收缩 retract"到该图上，并在该图构成的"网络 network"内进行路径规划。 首先我们解释一下在此语境下维诺图的含义。
回顾第5章(5.2节)，维诺图边上的点至少与两个站点等距，图的顶点至少与三个站点等距。 对于固定朝向的梯子 \(L\)，我们将障碍物关于 \(L\) 的维诺图定义为满足以下条件的自由点 \(x\) 的集合: 当梯子的参考点放置在 \(x\) 处时，\(L\) 与至少两个障碍点等距。
首先我们需要定义到 \(L\) 的距离。点 \(p\) 到 \(L\) 的距离是连接 \(p\) 到 \(L\) 上任意一点的所有线段中的最小长度。 正如与一个点距离为 \(r\) 的所有点构成一个圆一样，与 \(L\) 距离为 \(r\) 的所有点构成一个"跑道形 racetrack"。 这是一个由两条平行于 \(L\) 的边和两端的半圆连接而成的形状。图8.15 显示了围绕 \(L\) 的嵌套跑道形。 图中还用阴影线标示了维诺图，以及梯子的几个示例位置。例如，在位置 \(A\)，\(L\) 与 \(e_3\) 和 \(e_2\) 等距； 在位置 \(B\)，它与 \(e_1\) 和 \(e_9\) 等距；在位置 \(C\)，它与 \(e_5\) 以及 \(e_8\) 和 \(e_{10}\) 的公共顶点等距。 可以看出该图是不连通的，不存在从 \(A\) 到 \(B\) 的路径。
该图具有一个很好的性质，移动 \(L\) 使其参考点保持在图的边上时，\(L\) 会处于尽可能远离附近障碍物的位置，因为所有这些位置都与两个或更多障碍点等距。 对于试图避免与障碍物发生碰撞的机器人来说，这是一个非常有用的特性。
接下来的策略听起来应该很熟悉。我们可以设想每个 \(\theta\) 值对应的维诺图正交堆叠在 \(\theta\) 轴上，从而构成整个构型空间的维诺图。 可以看出，该图由扭曲的"片(sheets)"和以及"脊(ribs)"构成。片是由边的堆叠形成，而脊则由顶点的堆叠形成，即两个片相交之处。
收缩 (Retraction)
该问题将再次归结为图搜索问题，但其处理方式与单元分解方法截然不同。构型空间中维诺图上，片(sheets)之间的交线脊(ribs)形成了一个曲线网络。 这些曲线以一种自然的方式构成图 \(N\): 将每条曲线视为一条边，将两条或多条曲线的交点视为节点。
最后一步涉及起点 \(s\) 和终点 \(t\) 的两次收缩(retractions)。第一次收缩将这些点映射到维诺曲面上，第二次收缩将其从曲面映射到上述网络上。 设 \(s'\) 和 \(t'\) 为网络上这些收缩后的点。那么，当且仅当网络上存在一条从 \(s'\) 到 \(t'\) 的路径时，才存在一条从 \(s\) 到 \(t\) 的路径。 这个条件可通过搜索图 \(N\) 来确定。由此得到的"高净空(high-clearance)"路径在许多情况下都很适用，例如，控制切削刀具的运动。
8.5.3. 复杂度 (Complexity)
迄今为止，我们很少提及梯子运动规划的复杂度。与其试图分析上述那些描述尚不完整的算法的复杂度，不如简要回顾一下二维和三维空间中移动梯子问题的复杂度研究历程， 这至少能体现出学术界在该领域坚持不懈的探索精神。
本节中讨论的二维问题备受关注，某种程度上充当了算法思想的试验台。该问题的首个解法出现在关于"钢琴搬运工问题(piano movers problem)"的论文中， 随后出现了各种改进，并非所有改进都反映在渐近时间复杂度上。我曾证明，存在某些障碍物布局，迫使任何解路径都必须包含二次方数量级的独立“移动”， 从而确立了输出此类路径的算法下界。这一下界最终在1990年得以实现。时间复杂度如下表所示。
| 作者 | 时间复杂度 |
|---|---|
| (Schwartz & Sharir 1983a) | \(O(n^5)\) |
| (Ó’Dúnlaing et al. 1987) | \(O(n^2 \log n \log^* n)\) |
| (Leven & Sharir 1987) | \(O(n^2 \log n)\) |
| (Sifrony & Sharir 1987) | \(O(n^2 \log n)\) |
| (Vegter 1990) | \(O(n^2)\) |
| (O’Rourke 1985b) | \(\Omega(n^2)\) |
我们尚未讨论在多面体障碍物中移动梯子的三维问题。这显然要复杂得多，涉及五维的构型空间。同样，最初的算法是基于单元分解法实现的，但其时间复杂度极高。 迄今为止最快的算法采用了 Canny 的"路线图(roadmap)"算法，这是解决运动规划问题的另一种通用技术，是收缩法的推广。就目前而言，该算法的复杂度与理论最优下界之间仍存在差距。
| 作者 | 时间复杂度 |
|---|---|
| (Schwartz & Sharir 1984) | \(O(n^{11})\) |
| (Ke & O’Rourke 1987) | \(O(n^6 \log n)\) |
| (Canny 1987) | \(O(n^5 \log n)\) |
| (Ke & O’Rourke 1988) | \(\Omega(n^4)\) |
关于运动规划最强的通用结果由 Canny (1987) 给出:
定理 8.5.1. 任何涉及具有 \(d\) 个运动自由度的机器人运动规划问题，都可以在 \(O(n^d \log n)\) 时间内解决。
虽然这是目前最好的通用结果，但针对特定问题实例，存在渐近意义上更快的算法。例如，二维空间中的梯子有三个自由度，根据 Canny 的结果， 这意味着存在一个 \(O(n^3 \log n)\) 的算法。但我们已经看到，这一结果已经被提高了 \(n \log n\) 倍。
8.5.4. 练习
- 单元的形状 shape of cells。对于通过单元分解方法(第8.5.1节)在二维空间中移动梯子，证明或反驳以下命题:
- 由 \(G_\theta\) 的节点表示的每个单元都是凸的。
- 由 \(G\) 的节点表示的每个单元都是凸的。
- 梯子维诺图 Ladder Veronoi diagrams。证明或反驳: 对于固定朝向的梯子，其梯子维诺图仅由直线段构成。
- \(\Omega(n^2)\) 个连通分量。构造一个例子，证明移动梯子问题的连通图 \(G\) 可以有 \(\Omega(n^2)\) 个不同的分量。
-
[open] 椅子过门问题的最坏情况 Worst chair through a doorway。设门为一条垂直线，比如与 \(y\) 轴重合，其中从 \(y=0\) 到 \(y=1\) 的开线段被移除。 如果存在一种连续运动，能将多边形从门的左侧移动到右侧，且此过程中多边形的内部始终不与门上方的射线 (\(y = 1\)向上) 和下方的射线(\(y=0\) 向下)相交，则称该多边形能穿过该门。 本题要求构造一类具有 \(n\) 个顶点的多边形，它们都能穿过该门，但需要大量不同的"移动(move)"步骤才能通过。为了使这个问题有意义，我们需要定义何为"移动"。
在多边形内固定一个参考点 \(r\)。那么多边形的任何连续运动，都可以看作是随时间参数 \(t\) 连续的、关于参考点 \(r\) 的平移和旋转。 因此，多边形的运动可以用三个函数 \(x(t), y(t), \theta(t)\) 来表示，分别描述 \(r\) 的平移和关于 \(r\) 的旋转。
试想将这些函数随时间的变化绘制成图，参见图 8.16。我们将移动定义为包含一个极大的时间区间，在此区间内，上述三个函数都是单调的。 本任务是找到在该定义下，相对于多边形顶点数量而言，需要最多移动次数的多边形。从某种意义上说，这些形状是最难通过门口的。
目前已知的"最差"多边形需要 \(n/2\) 次移动(Jones & O’Rourke 1990)。但目前唯一的上界是 \(O(n^2)\) (Yap 1987)。 我们需要找到一个通用的示例，证明其移动次数超过线性量级。或者证明存在更小的上界。即使只是改进比例系数 \(\frac{1}{2}\) 也将极具研究价值。
- 最短梯子路径 Shortest ladder path。衡量梯子路径长度的方法有很多种。这里我们探讨其中三种。设线段长度为 1，且环境中无障碍物。
设线段的初始位置是 \([(0, 0), (1, 0)]\)，任务是求出最短路径，将其旋转至 \([(1, 0), (0, 0)]\)，即回到原始位置但方向相反。在三种度量标准下计算最短路径的长度
- 梯子路径的长度是运动过程中线段中点所经过的路径长度。
- 梯子路径的长度是线段的一个端点所经过的路径长度。
- 梯子路径的长度由线段两个端点所经过的路径长度之和(Icking, Rote, Welzl & Yap 1993)。
