Planning Algorithms 学习站 首页 › Part II › 第 6 章 组合运动规划

Part II · 第 6 章

组合运动规划 Combinatorial Motion Planning

第 5 章的采样方法把 \(\mathcal{C}_{obs}\) 藏进碰撞检测的黑盒,换来通用性,却只能做到分辨率完备或概率完备。这一章走另一条路:组合方法 combinatorial approaches 直接在连续的 \(\mathcal{C}\) 中找路径,不做任何近似,所以又叫精确算法 exact algorithms。它们都是完备的 complete:对算法所针对的那类问题的任何实例,要么找到解,要么正确地报告无解。

本章导读

输入的表示 多边形 / 半代数集 单元分解 6.2.2、6.3、6.4.2 直接构造路线图 6.2.3、6.2.4、6.4.3 路线图 𝒢 可达 + 保持连通 离散搜索 第 2 章 有解 → 路径 无解 → 正确报告

本章所有算法的共同骨架(补充示意图):把连续问题精确地变成一张图,再用第 2 章的搜索回答查询。

为什么要学组合方法?书中给了两个理由:

  1. 很多应用只关心一类特殊问题(比如平面里只能平移的机器人)。针对它们可以设计出优雅、高效、完备、不依赖近似的算法,性能远好于第 5 章的采样方法。
  2. 知道「对一大类运动规划问题存在完备算法」本身就很有意义:即使你的问题没什么特殊结构,也仍然有通用的完备工具;这些算法还给出了求解所需时间的理论上界。
书中的警告:有些方法不实用

别做错误的假设。本章有的算法高效又好实现,但很多两样都不占:渐近复杂度惊人,却几乎不可能实现。著名例子是 Chazelle 的单多边形三角剖分(「简单多边形」指没有洞的多边形区域):\(O(n)\) 时间,上过《纽约时报》,但复杂到怀疑是否有人会去实现它。有时理论上更差、却好写得多的算法才是更好的选择。两类方法都值得了解,权衡由你自己决定;找出一个问题「到底能多高效地解决」也是很有意思的智力追求,它会激励别人去找同样复杂度、但更简单的算法。

方法适用的问题做法时间
垂直单元分解(6.2.2)\(\mathcal{C}=\mathbb{R}^2\),\(\mathcal{C}_{obs}\) 是多边形平面扫描,切成梯形,再建路线图\(O(n\lg n)\)
最大间隙路线图(6.2.3)同上广义 Voronoi 图,离障碍尽量远朴素 \(O(n^4)\),最好 \(O(n\lg n)\)
最短路路线图(6.2.4)同上简化可见性图:反射顶点 + 双切线朴素 \(O(n^3)\),径向扫描 \(O(n^2\lg n)\)
三角剖分 / 柱形分解(6.3.2)同上其它切法;柱形分解能推广到任意维\(O(n\lg n)\) 起
三维垂直分解(6.3.3)\(\mathcal{C}_{obs}\) 分段线性(多面体)递归地扫描—
线段机器人(6.3.4)\(\mathcal{C}=\mathbb{R}^2\times\mathbb{S}^1\),多边形障碍平面上按临界曲线分区,再「提升」到 \(\theta\)\(O(n^5)\)
柱形代数分解(6.4.2)任何半代数模型(Formulation 4.1,甚至闭链)投影、再提升维数的双重指数
Canny 路线图(6.4.3)同上递归地取轮廓线与临界点维数的单指数
本章地图与读法
  • 6.1:「表示很重要」与路线图的两个条件。必读。
  • 6.2:平面多边形障碍下的三种算法,最直观,很多原则可以推广到高维。必读,它也是第 5 章 PRM 的「精确版」。
  • 6.3:单元分解的一般定义(单纯复形、奇异复形),以及向 6.4 过渡的柱形分解、三维分解、线段机器人。
  • 6.4:计算实代数几何——能解任何 Formulation 4.1 问题的完备算法,但极难实现、实际中太慢。可以先读概念,细节留到需要时。
  • 6.5:复杂度理论:一般问题是 PSPACE-hard,所以「维数的指数」似乎躲不掉;Davenport–Schinzel 序列出现在许多上界里。

前置知识:第 4 章的 \(\mathcal{C}_{obs}\)(4.3 节,尤其是 4.3.2 的 Minkowski 差与 4.3.3 的半代数模型,见 第 4 章教程)、第 3 章的半代数模型与双向边表(3.1 节,见 第 3 章教程)、第 2 章的图搜索、第 5 章的路线图概念(5.6 节,见 第 5 章教程)。

本页的 2D 互动图都直接画在 C-space 里:灰色是 \(\mathcal{C}_{obs}\),蓝色是单元与路线图,绿色是解路径,橙色是扫描线与事件,紫色是 Voronoi 曲线 / 临界曲线。参考代码 part2/code/ch6_combinatorial.py 核对了页面上出现的数值(文中写「参考代码第 k 项」)。

6.1 引言:完备性与路线图 Introduction

本章所有算法都是完备的。对照一下:第 5 章容忍了更弱的完备性——分辨率完备和概率完备。

表示很重要 Representation is important

研究组合方法时,必须仔细考虑输入的定义:机器人和障碍用什么表示?允许机器人做哪些变换?世界是几维的?机器人和障碍是凸的吗?是分段线性的吗?所有可能输入的规格说明,定义了算法要处理的问题实例集合。如果实例有某些方便的性质(低维、凸模型……),组合算法可能给出优雅实用的解;如果实例集太宽,同时要求完备与实用可能就不现实了——运动规划的很多一般形式都是 PSPACE-hard(这意味着 NP-hard,见 6.5.1 节)。尽管如此,一般的完备算法确实存在。注意:把注意力放在表示上,正好与采样方法的哲学相反——后者把这些问题都藏进了碰撞检测模块。

路线图 Roadmaps

几乎所有组合方法都会在求解途中构造一张路线图 roadmap。这个概念在 5.6 节出现过,但这里的要求更严格,因为构造它的算法必须是完备的。有些算法先构造 \(\mathcal{C}_{free}\) 的单元分解 cell decomposition,再由它导出路线图;另一些不考虑单元,直接构造路线图。

定义:路线图

