本文作为论文Sampling-Based Motion Planning Using Predictive Models的阅读笔记。

   个人感觉，将机器学习应用到运动规划是个大趋势，可是，这方面的论文数量却是少之又少，实在令人费解。偶然间读到了University of Massachusetts-Amherst的两个牛人Brendan Burns和Oliver Brock写的论文，才发现人家早在2004年就已经有利用机器学习解决运动规划问题的研究成果了。

   若抛开运动规划不谈，我们通常用机器学习解决分类问题，其实也就是一个预测问题。我们希望找到一个函数 $f\left(x \right )\rightarrow y$ ，给定一个输入x，就能判断，或者说预测出x的类别，输出y就是分类结果。对于监督学习而言，我们不仅要给定一个训练样本集，还要给出各个样本所属的类别，这一特点非常适合于解决位姿空间中的运动规划问题。在位姿空间中，每一个状态已知的采样点都被当做一个类别已知的训练样本，碰撞点的类别标记为-1，自由点的类别标记为1，分类结果的输出值在 $\left[-1,1 \right ]$ 之间，最终得到的类别是将y向两极离散（“两极离散”是我自己造的名词，说白了，就是看看y值更偏向哪边： $y<0$ ，则y偏向-1； $y>0$ ，则y偏向1； $y=0$ ，则偏向不确定）后得到的结果。

   这篇论文的整体思路就是先在位姿空间中生成少量的采样点，不论是碰撞点还是自由点，全部保留，把这些点当做训练样本集。然后利用局部加权回归（locally weighted regression，LWR）建立回归方程，这个方程就是位姿空间的近似模型（approximate model），将采样点输入方程，输出就是近似模型预测的采样点的状态。但是，回归总是有误差的，因此，为了使误差最小，论文采用主动学习（active learning）的方法选取采样点。回归误差比较大的区域是近似模型没有学习好的区域，这些区域往往是困难区域。主动学习选取采样点的标准恰好是能否减小回归误差，因此，利用主动学习指导采样，能够重点增强困难区域的采样密度。不仅如此，通过结合局部加权回归与主动学习两种方法，论文还提出了预测边有效性的算法，使得该论文提出的方法可以结合延迟碰撞检测的思想并用于单查询规划。

   其实，依我看，这篇论文最突出的贡献应该是应用创新。它把主动学习和局部加权回归用于指导位姿空间中的采样过程。有兴趣的读者可以查阅论文Active Learning with Statistical Models，这篇论文完整地给出了用主动学习的方法降低局部加权回归误差的一套理论，恰好也是Brendan Burns和Oliver Brock的最主要参考文献。

   局部加权回归（下文简写为LWR），顾名思义，是一种回归方法，它的特殊之处就在于四个字：局部加权。给定一个状态未知的采样点，LWR利用该点附近的采样点适配出一个曲面，以此预测该采样点的状态。为了强调“局部”，LWR给出了一个距离加权函数，即：

$w\left\(x,x_{i}\right\)=e^{-k\left\(x-x_{i}\right\)^{2}}$

该函数是一个高斯函数，其中，x是待预测点， $x_{i}$ 是训练样本点。可以看出，距离x越近的样本点，其权重越大，从而对x的影响越大。k是平滑参数，它决定了高斯函数的“宽度”。关于k的选择，在论文Active Learning with Statistical Models中有比较详细的谈论，这里就不展开了。既然给定了训练样本集和待预测点，就可以估计出高斯函数的均值，如下：

其中，x是待预测点， $x_{i},y_{i}$ 是训练样本点的坐标和状态。估计出训练样本集的方差如下：

协方差如下：

条件方差如下：

利用上面的这些参数，我们可以计算出输出的期望值：

$\hat{y}=\mu_{y}+\frac{\sigma_{xy}}{\sigma_{x}^{2}}\left\(x-\mu_{x}\right\)$

上面的方程就是局部加权回归方程，也就是我们需要的预测模型，这个模型的方差如下：

