Part III · 第 12 章
感知不确定下的规划 Planning Under Sensing Uncertainty
第 11 章引入了信息空间 information space(I-空间),并用许多例子帮助理解它。这一章真正去规划:感知不确定下的规划,归根到底就是在某个 I-空间里规划。我们会看到,通用算法只能对付极小的问题(I-空间爆炸得太快),所以本章的大部分篇幅属于更窄的问题类——定位、建图、追逃、操作——每一类都有利用其特殊结构的漂亮算法,能解决远比通用算法大得多的问题。
本章导读
本章的脉络。12.1 是在任何 I-空间上都能用、但只能对付很小问题的通用方法;后四节各自利用问题的结构,把 I-空间压缩到能处理的大小。
处理 I-空间时一个贯穿全章的哲学是:先设计一个 I-map,把 I-空间压缩得尽可能小、尽可能简单,得到一个导出 I-空间 derived I-space;然后利用「这个 I-空间还保留着全部必要的一般性」这一事实,设计一个专用算法高效地解新问题。最常用的导出 I-空间是 11.2.2 节的 \(\mathcal{I}_{ndet}\)(非确定 I-state = 可能状态的集合);11.2.3 节的 \(\mathcal{I}_{prob}\)(概率 I-state = 状态上的分布)也会出现。
第 6 章里我们看到,通用的运动规划算法只适用于简单问题,绕开它的办法要么是基于采样的技术,要么是专注于更窄的一类问题。把基于采样的思想用到 I-空间上很诱人,但(在写书时)这条路基本还没有人走过;所以本章大部分算法属于后一种思路。
- 12.1 通用方法:把 \(\mathcal{I}_{ndet}\) 或 \(\mathcal{I}_{prob}\) 当作一个普通的「大状态空间」,直接套用第 10 章的值迭代、策略迭代和图搜索。适用于一切问题,但只能处理几个到十几个状态。
- 12.2 定位 localization:地图已知,机器人要靠感知判断自己在地图上的哪里——实质是维护导出 I-state,并规划让它变小的动作。离散网格、连续多边形(组合方法)、概率方法(卡尔曼 / 粒子滤波)各一小节。
- 12.3 环境不确定与建图:机器人连自己所处的环境都不知道;状态空间和 I-空间同时考虑「可能的环境」和「在每个环境里可能的位置」。小心地分析 I-空间,往往能避免建立完整地图:迷宫搜索、D*、Bug 算法、间隙导航树、EM 建图。
- 12.4 基于可见性的追逃 pursuit-evasion:「捉迷藏」的形式化版本。追捕者提着灯笼,逃逸者速度无界、行为不可预测;非确定 I-state 描述逃逸者可能在哪。用临界曲线对 \(\mathcal{I}_{ndet}\) 做单元分解,得到一个有限的图搜索问题——很像 6.3.4 节为线段机器人找临界曲线的方法。
- 12.5 感知不确定下的操作规划:与 7.3.2 节不同,状态不再总是已知。12.5.1 介绍二十多年前为有界不确定模型提出的原像规划 preimage planning 框架;12.5.2 讨论感知极少、靠物体之间的物理作用获取信息的机器人——有些甚至完全不需要传感器。
前置:第 11 章(I-空间、I-map、\(\mathcal{I}_{ndet}\)、\(\mathcal{I}_{prob}\)、各种传感器模型)与第 10 章(值迭代、反向投影、Dijkstra 的非确定版本)。本章偶尔引用第 6 章(单元分解、最短路路线图)、第 7.6 节(覆盖规划)和第 8 章(漏斗)。参考代码 part3/code/ch12_sensing_uncertainty.py 核对了页面上出现的每个数值,以及下文标出的原书笔误。
蓝 = 机器人的真实状态、动作与走过的路;橙 = 非确定 I-state 里「还可能」的状态(自然可能的选择);紫 = 概率 I-state(信念、粒子);绿 = 目标、已确定、已清除;红 = 最坏情况、被污染;黄 = 当前看得见的区域 \(V(x)\)(与书中插图一致);深灰 = 障碍。
12.1 通用方法 General Methods
这一节为 11.1 节引入的问题给出规划方法。它们主要基于通用的动态规划,不利用问题的任何特殊结构,所以只能用于很小的状态空间;但因为极其通用,仍值得一讲。基本想法:用非确定 I-map 或概率 I-map,把问题完全写成导出 I-空间 \(\mathcal{I}_{ndet}\) 或 \(\mathcal{I}_{prob}\) 上的问题。一旦定义好导出信息转移方程(11.2.1 节),就可以想象 \(\mathcal{I}_{ndet}\) 或 \(\mathcal{I}_{prob}\) 是一个执行时能得到完美状态测量的状态空间——因为 I-state 总是已知的。
12.1.1 把 I-空间当作大状态空间 The Information Space as a Big State Space
任何用 Formulation 11.1 表述的问题(组件 \(X, U, \Theta, f, Y, h, x_I, X_G, L\)),都可以借助导出 I-state 转换成 Formulation 10.1 的问题——这正是 11.1.3 节末尾「把 I-空间当作大状态空间」的说法。下面的概念对任何充分 sufficient 的 I-map 都成立,但只讨论两个重要情形:\(\kappa_{ndet}\) 与 \(\kappa_{prob}\)。为了不与原问题的组件混淆,新表述的每个组件头上都加一个箭头。
| 项目 | 记号 | 说明 |
|---|---|---|
| 状态 | \(\vec x = \eta_{der}\) | 导出 I-state |
| 状态空间 | \(\vec X = \mathcal{I}_{der}\) | 导出 I-空间 |
| 动作空间 | \(\vec U = U\) | 原动作空间 |
| 自然动作空间 | \(\vec\Theta \subseteq Y\) | 原观测空间 |
| 状态转移方程 | \(\vec f(\vec x, \vec u, \vec\theta)\) | 自然动作就是观测 \(y\) |
| 初始状态 | \(\vec x_I = \eta_0\) | 初始 I-state,\(\eta_0\in\mathcal{I}_{der}\) |
| 目标集合 | \(\vec X_G\) | 原 \(X_G\) 的子集 |
| 代价泛函 | \(\vec L\) | 由原 \(L\) 导出 |
图 12.1:导出 I-空间可以当作一个普通的状态空间,在它上面做「完美状态信息」的规划。
新状态空间 \(\vec X = \mathcal{I}_{der}\),状态 \(\vec x\) 是导出 I-state。非确定不确定性下 \(\vec x_k\) 指 \(X_k(\eta_k)\)(\(\eta_k\) 是历史 I-state);概率不确定性下 \(\vec x_k\) 指 \(P(x_k|\eta_k)\)。动作空间不变:\(\vec U = U\)。
新表述里最奇怪的部分是自然动作空间 \(\vec\Theta(\vec x,\vec u)\)。Formulation 11.1 里的观测很像自然动作:它们不由机器人选择,而且(马上会看到)是新状态转移方程里唯一不可预测的部分。所以 \(\vec\Theta(\vec x,\vec u)\subseteq Y\),新的自然动作 \(\vec\theta\in\vec\Theta\) 就是一个观测:\(\vec\theta(\vec x,\vec u) = y\)。集合 \(\vec\Theta(\vec x,\vec u)\) 一般依赖于 \(\vec x\) 和 \(\vec u\),因为有些观测从某些状态根本收不到——例如测量机器人位置的传感器从不会错超过 1 米,那么离真实位置超过 1 米的观测就不可能。
导出状态转移方程 \(\vec f(\vec x_k,\vec u_k,\vec\theta_k)\) 给出新状态 \(\vec x_{k+1}\)。用原来的记号,它就是一个利用 \(\kappa(\eta_k)\)、\(u_k\)、\(y_k\) 计算下一个导出 I-state \(\kappa(\eta_{k+1})\) 的函数——因为用的是充分 I-map(11.2.1 节),这是可以做到的。
初始状态和目标集合是可选的。初始 I-state \(\eta_0\) 成为新的初始状态 \(\vec x_I = \eta_0\):在 \(\mathcal{I}_{ndet}\) 里它是 \(X\) 的子集,在 \(\mathcal{I}_{prob}\) 里是一个概率分布。非确定情形的新目标集合是
即那些保证真实状态落在 \(X_G\) 里的导出 I-state。概率版本可以要求「所有 \(P(x|\eta)\) 非零的状态都在 \(X_G\) 中」;也可以不要求非零而用一个阈值,例如只要 98% 确定已经到达目标。
代价泛函
Formulation 10.1 剩下的只有代价泛函。我们只用依赖状态与动作历史的代价模型——若代价依赖自然,就意味着代价直接依赖观测 \(y=\vec\theta\),这在 Formulation 11.1 里没有假设。一般的 \(K\) 阶段代价泛函写成
终止动作照常处理。\(\vec L\) 必须从原问题的 \(L\) 导出——而原问题的代价是用状态表达的,状态却是未知的。先看 \(\mathcal{I}_{prob}\):第 \(k\) 阶段的状态 \(x_k\) 服从 \(P(x_k|\eta_k)\),用期望给 \(\vec x_k\) 赋代价:
理想情况下 \(\mathcal{I}_{ndet}\) 也想写出类似的式子,但有一个问题:每一阶段都取最坏代价太悲观。例如相邻两个阶段可能都得到很高的代价,但它们各自对应 \(X\) 中不同的路径——没有什么约束让最坏情况分析落在同一条路径上。概率情形没有这个问题,因为概率可以赋给路径。非确定情形也能定义代价泛函,但动态规划所需的阶段可加性一般被破坏了。在一些限制下它仍能保持:设对每个历史 I-state \(\eta_k=\vec x_k\) 和 \(u_k\in U\),\(l(x_k,u_k)\) 在所有 \(x_k\in X_k(\eta_k)\) 上都相同,那么
其中 \(x_k\in X_k(\eta_k)\);以及
其中 \(x_F\in X_F(\eta_F)\)。
在导出 I-空间上的计划
导出 I-空间 \(\mathcal{I}_{ndet}\) 或 \(\mathcal{I}_{prob}\) 上的计划,也可以看作新状态空间 \(\vec X\) 上的计划。于是状态反馈又成为可能——只不过是在更大的状态空间 \(\vec X\) 上,而不是 \(X\) 上。由于观测的存在,动作的结果一般仍然不可预测。一个有趣的特殊情形是没有观测:这时 I-state 完全由机器人自己选的动作导出,因而是可预测的;新表述不再需要自然动作,退化成 Formulation 2.3。此时只要给定初始 I-state,就不再需要反馈,计划又可以写成一串动作。
即使原状态不可预测,未来的信息状态却可以预测——没有传感器时,新状态空间里的状态轨迹是完全可预测的。
12.1.2 非确定 I-空间的算法 Algorithms for Nondeterministic I-Spaces
在 \(\mathcal{I}_{ndet}\) 上表述好之后,10.2 节的方法可以直接用。主要限制是新状态空间 \(\vec X\) 比 \(X\) 大了指数倍:若 \(X\) 有 \(n\) 个状态,\(\vec X\) 就有 \(2^n-1\) 个状态(全部非空子集)。所以即使 10.2 节的某些方法实际能解一百万个状态的问题,也只对应原状态空间里约 20 个状态(\(2^{20}-1 = 1{,}048{,}575\))。处理大得多的问题,需要利用 I-空间特殊结构的专用方法,可能还要定义一个通向更小导出 I-空间的 I-map。
值迭代
10.2.1 节的值迭代无需修改即可使用。第一步用 (12.6) 初始化 \(G^*_F\)。在新问题的记号下,动态规划递推 (10.39) 成为
其中 \(\vec x_{k+1} = \vec f(\vec x_k,\vec u_k,\vec\theta_k)\)。计算 (12.7) 的主要困难是确定取最大值的集合 \(\vec\Theta(\vec x,\vec u)\)。假设用的是 11.1.1 节的状态-自然传感器映射。从 I-state \(\vec x_k = X_k(\eta_k)\) 出发施加 \(\vec u_k = u_k\),得到前向投影 \(X_{k+1}(\eta_k,u_k)\);所有可能的观测是
不用前向投影,也可以写成更长的等价形式:
对别的传感模型可以写出别的变体(习题 16、17)。
策略迭代、图搜索与无传感器情形
- 策略迭代(10.2.2 节)原则上可用,但不太可能解出有挑战的问题。例如 \(|X| = 10\) 时,每次迭代都要解含一百万个元素的矩阵(\(1023\times1023\))!好在许多应用里它们很可能是稀疏的。
- 图搜索:10.2.3 节基于反向投影的方法也能用于这个表述,初始时令 \(S = \vec X_G\)。若初始非空,可以尝试图 10.6 的通用算法;图 10.8 的 Dijkstra 算法能给出最坏情况最优的计划。
- 无传感器情形:没有传感器时可以用更好的方法,因为 Formulation 10.1 退化成了 Formulation 2.3:可以用 2.3 节更简单的值迭代或 Dijkstra;若不要求最优,2.2 节的任何搜索方法都行,比如在 \(\vec X\) 上做双向搜索,把 \(\vec x_I\) 连到某个 \(\vec x_G\)。
下面这个补充的小例子把上面的公式全部落到实处:五格走廊里的机器人不知道自己在哪,导出状态是「可能位置的集合」;表格列出从 \(X\) 出发可达的全部 I-state、(12.7) 算出的最坏情况代价 \(G^*\)、最优动作和 (12.8) 的 \(\vec\Theta\)。
- 默认(无自然、无传感器):一直按 L 四次就一定到 1 号格——「没有观测时 I-state 的路径可预测」,计划就是一串动作。把目标改到中间格,看 \(G^*(X)\) 怎么变。
- 把自然改成「可能打滑」:没有传感器时 \(G^*(X)=\infty\);加上「在 1 号格吗」传感器还是 \(\infty\)——只问最坏情况,自然可以让你永远打滑。这就是 12.1.1 末尾说的「最坏情况太悲观」的一种表现。
- 自然改成「可能冲过头」、传感器选「位置奇偶」:同一个动作之后可能收到不同的观测,\(\vec\Theta(\vec x,u)\) 有两个元素,表格的最后一列会列出来;执行时切换「对抗 / 随机」,看 I-state 的序列怎样依赖于自然。
12.1.3 概率 I-空间的算法(POMDP) Algorithms for Probabilistic I-Spaces (POMDPs)
概率情形里 10.2 节的方法不能直接用,因为 \(\mathcal{I}_{prob}\) 是连续空间,需要 10.6 节处理连续状态空间的动态规划。主要困难是 \(\vec X\) 的维数随 \(X\) 的状态数线性增长:\(X\) 有 \(n\) 个状态时,\(\vec X\) 是 \(n-1\) 维单纯形。10.6 节的方法受维数灾难所困,所以通用的动态规划技术只能用于 \(X\) 只有寥寥几个状态的问题。这类问题在运筹学与人工智能文献里叫部分可观马尔可夫决策过程 POMDP。
近似值迭代
10.6 节的连续空间方法可以直接拿来:在 \(\vec X\) 上插值得到代价到目标 cost-to-go 的值。采样点上的初始值 \(G^*_F\) 由终端代价给出4。仿照 (10.46),动态规划递推是
若 \(\vec\Theta(\vec x,\vec u)\) 有限,概率质量就分布在有限个点 \(y=\vec\theta\in\vec\Theta(\vec x,\vec u)\) 上,于是 \(P(\vec x_{k+1}|\vec x_k,\vec u_k)\) 也分布在 \(\vec X\) 的一个有限子集上。这有点不寻常:\(\vec X\) 是连续空间,通常需要概率密度;有限个未来状态让 (12.10) 能用求和而不是积分——严格说得到的是一个用 Dirac 函数表示的密度(只在单点上有非零概率质量,而这在构造连续概率密度时本来是不允许的)。仍然需要近似,因为 \(\vec x_{k+1}\) 一般不正好落在 \(G^*_{k+1}\) 的采样点上。
精确方法
阶段数很少时,精确表示在实践中是可以算的。有些方法基于这样的观察:最优的值函数是分段线性且凸的 [86]10;于是得到一个线性规划问题,可以用 9.3 节求零和博弈随机化鞍点的技术解。约束太多,于是有人提出了能在某些情况下大幅削减约束个数的方法(见章末的 POMDP 文献)。
书中还描述了一种精确的离散表示:设初始条件空间 \(\mathcal{I}_0\) 只有一个初始条件 \(\eta_0\)(或有限个),并且最多 \(K\) 个决策阶段。\(\Theta(x,u)\) 与 \(\Psi(x)\) 有限,于是可能的终端 I-state \(\eta_F = (\eta_0,\tilde u_K,\tilde y_F)\) 只有有限个。对每一个算出分布 \(P(x_F|\eta_F)\),也就是 \(\vec x_F\),再用 (12.4) 算出每个可能的 \(\vec x_F\) 的 \(G^*(\vec x_F)\)。这些状态的个数不幸是阶段数的指数,但毕竟有限。然后对 \(k=K\) 用 (12.10) 回滚一个阶段——每个可能的 \(\vec x_{k+1}\) 都是已经算过值的点,不需要插值——如此反复直到第一阶段。鉴于 \(\mathcal{I}\) 极其庞大,这只对非常小的问题实用。
无传感器情形
没有观测时,在 \(\mathcal{I}_{prob}\) 中的路径是可预测的。假设要表述一个可行规划问题:比如执行过程中对 \(X\) 上的概率分布有复杂的约束。既然 \(\vec X=\mathcal{I}_{prob}\) 是连续空间,很容易想到用第 5 章的运动规划技术来找一条成功的路径——但它们必须改写成使用动作和状态转移函数(第 5 章没有这样做);这种改写在第 14 章讨论。它们可以用来在 I-空间中搜索一串动作,使其穿过 I-空间的同时满足概率上的硬约束。
下面的补充例子是最小的 POMDP:两扇门,一扇后面是坑。横轴是信念 \(b=P(\text{坑在右})\)——\(n=2\) 个状态,所以 \(\vec X\) 是一维的 \([0,1]\)。图中画出剩 \(k\) 步时的最优期望代价 \(G^*_k(b)\):它是一组直线(α-向量)的下包络,分段线性;每一步「听」的回溯让直线个数按组合增长,再剪掉从不取到最小值的那些。
- 把 \(k\) 从 1 拖到 10:\(k=1\) 时只有三条直线(走左门、听、走右门);之后中间「听」的区间变宽、包络上的线段变多,但始终是分段线性、凹的。对比「书中精确方法要枚举的 I-state」:\(\sum_{i\le k}6^i\) 个,指数增长。
- 拖动竖线到 \(b=0.5\),连按两次「听到坑在左」:信念按 (11.38)(11.39) 移向 0,跨过某个阈值后最优动作变成「走右门」。把「听的正确率」调低,阈值离 0.5 更远——信息越差,越要多听几次。
- 打开「插值近似 (12.10)」,把采样点 \(N\) 调到 3–5:只在少数信念上做值迭代再线性插值,误差可以很大(参考代码第 3 项:\(N=5\) 时 8 步后误差约 10,\(N=41\) 时约 0.24)。
12.2 定位 Localization
定位是机器人学的基本问题:移动机器人必须用传感器判断自己在某张环境地图里的位置。它有被动和主动两个版本:
机器人施加动作,它的位置通过计算非确定或概率 I-state 来推断。例如用卡尔曼滤波时,概率 I-state 由均值与协方差刻画:均值是位置的估计,协方差表示不确定的程度。
必须设计一个计划,尽可能减小定位的不确定性:机器人该怎么走,才能弄清自己在哪?
这一节两种版本都讨论。很多应用里定位是增量的:初始位形已知,任务是在运动中维持良好的估计。更极端的版本是绑架机器人问题 kidnapped-robot problem:机器人一开始对自己的位形一无所知。两者都可以用适当的初始条件建模;绑架机器人问题更难,本节默认讨论它。
12.2.1 离散定位 Discrete Localization
先研究离散版本能学到很多关于真实定位问题的经验:离散问题往往更容易理解,而且可以嵌入更复杂、甚至含连续状态空间的问题。为简化表述,这里只考虑非确定 I-空间 \(\mathcal{I}_{ndet}\),概率情形见 12.2.3 节。
设机器人在例 2.1 那样的二维网格上移动。它有网格的地图,但不知道自己在网格里的初始位置和朝向(图 12.2a)。状态里同时包含位置与朝向:机器人可以朝 N、E、W、S(北、东、西、南)四个方向之一,状态写成 \(x=(p,d)\),\(p\) 是位置,\(d\) 是方向。虽然机器人被当作一个点,朝向却很重要——它没有指南针;它选择往某个方向走(比如「正前方」)时,并不一定知道那是四个方向中的哪一个。同一位置的一组状态用指向可能方向的上标表示,例如书中的 \(3^{\llcorner}\) 表示位置 3 上朝北或朝东的状态;本页用箭头写成 \(3^{\uparrow\rightarrow}\)。
机器人有四个动作
分别是「前进 forward」「后退 backward」「右移 right motion」「左移 left motion」,都相对于机器人当前(可能未知)的朝向(图 12.2b):F 向前走一格、保持朝向;B 先转 180° 再向前走一格;R 先右转 90° 再走一格;L 类似。若因障碍走不了,就假设机器人改变了朝向(B、R、L 的情形)但不改变位置(图 12.3a)。
机器人只有一个简单的传感器:只能检测刚才尝试的那一步有没有走成。传感器空间 \(Y=\{0,1\}\),传感器映射 \(h: X\times X\to Y\):若 \(x_{k-1}\) 与 \(x_k\) 的位置不同,\(y=h(x_{k-1},x_k)=1\),否则为 0。也就是说,传感器指示每次动作之后机器人是否动了。
采用非确定不确定性,初始 I-state \(\eta_0\) 总是假设为 \(X\)(很容易推广到任意非空子集)。第 \(k\) 阶段的历史 I-state 一般形如
与 (11.14) 相比做了一个特别的调整:没有观测 \(y_1\),因为这个传感器需要「前一个状态」才能报告;所以观测历史从 \(y_2\) 开始。书中给的一个第 5 阶段历史 I-state 的例子是
其中 \(\eta_0=X\)、\(\tilde u_4=(R,R,F,L)\)、\((y_2,y_3,y_4,y_5)=(1,0,1,1)\)2。
被动定位问题从给定的地图(如图 12.2a)与历史 I-state \(\eta_k\) 出发,计算非确定 I-state \(X_k(\eta_k)\subseteq X\)。主动定位问题是求某个 \(k\) 与动作序列 \((u_1,\ldots,u_{k-1})\),使非确定 I-state 尽可能小。最好的情况下 \(X_k(\eta_k)\) 变成单元素集合,即机器人知道了自己在地图上的位置和朝向。然而由于对称性(马上用例子说明),这可能做不到。
解被动定位问题
被动问题只要求机器人运动时正确地计算非确定 I-state。两个例子:
例 12.1(一个容易的定位问题):图 12.2a 的地图。设机器人初始在位置 1、朝东。初始条件 \(\eta_0 = X\),可以写成
即 \(X\) 的全部 20 个状态。施加动作序列 \((F,L,F,L)\),每一步都发生了移动,观测历史是 \((y_2,y_3,y_4,y_5)=(1,1,1,1)\)。第一个动作 \(u_1=F\) 之后,历史 I-state 是 \(\eta_2=(X,F,1)\),非确定 I-state 是
也就是说每个位置都还可能,但成功的向前移动排除了一些朝向。例如 \(1^{\uparrow}\) 不可能,因为那样之前的状态就得在 1 的正南方——那里是障碍。第二个动作 \(u_2=L\) 之后,
只剩两个可能的状态。看图 12.2a 很容易理解:只有两个状态能先向前移动、再向左移动;初始状态必然是 \(1^{\rightarrow}\) 或 \(3^{\uparrow}\)。施加 \(u_3=F\) 之后,唯一的可能是 \(x_3\) 曾经是 \(3^{\uparrow}\),于是
这已经精确定位了机器人:它在位置 4,朝北。最后一个动作 \(u_4=L\) 之后显然
即在最终状态 \(x_5\),机器人在位置 5、朝西1。一旦精确知道了状态,就不会再累积新的不确定性,因为所有动作的效果都是可预测的。书中没有演示,但用不产生移动的动作也能剪除可能的状态。
例 12.2(涉及对称性的问题):把地图扩展成图 12.3b 那样的环。这时不可能确定机器人的精确位置。为简单起见只考虑产生移动的动作(可以自己验证:允许别的动作也解决不了问题)。设机器人初始在位置 1 朝东,执行 \((F,L,F,L,\ldots)\),它会绕着环一圈圈地走。问题在于,从位置 3 朝北出发也可以施加同样的动作序列:每个动作都成功移动了机器人,所以对机器人来说信息完全相同。另外两种情形是从 5 朝西、从 7 朝南出发。从 2 朝东出发执行 \((L,F,L,F,\ldots)\) 时也是类似的情况——还有哪三个初始状态能让这个序列每一步都移动?(参考代码第 5 项:4 朝北、6 朝西、8 朝南。)顺时针绕圈、用右转代替左转时,也存在类似的对称。这个问题的状态空间有 32 个状态;执行一些移动之后,非确定 I-state 最多能缩小到不超过四个可能状态的对称类 symmetry class。怎样证明?一种办法是使用下面介绍的算法。
- 点「例 12.1」,再一步步按「下一步」:右边的表格逐行重现 (12.15)–(12.18);第三步后只剩 \(4^{\uparrow}\),最后是 \(5^{\leftarrow}\)(位置 5,不是书中写的位置 1)。
- 点「例 12.2(对称)」:走一整圈之后 I-state 停在 \(1^{\rightarrow}\cup3^{\uparrow}\cup5^{\leftarrow}\cup7^{\downarrow}\),再怎么走也不会更小——状态栏显示「对称类」。勾上「有指南针」再点「指南针 + 环形」:两步 \((E,N)\) 就定位了,对称性消失。
- 点「习题 1」:在图 12.2a 上从位置 3 朝北出发执行 \((L,L,F,B,F,R,F,F)\),观察哪几步「没动」也帮了忙(比如第 1、3 步)。
解主动定位问题
前两个例子说明了怎样计算非确定 I-state,也就解决了网格上的被动定位问题。现在考虑构造一个解主动定位问题的计划。想象用计算机帮助完成这个任务,有两种总的思路:
规划算法在计算机上读入环境地图,计算一个信息反馈计划:对执行中可能出现的所有 I-state(可以用导出 I-空间),立即给出该采取的动作。执行时动作直接从存好的计划里查出来。
地图同样已知,但每个阶段需要动作时才计算它。计算机在机器人上运行,必须根据当前 I-state 决定采取哪个动作。
这里的取舍与 5.6 节基于采样的路线图类似:想执行得快,预先计算的计划可能更好;若太耗时间或空间,懒惰计划可能更好。
两种思路都要回到 12.1.1 节的表述:把 \(\mathcal{I}_{ndet}\) 当作新状态空间 \(\vec X\),在上面可以使用状态反馈。虽然没有自然的感知动作,观测仍然不可预测,因为状态一般未知——给定 \(\vec x_k\) 与 \(\vec u_k\),\(\vec\theta\) 与未来的新状态 \(\vec x_{k+1}\) 都不可预测。所以计划必须使用反馈:它需要执行中学到的信息才能解决问题。新状态空间上的状态转移函数 \(\vec f\) 已经在例 12.1、12.2 里演示过了。初始状态 \(\vec x_I\) 是全体原状态构成的集合。若没有对称性,目标集合 \(\vec X_G\) 是 \(X\) 的全部单元素子集;否则是所有可达的最小 I-state(不需要事先构造)。需要的话可以定义代价得到最优规划问题,例如运动发生时 \(\vec l(\vec x,\vec u)=2\),否则 \(\vec l(\vec x,\vec u)=1\)。
先看预先计算计划:12.1.2 节的方法一般可以算出一个解决「从任意初始非确定 I-state 出发的定位问题」的计划 \(\pi:\vec X\to U\)。这在空间上可能很费,因为 \(\vec X\) 的每个状态都要存一个动作:\(n\) 个格子时 \(|\vec X| = 2^n-1\)。若初始 I-state 总是 \(X\),就可以把 \(\pi\) 限制在 \(\vec X\) 小得多的一部分上:从任意 \(\vec x\in\vec X_G\) 出发,可以做基于反向投影的搜索;一旦初始 I-state 被加入 \(S\),这个部分计划就能可靠地完成定位。\(\vec X\) 中 \(\pi\) 没有定义的部分永远不会到达,可以忽略。
- 图 12.2a:\(2^{20}-1\) 个非空子集里,从 \(X\) 可达的只有 98 个;按书中代价(动了 2、没动 1)求出的最坏情况最优计划 \(G^*(X)=9\),最坏 6 步定位(参考代码第 6 项)。点地图换真实初始状态,看蓝色分支怎样沿观测走到一个单元素叶子。
- 换到环形地图:叶子都是 4 个状态的对称类——这就回答了例 12.2 末尾「怎样证明」的问题:在全部可达 I-state 上穷举,最小的就是 4。
- 换到习题 3 的图 12.54,再把代价换成「每步 1」:计划树的形状与第一步动作可能改变——「最优」取决于代价怎么定。
再看懒惰方法:机器人上的算法可以通过实际执行动作、观察得到哪些 I-state 来进行某种搜索。这导致 \(\vec X\) 上一个随机器人运动逐步显露的有向图。之所以有向,是因为关于状态的信息一般会改进:例如一旦机器人知道了自己的状态(或对称类),就不可能回到表示更大不确定性的 I-state。很多情况下机器人可能运气好、在执行中就定位了自己,用的内存比预先计算的计划少得多。
为了系统地搜索,机器人需要认出「同一个位置以不同方式到达」。即使不知道自己在地图上的位置,它通常能推断出是否到过某个地方。一种做法是给访问过的位置赋 \((i,j)\) 坐标:初始位置是 \((0,0)\);施加 F 后若机器人移到新格子,就到了 \((1,0)\);施加 R 后若没被挡就到了 \((0,1)\);点 \((2,1)\) 可以由 \((F,F,R)\) 或 \((R,F,F)\) 到达。可以理解为在机器人的初始位置附着了一个 \(\mathbb{R}^2\) 中的局部坐标系,称为里程坐标 odometric coordinates。这个坐标系与地图之间的方向起初未知,但一旦机器人精确定位,就能算出两者之间的变换。
于是可以从初始状态 \(\vec x_I\) 出发试各种动作,直到满足目标条件(例如再也到不了更小的非确定 I-state)。但它与 2.2.1 节的搜索有一个关键区别:以前搜索可以从任何已探索过的状态继续,没有额外代价。现在有两个问题:
- 改道路径 reroute paths:大多数搜索算法允许任何时候从任何已考虑过的状态展开新状态。懒惰方法里,机器人必须真的移动到某个状态并施加动作,才能知道能否到达新状态。机器人可以借助里程坐标回到任何已考虑过的状态,但这带来了以前的搜索问题里没有的代价:搜索不能在搜索树中跳来跳去,而是一条机器人实际走过的长长的连续路径。这种跳跃叫做改道路径,在 12.3.2 节很重要。
- 信息改进 information improvement:机器人甚至可能回不到以前的非确定 I-state。例如机器人执行 \((F,F,R)\) 后再用 \((B,L,F)\) 回到同一个状态,它确实知道自己回到了同一个状态,但这个状态仍然未知;不过执行 \((F,F,R)\) 之后它可能已经缩小了当前状态的可能性,用 \((B,L,F)\) 回来时非确定 I-state 就不同了。
结论是搜索算法要考虑移动机器人的代价,而且搜索图是有向的。第二个问题其实不是问题:回到同一个位置时 I-state 虽然可能不同,但总是至少一样好——若 \(\eta_1\)、\(\eta_2\) 是同一位置先后的历史 I-state,总有 \(X(\eta_2)\subseteq X(\eta_1)\)。在这个版本的定位问题里信息总是改进的;所以试图回到以前的 I-state 时,机器人会得到一个更好的 I-state。
别的信息模型
到目前为止的模型只是许多有趣选择之一。比如机器人带一个永远指示方向的指南针,就不需要把方向作为状态的一部分了:可以直接用全局方向来指定动作,\(U=\{N,E,W,S\}\)。例 12.1 和 12.2 都变得平凡:第一个用动作序列 \((E,N)\) 就解决了;例 12.2 的对称问题消失,也用 \((E,N)\) 解决,因为 \((1,2,3)\) 是唯一与动作和指南针读数相容的位置序列。
给机器人更少的信息也能得到有趣的模型。到目前为止,机器人很容易推断自己相对起点的位置:即使不知道起点在地图上的哪里,总能用相对坐标表达——因为它依赖不同形式的里程计。比如方向是 E 时执行 \((L,L,L)\),就知道方向变成了 S,因为三次左转等于一次右转。设机器人不是在网格上,而是要探索一个图:它通过施加穿过某条边的动作在顶点之间离散地移动。设这是一个嵌入 \(\mathbb{R}^2\)、用直线段画出的平面图,每个顶点可用的动作数不同。一般可以定义 \(U=\mathbb{S}^1\):只要某个方向被挡,机器人就只转身不平移(这是网格情形的推广),传感器指示哪些动作导致了平移。这时模型很好地推广了网格的原模型;若机器人知道到达一个顶点的各条边之间的夹角,就能用角度里程计建立一个跟踪相对位置的局部坐标系。
情况还可以让机器人更糊涂:设 \(U=\mathbb{S}^1\) 不再表示方向,而是每个顶点上的动作集合只指示可以穿过哪些边——机器人能施加动作穿过某条边,却不知道它相对其它边的方向。这时角度里程计就用不了了:它分不清菱形、梯形和矩形。若能用角度里程计,比较顶点处各边的夹角就能避免一些对称性;新模型不允许这样做,所有度数相同的顶点看起来都一样。
12.2.2 连续定位的组合方法 Combinatorial Methods for Continuous Localization
现在考虑 \(X\) 是 \(\mathbb{R}^2\) 中连续区域的情形:设 \(X\) 由一个简单多边形(闭的多边形链,没有内部的洞)围成,机器人已知 \(X\) 的地图。机器人的速度 \(\dot x\) 直接由动作 \(u\) 指挥,运动模型 \(\dot x = u\),\(U\) 是原点处的单位球。这样计划就可以像整个 Part II 那样写成 \(X\) 中的一条连续路径——不必指定速度 \(u\),直接给路径更简单(\(\dot x=u\) 与更一般的 \(\dot x=f(x,u)\) 分别见 8.4 节和第 13 章)。机器人用两个传感器:
- 指南针:完美的指南针解决了 12.2.1 节出现的所有朝向问题。
- 可见性传感器:图 11.15 那样的可见性传感器,在所有方向上给出完美的距离测量。
两个传感器都没有自然感知动作。和 12.2.1 节一样,定位就是计算非确定 I-state。有了完美的指南针和多边形在 \(\mathbb{R}^2\) 中的已知朝向,状态里不需要再表示朝向,所以非确定 I-state 就是 \(X\) 的子集。设想在没有历史的情况下为图 11.15 的例子计算非确定 I-state:这是 (11.6) 定义的 \(H(y)\subseteq X\),只用到当前读数——要算出所有能得到图 11.15b 那组距离测量的状态。这意味着要找一个平移,把图 11.15b 的边完全叠到图 11.15a 的多边形边上。记 \(\partial X\) 为 \(X\) 的边界,可见性传感器的距离测量必须精确对应 \(\partial X\) 的一个子集。在那个例子里,这只能从一个状态得到(图 11.15a),所以机器人根本不用为这个例子再去定位自己。
像 8.4.3 节那样,记 \(V(x)\) 为可见多边形 visibility polygon:从 \(x\) 看得见的所有点。为了高效地完成计算,必须先预处理多边形,确定可见多边形从 \(X\) 的不同位置看上去可能是什么样子——即仔细确定 \(\partial X\) 的哪些边会出现在 \(\partial V(x)\) 上。状态空间 \(X\) 可以分解成有限个单元,在每个区域上不变量是:描述 \(V(x)\) 的是同一组边 [17, 74]。图 12.4 是一个例子。构造这种分解要延伸两类射线:图 12.5 是一对互相可见的顶点、可以向外延伸射线的情形(右边那种情形就是图 6.10 的双切线,只是这里的边向外延伸,而不是像可见性图那样向内);另一种情形是图 12.6,在每个反射顶点(内角大于 \(\pi\) 的顶点,见 6.2.4 节)上,从两条相邻边各向外延伸一条射线。得到的分解在最坏情况下有 \(O(n^2r)\) 个单元,\(n\) 是构成 \(\partial X\) 的边数,\(r\) 是反射顶点数(\(r\lt n\))。
拿到测量后,需要计算边或距离测量完全吻合的那个(或那些)单元,以确定 \(H(y)\)(从中能得到当前距离测量的那些 \(X\) 中的点)。[74] 给出了一个基于可见性骨架 visibility skeleton 的算法,用 \(O(m+\lg n+s)\) 时间和 \(O(n^5)\) 空间完成这些计算,其中 \(n\) 是 \(\partial X\) 的顶点数,\(m\) 是 \(V(x)\) 的顶点数,\(s=|H(y)|\) 是非确定 I-state 的大小。这个方法假设环境经过预处理,以便执行时快速查询;不预处理的话,\(H(y)\) 可以在 \(O(mn)\) 时间内算出。
若有多个状态与可见性传感器的距离数据吻合怎么办?[74] 的方法只算出 \(H(y)\subseteq X\),所以必须规划一些机器人运动来进一步减小不确定性——这又一次展示了 I-空间的威力:尽管状态空间是连续的,这里却用一个 I-state 在有限个可能性之间消除歧义。下面的例子取自 [50]。
例 12.3(基于可见性的定位):考虑图 12.7 的环境,初始状态如图。根据可见性传感器的观测,初始状态可能是图 12.8 所示四种可能中的任意一个,于是 \(H(y_1)\) 包含四个状态,\(y_1\) 是初始传感器观测。设执行图 12.9 所示的运动序列。第一步之后,机器人的位置缩小到两种可能(图 12.10)——因为剩下两种可能的走廊更长。第二步之后状态就完全确定了,因为检测到了那条短的侧向走廊。
一般地,定位问题可以用可见性单元分解(图 12.4)来解。初始时,\(X_1(\eta_1)=H(y_1)\) 由初始可见多边形算出,可以用可见性骨架高效完成 [74]。设 \(X_1(\eta_1)\) 包含 \(k\) 个状态,就把地图的 \(k\) 份平移副本叠在一起,使所有可能状态重合。然后执行一个减小不确定性的运动——例如穿过叠图里只对应部分(而非全部)副本的单元边界。这样下一个 I-state \(X_2(\eta_2)\) 就能排除一些可能状态。再用一次叠图,得到另一个消歧运动,产生 \(X_3(\eta_3)\),如此直到状态已知。[50] 给出了一个运动计划,使机器人走过的距离不超过「验证给定状态所需的最优距离」的 \(k\) 倍。这个定位问题看完例 12.3 也许不显得太难,但事实上,若允许任意简单多边形,用最优运动定位是 NP-难 的。[50] 证明了这一点:每棵抽象决策树都能实现为一个定位问题,而抽象决策树问题已知是 NP-难的。
- 例 12.3 风格的环境(我们按图 12.7 的意思自己搭的,补充):一开始 4 个候选,正好是四根竖走廊顶上的四面「小旗」。点「按书中路线走下一段」:走到走廊顶上往下看,走廊长短不同,剩 2 个;再往下走到侧向走廊的高度,看到侧向走廊一长一短,只剩 1 个。
- 在只剩 2 个候选时打开「叠图」:橙色虚线是把另一份地图平移到使候选与真实位置重合的样子。哪里的虚线与实线不重合,走过去就能消除歧义。
- 切到「图 12.4 风格多边形」并打开「可见性单元分解」:同色的区域里 \(V(x)\) 由同一组边构成;一般的多边形里 \(H(y)\) 往往只有一个点。
通过改变传感模型,可以构造出连续空间里许多有趣的定位问题变形。例如机器人只能测到某个上限内的距离,超出上限的点都看不见——这对应红外、声呐、激光测距仪等许多现实的传感系统,可能大大扩大 \(H(y)\)。设机器人只能在有限几个方向上测距(图 11.14b),是另一个有趣的变形;去掉指南针,又会引入 12.2.1 节那样的朝向混淆。甚至可以考虑感知极少或完全没有感知的有趣定位问题 [133, 134],得到的 I-空间与图 11.28 托盘倾斜例子的类似。
12.2.3 概率定位方法 Probabilistic Methods for Localization
到目前为止的定位问题只涉及非确定不确定性,而且假设自然不干扰状态转移方程和传感器映射。若自然介入传感器映射,未来的 I-state 就不可预测;对主动定位问题,这意味着定位计划必须使用信息反馈——动作要以 I-state 为条件,在得到新观测之后再做适当的决定。被动定位问题则是从感知与动作历史计算概率 I-state。同时含自然与非确定不确定性的定位问题留给读者,这里只讲概率情形。
离散问题
先给 12.2.1 节的离散网格问题加上概率。状态仍写成 \(x=(p,d)\),初始条件是 \(X\) 上的概率分布 \(P(x_1)\);一个合理的选择是均匀分布,每个方向和位置等可能。机器人仍有四个动作,但现在假设自然会干扰状态转移:例如 \(u_k=F\) 时机器人大概率向前走,但也可能以小概率向右、向左移动,甚至即使没被挡也根本没动。12.2.1 节的传感器映射指示机器人有没有动;现在自然也可以干扰这个测量:可能以小概率错误地报告「动了」而实际没动,或反过来。由于传感器依赖前后两个状态,映射写成
给定概率模型 \(P(\psi_k)\),它可以写成 \(P(y_k|x_k,x_{k-1})\)。
要解被动定位问题,就用 11.2.3 节计算导出 I-state 的式子。若传感器映射只用当前状态,(11.36)、(11.38)、(11.39) 不用修改即可使用;但 \(h\) 同时依赖 \(x_k\) 与 \(x_{k-1}\),所以要做些修改。回忆这个传感器的观测从 \(y_2\) 开始,于是 \(P(x_1|\eta_1)=P(x_1|y_1)=P(x_1)\),而不是用 (11.36)。每一阶段之后,先用 (11.38) 考虑动作 \(u_k\),由 \(P(x_k|\eta_k)\) 计算 \(P(x_{k+1}|\eta_{k+1})\)。(11.39) 考虑传感器观测 \(y_{k+1}\),但 \(P(y_{k+1}|x_{k+1},\eta_k,u_k)\) 没有直接给出,因为传感器映射还依赖前一个状态3。用边缘化把它化简为
和式里的第一个因子可以化成传感器模型
因为观测只依赖 \(x_{k-1}\)、\(x_k\) 和自然感知动作 \(\psi_k\)。(12.20) 的第二项用贝叶斯规则计算:
其中 \(P(x_k|\eta_{k-1},u_{k-1},x_{k-1})\) 化简为 \(P(x_k|u_{k-1},x_{k-1})\)——它直接来自状态转移概率 \(P(x_{k+1}|x_k,u_k)\)(把阶段下标前移一位);\(P(x_{k-1}|\eta_{k-1},u_{k-1})\) 就是上一阶段的概率 I-state(动作 \(u_{k-1}\) 不影响 \(x_{k-1}\))。这就完成了概率 I-state 的计算,解决了被动定位问题。把这几步合起来,其实就是 \(P(x_k|\eta_k)\propto\sum_{x_{k-1}}P(x_{k-1}|\eta_{k-1})P(x_k|x_{k-1},u_{k-1})P(y_k|x_{k-1},x_k)\);参考代码第 7 项验证了按 (12.20)–(12.22) 递推得到的结果与穷举全部状态序列逐项相等。
解主动定位问题难得多,因为搜索发生在 \(\mathcal{I}_{prob}\) 上。离散定位问题的那些选择在这里都还在。在整个 I-空间 \(\mathcal{I}_{prob}\) 上计算信息反馈计划理论上可行,但对大多数环境不实用。12.2.1 节「逐步生长有向图」的搜索思路也能用,方法成功与否取决于为这个特定问题开发的巧妙搜索启发式。
- 点「复现参考代码」:图 12.2a、\(p_{ok}=0.7\)、\(e_s=0.1\)、动作 \((F,L,F,R)\)、观测 \((1,1,0,1)\);概率最大的三个状态是 \(1^{\leftarrow}\)(0.1809)、\(4^{\uparrow}\)(0.1462)、\(3^{\downarrow}\)(0.1331),与参考代码第 7 项逐项一致。
- 点「例 12.1」,再依次点 \(\eta_2,\ldots,\eta_5\):没有噪声时,概率 I-state 恰好是 (12.15)–(12.18) 的非确定 I-state 上的均匀分布。再把 \(p_{ok}\) 拉到 0.9:同一串观测下,原来概率为 0 的状态也有了概率。
- 勾选「叠加支撑集」,在「办公室(补充)」地图上随机走几步:支撑集往往始终是全部状态,非确定 I-state 什么也没学到;概率 I-state 的熵却在下降。换到环形地图、去掉噪声反复前进:概率始终平分在对称的几个状态上(例 12.2)。
连续问题
近年来,用概率模型在连续空间里定位受到了大量关注 [37, 78, 109, 155, 166, 187]。由于传感器数据有噪声、建模有误差、还要求长时间稳健运行,移动机器人往往很难定位。概率建模与概率 I-state 的计算在许多实验系统中相当成功,室内室外都有。图 12.11 展示了只用声呐成功定位的例子。这方面的绝大多数工作研究被动定位,因为机器人通常在完成别的任务(例如到达环境的某个部分),所以重点主要是计算概率 I-state,而不是在 \(\mathcal{I}_{prob}\) 上做困难的搜索。
连续空间里的概率定位最常要定义两个概率密度:\(p(x_{k+1}|x_k,u_k)\) 与 \(p(y_k|x_k)\)(状态传感器映射的情形)。若各阶段代表等间隔的时刻,这两个密度通常在每个阶段都不变。状态空间通常是 \(X=SE(2)\),以同时考虑平移和转动;只考虑平移时也可以是 \(X=\mathbb{R}^2\)。密度 \(p(x_{k+1}|x_k,u_k)\) 描述了在一段固定时间内控制移动机器人时出现的不可预测性;[199] 给出了一种通过随机微分方程为非完整机器人估计这个分布的方法。
密度 \(p(y_k|x_k)\) 表示给定状态时各种测量的相对似然。它最常用来建模由激光测距仪、声呐阵列甚至红外传感器得到的距离测量。设机器人在二维环境里移动,并在多个朝向上测深度:在机器人机体坐标系里有 \(n\) 个角度要测深度。理想情况下测量看起来就像图 11.15b,但实际数据含有大量噪声。观测 \(y\in Y\) 是一个 \(n\) 维的带噪声深度测量向量。定义 \(p(y|x)\) 的一种常用方法是假设每个距离测量的误差服从高斯密度:给定 \(x\) 时测量的均值很容易算成真实距离,方差则应由传感器的实验评估确定。若再假设测量向量是一组独立同分布的随机变量,\(p(y|x)\) 就是高斯密度的简单乘积。
模型表述好之后,概率 I-state 的计算直接来自 11.2.3 与 11.4.1 节:初始条件是 \(X\) 上的概率密度函数 \(p(x_1)\);然后用边缘化和贝叶斯更新规则,对每个阶段 \(k\) 构造一列形如 \(p(x_k|\eta_k)\) 的密度函数。在某些有限的应用里,表达 \(p(x_{k+1}|x_k,u_k)\) 与 \(p(y_k|x_k)\) 的模型可能是线性高斯的,这时可以直接用 11.6.1 节的卡尔曼滤波。大多数情况下密度不是这种形式,可以用 11.4.3 节讨论的基于矩的近似:若用到二阶矩,就得到所谓扩展卡尔曼滤波 extended Kalman filter——把卡尔曼滤波的更新规则用到原问题的线性高斯近似上。近年来实验移动机器人学里最被广泛接受的方法之一,是用基于采样的技术直接计算和估计概率 I-state:11.6.2 节一般性介绍过的粒子滤波 particle filtering 方法用于定位时实验效果很好,在这种情境下常称为蒙特卡洛定位 Monte Carlo localization。
- 点「自动行驶」看前几步:粒子先铺满地图(图 12.11a),再聚成好几簇(图 12.11b、c),机器人在走廊里走一段、进出房间后只剩一簇(图 12.11d)。地图、行驶控制与运动噪声的形式都是补充的。
- 把光束数调到 4 再「重置粒子」:多峰保持更久,有时收敛到错的房间。关掉「自适应退火」(补充:粒子太少能解释观测时暂时用 \(p(y|x)^\beta,\ \beta<1\);定位后 \(\beta=1\),就是普通的贝叶斯更新)再重置:第一步有效粒子数就掉到 1,所有粒子被复制到同一个错误位姿。
- 收敛后点「绑架机器人」:粒子不会自己恢复——这正是绑架机器人问题;勾上「注入随机粒子」(补充,类似 Augmented MCL)后,几十步内重新找到机器人。
12.3 环境不确定与建图 Environment Uncertainty and Mapping
读完 12.2 节,你也许已经在想:如果没有地图会怎样?这引出一组对机器人学至关重要的迷人问题。若状态只表示位形,I-空间让我们不必知道精确位形就能完成任务;若状态也表示环境,I-空间就让我们连环境的完整表示都不用就能完成任务!这非常强大:给机器人的环境建立表示代价高昂、容易出错,而且很快就会过时。
12.3.1 网格问题 Grid Problems
为了把问题看清楚,还是先看离散问题——这是 12.2.1 节的延续。那里状态表示位置 \(p\) 和方向 \(d\);现在状态写成 \((p,d,e)\),\(e\) 表示机器人所在的具体环境。这需要定义一个环境空间——它很少被显式表示出来,通常表达为对可能环境类型的约束,例如「所有连通的二维网格规划问题」;简单连通的网格问题又是更强的约束。
马上出现一个问题:两张环境地图什么时候算等价?回忆图 12.2a 和 12.3b:图 12.3b 每转 90° 看起来都一样,图 12.2a 转了就不一样。即使看起来不一样,它也应该是同一个环境,对吧?想象给一个没有指南针、不知道北极方向的偏远小岛画地图:地图的朝向(哪边朝上?)可以任意选择而无害。若环境地图是在 \(\mathbb{R}^2\) 上「画」出来的,两张地图只要能用 \(SE(2)\) 中的一个变换(平移加转动)完全叠合,似乎就应当等价。定义环境空间时,必须明确两个环境等价意味着什么:例如若要求通过探索建立地图,是否还要求给出精确的平移与转动?这可能需要也可能不需要,但必须在问题描述里说清楚。所以我们允许任何可能:两张地图只差一个 \(SE(2)\) 变换时,根据应用,可以定义它们等价,也可以不。
为了考虑一些例子,定义有限或无限的环境集合会很方便。再次考虑二维网格上的规划:本节假设每个网格点 \(p\) 有 2.1 节那样的整数坐标 \((i,j)\in\mathbb{Z}\times\mathbb{Z}\)。记 \(E\) 为环境集合,\(D\) 为机器人可能朝向的四个方向。状态空间是
一般假设环境 \(e\in E\) 由 \(\mathbb{Z}\times\mathbb{Z}\) 的一个子集给出,表示所有能放机器人的白格;其它格都是黑格(障碍)。若允许 \(\mathbb{Z}\times\mathbb{Z}\) 的任何子集,\(E=\mathrm{pow}(\mathbb{Z}\times\mathbb{Z})\),这就包括了许多没用的地图,比如铺满整个平面的棋盘。这促使我们对 \(E\) 加一些限制,例如限定为这样的地图:原点 \((0,0)\) 是白格,其余白格都能从它到达,并且都在一个有界区域内。
例子马上就来,先想想能表述出哪些问题:
- 建图 map building:访问每个可达的格子并构造地图。取决于 \(E\) 的定义,这可能是确定 \(E\) 中的某一个环境,或一组与探索相容的环境。这也叫同时定位与建图 simultaneous localization and mapping(SLAM),因为构造完整地图通常意味着最终也知道了机器人的位置与朝向 [81, 191]。于是 (12.23) 的完整状态 \(x\in X\) 由建图过程确定。对这里的网格问题这一点是平凡的;对连续环境中的概率不确定性情形就难得多了(12.3.5 节)。
- 判定环境 determining the environment:想象机器人被随机放进一栋楼里再开机,它被告知自己在固定个数(比如 10 栋)楼中的某一栋里,必须判断是哪一栋。可能环境的个数增加时,这个问题看起来越来越像建图;事实上,建图可以看作「对可能环境几乎不加约束」的特例。
- 导航 navigation:机器人没有地图,却要到达一个目标位置。目标相对于机器人的位置可以由传感器给出。允许机器人不完全探索环境就解决问题,所以解决任务之后的非确定 I-state 可能包含大量可能的环境——解决问题只需要环境的一部分。
- 搜索 searching:目标状态只有在到达时(或被一个短程传感器检测到时)才能识别,没有别的传感器帮忙。环境必须被系统地探索,但找到目标就可以提前结束;地图不一定要建出来。搜索可以推广到 12.4 节的追逃。
下面给出判定环境和导航的简单例子。
例 12.4(判定环境):机器人被告知自己被放进了图 12.12 的某个环境里。设它的初始位置是 \((0,0)\)(图中的白圈)、初始方向朝东、环境是 \(e_3\)——这些机器人都不知道。动作和状态转移模型同 12.2.1 节。当前状态空间包含环境,但环境从不改变;改变的只是「在哪个环境里」的信息。传感模型同样只指示机器人在上一个动作之后是否改变了位置。初始条件是 \(X\):任何位置、朝向、环境都可能。设 \((u_1,u_2,u_3)=(F,R,R)\),传感器观测 \((y_2,y_3,y_4)\) 报告机器人一直没有改变位置。朝向变成了西,但机器人不知道(它确实知道自己现在朝着与初始朝向相反的方向)。能推出什么?机器人发现自己在一个三面被障碍包围的格子里,这意味着排除了 \(e_1\) 和 \(e_6\)。在剩下的四个环境里,机器人推断自己一定在某个端头格上:1) \(e_2\) 的左上,2) \(e_2\) 的右上,3) \(e_3\) 的下端,4) \(e_3\) 的最右端,5) \(e_4\) 的上端,6) \(e_5\) 的左下,7) \(e_5\) 的左上。它还能对朝向做出很强的推断——它甚至知道 \(u_4=R\) 一定会让它移动,因为四个方向不可能都被挡住。
施加 \((u_4,u_5)=(R,F)\):机器人应该移动两次,到达 \(e_3\) 的左上角、朝北。这时 \(e_2\)、\(e_3\)、\(e_4\)、\(e_5\) 都还可能;但它现在知道第 4 阶段的位置不可能是 \(e_5\) 的左上。若在 \(e_3\) 里,它知道自己一定在左上,但仍不知道朝向(可能朝北或朝西);它也可能在 \(e_2\) 的左下或右下。再令 \((u_6,u_7)=(R,F)\),机器人移动两次:此时排除了 \(e_4\) 和 \(e_5\),可能的环境集合是 \(\{e_2,e_3\}\)(\(e_2\) 里的一个朝向也被排除了)。若施加 \(u_8=R\),传感器观测 \(y_9\) 报告机器人没有动,这就排除了 \(e_2\)。最后机器人能推断出:它在 \(e_3\) 的右上角、朝南;还能推断出它的初始状态是 \(e_3\) 左下角、朝东。所有不确定性都通过构造非确定 I-state 消除了。
现在把图 12.13 的环境加入集合,重新开始。\(e_7\) 与 \(e_1\) 完全相同,只是原点挪了位置;\(e_8\) 与 \(e_2\) 相同,只是转了 180°。这两种情形下不存在能让机器人区分 \(e_1\) 与 \(e_7\)、或 \(e_2\) 与 \(e_8\) 的输入。合理的做法是宣布这两对环境两两等价:唯一的区别只在地图是怎么画的。若机器人执行前面给出的同样的动作序列,它也区分不了 \(e_3\) 和 \(e_9\):机器人不可能推断出某处有没有一个到不了的白格。一般的环境空间可能包含这类变化,使机器人无法知道精确的环境;但这通常不会给解决规划问题带来额外困难,所以宣布 \(e_3\) 与 \(e_9\) 等价可能是合理的。任务不必知道精确环境就能完成,这一点非常重要:某种意义上,环境是在「足以解决问题」的分辨率上被观察的,更多的细节无关紧要。机器人能忽略不必要的细节,往往就能造出更便宜、更可靠的系统。
例 12.5(到达目标状态):仍用图 12.12 的环境集合。这次假设位置 \(p=(0,0)\) 和朝向东是已知的;环境是 \(e_4\),但机器人不知道。任务是到达位置 \((2,0)\),即向东走两格。计划 \((u_1,u_2)=(F,F)\) 不必获得多少关于环境的信息就达成了目标。施加 \(u_1=F\) 之后,知道环境不是 \(e_3\);此后不再收集环境的信息,因为与解决问题无关。若目标是 \((2,2)\),就会获得更多环境信息;例如若计划 \((F,L,R,L)\) 到达了那里,就知道环境是 \(e_6\)。
- 点「例 12.4」逐步走:三次「没动」后 \(e_1\)、\(e_6\) 变暗,橙色短线正好落在书中列出的 7 个端头格上;第 8 步后只剩 \(e_3\) 右上角朝南。
- 点「例 12.4 + e7–e9」重做同一序列:最后剩 \(e_3\) 与 \(e_9\) 两个——那个到不了的白格永远看不出来。中间几步里 \(e_1\) 和 \(e_7\) 总是同时被排除或保留。
- 点「习题 5」:题目没说真实环境是哪一个(参考代码第 8c 项列出了五种情形的观测序列各不相同)。点地图换真实环境,看观测和 I-state 怎么变。
判定环境的算法
要判定环境(包括建图问题),到达并记住所有格子就够了。若机器人必须从一小组可能中判定环境,就可以预先计算一个最优最坏情况计划:可以在 \(\vec X=\mathcal{I}_{ndet}\) 上用值迭代或 10.2.3 节 Dijkstra 算法的非确定版本来计算。机器人被放进环境时,执行这个最优计划来推断位置、朝向和环境。若可能环境的集合太大(甚至无限),懒惰方法最合适——包括建图问题,那里对环境可能几乎没有假设。建图问题的懒惰方法只需保证访问到每个格子;另一个关心的问题可能是尽量减少 12.2.1 节说过的改道路径。一个既能解决问题、又能避免过多改道的简单算法是 2.2.2 节的深度优先搜索。
导航的算法
导航任务是在没有环境地图的情况下到达指定目标。假设目标用相对机器人初始位置和朝向的坐标(里程坐标)表达。若只有在机器人站上目标格时才能认出目标,就需要搜索,接下来讨论。如例 12.5 所示,解决导航问题不需要学到整个环境。可以用 2.2 节的搜索算法,例如 \(A^*\) 能找到到目标的最优路线,一个合理的 cost-to-go 低估启发式可以假设所有格子都是空的。这样虽然可行,但没有计入改道代价:除非之后有别的机器人用这些信息到达同一个环境里的同一个目标,否则 \(A^*\) 最终算出的最优路径可能毫无意义。对先走的那个倒霉机器人来说,可能浪费了大量探索步数,因为 \(A^*\) 不是为执行中的探索设计的。2.2 节的搜索算法虽然假设搜索图在执行中逐步显露、而不是事先给定,却允许搜索中的当前状态任意跳来跳去——在当前情境里,这就相当于把机器人瞬移到环境的不同地方。12.3.2 节介绍的导航算法扩展了 Dijkstra 算法,使它在执行中才发现代价的情况下也能正确工作;它可以很好地用于本节的网格导航问题,即使环境起初未知。
迷宫搜索的算法
用 I-map 大幅压缩 I-空间的一个迷人例子,很早以前就由 Blum 和 Kozen 给出了 [14]。建图需要的空间与格子数成线性;但其实可以用少得多的空间保证系统地搜索完环境。对二维网格环境,搜索问题不必维护完整的地图就能解决:必须系统地访问每个格子,但并不意味着必须记住访问过的所有地方,只要保证机器人在走遍所有格子之前不会陷入无限循环就行。[14] 证明了任何迷宫都可以只用格子数的对数那么大的空间来搜索。这意味着许多不同的环境在机器里有相同的表示——本质上,构造出的 I-map 把 \(\mathcal{I}_{ndet}\) 剧烈地坍缩成一个更小的导出 I-空间。
假设机器人运动模型同本节前面一样,但起初没有环境地图。机器人一开始朝向哪里,都可以无害地宣布为北。假设任何平面二维网格都可能,于是对四个朝向各有一张相同的地图;其中某张地图的北可能因为任意宣布初始方向为北而标错,但这对接下来的方法并不关键。假设机器人是一个有限自动机,外加一个二进制计数器——计数器是必需的,因为它能存任意大的值,单靠自动机做不到。
为了不让机器人永远原地绕圈,需要维护两条重要的信息:
- 纬度 latitude:从机器人初始位置向北的格数。
- 执行一条闭路时,需要知道它的方向 orientation:这条闭路是顺时针还是逆时针。
两者都能从历史 I-state 算出,历史 I-state 的形式同 (12.12),只是现在 \(X\) 由 (12.23) 给出,\(E\) 是所有有界环境的集合(有界指白格能被包含在一个大矩形里)。从历史 I-state 中,记 \(\tilde u'_k\) 为动作历史里产生了运动的那些动作组成的子序列。纬度 \(l(\tilde u'_k)\) 可以这样算:数产生向北运动的动作数,减去产生向南运动的动作数。闭路的方向可以用角度里程计确定(在这个问题里它等价于有一个指南针 [46])。记 \(r(\tilde u'_k)\) 为 \(\tilde u'_k\) 中右转的次数减去左转的次数。注意四次右转得到一条顺时针闭路,\(r(\tilde u'_k)=4\);四次左转得到逆时针闭路,\(r(\tilde u'_k)=-4\)。一般地可以证明:对任何不自交的闭路,要么 \(r(\tilde u'_k)=4\)(顺时针),要么 \(r(\tilde u'_k)=-4\)(逆时针)。
前面说需要一个有限自动机和一个二进制计数器。计数器用来在机器人移动时跟踪 \(l(\tilde u'_k)\)。事实上测量角度里程计不需要另一个计数器,机器人可以在数左右转时做模 3 运算:形成一条闭路后若 \(r\equiv1 \pmod 3\),机器人是顺时针走的;若 \(r\equiv2\pmod 3\),是逆时针走的5。这避免了使用无界多个比特(与维护纬度的情形相反)。(补充:模 3 是最小可用的模数——\(4-(-4)=8\),模 2 和模 4 都分不开 \(\pm4\)。)到此为止的构造可以看作把历史 I-state 映射到一个小得多的导出 I-空间的 I-map 的一部分。
计划用图 12.14 的例子来描述。任何环境内部都有障碍(这个例子有六个),还有一条外边界。利用纬度和朝向信息,可以在每个障碍和外边界上确定一个唯一点 unique point:定义为障碍的最南那些顶点中最西的那个(图 12.15 中的小圆点)。利用纬度和朝向信息,总能找到唯一点(习题 4)。
为了解决问题,机器人走到一条边界上,用沿墙走 wall following 绕着它走:机器人可以用感知信息,以「墙在它左手边」的方式移动。假设机器人总能检测到边界上的唯一点,就可以想象障碍是按图 12.15 那样连起来的:从每个唯一点向南延伸出一条虚构的细障碍,它把障碍连在一起,看起来就像外边界的延伸。换句话说,想象障碍都是从墙上凸出来的,而不是「漂浮」在内部。只要拒绝穿过这些虚构的障碍,机器人就能沿一条单一闭路绕过所有障碍的边界。到此为止的策略还不能保证访问每个格子,所以需要图 12.16 那样的修改:用之字形运动保证访问每个格子。比较一下 7.6 节的生成树覆盖规划很有意思:那里假设给定完整地图,目标是优化走过的距离。
若环境里有某个机器人到达时能检测到的特殊物体,上面的策略总能保证找到它——即使到最后机器人连地图都没有!得到的方法可以看作 I-空间上的一个信息反馈计划。在这个意义上,Blum 和 Kozen 是找到「能解决任何问题的计划」的那位「规划者」:因为这个计划不加修改就能处理所有可能的环境,所以不必根据问题数据计算别的计划。这就是直接在环境集合的 I-空间上工作、而不是要求做状态估计的威力。
- 点「运行」:机器人先往西走到墙,然后墙在左手边绕外墙走——因为虚拟细墙把六个障碍都接到了外墙上,它一圈就绕过了所有障碍。闭合时 \(r=+4\),\(r \bmod 3 = 1\),判定为顺时针(与原书的说法相反,见脚注)。
- 取消「虚拟细墙」,点一个紧挨某个内部障碍的白格作起点:机器人会绕着那个障碍逆时针转,\(r=-4\equiv2\);没有虚拟细墙时它永远到不了别处——这就是要识别唯一点的原因。
- 勾上「覆盖所有格子」:这里用一棵「尽量竖着连」的生成树代替书中图 12.16b 的之字形规则(补充;原论文 [14] 的局部规则只用对数空间)。沿墙走就走遍了整棵树,访问了全部格子。
12.3.2 Stentz 算法(D*) Stentz's Algorithm (D*)
想象用机器人车辆探索一个未知的星球:车辆在崎岖的地形上行驶,用测距仪精确测量附近的地面。行驶中它可能发现某些部分比原来以为的容易通过;另一些情况下又可能发现原本打算走的某个方向因为一块大石头或一道沟壑而无法通过。若目标是到达指定坐标,这就可以看作一个未知环境中的导航问题,得到的解是 12.2.1 节讨论的懒惰方法。
本节介绍 Stentz 算法 [174],它已用于许多户外车辆导航应用,比如图 12.17 的车辆(装有激光雷达等传感器、用 Stentz 算法导航的越野无人车 XUV)。这个算法可以看作 Dijkstra 算法反向版本的动态版:它维护 cost-to-go 的值,搜索从目标向外生长(而 2.3.3 节的 Dijkstra 维护的是从 \(x_I\) 出发的 cost-to-come)。这个方法适用于任何最优规划问题。在状态转移图的语言里,假设边的转移代价是未知的(等价地,每个代价 \(l(x,u)\) 未知);在导航问题里,正的代价表示从状态 \(x\) 走到 \(x'=f(x,u)\) 的难度。
具体地,想象星球表面被划分成高分辨率的网格。状态空间就是一个有界的格子集合,\(X\subseteq\mathbb{Z}\times\mathbb{Z}\)。每个格子有一个正实数 \(c(x)\),表示通过它的难度。每个网格点的动作 \(U(x)\) 可以用标准的网格邻居(如四邻接或八邻接)。这定义了 \(X\) 上的状态转移图:对任何 \(x'\in X\) 与 \(u'\in U(x')\),若 \(x=f(x',u')\),代价项就用 \(c\) 赋值:\(l(x',u')=c(x)\)(走进哪个格子,就付那个格子的代价)。这个模型推广了 12.3.1 节的网格:那里格子只有空或占用,这里任何正实数都允许。接下来的讨论里,代价可以比「从 \(c(x)\) 出发」更一般,状态转移图也不必从网格导出。一开始为所有 \(l(x,u)\) 任意赋一些初值,例如在星球探索应用里,可以统一假设通过平坦无障碍地面的代价。
任务是导航到某个目标状态 \(x_G\)。方法先在 \(X\) 的一个包含 \(x_I\) 与 \(x_G\) 的子集上构造一个反馈计划 \(\pi\):反复执行图 12.18 的过程,直到 \(x_I\) 的最优 cost-to-go 已知。像 Dijkstra 算法一样维护一个优先队列 \(Q\);但 Stentz 算法允许因执行中感知到的信息而修改 \(Q\) 中元素的代价。记 \(G_{best}(x)\) 为 \(x\) 留在 \(Q\) 中期间与之关联的最低 cost-to-go,\(Q\) 按 \(G_{best}\) 排序;记 \(G_{cur}(x)\) 为它当前的 cost-to-go 值——若某些代价变大,它可能比 \(G_{best}(x)\) 大。设某个 \(u\in U(x)\) 能到达状态 \(x'=f(x,u)\),记 \(G_{via}(x,x')\) 为从 \(x\) 经 \(x'\) 走的 cost-to-go:
若 \(G_{via}(x,x')\lt G_{cur}(x)\),说明 \(G_{cur}(x)\) 可以减小;若进一步有 \(G_{cur}(x')\le G_{best}(x)\),则 \(G_{cur}(x')\) 是最优的。两个条件都满足时,就把 \(G_{cur}(x)\) 更新为 \(G_{via}(x,x')\)。
图 12.18 的迭代结束后,机器人执行 \(\pi\),生成一串访问过的状态。记 \(x_k\) 为执行中的当前状态。若发现施加 \(\pi(x_k)=u_k\) 得到的代价与当前模型里的 \(l(x_k,u_k)\) 不符,就要更新代价。更一般地,机器人可能要能更新 \(x_k\) 周围、对应传感器视野的一整片区域里的代价。下面的描述假设只得到 \(x_k\) 处的一个更新(更一般的情形类似处理)。首先把代价更新为新测到的值;若 \(x_k\) 恰好已「死」(访问过但不在 \(Q\) 中),就以代价 \(G_{cur}(x_k)\) 把它重新放回 \(Q\)。然后执行图 12.18 的步骤,直到对所有 \(x\in Q\) 都有 \(G_{cur}(x_k)\le G_{best}(x)\)。之后继续执行计划,直到到达目标或发现另一处代价不符。执行中的任何时刻,机器人的运动在当前关于代价的信息下都是最优的 [174]。
(补充:与 Stentz 的原文对照,\(G_{best}\) 就是键值 \(k(x)\)、\(G_{cur}\) 就是 \(h(x)\);「把 \(x_k\) 重新放回 \(Q\)」对应原文的 MODIFY-COST——被重新插入的是代价改变了的那些边的终点。在「格子代价 \(c(x)\) 变了」的模型里,变的是所有走进 \(x\) 的边,所以重新插入的正是 \(x\) 自己。书中第 6 步的条件「\(G_{cur}(x)>G_{best}(x)\)」正是原文进入这一分支(RAISE 状态)的条件;原文另写的 \(h(x')>k_{old}\) 在第 2 步执行完之后会自动成立,所以两种写法等价。参考代码第 10 项在 24 组随机地形上逐次核对:每次重规划后 \(G_{cur}(x_k)\) 与沿 \(\pi\) 走到目标的代价都等于在当前已知代价上重新做 Dijkstra 的结果。)
图 12.19 演示了算法的执行:图 12.19a 是一个用随机分形生成的人造地形,越暗代价越高;中心的高代价地形像一道屏障,向下有一条逃生路线。初始状态在环境左边缘的中点,目标状态在右边缘。机器人一开始规划一条直线路径,然后在移动的每一步增量地更新路径。图 12.19b 里机器人遇到了高代价的中心区,开始找绕行的路;最后到达目标(图 12.19c)。实际执行的路径其实是一串最优路径,每条都基于施加单个动作时已知的信息。
- 点「运行」(地形是补充的多倍频噪声加一个开口向左、底部有缺口的杯形屏障,仿图 12.19a):机器人以为处处代价为 1,钻进杯形屏障,撞到墙后从下方缺口逃出。勾「显示真实地形」对比全知最优路径(细虚线)——执行的路径是「一串当时最优的路径」。
- 对比「D* 展开」与「每次从头反向 Dijkstra」两列:后者通常多十几倍。鼠标悬停在红点上看 RAISE 状态(\(G_{best}\lt G_{cur}\))。勾上「核对」:每次重规划后 \(h(x_k)\) 都等于在已知代价上新做的 Dijkstra(全是 ✓)。
- 把感知半径从 1 调到 6、或切换 4 / 8 邻接:看得更远不一定让执行代价更低——每一步都只是「当前信息下」最优。
用 I-空间来解释
下面给出另一种表述,帮助理解它与「环境集合的 I-空间」的联系。前面定义的状态空间也可以改称为位形空间 \(\mathcal{C}=\mathbb{Z}\times\mathbb{Z}\),记 \(q\in\mathcal{C}\) 为位形。设每个可能的环境对应位形转移图中所有边的一种代价赋值,那么这个问题所有可能环境的集合 \(E\) 似乎就是所有可能的代价赋值 \(l(q,u)\)。状态空间现在可以定义为 \(\mathcal{C}\times E\),对每个状态 \(x=(q,e)\in X\),位形和完整的代价集合都确定了。起初猜测机器人处于某个特定的 \(e\in E\);若发现代价不符,就意味着现在要假设一个不同的环境模型,因为某个转移代价与预期不同。代价其实应写成 \(l(x,u)=l(q,e,u)\),表明代价依赖于所假设的特定环境。
非确定 I-state 对应一组可能的代价赋值以及相应的位形。由于方法要求为还没观测到的代价赋值,它就猜测非确定 I-state 中的某一个特定环境是正确的。随着发现代价不符,原来的猜测已经落在更新后的非确定 I-state 之外,于是要改变猜测以纳入新的代价信息。在这个过程中非确定 I-state 持续缩小。但要注意,最后机器人可能在猜错精确的 \(e\in E\) 的情况下解决了问题:有些格子从未访问过,它们真实的代价因而未知;为了解决问题,对它们的代价做了默认假设,但真实的 \(e\) 只有访问所有格子才能知道。可以确定的只是:最后假设的默认值落在最终的非确定 I-state 之内。
12.3.3 未知连续环境中的规划 Planning in Unknown Continuous Environments
现在从离散环境转到连续环境,但仍用非确定不确定性。首先介绍几个 Bug 算法 bug algorithms [88, 115, 89],它们代表一族解决规划问题的运动计划,用到的想法在许多方面与 12.3.1 节的迷宫探索有关。除了 Bug 算法,还简要介绍竞争比的概念。
Bug 算法使用的模型如下:一个点机器人被放进一个未知的二维环境,里面可能有任意有限个有界障碍。假设每个障碍的边界和外边界(若存在)是分段解析的(这里「解析」意味着每一段光滑,且曲率只变号有限次)。于是障碍可以是多边形、光滑曲线,或曲线与直线的任意组合。可能环境的集合 \(E\) 庞大无比,但我们会避免显式构造它。机器人位形由位置和朝向刻画。主要有两个传感器注:
- 目标传感器 goal sensor:指示到目标的当前欧氏距离,以及相对于一个绝对「北」的目标方向。
- 局部可见性传感器 local visibility sensor:给出机器人周围很小距离内边界的精确形状。机器人必须与边界接触或几乎接触才能看到一部分边界,否则这个传感器不提供有用信息。
注:这只是一种可能的传感模型;别的传感器组合也行,只要能让接下来的运动策略执行所需的运动与决策(书中脚注 2)。
目标传感器本质上用极坐标(以目标为原点)编码了机器人的位置,因此机器人访问过的任何位置都能赋予唯一的 \((x,y)\) 坐标。这使它能增量地描出已经走过的障碍边界。局部可见性传感器提供的信息刚好够做沿墙走的运动;传感范围很短,机器人没法从中了解更多环境结构。下面考虑几种策略,每一种都可以看作非确定 I-空间上的一个信息反馈计划。
Bug1 策略
[115] 提出了一种叫 Bug1 的策略,见图 12.20:
- 朝目标走,直到遇到障碍或目标。到达目标就停。
- 左转,沿接触到的障碍走完整个周长。走完一圈后,回到离目标最近的那个点,然后回到第 1 步。
判断是否走完了整个周长似乎需要一块卵石或标记;其实只要找到目标传感器读数重复的那个点就能推断出来。最坏情况在概念上很容易理解:机器人走过的总距离不超过
其中 \(d\) 是从初始位置到目标位置的欧氏距离,\(p_i\) 是第 \(i\) 个障碍的周长,\(M\) 是障碍个数。也就是说每个障碍的边界最多被走 \(3/2\) 次。图 12.21 是每个障碍都被走了 \(3/2\) 次的例子。这个界依赖于「机器人总能回忆起沿边界到它需要离开的那个点的最短路径」——这是合理的,因为机器人可以从目标传感器推断出沿边界走过的距离。如果做不到,\(3/2\) 就要换成 2,因为最坏情况下机器人可能几乎走完边界两次。
Bug2 策略
Bug1 的另一种选择是 Bug2 策略(图 12.22):机器人总是试图沿着连接初始位置与目标位置的那条线段移动。机器人在这条线上时,目标方向要么与从初始状态看的方向相同,要么相差 \(\pi\)(机器人在目标的另一侧时)。第一步同 Bug1。第二步里,机器人只沿周长走到到达这条线、并且能朝目标方向移动为止,然后回到第 1 步。照这样表述可能出现无限循环,所以需要一个小修改:机器人记住它上一次离开边界时到目标的距离,只有当候选的离开点比那更近时才再次离开边界。反复执行,直到到达目标或判定不可能到达。Bug2 走过的总距离不超过
其中 \(n_i\) 是第 \(i\) 个障碍与「初始位置—目标位置」线段相交的次数。图 12.23 演示了相交带来的麻烦。
- 「图 12.21」场景选 Bug1:每个菱形恰好走 1.50 圈,实际距离贴近界 (12.25);换 Bug2,每个只走半圈。四个场景都是我们按书中插图的意思画的(补充)。
- 「图 12.23」场景选 Bug2:线段与障碍相交 12 次(\(n_1=12\)),机器人碰撞 4 次、沿边界走了 1.75 圈,比 Bug1 还长,但仍远低于 (12.26)。打开「深度不连续点」叠加,看图 12.25 那种距离传感器给出的候选方向。
- 「不可达」场景:Bug1 绕一圈半后,在离目标最近的点发现目标方向指向障碍内部;Bug2 绕回碰撞点 \(H_1\)。两者都在有限步内正确报告失败。把 \(x_G\) 拖出环外再看。(Bug2 的离开规则按 Lumelsky 原文:离开点必须比这一次的碰撞点更靠近目标。)
利用距离数据
VisBug [114] 和 TangentBug [89, 100] 策略加入了距离或可见性传感器的测量来提高效率。这里介绍 TangentBug,见图 12.247。设机器人除了前面的传感器,还有一个给出图 12.25 那样测量的传感器:相对距离传感器的候选运动,是深度图中不连续的那些方向;机器人到小圆点的距离用来选择运动。策略如下:
- 朝目标走——穿过空间内部或沿墙走——直到意识到机器人陷入局部极小,或到达目标。这类似 5.4.3 节势场规划器的梯度下降运动。到达目标就停,否则进入下一步。
- 沿边界运动。首先比较之前的前进方向与目标方向来选一个方向。沿边界移动时跟踪两个距离:\(d_f\) 与 \(d_r\)。\(d_f\) 是沿边界走时观测到的到目标的最小距离;\(d_r\) 是从当前位置到目标的最短路径长度,假设唯一的障碍是距离传感器看得见的那些。若 \(d_r\lt d_f\),机器人就停止沿边界走,回到第 1 步。若机器人绕整个障碍一圈都没出现这个条件,算法就报告目标不可达。
给距离传感器设一个深度上限,就得到 TangentBug 算法的一个单参数族。最大深度减小时,机器人变得短视,性能下降。[89] 证明了走过的距离不超过
其中 \(m_i\) 是第 \(i\) 个障碍的局部极小个数,\(d\) 是到目标的初始距离。界取在 \(M\) 个障碍上,假设它们与以目标为中心、半径为 \(d\) 的圆盘相交(其余障碍都可以忽略)。TangentBug 的一个变体 WedgeBug 是在 [100] 中为视场有限的行星漫游车开发的。
竞争比
评价使用不同信息的算法的一种流行方法,来自算法学界:计算竞争比 competitive ratio,让一个在线算法 on-line algorithm 与一个获得更多信息的算法竞争 [119, 171]。这个想法一般也能用于计划。首先表述一个代价,例如机器人解决导航任务走过的总距离。竞争比定义为
最大值取遍所有 \(e\in E\),像 Bug 算法那样,\(E\) 通常是无限集。导航问题的竞争比,可以拿最优距离与在线算法执行中机器人走过的总距离相比。由于 \(E\) 无限,许多计划给不出有限的竞争比。Bug 算法虽然优雅,就是这样的例子:想象目标非常近,但需要探索一大段障碍边界——障碍边界可以任意大,而到目标的最优距离很小,于是在 (12.28) 中对所有环境取值时结果无界。某些场合,把比值表达成表示规模的函数仍然有用,例如若 \(E\) 是 \(n\) 条边的多边形,\(O(\sqrt n)\) 的竞争比意味着 (12.28) 对所有 \(n\) 以 \(c\sqrt n\)(某个 \(c\in\mathbb{R}\))为界。Bug 算法的竞争比分析见 [65]。
迷路的牛问题 lost-cow problem [5] 很好地演示了竞争比分析及其中的问题。如图 12.26a,一头短视的牛沿着一道无限长的篱笆走,想找到门。这是一个方便的一维规划问题。若告诉牛门的位置,它直接走过去就行。若告诉它门恰好在距离 1 处,它可以朝一个方向走 1 个单位、没找到就回头试另一个方向;这时(环境集合对应所有门的位置)竞争比是 3。若只告诉牛门至少在距离 1 处呢?这时最好的策略是螺旋搜索 spiral search:来回之字形移动,每次把在各个方向上走的距离加倍,见图 12.26b——左 1 个单位、右 2 个单位、左 4 个单位……6。这个策略的竞争比是 9,而且是最优的。这种方法类似 2.2.2 节的迭代加深。
- 选「倍增」,点「把门放到最坏处」:门刚好在某个折返点外面一点,比值约 8.996——只能逼近 9、取不到。把门拖到折返点两侧,看 (b) 中比值的跳变:竞争比是最坏情况。
- 选「原书文字逐字执行」(左 1、右 1、左 2、右 2、左 4……):门在右边时比值逼近 13,在左边时只到 9;只有每次换方向都把离起点的距离加倍,最坏比值才是 9(参考代码第 11 项)。
- 选「一般增长因子 r」:最坏比值 \(1+2r^2/(r-1)\)(补充)在 \(r=2\) 时取最小值 9;\(r=1.5\) 和 \(r=3\) 都是 10。
12.3.4 没有几何模型的最优导航 Optimal Navigation Without a Geometric Model
本节介绍间隙导航树 gap navigation trees(GNT)[184, 186]:一种数据结构及相应的规划算法,用于在 12.3.3 节考虑的那类连续环境中做最优导航。本节假设机器人装有一个间隙传感器 gap sensor,如 11.5.1 节图 11.16 所示。任一时刻,对间隙传感器里可见的每个间隙,机器人都有一个动作可用;施加这个动作,机器人就朝相应的间隙移动。这可以在连续时间里施加,使机器人能「追 chase」某个特定的间隙。机器人没有别的感知信息:没有指南针,也不能测距离。因此不可能构造含有度量信息的环境地图。
设机器人被放进一个未知但简单连通的平面环境 \(X\)。GNT 可以推广到多连通环境,但那时有微妙的可区分性问题,只能保证在一个同伦类内最优 [185]。通过分析间隙传感器里临界事件发生的方式,可以建立一种树形表示,指示怎样在环境中最优地移动——尽管做不到精确的测量。既然间隙传感器连距离都测不了,机器人居然能沿最短路径移动,这似乎很不寻常——这再一次展示了 I-空间的威力。
相对于机器人位置的环境样貌,被编码成一棵树,指示机器人移动时间隙怎样变化。它给机器人提供了足够的信息,能沿最短路径走到环境的任何部分。重要的是要理解:这棵树不对应某张静态的环境地图,它表达的是环境相对于机器人看起来怎样,因而会随机器人在环境中移动而改变。
树根表示间隙传感器。对传感器里当前出现的每个间隙,都有一条边连到根,称为根边 root edges。每条根边对应机器人可以施加的一个动作:选一条根边,这个动作就让机器人沿直线朝那个间隙移动。于是有一个简单的控制模型,能让机器人精确地朝边界 \(\partial X\) 上的某个特定点移动(图 12.27:间隙追逐动作让机器人沿间隙方向直走,直到接触边界;一旦接触,环境的新部分就变得可见)。
记 \(V(x)\) 为可见区域:从 \(x\) 看得见的 \(X\) 中所有点的集合。\(X\setminus V(x)\) 称为阴影区域 shadow region,即从 \(x\) 看不见的所有点;阴影区域的每个连通分量叫一个阴影分量 shadow component。间隙传感器里的每个间隙对应 \(X\) 中一条在两处接触 \(\partial X\) 的线段(见图 11.15a);每条线段都是可见区域与某个阴影分量之间的边界。机器人想去这个阴影分量时,最短的走法就是直接朝间隙走。朝间隙移动时,机器人最终会到达 \(\partial X\),那时必须选择新的动作。
临界间隙事件
机器人移动时,间隙传感器里会发生几种重要事件:
- 消失 Disappear:机器人越过一条拐点射线 inflection ray(图 12.28),一个间隙消失——之前的某个阴影分量现在可见了。
- 出现 Appear:反方向越过拐点射线,一个间隙出现——出现了一个新的阴影分量,代表环境中新被遮住的部分。
- 分裂 Split:机器人越过一条双切射线 bitangent ray(图 12.29,图 12.5 也出现过),一个间隙分裂成两个——一个阴影分量分裂成两个。
- 合并 Merge:反方向越过双切射线,两个间隙合并成一个——两个阴影分量合并成一个。
在一般位置 general position 假设下(排除三个间隙合并成一个、或在两个间隙分裂处恰好出现一个间隙之类导致退化的环境),这是全部可能的事件。每发生一个间隙事件,都要反映到树上:间隙消失(图 12.30),相应的边和顶点直接删除;合并(图 12.31),插入一个中间顶点——它表示若追这个间隙,它会分裂成原来的两个间隙;分裂(图 12.32),中间顶点被删除;间隙出现是一个重要的情形,它产生树中的一个原始顶点 primitive vertex(图 12.33,用方块表示)。注意原始顶点永远不会分裂,因为追它只会导致它消失。
例 12.6(间隙导航树):设机器人不知道图 12.34 的环境。它从单元 1 依次走到 7,再回到单元 1。树的序列是 \(T_1,\ldots,T_7,T'_6,\ldots,T'_1\)(图 12.35)。根是实心黑点;还不知道是否原始的顶点画成圆圈,原始顶点画成方块。若任何叶子是圆圈,就意味着那个间隙遮住的 \(R\) 的阴影区域还没被完全探索。注意机器人一到单元 5 就看过了整个环境——这恰好发生在所有叶子都是原始顶点的时候。机器人回到第一个区域时,树更大了,因为它知道右边的区域由两个更小的区域组成。所有叶子都是方块,就意味着环境已被完全探索。
例子里环境中所有有趣的部分都探索过了。从这时起,所有叶子都是原始顶点,因为所有可能的分裂都已发现。某种意义上,环境已在间隙传感器所能达到的分辨率上被完全学到。探索环境的一个简单策略是:去追那些本身是非原始叶子、或者其孩子是非原始叶子的间隙。树中的叶子可以通过反复施加追它对应间隙的动作来追逐。这可能让树增量地改变;但只要选择去追「挡住目标叶子的那个间隙」,就没有问题(图 12.36)。每个非原始叶子要么分裂、要么消失。所有非原始叶子都追过之后,所有可能的分裂都已执行,只剩下原始叶子,环境就完全学到了。
用 GNT 做最优导航
既然没有精确的环境地图,就不可能用 \(\mathbb{R}^2\) 中的坐标表达目标状态。但目标可以用「为了让那个状态可见、必须去追的那个顶点」来表达。例如机器人探索时给它看一个物体:起初物体是看得见的,但可能有间隙出现把它挡住;经过几次合并后,树深处的某个顶点就对应着物体可见的那个位置。机器人可以通过追「最初因出现而挡住物体的那个顶点」,最优地导航回到物体。一旦这个顶点及其间隙消失,物体就可见了;这时机器人就能径直朝物体走(假设另有传感器指示物体方向)。[186] 论证了:机器人追 GNT 中的一个顶点时,恰好沿 6.2.4 节介绍的最短路路线图的路径走;每一对相继的间隙事件对应走过一条双切边。
用 I-空间来解释
用环境集合上的 I-空间来说,GNT 把大量环境当作等价的。这意味着构造了一个 I-map,导出 I-空间是所有可能 GNT 的集合;在这个 I-map 下,许多环境对应同一棵 GNT。因此机器人不用要求更多信息就能完成有趣的任务。例如两个环境只差旋转或缩放,GNT 表示就完全一样;令人惊讶的是,机器人甚至不必关心环境边界是多边形还是曲线,唯一重要的是间隙事件怎样发生。比如图 12.37 的环境都产生相同的 GNT,因而对机器人来说不可区分:它不能测距离,甚至不在乎墙是直是弯——这与导航任务无关;尽管如此,它执行的运动在欧氏距离意义下是最优的。正如 12.3.1 节的迷宫探索算法不需要完整地图就能找到物体,GNT 也不需要地图就能最优地导航。
- 切到「书中例 12.6」逐棵看图 12.35 的树:\(T_5\) 时所有叶子都是方块(整个环境都看过了);\(T'_1\) 比 \(T_1\) 多了两个方块孩子。
- 回到「自己拖着走」,点「沿路线走一圈」(我们自己的环境,补充):右边的日志记下每一次出现 / 消失 / 分裂 / 合并。顶点都稍微错开了一点,满足一般位置假设。
- 走进一个房间后点「在这里放一个物体」,再拖着机器人走到大厅另一头:日志会记下物体被哪个结点挡住;点「回到物体」,机器人只靠追这个结点(中途它会分裂、合并)就绕回了物体——全程没有测过一次距离。
12.3.5 概率定位与建图 Probabilistic Localization and Mapping
12.3 节到目前为止的问题都回避了概率建模。现在假设状态转移和观测都有概率模型。许多问题可以把 12.3.1 节的非确定模型换成概率模型来表述,这会得到表示「可能网格集合上、以及每个网格里位形上」的分布的概率 I-state。若问题保持完全一般,I-空间大到看起来没希望用目前的方式处理;若不要求最优,在某些特殊情形下可能取得进展。
当前的问题是:构造环境地图,同时相对这张地图定位机器人。回忆 1.2 节的图 1.7。本节介绍近年来在移动机器人学中流行的一般框架(见章末推荐的文献)。这里的讨论可以看作 12.2.3 节的推广——那里只关心当前问题的定位部分,现在连环境都不知道。当前问题可以理解为在状态空间
中的定位,\(\mathcal{C}\) 是位形空间,\(E\) 是环境空间。状态 \(x_k\) 表示成 \(x_k=(q_k,e)\);\(e\) 没有下标 \(k\),因为假设环境是静态的。历史 I-state 提供了确定状态所用的数据。和 12.2 节的定位一样,有被动和主动两个版本;主动问题的一个增量版本有时叫下一最佳视角问题 next-best-view problem [6, 35, 147]。难点在于机器人有两个相互冲突的目标:1) 在能获得尽可能多新数据的地方打开传感器;2) 这种对冗余的最小化可能使所有测量难以融合成一张全局地图。这里介绍被动问题;它的方法可以为解决主动问题提供信息。
设机器人是在 \(\mathbb{R}^2\) 中平移和转动的点。按 4.2 节,这给出 \(\mathcal{C}=\mathbb{R}^2\times\mathbb{S}^1\),即 \(SE(2)\)。记 \(q\in\mathcal{C}\) 为位形,给出机器人的位置和朝向。假设位形转移用概率建模,需要指定概率密度 \(p(q_{k+1}|q_k,u_k)\)。假设位形转移与环境无关(假设永远不发生碰撞),就可以把它提升到状态空间上得到 \(p(x_{k+1}|x_k,u_k)\):用 \(x_k\)、\(x_{k+1}\) 代替 \(q_k\)、\(q_{k+1}\),其中对任何 \(e\in E\),\(x_k=(q_k,e)\)、\(x_{k+1}=(q_{k+1},e)\)。
设观测来自一个深度传感器,理想情况下得到图 11.15b 那样的测量,但数据假设有噪声。12.2.3 节讨论的概率模型可以用来定义 \(p(y|x)\)。现在想象机器人走到环境的几个部分(比如图 11.15a 的那些),在每个地方做一次传感器扫描。若不知道每次扫描 \(y_k\) 是从哪个位形 \(q_k\) 做的,怎么把这些数据集缝合成一张正确的全局地图?知道位形的话这是平凡的;不知道的话,问题就像拼拼图。所以每个阶段的重要数据构成一个向量 \((y_k,q_k)\);若传感器观测 \(y_k\) 没有标上它所来自的位形 \(q_k\),就出现了拼图问题。若用信息严格约束 \(q_k\) 的可能性,拼起来就容易了。这个直觉引出下面的方法。
EM 算法
这个问题在实践中常用期望最大化 expectation-maximization(EM)算法 [11] 来解。在一般框架里有三种不同的空间:
- 参数集合:要通过某种测量与估计过程确定的东西。在我们的问题里它表示 \(E\),因为主要目标是确定环境。
- 数据集合:提供可用于估计参数的信息。在定位与建图问题里,它对应历史 I-空间 \(\mathcal{I}_K\)。每个历史 I-state \(\eta_K\in\mathcal{I}_K\) 是 \(\eta_K=(p(x),\tilde u_{K-1},\tilde y_K)\),\(p(x)\) 是 \(X\) 上的先验概率密度。
- 隐变量集合:未知、但为了完成参数的确定需要估计。在定位与建图问题里,这是位形空间 \(\mathcal{C}\)。
参数和隐变量都是未知的,两者之间的划分似乎很随意;但会看到,可以推出能很好地表达隐变量概率密度的式子,而参数则复杂得多。EM 算法由一个期望步接一个最大化步组成,两步按需重复,直到得到所需精度的解。这个方法在一般条件下保证收敛 [39, 192, 193];实践中即使对理论上不保证收敛的情形也似乎工作得很好 [181]。
从这里起,记 \(E\)、\(\mathcal{I}_K\)、\(\mathcal{C}\) 为 EM 算法的三个空间,因为它们直接属于这个问题。设机器人在环境中走了 \(K-1\) 个阶段,得到最终阶段 \(K\)。每个阶段 \(k\in\{1,\ldots,K\}\) 用传感器得到一个观测 \(y_k\)(例如声呐或测距仪的一组距离测量);对 \(k=1\) 到 \(k=K\) 施加动作 \(u_k\);起初假设 \(X\) 上有先验概率密度 \(p(x)\),这就得到 (11.14) 定义的历史 I-state \(\eta_k\)。
现在设想已经执行了 \(K\) 个阶段,任务是估计 \(e\)。从每个 \(q_k\) 测得环境的一部分 \(y_k\)。EM 算法生成一列不断改进的 \(e\) 的估计:两步 EM 的每一次迭代产生一个新的估计 \(e\in E\)。记 \(\hat e_i\) 为第 \(i\) 次迭代后的估计,\(\tilde q_K\) 为第 1 到第 \(K\) 阶段的位形历史。期望步计算给定 \(\hat e_i\) 时 \(\eta_K\) 的期望似然:
期望取遍位形历史。(书中脚注 3:实践中会对 \(p(\eta_K,q_K|e)\) 取对数,因为通常会出现含指数的密度;取对数让式子更简单而不影响优化结果,这里没有取,因为不涉及这个层次的细节。)既然 \(\eta_K\) 已给定,而期望消去了 \(\tilde q_K\),(12.30) 只是 \(e\) 与 \(\hat e_{i-1}\) 的函数。\(p(\eta_K,\tilde q_K|e)\) 可以写成
其中 \(p(\eta_K)\) 是只给定环境 \(e\) 时 I-空间上的先验密度。因子 \(p(\tilde q_K|\eta_K,e)\) 与 (12.30) 被积函数的第二个因子只差用 \(e\) 还是 \(\hat e_{i-1}\)。计算 (12.30) 的主要困难是计算 \(p(\tilde q_K|\eta_K,\hat e_{i-1})\)(或用 \(e\) 的版本)。这本质上是 12.2.3 节考虑的地图已知的定位问题:第 \(k\) 阶段的信息可以给出每个 \(q_k\) 的概率 I-state \(p(q_k|\eta_k,\hat e_{i-1})\);但这忽略了其余阶段的信息——这些新信息可以用来推断旧的位形:例如根据当前的测量和对施加过的动作的记忆,我们对几个阶段之前的位形有了更好的信息。[182] 给出了一种计算 \(p(q_k|\eta_k,\hat e_{i-1})\) 的方法,它计算两项:一项是 \(p(q_k|\eta_k)\),另一项是从阶段 \(K\) 开始、一直往回算到 \(k+1\) 的反向概率 I-state。
注意一旦确定下来,(12.30) 只是 \(e\) 与 \(\hat e_{i-1}\) 的函数。最大化步选出使 (12.30) 最大的 \(\hat e_i\):
这个优化常常太难;若选出的 \(\hat e_i\) 满足 \(Q(\hat e_i,\hat e_{i-1})>Q(\hat e_{i-1},\hat e_{i-1})\),收敛条件仍然存在。反复迭代 EM 算法,得到的是一种在 \(E\) 中局部爬升、到达一个局部最优的过程8。
方法成功与否的一个重要因素是 \(E\) 的表示。在 EM 的计算中,一种常见的做法是用一组路标 landmarks(11.5.1 节提到过):环境中能被传感器识别的特殊地点,若分类正确,能极大地改进定位。在 [182] 中,路标是机器人移动时由用户指示的。分类和定位误差都可以用概率建模并纳入 EM 方法。另一个极大简化 \(E\) 的表示的想法,是用细分辨率的网格来近似环境:给网格单元赋概率,得到一种叫占据栅格 occupancy grid 的数据结构 [52, 124, 160]。无论如何,\(E\) 都必须仔细定义,以保证在机器人刚开始移动时能为 \(p(e)\) 设一个合理的先验来初始化 EM 算法。
- 这个例子是补充的简化:只平移、线性高斯、已知数据关联、地图是一组路标。先看第 0 步:同一路标的拼图块 \(y+\hat q\) 散得很开,航位推算路径越走越偏。点几次「EM 一步」:拼图块很快对齐,但整张图的整体偏移要很多次迭代才慢慢纠正。
- 右边的 \(\log p(\eta|\hat e_i)\) 随迭代单调上升,最后贴近虚线(联合最小二乘的最优值);切到「log₁₀(距最优)」,后半段近似直线——EM 是线性收敛的。把 \(\sigma_y\) 调小,直线变平、收敛更慢。
- 勾上「E 步后验的 2σ 圆」并把感知半径 \(r\) 调小:观测越少,E 步对路径越没把握;从没进入感知半径的路标根本无法估计。
12.4 基于可见性的追逃 Visibility-Based Pursuit-Evasion
本节考虑基于可见性的追逃 visibility-based pursuit-evasion [105, 177]——1.2 节把它描述成一个捉迷藏游戏。这个题目极好地展示了 I-空间概念的威力。
12.4.1 问题表述 Problem Formulation
- 给定的连续环境区域 \(R\subset\mathbb{R}^2\):由简单闭曲线围成的开集。边界 \(\partial R\) 常是多边形,但也可以是任何分段解析的闭曲线。
- 无界时间区间 \(T=[0,\infty)\)。
- 逃逸者 evader:\(R\) 中的一个运动点。逃逸者在时刻 \(t\in T\) 的位置 \(e(t)\) 由一个连续的位置函数 \(\tilde e:[0,1]\to R\) 决定(书中脚注 4:按标准的函数记号,应写 \(\tilde e(t)\) 而不是 \(e(t)\),但书中不遵循这一点)。
- 追捕者 pursuer:\(R\) 中的一个运动点。逃逸者的位置函数 \(\tilde e\) 是追捕者不知道的。
- 可见性传感器:对每个 \(r\in R\) 定义一个集合 \(V(r)\subseteq R\)。
任务是为追捕者找一条路径 \(\tilde p:[0,1]\to R\),使得无论逃逸者的位置函数是什么,都保证能发现它,即存在 \(t\in T\) 使 \(e(t)\in V(p(t))\)。追捕者的速度并不重要:追捕者慢的话,时间域可以任意拉长。
把问题解成「验证没有逃逸者」会很方便:为追捕者找一条路径,走完之后保证没有任何地方还可能藏着逃逸者。这保证了执行计划的过程中追捕者会遇到任何一个逃逸者。事实上可以有任意多个逃逸者,追捕者会找到全部。这个方法系统地排除逃逸者可能藏身的任何地方。
状态给出追捕者与逃逸者的位置 \(x=(p,e)\),状态空间 \(X=R\times R\subset\mathbb{R}^4\)。逃逸者的位置未知,所以当前状态未知,I-空间就出现了。观测空间 \(Y\) 是 \(R\) 的子集族:对每个 \(p\in R\),传感器给出可见多边形 \(V(p)\subseteq R\)(用 11.1.1 节的记号是 \(y=h(p,e)\))。考虑时刻 \(t\) 的历史 I-state:追捕者的初始位置 \(p(0)\) 已知(没给就任意选一个),逃逸者可能在 \(R\) 中任何地方。输入历史 \(\tilde u_t\) 可以写成追捕者的历史 \(\tilde p_t\)(书中脚注 5:按 11.4 节的记号,运动模型是 \(\dot p = u\),\(u\) 是追捕者的速度;可以用自然动作建模逃逸者的速度 \(\dot e\);对 \(\dot p\) 积分就能得到任意 \(t\) 时的 \(p(t)\),所以 \(\tilde p_t\) 可以作为输入历史的更简单表示,不必直接提速度)。于是历史 I-state 是
其中 \((p(0),R)\subset X\) 反映初始条件:\(p(0)\) 已知,逃逸者位置 \(e(0)\) 可能在 \(R\) 中任何地方。
考虑非确定 I-空间 \(\mathcal{I}_{ndet}\)。追捕者的位置总是已知的,所以 \(R\) 中有意思的部分是逃逸者可能在的那个子集。于是非确定 I-state 可以写成 \(X_t(\eta_t)=(p(t),E(\eta_t))\),\(E(\eta_t)\) 是给定 \(\eta_t\) 时逃逸者可能位置的集合。照例,\(E(\eta_t)\) 是与 \(\eta_t\) 全部信息相容的最小集合。
看看 \(E(\eta_t)\) 怎样随时间变化。第一个瞬间之后观测到 \(V(p(0))\),知道逃逸者在 \(R\setminus V(p(0))\) 中——这正是 12.3.4 节定义的、从 \(p(0)\) 看的阴影区域。追捕者移动时 \(E(\eta_t)\) 随之变化。设告诉你追捕者现在在 \(p(t)\),但还没告诉你 \(\eta_t\),\(E(\eta_t)\) 有哪些可能?这取决于历史,但唯一有意思的可能是:每个阴影分量可能含有、也可能不含有逃逸者。对其中一些分量,我们可以确定它不含逃逸者。例如图 12.38:设追捕者起初认为走廊尽头可能有逃逸者;若它沿较小的闭路走,非确定 I-state 逐渐变化,但闭路走完时回到原值;然而若它绕较大的闭路走,走完时就能确定走廊里没有逃逸者。这个例子里越过的那条虚线,也许会让你想到 6.3.4 节那样基于临界边界的单元分解——这个想法马上就会用来设计解决这个问题的完整算法。在给出完整算法之前,先看几个有趣的例子。
例 12.7(问题什么时候可解?):图 12.39 是四个类似的问题。逃逸者的位置从不画出来,因为解法是保证没有逃逸者能藏起来。注意追捕者的速度与非确定 I-state 无关,所以解可以简单地画出追捕者的路径来定义。前三个例子很容易解;第四个却无解,因为至少有三个不同的藏身处(你能找到吗?)。记 \(V(V(p))\) 为从 \(V(p)\) 中至少一个点看得见的所有点的集合。使问题无解的条件是:存在三个位置 \(p_1,p_2,p_3\),对每个 \(i,j\in\{1,2,3\}\)、\(i\neq j\),都有 \(V(V(p_i))\cap V(V(p_j))=\emptyset\)。一旦到达一个藏身处,逃逸者就能溜到另外两处之间。最坏情况下这可能导致无休止的追逐,逃逸者永远逃脱。我们想要一个算法:系统地搜索 \(\mathcal{I}_{ndet}\),判断解是否存在。
既然一个追捕者解不了某些问题,就会好奇两个追捕者能否解决任何问题。下一个例子给出一个有趣的环境序列,表明对任意正整数 \(k\),都存在恰好需要 \(k\) 个追捕者才能解的环境。
例 12.8(一列困难的问题):图 12.40 序列中的每个环境都比前一个多需要一个追捕者 [73]。构造的基础是递归地保证有三个孤立的藏身处,就像图 12.39 最后一个问题那样;每这样做一次,就需要再多一个追捕者。这个序列递归地把三个需要 \(k\) 个追捕者的环境接在一起,得到一个需要 \(k+1\) 个追捕者的问题:三个环境连接的路口总需要一个额外的追捕者看守。这个构造基于图上追逃的 3-可分性 3-separability 概念 [143]。
考虑多连通环境(有洞的环境),问题会更有挑战:一个追捕者解不了任何这样的问题。确定解一个这类问题所需的最少追捕者个数是 NP-难 的 [73]。
12.4.2 一个完整算法 A Complete Algorithm
现在考虑设计一个解单个追捕者情形的完整算法。完整 complete 意味着有解就必须找到,否则就正确地报告无解。回忆图 12.38:非确定 I-state 只有在越过某条临界边界之后才发生有意思的变化。仔细分析所有可能发生这种临界变化的情形,就能解决追逃问题。结果它们恰好就是 12.3.4 节考虑过的那些情形:越过拐点射线和双切射线。图 12.38 是越过拐点射线的例子;图 12.41 指出了 12.3.4 节的间隙与环境中可能含有逃逸者的部分之间的联系——每个间隙后面,都是环境中可能含有、也可能不含逃逸者的一部分。
回忆阴影区域是从某个 \(p(t)\) 看不见的所有点的集合,写成 \(R\setminus V(p(t))\)。每个临界事件都会改变阴影分量的个数:越过拐点射线,一个阴影分量出现或消失(取决于方向);越过双切射线,要么两个分量合并成一个,要么一个分裂成两个。为了跟踪非确定 I-state,必须确定阴影区域的每个分量是清除的 cleared(一定不含逃逸者)还是被污染的 contaminated(可能含有逃逸者)。起初所有分量都标为被污染;追捕者移动时会出现清除的分量。解追逃问题就是移动追捕者,直到所有阴影分量都被清除——这时就知道没有地方还能藏着逃逸者。
- 出现:越过拐点射线、出现一个新阴影分量时,它总是标为清除,因为这是刚刚还看得见的那部分环境。
- 分裂:越过双切射线、发生分裂时,标签分给两个分量:被污染的分量分裂成两个被污染的分量,清除的分量分裂成两个清除的分量。
- 合并:反方向越过双切射线、分量合并时情况更复杂:若一个清除、另一个被污染,合并后的分量是被污染的;只有两个原分量都已清除时,合并后的分量才能标为清除。
- 消失:分量变成可见,直接删掉。
四种临界情形里,只有合并可能撤销追捕者的工作,也就是导致再污染 recontamination。
考虑用拐点射线和双切射线把 \(R\) 分解成单元,见图 12.42。这些单元具有下面的信息守恒性质 information-conservative property:若追捕者沿任何留在一个二维单元内的闭路走一圈,回到起点时 I-state 不变。这意味着追捕者在单元内走的具体路径并不重要。追逃问题的解可以描述为一串必须访问的相邻二维单元;由于信息守恒性质,穿过一串单元的具体路径可以任意选择。
在单元中搜索解,比在第 6 章里搜索路径更复杂,因为搜索必须在 I-空间里进行:追捕者可能在不同的时候、带着关于哪些分量已清除和被污染的不同知识访问 \(R\) 中的同一个单元。可以这样构造一个有向图 \(\mathcal{G}_I\):对 \(R\) 中每个二维单元,以及阴影分量的每种可能标签组合,在 \(\mathcal{G}_I\) 中定义一个顶点。例如某个单元的阴影区域有三个分量,\(\mathcal{G}_I\) 中就有 \(2^3=8\) 个对应顶点。\(\mathcal{G}_I\) 中两个顶点之间有边,当且仅当:1) 它们对应的单元相邻;2) 分量的标签与穿过两个单元之间边界所引起的变化相容。第二个条件意味着必须遵守出现、消失、分裂、合并的标签规则——例如穿过边界导致一个被污染的阴影分量分裂,那么新分量必须标为被污染,其它分量必须保持原来的标签。注意 \(\mathcal{G}_I\) 是有向的,因为 \(\mathcal{I}_{ndet}\) 中的许多运动不可逆:例如一个被污染的区域消失后,沿原路返回并不能让它以被污染的身份重新出现。还要注意,这个有向图里的信息不像 12.2.1 节懒惰离散定位那样单调改进:在当前的情境里,阴影分量合并时信息可能变差,因为污染会扩散。
搜索 \(\mathcal{G}_I\) 时,从任何一个所有阴影分量都标为被污染的顶点出发——具体从哪个单元出发并不重要。可以用 2.2 节的任何搜索算法找一个目标顶点:所有阴影分量都标为清除的 \(\mathcal{G}_I\) 顶点。若从初始状态到达不了这样的顶点,算法就能正确地宣布无解。若找到了目标顶点,\(\mathcal{G}_I\) 中的路径就给出解决问题必须访问的单元序列,\(R\) 中的实际路径由单元序列构造。有些单元可能不是凸的,但它们的形状足够简单,不需要复杂的运动规划算法就能构造出穿过单元序列的路径。
这里的算法概念上很直接,实践中表现也很好;但它的最坏情况运行时间是拐点射线个数的指数。考虑用 \(n\) 条边表达的多边形环境:可能有多达 \(O(n)\) 条拐点射线和 \(O(n^2)\) 条双切射线,单元个数以 \(O(n^3)\) 为界 [72]。不幸的是 \(\mathcal{G}_I\) 的顶点数是指数的,因为可能有多达 \(O(n)\) 个阴影分量,\(n\) 个分量有 \(2^n\) 种可能的标签。注意 \(\mathcal{G}_I\) 不必在搜索之前算好,可以在规划过程中增量地显露出来。最高效的完整算法更复杂,它在 \(O(n^2)\) 时间内解决追逃问题,推导方法是先证明:任何能用可见多边形解决的问题,都能被只用两束光的追捕者解决 [140]。这把 \(V(p(t))\) 从 \(R\) 中的二维区域简化成从 \(p(t)\) 发出的两条可转动射线,大大降低了 I-空间的复杂度。
- 「图 12.38 风格」:拖着追捕者在房间里绕小圈,走廊尽头一直是红的;走到走廊下方越过临界线,它就变绿了。所有环境都是网格近似(补充):每走一格,新的阴影分量只要与原来的污染区域有重叠就被污染(逃逸者速度无界),这一条规则同时给出了上面四条标签规则。
- 点「完整算法:自动求解」:在(位置, 标签)构成的图上做广度优先搜索——两条走廊和 T 形障碍的环境都找到了清除路线;三条拐两次弯的走廊、以及带洞的环境,搜完全部可达顶点后报告无解。
- 切到「例 12.7」,在三条走廊的环境里把三个点放在三条走廊的尽头:三块橙色的 \(V(V(p_i))\) 两两不相交,这就证明了一个追捕者无解(习题 14)。打开「信息守恒单元」看网格上近似的图 12.42 单元分解。
12.4.3 其它变形 Other Variations
本节的追逃问题有许多变形。有多个追捕者时问题难得多:可以根据阴影分量的变化做单元分解,但由于不同追捕者可见多边形之间复杂的相互作用,一些单元边界是代数曲面,因而很难实现完整算法。另一方面,可以用直接的启发式来指导多个追捕者:一个追捕者可以用本节的完整算法;它失败时,可以走到环境的某个部分然后等待,让第二个追捕者对每个阴影分量运行完整的单追捕者算法。这个想法可以对任意多个机器人递归使用。
给逃逸者加速度上界会让问题更复杂。这虽然让追捕者更强大,但更难设计一个能正确利用这额外信息的完整算法——(写书时)还没有这种情形的完整算法。
图 12.43 展示了几种给出不同 \(V(p(t))\) 定义的检测模型:(a) 距离无限的全向感知;(b) 视场有限的可见性;(c) 一条能转动的可见射线;(d) 距离有限、能转动的视锥,与相机模型很接近;(e) 三条能转动的可见射线。由于 I-空间的结构随感知模型剧烈变化,每种模型都需要不同的追逃算法。例如用图 12.43c 的模型时,一个追捕者需要沿 \(\partial X\) 移动;一旦它走进内部,阴影区域总是变成单一的连通分量。这种模型有时叫手电筒 flashlight。有两个手电筒时,一个可以走进内部,另一个保护之前的工作。有限深度的情形在实践中非常真实,但不幸的是最有挑战:所需追捕者个数一般取决于环境的度量性质,比如它的最小「厚度」。本节的方法在 [66] 中推广到了视场有限的情形,得到的临界曲线与 6.3.4 节的类似。更多相关材料见章末的文献综述。
12.5 感知不确定下的操作规划 Manipulation Planning with Sensing Uncertainty
操作规划是有趣的 I-空间最丰富的来源之一。机器人与世界中的障碍或物体相互作用时,估计状态的负担更重了。应对这个问题的经典方法,是严格限制机器人与障碍相互作用的方式:在 7.3.2 节的操作规划框架里,这意味着机器人必须抓起物体、把它搬到目的地;任何物体被抓取时必须处于稳定位形,放下后也必须回到稳定位形。
经典操作规划框架的假设放松之后,预测机器人和其它物体的行为就更难了。这立刻带来第 10 章的基础——可预测性方面的不确定性。下一个问题是设计传感器,使目标在这种不确定性下仍能达成;对每种感知模型,都会出现一个 I-空间。
12.5.1 节介绍原像规划框架 [53, 113],第 10、11 章讨论过的许多有趣问题都在一个具体的操作规划问题中得到处理:I-state、前向投影、反向投影和终止动作都在这个情境里得到刻画;而且在这个框架下证明了若干关于不确定性下规划的算法复杂度结果。12.5.2 节介绍的方法清楚地展示了直接用 I-空间推理的威力:其哲学是允许非抓取的操作形式(推、挤、扔),并设计简单的传感器,甚至完全不用传感器。这在仍然允许可行计划存在的同时,大大缩小了 I-空间。这违背了「信息越多越好」的直觉:用更少的信息会让状态更不确定,但在某些问题里这并不重要,重要的只是 I-空间变得更简单。
12.5.1 原像规划 Preimage Planning
原像规划框架(也叫 LMT 框架,以它的提出者 Lozano-Pérez、Mason 和 Taylor 命名)是作为一种进行不确定性下操作规划的一般方法而提出的 [53, 113]。这些概念适用于一般的位形空间,但这里只讲 \(\mathcal{C}=\mathbb{R}^2\)、\(\mathcal{C}_{obs}\) 是多边形的情形——这也是这个框架下大部分工作的共同假设。它可以对应一个在 \(\mathcal{W}=\mathbb{R}^2\) 中平移、可能还拿着一个零件的机器手的简化模型。一个流行的示例任务是插孔问题 peg-in-hole problem:零件是一根要插进稍大一点的孔里的钉子。制造业的机器人组装产品时经常执行这种操作。用 4.3.2 节的位形空间表示,机器人成为在 \(\mathbb{R}^2\) 中多边形障碍之间移动的一个点。
原像规划所用模型的显著特点如下:
- 机器人能执行顺应运动 compliant motions:它可以沿 \(\mathcal{C}_{obs}\) 的边界滑动。这不同于 Part II 中通常要求机器人避开障碍的要求。
- 预测中有非确定不确定性:动作决定运动方向,但执行中出现多大误差由自然决定。假设有界误差模型。
- 感知中有非确定不确定性,真实状态不能被可靠地估计。
- 目标区域通常是 \(\mathcal{C}_{obs}\) 的一条边,但更一般地可以是 \(\mathrm{cl}(\mathcal{C}_{free})\)(\(\mathcal{C}_{free}\) 的闭包)的任何子集。
- 使用分层规划模型:给机器人发一串运动命令 motion commands,每个运动命令都根据 I-state 施加终止动作 \(u_T\) 来结束。
顺应运动
马上会看到,能够执行顺应运动对减小机器人位置的不确定性至关重要。记 \(\mathcal{C}_{con}\) 为障碍边界 \(\partial\mathcal{C}_{obs}\)(也就是 \(\mathcal{C}_{con}=\partial\mathcal{C}_{free}\))。需要表述 \(q\in\mathcal{C}_{con}\) 时机器人运动的模型——一般来说,它因摩擦而变得复杂。这里假设简单的库仑摩擦 Coulomb friction 模型(操作规划中摩擦建模的更多细节见 [123])。设机器人在某个 \(q\in\mathcal{C}_{con}\) 处施加合力 \(F\),这个力可以用机器人控制的广义阻尼模型 generalized damper model [188] 维持。
得到的运动用摩擦锥 friction cone 刻画,见图 12.44a。牛顿力学的一个基本原理是障碍会施加反作用力(可以先看看 13.3 节对力学的介绍)。若 \(F\) 指向表面且与之垂直,障碍提供的反作用力会抵消 \(F\),不发生运动。若 \(F\) 不垂直于表面,可能发生滑动:一个极端是 \(F\) 平行于表面,这时一定沿边界滑动。一般 \(F\) 可以分解成平行和垂直分量;若平行分量相对垂直分量太小,机器人就卡住。图 12.44a 的摩擦锥精确地指出了发生运动的条件:参数 \(\alpha\) 刻画摩擦的大小(摩擦越大 \(\alpha\) 越大)。图 12.44b 是把摩擦锥倒过来得到的、\(F\) 的各种方向对应的行为:若 \(F\) 指向底部的区域,发生粘住 sticking,机器人不能动;若 \(F\) 指离障碍边界,接触就断开(这是合理的,除非边界有粘性);其余两种情形,机器人沿边界滑动。
- 在左图上拖动 \(F\),看 \(-F\) 什么时候进出摩擦锥,右图倒锥上高亮的区域(脱离接触 / 向左滑 / 粘住 / 向右滑)同时跟着变。
- 把 \(\alpha\) 拖到 0,再点「F 垂直压向边界」:只有恰好垂直时才粘住,偏一点就滑走——这就是「即使 \(\alpha=0\) 也可能粘住」的意思:自然的方向误差锥只要包含法向,就可能恰好垂直。
- 勾选「F = 重力」,慢慢加大边界倾角:倾角一超过 \(\alpha\),物体就开始下滑(滑动箭头的长短按库仑摩擦扣掉了摩擦力,属于补充)。
不确定性的来源
自然既干扰位形转移,也干扰传感器。令 \(U=[0,2\pi)\),表示命令机器人前进的 \(\mathbb{R}^2\) 中的方向。自然干扰这个命令,实际方向落在 \(\mathbb{S}^1\) 的一个区间内。如图 12.45a,固定动作 \(u\in U\) 的前向投影(回忆 10.1.2 节)是可能的未来位形构成的一个锥(运动模型用微分方程的精确表述见例 13.15)。图 12.45b 的感知模型在 11.5.1 节已经给出过:自然感知动作构成 (11.67) 给出的圆盘,\(y=q+\psi\),\(q\) 是真实位形,\(\psi\) 是自然感知动作,\(y\) 是观测;结果见图 11.11。
目标区域与运动命令
既然允许与障碍接触,目标区域就可以既包括 \(\mathcal{C}_{free}\) 中的点、也包括 \(\mathcal{C}_{obs}\) 的边。最常见的是选 \(\mathcal{C}_{obs}\) 的一条边作为目标区域。
现在可以描述规划问题了。也许很想用连续时间而不是离散阶段来表达模型。这是可行的路线,但会引出微分约束下的规划——那是 Part IV 的主题,复杂得多。原像规划框架采用分层的方法:定义一种受限的计划,叫运动命令 \(\mu\),通过构造一串运动命令来达成目标。这把连续时间的决策问题转换成一个涉及离散阶段的规划问题。每施加一个运动命令,机器人都必须施加一个终止动作来结束它,然后才能发出下一个运动命令。想象一个高层模块发出运动命令,一个低层模块执行每个命令直到满足终止条件。
对某个动作 \(u\in U\),令 \(M_u=\{u,u_T\}\),\(u_T\) 是终止动作。运动命令是一个反馈计划 \(\mu:\mathcal{I}_{hist}\to M_u\),\(\mathcal{I}_{hist}\) 是基于初始条件、动作历史和感知历史的标准历史 I-空间。运动命令在连续时间里执行:\(t=0\) 时 \(\mu(\eta_0)=u\);利用执行中收集的历史 I-state \(\eta\),运动命令最终给出 \(\mu(\eta)=u_T\),从而结束。若没达到目标,高层模块可以施加另一个运动命令。
原像
现在考虑怎样构造运动命令。用分层方法,「终止在目标区域中」这个主任务可以分解成达成一系列中间子目标。运动命令 \(\mu\) 与子目标 \(G\subset\mathrm{cl}(\mathcal{C}_{free})\) 的原像 preimage \(P(\mu,G)\),是所有这样的历史 I-state 构成的集合:从它们出发,不管自然怎样干扰,\(\mu\) 都保证达成 \(G\)。每个运动命令都必须能识别出子目标已经达成,才能施加终止动作。子目标一旦达成,得到的历史 I-state 必须落在下一个运动命令所需的历史 I-state 集合之内。记 \(\mathcal{M}\) 为所有允许的运动命令构成的集合,它其实可以看作高层模块的动作空间。
用运动命令规划
可以构造一个高层的开环计划
它是 \(k\) 个运动命令构成的序列(书中脚注 6:这个开环计划由闭环的运动命令构成,用分层建模完全可以接受)。尽管机器人执行的精确路径不可预测,运动命令的序列假设是可以预测的。每个运动命令 \(\mu_i\)(\(1\le i\lt k\))都必须以一个 \(\eta\in P(\mu_{i+1},G_{i+1})\) 的 I-state 终止9;\(\mu_1\) 的原像必须包含初始 I-state \(\eta_0\);目标由最后一个运动命令 \(\mu_k\) 达成。
更一般地,选择哪个运动命令不必可预测,可以依赖执行中的 I-state:这时可以设计高层反馈计划 \(\pi:\mathcal{I}_{hist}\to\mathcal{M}\),运动命令 \(\mu=\pi(\eta)\) 根据上一个运动命令终止后得到的历史 I-state \(\eta\) 来选择。这类变形见 [42, 53, 98]。
高层规划问题可以用第 2 章和第 10 章的离散规划算法来解。原像规划框架里最流行的方法是从目标出发做反向搜索。听起来简单,但可能的运动命令集合是无限的,很难以一种能保证完备性的方式采样 \(\mu\)。另一个麻烦是终止基于历史 I-state。所以规划相当有挑战:[53] 甚至用图灵机停机问题 [170] 的归约证明了原像一般是任何算法都不可计算的;[130] 证明了障碍为多面体的三维原像规划是 PSPACE-难的;之后 [26] 又证明了它甚至是 NEXPTIME-难的(书中脚注 7:NEXPTIME 是能在非确定指数时间内解决的所有问题的复杂度类,超出了图 6.40 所列的那些类)。
反向投影
Erdmann 提出了一种计算有效运动命令的实用方法:把可达性 reachability 与可识别性 recognizability 两个问题分开 [53, 54]。可达性指刻画保证能到达的点集;可识别性指根据历史 I-state 知道子目标已经达成。理解这种分离的另一种方式是:把自然对位形转移的影响与自然对感知的影响分开。
做可达性分析时,忽略感知不确定性,就可以用 10.1.2 节的前向投影与反向投影概念——唯一的区别是这里把它们用于连续空间和运动命令(而不是 \(u\))。记 \(S\) 为 \(\mathrm{cl}(\mathcal{C}_{free})\) 的子集,可以定义弱反向投影 \(\mathrm{WB}(S,\mu)\) 和强反向投影 \(\mathrm{SB}(S,\mu)\);还可以定义不定向反向投影 nondirectional backprojections \(\mathrm{WB}(S)\) 与 \(\mathrm{SB}(S)\),分别类似于 (10.25) 与 (10.26)。
图 12.46 是一个简单的问题:任务是用一个指向下方的运动命令到达一条目标边——灵感来自插孔问题。图 12.47 是图 12.46 问题中从目标区域出发的几个反向投影。动作是 \(u=3\pi/2\),但由于自然,实际运动落在图示的锥内。先假设除了目标区域,不允许与障碍接触:强反向投影见图 12.47a,从三角形区域内任何一点出发,不管自然怎样,都保证到达目标。弱反向投影是图 12.47b 所示的无界区域,表示从那里可能到达目标的位形。弱反向投影不再进一步考虑,因为这里重要的是保证到达目标,这由强反向投影完成;从这里起默认「反向投影」指强反向投影。利用弱反向投影,可以发展出另一个框架——Donald 提出的错误检测与恢复 error detection and recovery(EDR)[42]。
现在假设允许沿障碍边界做顺应运动,这能扩大反向投影。为简单起见设没有摩擦(图 12.44a 中 \(\alpha=0\))。反向投影见图 12.47c:机器人碰到侧壁后就滑下去,直到到达目标。滑动过程中不必跟踪精确的位形——这说明了顺应运动在减小不确定性方面的威力(12.5.2 节会进一步发挥这一点)。图 12.47d 是另一个运动命令的反向投影。
现在考虑在更一般的情形下计算反向投影:反向投影可以从 \(\mathrm{cl}(\mathcal{C}_{free})\) 的任何子集定义,也可以允许参数为 \(\alpha\) 的摩擦锥。要被包含在反向投影里,必须避开可能发生粘住的点。注意即使 \(\alpha=0\) 也可能粘住:例如在图 12.46 中,自然可能让运动方向恰好垂直于障碍边界,这时水平边上会粘住,因为没有切向运动。一般地,必须确定 \(\mathcal{C}_{obs}\) 的每条边和每个顶点上是否可能粘住。一条边上可能粘住,取决于 \(u\)、\(\alpha\),以及自然贡献的最大方向误差;若在顶点的任一条相邻边上可能卡住,机器人就可能卡在这个顶点上。
计算反向投影
人们提出了许多计算反向投影的算法,最早的一个见 [53, 54]。假设目标区域是包含在 \(\mathcal{C}_{con}\) 的边上的一条或几条线段。算法对一个固定的、基于方向 \(u\in U\) 的运动命令 \(\mu\) 按下列步骤进行:
- 标出每个可能粘住的障碍顶点;若能从目标区域边界上的某点滑离目标,也标出这个点。
- 对每个标出的顶点,沿执行 \(u\) 时自然允许的最大偏差方向延伸两条射线——这是把图 12.45a 的锥倒过来。图 12.48 画出了无摩擦(\(\alpha=0\))时延伸的射线。
- 从每条目标边出发,描出反向投影区域的边界。遇到的每条边都定义了一个半平面,机器人从其中的位形出发保证会进入这条边;在图 12.48 中这对应于在某条射线下方。描反向投影边界时,在每个交点处的走向根据「包含半平面中的点」来决定。
得到的反向投影见图 12.49:从三角形较陡的那条边上保证会滑动,所以它被包含在反向投影中;而从另一条顶边上可能粘住。适用于包含 \(\mathcal{C}_{free}\) 中多边形区域的目标区域的更一般算法见 [43](部分细节也见 [98]):它利用平面扫描原理(6.2.2 节)给出在 \(O(n\lg n)\) 时间内计算反向投影的算法,\(n\) 是定义 \(\mathcal{C}_{obs}\) 的边数;反向投影本身不超过 \(O(n)\) 条边。计算不定向反向投影的算法见 [18, 43];这时的一个困难是反向投影的边界可能相当复杂。[18] 给出了在 \(O(n^2\lg n)\) 时间内计算大小为 \(O(n^2)\) 的不定向反向投影的增量算法。
得到计算反向投影的算法后,还要改造它来计算原像。用图 12.45b 的感知模型,可以通过缩小子目标区域 \(G\) 来得到原像:记 \(\epsilon\) 为图 12.45b 中圆盘的半径,\(G'\subset G\) 为去掉一条厚度为 \(\epsilon\) 的带之后的子目标子集。若传感器返回 \(y\in G'\),就保证 \(q\in G\)。这给出了一种通过缩小子目标获得原像的方法;但若 \(\epsilon\) 太大,即使存在成功的计划,也可能找不到。
高层计划可以通过一个从(缩小 \(\epsilon\) 后的)目标区域出发计算反向投影的反向搜索来找。仍然有 \(\mathcal{M}\) 太大的困难,它控制着搜索的分支因子。一种可能是计算不定向反向投影;另一种可能是把 \(\mathcal{M}\) 离散化,例如 [98, 99] 把 \(\mathcal{M}\) 缩减成四个主方向,并用粘住的边作为子目标来为复杂环境计算计划。但离散化之后,就更难保证规划算法的完备性了。
原像规划框架看起来只适用于一个非常特殊的模型,但它可以推广、改造到更一般的设定:[27] 把它推广到半代数障碍模型,得到一个运行时间是位形空间维数双重指数的规划方法(基于 6.4.2 节的柱形代数分解);[22] 给本节考虑的自然动作空间赋一个均匀概率密度,引入了概率反向投影;[101, 104] 又进一步把反向投影和原像推广定义为最优 cost-to-go 函数的水平集,于是可以用动态规划方法计算计划。
- 依次点「对照图 12.47」的 (a)(b)(c):不允许接触时强反向投影是目标上方的小三角形;弱反向投影是向上张开的无界区域;允许顺应运动(\(\alpha=0\))后整个槽都进来了,上方还多了一个更高的三角形。
- 点 (d)(斜向下的命令):在我们的模型里右侧顶面不会粘住,机器人能沿它滑进槽,所以算出的区域比书中图 12.47d 画的大一些——书中的图可能另有假设。整个计算是网格上的近似(补充:自然每一小步可以改变一次方向,边界误差约 1–2 格)。
- 切到「图 12.48 / 12.49」:三角形较平的左上边是红色的粘住边,它上方没有被涂色;较陡的右上边上方属于强反向投影。把 \(\alpha\) 调到 20°,右上边也变红,区域随之缩小。再勾「预像:把目标缩小 \(\epsilon\)」并加大 \(\epsilon\):预像缩成 \(G'\) 上方的小三角形,\(\epsilon\) 太大时干脆消失。
12.5.2 非抓取操作 Nonprehensile Manipulation
靠抓取来操作是非常受限的。人操作物体的许多有趣方式都不涉及抓取:物体可以被推、翻、扔、挤、转、拍、吹……厨房里的经典例子是握着平底锅、手腕一抖把薄饼翻过来。这些都是非抓取操作 nonprehensile manipulation 的例子,即不抓取的操作。
让机器人抓取物体的诱惑,来自对「估计并控制状态」的执念。对非抓取操作,这个任务更令人生畏,因为有时物体看起来脱离了直接控制,这导致可预测性上更大的不确定性和更重的感知负担。然而在 I-空间中规划,也许能避开所有这些问题。已经出现了一些工作,表明用很少的感知甚至完全不用感知,就能达成操作目标。这导致了一种极简主义 minimalism [28, 57, 123]:设计传感器的方式要让 I-空间简化,而不是去操心精确的估计。寻找极简机器人系统,与 11.2.1 节提到的「尽可能小的导出 I-空间」的追求完全一致:传感系统应当简单,却仍能完成任务——最好不丢掉完备性。这方面的大多数工作关心的是找可行解,而不是最优解,这使 I-空间得以进一步简化。
本节给出一个代表这种极简主义极端版本的例子:开发一个无传感器操作 sensorless manipulation 系统。乍看之下这似乎很荒唐:从 10.1.2 节的前向投影看,若自然在位形转移中引入不确定性又没有传感器,不确定性似乎只能增长。为了反驳这种直觉,顺应运动有减小不确定性的能力——这与 11.5.4 节的讨论一致:只要知道某些运动命令被成功执行了,就可能减小不确定性。在无传感器操作的一个早期演示中,人们证明了只要沿几个方向倾斜托盘,就能把躺在托盘里的内六角扳手(L 形扳手)放到已知的朝向 [57]:不管扳手的初始位形如何,最后都得到同样的朝向,而且不需要任何传感器。这可以看作图 11.29 托盘里滚球的更复杂的推广,也是图 12.44 那样顺应运动的一个例子——只是现在的力 \(F\) 由重力产生。
挤压零件
现在介绍另一个无传感器操作的例子,由 Goldberg 和 Mason 提出 [67, 68, 69](另见 [123]),[15] 有一个 Java 实现。设工厂里的传送带上一个个地送来凸多边形零件,它们要用在装配操作中,需要摆成给定的朝向。图 12.50 是一个平行夹爪 parallel-jaw gripper 的俯视图:机器人可以把两个夹爪合拢来执行一次挤压操作,图 12.50a 是挤压之前的零件,图 12.50b 是之后。假设一个简单的力学模型:两个夹爪以恒定速度相向运动,而且运动得足够慢,可以忽略动力学。为了帮助零件滑到位,可以把其中一个夹爪看作无摩擦接触(这是一种真实的装置,见 [28])。机器人可以在 \([0,2\pi)\) 中的任何朝向上执行挤压(由于对称,其实只需要 \([0,\pi)\))。记 \(U=[0,2\pi)\) 为所有挤压动作的集合。每个挤压动作在零件不能再被挤压时自行终止(不会压坏零件)。
规划问题可以建模成与自然的博弈:零件的初始朝向 \(x\in[0,2\pi)\) 由自然选择,而且未知。状态空间是 \(\mathbb{S}^1\)。对给定的零件,任务是设计一个挤压操作序列
使零件无论初始状态如何都到达一个已知的朝向。注意对最终状态没有具体要求。第 \(i\) 个运动命令结束后,历史 I-state 就是到目前为止施加过的挤压序列
下面使用非确定 I-空间 \(\mathcal{I}_{ndet}\)。要求可以表述为得到一个单元素的非确定 I-state(只含一个可能的朝向)。若零件有对称性,任务就改成确定一个对称类(只含有限个朝向)。
考虑一个未知朝向的零件怎样运动。由于转动对称,用零件与机器人之间的相对角度来描述挤压的效果会很方便:令 \(\alpha=u-x\)(模 \(2\pi\) 运算)。起初 \(\alpha\) 可以取 \([0,2\pi)\) 中的任何值。结果是一次挤压之后,\(\alpha\) 总被逼到有限个值之一。这可以用直径函数 diameter function \(d(\alpha)\) 来解释:它表示在朝向 \(\alpha\) 处切零件得到的最大厚度。图 12.51 是一个矩形的这种切片。距离函数的局部极小指示零件会稳定在哪些朝向上,如图 12.50b。零件在挤压中改变朝向时,\(\alpha\) 的变化方式让 \(d(\alpha)\) 逐渐减小。于是 \([0,2\pi)\) 可以划分成若干吸引域 regions of attraction,如图 12.52,它们的行为很像 8.5.1 节的漏斗。
不用传感器解决问题的关键观察是:每次挤压,不确定性不会变得更糟,而且通常会减小。设 \(u\) 固定,对状态转移方程 \(x'=f(x,u)\),一个区间的 \(x\) 值会得到同一个 \(x'\)。由于转动对称,最好用 \(\alpha\) 来表达:记 \(s(\alpha)\) 为一次挤压后得到的相对朝向。\(\alpha\) 是 \(x\) 与 \(u\) 的函数,所以这可以写成一个挤压函数 squeeze function \(s:\mathbb{S}^1\to\mathbb{S}^1\):
(关于符号约定,见脚注11。)也可以定义关于 \(\alpha\) 值的区间 \(A\) 的前向投影:
任何区间 \(A\subset[0,2\pi)\) 都可以理解为一个非确定 I-state,基于已执行过的挤压历史——只不过它是关于相对朝向、而不是原状态定义的。12.1.2 节讨论的算法可以用于 \(\mathcal{I}_{ndet}\)。[68] 给出了一个从单元素非确定 I-state 出发的反向搜索算法:规划通过在 \(\mathcal{I}_{ndet}\) 上反向搜索进行,每次迭代中可能相对朝向的区间 \(A\) 增大,直到最终到达整个 \(\mathbb{S}^1\)(若有对称性,则是对称的周期)。
这个算法是贪心的:每一步都试图让 \(A\) 尽可能大。从图 12.52 注意到,吸引域在直径函数的极小处最大,所以只有极小值才值得作为 \(\alpha\) 的候选。记 \(B\) 为函数 \(s\) 的原像。第一步,算法找出使 \(B(\alpha)\) 最大(按 \(\mathbb{S}^1\) 中的长度)的 \(\alpha\),记这个相对朝向为 \(\alpha_0\),令 \(A_0=B(\alpha_0)\)。之后的每次迭代,令 \(A_i\) 为 \([0,2\pi)\) 中满足
的最大区间,\(|\cdot|\) 表示区间长度。这意味着存在一次挤压操作,能把 \(S(A_{i-1})\) 中的任何相对朝向一次挤进 \(A_i\)。迭代重复进行,生成 \(A_{-1}\)、\(A_{-2}\) 等等,直到 (12.39) 不再能满足。[68] 证明了对任何多边形零件,区间 \(A_i\) 会一直增大,直到得到整个 \(\mathbb{S}^1\)(或对称的周期)。
设已经算出序列 \((A_{-k},\ldots,A_0)\),还必须把它变换成一个用机器人固定坐标系表达的计划。\(k\) 步动作序列 \((u_1,\ldots,u_k)\) 由下式恢复:
且 \(u_{-k}=0\) [68]。(12.40) 中的每个 \(a_i\) 是 \(A_i\) 的左端点。对齐方式有一定的选择自由,(12.40) 的第三项选取中间的动作,以提高对朝向误差的稳健性。(书中没有定义 \(\beta_{i-1}\);页面上的组件用等价的「前向对齐」来构造计划:每一步把当前的不确定区间平移到下一个原像区间的正中间。)利用 [30] 中「\(n\) 条边的零件不需要超过 \(O(n)\) 次挤压操作」的证明,这个完整算法的运行时间是 \(O(n^2)\)。
例 12.9(挤压一个矩形):图 12.53 是一个需要两次挤压的简单计划:无论初始朝向如何,都能把矩形零件摆正。每一列是计划的一次执行,共四次。第一次挤压后,零件的朝向是 \(\pi/2\) 的倍数;第二次挤压后,朝向就已知了。虽然每次执行看起来都不一样,却不需要反馈,因为 I-state 里根本不含传感器信息。
- 选矩形,夹爪角拖到 0° 挤一下,I-state 变成 {0°, 90°};再拖到 45° 挤一下,朝向就唯一了——这就是例 12.9 的两步计划。贪心反向搜索给出的区间宽度是 126.9° 再到 180°(参考代码第 12 项)。
- 点「执行计划」,看直径函数 \(d(\varphi)\) 图上的蓝点在每次挤压时滑进各自吸引域的极小,就像漏斗;绿色阴影是这一步的原像区间。
- 选等边三角形执行计划:挤压函数的周期是 60°,读数都一样(mod 60°),但有的副本尖朝上、有的尖朝下——平行夹爪分不清它们(补充:朝向最多定到挤压函数的周期 \(T\),\(T\) 整除 \(\pi\))。不规则五边形需要 3 次挤压。
延伸阅读 Further Reading
书中说,这一章的材料很容易扩充成一整本关于感知不确定下规划的书:讲了几个关键主题,还有大量别的主题没讲。下面按原书顺序整理它给出的(不完整的)文献指引:
- 12.1 节把 I-空间转换成普通状态空间,所以第 10 章的许多方法与文献都适用。POMDP 在运筹学和随机控制理论中有大量工作 [94, 112, 125, 173],近年在人工智能中也有很多 [86, 110, 111, 131, 142, 146, 149, 150, 157, 197, 198]。其中许多算法会压缩或近似 \(\mathcal{I}_{prob}\),得到的可能是非最优解,但能处理几十个状态的问题。
- 12.2 节的定位是机器人学最基本的问题之一,相关文献数以百计。图上的定位见 [49, 61];组合定位的讲法基于 [50, 74];对称造成的歧义也出现在 [7];感知极少的组合定位见 [134]。概率定位的进一步阅读见 [3, 37, 76, 78, 83, 85, 93, 108, 109, 135, 155, 166, 167, 187]。[179, 180] 用传感器不确定性场表达定位不确定性,那是一种导出 I-空间。
- 12.3 节综合了许多来源。迷宫搜索方法及其向图探索的推广见 [14];可区分性与卵石的问题再次出现在 [9, 46, 47, 116, 159, 185];竞争比与在线导航的组合方法见 [13, 38, 40, 60, 65, 90, 91, 119, 139, 153]。Stentz 算法及相关工作见 [92, 174]([92] 是 D* Lite);地形探索的多分辨率方法见 [138];Bug 算法见 [89, 95, 100, 114, 115, 151, 164];基于广义 Voronoi 图的相关传感器规划见 [32, 33],另见 [156]。间隙导航树在 [184, 185, 186] 中提出;其它极简建图工作见 [82, 154, 162];基于路标的导航见 [64, 99, 165]。
- 概率建图与定位(常称 SLAM)有大量文献 [183],另见 [29, 34, 41, 127, 141, 195]。最早的工作之一是 [172];动态规划在这一情境下的早期应用见 [97];一个著名的 SLAM 演示见 [25](博物馆导览机器人)。EM 算法的入门见 [11],收敛性见 [39, 192, 193]。移动机器人学的一般读物见 [16, 48]。
- 12.4 节主要基于 [73, 105]。追逃问题最早在微分博弈论中研究 [4, 77, 80];图上的追逃在 [143] 中提出,相关理论分析见 [10, 96, 126]。基于可见性的追逃在 [177] 中提出,第一个完整算法见 [105];简单多边形中单个追捕者的 \(O(n^2)\) 算法见 [140]。考虑曲线环境、光束等的变形见 [31, 36, 51, 103, 107, 132, 168, 169, 176, 178, 194];三维追逃见 [106];感知极少、没有事先给定地图的版本见 [75, 87, 151, 159, 196]。视觉跟踪运动目标的问题与追逃密切相关,有障碍的见 [8, 70, 71, 102, 128, 129],没有障碍的见 [59, 79, 161]。计算可见性信息的组合算法综述见 [137];艺术画廊与传感器布置问题也相关 [19, 136, 163]。双切事件也出现在可见性复形 [148] 和视点图 aspect graph [145] 中,它们是相关的基于可见性的数据结构。
- 12.5 节主要受 [43, 53, 57, 69, 113, 189] 启发,许多工作在 [123] 中有综述。概率版本的原像规划见 [23, 24, 104];视觉原像见 [62];操作不确定性的仔细分析见 [20, 21];原像规划的更多内容见 [98, 99]。错误检测与恢复(EDR)框架用到了许多原像规划的想法,但通过允许执行中出现可修正的错误,能解决更多问题 [42, 44, 45]。顺应运动也见 [18, 43, 84, 120, 122, 144];摩擦在位形空间中的效果见 [55]。零件定向的更多工作见 [28, 58, 67, 68, 152, 190];更多形式的非抓取操作见 [1, 2, 12, 56, 117, 118, 175]。一篇提出「虚拟泥土原理 principle of virtual dirt」的幽默论文是 [121];这个想法后来出现在 [158] 中,也出现在 iRobot 公司的 Roomba 自动吸尘器里。
本章速查表
| 概念 | 要点 |
|---|---|
| 大状态空间 | 图 12.1:\(\vec x=\eta_{der}\)、\(\vec X=\mathcal{I}_{der}\)、\(\vec U=U\)、\(\vec\Theta\subseteq Y\)(自然动作 = 观测)、\(\vec f\)、\(\vec x_I=\eta_0\);(12.1) \(\vec X_G\):保证在 \(X_G\) 里的 I-state。 |
| 代价 | (12.2);概率:(12.3)(12.4) 取期望;非确定:每阶段取最坏太悲观、阶段可加性被破坏,代价在 \(X_k(\eta_k)\) 上不变时 (12.5)(12.6)。无观测 ⇒ I-state 可预测 ⇒ Formulation 2.3。 |
| \(\mathcal{I}_{ndet}\) 上的算法 | \(|\vec X|=2^n-1\)(百万 ≈ 20 个原状态);值迭代 (12.7);\(\vec\Theta\) 由 (12.8)(12.9) 给出;策略迭代、反向投影图搜索、Dijkstra(最坏情况最优);无传感器时退化成 2.3 节。 |
| POMDP | \(\mathcal{I}_{prob}\) 是 \(n-1\) 维连续空间;近似值迭代 (12.10)(有限 \(\vec\Theta\) ⇒ 求和、Dirac);精确方法:值函数分段线性 + LP,或枚举有限个终端 I-state 逐级回滚。 |
| 定位 | 被动 = 计算 I-state,主动 = 规划使 I-state 变小;绑架机器人问题;网格:\(x=(p,d)\)、(12.11) \(U=\{F,B,R,L\}\)、\(y\) = 动没动、(12.12) 观测从 \(y_2\) 开始;对称类;预先计算 vs 懒惰;里程坐标、改道路径、信息改进 \(X(\eta_2)\subseteq X(\eta_1)\);指南针让对称消失。 |
| 连续组合定位 | 指南针 + 可见性传感器;\(H(y)\) = 平移叠合;可见性单元分解 \(O(n^2r)\) 个单元;可见性骨架 \(O(m+\lg n+s)\) 时间、\(O(n^5)\) 空间;叠 \(k\) 份地图找消歧运动;\(k\) 倍竞争;最优定位 NP-难。 |
| 概率定位 | (12.19) \(y_k=h(x_k,x_{k-1},\psi_k)\);(12.20)–(12.22);连续:\(p(x_{k+1}|x_k,u_k)\)、\(p(y|x)\) = 高斯乘积;卡尔曼 / 扩展卡尔曼 / 粒子滤波(蒙特卡洛定位)。 |
| 环境不确定 | (12.23) \(X=\mathbb{Z}\times\mathbb{Z}\times D\times E\);地图等价(\(SE(2)\));建图 / 判定环境 / 导航 / 搜索;例 12.4(\(e_1\equiv e_7\)、\(e_2\equiv e_8\)、\(e_3\) vs \(e_9\));「足以解决问题的分辨率」。 |
| 迷宫搜索 | Blum–Kozen:有限自动机 + 一个计数器(纬度)+ 转角 \(r\bmod3\)(\(+4\equiv1\) 顺时针、\(-4\equiv2\) 逆时针);唯一点 + 向南的虚拟细障碍 ⇒ 一条闭路;之字形覆盖;对数空间。 |
| D* | 反向 Dijkstra 的动态版;\(G_{best}\)(键)、\(G_{cur}\)、(12.24) \(G_{via}\);图 12.18 六步;代价变了就把它放回 \(Q\),处理到 \(G_{cur}(x_k)\le G_{best}\);执行时始终是当前信息下最优;I-空间解释 \(X=\mathcal{C}\times E\)。 |
| Bug 与竞争比 | 目标传感器 + 局部可见性;Bug1 (12.25) \(d+\tfrac32\sum p_i\);Bug2 (12.26) \(d+\tfrac12\sum n_ip_i\);TangentBug (12.27);竞争比 (12.28);迷路的牛:恰为 1 → 3,倍增 → 9(最优)。 |
| GNT | 间隙传感器、根边、追间隙;阴影分量;四种事件(出现 / 消失 / 分裂 / 合并);原始顶点(方块);全是方块 ⇒ 探索完毕;追结点 = 沿最短路路线图;导出 I-空间 = 所有 GNT。 |
| EM 建图 | (12.29) \(X=\mathcal{C}\times E\);拼图直觉;参数 \(E\)、数据 \(\mathcal{I}_K\)、隐变量 \(\mathcal{C}\);E 步 (12.30)(12.31)(需要用全部阶段做平滑);M 步 (12.32);路标、占据栅格。 |
| 追逃 | Formulation 12.1;(12.33);\(X_t(\eta_t)=(p(t),E(\eta_t))\);清除 / 污染、四条标签规则、只有合并会再污染;信息守恒单元;有向图 \(\mathcal{G}_I\);\(O(n^3)\) 个单元、\(2^n\) 种标签;\(O(n^2)\) 双光束算法;\(V(V(p))\) 判据;\(k\) 个追捕者的环境序列;有洞 ⇒ 一个不够;最少追捕者数 NP-难。 |
| 原像规划 | LMT;顺应运动、摩擦锥(粘住 / 滑动 / 脱离);方向误差锥;运动命令 \(\mu:\mathcal{I}_{hist}\to\{u,u_T\}\);原像 \(P(\mu,G)\);(12.34);可达性 vs 可识别性;SB / WB;算反向投影三步、\(O(n\lg n)\);缩小 \(\epsilon\) 得原像;不可计算 / PSPACE-难 / NEXPTIME-难。 |
| 挤压零件 | 无传感器;(12.35)(12.36);直径函数的极小 = 稳定朝向,吸引域像漏斗;挤压函数 (12.37)、(12.38);贪心反向搜索 (12.39)、(12.40);\(O(n)\) 次挤压、\(O(n^2)\) 算法;例 12.9:矩形两次。 |
常见陷阱
- 把「原状态不可预测」当成「必须用反馈」:没有观测时,导出 I-state 的路径是完全可预测的,计划可以是一串动作(12.1.1、例 12.5、例 12.9)。
- 在 \(\mathcal{I}_{ndet}\) 上每阶段都取最坏代价:不同阶段的最坏情况可能来自不同的状态路径,过于悲观,还破坏阶段可加性;要么让代价在 \(X_k(\eta_k)\) 上不变((12.5)(12.6)),要么换概率模型。
- 低估 I-空间的规模:\(n\) 个状态的 \(\mathcal{I}_{ndet}\) 有 \(2^n-1\) 个状态,\(\mathcal{I}_{prob}\) 是 \(n-1\) 维单纯形;通用方法只能对付十几个状态——所以要找结构、找小的导出 I-空间。
- 以为一定能定位到单个状态:对称性(例 12.2)使最好的结果也只是一个对称类;目标集合要定义成「最小可达 I-state」。
- 把懒惰搜索当成普通图搜索:机器人不能瞬移,展开一个状态要真的走过去(改道路径的代价);搜索图是有向的。
- 把 \(H(y)\) 当成单个点:可见性传感器再完美,环境里重复的结构也会让多个位置给出相同读数(例 12.3)。
- 认为不知道精确环境就没法完成任务:例 12.4、12.5、迷宫搜索、GNT 都表明,环境只要在「足以解决问题」的分辨率上被认识;\(e_1\) 与 \(e_7\) 对机器人来说根本是同一个环境。
- 记反模 3 的规则:右转 +1、左转 −1,顺时针一圈 \(r=+4\equiv1\),逆时针 \(r=-4\equiv2\)(原书写反了)。
- 以为 \(A^*\) 在未知环境里也是「最优」的:它不计改道代价,执行起来可能浪费大量探索;D* 才保证每一步都是当前信息下的最优。
- 以为 Bug 算法有有限的竞争比:目标很近、障碍边界很长时,(12.28) 无界;Bug1、Bug2 谁更好取决于环境。
- 把迷路的牛的「加倍」理解成每个距离左右各走一次再加倍:那样竞争比是 13;要每次换方向时都把离起点的距离加倍,才是 9。
- 在追逃里把「看见过」当成「清除了」:逃逸者速度无界,清除的阴影分量一与污染分量合并就重新被污染;追捕者的速度反而无关紧要。
- 忘了即使 \(\alpha=0\) 也可能粘住:自然的方向误差锥若包含某条边的法向,那条边上就可能粘住,必须从反向投影中排除。
- 以为没有传感器不确定性只能增长:顺应运动与挤压能把一整个区间的初始状态逼到同一个结果——每次挤压不确定性都不会变差。
习题导引
只给思路,不给完整解答。标「互动」的可以先在本页对应的图里做实验;数值都由参考代码核对。
- 图 12.2a 上的非确定 I-state(原书写「图 12.1a」12):从位置 3 朝北出发、\(\eta_0=X\),执行 \((L,L,F,B,F,R,F,F)\)。逐步做 \(\vec f\):第一步「没动」也能排除状态。(互动:被动定位的「习题 1」预设;最终定位到 \(4^{\rightarrow}\)。)
- 用图 10.6 的算法设计定位计划:在 \(\vec X=\mathcal{I}_{ndet}\) 上从 \(S=\vec X_G\)(单元素或最小可达 I-state)出发做反向投影,直到 \(X\) 被加入 \(S\)。
- 图 12.54 的定位计划:先用被动定位的方法看哪些动作序列能分开状态;最坏情况最优计划的结构可以在「主动定位」图里选「图 12.54」看到(参考代码第 6 项:可达 I-state 180 个,按书中代价 \(G^*(X)=12\),最坏 7 步)。
- 用纬度和朝向找唯一点:沿障碍边界走一圈,纬度的最小值给出最南的那一排;在最南的顶点里,靠闭路方向(模 3)判断哪个在最西。
- 六个环境里的观测序列:注意题目没有说真实环境是哪一个(\(e_4\) 的右上格甚至是障碍);不同的真实环境给出不同的观测(参考代码第 8c 项)。(互动:判定环境的「习题 5」预设,点地图换环境。)
- 用两块卵石代替计数器:一块卵石放在纬度 0 的参考处,另一块按「计数器的值」来回挪动;比较两块卵石是否在同一格来模拟计数器的比较与增减。
- 把图 12.23 的轨迹走完:按 Bug2 的规则,每次只在 m-线上比上次碰撞点更近、且能朝目标走的点离开。(互动:Bug 图的「图 12.23」场景。)
- 迷路的牛的竞争比是 9:门在折返点 \(2^k\) 外一点时,走过的距离是 \(2\sum_{i\le k+1}2^i+2^k\),除以 \(2^k\) 趋于 9。注意要按 (−2)^i 的折返点(见脚注 6)。(互动:迷路的牛。)
- \(n\) 道篱笆:(a) 若像正文那样门恰好在距离 1,依次探每一道(走 1 再回来),最坏比值 \(2n-1\);若只知道「不超过 1」,门可以离得任意近——想想为什么这时任何策略的最坏比值都无界。(b) 距离未知:在 \(n\) 道上轮流按几何级数加深,选最优的增长因子;(补充)已知的最优竞争比是 \(1+2n^n/(n-1)^{n-1}\),\(n=2\) 时正是 9 [5]。
- 图 12.42 的环境里沿图 12.55 的路线画 GNT:每越过一条拐点射线或双切射线,就按出现 / 消失 / 分裂 / 合并更新树。(互动:GNT 图「自己拖着走」时右侧的事件日志就是这种逐步更新。)
- 让 Bug1 的界 (12.25) 取等号:要在每个障碍上恰好走 \(3/2\) 圈,离开点还必须与碰撞点在空间上几乎重合(否则两点之间的那段直线被省掉了)。考虑一根垂直于连线的细墙:碰撞点与墙另一面正对的点几乎重合,沿边界却相距半个周长——界在墙变薄的极限下取到。
- 图 12.56a 的单追捕者解:有的区域必须访问多次,因为离开后会被再污染;先把 \(a\)…\(g\) 这些口袋按相互可见关系分组。
- 图 12.56b 任意多对「脚」:找一个与脚的对数无关的扫描模式,逐对清除并保证清除过的脚不会通过合并被再污染。
- 三个 \(V(V(p_i))\) 两两不相交 ⇒ 一个追捕者不够:追捕者在一个时刻最多「威胁」一个藏身处的邻域;逃逸者总能待在另外两个之一。(互动:追逃图的「例 12.7」。)
- 直径函数最多 \(O(n^2)\) 个顶点:\(d(\varphi)\) 在每一段上等于某一对顶点在夹爪法向上的投影之差(一段正弦曲线),分段点是这对「支撑顶点」发生变化的角度;顶点对最多 \(O(n^2)\) 个。(补充:用旋转卡壳的论证,凸 \(n\) 边形的对踵顶点对只有 \(O(n)\) 个,所以这个界并不紧。)正多边形时直径函数的周期很小。(互动:挤压图换正六边形。)
- (12.8)(12.9) 的其它版本:正文的 (12.8)(12.9) 本身就是按状态-自然传感器映射写的13;可以写出状态传感器映射(去掉 \(\psi\))的特例,作为热身。
- 历史传感器映射:观测依赖整个状态历史时,\(\vec\Theta\) 要对与 \(\eta_k\) 相容的所有状态历史求并。
- 迷宫搜索的 I-map:把历史 I-state 映到(自动机状态, 纬度计数器, \(r\bmod3\))。检查 11.2.1 节意义下的充分性:能否只由 \(\kappa(\eta_k)\)、\(u_k\)、\(y_{k+1}\) 算出 \(\kappa(\eta_{k+1})\)?纬度和 \(r\bmod 3\) 都能这样递推——尽管它远远恢复不了非确定 I-state,却足以执行计划;和 \(2^{|X|}-1\) 个非确定 I-state 相比,规模只有对数级。
- Bug1 的 I-map:记住(模式, 碰撞点, 目前最近点及沿边界走过的距离);同样检查它能否由上一个值、动作与新读数递推更新。
- 队伍成员的三种标签:每个阴影分量对每个队伍记「肯定没有 / 可能有 / 肯定至少一个」;推广本节的标签规则——注意「肯定至少一个」在分裂时只能变成「可能有」。
- 用更少的边造出需要 \(k\) 个追捕者的环境:保留 3-可分的递归结构,但把每个走廊的「钩子」做得更省边。
- (实现)2D 网格上的概率被动定位:本页「概率定位」图就是一个实现,可以对照它的 (12.20)–(12.22) 写法。
- (实现)12.1.3 的精确值迭代:本页 POMDP 图的 α-向量回溯就是一个实现;试着加大 \(K\)、\(\Theta\)、\(\Psi\),看 α-向量和终端 I-state 个数怎样增长。
- (实现)在 \(\mathcal{I}_{ndet}\) 上做网格定位的图搜索:本页「主动定位」图在可达 I-state 上做了最坏情况值迭代;可以尝试启发式(如 I-state 大小)来加速。
- (实现)Bug1、Bug2、VisBug(无限半径):本页实现了前两个;VisBug 可以从「深度不连续点」叠加出发。
- (实现)网格定位的概率 I-state:同第 22 题。
- (实现)12.3.4 节的 GNT 方法:本页 GNT 图用「反射顶点编号间隙」来检测四种事件,可以作为起点。
- (实现)简单多边形中单追捕者的追逃算法:本页追逃图在网格近似上搜索(位置, 标签)图;精确版本需要用拐点射线与双切射线做单元分解。
- (实现)挤压零件算法:本页挤压图实现了贪心反向搜索与前向对齐。
脚注:原书笔误
以下每一条都对照原书 PDF 的原页核对过(页码为书中页码),能用数值核对的都在参考代码里有对应的检查。
1 第 644 页例 12.1:原书写「in the final state, \(x_5\), the robot is at position 1 facing west」。按紧挨着的 (12.18) \(X_5(\eta_5)=5^{\leftarrow}\),应为位置 5 朝西(参考代码第 4 项)。↩
2 第 642 页 (12.13):这只是一个记号示例,但它与模型不相容:\(u_2=R\) 没动(\(y_3=0\))说明转身后面对的方向被挡住,紧接着的 \(u_3=F\) 朝同一方向,必然也不动,所以 \(y_4=1\) 不可能——\(X_5(\eta_5)=\emptyset\),与地图无关(参考代码第 4 项)。↩
3 第 653 页:原书写「\(P(y_{k+1}|x_{k+1},\eta_k,u_k)\) is not given because the sensor mapping also depends on \(x_{k-1}\)」。在这个下标里观测 \(y_{k+1}\) 依赖的是 \(x_{k+1}\) 和 \(x_k\),应为 \(x_k\)(紧接着的 (12.20) 把下标整体前移一位,那里才是 \(x_{k-1}\))。同一段说 \(P(x_{k-1}|\eta_{k-1},u_{k-1})\)「由 (11.38) 给出」也不够准确:它就是上一阶段的概率 I-state(动作 \(u_{k-1}\) 不影响 \(x_{k-1}\))。都是小问题。↩
4 第 639 页(疑似笔误):原书说近似值迭代在采样点上的初始值 \(G^*_F\)「is obtained by (12.6)」。(12.6) 是非确定情形的终端代价;这里是概率 I-空间,对应的应是 (12.4) \(\vec l_F(\eta_F)=\sum_{x_F}P(x_F|\eta_K)l_F(x_F)\)。12.1.2 节的值迭代「用 (12.6) 初始化」则是对的。↩
5 第 662 页:原书写「If the result is \(r(\tilde u'_k)=1 \bmod 3\) after forming a loop, then the robot traveled counterclockwise. If the result is \(r(\tilde u'_k)=2\bmod 3\), then the robot traveled clockwise」。按它自己前面的定义,四次右转(顺时针)\(r=+4\equiv1\),四次左转(逆时针)\(r=-4\equiv2\pmod 3\),所以两句写反了:\(\equiv1\) 是顺时针,\(\equiv2\) 是逆时针(参考代码第 9 项;迷宫图在闭合时也会显示)。↩
6 第 674 页迷路的牛:原书把加倍的螺旋搜索说成「left one unit, right one unit, left two units, right two units, left four units, and so on」,并说竞争比是 9。若按字面执行(每个距离左右各走一次再加倍,折返点 −1, +1, −2, +2, −4, …),门刚好在右侧某个折返点 \(2^k\) 外面时,走过的距离是 \(13\cdot2^k-4\),竞争比趋于 13。竞争比为 9 的最优策略是每次换方向都把离起点的距离加倍:折返点 1, −2, 4, −8, …(即 \((-2)^i\)),这也正是图 12.26b 与习题 8 的「doubling spiral」(参考代码第 11 项;迷路的牛图里可以直接比较)。↩
7 第 671–672 页:正文说「The TangentBug strategy will be described here and is illustrated in Figure 12.24」,而图 12.24 的图注是「An illustration of the VisBug strategy with unlimited radius」。两者不一致(小问题;无限半径时两种策略的路径很相近)。↩
8 第 684 页 EM:原书写「The maximization step involves selecting an \(\hat e_i\) that minimizes (12.30)」,紧接着的公式却是 argmax;末尾又说反复迭代「result in a kind of gradient descent that arrives at a local minimum in E」。EM 是在最大化期望似然,应为「maximizes」和「局部爬升到局部最大」(措辞问题;本页正文已按最大化改写)。↩
9 第 697 页:原书写「Each motion command \(\mu_i\) for \(1\lt i\lt k\) must terminate with an I-state \(\eta\in P(\mu_{i+1},G_{i+1})\)」。\(\mu_1\) 同样必须终止在 \(\mu_2\) 的原像里,下标范围应为 \(1\le i\lt k\)(小问题)。↩
10 第 639 页:原书写「the cost-to-come is piecewise linear and convex [86]」。[86] 说的是最优值函数(对应 cost-to-go,不是 cost-to-come)分段线性且凸——那里用的是回报最大化;改用代价最小化时,cost-to-go 是一组线性函数的最小值,分段线性且凹(POMDP 图里的下包络就是这样)。↩
11 第 704 页:前面定义相对角 \(\alpha=u-x\),(12.37) 却写 \(s(\alpha)=f(x,u)-u\),即挤压后用的是 \(x'-u\) 的约定,正负号与 \(\alpha\) 的定义相反;按 \(\alpha=u-x\) 一致的写法应为 \(s(\alpha)=u-f(x,u)\)。由于对称这不影响结论;本页的挤压图统一使用 \(\varphi=x-u\)。另外 (12.40) 里的 \(\beta_{i-1}\) 书中没有定义。↩
12 第 707 页习题 1:原书写「For the environment in Figure 12.1a」。图 12.1 是导出 I-空间组件的表格,没有 (a);这里指的是网格地图图 12.2a。↩
13 第 710 页习题 16(疑似):要求「Develop versions of (12.8) and (12.9) for state-nature sensor mappings」,但 12.1.2 节的 (12.8)(12.9) 本来就是在「状态-自然传感器映射」的假设下写的。题意可能是别的映射(例如状态传感器映射或随时间变化的映射)。同页习题 5 没有指明真实环境,答案依赖于它(参考代码第 8c 项)。↩
注 其它拼写小错:第 655 页「Guassian」(应为 Gaussian)。↩