设 \(\mathcal{G}\) 是一个映入 \(\mathcal{C}_{free}\) 的拓扑图(例 4.6),\(S\subset\mathcal{C}_{free}\) 是它扫过的集合(swath,即 \(\mathcal{G}\) 到达的所有点,式 5.40)。\(\mathcal{G}\) 称为路线图,如果它满足两个条件:

  1. 可达性 Accessibility:从任何 \(q\in\mathcal{C}_{free}\) 出发,都能简单高效地算出一条路径 \(\tau:[0,1]\to\mathcal{C}_{free}\),使 \(\tau(0)=q\)、\(\tau(1)=s\),\(s\) 可以是 \(S\) 中任何一点。通常 \(s\) 取离 \(q\) 最近的点(假设 \(\mathcal{C}\) 是度量空间)。
  2. 保持连通性 Connectivity-preserving:用第一个条件总能把 \(q_I\)、\(q_G\) 分别连到 \(S\) 中的 \(s_1\)、\(s_2\)。第二个条件要求:只要存在 \(\tau:[0,1]\to\mathcal{C}_{free}\) 使 \(\tau(0)=q_I\)、\(\tau(1)=q_G\),就也存在 \(\tau':[0,1]\to S\) 使 \(\tau'(0)=s_1\)、\(\tau'(1)=s_2\)。于是不会因为 \(\mathcal{G}\) 没抓住 \(\mathcal{C}_{free}\) 的连通性而漏掉解。

满足这两条,路线图就是原连续运动规划问题的离散表示,而且没有丢掉解题所需的任何连通性信息。查询 \((q_I,q_G)\) 的回答方式:把两个查询点连到路线图上,再在 \(\mathcal{G}\) 上做离散图搜索。第一个条件保证任何查询都能连上 \(\mathcal{G}\),第二个条件保证有解时搜索一定成功。

试一试
  • 「好的路线图」:把 qI 放进左下角那个被 L 形墙围住的小角落,qG 放到右上——查询成功,绿线先沿虚线连到路线图上。
  • 切到「伸不进角落」:qI 在角落里时看不见路线图上的任何一点,可达性失败;而「真实答案」一栏(用 6.2.2 节的完备算法判定)说明其实有解。
  • 切到「断开了」:把 qI、qG 分别放在中央方块的左右两侧,G 上两点不连通,但真实答案是有解——这张图没有保持连通性,会漏解。

6.2 多边形障碍区域 Polygonal Obstacle Regions

先别急着进入最一般的组合规划。先看一个容易可视化的情形:\(\mathcal{C}=\mathbb{R}^2\)、\(\mathcal{C}_{obs}\) 是多边形。这时有好几种优雅、直接的算法。大多数不能直接推广到高维,但其中的一般原则仍然适用,所以看清它们在二维怎么工作非常有启发。它们也有直接的应用:把小型移动机器人看成在二维多边形平面图(建筑楼层图)里移动的点。

6.2.1 讲表示;6.2.2–6.2.4 给出解决同一个问题的三种算法:6.2.2 先做单元分解再得到路线图;6.2.3 与 6.2.4 直接构造路线图——6.2.3 算的是最大间隙路径,6.2.4 算的是最短路径(因此完全没有间隙)。

6.2.1 表示:双向边表 Representation

设 \(\mathcal{W}=\mathbb{R}^2\),障碍 \(\mathcal{O}\) 是多边形,机器人 \(\mathcal{A}\) 是只能平移的多边形。在这些假设下 \(\mathcal{C}_{obs}\) 是多边形。

  • 特例:\(\mathcal{A}\) 是一个点,\(\mathcal{O}\) 原封不动地映成 \(\mathcal{C}_{obs}\)。所以本节的问题也可以看作点机器人的规划。
  • \(\mathcal{A}\) 不是点时要算 \(\mathcal{O}\) 与 \(\mathcal{A}\) 的 Minkowski 差(4.37)。两者都凸时用 4.3.2 节的算法逐个分量地算。一般情形下两者都可能非凸、甚至有洞,得到图 6.1 那样的 \(\mathcal{C}_{obs}\):先分解成凸块(可以改造 6.2.2 节的单元分解算法来做),每对凸块算 Minkowski 差,再合并成一组简单多边形(合并的高效算法见 de Berg 等人《Computational Geometry》第 2.4 节,也可以基于 6.2.2 节规划算法的很多原理)。

实现时需要一个能方便地访问模型信息的数据结构:外边界怎么表示?障碍里的洞怎么表示?怎么知道哪个洞在哪个障碍里?3.1.3 节为了给多面体的面一致地编号介绍过的双向边表 doubly connected edge list 能高效回答这些问题。它有三种记录:

双向边表的三种记录
  • 顶点 Vertices:指向点 \((x,y)\in\mathcal{C}=\mathbb{R}^2\) 的指针,以及指向某条以它为起点的半边的指针。
  • 面 Faces:一个指针指向围住这个面的边界上的某条半边(若这个面是最外面的边界则为 NIL);还有一个指针列表,对面里包含的每个连通分量(即洞)各指向该分量边界上的一条半边。
  • 半边 Half-edges:每条半边都有方向,障碍总在它的左手边。它有五个指针:起点 origin vertex;孪生 twin(指向反方向的那条半边,3.1.3 节;若这条半边紧贴障碍就是 NIL);它的内部面;以及环中的 next、prev。半边总是排成首尾相接的环,构成一个面的边界,并且定向使得障碍(或孪生半边)在左侧。

图 6.1 的例子里有四条半边环,各自围住一个不同的面。小三角形洞的面记录指向包含它的那个障碍的面;每个障碍都有指向最外边界所表示的面的指针。只要定向一致,围住障碍的环总是逆时针,围住洞的环总是顺时针。一开始没有孪生半边,因为所有半边都贴着 \(\mathcal{C}_{obs}\)。但双向边表足够通用,允许再插入切开 \(\mathcal{C}_{free}\) 的额外的边——它们不在 \(\mathcal{C}_{obs}\) 的边界上,可以用 twin 指针成对管理。6.2.2 节就会用到这一点。

试一试
  • 点一条蓝色半边(障碍 A 或 B 的),再连按 next:一圈正好绕障碍逆时针一周,灰色障碍始终在箭头左边。点三角形洞或外边界上的半边:它们是顺时针的。
  • 看右下的面记录:B 的面把三角形洞列为「内部分量」;外边界之内的 C_free 面把两个障碍列为它的洞。(「左侧的面」一栏按「障碍在左」来理解书中的 internal face,这是我们的读法,见脚注 1。)
  • 勾上「加入竖直线段」:每条竖直线段变成一对方向相反的半边,twin 指针不再是 NIL——这正是 6.2.2 节往双向边表里加切割边的方式。

6.2.2 垂直单元分解 Vertical Cell Decomposition

单元分解的正式定义在 6.3 节,这里先非正式地用。组合方法必须构造一个能精确编码规划问题的有限数据结构。单元分解算法把 \(\mathcal{C}_{free}\) 划分成有限个称为单元 cells 的区域来做到这一点;k-单元指 \(k\) 维的单元。单元分解应满足三条性质:

  1. 在一个单元内部从一点走到另一点必须极其容易。例如每个单元都凸,任意两点连直线即可。
  2. 单元之间的邻接信息容易提取,用来建路线图。
  3. 对给定的 \(q_I\)、\(q_G\),能高效地判断它们落在哪个单元里。

满足这三条,运动规划问题就化成了图搜索问题,又可以用 2.2 节的算法了——只是在现在的设定里,整张图 \(\mathcal{G}\) 通常是事先已知的2,而离散规划里没有这个假设。

定义垂直分解

垂直单元分解 vertical cell decomposition 把 \(\mathcal{C}_{free}\) 划分成有限个 2-单元和 1-单元。每个 2-单元要么是两边竖直的梯形,要么是三角形(退化的梯形),所以这个方法也叫梯形分解 trapezoidal decomposition。定义如下:设 \(P\) 是定义 \(\mathcal{C}_{obs}\) 的顶点集合。在每个 \(p\in P\) 处,尝试穿过 \(\mathcal{C}_{free}\) 向上、向下各延伸一条射线,直到碰到 \(\mathcal{C}_{obs}\)。按两个方向能不能延伸,共有四种情形(图 6.2):① 向上、向下都延伸;② 只向上;③ 只向下;④ 都不能延伸。按这些射线切开 \(\mathcal{C}_{free}\),就得到垂直分解。

试一试
  • 依次按「情形 1–4」:障碍在 p 右边时上下都能延伸;障碍罩在 p 上方时只能向下……情形 4 需要一个凹进去的顶点(障碍在 ∠apb 之外,p 的上下都被障碍占着)。
  • 拖动 a、b 让它们一个在左一个在右:L 的更新方式从「插入 / 删除两条」变成「替换一条」——射线的情形与 L 的更新是两件独立的事。

每个 1-单元是一条竖直线段,是两个 2-单元的分界。要保证 \(\mathcal{C}_{free}\) 的拓扑被正确表示:\(\mathcal{C}_{free}\) 定义为 \(\mathbb{R}^2\) 中的开集,所以每个 2-单元其实是梯形或三角形的内部,1-单元是线段的内部。似乎应该再加上 0-单元(线段的端点),但端点都在 \(\mathcal{C}_{obs}\) 里,所以不允许。

一般位置 general position

如果竖线上恰好有两个 \(\mathcal{C}_{obs}\) 的点怎么办?如果 \(\mathcal{C}_{obs}\) 的某条边就是竖直的呢?组合运动规划里通常忽略这些特例,假设 \(\mathcal{C}_{obs}\) 处于一般位置:把所有数据点往随机方向扰动一点点,特例出现的概率为零。竖直的边扰动后就不竖直了,所以它不在一般位置。这个假设能大大简化算法的叙述(有时渐近运行时间甚至更低),但实际中可能非常恼人——大部分实现时间往往花在正确处理特例上。随机扰动可以回避它,但往往不必要地复杂化了解。对垂直分解,不靠扰动处理特例并不太难(习题 1);但一般来说,要意识到这个困难,它在大多数其它场合可没这么好修。本页的互动图在你拖动顶点时会自动把 x 坐标错开一点点,以保持一般位置。

定义路线图与回答查询

对每个单元 \(C_i\),取一个样本点 \(q_i\in C_i\)(可以取形心,具体怎么选不太重要)。拓扑图 \(\mathcal{G}(V,E)\) 这样定义:每个单元(每个 1-单元和每个 2-单元)对应一个顶点 \(q_i\in V\);对每个 2-单元,从它的样本点到它边界上每个 1-单元的样本点各连一条边,每条边是连接两个样本点的线段。这就是图 6.4 的路线图。可达性成立,因为每个单元都是凸的,样本点可以用直线到达;保持连通性成立,因为 \(\mathcal{G}\) 直接由单元分解导出,而单元分解保持了 \(\mathcal{C}_{free}\) 的连通性。路线图建好之后,单元信息就不再需要了。

回答查询 \((q_I,q_G)\):设 \(C_0\)、\(C_k\) 是包含 \(q_I\)、\(q_G\) 的单元,在 \(\mathcal{G}\) 中搜索从 \(C_0\) 的样本点到 \(C_k\) 的样本点的路径。没有这样的路径,算法就正确地宣告无解。有的话,设沿途经过的 1-单元和 2-单元依次是 \(C_1,\ldots,C_{k-1}\),样本点是 \(q_0,q_1,\ldots,q_k\);解路径 \(\tau:[0,1]\to\mathcal{C}_{free}\) 就是「连点成线」:\(\tau(0)=q_I\),依次经过 \(q_0,\ldots,q_k\),\(\tau(1)=q_G\)(图 6.5)。注意样本点必须取在 2-单元的内部,才能保证相邻单元样本点之间的线段无碰撞3。

试一试
  • 图 6.6 的例子:15 个 2-单元(其中 4 个是三角形)、16 条竖直线段,路线图 31 个顶点、32 条边(参考代码第 2 项)。拖动 qI、qG:绿色解路径总是「样本点 → 竖线中点 → 样本点……」交替。
  • 把 qG 拖进被障碍完全包住的地方——比如选「图 6.1 风格」场景,把 qG 拖进障碍 B 里的三角形洞:查询显示无解。这不是「没找到」,而是算法证明了无解。
  • 拖动障碍顶点:分解实时重算;「χ」一栏始终等于「自由连通分量数 − 洞数」(补充的拓扑检查,见 6.3.1 节例 6.1)。

计算分解:平面扫描

不考虑效率的话,每一步都可以暴力计算:若 \(\mathcal{C}_{obs}\) 有 \(n\) 个顶点,每条竖直射线都要和每条线段求交,至少 \(O(n^2)\),还没算找查询点所在单元、建路线图的数据结构开销。仔细组织计算后,总运行时间只要 \(O(n\lg n)\)。

算法基于计算几何中的平面扫描 plane-sweep(或线扫描 line-sweep)原理,它是许多组合运动规划算法、乃至很多其它算法的基础。计算几何的大部分内容可以看作把排序问题推广到多维的数据结构与算法——这些算法在小心地「排序」几何信息。之所以叫「扫描」,是因为可以想象一条直线(或平面)扫过空间,只在信息发生关键变化的地方停下。这给了直觉,但算法并不显式地表示扫描线。

构造垂直分解时,想象一条竖线从 \(x=-\infty\) 扫到 \(x=\infty\)。由 6.2.1 节,\(\mathcal{C}_{obs}\) 的顶点集 \(P\) 是问题输入中仅有的 \(\mathbb{R}^2\) 数据,所以有趣的事只会发生在这些点上。把 \(P\) 按 \(X\) 坐标递增排序(一般位置:没有两点 \(X\) 坐标相同),依次访问;每次访问称为一个事件 event。在事件之前、之后以及之间,维护一个列表 \(L\),记录当前被扫描线「刺穿」的 \(\mathcal{C}_{obs}\) 的边,按自下而上的顺序排好。

算法执行:开始时 \(L\) 为空,用双向边表表示 \(\mathcal{C}_{free}\),每个连通分量是一个面。假设经过若干事件后 \(L\) 维护正确。每个事件都对应图 6.2 的一种情形。把 \(L\) 存在平衡二叉搜索树里,\(p\) 上方和下方的边可以在 \(O(\lg n)\) 时间找到(逐条检查要 \(O(n)\))。按情形做不同的更新:情形 1 插入两条竖直线段,\(p\) 所在边界的那个面被切开两次,每条线段加两条半边,所有面与半边都要正确更新(只涉及附近的记录,是局部操作);情形 2、3 只切开一个面;情形 4 不切。

切完之后更新 \(L\)。扫描线经过 \(p\) 时总有两条边受影响:图 6.2 的第一种与最后一种情形要把两条边插入 \(L\)(它们的镜像情形则删除两条);中间两种情形是一条边替换另一条。插入、删除都是 \(O(\lg n)\),一共 \(n\) 个事件,构造算法的运行时间是 \(O(n\lg n)\)。

路线图可以从双向边表的面指针算出来。更优雅的做法是在每个事件处增量地建 \(\mathcal{G}\):只要 \(\mathcal{G}\) 建对、每个单元的样本点顺路求出,维护双向边表一致性的指针操作全都可以省掉。甚至可以更进一步,完全不管单元分解,直接建一张连接相邻单元样本点的线段拓扑图。

试一试
  • 在「图 6.6 的例子」上一步步按「下一个事件」:右边的表格逐行对照图 6.7,14 个事件后的 \(L\) 全部一致(✓)。图 6.6 的几何是我们按原图的像素位置量出来重建的,边名 a–n 与原图相同(参考代码第 1 项)。
  • 事件 4(左障碍的凹口)是情形 4:没有竖线,但 \(L\) 插入了 g、h 两条边;事件 5(右障碍的尖端伸进凹口)插入 j、n,此时 \(L\) 最长,有 8 条边。
  • 切到「柱形分解」:竖线一路穿过所有面,已扫过的竖条里自下而上是自由、障碍交替的一摞单元(图 6.18、6.19;见 6.3.2 节)。

6.2.3 最大间隙路线图 Maximum-Clearance Roadmaps

最大间隙路线图 maximum-clearance roadmap 尽量离 \(\mathcal{C}_{obs}\) 远一些,如图 6.8 的走廊所示。移动机器人应用里常常偏爱这样的解路径,因为机器人的精确位置很难测量和控制;沿最大间隙路线图走,可以降低这些不确定性导致碰撞的机会。它还有别的名字:广义 Voronoi 图 generalized Voronoi diagram、收缩法 retraction method。它可以看作 Voronoi 图(回忆 5.2.2 节)从「点」到「多边形」的推广。路线图边上的每一点,都到 \(\mathcal{C}_{obs}\) 边界上的两个点等距;每个路线图顶点是两条以上路线图边的交点,因此到边界上三个或更多点等距。

定义:形变收缩 deformation retract

「收缩」这个名字来自拓扑,它给出了很好的直觉。拓扑空间 \(X\) 的子空间 \(S\) 称为 \(X\) 的形变收缩,如果存在连续同伦 \(h: X\times[0,1]\to X\) 满足:

  1. 对所有 \(x\in X\),\(h(x,0) = x\);
  2. \(h(x,1)\) 是一个连续函数,把 \(X\) 的每个元素映到 \(S\) 的某个元素;
  3. 对所有 \(t\in[0,1]\) 和 \(s\in S\),\(h(s,t) = s\)。

直觉是:\(\mathcal{C}_{free}\) 在同伦过程中被逐渐「削薄」,直到只剩一副骨架 \(S\)。可以想象沿 \(\mathcal{C}_{free}\) 的整个边界削掉薄薄一层,反复进行,最后剩下的就是最大间隙路线图(假设削到只剩细「薄片」时就停下)。

构造它时再次用到 5.3.3 节的特征 features:特征集指 \(\mathcal{C}_{obs}\) 所有的边和顶点。每一对特征都给出路线图的候选曲线,这引出一个朴素的 \(O(n^4)\) 算法:

  • 每对边–边特征,生成一条直线(图 6.9a,两条直线的角平分线);
  • 每对顶点–顶点特征,生成一条直线(图 6.9b,中垂线);
  • 点到直线的最大间隙路径是抛物线,所以每对边–点特征生成一条抛物线(图 6.9c,第三种情形是二次曲线)。

候选曲线上哪些部分真正属于最大间隙路线图,要通过曲线之间求交来确定。有渐近时间更好的算法,但难实现得多;已知最好的算法是 \(O(n\lg n)\),这里 \(n\) 是路线图曲线的条数。

试一试
  • 「走廊(图 6.8)」:把探针拖到紫色中线上,两条到障碍的连线同时变成橙色——这里有两个最近点;离开中线就只剩一个。
  • 「顶点–边」:曲线是抛物线(焦点是顶点,准线是边)。把顶点拖近边,抛物线变尖;拖到边上它就退化掉了。
  • 「边–边」:只画出「两条边的垂足都落在边内部」的那部分角平分线——到线段的距离只在这时由「到直线的距离」给出,其余部分要换成顶点特征来算。
试一试
  • 勾上「显示全部候选曲线」:淡紫色虚线是每一对特征生成的直线、抛物线(O(n²) 条);粗紫线是其中「这两个特征确实是最近特征」的部分——这正是书中朴素算法的做法。
  • 慢慢拖动「削掉的厚度」:橙色是已经削掉的薄层,最后只剩紫色骨架——形变收缩的直觉。
  • 比较两种路径:最大间隙路径(绿)更长,但途中的最小间隙远大于最短路(红色虚线,它贴着角走,最小间隙是 0)。(补充说明:查询部分先把 qI、qG 沿「背离最近障碍点」的方向推到骨架上,再在栅格化的骨架上搜索,是演示用的近似实现;紫色曲线本身由朴素算法逐点精确算出。)

6.2.4 最短路路线图 Shortest-Path Roadmaps

如果目标不是最大化间隙,而是找最短路径,就得到最短路路线图 shortest-path roadmap,Latombe 的书里也叫简化可见性图 reduced visibility graph。这个想法最早由 Nilsson(1969)提出,也许是第一个运动规划算法。它与最大间隙直接冲突:最短路径总是擦着 \(\mathcal{C}_{obs}\) 的角走。

事实上问题本身是病态的:\(\mathcal{C}_{free}\) 是开集,对任何路径 \(\tau:[0,1]\to\mathcal{C}_{free}\) 总能找到更短的。所以必须改为在闭包 \(\mathrm{cl}(\mathcal{C}_{free})\) 里求最短路径:机器人可以「碰到」或「擦过」障碍,但不能穿进去。要把算出的路径真正用作解,得稍微调整,让它非常接近 \(\mathcal{C}_{obs}\) 而不接触——路径会变长一点,但多出的代价可以任意小。

定义:反射顶点与最短路路线图

反射顶点 reflex vertex:多边形顶点中,(在 \(\mathcal{C}_{free}\) 一侧的)内角大于 \(\pi\) 的那些。凸多边形障碍的所有顶点都是反射顶点(假设没有三个相邻顶点共线)。

最短路路线图 \(\mathcal{G}\) 的顶点就是反射顶点;边有两种来源:

  1. 相邻的反射顶点:两个反射顶点恰好是 \(\mathcal{C}_{obs}\) 某条边的两个端点,就在 \(\mathcal{G}\) 中连一条边。
  2. 双切线边 bitangent edges:若能画一条穿过两个反射顶点的双切线,就在 \(\mathcal{G}\) 中连一条边。双切线(图 6.10)与两个反射顶点相切,在这两个顶点处都不刺入 \(\mathcal{C}_{obs}\) 的内部(直线可以越过每个顶点继续向外延伸而不进入障碍);并且这两个顶点必须互相可见。

图 6.11 是一个例子。路线图可能有孤立顶点。回答查询:把 \(q_I\)、\(q_G\) 连到所有它们能看见的路线图顶点(图 6.12),得到一张扩展路线图;用 Dijkstra 算法搜索,边的代价取长度,得到的就是 \(q_I\) 到 \(q_G\) 的最短路径(图 6.13)。

试一试
  • 默认场景:21 个顶点里有 16 个反射顶点(橙点);路线图 35 条边 = 14 条相邻反射顶点之间的障碍边 + 21 条双切线。勾上「完整可见性图」变成 88 条边,但最短路长度完全相同(统计栏打 ✓;参考代码第 5 项用 200 次随机查询核对过)。
  • 拖动 qI、qG:最短路只在反射顶点处拐弯,且总是贴着障碍「外凸」的一侧。凹进去的顶点(不是橙点)永远不会出现在最短路上。
  • 勾上「径向扫描模式」,点一个橙点再拖动 θ:射线从 θ = 0 开始绕顶点转,按角度依次碰到其它顶点(事件),沿途确认这个顶点的双切线。

复杂度:朴素地做双切线测试,算法是 \(O(n^3)\),\(n\) 是 \(\mathcal{C}_{obs}\) 的顶点数:要检查 \(O(n^2)\) 对反射顶点,每对还要 \(O(n)\) 时间确认没有别的边挡住它们的相互可见性。把 6.2.2 节的平面扫描改造一下能做到 \(O(n^2\lg n)\):从每个反射顶点 \(v\) 做一次径向扫描 radial sweep——射线从 \(\theta=0\) 出发,碰到顶点就是事件,\(O(n\lg n)\) 时间算出过 \(v\) 的所有双切线;共 \(O(n)\) 个反射顶点,总计 \(O(n^2\lg n)\)(细节见 de Berg 等人的书第 15 章)。还有 \(O(n\lg n + m)\) 的算法,\(m\) 是路线图的总边数;若障碍区域是一个简单多边形,复杂度可以降到 \(O(n)\)。

不用三角函数的双切线测试

为了数值稳健,最短路路线图可以完全不用三角函数来实现。对三个点 \(p_1,p_2,p_3\),定义左转谓词 left-turn predicate \(f_l:\mathbb{R}^2\times\mathbb{R}^2\times\mathbb{R}^2\to\{\mathrm{TRUE},\mathrm{FALSE}\}\):\(f_l(p_1,p_2,p_3)=\mathrm{TRUE}\) 当且仅当 \(p_3\) 在从 \(p_1\) 出发、穿过 \(p_2\) 的射线的左侧。点 \(p_2\) 是反射顶点当且仅当 \(f_l(p_1,p_2,p_3)=\mathrm{TRUE}\),其中 \(p_1\)、\(p_3\) 分别是沿 \(\mathcal{C}_{obs}\) 边界在 \(p_2\) 之前、之后的点。

双切线测试按图 6.14 给各点编号。假设没有三点共线,且连接 \(p_2\)、\(p_5\) 的线段不碰撞。顶点对 \(p_2,p_5\) 应该得到一条双切线边,当且仅当下式为 FALSE:

$$\big(f_l(p_1,p_2,p_5)\oplus f_l(p_3,p_2,p_5)\big)\ \vee\ \big(f_l(p_4,p_5,p_2)\oplus f_l(p_6,p_5,p_2)\big), \tag{6.1}$$

\(\oplus\) 是逻辑异或。\(f_l\) 不用三角函数就能实现:定义

$$M(p_1,p_2,p_3)=\begin{pmatrix}1 & x_1 & y_1\\ 1 & x_2 & y_2\\ 1 & x_3 & y_3\end{pmatrix}, \tag{6.2}$$

其中 \(p_i=(x_i,y_i)\)。若 \(\det(M)>0\),则 \(f_l(p_1,p_2,p_3)=\mathrm{TRUE}\);否则为 FALSE。

为什么 (6.1) 对?(补充)\(f_l(p_1,p_2,p_5)\) 其实是在问「\(p_1\) 在有向直线 \(p_2\to p_5\) 的哪一侧」(行列式在循环换序下不变)。所以第一个异或为 TRUE 恰好意味着 \(p_2\) 的两个邻点分在直线两侧——直线在 \(p_2\) 处刺进了障碍。参考代码第 4 项用 20000 组随机点验证了 (6.1) 与这个几何定义完全一致。

试一试
  • 「左转谓词」:拖动 p3 穿过射线,\(\det M\) 变号,三角形的颜色随之翻转——\(\det M\) 就是有向面积的 2 倍。
  • 「双切线测试」:默认是图 6.14 的位置,(6.1) = FALSE,是双切线。把 p4 拖到 p5 的右上方(例如 (3.6, 2.2) 附近):右边三角形在 p5 处跨到了直线 p2p5 的两侧,直线越过 p5 后就刺进障碍,第二个异或变成 TRUE。
  • 把 p2p5 拖得穿过一个三角形:会出现警告——(6.1) 假设线段 p2p5 不碰撞,可见性要另外检查。

6.3 单元分解 Cell Decompositions

6.2.2 节用垂直单元分解解决了 \(\mathcal{C}_{obs}\) 为多边形时的运动规划问题。但要明白:这只是众多分解方式中的一种。有些选择在二维里未必更好,却可能更好地推广到高维。所以本节介绍其它的单元分解,作为从垂直分解到 6.4 节柱形代数分解的平滑过渡——后者能在任何维数、对任何半代数模型解决运动规划问题。途中,6.3.4 节会为 \(\mathcal{W}=\mathbb{R}^2\) 中的线段机器人构造一个柱形分解。

6.3.1 一般定义:复形 General Definitions

这一节里,复形 complex 指一组单元连同它们的边界。由复形可以得到一个划分,但复形还包含「单元怎样拼在一起」的额外信息。单元分解仍然指把空间划分成单元——它是从复形导出的。

很想用非常宽泛的方式定义复形和单元分解:比如任何对 \(\mathcal{C}_{free}\) 的划分都叫单元分解。但那样单元可以复杂到毫无用处——\(\mathcal{C}_{free}\) 本身都可以当作一个大单元。更有用的是由更简单的单元(比如没有洞的单元)构成的分解。形式上,这要求每个 \(k\) 维单元都同胚于 \(B^k\subset\mathbb{R}^k\)——\(k\) 维开单位球。从运动规划的角度看这样的单元仍然可能相当复杂,要靠具体的分解方法加上更多约束,才能得到完备的规划算法。

下面介绍两种复形。单纯复形 simplicial complex 最容易理解,很多应用中很有用,但表达力不足以表示运动规划中出现的所有复形;奇异复形 singular complex 定义更复杂,却涵盖了本书关心的所有单元复形,还给出了一种表示拓扑空间的优雅方式。另一种重要的复形 CW-复形这里不讲。

单纯复形 Simplicial Complex

设 \(X=\mathbb{R}^n\),\(p_1,p_2,\ldots,p_{k+1}\) 是 \(\mathbb{R}^n\) 中 \(k+1\) 个线性无关的点4。由它们构成的 k-单纯形 k-simplex \([p_1,\ldots,p_{k+1}]\) 是

$$[p_1,\ldots,p_{k+1}] = \left\{\sum_{i=1}^{k+1}\alpha_i p_i\in\mathbb{R}^n\ \middle|\ \alpha_i\ge 0 \text{ 对所有 } i,\ \text{且}\ \sum_{i=1}^{k+1}\alpha_i = 1\right\}, \tag{6.3}$$

\(\alpha_ip_i\) 是 \(\alpha_i\) 与点坐标的数乘。(6.3) 也可以看作这 \(k+1\) 个点的凸包(在它们之间做所有可能的线性插值)。\(k=2\) 得到三角形区域,\(k=3\) 得到四面体。对任何 \(k\)-单纯形和任何 \(1\le i\le k+1\),令 \(\alpha_i=0\),得到一个 \((k-1)\) 维单纯形,称为原单纯形的一个面 face。2-单纯形有三个面,都是 1-单纯形,可以叫边;每个 1-单纯形有两个面,是 0-单纯形,叫顶点。

定义:单纯复形

要构成复形,单纯形必须好好地拼在一起,这得到三角剖分的高维推广(在 \(\mathbb{R}^2\) 中就是用三角形区域铺满)。单纯复形 \(\mathcal{K}\) 是满足下列条件的有限个单纯形的集合:

  1. \(\mathcal{K}\) 中任何单纯形的任何面也在 \(\mathcal{K}\) 中;
  2. \(\mathcal{K}\) 中任意两个单纯形的交,要么是两者的公共面,要么为空。

对 \(k>0\),\(\mathcal{K}\) 的 \(k\)-单元定义为任何 \(k\)-单纯形的内部 \(\mathrm{int}([p_1,\ldots,p_{k+1}])\);对 \(k=0\),每个 0-单纯形就是一个 0-单元。所有单元的并构成 \(\mathcal{K}\) 所覆盖点集的一个划分,因此给出一个与 6.2.2 节意义一致的单元分解。

试一试
  • 「单纯形 (6.3)」:把探针 x 拖到三角形外,某个 \(\alpha_i\) 变负;拖到一条边上,那个边对面的 \(\alpha_i\) 变成 0——这就是「令 \(\alpha_i = 0\) 得到面」。
  • 「复形检查」·图 6.15 左:中间三角形的顶点落在左边三角形的边内部(红圈),两者的交是一个点,却不是两者的公共面,违反条件 2(参考代码第 15 项用同样的检查核对过两个例子)。把那个顶点往右拖离这条边,违例消失——不过两个三角形也就不再接触了:要合法地贴在一起,必须共享一整条边或一个顶点。
  • 「把梯形对半切成三角形」:图 6.6 的垂直分解切出 26 个三角形,有 18 对违反条件 2,全是 T 形接头。这就是 6.3.2 节说的「这样做得不到单纯复形」。

奇异复形 Singular Complex

单纯复形在几何建模、计算机图形学等计算模型拓扑的应用里很有用。可是运动规划里出现的拓扑空间复杂、模型是隐式的、非线性的,分解算法也五花八门,单纯复形不够用。奇异复形是它的推广:它不限于 \(\mathbb{R}^n\),可以定义在任何流形 \(X\) 上(甚至任何 Hausdorff 拓扑空间)。主要区别是:单纯复形里每个单纯形是 \(\mathbb{R}^n\) 的子集;而奇异复形里每个奇异单纯形其实是从 \(\mathbb{R}^n\) 中某个(单纯)形到 \(X\) 的某个子集的同胚。

先看一维奇异复形——它恰好是一张拓扑图(例 4.6)。区间 \([0,1]\) 是一个 1-单纯形,连续路径 \(\tau:[0,1]\to X\) 是一个奇异 1-单纯形,因为它是 \([0,1]\) 到 \(\tau\) 在 \(X\) 中的像的同胚。设 \(\mathcal{G}(V,E)\) 是拓扑图,单元是 \(X\) 的子集:每个 \(v\in V\) 是 \(X\) 中的一个 0-单元——按形式主义,把它看作函数 \(f:\{0\}\to X\) 的像,这使它成为一个奇异 0-单纯形(\(\{0\}\) 是 0-单纯形)。对每条路径 \(\tau\in E\),对应的 1-单元是

$$\{x\in X\mid \tau(s)=x \text{ 对某个 } s\in(0,1)\}. \tag{6.4}$$

换句话说就是 \(\tau((0,1))\):路径 \(\tau\) 的像去掉两个端点——端点已经被 0-单元覆盖了(单元必须构成划分)。

推广到高维时,由于同维的球与单纯形同胚,可以用球代替单纯形。设 \(B^k\subset\mathbb{R}^k\) 表示 \(k\) 维闭单位球

$$D^k = \{x\in\mathbb{R}^k\mid \|x\|\le 1\}, \tag{6.5}$$

\(\|\cdot\|\) 是欧氏范数5。奇异 \(k\)-单纯形是连续映射 \(\sigma:D^k\to X\)。记 \(\mathrm{int}(D^k)\) 为 \(D^k\) 的内部。对 \(k\ge 1\),奇异 \(k\)-单纯形 \(\sigma\) 对应的 \(k\)-单元是像 \(C=\sigma(\mathrm{int}(D^k))\subseteq X\)。0-单元直接由 0 维奇异单纯形的像得到,每个奇异 0-单纯形映到 \(X\) 中的那个 0-单元。若把 \(\sigma\) 限制在 \(\mathrm{int}(D^k)\) 上,它就是 \(\mathrm{int}(D^k)\) 与 \(C\) 之间的同胚;\(k>0\) 时两者都是开集。

定义:奇异复形

单纯复形要求单纯形好好地拼在一起;这里用拓扑概念表达同一个意思,因为它更一般。设 \(\mathcal{K}\) 是若干维数不同的奇异单纯形的集合,\(S_k\) 表示所有奇异 \(i\)-单纯形(\(i\le k\))的像的并。映入拓扑空间 \(X\) 的一组奇异单纯形称为奇异复形,如果:

  1. 对每个维数 \(k\),集合 \(S_k\subseteq X\) 是闭集——单元必须好好地拼在一起;
  2. 每个 \(k\)-单元在拓扑子空间 \(S_k\) 中是开集。注意 0-单元在 \(S_0\) 中是开的,尽管它们在 \(X\) 中通常是闭的。

例 6.1(垂直分解):6.2.2 节的垂直分解是奇异复形、但不是单纯复形的好例子——它含有梯形。每个梯形和三角形的内部是一个 2-单元(开集);每对相邻的 2-单元,在它们的公共边界上有一个 1-单元;没有 0-单元,因为顶点在 \(\mathcal{C}_{obs}\) 里,不在 \(\mathcal{C}_{free}\) 里。把所有 2-单元和 1-单元并起来得到 \(S_2=\mathcal{C}_{free}\)。这满足闭性要求,因为复形只建在 \(\mathcal{C}_{free}\) 上,拓扑空间就是 \(\mathcal{C}_{free}\);\(S_2=\mathcal{C}_{free}\) 既开又闭。\(S_1\) 是所有 1-单元的并,它也是闭的,因为 1-单元的端点都在 \(\mathcal{C}_{obs}\) 中;每个 1-单元也是开集。

为避免把拓扑限制在 \(\mathcal{C}_{free}\) 上带来的这些怪结论,可以改在闭包 \(\mathrm{cl}(\mathcal{C}_{free})\) 上建垂直分解:从原来的分解出发,给 \(\mathcal{C}_{obs}\) 的每条边加一个 1-单元,每个顶点加一个 0-单元。这样(书中写作 \(S_3\),由于没有 3-单元它就等于 \(S_2\))\(S_2=\mathrm{cl}(\mathcal{C}_{free})\) 在 \(\mathbb{R}^2\) 中是闭的,\(S_1\)、\(S_0\) 也都按通常意义是闭的。每个 \(k\) 维单元在拓扑空间 \(S_k\) 中都是开的;唯一怪的是 0-单元被看作开集,但在离散拓扑空间 \(S_0\) 中这是对的。(补充:严格地说,竖直线段落在障碍边上的那个端点也要算成 0-单元,把那条边切成几个 1-单元。上面「垂直单元分解」互动图里的 χ 一栏就是这样数的:\(V-E+F\) 恒等于「自由连通分量数 − 洞数」,这是复形拼对了的一个检验。)

6.3.2 二维分解 2D Decompositions

6.2.2 节的垂直分解只是 \(\mathcal{C}_{obs}\) 为多边形时众多单元分解中的一种。它在单元个数、计算效率和实现难度之间取得了很好的平衡。通常可以把自由空间分解成少得多的凸单元6,这对多查询应用更好,因为路线图更小。可惜单元个数很难优化:求一个带洞多边形区域的、凸单元最少的分解是 NP-hard。所以我们愿意容忍非最优的分解。

三角剖分 Triangulation

垂直分解的一个替代是做三角剖分,它给出 \(\mathcal{C}_{free}\) 上的一个单纯复形(图 6.16)。因为 \(\mathcal{C}_{free}\) 是开集,没有 0-单元。每个 2-单纯形(三角形)有一个、两个或三个面(作为 1-单元),取决于它的边界有多少与 \(\mathcal{C}_{obs}\) 共享。连接 1-单元和 2-单元的样本点,就得到路线图(图 6.17)。三角剖分的方式有很多;在计算几何里,如何找到「好的」三角剖分(比如尽量避免细长三角形)得到了相当多的关注。

怎样计算?很想直接跑 6.2.2 节的垂直分解,再把每个梯形切成两个三角形。虽然得到的都是三角形单元,但这不是单纯复形——两个三角形可能贴在另一个三角形同一条边的不同部分上(上面单纯复形互动图的第三个例子)。朴素的做法是逐步切分面:尝试用线段连接一个面的两个顶点,若这条线段不与其它线段相交就切开。对所有多于三个顶点的面反复进行,直到得到三角剖分。可惜这是 \(O(n^3)\) 的:最坏要检查 \(O(n^2)\) 对顶点,每次检查要 \(O(n)\) 时间判断是否与其它线段相交。用径向扫描很容易降到 \(O(n^2\lg n)\)。de Berg 等人书中第 3 章给出 \(O(n\lg n)\) 的算法:先把 \(\mathcal{C}_{free}\) 划分成单调多边形 monotone polygons,再高效地三角剖分每个单调多边形。若 \(\mathcal{C}_{free}\) 单连通,令人惊讶地可以在线性时间内三角剖分,但那个算法太复杂、不实用(也有更简单、复杂度接近 \(O(n)\) 的算法)。

试一试
  • 图 6.6 的例子:不论按什么顺序加对角线,总是 17 条对角线、16 个三角形(\(n+2h-2 = 14+4-2\),参考代码第 3 项)——变的只是三角形的形状。
  • 比较「最短优先」和「随机顺序」:在这个例子里最小内角从 6.5° 掉到 1.1°,随机顺序产生了很多细长三角形。不过「最短优先」只是个朴素的启发式,换到「最短路例子」场景它反而更差——想系统地避免细长三角形,要用 Delaunay 三角剖分之类的专门方法(补充)。
  • 「交叉检查次数」显示朴素 \(O(n^3)\) 算法做了多少次线段相交测试;拖动顶点、换更复杂的场景看它怎么增长。

柱形分解 Cylindrical Decomposition

柱形分解与垂直分解非常相似,只是当图 6.2 的任何情形发生时,都用一条竖线贯穿所有的面,从 \(y=-\infty\) 一直到 \(y=\infty\),得到图 6.18(可以看作一个奇异复形)。与垂直分解相比它显得很浪费;之所以介绍它,是因为它能很好地推广到任意维数、任意 C-space 拓扑、任意半代数模型,作为通向更一般分解的过渡。它最重要的性质见图 6.19:考虑两个事件之间的每一个竖条,从 \(y=-\infty\) 往 \(y=\infty\) 走,点在 \(\mathcal{C}_{obs}\) 与 \(\mathcal{C}_{free}\) 之间交替。例如在事件 4、5 之间,边 f 以下的点在 \(\mathcal{C}_{free}\) 中,f 与 g 之间在 \(\mathcal{C}_{obs}\) 中,g 与 h 之间又在 \(\mathcal{C}_{free}\) 中,依此类推。这个单元分解也可以定义成在 \(\mathcal{C}_{obs}\) 里也产生 2 维单元。设 \(S(x,y)\) 是 3.1.1 节的逻辑谓词 (3.6),沿竖条走时 \(S(x,y)\) 的值也交替变化。这就是构造柱形分解的主要原因,到 6.4.2 节会更清楚。每个竖条其实被看作一个柱体 cylinder,这就是「柱形分解」名字的由来(不一定真有三维几何意义上的圆柱)。

试一试
  • 图 6.6 的例子:柱形分解在 \(\mathcal{C}_{free}\) 里有 27 个 2-单元、28 条竖直线段,垂直分解只有 15 个、16 条(参考代码第 2 项)。
  • 看事件 4 与 5 之间那一竖条(左障碍的凹口里):自下而上依次是 自由 d–f、障碍 f–g、自由 g–h、障碍 h–i、自由 i–b,正是图 6.19 说的交替(虚线框是 \(\mathcal{C}_{obs}\) 里的单元)。
  • 在三种分解之间切换,比较解路径:它们都正确(完备),但路线图的大小和路径的样子各不相同。

6.3.3 三维垂直分解 3D Vertical Decomposition

6.2.2 节的垂直分解可以递归地应用扫描的思想推广到任意维数。但这个方法要求 \(\mathcal{C}_{obs}\) 是分段线性的,即 \(\mathcal{C}_{obs}\) 用所有图元都是线性的半代数模型表示。可惜大多数一般的运动规划问题都涉及非线性的代数图元,因为旋转带来非线性变换——回忆 4.3.3 节构造的复杂的代数 \(\mathcal{C}_{obs}\) 模型。要处理一般的代数模型,需要计算代数几何的强大技术,那是 6.4 节的内容。

\(\mathcal{C}_{obs}\) 分段线性的一个问题是:多面体机器人在 \(\mathbb{R}^3\) 中平移,\(\mathcal{W}\) 中的障碍是多面体。由于此时变换方程是线性的,\(\mathcal{C}_{obs}\subset\mathbb{R}^3\) 是多面体;它的多边形面由 \(\mathcal{A}\) 与 \(\mathcal{O}\) 之间 Type FV、Type VF、Type EE 三种接触各自生成几何图元得到(4.3.2 节)。

图 6.20 画出了构造三维垂直分解的算法,可以和 6.2.2 节对照。设 \((x,y,z)\) 是 \(\mathcal{C}=\mathbb{R}^3\) 中的点。垂直分解给出凸的 3-单元、2-单元和 1-单元。不考虑退化情形,一个一般的 3-单元由六个平面围成:固定 \(x\) 的横截面是平行于 \(yz\) 平面的平面里的梯形或三角形,与二维情形完全一样;一般 3-单元有两个侧面平行于 \(yz\) 平面,另外两个平行于 \(xz\) 平面,上下由 \(\mathcal{C}_{obs}\) 的两个多边形面封住。

先把 \(\mathcal{C}_{obs}\) 的顶点按 \(x\) 坐标排序得到事件。想象一个垂直于 \(x\) 轴的平面扫过去,固定 \(x\) 的平面切出 \(\mathcal{C}_{obs}\) 的一个二维多边形截面(图 6.20 下方的三个切片)。每个切片平行于 \(yz\) 平面,看上去正是一个可以用二维垂直分解求解的问题;切片里的 2-单元其实是三维分解中 3-单元的切片。这些 3-单元只可能在扫描平面停在某个 \(x\) 值时发生关键变化。图 6.20 中间的切片对应碰到一个凸多面体的顶点、而多面体其余部分都在扫描平面右边(还没被碰到)的情形——这正是切片必须发生关键变化的地方,它们是图 6.2 各情形的三维版本,指出垂直分解要怎样更新。算法先在第一个 \(x\) 事件处建二维垂直分解,在每个事件处更新它以反映关键变化;在此过程中可以像二维情形一样增量地构造三维分解和路线图。

路线图:在每个 3-单元和 2-单元的中心放一个样本点;顶点就是这些样本点,每当一个 3-单元与一个 2-单元相邻,就连接它们的样本点。同样的原理可以推广到任何维数,但在运动规划中的应用受限,因为它需要线性模型(或者至少很难改造到非线性模型;某些特殊情形可以做到)。

试一试
  • 慢慢拖动 x:在两个事件之间,右图(平行于 yz 平面的切片)里的截面只是平滑变形,2-单元个数不变;用「下一个事件」跨过一个顶点,截面出现、消失或改变形状,单元个数随之改变。
  • 右图就是二维垂直分解,只是「竖直」方向是 z:每个 2-单元是某个 3-单元在这个 x 处的横截面。
  • 在左图里拖动来旋转视角,看清斜放的长方体怎样被扫描平面切出一个四边形截面。

6.3.4 线段机器人的分解 A Decomposition for a Line-Segment Robot

这一节给出最简单的一种涉及非线性模型的单元分解,它已经相当复杂了,有助于体会组合规划一般地有多难。考虑图 6.21 的规划问题:机器人 \(\mathcal{A}\) 是一条线段,可以在 \(\mathcal{W}=\mathbb{R}^2\) 中平移和旋转(\(\mathcal{A}\) 一端的点只用来标出原点,不属于模型)。C-space \(\mathcal{C}\) 同胚于 \(\mathbb{R}^2\times\mathbb{S}^1\),用参数化 \(\mathbb{R}^2\times[0,2\pi]/\sim\)(等同 \(\theta=0\) 与 \(\theta=2\pi\)),\(\mathcal{C}\) 中的点记作 \((x,y,\theta)\)。

一个近似解

先考虑线段只能平移的情形。可以用 4.3.2 节的方法计算 \(\mathcal{C}_{obs}\),把机器人与障碍的相互作用当作 Type EV 与 Type VE 接触:\(\mathcal{A}\) 的内部碰到障碍的顶点是 Type EV;\(\mathcal{A}\) 的一个端点碰到障碍的内部是 Type VE。每种情形产生 \(\mathcal{C}_{obs}\) 的一条边,\(\mathcal{C}_{obs}\) 是多边形;表示出来后就能用垂直分解解决问题。这启发了一个处理旋转的合理数值方法:把 \(\theta\) 离散成 \(K\) 个值 \(i\Delta\theta\)(\(0\le i\le K\),\(\Delta\theta=2\pi/K\))。每个 \(\theta\) 对应的 \(\mathcal{C}_{obs}\) 都是多边形,可以想象一摞 \(K\) 个多边形区域。路线图既在每个切片内部照常连接样本点,也在相邻切片的对应单元之间连接样本点。\(K\) 足够大时效果很好,但它不完备,因为事先无法确定多大的 \(K\) 才够。这个方法其实是组合方法与采样方法之间有趣的混合;可以设想它的一个分辨率完备的版本(习题 7)。

当 \(K\to\infty\) 时,\(\mathcal{C}_{obs}\) 的表面沿 \(\theta\) 方向弯曲。需要用 4.3.3 节的条件生成真正的障碍区域——这能做到,而且给出 \(\mathcal{C}_{obs}\) 用隐式多项式图元表示的半代数表示;但要确定一个可用于运动规划的、由简单单元构成的显式表示并不容易。6.3.3 节的方法不能用,因为 \(\mathcal{C}_{obs}\) 不是多面体。所以需要专门分析来得到单元分解。

总的思路是:先只考虑平移部分 \((x,y)\),在 \(\mathbb{R}^2\) 中构造一个单元分解;然后把 \(\theta\) 当作 \(xy\) 平面「上方」的第三根轴,把 \(\mathbb{R}^2\) 中的每个单元提升 lift 到 \(\mathcal{C}\) 中。这得到一个柱形分解:\(xy\) 平面里的每个单元产生一摞对应不同 \(\theta\) 的单元。回忆图 6.18、6.19 里的柱体:现在竖轴对应 \(\theta\),水平轴换成了 \(x\)、\(y\) 两根轴。

雷达图 Radar maps

为了在 \(\mathbb{R}^2\) 中构造分解,考虑图 6.22 中机器人与障碍的各种接触。图 6.22a 中固定 \((x,y)\),让线段绕一圈。出现两种接触:在某个朝向,线段碰到 \(v_1\),形成 Type EV 接触;在另外三个朝向,线段碰到边,形成 Type VE 接触。再次用特征的概念:线段在四个朝向接触到特征,每个特征是顶点或边。在与 \(e_2\)、\(e_3\) 的两次接触之间,机器人不碰撞,这些位形在 \(\mathcal{C}_{free}\) 中;位于 \(e_3\)(最右边那次接触)与 \(v_1\) 之间的位形也在 \(\mathcal{C}_{free}\) 中;其余朝向都在 \(\mathcal{C}_{obs}\) 中。注意:除非改变 \((x,y)\),线段无法从「\(e_2\) 与 \(e_3\) 之间」转到「\(e_3\) 与 \(v_1\) 之间」。所以它们应该对应分解中不同的单元。

图 6.22b 画出哪些 \(\theta\) 值会碰撞,我们称这种表示为雷达图 radar map。四个接触朝向由接触特征标出;记号 \([e_3,v_1]\) 与 \([e_2,e_3]\) 标出使 \((x,y,\theta)\in\mathcal{C}_{free}\) 的两个区间。把 \((x,y)\) 改变一点点得到 \((x',y')\),雷达图会怎样?接触发生的确切角度会变,但 \(\mathcal{C}_{free}\) 中位形的记号 \([e_3,v_1]\) 与 \([e_2,e_3]\) 不变。即使角度变了,接触关系没有任何有意思的变化;因此把 \((x,y,\theta)\) 与 \((x,y,\theta')\) 声明为 \(\mathcal{C}_{free}\) 中同一个单元是合理的——只要 \(\theta\) 与 \(\theta'\) 都把线段放在同样两个接触之间。想象 \((x,y)\) 附近一小块区域上方的一列 3-单元:一个对应 \([e_3,v_1]\) 中的朝向,另一个对应 \([e_2,e_3]\)。它们看上去是 \(\mathcal{C}_{free}\) 中的三维区域,因为 \(x\)、\(y\)、\(\theta\) 都可以扰动一点而不离开单元。

当然,\((x,y)\) 变得足够多时,雷达图终将发生剧烈变化。例如设想 \(e_3\) 无限长,在图 6.22a 中逐渐增大 \(x\):图 6.22b 中 \(v_1\) 与 \(e_2\) 之间的黑带逐渐缩短;当 \((x',y')\) 到 \(v_1\) 的距离超过 \(\mathcal{A}\) 的长度时,黑带消失(图 6.23)。注意这个变化非常重要:那个区域消失之后,任何「从 \(e_3\) 绕远路到 \(e_3\)」之间的朝向 \(\theta'\) 都给出 \((x',y',\theta')\in\mathcal{C}_{free}\)。这一点很重要,因为它告诉我们:可以先把机器人移得离 \(v_1\) 更远,转一下,再移回来,从而在原来的两个单元之间穿行。现在从图 6.23 的位置往 \(y\) 正方向移动:剩下的黑带开始缩短,当到 \(e_3\) 的距离超过机器人长度时最终消失——这是另一个关键变化。

雷达图可以用一个环形顺序 circular ordering 来刻画:

$$\big([f_1,f_2],[f_3,f_4],[f_5,f_6],\ldots,[f_{2k-1},f_{2k}]\big), \tag{6.6}$$

这里有 \(k\) 个朝向区间使位形落在 \(\mathcal{C}_{free}\) 中。图 6.22b 的雷达图给出 \(([e_3,v_1],[e_2,e_3])\)。每个 \(f_i\) 是一个特征,可以是边或顶点;有些 \(f_i\) 可以相同,比如图 6.23b 的表示是 \(([e_3,e_3])\)。区间按雷达图上的逆时针顺序列出;由于顺序是环形的,从哪个区间开始写都可以。有两种退化情形:若对所有 \(\theta\in[0,2\pi)\) 都有 \((x,y,\theta)\in\mathcal{C}_{free}\),记作 \(()\);若对所有 \(\theta\) 都在 \(\mathcal{C}_{obs}\) 中,记作 \(\emptyset\)。

试一试
  • 默认位置 (0, 0):右边的雷达图给出 \(([e_3,v_1],[e_2,e_3])\),与图 6.22b 一样(参考代码第 12 项)。拖动机器人末端改变 θ,红线在黑带里会变成虚线(碰撞)。
  • 把原点往右拖到 (0.6, 0) 附近:越过以 \(v_1\) 为心、半径 L 的紫色圆时,黑带消失,表示变成 \(([e_3,e_3])\),下方提示「两个自由区间合并成一个」——这就是图 6.23。
  • 再往右上拖到离 \(e_3\) 超过 L 的地方(越过与 \(e_3\) 平行的紫线):最后一段黑带消失,表示变成 \(()\)。把 L 调大调小,看紫色临界曲线怎样移动。

单元的关键变化 Critical changes in cells

现在可以更详细地解释单元分解了。想象沿 \(\mathbb{R}^2\) 中的一条路径移动,同时得到图 6.22b 雷达图的动画。每当 (6.6) 的环形顺序表示改变,就说发生了一次关键变化 critical change。变化发生在区间:1) 出现;2) 消失;3) 分裂;4) 合并;5) 某个区间的特征改变。第一个任务是把 \(\mathbb{R}^2\) 划分成不发生关键变化的极大 2-单元。每个这样的 2-单元 \(R\) 代表 \(\mathcal{C}_{free}\) 中一条 3-单元带的投影。每个 3-单元这样定义:令 \(\{R,[f_i,f_{i+1}]\}\) 表示 \(\mathcal{C}_{free}\) 中满足 \((x,y)\in R\)、且 \(\theta\) 使线段位于接触 \(f_i\) 与 \(f_{i+1}\) 之间的那个三维区域。\(R\) 上方的单元柱体由 (6.6) 表示中的每个区间对应的 \(\{R,[f_i,f_{i+1}]\}\) 给出。若在 \(R\) 中 \(\mathcal{A}\) 永远碰不到障碍、任何朝向都可以,就记作 \(\{R\}\)。

