博文
读书笔记——SSRP，一种解决PRM中窄道问题的方法
|||
本文作为论文Finding Narrow Passages with Probabilistic Roadmaps: The Small-Step Retraction Method的阅读笔记。
我从这篇文章中得到的第一个有趣信息是关于解决窄道问题方法的分类。作者把这些方法分成两大类：过滤（filtering）和收回（retraction），并给出了解释：过滤策略在C-Space中过采样，然后通过估计每一个无碰撞位姿位于窄道中的可能性来确定该位姿成为里程碑（milestone）的概率。典型例子就是高斯采样策略和桥测试策略。收回策略将一些碰撞位姿移出碰撞区域，利用它们引导生成里程碑。典型例子有不少，本文就算其中一个。
本文提出的新方法叫小步收回（small-step retraction）。为什么叫“小步”呢？因为它只将那些几乎没有碰撞的位姿收回到自由空间中。什么又是“几乎”没有碰撞呢？“收回”又是怎样的一种操作呢？莫急，咱们先看看小步收回的主要步骤：预先计算机器人或障碍物的“瘦化（thinned）”几何模型，然后利用这些瘦化模型建立一张地图，最后通过将碰撞空间中的一部分位姿收回，从而使它们脱离碰撞。瘦化，顾名思义，就是将原来的几何模型收缩，使当前的几何模型包含于原来的几何模型。为什么要瘦化呢？注意，本文的题目已经说明了它的主要内容是针对窄道问题的，试想，如果将障碍物和机器人都进行瘦化，窄道当然会变宽。这就是本文的中心思想！收回，是一种修复操作，用于将不在路径上不在自由空间内的部分拉回自由空间。为什么要收回呢？理由很简单，因为先前构建地图时使用的是“减肥”之后的障碍物和机器人，不是它们的本来面目，因而在这种地图上找到的路径往往无法直接使用，这时，收回路径上的某些部分就起到了修复路径的作用。设原始的自由空间为F，瘦化障碍物和机器人之后得到的自由空间为$F^{*}$ ，称作膨胀的（fattened）自由空间，$F^{*}$ 是F的超集。F中的窄道在$F^{*}$中变宽，从而使得在$F^{*}$中连通一幅地图更容易。但是，有些通道（passage）原本在F中并不存在，由于自由空间的膨胀，这些通道出现在$F^{*}$中，我们称之为假通道（false passage）。与之对应，如果有些通道原本就在F中，$F^{*}$中这些通道应该变得更宽，我们称之为真通道（true passage）。假通道是无法修复的，试想，如果一个通道原本并不存在，那么，不管怎样修复，在F中通道总是不存在的，所有的修复都将是徒劳；而真通道是可以修复的，因为真通道在F中原本就是存在的，瘦化机器人和障碍物后，真通道会变宽，规划路径会更方便，然后修复在$F^{*}$ 得到的路径，使之能够适用于F。现在你理解什么叫做“几乎”没有碰撞了吗？是的，那些只穿过真通道的路径就是几乎没有碰撞的路径，因为就算这些路径没有完全位于F中，它也不会差到哪里去，毕竟机器人和障碍物的瘦化程度非常小，路径如果有碰撞，也只是刺入障碍物一点点而已。
如果你了解高斯采样和桥测试，那么你一定已经知道了何为过滤策略。但是，收缩策略好像稍微晦涩一些。没关系，咱们先看几个实验现象。
第一个实验场景如下图所示：
其中，机器人R是一个半径为r的小圆盘，s和g分别是起始点和目标点，锯齿形窄道宽度为w。上图表示的是工作空间，而它的位姿空间和工作空间形状非常相似，不同之处在于位姿空间中的窄道宽度应为w-2r，因为位姿空间中的机器人只是一个点，障碍物的宽度则应该加上圆盘机器人的半径r。为了考察规划时间与窄道宽度之间的关系，作者定义了一个收缩因子（shrinking factor）：$\alpha= 2r/ \left (1-\varepsilon \right )w$，其中，$\varepsilon=0.005$，w为常数。显然，收缩因子与r的大小成正比。如果将r逐渐减小，C-Space中窄道的宽度w-2r应该不断增加，窄道变宽了，规划时间自然应该减小。于是我们分析，规划时间随着$\alpha$的减小不断减小。实验结果印证了我们分析的正确性：
其中，左图给出了不同收缩因子对应的规划时间。作者使用SBL作为规划器，对于每一个r，SBL用不同的种子运行100次，每次直至找到路径后才停止，然后求出平均规划时间。当$\alpha=1$时，对应的$r= \left (1- \varepsilon \right )w/2$为最大半径，这时的窄道宽度$0.005 \times w$
为最小。当$\alpha=0.3$时，窄道宽度$0.7 \times w$为最大。右图是左图的函数图。这个实验结果正常人都能想得到，而且分析起来也相当简单，无非就是增加窄道宽度能够使落入其中的采样点数目增加。而这恰恰是本文SSRP方法的核心思想！
第二个实验的场景如下图所示：
其中，机器人R依然是半径为r的圆盘，两条宽度分别为$w_{1}$
和$w_{2}$
的窄道分别位于工作空间的上方和下方，$s_{i},g_{i},i=1,2,3$分别是三组不同的起始点和目标点。$s_{3},g_{3}$距离上下两个窄道的距离相同，$s_{1},g_{1}$则是距离上方窄道最近的一对点。现在，将SBL作为规划器，运行100次，分别记录穿过上方窄道和下方窄道的路径数，得到如下结果：
可以看出，如果在$s_{1},g_{1}$之间找到100条路径的话，有88条穿过上方的窄道，有12条穿过下方的窄道——相差悬殊；如果在$s_{3},g_{3}$之间找到100条路径，有52条穿过上方的窄道，48条穿过下方的窄道——数量相当！隐隐约约能够感觉到SBL好像更倾向于穿过离起始点和目标点比较近的通道。现在使用相同的场景再来做一个实验，但是这次只考虑$s_{3},g_{3}$这么一对点。设$w_{2}=\beta \times w_{1}$，其中$\beta \geq 1$。尝试一系列递增的$\beta$，对每一个$\beta$都运行100次SBL，考察随着$\beta$的变化，穿过上方窄道和下方窄道的路径数目的变化情况，得到如下结果：
随着$\beta$的不断增大，$w_{2}$不断增大，对于距离上方和下方两条窄道距离相同的$s_{3},g_{3}$来说，更加宽阔的下方窄道无疑更受欢迎。从上图可以看出，当$\beta=1.5$时，所有的路径都从下方窄道中穿过，上方窄道被完全“冷落”。
第二个实验场景的两个实验说明，如果空间中存在多条窄道，SBL倾向于穿过最容易的一条。现在想想，这些窄道有真有假，那么，SBL找到的路径更倾向于穿过真通道还是假通道呢？答案是真通道。在$F^{*}$中，真通道的宽度往往大于假通道。原因很简单，一个原本就存在于F中的通道，一个是原本不存在于F中的通道，当机器人和障碍物经过相同的瘦化后，原本就有的通道应该更宽一些——因为真通道有基础，“起点”比假通道高！因此，$F^{*}$中的真通道比假通道更容易穿过。
我们暂时不管障碍物和机器人是怎样被瘦化的，权且认为它们已经“减肥”成功。现在来看作者提出的SSRP算法。这个算法又包含了两个算法：乐观算法（Optimist）和悲观算法（Pessimist）。它们都以SBL为基础，在执行过程中都会调用SBL算法。乐观算法执行速度快，被SSRP首先调用，但是不可靠；悲观算法执行速度较慢，但是更可靠，被放在乐观算法之后调用。令F表示自由空间，$F^{*}$表示膨胀的自由空间，$F \subset F^{*}$ ，$\partial^{*} F = F^{*} \setminus F$称为F的膨胀边界（fattened boundary）。我们先来看看乐观算法：
其中，M表示原始机器人和障碍物的几何模型，$M^{*}$ 表示瘦化之后的模型。乐观算法调用SBL，在$F^{*}$中找一条路径$\tau^{*}$。显然，乐观算法认为$\tau^{*}$穿过的都是真通道，并尝试修复$\tau^{*}$。这也是乐观算法名字的来历：认为SBL找到的路径都穿过真通道，等SBL找到一条完整路径后再尝试修复这条路径。修复$\tau^{*}$就是将路径$\tau^{*}$上位于F的膨胀边界$\partial^{*}F$中的部分移回F中。首先修复点，然后修复边。怎样修复点？看下面的算法：
Repair-Conf用于修复路径$\tau^{*}$上位于$\partial^{*}F$ 内的每个里程碑c。该函数在中心为c、半径为$\rho$ 的球$B \left (c, \rho \right )$ 中采样，试图为c寻找一个合适的替代点$c^{'}$ 。$\eta >1$ ，半径$\rho$起初较小，然后逐渐增大。如果Repair-Conf在迭代K次之后返回失败，我们就认为路径$tau^{*}$是无法修复的，即，任何一个点修复失败，乐观算法都会失败。如果乐观算法成功，就用返回的$c^{'}$ 代替里程碑c。路径$\tau^{*}$上的所有里程碑都被修复后，就该修复路径上的每一条与$\partial^{*}F$ 相交的边e了。修复边无非就是修复该边上的若干个点，所以，修复边依然要调用Repair-Conf，但是要将Repair-Conf(c, M)中的c赋值为边e的中点。同样，如果任何一条边修复失败，乐观算法都会失败。由于$F^{*}$中可修复的路径都靠近F的边界，那么，半径$\rho$不用太大应该就能找到合适的$c^{'}$ ，所以我们将K值设得较小，论文中取K=100。
乐观算法认为路径总是可以被修复的，但是，现实往往与之相反，即$SBL \left (s, g, M^{*} \right )$找到的路径穿过了假通道。下图示意了在2维C-Space中，路径穿过假通道究竟是怎样的一幅情景：
白色区域是自由空间F，浅灰色和深灰色区域是碰撞空间（collision space），其中浅灰色区域为F的膨胀边界$\partial^{*}F$。s是起始点，g是目标点，s和g的直线相距很近，却被中间的障碍物隔开。SBL要在s和g之间寻找一条路径。根据前面提到的实验现象，SBL倾向于找到一条最容易的路径。从图上可以看出，在$F^{*}$中，从s到g有两条路可走：一条是从s出发上行，穿过上方的窄道，再下行至g；另一条是从s出发，直接右行，穿过$\partial^{*}F$到达g。如果按照之前提到的实验结果进行推测，SBL显然更倾向于走第二条路。然而，第二条路径要穿过的窄道就是之前提到的假通道，而假通道是无法修复的。因此，如果只依靠乐观算法，SBL可能无法找到F中的可用路径。这时，作者提出了悲观算法。乐观算法是在SBL找到一条完整路径后再对此路径进行修复，而悲观算法则表现得相当谨慎：一旦发现采样点位于$\partial^{*}F$，立刻将其修复。这只需稍稍修改SBL算法即可做到，即每当采样一个新的位姿c，都按以下步骤执行：
SBL的一大特点就是延迟碰撞检测，即直到找到一条完整路径，SBL才对路径上的每一条边进行碰撞检测。悲观算法不改变SBL的这一特点，它不会在立即修复点之后紧接着立即修复边。事实上，它根本就不修复边，也不修复任何一条穿过假通道的路径。对于每个在F以外的采样点c而言，悲观算法都对其进行了两次碰撞检测：一次出现在悲观算法的步骤1，一次出现在悲观算法的步骤2，更精确的位置是Repair-Conf的步骤2.2。如果发现c位于$\partial^{*}F$中，则将其修复。然而，就算c被修复，它也不一定出现在最终的路径上，因此，悲观算法用于每个采样点的平均时间比普通SBL和乐观算法都多。不过，这恰恰保证了悲观算法的可靠性：它避免了乐观算法中产生的致命错误，使每一个采样点被及时收回到自由空间F中；同时，由于产生了较好的分布，使得它构建的地图规模比普通SBL小。
作者力图实现乐观算法和悲观算法的优势互补，于是设计出small-step retraction planner即SSRP算法，如下所示：
乐观算法速度快，但是生成的路径可靠性低；悲观算法略慢，但是可靠性高。注意，悲观算法速度虽不及乐观算法，但是依旧比普通的SBL快很多。如果乐观算法执行了N次都无法找到可用路径，则调用悲观算法。经过实验，发现如果乐观算法连续失败几次，那么它很可能会一直失败下去，所以可以将N的值设小一些，论文中取N=5。由于乐观算法速度比悲观算法快很多，所以就算乐观算法N次全部失败，对SSRP总的规划时间也没有太大影响。
至此，SSRP算法就介绍完了。现在回过头来看看论文如何瘦化障碍物和机器人模型。为了读懂这部分，我花了较多的时间，令人沮丧的是，依然没有完全搞懂。论文中提到这个瘦化方法来源于论文Near Parallel Computation of MAT of 3D Polyhedra，但是我google了很久都没找到这篇文章，因而无法深入了解。这篇博客旨在让大家了解SSRP的乐观算法、悲观算法和两者的优势互补，因而不打算把瘦化模型这种与图形学和计算几何联系密切的理论讲得十分透彻。下面来分享一点我本人对瘦化过程的理解。
相信大家已经知道什么是中轴（medial axis，MA）了。论文中采用的瘦化方法就利用了这一概念。首先，每一个物体都被建模为多面体，则任一个物体X的中轴MA可由它的子中轴（sub-MA）组合而成。每个子中轴都由一个控制边界元素（governing boundary element）（包括面，边和顶点）提供。每个子中轴都是由图形硬件独立计算得出，与其他子中轴无关。论文中的瘦化方法只用到了由面提供的子中轴，所以下面描述由物体X的各个面控制的子中轴的建立和组合。先看一幅建立子中轴的示意图：
图a给出了一个长方体X，并且以该长方体底面e为控制元素。现在考虑X的其他5个面，它们部分或全部位于e的支撑面（supporting plane）的内侧（inward side）。这里我要声明，我并不知道支撑面的确切定义，也没找到能够解释它的资料，不过，如果将X想象为放在一张桌子上，那么e的支撑面应该就是桌子平面。X的其他5个面都位于桌面以上，于是就说成是位于支撑面的内侧。设其他5个面的任意一个为$e^{'}$，则每个$e^{'}$和e之间都有一个平分面，该面上的所有点到$e^{'}$和e的距离相等。例如，在图a中，设$e^{'}$为顶面，则$e^{'}$和e的平分面就是底面和顶面之间的中位面，该面上的所有点到底面e和顶面$e^{'}$之间的距离相等。再比如，设$e^{'}$为底面右侧的直立侧面，则$e^{'}$和e的平分面就是底面和侧面之间的角平分面。在图形缓存中用不同的颜色渲染这些平分面即可得到可见部分（visible portions），如图b所示。现在沿着e的法线观察e的所有平分面，则可见部分就构成了由e控制的子中轴，如图c所示，这时，缓存中的内容就变成了子中轴。
一旦将X的所有面控制的子中轴全部建好，就要将它们组合在一起形成X的中轴MA。图c所示的棱台是由X底面e控制的子中轴，根据对称性，X的顶面也有类似形状的子中轴，只不过是一个倒过来的棱台。这两个棱台有一个公共面，即图c所示的红色面。更一般地，考虑两个子中轴，它们分别由e和$e^{'}$控制，则这两个子中轴必有一个公共面，这个面就是e和$e^{'}$的平分面。现在，将X中每一对e和$e^{'}$都按照它们的公共面对齐，就得到X的MA。
有了MA，现在来考虑怎样瘦化模型。先来介绍一个名词：MA球（MA ball）。你应该已经知道（如果不知道，去看我的另一篇介绍MAPRM的博客），3D物体X的MA其实是一些包含于X内部的局部最大球（locally maximal ball）的中心的轨迹。MA上的点连同该点对应的局部最大球的半径定义了中轴转换（medial-axis transform，MAT）。而这些局部最大球就叫做MA球。为了瘦化物体X，我们需要减小MA球的半径，然后建立由这些缩小后的球重建物体模型。采用不同的减小半径方法会得到不同的结果。例如，我们可以将MA球半径乘以一个常数$\beta <1$，也可以将所有MA球的半径减去一个常数$\delta$，并删除所有半径小于$\delta$的MA球。下图的a和b分别示意了这两种方法：
在这篇论文中，作者采用了第二种方法，因为它得出的结果更容易计算。设$\delta = \alpha \times r_{max}$，其中$r_{max}$是最大MA球的半径，常数$\alpha < 1$称为瘦化因子（thinning factor），在该论文中，$\alpha \approx 0.2$。
对于由面e控制的子中轴，令P表示将e的支撑面向内侧平移$\delta$得到的平面。我们将子中轴位于P内侧的部分投影到P上。X的瘦化模型的边界就由它的所有面控制的所有子中轴的投影面构成。下面看一个2D的示意图，其中X是一个用虚线画出的矩形，e是它的底边。e控制的子中轴包括三条边，它们被全部或部分地投影到直线P上：
注意，上图中由e控制的子中轴投影到P后好像产生了两个间隙，即子中轴投影后变成了三条共面线段，如果推广到3D情况下，则是三个共面面。这是由投影技术导致的。因此，大部分的物体在瘦化以后都会比原模型多许多多边形面。不过，这对于使用包围体分层方法（bounding-volume hierarchy approach）的碰撞检测器的执行时间影响不大。来看一下瘦化之后的物体模型：
最后一点需要注意的是，这篇论文将物体的瘦化过程看作预计算（pre-computation）过程。这意味着瘦化过程的时间不计入规划的总时间。作者给出了几个理由：首先，不论物体的位置和方向如何，对于每个物体而言，瘦化过程只需执行一次，不需要为任何一个新的规划问题重复执行；不仅如此，物体模型早在被用于运动规划之前很长时间就已经可用，这为预计算留下了很多时间；最后，生成一个物体的几何模型要比计算它的MA多花很多时间，因此将瘦化作为预计算不会带来很大影响。事实上，很多计算都被作为预计算。例如，很多规划器都假设几何模型使用多边形网格（polygonal meshes）来描述物体表面。如果几何模型不是以这种形式出现的，就需要从给出的描述形式中提取多边形网格，这一过程就常常作为预计算。与此类似，如果一个规划器使用了BVH碰撞检测器，那么计算包围体层次就被当作预计算，因为对于每个物体它只需进行一次。不过，增加预计算也有弊端。在某些机器人应用中，物体模型事先是不可用的，而且感应-建模-规划-执行（sensing-modeling-planning-execution）序列必须尽快执行，增加任何计算都会降低机器人的反应能力。即使时间不是关键因素，我们依然必须存储预计算结果并在随后几何形状改变时更新它们。幸运的是，在大部分情况下，论文使用的规划器能够在充分瘦化机器人的同时保持障碍物不变，这可以省去相当多的更新几何模型带来的开销。
实验和总结部分略过。其实我也不想略过，因为它们都是很重要的部分，而且给出了很多算法的实现细节和实验对比结果。不过，我相信当你看懂我写的博客时，再看实验和总结部分应该不会遇到太多困难。这篇“长文”就此完成！
https://blog.sciencenet.cn/blog-795645-634061.html
上一篇：读书笔记——MAPRM，在自由空间的中轴上采样
下一篇：读书笔记——MLDP，在PRM中解决窄道采样问题
我从这篇文章中得到的第一个有趣信息是关于解决窄道问题方法的分类。作者把这些方法分成两大类：过滤（filtering）和收回（retraction），并给出了解释：过滤策略在C-Space中过采样，然后通过估计每一个无碰撞位姿位于窄道中的可能性来确定该位姿成为里程碑（milestone）的概率。典型例子就是高斯采样策略和桥测试策略。收回策略将一些碰撞位姿移出碰撞区域，利用它们引导生成里程碑。典型例子有不少，本文就算其中一个。
本文提出的新方法叫小步收回（small-step retraction）。为什么叫“小步”呢？因为它只将那些几乎没有碰撞的位姿收回到自由空间中。什么又是“几乎”没有碰撞呢？“收回”又是怎样的一种操作呢？莫急，咱们先看看小步收回的主要步骤：预先计算机器人或障碍物的“瘦化（thinned）”几何模型，然后利用这些瘦化模型建立一张地图，最后通过将碰撞空间中的一部分位姿收回，从而使它们脱离碰撞。瘦化，顾名思义，就是将原来的几何模型收缩，使当前的几何模型包含于原来的几何模型。为什么要瘦化呢？注意，本文的题目已经说明了它的主要内容是针对窄道问题的，试想，如果将障碍物和机器人都进行瘦化，窄道当然会变宽。这就是本文的中心思想！收回，是一种修复操作，用于将不在路径上不在自由空间内的部分拉回自由空间。为什么要收回呢？理由很简单，因为先前构建地图时使用的是“减肥”之后的障碍物和机器人，不是它们的本来面目，因而在这种地图上找到的路径往往无法直接使用，这时，收回路径上的某些部分就起到了修复路径的作用。设原始的自由空间为F，瘦化障碍物和机器人之后得到的自由空间为$F^{*}$ ，称作膨胀的（fattened）自由空间，$F^{*}$ 是F的超集。F中的窄道在$F^{*}$中变宽，从而使得在$F^{*}$中连通一幅地图更容易。但是，有些通道（passage）原本在F中并不存在，由于自由空间的膨胀，这些通道出现在$F^{*}$中，我们称之为假通道（false passage）。与之对应，如果有些通道原本就在F中，$F^{*}$中这些通道应该变得更宽，我们称之为真通道（true passage）。假通道是无法修复的，试想，如果一个通道原本并不存在，那么，不管怎样修复，在F中通道总是不存在的，所有的修复都将是徒劳；而真通道是可以修复的，因为真通道在F中原本就是存在的，瘦化机器人和障碍物后，真通道会变宽，规划路径会更方便，然后修复在$F^{*}$ 得到的路径，使之能够适用于F。现在你理解什么叫做“几乎”没有碰撞了吗？是的，那些只穿过真通道的路径就是几乎没有碰撞的路径，因为就算这些路径没有完全位于F中，它也不会差到哪里去，毕竟机器人和障碍物的瘦化程度非常小，路径如果有碰撞，也只是刺入障碍物一点点而已。
如果你了解高斯采样和桥测试，那么你一定已经知道了何为过滤策略。但是，收缩策略好像稍微晦涩一些。没关系，咱们先看几个实验现象。
第一个实验场景如下图所示：
第二个实验的场景如下图所示：
第二个实验场景的两个实验说明，如果空间中存在多条窄道，SBL倾向于穿过最容易的一条。现在想想，这些窄道有真有假，那么，SBL找到的路径更倾向于穿过真通道还是假通道呢？答案是真通道。在$F^{*}$中，真通道的宽度往往大于假通道。原因很简单，一个原本就存在于F中的通道，一个是原本不存在于F中的通道，当机器人和障碍物经过相同的瘦化后，原本就有的通道应该更宽一些——因为真通道有基础，“起点”比假通道高！因此，$F^{*}$中的真通道比假通道更容易穿过。
我们暂时不管障碍物和机器人是怎样被瘦化的，权且认为它们已经“减肥”成功。现在来看作者提出的SSRP算法。这个算法又包含了两个算法：乐观算法（Optimist）和悲观算法（Pessimist）。它们都以SBL为基础，在执行过程中都会调用SBL算法。乐观算法执行速度快，被SSRP首先调用，但是不可靠；悲观算法执行速度较慢，但是更可靠，被放在乐观算法之后调用。令F表示自由空间，$F^{*}$表示膨胀的自由空间，$F \subset F^{*}$ ，$\partial^{*} F = F^{*} \setminus F$称为F的膨胀边界（fattened boundary）。我们先来看看乐观算法：
其中，M表示原始机器人和障碍物的几何模型，$M^{*}$ 表示瘦化之后的模型。乐观算法调用SBL，在$F^{*}$中找一条路径$\tau^{*}$。显然，乐观算法认为$\tau^{*}$穿过的都是真通道，并尝试修复$\tau^{*}$。这也是乐观算法名字的来历：认为SBL找到的路径都穿过真通道，等SBL找到一条完整路径后再尝试修复这条路径。修复$\tau^{*}$就是将路径$\tau^{*}$上位于F的膨胀边界$\partial^{*}F$中的部分移回F中。首先修复点，然后修复边。怎样修复点？看下面的算法：
Repair-Conf用于修复路径$\tau^{*}$上位于$\partial^{*}F$ 内的每个里程碑c。该函数在中心为c、半径为$\rho$ 的球$B \left (c, \rho \right )$ 中采样，试图为c寻找一个合适的替代点$c^{'}$ 。$\eta >1$ ，半径$\rho$起初较小，然后逐渐增大。如果Repair-Conf在迭代K次之后返回失败，我们就认为路径$tau^{*}$是无法修复的，即，任何一个点修复失败，乐观算法都会失败。如果乐观算法成功，就用返回的$c^{'}$ 代替里程碑c。路径$\tau^{*}$上的所有里程碑都被修复后，就该修复路径上的每一条与$\partial^{*}F$ 相交的边e了。修复边无非就是修复该边上的若干个点，所以，修复边依然要调用Repair-Conf，但是要将Repair-Conf(c, M)中的c赋值为边e的中点。同样，如果任何一条边修复失败，乐观算法都会失败。由于$F^{*}$中可修复的路径都靠近F的边界，那么，半径$\rho$不用太大应该就能找到合适的$c^{'}$ ，所以我们将K值设得较小，论文中取K=100。
乐观算法认为路径总是可以被修复的，但是，现实往往与之相反，即$SBL \left (s, g, M^{*} \right )$找到的路径穿过了假通道。下图示意了在2维C-Space中，路径穿过假通道究竟是怎样的一幅情景：
作者力图实现乐观算法和悲观算法的优势互补，于是设计出small-step retraction planner即SSRP算法，如下所示：
至此，SSRP算法就介绍完了。现在回过头来看看论文如何瘦化障碍物和机器人模型。为了读懂这部分，我花了较多的时间，令人沮丧的是，依然没有完全搞懂。论文中提到这个瘦化方法来源于论文Near Parallel Computation of MAT of 3D Polyhedra，但是我google了很久都没找到这篇文章，因而无法深入了解。这篇博客旨在让大家了解SSRP的乐观算法、悲观算法和两者的优势互补，因而不打算把瘦化模型这种与图形学和计算几何联系密切的理论讲得十分透彻。下面来分享一点我本人对瘦化过程的理解。
相信大家已经知道什么是中轴（medial axis，MA）了。论文中采用的瘦化方法就利用了这一概念。首先，每一个物体都被建模为多面体，则任一个物体X的中轴MA可由它的子中轴（sub-MA）组合而成。每个子中轴都由一个控制边界元素（governing boundary element）（包括面，边和顶点）提供。每个子中轴都是由图形硬件独立计算得出，与其他子中轴无关。论文中的瘦化方法只用到了由面提供的子中轴，所以下面描述由物体X的各个面控制的子中轴的建立和组合。先看一幅建立子中轴的示意图：
一旦将X的所有面控制的子中轴全部建好，就要将它们组合在一起形成X的中轴MA。图c所示的棱台是由X底面e控制的子中轴，根据对称性，X的顶面也有类似形状的子中轴，只不过是一个倒过来的棱台。这两个棱台有一个公共面，即图c所示的红色面。更一般地，考虑两个子中轴，它们分别由e和$e^{'}$控制，则这两个子中轴必有一个公共面，这个面就是e和$e^{'}$的平分面。现在，将X中每一对e和$e^{'}$都按照它们的公共面对齐，就得到X的MA。
有了MA，现在来考虑怎样瘦化模型。先来介绍一个名词：MA球（MA ball）。你应该已经知道（如果不知道，去看我的另一篇介绍MAPRM的博客），3D物体X的MA其实是一些包含于X内部的局部最大球（locally maximal ball）的中心的轨迹。MA上的点连同该点对应的局部最大球的半径定义了中轴转换（medial-axis transform，MAT）。而这些局部最大球就叫做MA球。为了瘦化物体X，我们需要减小MA球的半径，然后建立由这些缩小后的球重建物体模型。采用不同的减小半径方法会得到不同的结果。例如，我们可以将MA球半径乘以一个常数$\beta <1$，也可以将所有MA球的半径减去一个常数$\delta$，并删除所有半径小于$\delta$的MA球。下图的a和b分别示意了这两种方法：
对于由面e控制的子中轴，令P表示将e的支撑面向内侧平移$\delta$得到的平面。我们将子中轴位于P内侧的部分投影到P上。X的瘦化模型的边界就由它的所有面控制的所有子中轴的投影面构成。下面看一个2D的示意图，其中X是一个用虚线画出的矩形，e是它的底边。e控制的子中轴包括三条边，它们被全部或部分地投影到直线P上：
实验和总结部分略过。其实我也不想略过，因为它们都是很重要的部分，而且给出了很多算法的实现细节和实验对比结果。不过，我相信当你看懂我写的博客时，再看实验和总结部分应该不会遇到太多困难。这篇“长文”就此完成！
https://blog.sciencenet.cn/blog-795645-634061.html
上一篇：读书笔记——MAPRM，在自由空间的中轴上采样
下一篇：读书笔记——MLDP，在PRM中解决窄道采样问题
