抽骨架方法

25.4.3 抽骨架方法

路径规划算法的第二个主要家族是基于抽骨架的思想。这些算法将机器人的自由空间缩减为一个一维的表示，从而使规划问题变得更容易。这种低维的表示方法被称为构型空间的骨架。

图25.16显示了抽骨架的一个例子：它是自由空间的一个Voronoi图——到两个或更多障碍物距离相等的所有点的集合。为了利用Voronoi图进行路径规划，机器人首先将它的当前构型转变为Voronoi图中的一点。很容易证明这总是能够通过构型空间中的一个直线运动得到。然后，机器人沿着Voronoi图前进，直到它到达离目标构型最近的点。最后，机器人离开 Voronoi 图，向目标移动。再一次，这最后一步仍然涉及到构型空间中的直线运动。

图25.16 （a）Voronoi图是构型空间中与两个或更多障碍物等距离的点的集合。（b）一个概率的路径图，由自由空间中400个随机选取的点组成

在这种方法中，原来的路径规划问题被简化为在 Voronoi 图上寻找一条路径，一般来说是一维的（一些特例除外），并且3条或3条以上一维曲线的交点是有限多的。因此，在Voronoi图中寻找最短路径就属于在第三章和第四章中所讨论的离散图搜索问题。使用 Voronoi 图也许不会帮我们找到最短的路径，但是结果路径往往能使空隙最大化。Voronoi图技术的缺点是，很难将它们应用于较高维的构型空间，而且当构型空间比较宽阔时，它们容易导致大量不必要的弯路。而且 Voronoi 图可能很难计算，尤其是在构型空间中，因为障碍物的形状会非常复杂。

Voronoi图的一种替代方法是概率路径图（probabilistic roadmap），提供了更多可能路径，并因此能够更好地处理宽阔空间的抽骨架方法。图25.16（b）显示了一个概率路径图的例子。随机生成大量的构型，并丢弃那些没有落在自由空间中的，就建立了这张图。然后，我们把任意两个节点，如果很“容易”从一个节点到达另一个的话——例如通过自由空间的一条直线——用一段弧连接起来。所有这些结果就是机器人自由空间内的一幅随机图。如果我们把机器人的初始和目标构型加入到这个图中，路径规划就相当于一个离散图搜索问题。理论上，这种方法是不完备的，因为对随机点的不好的选择可能会使我们得不到任何从起点到目标的路径。根据生成的点数和构型空间的某些几何特性对失败的概率加以限制是可能的。还可以把取样点的生成引导到那些局部搜索表明有可能找到好路径的区域，并从起点和目标两个位置双向进行。有了这些改进，概率路径图规划比大多数其它路径规划技术更易于扩展到高维构型空间。