\(\mathbb{R}^2\) 中哪些位置会引起关键变化?共有五种情形,每种产生 \(\mathbb{R}^2\) 中的一组临界曲线 critical curves。越过其中一条曲线,就发生关键变化;不越过任何一条,就不会发生。所以这些曲线恰好定义了所求 2-单元的边界。设 \(L\) 是机器人(线段)的长度。

  1. (a) 到边的距离为 L(图 6.24a):与边 e 平行、相距 L 的直线——越过它,\(\mathcal{A}\) 开始或不再能碰到 e。
  2. (b) 到顶点的距离为 L(图 6.24b):以顶点 v 为心、半径 L 的圆。(a)(b) 两种在图 6.22、6.23 中已经见过:\((x,y)\) 到一条边或一个顶点的距离不超过 L 时出现。
  3. (c) 边在反射顶点处的延长线(图 6.24c):越过它,\(\mathcal{A}\) 从能碰到 e 变成能碰到 v。凡是在端点为反射顶点(内角大于 \(\pi\))的边,都要从那里延长出去。
  4. (d) 双切线(图 6.24d):图 6.10 的双切线情形回来了(它在最短路图里出现过)。若两个顶点相距不到 L,就产生一条直线临界曲线:从右往左越过它时,\(\mathcal{A}\) 不再能碰到 \(v_2\)。双切线总是成对地产生曲线,图中没画 \(v_2\) 上方那一条。
  5. (e) Nicomedes 蚌线(图 6.25):最复杂的情形,是一条四次代数曲线,来自 \(\mathcal{A}\) 同时接触 v 与 e。在泪滴形曲线内部,\(\mathcal{A}\) 能接触 e 但碰不到 v;刚出曲线,就又能碰到 v。若把 \(xy\) 坐标系放在 v 处、使 v 在 \((0,0)\),曲线的方程是
    $$(x^2 + y^2)(y + d)^2 - y^2L^2 = 0, \tag{6.7}$$
    其中 d 是 v 到 e 的距离7。
