单元分解方法

25.4.2 单元分解方法

我们的第一个路径规划方法利用了单元分解——也就是，它将自由空间分解成个数有限的相邻区域，称为单元。这些区域具有重要的性质，即在单个区域内的路径规划问题能够用简单方式解决（例如沿直线移动）。于是路径规划问题变成了一个离散图搜索问题，非常像在第三章中介绍的搜索问题。

最简单的单元分解由一个规则地分隔的网格组成。图25.14（a）显示了空间的正方形网格分解和在这个网格尺寸下的最优解路径。我们还使用灰度级明暗来表示每个自由空间网格单元的值——即，从该单元到目标的最短路径耗散。（这些值能够用图17.4给出的VALUE-ITERATION算法的一种确定性的形式来计算。）图25.14（b）显示了手臂在工作空间中对应的轨迹。

图 25.14 （a）为构型空间的离散网格单元近似形式找到的价值函数和路径。（b）以工作空间坐标形象化显示的同一条路径。注意机器人是如何弯曲它的肘部来避免与竖直障碍物发生碰撞的

这种分解的优点是非常容易实现，但是它也受到两个限制。首先，它只能在低维的构型空间中工作，因为网格数目随着维数d呈指数级增长。其次，存在如何处理“混合型”单元的问题——也就是说，既不完全在自由空间中，也不完全在占用空间中的单元的问题。一条包含这种单元的解路径也许不是一个真正的解，因为有可能无法沿一条直线从期望方向穿过单元。这会造成路径规划不可靠。另一方面，如果我们坚持只能使用完全自由的单元，规划将会是不完备的，因为有可能仅有的通往目标的路径要穿过混合单元——尤其是在单元的大小和空间中通道及开阔地的大小可比拟的时候。

有两种方法修改单元分解方法，从而避免这些问题。第一种是对混合单元作进一步的子分解——有可能采用尺寸为原始大小一半的单元。这可以递归地进行，直到找到一条完全处于自由单元中的路径。（当然，这个方法只有当存在一种能判断给定单元是否为混合单元的途径时才有效，而这种判断只有在构型空间边界具有相对简单的数学描述时才比较容易实现。）倘若一个解必须通过的最小通道是有边界的，则这种方法就是完备的。虽然大多数的计算努力都集中在构型空间中的棘手区域，它仍然不能很好地扩展到高维问题，因为每次对一个单元进行递归分解都会创造出2d个更小的单元。第二种获得完备算法的方法是要求自由空间上的准确单元分解（exact cell decomposition）。这种方法必须允许单元在遇到自由空间边界时的形状是不规则的，但是从对任意自由单元进行遍历计算必须简单的意义上说，这个形状还必须是“简单”的。这个技术需要一些非常高深的几何思想，所以我们不在这里深入地讨论它。

观察图25.14（a）中所示的解路径，我们能够发现另外一些不得不解决的困难。首先，注意到路径中包括任意尖锐的拐角；一个以任何有限速度运动的机器人都不能执行这样的路径。其次，注意到路径与障碍物挨得很近。任何一个驾驶过汽车的人都知道，在停车场中的一个两侧只有一毫米空隙的停车间里根本无法停车；出于同样的原因，我们将更愿意选择对微小运动误差比较鲁棒的解路径。

我们希望在最小化路径长度的同时也最大化到障碍物的空隙。这可以通过引入一个势场（potential field）来实现。一个势场是一个定义在状态空间上的函数，它的值随着到最近障碍物距离的增长而增长。图25.15（a）显示了一个这样的势场——状态空间越暗，它离障碍物就越近。当它被用于路径规划时，这个势场就成了优化问题中的一个附加的代价项。这引出了一个有趣的折中。一方面，机器人寻求达到目标的最小距离长度。另一方面，它试图凭借使势函数最小化来远离障碍物。对两个目标分别给予合适的权重，作为结果的一条路径或许看起来如图25.15（b）中所示的那条。此图还显示了从联合的代价函数派生出的价值函数，仍然通过价值迭代进行计算。显然，结果路径长了一些，但也更安全了。

图25.15 （a）一个排斥势场将机器人推离障碍物。（b）通过同时对路径长度和势进行最小化而找到的路径