本文作为论文RESAMPL: A Region-Sensitive Adaptive Motion Planner的阅读笔记。

   这篇论文发表在08年的Algorithm Foundation of Robotics VII上，可见此论文含金量较足。和高斯采样、桥测试一样，它要解决的是位姿空间中存在窄道等困难区域时的路径规划问题。方法的新颖之处如同题目中提到的，这个方法是“区域敏感”的。那么，RESAMPLE到底是个什么方法？

   RESAMPL的大体思路是：首先在位姿空间中随机生成一些采样点，不管是自由还是碰撞，统统留下；然后根据这些采样点建立若干区域（region），下一步就是研究各个区域的性质，看看它们到底是“困难”还是“非困难”。直观上，困难区域碰撞点比较多，非困难区域的自由点比较多。将区域分类的直接用途就是指导后续的采样过程，使困难区域多采样，非困难区域少采样。研究完区域自身的信息，我们再来挖掘区域之间的关系。这里用到的数据结构是图，把每个区域看作图中的一个点，如果两个区域有重叠，则在这两个区域对应的两点之间建立一条边，如此可得到一个区域图（region graph）。区域图有什么用呢？显然，它比普通roadmap的“视野”更开阔，因而可以从宏观上指导全局路径规划。RESAMPL的一个特点就是它既适用于多查询（multi-query）问题，又适用于单查询（single-query）问题，区域图在其中扮演了一个重要角色。下图展示了区域模型的建立、分类和指导后续采样的效果：

   OK，是时候详细了解RESAMPL了！

   首先，我们要了解所谓的“区域”是如何建立的。上文中提到过，我们必须先在位姿空间中生成一些采样点。从这些初始点集中随机选取一个采样点，作为区域的中心，称为该区域的“代表采样点（representative sample）”，再从初始点集中找到距离该中心最近的k个点，称为该区域的“邻近采样点（neighboring sample）”。一个代表采样点和k个邻近采样点就确定了一个区域。需要注意的是，每次从初始点集中选择代表采样点时，该点必须尚未被任何区域包含，而邻近采样点则无此限制。这里的“区域”是一个比较特殊的概念，没有一个明确的半径，完全是由若干点确定的。但是，通过以上的方法确定的所有区域半径都会比较接近。下面给出建立区域的具体算法：

   区域已经建好了，下一步就要为区域“分类”，即分析区域的困难程度。论文中提出了“熵（entropy）”的概念，用于衡量区域中自由点和碰撞点的比例。其实我觉得这个概念纯粹是为了博人眼球的，因为“熵”这个词要比“比例”听上去高端得多！这里稍稍科普一下，熵最初用于衡量一个热力学系统的无序程度，1948年，香农把熵的概念引入信息论领域，用于测量不确定性。“但是在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少”，维基百科如是说。这篇论文并没有明确给出熵的定义，只是给出一个笼统的判断熵高低的规则：如果一个区域的所有采样点都是自由的或者都是碰撞的，我们就认为这个区域具有低熵（low entropy）；如果一个区域中自由点又有碰撞点，则这个区域具有高熵（high entropy）。根据熵的高低，我们把区域分成4类：自由（free），表面（surface），狭窄（narrow）和阻塞（blocked）。其中，自由区域和阻塞区域都是低熵的，表面区域和狭窄区域是高熵的。下图分别表示了区域的建立以及4种不同的区域：

   现在我们就来看看RESAMPL是怎样根据熵来对区域进行分类的。

   对于一个区域，RESAMPL采用多次迭代来计评估它的熵，然后尝试对其进行分类。如果暂时无法分类，就在这个区域中增加一些采样点，并在下一次迭代中继续尝试分类。

   自由区域是最容易区分的，我们计算出该区域中碰撞点所占的比例，或者称之为熵。如果熵足够低，那么这个区域就被认为是自由的。经验表明，其他类型的区域通常不会被这种方法误判为自由区域。如果初始的粗略的采样可以使一个区域中绝大多数的点都是自由的，那么后续的更好的采样依然可以使这个区域中的绝大多数点是自由的。因此，在每次迭代中，我们首先判断该区域是否为自由区域。

   阻塞区域也可以用一种类似的方法判断，即如果该区域中自由点所占的比例，即熵，足够低，则该区域为阻塞区域。然而，仅凭一次迭代往往不足以说明一个区域是阻塞的，这是因为随着采样点的增加，当前的低熵区域可能会是一个潜在的高熵区域。所以，只有多次尝试对该区域进行分类并增加采样点后，才能判断一个区域是否为阻塞区域。

   如果一个区域的子区域具有低熵，则这个区域是表面区域。子区域可以这样定义：设 $c_{F}$ 为父区域中所有自由点的质心， $c_{B}$ 为父区域中所有碰撞点的质心，将 $c_{F}$ 和 $c_{B}$ 作为两个子区域的中心，对于父区域中的每一个点，考察它到两个子区域中心的距离，并将它分配到较近的中心所确定的子区域中。两个子区域确定之后，如果它们都是低熵的，该父区域就被分类为表面区域。

   如果一个区域是高熵的，且无法被划分为两个低熵的子区域，则这个区域是狭窄区域。同阻塞区域一样，狭窄区域容易被误判，因此我们多次尝试对该区域进行分类并增加采样点后，才能判断该区域是否为狭窄区域。

   如果一个区域无法被上述方法判别，就认为它是表面区域。经验表明，对于无法判别的区域而言，表面区域是最好的归类选择。对一个区域进行分类的算法如下所示：

   区域也建立了，分类也成功了，下面就要进行后续的采样和规划了。我们先来看一个概念，即上文中提到的区域图。令每个区域对应一个点，重叠的区域之间有一条边，就构成了区域图。根据连接的区域类型，为每条边赋予权值。利用区域图，我们可以获取区域路径（region paths）来辅助解决单查询规划问题，也可以通过改进区域图，辅助解决多查询规划问题。那么，区域图应该怎样改进呢？一种办法是把相邻的两个类型相同的区域合并，或者把分类情况不明晰的区域拆分。如果两个类型相同的区域合并之后得到的父区域与两个子区域的类型相同，则这两个区域是可合并的。区域合并（region merging）可以减少区域数量，并得到更大的与子区域具有相同类型的区域，这对基于区域类型进行采样点增加或删除是很重要的。

   对于多查询规划，我们希望利用一个能够充分反映位姿空间连通性的roadmap解决多种查询。上述根据区域图进行区域合并的办法可以有效地提高后续采样的效率，在困难区域生成更多的采样点，得到更能反映自由空间连通性的roadmap。同时，在后续采样时，我们可以对不同类型区域内的采样点进行“筛选”：以一个较低的概率 $p_{F}$ 保留自由区域中的点，以一个较高的概率 $p_{S}$ 保留表面区域中的点，同样以一个较高的概率 $p_{N}$ 保留狭窄区域中的点。对于阻塞区域中的采样点，我们不予保留。这样的策略能够使roadmap变得“小而精”。同时，通过区域分类，我们知道了哪些区域是困难区域，就可以利用一些特定的方法来增强这些困难区域，例如利用RRT快速扩展的特性，使之在困难区域迅速生长，从而达到增强困难区域采样密度的目的。

   对于单查询规划，我们不必完全掌握位姿空间的拓扑结构，而是本着“够用就好”的态度，希望尽量少探索与本次规划路径无关的区域，以提高规划效率。这时，区域图就派上用场了。我们可以先在区域图中获取一条连接起始区域和目标区域的区域路径，用以宏观指导实际路径的规划。

   现在的问题是，怎样获取区域路径呢？首先，我们要确定起始区域和目标区域：起始位姿和目标位姿能够连接到的最近非阻塞（自由，表面，狭窄）区域分别作为起始区域和目标区域。然后，根据区域图，在起始区域和目标区域之间找到一条最短区域路径。由于区域图的边具有不同权值，使最短区域路径能够尽可能地避开阻塞区域，而最终出现在路径中的阻塞区域也可以采用重新分类的办法将它们变成连续的非阻塞区域。

   既然已经有了区域路径，现在考虑如何从区域路径中提取实际路径（actual path）。在区域图中，如果一条边连接的是两个自由区域，那么实际路径是容易提取的。然而，如果一条边连接的是两个困难（表面，狭窄，阻塞）区域，提取实际路径就有难度了。论文中给出了一种方法，用于提高从区域路径中提取实际路径的能力：设区域路径上两个连续的区域为 $R_{i}$ 和 $R_{i+1}$ ，如果它们都是自由区域，则不进行特殊处理；否则，在提取实际路径的时候，把区域路径上与 $R_{i}$ 和 $R_{i+1}$ 相邻的非阻塞区域也包含进来，这样就增加了自由点的数量，使得提取实际路径的成功率更高。那么，实际路径到底是怎样提取的呢？很简单，对两个或更多区域中的每个采样点，找到距它的最近的k个点并用局部规划器连接即可。可见，区域路径起到了一个宏观指导规划的作用。

   OK，就这样，一个人深夜在实验室，完成了2014年的第一篇博客！加油，光明就在不远处！