试一试
  • 沿 e 拖动接触点:机器人始终擦过 v、末端落在 e 上,它的原点(黑点)沿橙色的环走——这个环与紫色曲线(更正后的方程)完全重合,红色虚线(原书印的方程)只在对称轴 \(x = 0\) 上与它相交。
  • 把 d 调到 L 以上:v 离 e 太远,机器人不可能同时碰到两者,环消失。
  • 这正是习题 6 要你推导的方程:右边给出了用相似三角形的两行推导。

把所有曲线放在一起,就得到 \(\mathbb{R}^2\) 的一个单元分解:存在一些非临界区域 noncritical regions,在其上 (6.6) 不变,它们构成 2-单元;相邻 2-单元之间的边界是临界曲线的若干段,构成 1-单元;临界曲线相交处还有 0-单元。图 6.26 是一个改编自 Latombe 书的例子。注意:若临界曲线对应的位形全在 \(\mathcal{C}_{obs}\) 中,就不画出它。即使画了,方法仍然正确,只是多出一些不必要的单元边界。好玩的是,也可以用它们把 \(\mathcal{C}_{obs}\) 也做成一个漂亮的单元分解;但既然要避开 \(\mathcal{C}_{obs}\),最好别浪费时间分解它。这些不必要的情形可以这样识别:把 \(\mathcal{A}\) 想象成射程为 L 的激光,激光扫一圈时只有被它照到的特征才相关,被挡住的特征对应不必要的边界。

试一试
  • 这是仿照图 6.26 搭的楔形走廊(特征名 \(e_1\)–\(e_4\)、\(x_1\)、\(x_2\) 与原图对应)。点「给平面着色」:同色块内 (6.6) 的表示处处相同,色块的边界与紫色临界曲线吻合——这些色块就是非临界区域(图 6.26 的 \(R_1,\ldots,R_{13}\))。
  • 把机器人放进三角障碍尖端 \(x_1\) 附近,慢慢越过一条紫色蚌线:提示栏会报告是哪一种关键变化。
  • 把 L 调小:临界曲线向障碍收缩,区域变少;L 小于走廊宽度时,走廊里很多地方的表示变成 \(()\)。

在 \(\mathbb{R}^2\) 中构造好单元分解后,要把它提升到 \(\mathbb{R}^2\times[0,2\pi]/\sim\),在每个二维非临界区域 \(R\) 上方生成一个 3-单元柱体。路线图本可以给每个 3-单元和 2-单元各设一个顶点,与之前的单元分解保持一致;但为了让接下来的例子更容易理解,这里不给 2-单元设顶点。每个 3-单元 \(\{R,[f_i,f_{i+1}]\}\) 对应路线图的一个顶点;路线图的边连接以一个 2-单元为公共边界的相邻 3-单元——这意味着在 \(\mathbb{R}^2\) 中,它们共享某条临界曲线的一段一维部分。

构造路线图:问题是判断哪些 3-单元真正相邻。图 6.27 画出需要连接的情形(把 \(xy\) 平面表示成一根轴)。考虑平面里两个相邻的 2-单元(非临界区域)\(R\)、\(R'\),假设它们之间隔着一个 1-单元(临界曲线)。任务是把 \(R\)、\(R'\) 上方柱体中的 3-单元连起来。若相邻单元有相同的特征对,就连接,即 \(\{R,[f_i,f_{i+1}]\}\) 与 \(\{R',[f_i,f_{i+1}]\}\) 必须相连。有时一个特征会变而朝向区间不变——例如机器人从接触一条边变成接触这条边的一个顶点——这时也要连。图 6.27 还画了一种朝向区间分裂或合并的情形:从 \(R\) 走到 \(R'\),两个区域合并成一个,就要把原来的两个 3-单元都连到合并后的 3-单元。构造路线图的边时,应同时用 3-单元和 2-单元的样本点来保证路径无碰撞,就像 6.2.2 节的垂直分解那样。图 6.28 画出图 6.26 例子中的单元:每个非临界区域上方有一到三个单元,每个单元用一条指向该单元大致方向的(缩短了的)机器人表示。图 6.29 抽象地画出得到的路线图:每个顶点代表 \(\mathcal{C}_{free}\) 中的一个 3-单元,每条边代表相邻 3-单元之间穿过一个 2-单元。为了与前面的路线图一致,可以在每条边上插入一个顶点,强制路径经过对应 2-单元的样本点。

路线图建好后,就能像本章其它路线图一样回答查询。很多实现细节这里都略过了。由于第五种情形,\(\mathbb{R}^2\) 中有些区域的边界是四次代数曲线。避免显式刻画每个非临界区域边界的办法和其它实现细节见 Bañon 的论文,Latombe 的书里也有部分总结。

复杂度:最坏情况下能有多少个单元?先数 \(\mathbb{R}^2\) 中的非临界区域:前三种临界曲线各对应单个特征,共 \(O(n)\) 种生成方式;可惜双切线和蚌线基于特征对,有 \(O(n^2)\) 种。假设没有自交,\(\mathbb{R}^2\) 中 \(O(n^2)\) 条曲线最多相交出 \(O(n^4)\) 个区域。每个非临界区域上方可能有 \(O(n)\) 个 3-单元,所以单元分解的规模最坏是 \(O(n^5)\)。实际上这些交点不太可能全部出现,单元个数应该是合理的。存在构造这个分解的 \(O(n^5)\) 时间算法;6.5.3 节提到了运行时间好得多、但更难理解和实现的算法。

6.4 计算代数几何 Computational Algebraic Geometry

这一节的算法通用到能解 Formulation 4.1 的任何问题,甚至 4.4 节的闭链问题。这样的算法竟然存在,令人惊叹;可惜它们实现起来极具挑战,对大多数应用也不够高效。相关概念和工具主要是在计算实代数几何 computational real algebraic geometry 的背景下发展起来的,它们足以攻克机器人学、计算机视觉、几何建模、计算机辅助设计、几何定理证明中的许多问题,运动规划恰好是其中之一——它与计算代数几何的联系最早由 Schwartz 与 Sharir 认识到。

6.4.1 基本定义与概念:Tarski 语句与符号分配

本节建立在 3.1 节的半代数模型和 4.4.1 节的多项式定义之上。假设 \(\mathcal{C}\subseteq\mathbb{R}^n\),例如把 \(SO(2)\)、\(SO(3)\) 的每个副本表示成 2×2 或 3×3 矩阵就会这样。例如三维刚体的 \(\mathcal{C}=\mathbb{R}^3\times\mathbb{RP}^3\) 是六维流形,但可以嵌入 \(\mathbb{R}^{12}\)(\(\mathbb{R}^3\) 与所有 3×3 矩阵的集合的笛卡儿积)。迫使矩阵落在 \(SO(2)\) 或 \(SO(3)\) 中的约束都是多项式,可以加进 \(\mathcal{C}_{obs}\) 与 \(\mathcal{C}_{free}\) 的半代数模型。若 \(\mathcal{C}\) 的维数小于 \(n\),下面的算法仍然够用,但会有一些表示和复杂度上的问题,促使人们用特殊的参数化让两个维数相同、同时把 \(\mathcal{C}\) 的拓扑改成同胚于 \(\mathbb{R}^n\)(6.4.2 节末尾简单讨论)。

设 \(\mathbb{R}^n\) 中的模型都用 \(\mathbb{Q}[x_1,\ldots,x_n]\) 中的多项式表示——即有理数域 \(\mathbb{Q}\) 上的多项式(稍后解释为什么用 \(\mathbb{Q}\) 而不用 \(\mathbb{R}\))。记 \(f\in\mathbb{Q}[x_1,\ldots,x_n]\) 为一个多项式。

Tarski 语句 Tarski sentences

回忆 3.1 节构造的逻辑谓词,现在把它定义得更灵活一些。对任何 \(f\in\mathbb{Q}[x_1,\ldots,x_n]\),原子 atom 是形如 \(f\bowtie 0\) 的表达式,\(\bowtie\) 可以是 \(\{=,\neq,<,>,\le,\ge\}\) 中任一关系(3.1 节只用了 \(\le\))。无量词公式 quantifier-free formula \(\phi(x_1,\ldots,x_n)\) 是由原子和逻辑连接词「与」「或」「非」(\(\wedge\)、\(\vee\)、\(\neg\))组成的逻辑谓词;每个原子本身是一个逻辑谓词,当且仅当多项式在点 \((x_1,\ldots,x_n)\in\mathbb{R}^n\) 处取值满足关系时为 TRUE。

例 6.2(一个谓词):设 \(\phi\) 是 \(\mathbb{R}^3\) 上的谓词

$$\phi(x_1,x_2,x_3) = (x_1^2x_3 - x_2^4 < 0)\ \vee\ \big(\neg(3x_2x_3\neq 0)\wedge(2x_3^2 - x_1x_2x_3 + 2\ge 0)\big). \tag{6.8}$$

连接词的优先级按布尔代数的规则8。

设量词 quantifier \(\mathcal{Q}\) 是 \(\forall\)(「对所有」)或 \(\exists\)(「存在」)。Tarski 语句 \(\Phi\) 是还可以对部分或全部变量加量词的逻辑谓词,一般形如

$$\Phi(x_1,\ldots,x_{n-k}) = (\mathcal{Q}z_1)(\mathcal{Q}z_2)\cdots(\mathcal{Q}z_k)\ \phi(z_1,\ldots,z_k,x_1,\ldots,x_{n-k}), \tag{6.9}$$

\(z_i\) 是受量词约束的变量,\(x_i\) 是自由变量,\(\phi\) 是无量词公式。量词不一定非得写在最左边,但任何表达式都能化成 (6.9) 那样量词全在前面的等价形式:1) 去掉多余的量词;2) 重命名变量,使同一个变量不会既自由又受约束;3) 把否定号尽量往里推;4) 把量词推到左边。

例 6.3(几个 Tarski 语句):没有自由变量的 Tarski 语句,整体就是 TRUE 或 FALSE,因为没有可以依赖的参数。语句

$$\Phi = \forall x\,\exists y\ (x^2 - y < 0) \tag{6.10}$$

为 TRUE,因为对任何 \(x\in\mathbb{R}\),总能选 \(y\in\mathbb{R}\) 使 \(y>x^2\)。按 (6.9) 的记号,这里 \(\mathcal{Q}z_1=\forall x\)、\(\mathcal{Q}z_2=\exists y\)、\(\phi(z_1,z_2)=(x^2-y<0)\)。交换量词的顺序,得到 Tarski 语句

$$\Phi = \exists y\,\forall x\ (x^2 - y < 0), \tag{6.11}$$

它为 FALSE,因为对任何 \(y\),总有 \(x\) 使 \(x^2>y\)。再看一个带自由变量的 Tarski 语句:

$$\Phi(z) = \exists y\,\forall x\ (x^2 - zx^2 - y < 0). \tag{6.12}$$

它给出一个函数 \(\Phi:\mathbb{R}\to\{\mathrm{TRUE},\mathrm{FALSE}\}\):

$$\Phi(z) = \begin{cases}\mathrm{TRUE} & \text{若 } z\ge 1\\ \mathrm{FALSE} & \text{若 } z<1.\end{cases} \tag{6.13}$$

可以定义一个与 (6.12) 取值处处相同的等价无量词公式 \(\phi(z)=(z\ge 1)\)9。这会让人好奇:是否总能做这样的化简、把量词消掉?这叫量词消去问题,稍后解释。

试一试
  • (6.10):∀x∃y 的意思是「每一条竖线都碰到阴影」。拖动竖线,总能在上面找到阴影里的点(橙点)。
  • (6.11):∃y∀x 的意思是「有一整条横线都在阴影里」。不管把横线拖多高,它总会在 \(x=\pm\sqrt{y}\) 处穿出抛物线——FALSE。量词的顺序就是「竖线」与「横线」的区别。
  • (6.12):调 z。z < 1 时抛物线开口向上,找不到整条在阴影里的横线;点「z = 1」:抛物线压平成 \(y=0\),横线 \(y=1\) 整条在阴影里,Φ(1) 为真——所以无量词公式应是 \(z\ge 1\)。

判定问题 the decision problem:(6.10)、(6.11) 引出一个有趣的问题。考虑所有没有自由变量的 Tarski 语句,其中为 TRUE 的那些构成实数的一阶理论 first-order theory of the reals。能否设计一个算法判断这样一个语句是否为真?这叫实数一阶理论的判定问题。乍看似乎没希望:\(\mathbb{R}^n\) 不可数无穷,而算法只能处理有限集——这正是运动规划里一再遇到的问题。第 5 章的采样方法给出一类解法;用到判定问题上会同样缺乏完备性,因为不可能用采样检查 \(\mathbb{R}^n\) 中所有可能的点。相反,判定问题可以这样解:构造一个组合表示,把 \(\mathbb{R}^n\) 划分成有限个区域来精确地表示判定问题,每个区域里只需检查一个点。这已经很像运动规划里的单元分解了;结果,为判定问题发展的方法也能攻克运动规划。

量词消去问题 the quantifier-elimination problem:(6.12) 体现了另一个重要问题。考虑所有形如 (6.9) 的 Tarski 语句(可以有也可以没有自由变量)。能否设计算法,输入 \(\Phi\),输出等价的无量词公式 \(\phi\)?设 \(x_1,\ldots,x_n\) 是自由变量,等价是指两者在 \(\mathbb{R}^n\)(自由变量所有可能的赋值)上取同样的真值。给定 Tarski 语句 (6.9),量词消去问题就是找无量词公式 \(\phi\) 使

$$\Phi(x_1,\ldots,x_n) = \phi(x_1,\ldots,x_n) \tag{6.14}$$

对所有 \((x_1,\ldots,x_n)\in\mathbb{R}^n\) 成立。这等价于构造一个半代数模型,因为 \(\phi\) 总能写成

$$\phi(x_1,\ldots,x_n) = \bigvee_{i=1}^{k}\ \bigwedge_{j=1}^{m_i}\ \big(f_{i,j}(x_1,\ldots,x_n)\bowtie 0\big), \tag{6.15}$$

\(\bowtie\) 可以是 \(<\)、\(=\)、\(>\)。这看上去和 (3.6) 一样,区别是 (6.15) 用了 \(<\)、\(=\)、\(>\),可以表示开的和闭的半代数集;而 (3.6) 只用 \(\le\),为 \(\mathcal{O}\) 和 \(\mathcal{A}\) 构造闭的半代数集。问题同样定义在不可数的 \(\mathbb{R}^n\) 上,而算法只能处理有限表示——这由 6.4.2 节的单元分解技术来实现。

