• 网格方法一种运动规划方法
  • 多分辨率网格表示
  • 带有运动约束的网格方法
    • 轮式机器人基于网格点的路径规划
    • 手臂机器人基于网格点的运动规划

网格方法——一种运动规划方法

网格方法是一种类似于 A∗ 搜索算法的需要离散化搜索空间的搜索方法。配置空间（configuration space，C-space）最简单的离散方式就是网格化。比如，如果配置空间是 n 维的，我们把每一维度分成k个网格点，那么配置空间就可以通过 kn 网格点表示。

通过以下的简单修正， A∗ 算法可以用来作为配置空间网格的路径规划：

• 网格点中“相邻点”的定义必须是可以选择的：机器人是否强迫在配置空间中轴对齐的方向上运动，或者同时在多维方向上运动？

  比如在二维配置空间中，相邻点可以有4个连接点（指南针上的四个主要方向：东、南、西、北）或8个连接点（允许对角线连接的话），如图1所示。

  图1

  

  如果允许对角移动，那么应该对对角移动的成本进行合理的惩罚。比如南/北/西/东等相邻的移动成本如果为1的话，那么对角移动的成本应该是 2√ 。如果期望的成本是整数，那么为了方便实现，5到7都可以用作对角运动的成本。

• 如果只能沿着轴向运动，那么到目标点的启发式成本应该基于曼哈顿距离，而不是欧式距离。曼哈顿距离计算需要途径的“城市模块”，如图2所示。

  图2

  

• 如果当前节点 current 到 nbr 节点是无碰撞的，那么只把 nbr 添加到 OPEN 列表中。
• 对于常规的网格结构，其他最优化方法也是可行的。

基于网格点的 A∗ 路径规划算法是全分辨率的：如果离散配置空间中的解存在，通过搜索就可以找到。而且路径是可允许的运动路径当中最短的。

基于网格的规划是单一查询规划器。它可以从头开始解决每个路径规划查询问题。但是，如果相同的 qgoal 将用于相同环境中多个路径规划查询的问题，那么可能值得对整个网格进行预处理，以支持快速路径规划。这叫作wavefront规划器，如图3所示。

图3

在二维网格中的wavefront规划器。目标点配置被设为0，所有无碰撞的四个相邻节点被设为1，按照这个规律，所有没有被赋值的相邻节点依次加1，直到所有相连接的节点都被赋值，从哪里开始进行轨迹规划已经不重要了：只要在每一步中，机器人都按照“下坡”的原则走向相邻点，就会达到目标点。（对产生碰撞的网格点给一个比较高的值）
           

尽管基于网格点的路径规划很容易实现，但它仅适用于低维配置空间。如果维数增加，那么网格点的数量与路径规划算法的复杂度将程指数增加。

多分辨率网格表示

减少基于网格点规划方法计算复杂度的一个方式就是采用自由配置空间 Cfree 的多分辨率网格表示。从概念上讲，如果以网格点为中心的直线单元的任何部分碰到了c障碍，则网格点被认为是一个障碍。为了改善障碍的表现，一个障碍单元可以被细分成更小的单元。原始单元的每一个维度都可以分成两部分，形成 2n 个子单元。任何包含障碍的单元还可以继续分裂，直到最大分辨率。

这种表示方法的优势是只有靠近障碍物的空间被改善成了高分辨率的，而那些远离障碍物的空间仍然由粗糙的分辨率表示。这可以使路径规划器用最小步长通过杂乱的空间，而使用大步长通过宽阔的空间。这一想法如图4所示

图4

图中只用了10个单元就表示了需要相同分辨率下用64个单元表示的障碍物。

当维数 n=2 时，多分辨率表示法被叫作四叉树（quadtree），因为每一个单元可以分成 22=4 个子单元。当 n=3 时，这种表示法就叫作八叉树（octtree）了。

带有运动约束的网格方法

以上关于网格的规划算法是建立在一种假设的基础之上的，那就是机器人可以从一个节点单元运动到配置空间网格中任意相邻单元中。这在有些机器人中是不可行的。比如一辆车无法一步达到侧面的相邻单元。而且机器人手臂应该在状态空间中考虑手臂的动力学进行规划，而不是仅仅在配置空间中。在状态空间中机器人手臂没有办法按照一个指定的方向运动，如图5所示

图5

在相位图中，初始状态$\dot q>0$时轨迹无法向左运动，因为向左表示$q$下降
           

基于网格的规划器必须适应特定机器人的运动约束。特别是，约束可能是有向图表示的。一种方法是将机器人控制离散化，同时仍然适当地在C空间或状态空间上使用网格。在下一部分详细描述了一个轮式移动机器人和一个动态机器人手臂。

轮式机器人基于网格点的路径规划

图6

图6 独轮车，驱动器和汽车式机器人的控制集的离散化

迪杰特斯拉(Dijkstra)短路径算法

手臂机器人基于网格点的运动规划

待续……