至此，我们已经利用训练样本集和LWR建立了预测模型，输入一个待预测的采样点x，该模型输出它的分类结果y。这意味着后续加入模型的采样点，只需经过常数时间的计算就能获取预测的分类结果。剩下的问题就是，如何向模型中添加后续的采样点。

   向模型中添加采样点的过程可以看作是对位姿空间的探索过程，采样点的状态总是可以通过碰撞检测得到，加入模型的每个采样点都会增加模型对位姿空间的认知程度。一个好的采样策略所选择的采样点能够最大程度上获取关于位姿空间的信息，于是，论文采用了主动学习的方法，以选择“最有用”的采样点加入模型。

   什么是主动学习？这里做一点简单的科普吧！

   咱们先来看个例子：在学校里，好学生的学习积极性总是很高，他们不用老师督促，自己就会找很多书来读，找很多题目来做，可以主动地获取知识，这些学生的成绩越来越好；一般的学生在学习上就会稍显被动，他们被动地接收着来自老师传授，老师讲一点，他们就学一点，这些学生的成绩自然难以赶上学习积极性较高的那些学生。把这个例子放在机器学习领域，就出现了主动学习和被动学习的概念。其实，在机器学习中，大部分的学习机制都是被动的（passive），这些学习器被动地接收数据，然后做处理，可是，学习器最强大的能力恰恰在于主动收集有用数据，并“影响它们正在试图理解的世界“！（这句话太霸气，Active Learning with Statistical Models原文中就这么说的。）主动学习正是要研究如何挖掘学习器的这一强大能力，即学习器应当自主选择有用的数据来处理。

   在主动学习中，学习器自己负责收集训练数据集。我们假设学习器能够迭代地选择输入 $\tilde{x}$ ，获得相应的输出 $\tilde{y}$ ，然后将 $\left\(\tilde{x},\tilde{y}\right\)$ 加入训练集（当然， $\tilde{x}$ 可能是从某个特定集合中选取的）。主动学习关心的问题是，下一个 $\tilde{x}$ 应该如何选取？这个问题很有实际意义，如果 $\tilde{x}$ 选择得当，即进行了一次恰当的查询或者动作，一些问题中对数据的需求可能大幅下降，一些NP完全的学习问题可能变成多项式时间可解的问题。在实际应用中，主动学习在一些数据难以获取或者获取代价较大的环境中发挥了巨大威力。例如，在工业环境中，每获取一个训练数据可能要用几天的时间，花费大量的资金；如果有一种方法，能够不断选择最有用的数据，无疑可以节省大量的时间和金钱。主动学习就是这样一种方法。

   说完了主动学习，我们终于可以来看看它在这篇论文中的应用了。对于由LWR建立的位姿空间预测模型来说，最大的改进就是使模型的方差最小。为何要使方差最小？因为方差越大，模型的预测就越不可靠，相反，方差越小，说明模型预测越可靠。事实上，已经被模型理解地很好的区域方差较低，这些区域往往是非困难区域；未被模型较好地理解的区域方差较大，这些区域往往是困难区域。主动学习的目的正是为了找到使期望方差（expected variance）最小的采样点，以此提高困难区域的采样点密度，降低非困难区域的采样点密度。假设我们下一步要向模型中添加采样点 $\tilde{x}$ ，则加入该点后，模型具有新的均值，如下：

其中，x是待预测点。在位姿空间中，它的坐标是已知的，状态是未知的。训练样本集新的方差和期望方差如下：

期望协方差和平方协方差如下：

期望条件协方差如下：

利用以上参数，可以计算出预测模型新的期望方差，如下：

由于x坐标已知，上式就成为关于 $\tilde{x}$ 的函数，主动学习要求出使上式取最小值的 $\tilde{x}$ 。在实现该算法时，可以随机选择一些状态已知的采样点作为有限样本集，然后从样本集中选择使上式取极小值的点即可。当然，我们也可以对上式求导，得到关于 $\tilde{x}$ 的导数，然后再计算出使上式取最小值的点，这个点就是下一步要生成的采样点。可见，论文中提出的采样策略将LWR与主动学习结合在一起，因此得名“主动采样（active sampling）”，算法如下：

   预测模型不仅能够指导采样，而且能够预测roadmap边的有效性。先说说为什么要预测边的有效性吧！首先，边的碰撞检测是很耗时的，拿普通的PRM来说，建立roadmap的时间有四分之三是用在了边的碰撞检测上。其次，roadmap中的有些边是冗余的，本来就没有必要检测这些边的有效性，因为它们根本不会最终规划出的路径上，对于单查询规划尤其如此。对于第一个问题，在建立roadmap的过程中，我们考虑用时间复杂度较低的预测机制代替时间复杂度较高的碰撞检测；对于第二个问题，由于在建立roadmap时使用了边有效性的预测机制，只有被预测为有效的边才会加入roadmap，当然，被预测为有效的边未必真的有效，在路径查询的时候，还要进行真正的碰撞检测，但是，预测机制就像一轮筛选，那些被预测为无效的边根本没有机会加入roadmap，因此可以直接减少大量冗余的边。

   既然明白了边的有效性预测的重要性，我们就来看看如何进行有效性预测。

   边的有效性预测其实很简单，形式几乎与上文所述的点的有效性预测一模一样，也是用LWR实现的，即利用边附近的采样点推测边的有效性。LWR的距离加权函数如下：

$w'\left\(e,x_{i}\right\)=e^{-k\left\(NearestPoint\left(e,x_{i} \right )-x_{i}\right\)^{2}}$

其中， $NearestPoint\left\(e,x_{i}\right\)$ 表示边e上距离 $x_{i}$ 最近的那个点。边有效性的预测方程如下：

$\hat{y}=\mu_{y}+\frac{\sigma_{xy}}{\sigma_{x}^{2}}\left\(NearestPoint\left\(e,\mu_{x}\right\)-\mu_{x}\right\)$

其中， $\hat{y}$ 是预测结果。如果预测结果大于无效阈值，就判断为无效；如果预测结果大于有效阈值，就判断为有效；否则，将边等分成两部分，分别检测这两部分的有效性，如果两部分都判断为有效，则判断为有效，否则就判断为无效。边有效性预测算法如下：

利用边有效性预测机制建立的roadmap称为“predictive roadmap”。现在，我们终于可以把上文中的主动采样算法与边有效性预测算法合二为一，组成基于预测模型的路径规划算法了：

其中，EXTRACTPATH过程就是真正的路径查询过程，在这个过程中需要调用真正的碰撞检测对之前被预测为有效的边进行最终检验。

   至此，基于预测模型的运动规划算法就介绍完了。这篇论文让我收获很大，至少了解了LWR和主动学习的概念，知道了将机器学习应用到运动规划中的办法。或许，我也可以按照这个思路写一篇论文呢。