半代数分解 Semi-algebraic decomposition

如 6.3.1 节所说,在复形的每个单元里做运动规划应当很平凡。为了解判定问题和量词消去问题,人们发展了一种让这两个问题在每个单元里都变得平凡的单元分解:只需在每个单元里查一个点就能解判定问题。用 (6.15) 表示的半代数集 \(Y\subseteq\mathbb{R}^n\) 是

$$Y = \bigcup_{i=1}^{k}\ \bigcap_{j=1}^{m_i}\ \{(x_1,\ldots,x_n)\in\mathbb{R}^n \mid \mathrm{sgn}(f_{i,j}(x_1,\ldots,x_n)) = s_{i,j}\}, \tag{6.16}$$

sgn 是符号函数,每个 \(s_{i,j}\in\{-1,0,1\}\)(sgn 的值域)。3.1 节讲过的集合论与逻辑之间的漂亮关系再次出现:把 \(\cup\)、\(\cap\) 换成 \(\vee\)、\(\wedge\),集合论的描述就变成逻辑谓词。

定义:符号分配与半代数分解

设 \(\mathcal{F}\) 是 (6.16) 中出现的 \(m=\sum_{i=1}^k m_i\) 个多项式的集合。关于 \(\mathcal{F}\) 的符号分配 sign assignment 是向量值函数 \(\mathrm{sgn}_{\mathcal{F}}:\mathbb{R}^n\to\{-1,0,1\}^m\):每个 \(f\in\mathcal{F}\) 在符号向量里占一个位置,那里写 \(\mathrm{sgn}(f(x_1,\ldots,x_n))\in\{-1,0,1\}\)。半代数分解是把 \(\mathbb{R}^n\) 划分成有限个连通区域,每个区域符号不变 sign invariant——在区域里 \(\mathrm{sgn}_{\mathcal{F}}\) 保持常数。这些区域不叫「单元」,因为半代数分解不一定是 6.3.1 节定义的奇异复形:这里的区域可以有洞。

例 6.4(符号分配):回忆例 3.1 和 3.1.2 节的图 3.4。图 3.4a 是只有一个多项式 \(\mathcal{F}=\{x^2+y^2-4\}\) 的情形,符号分配是

$$\mathrm{sgn}_{\mathcal{F}}(x,y) = \begin{cases}-1 & \text{若 } x^2+y^2-4<0\\ 0 & \text{若 } x^2+y^2-4=0\\ 1 & \text{若 } x^2+y^2-4>0.\end{cases} \tag{6.17}$$

现在考虑图 3.4b 姜饼人脸的符号分配 \(\mathrm{sgn}_{\mathcal{F}}\)(图 6.30)。半代数模型的多项式是例 3.1 定义的 \(\mathcal{F}=\{f_1,f_2,f_3,f_4\}\),依次是「头」「左眼」「右眼」「嘴」,符号分配给出四维的符号向量。若 \((x,y)\) 落在 \(\mathcal{F}\) 中某个多项式的零点上,符号向量里就出现 0;若两条以上的曲线相交,交点处会出现多于一个 0。姜饼人脸的半代数分解有九个区域:五个二维区域,分别对应 1) 脸外、2) 左眼里、3) 右眼里、4) 嘴里、5) 脸里但在嘴和眼之外;四个一维区域,各对应一个多项式的零点集。得到的分解不是奇异复形,因为 \((-1,1,1,1)\) 那个区域有三个洞10。

试一试
  • 把鼠标在脸上移动:五个颜色块的符号向量各不相同;停在某条曲线上,对应位置变成 0。
  • 切换到「按例 3.1 的定义」:f₂、f₃、f₄ 的符号整体翻转,但区域的划分完全一样——符号约定不影响分解(参考代码第 9 项)。

图 6.30 这样的分解对运动规划没多大用,因为区域里有洞;需要进一步细化,这正好由柱形代数分解完成。另一方面,任何半代数分解都很适合解判定问题:每个区域里只需查一个点,就能判断某个没有自由变量的 Tarski 语句是否为真。为什么?如果多项式的符号在一个区域上不变,对应逻辑谓词 \(\Phi\) 的真值也就不变。所以每个符号不变区域只查一个点就够了。

6.4.2 柱形代数分解 Cylindrical Algebraic Decomposition

柱形代数分解是一种通用方法,它产生的柱形分解,与 6.3.2 节为多边形、6.3.4 节为线段机器人所做的柱形分解是同一个意思。它也以最初的发展者命名为 Collins 分解。图 6.19 其实就可以看作一个柱形代数分解,只是其中每个几何图元都是线性多项式。本节把这样的分解推广到 \(\mathbb{R}^n\) 中的任何半代数集。

思路是构造一串投影,每次把半代数集的维数降一。开始时集合定义在 \(\mathbb{R}^n\) 上,投影一次后得到 \(\mathbb{R}^{n-1}\) 中的半代数集;最终投影到 \(\mathbb{R}\),得到一个单变量多项式,它的零点正好是需要立单元边界的临界位置。划分 \(\mathbb{R}\) 得到由 1-单元(区间)和 0-单元组成的单元分解。然后把这个过程反过来,从 \(\mathbb{R}^2\) 一直到 \(\mathbb{R}^n\) 依次构造分解:每次迭代从 \(\mathbb{R}^i\) 的单元分解出发,提升 lift 成 \(\mathbb{R}^{i+1}\) 中的单元柱体。图 6.35 是姜饼人脸例子的分解;因为 \(n=2\),只有一次投影和一次提升。

半代数集的投影仍是半代数集

由 Tarski–Seidenberg 定理可以推出:把一个半代数集从 n 维投影到 n − 1 维,得到的仍是半代数集。

这给出半代数集在投影下的一种封闭性,它保证 \(\mathbb{R}^i\) 中半代数集的每次投影都得到 \(\mathbb{R}^{i-1}\) 中的半代数集。对 4.4.1 节介绍的(实)代数簇,这个性质不成立:代数簇只用 \(=\) 关系定义,在投影下不封闭。所以我们用半代数集是件好事(而不是巧合!)。

实代数数 Real algebraic numbers

如前所述,投影序列结束于 \(\mathbb{R}\) 上的一个单变量多项式,单元的边界由它的根的准确位置决定。此外,在 \(\mathbb{R}^n\) 的复形中为 \(k<n\) 维的单元取样本点需要完全精确:坐标稍有偏差,点就落到别的单元里去了。这就带来一个复杂的问题:这些根在计算机里怎样表示、怎样运算?

次数不超过 4 的单变量多项式有公式能用平方根和更高次方根表示所有根。由 Galois 理论知道,大多数更高次的多项式不存在这样的公式和漂亮表达式,而运动规划导出的复杂半代数模型里当然会出现高次多项式。\(\mathbb{R}\) 中的根可以是任何实数,很多实数需要无穷长的表示。避开这团乱麻的一个办法是:只用 \(\mathbb{Q}[x_1,\ldots,x_n]\) 中的多项式,而不用更一般的 \(\mathbb{R}[x_1,\ldots,x_n]\)。域 \(\mathbb{Q}\) 不是代数封闭的,因为多项式的零点可能在 \(\mathbb{Q}^n\) 之外:例如 \(f(x_1)=x_1^2-2\) 的零点是 \(x_1=\pm\sqrt2\),而 \(\sqrt2\notin\mathbb{Q}\)。另一方面,\(\mathbb{R}\) 中有些元素永远不可能是 \(\mathbb{Q}[x_1,\ldots,x_n]\) 中多项式的根。

\(\mathbb{Q}[x]\) 中所有多项式的所有实根构成的集合 \(\mathbb{A}\) 叫实代数数 real algebraic numbers。\(\mathbb{A}\subset\mathbb{R}\) 构成一个域(回忆 4.4.1 节)。\(\mathbb{A}\) 中的数有几条很好的算法性质:1) 都有有限表示;2) \(\mathbb{A}\) 中元素的加法、乘法能在多项式时间内完成;3) 不同的实代数数表示之间能在多项式时间内转换。这意味着所有运算都能高效完成,无需借助任何数值近似。在有些应用里近似没问题;但对代数分解,近似可能混淆根(比如怎样确知一个多项式有一个二重根,还是两个靠得很近的根?),从而破坏关键信息。

细节这里不展开,但表示实代数数并高效运算的方法有好几种,柱形代数分解的运行时间最终取决于这种表示。实际中可以用带精度参数 \(\epsilon\) 的数值求根方法,选足够小的 \(\epsilon\) 保证根不被混淆;用间隙定理 gap theorems(用多项式系数给出实根间距的下界)可以确定多小才算够小。有的方法不需要精度参数,一个著名的例子是由给定多项式导出 Sturm 序列,用它为每个根找出隔离区间 isolating intervals:多项式连同它的隔离区间,可以看作根的精确表示。用这种表示,代数运算甚至可以在 \(O(d\lg^2d)\) 时间内完成,\(d\) 是多项式的次数。

一维分解 One-dimensional decomposition

为了解释柱形代数分解,先对 \(\mathbb{R}\) 做半代数分解——它是投影序列的最后一步。弄懂这一步,多维情形就容易了。设 \(\mathcal{F}\) 是 \(m\) 个单变量多项式的集合

$$\mathcal{F} = \{f_i\in\mathbb{Q}[x]\mid i=1,\ldots,m\}, \tag{6.18}$$

它们用来定义 \(\mathbb{R}\) 中的某个半代数集。\(\mathcal{F}\) 中的多项式可以直接来自一个无量词公式 \(\phi\)(\(\phi\) 甚至可以出现在 (6.9) 那样的 Tarski 语句里)。定义一个多项式 \(f=\prod_{i=1}^m f_i\),设它有 \(k\) 个不同的实根,按递增顺序排好:

$$-\infty < \beta_1 < \beta_2 < \cdots < \beta_{i-1} < \beta_i < \beta_{i+1} < \cdots < \beta_k < \infty. \tag{6.19}$$

一维的半代数分解由下面交替出现的 1-单元和 0-单元给出:

$$(-\infty,\beta_1),\ [\beta_1,\beta_1],\ (\beta_1,\beta_2),\ \ldots,\ (\beta_{i-1},\beta_i),\ [\beta_i,\beta_i],\ (\beta_i,\beta_{i+1}),\ \ldots,\ [\beta_k,\beta_k],\ (\beta_k,\infty). \tag{6.20}$$

任何能用 \(\mathcal{F}\) 中的多项式表示的半代数集,也能表示成 (6.20) 中某些 0-单元和 1-单元的并。它也可以看作一个奇异复形(甚至可以看作单纯复形,但这推广不到高维)。

样本点:对无界单元 \((-\infty,\beta_1)\) 与 \((\beta_k,\infty)\),取 \(\beta_1-1\) 与 \(\beta_k+1\)11;对每个有限的 1-单元 \((\beta_i,\beta_{i+1})\),取中点 \((\beta_i+\beta_{i+1})/2\);对每个 0-单元 \([\beta_i,\beta_i]\),唯一的选择就是 \(\beta_i\) 本身。

例 6.5(一维分解):图 6.31 是由两个多项式 \(f_1(x)=x^2-2x\)、\(f_2(x)=x^2-4x+3\) 定义的 \(\mathbb{R}\) 的半代数子集 \([1,2]\),\(\mathcal{F}=\{f_1,f_2\}\)。考虑无量词公式

$$\phi(x) = (x^2-2x\le 0)\wedge(x^2-4x+3\le 0). \tag{6.21}$$

分解成五个 1-单元和四个 0-单元(图 6.32),每个单元符号不变。1-单元的样本点依次是 \(-1\)、\(1/2\)、\(3/2\)、\(5/2\)、\(4\);0-单元的样本点依次是 \(0,1,2,3\)。判定问题可以用这个分解漂亮地解决。假设给定一个用 \(\mathcal{F}\) 中多项式写成的 Tarski 语句,例如

$$\Phi = \exists x\,\big[(x^2-2x\le 0)\wedge(x^2-4x+3\le 0)\big]. \tag{6.22}$$

只看样本点就足以判定 \(\Phi\) 是真是假:一试到 \(x=1\),就发现 \(\Phi\) 为 TRUE12。量词消去问题这时还没法讨论,需要更多维数。

试一试
  • 选「更正:≤ 0」,连按「试下一个样本点」:−1、0、1/2 都不满足,试到 x = 1 才第一次为真,φ 的集合正好是图 6.31 的 [1, 2](参考代码第 8 项)。
  • 换回「原书 (6.21):≥ 0」:集合变成 (−∞,0] ∪ [3,∞),第一个样本 x = −1 就让 Φ 为真——与正文对不上,这就是脚注 12 说的笔误。
  • 拖动「把 f₂ 上下平移」:f₂ 的根移动、合并(重根)乃至消失,单元个数随之改变;但无论怎样,只查这有限几个样本点就能判定 ∃x φ(x)。

归纳到高维 The inductive step to higher dimensions

现在考虑为 \(\mathbb{R}^n\) 构造柱形代数分解(这个分解其实是半代数的)。图 6.35 是 \(\mathbb{R}^2\) 的例子。先考虑怎样把多项式一步步投影到 \(\mathbb{R}\),使得在构造 \(\mathbb{R}^n\) 的分解时保持符号不变性;得到的分解对应一个奇异复形。

有两种情形需要立单元边界(图 6.33):曲面在竖直方向上折叠,以及曲面相交。设 \(\mathcal{F}_n\) 是 \(\mathbb{Q}[x_1,\ldots,x_n]\) 中用来定义半代数集(或 Tarski 语句)的原始多项式集合。构造单个多项式 \(f=\prod_{i=1}^m f_i\),令 \(f'=\partial f/\partial x_n\)(它也是多项式),再令 \(g=\mathrm{GCD}(f,f')\)——\(f\) 与 \(f'\) 的最大公因式。\(g\) 的零点集就是同时是 \(f\) 和 \(f'\) 的零点的那些点。\(f'\) 为零意味着:沿 \(x_n\) 方向扰动时,曲面 \(f=0\) 局部不变——这些地方要立单元边界,因为曲面可能在 \(x_n\) 方向上折回自身,而柱形分解不允许这样。另一个需要立边界的地方是 \(\mathcal{F}_n\) 中两个以上多项式的交。从 \(\mathbb{R}^n\) 到 \(\mathbb{R}^{n-1}\) 的投影技术生成一组多项式 \(\mathcal{F}_{n-1}\subset\mathbb{Q}[x_1,\ldots,x_{n-1}]\),满足这些要求:在每个满足 \(f(x)=0\) 且 \(f'(x)=0\) 的点 \(x\in\mathbb{R}^n\) 正下方、或 \(\mathcal{F}_n\) 中多项式相交处的正下方,\(\mathcal{F}_{n-1}\) 至少有一个多项式在那里为零。构造 \(\mathcal{F}_{n-1}\) 的投影方法要计算主子结式系数 principal subresultant coefficients;子结式是结式 resultants 的推广。

然后把 \(\mathcal{F}_{n-1}\) 中的多项式投影到 \(\mathbb{R}^{n-2}\) 得到 \(\mathcal{F}_{n-2}\),一直进行到得到 \(\mathcal{F}_1\)——\(\mathbb{Q}[x_1]\) 中的一组多项式。照前面的做法构造一维分解:把它们乘成一个多项式,把 \(\mathbb{R}\) 划分成 0-单元与 1-单元。接下来描述把 \(\mathbb{R}^{i-1}\) 上的分解提升到 \(\mathbb{R}^i\) 的过程,反复应用直到 \(\mathbb{R}^n\)。

归纳地假设已经为 \(\mathbb{Q}[x_1,\ldots,x_{i-1}]\) 中的多项式集 \(\mathcal{F}_{i-1}\) 算出了柱形代数分解,它由 \(0\le k\le i-1\) 的 \(k\)-单元构成13。令 \(p=(x_1,\ldots,x_{i-1})\in\mathbb{R}^{i-1}\)。对每个 \(k\)-单元 \(C_{i-1}\),它上方的柱体 cylinder 定义为 \((k+1)\) 维集合

$$\{(p,x_i)\in\mathbb{R}^i\mid p\in C_{i-1}\}. \tag{6.23}$$

用 \(\mathcal{F}_i\) 中的多项式把柱体切成一条由 \(k\) 维与 \((k+1)\) 维单元组成的带。设 \(f_j\) 是柱体中 \(\ell\) 个切片多项式之一,按 \(x_i\) 递增排成 \(f_1,f_2,\ldots,f_j,f_{j+1},\ldots,f_\ell\)。产生下列几种单元(图 6.34):

  1. 下无界扇区 lower unbounded sector:\(\{(p,x_i)\in\mathbb{R}^i\mid p\in C_{i-1}\ \text{且}\ x_i<f_1(p)\}\)。(6.24)
  2. 截面 section:\(\{(p,x_i)\in\mathbb{R}^i\mid p\in C_{i-1}\ \text{且}\ x_i=f_j(p)\}\)。(6.25)
  3. 有界扇区 bounded sector:\(\{(p,x_i)\in\mathbb{R}^i\mid p\in C_{i-1}\ \text{且}\ f_j(p)<x_i<f_{j+1}(p)\}\)。(6.26)
  4. 上无界扇区 upper unbounded sector:\(\{(p,x_i)\in\mathbb{R}^i\mid p\in C_{i-1}\ \text{且}\ f_\ell(p)<x_i\}\)。(6.27)

(这里 \(f_j(p)\) 指第 \(j\) 个切片在 \(p\) 正上方的高度——书中沿用了多项式的名字。)

有一种退化的可能:柱体里没有切片多项式,整个柱体就是一个无界单元。一般地,样本点这样计算:在 \(C_{i-1}\) 中取一点 \(p\),竖起一列形如 \((p,x_i)\) 的样本——此时得到 \(\mathbb{Q}[x_i]\) 中的一个多项式,用一维分解的样本分配方法放置样本即可。

例 6.6(肢解姜饼人脸):图 6.35 是姜饼人脸的柱形代数分解。注意得到的复形与图 6.19 非常相似。图中有 37 个 2-单元、64 个 1-单元、28 个 0-单元;直的 1-单元是竖线的区间,弯的 1-单元是 \(\mathcal{F}\) 中某个多项式零点集的一段;下方还画出了 \(\mathbb{R}\) 的分解。

试一试
  • 默认参数下正好是 37 个 2-单元、64 个 1-单元、28 个 0-单元(参考代码第 10 项),编号方式与图 6.35 相同:从左到右、每列自下而上。把鼠标移到某个单元上,看它是哪个柱体里的哪种扇区或截面。
  • 拖动「嘴的半宽」:嘴伸出脸外时与 f₁ 相交,交点也变成投影的临界点,单元数变多(a = 2.3 时是 57 / 96 / 40)。把嘴缩到 a = 0.7 左右,竖线的顺序变了,总数却恰好还是 37 / 64 / 28;缩到 a < 0.4,嘴完全落在两眼之间,单元数就变少了。
  • 切到「三个圆」(习题 9 / 图 6.43),拖动圆心:两圆的交点把一个个新的 β 加到 ℝ 上。数一数单元,再和你手算的结果比一比。

注意,单元的投影不一定是矩形的集合(这和高维垂直分解不同)。例如 \(\mathbb{R}^n\) 分解中一个一般的 \(n\)-单元 \(C_n\) 可以描述为满足下列条件的 \((x_1,\ldots,x_n)\in\mathbb{R}^n\) 构成的开集(下标已按投影顺序整理,见脚注 13):

  • \(C_0<x_1<C_0'\),\(C_0,C_0'\in\mathbb{R}\) 是某两个 0-单元,它们是某些 \(f,f'\in\mathcal{F}_1\) 的根;
  • \((x_1,x_2)\) 位于某两个 1-单元 \(C_1\)、\(C_1'\) 之间,它们是某些 \(f,f'\in\mathcal{F}_2\) 的零点;
  • …… \((x_1,\ldots,x_i)\) 位于某两个 \((i-1)\)-单元 \(C_{i-1}\)、\(C'_{i-1}\) 之间,它们是某些 \(f,f'\in\mathcal{F}_i\) 的零点;……
  • \((x_1,\ldots,x_n)\) 位于某两个 \((n-1)\)-单元 \(C_{n-1}\)、\(C'_{n-1}\) 之间,它们是某些 \(f,f'\in\mathcal{F}_n\) 的零点。

得到的分解是符号不变的,所以判定问题和量词消去问题都能在有限时间内解决。解判定问题:在每个样本点处计算 \(\mathcal{F}_n\) 中的多项式,看是否有一个样本点满足 Tarski 语句。解量词消去问题:注意由 \(\mathcal{F}_n\) 能构造的任何半代数集都能写成分解中某些单元的并;对给定的 Tarski 语句,用其中出现的所有多项式组成 \(\mathcal{F}_n\) 再做单元分解,然后用符号信息决定哪些单元要放进并集里——这个并集恰好由使 Tarski 语句为 TRUE 的那些点组成。

解运动规划问题

柱形代数分解也能解第 4 章提出的任何运动规划问题。先假设 \(\mathcal{C}=\mathbb{R}^n\)。和其它分解一样,形成一张路线图:每个顶点是一个 \(n\)-单元,每对相邻的 \(n\)-单元——即能经过一个 \((n-1)\)-单元互相到达的——之间连一条边。在一个柱体内部判断邻接很直接;跨柱体的邻接则有一些技术细节(Basu–Pollack–Roy 的书第 152–154 页举了一个说明这个问题的例子)。维数低于 \(n-1\) 的单元对运动规划不需要(就像 6.2.2 节的垂直分解不需要 0-单元)。查询点 \(q_I\)、\(q_G\) 按所在单元连到路线图上,然后做离散搜索。

若 \(\mathcal{C}\subset\mathbb{R}^n\) 而它的维数 \(k<n\),那么所有有意思的单元都是低维的。例如为了让矩阵落在 \(SO(2)\) 或 \(SO(3)\) 中的约束就会导致这种情况;4.4 节中闭链减少了自由度的问题也会。柱形代数分解仍然能解这些问题,只是确定单元邻接时,精确的根表示问题更复杂。对 \(SO(2)\) 和 \(SO(3)\),可以用球极投影 stereographic projection 把 \(\mathbb{S}^1\) 映到 \(\mathbb{R}\)、把 \(\mathbb{S}^3\) 映到 \(\mathbb{R}^3\) 来回避这个麻烦:这个映射从每个空间去掉一个点,但 \(\mathcal{C}_{free}\) 的连通性不受影响。单位四元数 \(\mathbb{S}^3\) 的对径点等同也不成问题:只是多了一份 \(\mathcal{C}\) 的冗余拷贝,不影响连通性。

柱形代数分解的运行时间取决于许多因素,但一般来说,它是 \(\mathcal{F}_n\) 中多项式个数的多项式、多项式最高次数的多项式、而维数的双重指数。复杂度问题在 6.5.3 节详细讨论。

6.4.3 Canny 路线图算法 Canny's Roadmap Algorithm

柱形代数分解的双重指数运行时间激励研究者寻找更好的办法。已经证明量词消去需要双重指数时间;但运动规划是另一个问题。Canny 提出的方法直接从半代数集构造路线图,而不是途中先构造单元分解。由于柱形代数分解里有双重指数多个单元,避开这个构造是值得的。Canny 的路线图方法解运动规划问题的时间,仍是多项式个数和代数次数的多项式,但只是维数的单指数。

和其它组合方法一样,它基于寻找临界曲线和临界点。主要思想是构造从 \(\mathbb{R}^n\) 到 \(\mathbb{R}^2\) 的线性映射,产生半代数集的轮廓线 silhouette curves。对原始半代数集做一次这样的映射就得到一张路线图,但它可能没有保持原来的连通性。于是还要对原集合的某些 \((n-1)\) 维切片做从 \(\mathbb{R}^{n-1}\) 到 \(\mathbb{R}^2\) 的线性映射,得到更多路线图曲线。这个过程递归进行,直到切片已经是一维的。最终的路线图由所有递归调用得到的片段合并而成,它与原半代数集有相同的连通性。

设 \(\mathcal{C}=\mathbb{R}^n\),\(\mathcal{F}=\{f_1,\ldots,f_m\}\) 是定义半代数集的多项式,假设这个集合是若干流形的不交并,每个 \(f_i\in\mathbb{Q}[x_1,\ldots,x_n]\)。首先对输入多项式 \(\mathcal{F}\) 做一个小扰动,保证 \(\mathbb{R}^n\) 的每个符号不变集合都是流形——这迫使多项式处于某种一般位置,用随机扰动以概率 1 能做到,也有确定性的方法。对输入多项式和二维投影方向的一般位置要求相当强,这激发了后来消除其中很多问题的工作。从这里起假设多项式处于一般位置。

回忆 6.4.1 节的符号分配函数。由于一般位置假设,每个符号不变集合都是流形。Canny 的方法为任意 \(k<n\) 维流形计算路线图。这样的流形恰有 \(n-k\) 个符号为 0(即点落在 \(n-k\) 个多项式的零点集上)。至少要有一个符号为 0,这意味着 Canny 的路线图其实位于 \(\partial\mathcal{C}_{free}\) 中(严格说这不允许,但算法仍能正确判断是否存在穿过 \(\mathcal{C}_{free}\) 的解路径)。

每个 \(f_i\) 是函数 \(f_i:\mathbb{R}^n\to\mathbb{R}\),记 \(x=(x_1,\ldots,x_n)\in\mathbb{R}^n\)。把符号为零的那 \(k\) 个多项式依次放在一起14,得到映射 \(\psi:\mathbb{R}^n\to\mathbb{R}^k\),向量 \(\psi(x)\) 的第 \(i\) 个分量是 \(\psi_i(x)=f_i(x)\)。这与 6.4.1 节的符号分配函数密切相关,只是现在直接用每个多项式的实数值,而不取符号。再引入函数 \(g:\mathbb{R}^n\to\mathbb{R}^j\),\(j=1\) 或 \(j=2\)(下面的一般概念对其它 \(j\) 也成立,但 Canny 的方法只需要这两个值)。\(g\) 的作用与柱形代数分解里的投影相同,但它直接从 \(n\) 维降到 2 维或 1 维,而不像柱形投影那样降到 \(n-1\) 维。

令 \(h:\mathbb{R}^n\to\mathbb{R}^{k+j}\) 是由 \(\psi\) 和 \(g\) 直接构造的映射:第 \(i\) 个分量,若 \(i\le k\),\(h_i(x)=\psi_i(x)=f_i(x)\);若 \(i>k\),\(h_i(x)=g_{i-k}(x)\)。假设 \(k+j\le n\)。记 \(J_x(h)\) 为 \(h\) 在 \(x\) 处的 Jacobian:

$$J_x(h) = \begin{pmatrix}\frac{\partial h_1(x)}{\partial x_1} & \cdots & \frac{\partial h_1(x)}{\partial x_n}\\ \vdots & & \vdots\\ \frac{\partial h_{k+j}(x)}{\partial x_1} & \cdots & \frac{\partial h_{k+j}(x)}{\partial x_n}\end{pmatrix} = \begin{pmatrix}\frac{\partial f_1(x)}{\partial x_1} & \cdots & \frac{\partial f_1(x)}{\partial x_n}\\ \vdots & & \vdots\\ \frac{\partial f_k(x)}{\partial x_1} & \cdots & \frac{\partial f_k(x)}{\partial x_n}\\ \frac{\partial g_1(x)}{\partial x_1} & \cdots & \frac{\partial g_1(x)}{\partial x_n}\\ \vdots & & \vdots\\ \frac{\partial g_j(x)}{\partial x_1} & \cdots & \frac{\partial g_j(x)}{\partial x_n}\end{pmatrix}. \tag{6.28}$$

使 \(J_x(h)\) 奇异的点 \(x\in\mathbb{R}^n\) 称为临界点 critical point。矩阵奇异是指它的每个 \((k+j)\times(k+j)\) 子行列式都为零。\(J_x(h)\) 的前 \(k\) 行各自算出 \(f_i(x)=0\) 的曲面法向;若这些法向与后 \(j\) 行给出的方向不线性无关,矩阵就奇异。下面这个例子很好地说明了这个原理。

例 6.7(Canny 路线图算法):取 \(n=3\)、\(k=1\)、\(j=1\)。单个多项式 \(f_1\) 的零点定义 \(\mathbb{R}^3\) 的一个二维子集。设 \(f_1\) 是单位球面 \(\mathbb{S}^2\):

$$f_1(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2-1. \tag{6.29}$$

设 \(g:\mathbb{R}^3\to\mathbb{R}\) 为 \(g(x_1,x_2,x_3)=x_1\)。Jacobian (6.28) 变成

$$\begin{pmatrix}2x_1 & 2x_2 & 2x_3\\ 1 & 0 & 0\end{pmatrix}, \tag{6.30}$$

当三个可能的 2×2 子行列式都为零时它奇异,即当且仅当 \(x_2=x_3=0\)。这在 \(\mathbb{S}^2\) 上给出临界点 \((-1,0,0)\) 与 \((1,0,0)\)——正是 \(\mathbb{S}^2\) 的曲面法向平行于 \([1\ 0\ 0]\) 的地方。现在设 \(j=2\),得到 \(g:\mathbb{R}^3\to\mathbb{R}^2\),\(g(x_1,x_2,x_3)=(x_1,x_2)\)。这时 (6.28) 变成

$$\begin{pmatrix}2x_1 & 2x_2 & 2x_3\\ 1 & 0 & 0\\ 0 & 1 & 0\end{pmatrix}, \tag{6.31}$$

它奇异当且仅当 \(x_3=0\)。所以临界点是 \(x_1x_2\) 平面与 \(\mathbb{S}^2\) 的交15,给出赤道上的点(所有满足 \(x_1^2+x_2^2=1\) 的 \((x_1,x_2)\in\mathbb{R}^2\))。这时产生了更多的点,因为对于平行于 \([1\ 0\ 0]\)、\([0\ 1\ 0]\) 或它们任意线性组合的 \(\mathbb{S}^2\) 的曲面法向,矩阵都会退化。

例 6.7 的第一个映射给出两个孤立的临界点,第二个映射给出一个一维的临界点集,称为轮廓线。轮廓线与孤立临界点的并,就是 \(\mathbb{S}^2\) 的路线图。推广到一般的 \(n\) 和 \(k\),得到完整的算法:构造一个线性映射 \(g:\mathbb{R}^n\to\mathbb{R}^2\),它可能不像例 6.7 那样与坐标轴对齐,因为必须选在一般位置(否则路线图里可能出现退化)。令 \(\psi\) 为在要构造路线图的流形上为零的那组多项式,构造矩阵 (6.28),确定轮廓线——一般要用柱形代数分解中也需要的子结式技术。记 \(g_1\) 为 \(g\) 的第一个分量,即映射 \(g_1:\mathbb{R}^n\to\mathbb{R}\)。用 \(g_1\) 构造 (6.28) 得到有限个临界点。临界点与轮廓线的并构成路线图的一部分。

到这里为止,并不能保证连通性得到保持。为此 Canny 的算法递归进行:对每个临界点 \(x\in\mathbb{R}^n\),过 \(x\) 取一个 \(n-1\) 维超平面,以 (6.28) 中 \(g_1\) 那一行为法向(因此在某种意义上垂直于 \(g_1\) 的流动)。在这个超平面内构造新的 \(g\) 映射,这次方向重选,映射形如 \(g:\mathbb{R}^{n-1}\to\mathbb{R}^2\)。再一次求出轮廓线和临界点并加进路线图。这个过程递归地重复,直到到达基本情形:不用构造 \(g\) 就能直接得到轮廓线和临界点。由于方法涉及一串二维投影,很难可视化。\(\mathbb{R}^4\) 及更高维的问题会涉及两次以上的二维投影,因而更有意思;这里给的是 \(\mathbb{R}^3\) 上的例子,可惜只有一次投影。

例 6.8(环面上的 Canny 算法):考虑图 6.36 的三维代数集(实心环)。定义映射 \(g(x_1,x_2,x_3)=(x_1,x_2)\) 后得到图 6.37 的路线图:轮廓线由 \(g\) 得到,临界点由 \(g\) 的第一个分量 \(g_1\) 得到。注意实心环原来的连通性没有保持,因为内圈和外圈没有连起来。这说明还需要为低维切片计算路线图:对四个临界点中的每一个,在平行于 \(x_2x_3\) 平面、\(x_1\) 位置由临界点决定的平面里计算临界曲线。图 6.38 是一个内侧临界点处的切片,这时切片已经是二维的;新的轮廓曲线加进路线图,得到图 6.39 的最终结果。

试一试
  • 「例 6.7:球面」:用纬度、经度滑块移动探针。g = x₁ 时,只有转到 (±1, 0, 0) 两个红点上时三个 2×2 子式才同时为 0;g = (x₁, x₂) 时,只要纬度为 0(赤道)就有 det J = 2x₃ = 0。
  • 「例 6.8:环面」:只勾「轮廓线」——内外两个紫色圆互不相连,路线图没有保持实心环的连通性(图 6.37)。再勾上切片:内侧两个临界点处各有一条「8」字形曲线,把内圈接到外圈上(图 6.38、6.39;参考代码第 11 项核对了「8」字的自交点与它落在外圈上的位置)。
  • 改 r₁、r₂:「8」字碰到外圈的位置始终是 \(x_2=\pm2\sqrt{r_1r_2}\)(右边的俯视图)。

要解规划问题,把查询点 \(q_I\)、\(q_G\) 人为地声明为最顶层递归中的临界点,这迫使算法生成把它们连到路线图其余部分的曲线。方法的完备性需要非常仔细的分析,Basu–Pollack–Roy 的书和 Canny 的书里有透彻的论述。分析的主要内容是证明:1) 多项式可以被扰动、\(g\) 可以被选择,以保证一般位置;2) (6.28) 的奇异条件导出代数集(簇);3) 得到的路线图对 \(\mathcal{C}_{free}\) 具有 6.1 节要求的可达性和保持连通性(其实是对 \(\partial\mathcal{C}_{free}\) 证明的)。上面的方法为每个符号不变集合计算一张路线图,但要得到规划问题的路线图,来自各个符号不变集合的路线图必须正确地连起来——幸运的是 Canny 的 Linking Lemma 解决了这一点。然而一个大问题是:即使知道了路线图的连通性,得到路线图上每条曲线的参数化仍然是相当大的挑战。由于这一点和许多其它技术原因,目前似乎还不存在 Canny 算法的通用实现。另一个问题是需要 Whitney 分层 Whitney stratification(可以通过扰动输入来解决)。Basu–Pollack–Roy 路线图算法克服了这个问题。

6.5 运动规划的复杂度 Complexity of Motion Planning

这一节总结刻画运动规划问题复杂度的理论工作。注意这不等于刻画某个具体算法的运行时间。存在一个算法就给出了问题难度的上界 upper bound,因为它是一个「举例证明」:解这个问题所需的不会超过这个算法所需的。另一方面,下界 lower bounds 也非常有用,它们表明问题本身有多难。例如,假设你拿到一个 \(O(n^2)\) 的算法,还值得去找更高效的吗?值得去找运行时间是维数多项式的通用运动规划算法吗?下界能回答这类问题。下界通常靠构造一些古怪、复杂的例子得到——它们是问题定义所允许的,但最初提出问题的人往往没想到。在这方面的研究中,进展要么来自提高下界(除非已经紧了),要么来自证明问题更窄的版本仍然允许这些古怪的例子。后者在运动规划中很常见。

6.5.1 下界 Lower Bounds

许多运动规划问题以及更广泛的规划问题都已经有了下界。要解读这些下界,需要对计算理论有基本的了解,这里只能非常不公平地用几段话概括这个迷人的学科。问题 problem 是一组实例 instances,每个实例都仔细地编码成一个二进制串。算法形式上被看作一台 Turing 机:一个能在无界纸带上读写比特的有限状态机。也有其它计算模型,例如整数 RAM 和实数 RAM;关于哪个模型最合适有争论,尤其是在涉及实数的几何计算中。下面一律用标准的 Turing 机模型。算法通常被构造成产生二元输出:接受 accepting 或拒绝 rejecting 一个最初写在纸带上交给算法的问题实例。在运动规划中,这相当于判定一个给定的问题实例是否存在解路径。

语言 Languages:语言是与一个问题相关联的一组二进制串,它表示这个问题的全部实例。如果一个算法能在有限时间内正确地接受所有属于这个语言的串、拒绝所有其它串,就说它判定 decide 了这个语言。有意思的问题是:判定一个语言需要多少时间或空间?这个问题是针对问题问的,假设用的是最好的算法(我们很容易想出浪费资源的低效算法)。

复杂度类 complexity class 是能在某个资源限制内判定的所有语言的集合。类 P 是所有存在多项式时间算法的语言(因而问题)的集合(即算法运行时间为 \(O(n^k)\),\(k\) 是某个整数)。按定义,算法若在多项式时间内判定其对应的语言,就称为高效的 efficient注;若不存在高效算法,问题就称为难解的 intractable。理论运动规划中常出现的几个类之间的关系见图 6.40。类 NP 是能用非确定性 Turing 机在多项式时间内求解的语言(11.3.2 节会讨论非确定性机器);直观地说,解可以在多项式时间内被验证,因为机器神奇地知道判定过程中该做哪些选择。类 PSPACE 是能用多项式空间判定的语言(NPSPACE = PSPACE,所以没有非确定性版本)。类 EXPTIME 是能在 \(O(2^{n^k})\) 时间内判定的语言。已知 EXPTIME 比 P 大,但不知道 NP 与 PSPACE 的边界到底在哪里。有可能 P = NP = PSPACE(尽管几乎没人相信),也可能 NP = PSPACE = EXPTIME。

注(原书脚注 7):这个定义在实际中可能很荒谬——一个 \(O(n^{90125})\) 时间的算法对大多数用途大概都不算高效。

P NP PSPACE EXPTIME

图 6.40 的重画:已知 P ⊂ EXPTIME 是严格包含;NP 和 PSPACE 到底多大并不清楚。

难度与完全性 Hardness and completeness:由于较容易的类是较难的类的子集,有一个「某语言(问题)是某个类中最难的之一」的概念会很有帮助。令 X 表示 P、NP、PSPACE 或 EXPTIME 中的任一个。如果类 X 中的每个语言 B 都能多项式时间归约到语言 A,就称 A 是 X-hard 的。简言之,这意味着在多项式时间内,B 中的任何语言都能翻译成语言 A 的实例,再把 A 的判定结果在多项式时间内翻译回来,就正确地判定了 B。因此只要能判定 A,就能在多项式因子之内判定 X 中的每个语言。难度的概念甚至可以用于不属于这个类的语言(问题):例如即使 A ∉ NP(它可能更难,比如属于 EXPTIME),也可以说 A 是 NP-hard。如果已知一个语言对某个类 X 是 hard 的、同时又属于 X,就称它是 X-complete 的(即 NP-complete、PSPACE-complete 等)注。由于 P、NP、PSPACE 之间关系的不确定性,问题是 NP-hard 或 PSPACE-hard 时不能说它难解;但若问题是 EXPTIME-hard,就可以这么说。还要记住一点:PSPACE-hard 蕴含 NP-hard。

注(原书脚注 8):如果你记得听说过某个规划问题是「NP 什么」,却记不起是 NP-hard 还是 NP-complete,那么说它是 NP-hard 总是安全的,因为 NP-complete 蕴含 NP-hard。对 PSPACE-complete 与 PSPACE-hard 等其它类也一样。

运动规划的下界:一般的运动规划问题 Formulation 4.1 在 1979 年被 Reif 证明是 PSPACE-hard 的。事实上,问题限制在多面体障碍、以及由球铰连接的有限个多面体机器人刚体上;所有多面体的坐标都假设在 \(\mathbb{Q}\) 中(这使问题实例可以用有限长的串编码)。证明构造了一个迷人的运动规划实例:很多相连的、晃来晃去的机器人部件必须穿过一个复杂的隧道系统,整体模拟一台对称 Turing 机的运行。Canny 后来证明 Formulation 4.1(用有理系数多项式表示)属于 PSPACE。所以一般的运动规划问题是 PSPACE-complete 的。

许多其它规划问题也已经证明了下界。一个著名例子是图 6.41 的仓库管理员问题 Warehouseman's problem:在一个矩形世界里,有限个平移的、轴对齐的矩形。它被证明是 PSPACE-hard 的。这是一个漂亮的例子,说明看似简单的问题表述可以导致这么高的下界。最近甚至证明了推箱子游戏 Sokoban(离散二维网格上的仓库管理员问题)也是 PSPACE-hard 的。其它被证明 PSPACE-hard 的一般运动规划问题包括:平面中一串刚体的运动规划,以及 \(\mathbb{R}^3\) 中一串刚体在多面体障碍间的运动规划。对一般运动规划问题的各种扩展和变体也有很多下界。例如,已经证明三维多面体环境中机器人的某种不确定性规划是 NEXPTIME-hard 的,这比图 6.40 中的任何一类都难;NEXPTIME 中最难的问题被认为需要双重指数时间来求解。

表示的影响:下界或难度结果很大程度上取决于问题的精确表示。例如,可以用指数级过长的实例编码让问题显得更容易。运行时间或空间是以输入规模 \(n\) 来表示的;若运动规划实例用比必要多指数级的比特编码,就会得到一个属于 P 的语言。只要实例编码在最优编码的多项式因子之内(这可以用 Kolmogorov 复杂度来精确表述),这种怪异行为就能避免。表示的另一个重要方面是注意问题表述中的参数怎样变化。我们可以把运动规划重新定义为「\(\mathcal{C}\) 的维数从不超过 \(2^{1000}\) 的所有实例」——这个维数对几乎所有应用都足够大了。得到的语言属于 P,因为柱形代数分解和 Canny 的算法都能在多项式时间内解决这样的运动规划问题!为什么?因为表达式里的维数参数现在可以换成常数 \(2^{1000}\)。这在形式上意味着,对我们可能关心的任何运动规划问题,都已经有了高效算法。不过这个推论没有任何实际价值。所以解读理论界限时要非常小心。

下界看起来令人沮丧。从这里出发有两个大方向:一是削弱要求,容忍某种分辨率完备或概率完备的算法——第 5 章走的是这条路,并得到了许多高效的算法;二是定义更窄的问题,排除那些导致坏下界的古怪构造——6.2、6.3 节走的是这条路。6.5.3 节将介绍一些处理更窄问题的算法的上界,以及一般运动规划算法的上界。其中好几个上界涉及 Davenport–Schinzel 序列,下面先介绍它们。

6.5.2 Davenport–Schinzel 序列 Davenport-Schinzel Sequences

Davenport–Schinzel 序列有力地刻画了一族函数的下包络或上包络的结构。图 6.42 画出五个函数的下包络。这样的包络出现在计算几何的许多问题中,包括很多运动规划问题。它们是许多现代算法设计与分析的重要组成部分,算法的时间复杂度往往含有直接来自这些序列的项。所以在解读 6.5.3 节的一些结果之前,值得理解一点基础。

定义:(n, s) Davenport–Schinzel 序列

对正整数 \(n\)、\(s\),(n, s) Davenport–Schinzel 序列是由 \(n\) 个符号组成的序列 \((u_1,\ldots,u_m)\),满足:

  1. 同一个符号不能连续出现:对任何 \(1\le i<m\),\(u_i\neq u_{i+1}\)。
  2. 不含任何只用两个符号、长度为 \(s+2\) 的交替子序列(删去原序列中任意元素可以得到子序列)。即:不存在 \(s+2\) 个下标 \(i_1<i_2<\cdots<i_{s+2}\),使 \(u_{i_1}=u_{i_3}=u_{i_5}=\cdots=a\)、\(u_{i_2}=u_{i_4}=u_{i_6}=\cdots=b\),\(a\)、\(b\) 是某两个符号。

例如 (n, 3) 序列不能形如 \((a\cdots b\cdots a\cdots b\cdots a)\),每个 \(\cdots\) 可以填任意符号序列。记 \(\lambda_s(n)\) 为 (n, s) Davenport–Schinzel 序列可能的最大长度。

现在可以解释图 6.42 与这些序列的联系了:考虑依次经过下包络的函数下标序列,在这个例子里是 \((5,2,3,4,1)\)。假设已知每对函数至多相交 \(s\) 次;若有 \(n\) 个实值连续函数,函数下标序列一定是一个 (n, s) Davenport–Schinzel 序列。令人惊讶的是这样的序列不可能很长:对固定的 \(s\),它们接近线性。标准的界是

$$\begin{aligned} \lambda_1(n) &= n &(6.32)\\ \lambda_2(n) &= 2n-1 &(6.33)\\ \lambda_3(n) &= \Theta(n\,\alpha(n)) &(6.34)\\ \lambda_4(n) &= \Theta(n\cdot 2^{\alpha(n)}) &(6.35)\\ \lambda_{2s}(n) &\le n\cdot 2^{\alpha(n)^{s-1} + C_{2s}(n)} &(6.36)\\ \lambda_{2s+1}(n) &\le n\cdot 2^{\alpha(n)^{s-1}\lg\alpha(n) + C'_{2s+1}(n)} &(6.37)\\ \lambda_{2s}(n) &= \Omega\big(n\cdot 2^{\frac{1}{(s-1)!}\alpha(n)^{s-1} + C'_{2s}(n)}\big). &(6.38) \end{aligned}$$

上式中 \(C_r(n)\)、\(C'_r(n)\) 是比主导指数小的项(\(O\) 表示上界,\(\Omega\) 表示下界,\(\Theta\) 表示上下界都紧)。\(\alpha(n)\) 是反 Ackermann 函数,一个增长极其缓慢、在算法中频繁出现的函数。Ackermann 函数这样定义:令 \(A_1(m)=2m\),\(A_{n+1}(m)\) 表示把 \(A_n\) 作用 \(m\) 次。于是 \(A_1(m)\) 做加倍,\(A_2(m)\) 做幂运算,\(A_3(m)\) 做塔式幂运算 tower exponentiation,得到一叠高度为 \(m\) 的 2:

$$2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}. \tag{6.39}$$

Ackermann 函数定义为 \(A(n)=A_n(n)\)。它增长得极快:\(A(4)\) 已经是一座高度为 65536 的 2 的指数塔。所以反 Ackermann 函数 \(\alpha\) 增长得非常慢:只要 \(n\) 不超过一座 65536 个 2 的指数塔,就有 \(\alpha(n)\le 4\)。即使它出现在 Davenport–Schinzel 界的指数上,也算不上显著的增长。(参考代码第 14 项:\(A(1)=2\)、\(A(2)=4\)、\(A(3)=16\)、\(A_3(4)=65536\)。)

例 6.9(线段的下包络):Davenport–Schinzel 序列的一个有趣应用是 \(\mathbb{R}^2\) 中一组线段的下包络。由于处于一般位置的线段可能在下包络上出现多次,边的总数是 \(\Theta(\lambda_3(n))=\Theta(n\alpha(n))\),比无限长直线得到的要多。确实存在线段的排列达到这个界。

试一试
  • 「直线」:每条直线在下包络上至多出现一段,序列长度 ≤ n = λ₁(n)。换成「抛物线」:两两至多交两次,可以出现 \(a\,b\,a\) 这样的回头,但长度 ≤ 2n − 1。
  • 「线段」:多按几次「换一组」,常能看到同一条线段在下包络上出现两次(被别的线段截断后又露出来),但永远不会出现 \(a\cdots b\cdots a\cdots b\cdots a\)。拖动端点试着造一个——做不到。
  • 在下面的输入框里试 \(a\ b\ a\ b\ a\):它不是 (2, 3) 序列,却是 (2, 4) 序列。λ 的小值(如 λ₃(5) = 17、λ₃(6) = 22)由参考代码第 13 项暴力枚举得到。

6.5.3 上界 Upper Bounds

运动规划问题的上界来自求解它们的完备算法的存在。本节先讲基于 6.4 节方法的最一般的界,最后讲更简单的运动规划问题的界。

一般算法:Formulation 4.1 一般运动规划问题的第一个上界来自柱形代数分解的应用。令 \(n\) 为 \(\mathcal{C}\) 的维数,\(m\) 为 \(\mathcal{F}\) 中用来定义 \(\mathcal{C}_{obs}\) 的多项式个数(回忆 4.3.3 节,即使是简单例子它也增长得很快),\(d\) 为 \(\mathcal{F}\) 中多项式的最高次数。投影得到的多项式的最高次数以 \(O(d^{2^{n-1}})\) 为界,多项式总数以 \(O((md)^{3^{n-1}})\) 为界。用柱形代数分解做运动规划,总运行时间以 \((md)^{O(1)^n}\) 为界注。注意算法是维数 \(n\) 的双重指数,却是 \(m\) 和 \(d\) 的多项式。理论上,对维数有界的运动规划问题,它可以被称为是高效的(当然,在任何实际意义上它对运动规划都不高效)。

注(原书脚注 10):\(O(\cdot)\) 出现在表达式中间可能显得奇怪。在这里它的意思是存在某个 \(c\in[0,\infty)\),使运行时间以 \((md)^{c^n}\) 为界;注意不需要在整个式子前面再加一个 \(O\)。

由于一般问题是 PSPACE-complete 的,看来一个完备的一般运动规划算法不可避免地需要维数的指数时间。柱形代数分解是双重指数的,这让 1980 年代的许多人好奇这个上界能否降低。Canny 的路线图算法做到了:它的运行时间以 \(m^n(\lg m)d^{O(n^4)}\) 为界,因此是单指数的。这看起来已经很接近最优,因为它顶住了 PSPACE-hardness 似乎蕴含的下界(以及确实存在需要 \((md)^n\) 个连通分量的路线图的问题)。算法的复杂度很大一部分来自寻找一个合适的确定性扰动、把输入多项式置于一般位置。可以改用随机算法,其随机期望运行时间以 \(m^n(\lg m)d^{O(n^2)}\) 为界。对随机算法,随机期望运行时间仍是最坏情况的上界,只是对算法内部引入的随机「抛硬币」取平均;它不反映对输入分布的任何平均。这两个界是一般运动规划问题目前最好的上界。Canny 的算法也可以用来解 4.4 节的运动学闭合问题,但其复杂度没有反映代数簇的维数 \(k\) 小于 \(\mathcal{C}\) 的维数 \(n\) 这一事实;有一个特别适合这类问题的路线图算法,运行时间以 \(m^{k+1}d^{O(n^2)}\) 为界,这是 4.4 节问题目前最好的上界。

试一试
  • m、d 取默认值:n = 6 时双重指数那条线已经是 10 的几十次方,单指数那条还在 10 的十几次方。
  • 把 m 调大:两条线都抬高,但形状不变——两者对 m、d 都只是多项式;真正的差别只在维数 n 上。(补充示意:常数是我们取的,交点的位置没有意义。)

专门算法:下面总结一些更窄的问题的上界,它们比一般问题解得更高效。这些问题都只有两个或三个自由度,所以界比一般问题低得多。很多情况下会出现 6.5.2 节的 Davenport–Schinzel 序列。这里的大多数界基于不实用的算法,主要用来指出一个问题能得到的最好渐近性能。

问题已知的界
6.2 节:凸多边形 \(\mathcal{A}\)(\(k\) 条边)在 \(\mathbb{R}^2\) 中平移;\(\mathcal{O}\) 是 \(m\) 个内部不相交的凸多边形,共 \(n\) 条边\(\partial\mathcal{C}_{free}\)(用 Minkowski 差算,4.3.2 节)至多有 \(6m-12\) 个非反射顶点(内角小于 \(\pi\))和 \(n+km\) 个反射顶点(内角大于 \(\pi\))。\(\mathcal{C}_{free}\) 可以在 \(O((n+km)\lg^2n)\) 时间内分解并搜索;用随机算法降到 \(O((n+km)\cdot2^{\alpha(n)}\lg n)\) 随机期望时间。
非凸多边形 \(\mathcal{A}\)(\(k\) 条边)在类似的多边形区域 \(\mathcal{O}\)(\(n\) 条边)中平移Minkowski 差可能产生多达 \(\Omega(k^2n^2)\) 条边。只在 \(\mathcal{C}_{free}\) 的单个连通分量里搜索就能避免:用 Davenport–Schinzel 序列的分析,最坏的连通分量复杂度为 \(\Theta(kn\alpha(k))\),规划可以在 \(O(kn\lg^2n)\) 确定性时间、或 \(O(kn\cdot2^{\alpha(n)}\lg n)\) 随机期望时间内完成。
只平移,\(\mathcal{C}_{obs}\) 由 \(\mathbb{R}^2\) 中 \(n\) 条次数不超过 \(d\) 的代数曲线组成确定性 \(O(\lambda_{s+2}(n)\lg^2n)\),随机期望 \(O(\lambda_{s+2}(n)\lg n)\)。\(\lambda_{s+2}(n)\) 来自 (n, s+2) Davenport–Schinzel 序列的界 (6.37),\(s\le d^2\)。
6.3.4 节的线段机器人,障碍区域有 \(n\) 条边前面给了 \(O(n^5)\) 的算法——不是最好的,但比更高效的方法好懂。基于收缩的路线图算法 \(O(n^2\lg n\lg^*n)\)(\(\lg^*n\) 是对 \(n\) 反复取 lg 直到结果 ≤ 1 所需的次数,实际上可以当作 \(O(n^2\lg n)\));已知最紧的上界是 \(O(n^2\lg n)\)。已证明存在解路径需要 \(\Omega(n^2)\) 长度才能编码的例子。
\(\mathbb{R}^3\) 中的线段在多面体障碍(共 \(n\) 个顶点)间运动完备算法 \(O(n^{4+\epsilon})\)(任意 \(\epsilon>0\))16;已证明存在复杂度 \(\Omega(n^4)\) 的解路径。
\(\mathcal{C}=SE(2)\):凸多边形 \(\mathcal{A}\)(\(k\) 条边),多边形区域 \(\mathcal{O}\)(\(n\) 条边)\(\partial\mathcal{C}_{free}\) 至多 \(O(kn\lambda_6(kn))\) 条边,可以在 \(O(kn\lambda_6(kn)\lg kn)\) 时间内算出并解决规划问题;有一个 \(O(k^4n\lambda_3(n)\lg n)\) 的算法能给出机器人与障碍之间更好的间隙。\(\mathcal{A}\) 非凸的更一般情形有一个 \(O(k^3n^3\lg(kn))\) 的算法(而且真的实现过);此时 \(\mathcal{C}_{obs}\) 的面数可能高达 \(\Omega(k^3n^3)\)。只显式表示并搜索一个连通分量,已知最好的上界是 \(O((kn)^{2+\epsilon})\),\(\epsilon>0\) 可以任意小。
\(\mathcal{A}\) 在 \(\mathcal{W}=\mathbb{R}^3\) 中平移(\(\mathcal{C}=\mathbb{R}^3\))多面体的复杂度指面、边、顶点的总数。\(\mathcal{A}\) 复杂度为 \(k\)、\(\mathcal{O}\) 复杂度为 \(n\) 时,\(\partial\mathcal{C}_{free}\) 是复杂度 \(\Theta(k^3n^3)\) 的多面体曲面;限制在单个分量里搜索,可以在 \(O((kn)^{2+\epsilon})\) 时间内解决。若 \(\mathcal{A}\) 是凸的、有 \(m\) 个凸障碍,已知最好的界是 \(O(kmn\lg^2m)\)。更一般地,若 \(\mathcal{C}_{obs}\) 由 \(n\) 个最高次数为常数的代数曲面片围成,垂直分解方法能在 \(O(n^{2+\epsilon})\) 时间内解决 \(\mathcal{C}_{free}\) 单个连通分量里的运动规划问题。

延伸阅读 Further Reading

组合规划的大部分文献比采样规划的文献古老得多。Schwartz、Sharir、Hopcroft 编的文集收录了很多早期论文,包括 Reif 的 PSPACE-hardness、Schwartz–Sharir 的「钢琴搬运工问题」系列和 O'Dunlaing–Sharir–Yap 的收缩法。Latombe 的经典教材《Robot Motion Planning》覆盖了本章的大部分方法;本章的组织方式与它不同——它把单元分解方法和路线图方法分成两类,而这里因为单元分解是用来构造路线图的,把两者统一了起来。组合算法、计算几何以及运动规划完备算法方面的材料,Goodman 与 O'Rourke 编的《Handbook of Discrete and Computational Geometry》里的综述是极好的参考。

6.2 节沿用了计算几何基础算法的思路。计算几何的入门(包括对垂直分解的清楚讲解)见 de Berg 等人的《Computational Geometry: Algorithms and Applications》;其它来源有 Boissonnat–Yvinec、Edelsbrunner、Preparata–Shamos。理解多边形最优分解的难处见 O'Rourke–Suri 的综述;最短路径的进一步阅读见 Mitchell 的综述等。

单元分解与胞腔复形在计算几何与代数拓扑中都非常重要。6.3 节只是从运动规划的角度简短地介绍。单纯复形可以看代数拓扑的教材(Kahn、Kinsey、Rotman);奇异复形见 Rotman。计算几何里出现各种单元分解,研究最多的是三角剖分和排列(arrangements,由一组图元——比如平面中的直线或圆——生成的区域)。运动规划中早期的单元分解方法见上面那本文集;计算拓扑的综述见 Vegter。

6.4 节内容最现代、最完整的参考是 Basu–Pollack–Roy 的《Algorithms in Real Algebraic Geometry》;Cox–Little–O'Shea 的《Ideals, Varieties, and Algorithms》是计算代数几何的温和入门。多项式代数计算的细节见 Mishra 的书,计算实代数几何的综述见 Mishra 的手册章节。柱形代数分解的其它一般参考是 Arnon、Collins 的论文;它在运动规划中的应用见 Latombe 的书与 Schwartz–Sharir。Canny 路线图算法的主要参考是 Canny 的书《The Complexity of Robot Motion Planning》;与 6.4.3 节相当的其它高层概述见 Choset 等人的《Principles of Robot Motion》和 Latombe 的书。变体与改进见 Basu–Pollack–Roy;Canny 路线图算法一个可能的基于函数的扩展见 Canny–Lin。

关于运动规划复杂度的进一步阅读,请参考 6.5 节给出的大量文献。

本章速查表

概念要点
完备 / 精确不做近似;有解必找到,无解必报告(第 5 章只有分辨率完备 / 概率完备)。代价:要仔细选择输入的表示。
路线图两条件可达性(任何 q 能简单地连到 S)+ 保持连通性(C_free 里连通 ⇒ S 里连通)。查询 = 连到 G + 图搜索。
双向边表顶点、面、半边三种记录;障碍在半边左侧;障碍环逆时针、洞环顺时针;切开 C_free 的边成对出现(twin)。
垂直单元分解每个顶点向上 / 下延伸射线(图 6.2 四种情形);2-单元是梯形或三角形(凸);样本点取在单元内部;平面扫描 + 平衡树,\(O(n\lg n)\)。
一般位置假设没有两点 x 相同、没有竖直边;简化叙述,但实现时最费工夫。
最大间隙路线图广义 Voronoi 图 / 收缩法;边–边、顶点–顶点 → 直线,顶点–边 → 抛物线;朴素 \(O(n^4)\),最好 \(O(n\lg n)\);形变收缩 \(h:X\times[0,1]\to X\) 的三条件。
最短路路线图简化可见性图:顶点 = 反射顶点(C_free 内角 > π),边 = 相邻反射顶点 + 双切线;查询连到所有可见顶点后 Dijkstra;\(O(n^3)\) → 径向扫描 \(O(n^2\lg n)\) → \(O(n\lg n+m)\);在 cl(C_free) 里才良定义。
(6.1)(6.2)\(f_l(p_1,p_2,p_3)\) ⇔ \(\det M>0\);(6.1) 为 FALSE ⇔ 两端邻点各在同侧 ⇔ 双切线。
单纯复形k-单纯形 (6.3) = k+1 个线性无关点的凸包;面 = 令某 \(\alpha_i=0\);条件:面也在 K 里;两单纯形之交是公共面或空。
奇异复形奇异 k-单纯形 \(\sigma:D^k\to X\);k-单元 \(\sigma(\mathrm{int}D^k)\);\(S_k\) 闭,k-单元在 \(S_k\) 中开。垂直分解是奇异复形而非单纯复形(例 6.1)。
二维分解三角剖分:n + 2h − 2 个三角形;把梯形切成三角形不是单纯复形;朴素 \(O(n^3)\),单调多边形 \(O(n\lg n)\)。柱形分解:竖线贯穿所有面,竖条内自由 / 障碍交替。凸单元数最少的分解是 NP-hard。
三维垂直分解只适用于分段线性 C_obs;扫描平面切出的每一片做二维垂直分解;3-单元由六个平面围成。
线段机器人C = ℝ²×S¹;雷达图 (6.6) \(([f_1,f_2],\ldots)\);关键变化:出现 / 消失 / 分裂 / 合并 / 换特征;五种临界曲线(平行线、圆、延长线、双切线、蚌线 (6.7));非临界区域上方提升出 3-单元柱体;\(O(n^5)\)。
Tarski 语句原子 \(f\bowtie0\),无量词公式,(6.9) 前束形;判定问题(无自由变量)与量词消去问题 (6.14)(6.15);量词顺序很要紧。
半代数分解符号分配 \(\mathrm{sgn}_{\mathcal F}\);符号不变区域(可有洞);判定问题每区域查一点。
柱形代数分解投影(折叠 \(f=f'=0\)、相交)到 ℝ,一维分解 (6.20),再逐层提升:扇区 / 截面 (6.24)–(6.27);Tarski–Seidenberg;实代数数;维数的双重指数;姜饼人脸 37 / 64 / 28。
Canny 路线图\(h=(\psi,g)\),Jacobian (6.28) 奇异 = 临界点;轮廓线 + 临界点 + 过临界点的切片递归;查询点当临界点;维数的单指数;没有通用实现。
下界Formulation 4.1 是 PSPACE-complete(Reif 下界、Canny 上界);仓库管理员问题、Sokoban PSPACE-hard;PSPACE-hard ⇒ NP-hard;编码与参数的选择会扭曲结论。
DS 序列(n,s):无相邻重复、无长 s+2 的双符号交替;下包络序列;λ₁ = n,λ₂ = 2n−1,λ₃ = Θ(nα(n));α(n) ≤ 4 在实际中恒成立。
上界CAD \((md)^{O(1)^n}\);Canny \(m^n(\lg m)d^{O(n^4)}\),随机 \(d^{O(n^2)}\);专门问题见 6.5.3 节表格。

常见陷阱

  1. 把两种「失败」混为一谈:组合算法报告「无解」是一个证明;PRM / RRT 找不到路径只说明「在这些样本下没找到」。
  2. 样本点放在单元边界上:相邻单元样本点之间的线段可能擦碰障碍(脚注 3)。垂直分解要把样本点取在 2-单元内部,竖直线段取中点。
  3. 忽视一般位置:理论上「假设没有两点 x 相同」很轻松,实现时竖直边、共线点会让扫描算法崩掉。要么认真处理特例(习题 1),要么小心地扰动。
  4. 以为把梯形对半切就得到三角剖分(单纯复形):会出现 T 形接头,违反「两单纯形之交是公共面」。
  5. 在开集 C_free 里求最短路:问题是病态的,必须在闭包里求,再把路径稍微推离障碍。
  6. 可见性图里漏了「沿障碍边走」的边,或多了非反射顶点:前者会漏掉贴着障碍边走的最短路;后者只是浪费(最短路不会在凹进去的顶点拐弯)。
  7. 记反了符号约定:图 6.30 的符号向量对应「未取负」的圆和椭圆方程,和例 3.1 (3.11) 的 \(f_2,f_3,f_4\) 正好相反(脚注 10)。
  8. 随手交换量词:∀x∃y 和 ∃y∀x 是完全不同的语句(例 6.3)。
  9. 在代数分解里用浮点数近似根:分不清「一个二重根」和「两个很近的根」,单元结构就错了;要用实代数数(如 Sturm 序列的隔离区间)。
  10. 把「维数有界时多项式时间」当成「实用」:取维数上限 \(2^{1000}\) 就能在形式上让一切运动规划「高效」,但毫无实际意义。同样,NP-hard、PSPACE-hard 不等于已证明难解,EXPTIME-hard 才是。
  11. 以为线段的下包络和直线一样是线性的:线段是「被截断」的函数,包络长度是 Θ(λ₃(n)) = Θ(nα(n))。
  12. 以为渐近最好的算法就该用:线性时间三角剖分、Canny 算法都几乎没人实现;常常应该选理论上差一点、却容易实现的算法。

习题导引

只给思路,不给完整解答。标「互动」的可以先在本页对应的图里做实验。

  1. 垂直分解的特例(两点 x 相同、竖直边,不许随机扰动):想象把坐标系转一个无穷小的角度——x 相同时按 y 排序就是这个效果;竖直边则相当于两个事件之间宽度为零的竖条。逐一检查图 6.2 的四种情形在这种「符号扰动」下怎样更新 L。(互动:「平面扫描」)
  2. 证明 (6.1) 并考虑所有类型的双切线:先证 \(f_l(p_1,p_2,p_5)\) 等价于「\(p_1\) 在有向直线 \(p_2\to p_5\) 左侧」(行列式的循环不变性)。两个凸多边形之间有四条公切线:两条「外公切线」和两条「内公切线」(分隔线),检查 (6.1) 对四种都给出 FALSE。(互动:「不用三角函数的双切线测试」)
  3. 用平面扫描求两个非凸多边形的并:事件除了顶点,还有两多边形边的交点(扫描过程中动态发现,插入事件队列);L 中相邻两边之间的区域属于并集,当且仅当至少一个多边形覆盖它——用「穿越计数」来维护。
  4. 边界含圆弧的垂直分解:除了顶点,圆弧上切线竖直的点(最左、最右点)也必须是事件——这正是图 6.33 的「折叠」情形;L 里的元素比较需要算圆弧与竖线的交点。
  5. 边界含圆弧的最短路路线图:最短路会沿凸圆弧「贴着走」一段;双切线换成「点–圆」「圆–圆」的公切线,路线图的边还要包括相邻切点之间的圆弧段。
  6. 推导 Nicomedes 蚌线的方程:以 v 为极点,原点 p、v、e 上的接触点 q 共线且 \(|pq| = L\),用相似三角形即可(答案应为更正后的 (6.7),注意原书的笔误)17。(互动:「Nicomedes 蚌线」)
  7. 分辨率完备的线段机器人规划:对每个 θ 精确算出 C_obs 切片(多边形,用垂直分解),θ 按 van der Corput 序列取(第 5 章),相邻(按角度排序后)切片中重叠的单元相连。样本稠密 ⇒ 分辨率完备,但仍不完备。
  8. 球面 \(\mathbb{S}^n\) 的柱形代数分解:先画 \(\mathbb{S}^1\)(投影到 \(x_1\) 轴,临界点 ±1)和 \(\mathbb{S}^2\)(投影到 \(x_1x_2\) 平面得到圆盘,再投影到 \(x_1\) 轴)。注意每一层投影后得到的仍是一个低一维的「球面 + 圆盘」结构,单元数可以写成递推式。
  9. 三个相交圆的柱形代数分解:除了每个圆的左右端点,每对圆的两个交点也都给出临界 x。(互动:「柱形代数分解」切到「三个圆」,它会数出图中这组位置的单元数;拖动圆心看看它怎样随交点的相对位置变化,再和你手算的结果比一比。)
  10. 用 (6.28) 验证环面的 Canny 路线图:取 \(\psi=f\)(式 6.40),\(g=(x_1,x_2)\):\(\partial f/\partial x_3 = 4x_3(\|x\|^2+r_1^2-r_2^2)\) 只在 \(x_3=0\) 为零,得到两条轮廓圆;再用 \(g_1=x_1\) 求临界点(四个),最后在内侧两个临界点处取 \(x_2x_3\) 切片。(互动:「Canny 路线图」的环面)
  11. 能平移并连续缩放的多边形机器人:顶点位置是 \((x,y)+s\,a_i\),对 \((x,y,s)\) 是线性的,所以 C_obs 是 \(\mathbb{R}^2\times(0,\infty)\) 中的多面体——直接用 6.3.3 节的三维垂直分解。剪切变换同理(顶点仍是参数的线性函数)。
  12. 平坦环面上的最短路路线图:把正方形复制成 3×3 的「平铺」(万有覆叠),在平铺上建可见性图,跨过等同边的直线段在环面上就是一条连续的直线;最短路在平铺上仍只在反射顶点处拐弯。
  13. –19. 实现题:13 → 「垂直单元分解 → 路线图 → 查询」与「平面扫描」(参考代码 decompose());14 → 「最大间隙路线图」(朴素算法);15 → 「三维垂直分解」的切片思路;16 → 「柱形分解」;17 → 「雷达图与临界曲线」;18 → 「一维分解」「柱形代数分解」,可以借助现成的计算代数几何软件包;19 → 习题 7 的算法。

脚注

1 原书说每条半边存一个指向它的「internal face」的指针,但没有明说是哪一侧的面;由于这里每条边只有一条半边(障碍在左),我们把它理解为左侧(障碍一侧)的面,于是自由空间的面只通过面记录的「外边界 / 内部分量」指针与半边相连。这是我们的读法(补充)。↩

2 原书脚注 3:例外是 6.5.3 节提到的一些算法,它们只维护一个连通分量以提高效率。原文写的是「\(\mathcal{C}_{obs}\) 的一个连通分量」;按 6.5.3 节的说法(「在 \(\mathcal{C}_{free}\) 的单个连通分量里搜索」),这里应为 \(\mathcal{C}_{free}\)——原书笔误(已对照 PDF 原页)。↩

3 原书脚注 4:这正是本书的定义与 Latombe 书第 1 章不同的原因——那里样本点不放在 2-单元的内部,于是对某些查询可能发生碰撞。↩

4 原书脚注 5:用 \(p_1\) 去减其余 \(k\) 个点,得到 \(k\) 个向量(\(k\le n\)),排成 \(k\times n\) 矩阵;线性无关要求至少有一个 \(k\times k\) 子式的行列式不为零。例如 \(k=2\) 时三点不能共线。↩

5 原书 (6.5) 写作 \(D^k=\{x\in\mathbb{R}^n\mid\|x\|\le1\}\),但前一句说的是 \(B^k\subset\mathbb{R}^k\),这里应为 \(\mathbb{R}^k\);接下来「σ 限制在 \(\mathrm{int}(D^k)\) 上是 \(D^k\) 与 \(C\) 之间的同胚」一句中的 \(D^k\) 也应为 \(\mathrm{int}(D^k)\)。两处都是小的记号笔误(已对照 PDF 原页),本页已改正。↩

6 原书写的是「通常可以把 \(\mathcal{C}_{obs}\) 分解成少得多的凸单元」以及「求带洞的多边形 \(\mathcal{C}_{obs}\) 的最少凸单元分解是 NP-hard」。按上下文(路线图建在自由空间的单元上),被分解的应是 \(\mathcal{C}_{free}\)——外边界之内、以障碍为洞的那个多边形区域。↩

7 原书笔误:原书 (6.7) 印作 \((x^2 - y^2)(y+d)^2 - y^2L^2 = 0\)(已对照 PDF 原页)。以 v 为极点、e 为直线 \(y=-d\)、杆长 L 的 Nicomedes 蚌线应为 \((x^2 + y^2)(y+d)^2 - y^2L^2 = 0\):原点 p 与接触点 q 在同一条过 v 的直线上、\(|pq|=L\),由相似三角形 \(|y+d|/L = |y|/\sqrt{x^2+y^2}\),平方即得。参考代码第 6 项对机械构造出的点检验:更正式的残差 ~\(10^{-16}\),原书的式子残差达 0.72。两式只在对称轴 \(x=0\) 上一致。↩

8 原书笔误:原书 (6.8) 中间的原子印作 \(\neg(3x^2x^3\neq0)\),用的是上标;变量是 \(x_1,x_2,x_3\),应为下标 \(3x_2x_3\)(已对照 PDF 原页)。↩

9 原书笔误:原书写「等价的无量词公式 \(\phi(z)=(z>1)\)」,但 (6.13) 本身(正确地)给出 \(\Phi(z)\) 在 \(z\ge1\) 时为 TRUE。\(z=1\) 时原子变成 \(-y<0\),取 \(y=1\) 即对所有 x 成立,所以应为 \(\phi(z)=(z\ge1)\)(已对照 PDF 原页;参考代码第 7 项)。↩

10 原书前后不一致:例 3.1 的 (3.11) 给 \(f_2,f_3,f_4\) 乘了 −1(使 \(\le0\) 表示圆、椭圆之外,见第 3 章 PDF 原页),按这个定义,眼睛里 \(f_2>0\)、脸里眼外 \(f_2<0\)。而图 6.30 把「左眼里」标为 \((-1,-1,1,1)\)、「脸里」标为 \((-1,1,1,1)\),对应的是未取负的方程。两种约定下区域的划分完全相同,只是 \(f_2,f_3,f_4\) 的符号整体相反(参考代码第 9 项);本页「符号分配」互动图可以在两种约定之间切换。另外,例 3.1 没有给出具体参数,本页用的是我们取的一组值(头半径 2,眼睛 \((\pm0.7,0.6)\) 半径 0.3,嘴 \((0,-0.7)\) 半轴 1.15、0.25),它恰好复现图 6.35 的单元数。↩

11 原书这里把两个无界单元写成 \([-\infty,\beta_1)\) 与 \((\beta_k,\infty]\),与 (6.20) 的 \((-\infty,\beta_1)\)、\((\beta_k,\infty)\) 不一致;只是括号的笔误,本页按 (6.20) 写。↩

12 原书笔误:原书 (6.21) 与 (6.22) 用的是 \(\ge 0\)(已对照 PDF 原页)。但 \((x^2-2x\ge0)\wedge(x^2-4x+3\ge0)\) 定义的是 \((-\infty,0]\cup[3,\infty)\),不是图 6.31 标出、图注也写明的 \([1,2]\);而且按 \(\ge\),第一个样本 \(x=-1\) 就使 Φ 为真,与正文「试到 \(x=1\) 才发现为真」对不上(\(f_1(1)=-1<0\))。两处都应为 \(\le 0\),本页已改正(参考代码第 8 项列出了两种写法的结果)。↩

13 两处记号问题(已对照 PDF 原页):① 原书说 \(\mathcal{F}_{i-1}\) 的分解「由 \(0\le k\le i\) 的 k-单元构成」,但那是 \(\mathbb{R}^{i-1}\) 的分解,应为 \(0\le k\le i-1\)。② 描述一般 n-单元的几条列表里,原书写成 \(C_0<x_n<C_0'\)、「\((x_{n-1},x_n)\) 位于 1-单元之间」、「\((x_{n-i+1},\ldots,x_n)\) 位于 i-单元 \(C_{i-1}\)、\(C'_{i-1}\) 之间」——下标与前文的投影顺序(\(\mathcal{F}_1\subset\mathbb{Q}[x_1]\))正好相反,并且 \(C_{i-1}\) 是 \((i-1)\)-单元而不是 i-单元。本页按前文的约定写成 \(x_1\)、\((x_1,x_2)\)、\((x_1,\ldots,x_i)\)。↩

14 两处记号问题(已对照 PDF 原页):① 前一段说「k 维流形恰有 n − k 个符号为 0」,这里又说「符号为零的那 k 个多项式」——k 先表示流形的维数、后表示为零的多项式个数(例 6.7 中 k = 1 个多项式,定义的是 2 维的球面)。② 原书 (6.28) 左边最后一行写作 \(h_{m+k}\),正文说奇异是指每个 \((m+k)\times(m+k)\) 子行列式为零;但 \(h:\mathbb{R}^n\to\mathbb{R}^{k+j}\) 只有 \(k+j\) 个分量(m 是 \(\mathcal{F}\) 中多项式的总数),应为 \(h_{k+j}\) 与 \((k+j)\times(k+j)\)。本页已改正。↩

15 原书笔误:原书写「临界点是 \(x_1x_2\) 平面与 \(\mathbb{S}^3\) 的交」;例 6.7 处理的是 \(\mathbb{R}^3\) 中的单位球面 \(\mathbb{S}^2\),应为 \(\mathbb{S}^2\)(同一段最后一句原书自己也写的是 \(\mathbb{S}^2\);已对照 PDF 原页)。↩

16 原书笔误:原书印作「\(O(n^4+\epsilon)\) for any \(\epsilon>0\)」(已对照 PDF 原页)。在 O 里加一个常数 \(\epsilon\) 没有意义,所引的 Koltun 的结果是 \(O(n^{4+\epsilon})\),应为指数上的 \(\epsilon\)。↩

17 原书习题 6 写「shown in Figure 6.24」,但蚌线画在图 6.25(图 6.24 的图注是「五种情形中的四种」)。小的交叉引用笔误(已对照 PDF 原页)。↩