运动规划

一个基本的运动规划问题是在避免与已知障碍物碰撞的情况下，产生一个连接起始配置S和目标配置G的连续运动。机器人和障碍物的几何结构在二维或三维工作空间中描述，而运动在配置空间（可能更高维度）中表示为路径。

1.1 配置空间

配置描述了机器人的姿态，配置空间C 是所有可能配置的集合。例如:

• 如果机器人是在二维平面（工作空间）中平移的单点（零大小），则C是一个平面，并且可以使用两个参数（X，Y）表示配置。
• 如果机器人是可以平移和旋转的二维形状，那么工作空间仍然是二维的。然而，C是特殊的欧几里得群SE(2) =r²     SO(2)(其中SO(2)是2D旋转的特殊正交群，并且配置可以使用3个参数(x，y，θ)来表示。
• 如果机器人是一个可以平移和旋转的三维实体，那么工作空间是三维的，但是C是一个特殊的欧几里得群SE(3)=r³    SO(3)，并且一个配置需要6个参数:(x，y，z)用于转换，和欧拉角 (α，β，γ)。
• 如果机器人是一个具有N个旋转关节(并且没有闭环)的固定基座机械手，则C是N维的。

1.2 自由空间

避免与障碍物碰撞的一组构型称为自由空间C_free 。C_free 在C中的补集称为障碍或禁区。

通常，明确计算C_free的形状极其困难。然而，测试给定的配置是否在C_自由的中是有效率的。首先，正向运动学确定机器人几何图形的位置，碰撞检测测试机器人几何图形是否与环境几何图形碰撞。

1.3 目标空间

目标空间是自由空间的线性子空间，它表示我们希望机器人移动到哪里。在全局运动规划中，目标空间是由机器人的传感器观察到的。然而，在局部运动规划中，机器人在某些状态下无法观察目标空间。为了解决这个问题，机器人穿过几个虚拟目标空间，每个虚拟目标空间都位于可观察区域内(机器人周围)。虚拟目标空间被称为子目标。

1.4 障碍空间

障碍空间是机器人不能移动到的空间。障碍空间不是自由空间的补集。

1.5 危险空间

危险空间是机器人可以但不希望移动到的空间。危险空间既不是障碍空间，也不是自由空间。例如，林区的泥坑和工厂的油腻地板可被视为危险空间。如果机器人找不到完全属于自由空间的轨迹，它必须穿过危险空间。在某些情况下，在具有时间/能量约束的运动规划中，机器人可能更喜欢在危险空间中选择短路径，而不是在自由空间中选择长路径。^[1]

低维问题可以通过基于网格的算法来解决，这些算法将网格覆盖在配置空间的顶部，或者通过几何算法来计算C_free的形状和连通性。

复杂约束下高维系统的精确运动规划在计算上是棘手的。势场算法是有效的，但会陷入局部极小值(谐波势场是一个例外)。基于采样的算法避免了局部极小的问题，并且很快解决了许多问题。他们无法确定不存在路径，但随着时间的推移，失败的概率会降至零。

基于采样的算法目前被认为是高维空间运动规划的最新技术，并已被应用于几十甚至数百维的问题(机器人操纵器、生物分子、动画数字角色和腿型机器人)。

2.1 基于网格的搜索

基于网格的方法在配置空间上覆盖一个网格，并假设每个配置都用一个网格点来标识。在每个网格点，只要它们之间的线完全包含在C_free 中，机器人就可以移动到相邻的网格点(这通过碰撞检测进行测试)。这离散化了一组动作，搜索算法(如 A* )用于找到从开始到目标的路径。

这些方法需要设置网格分辨率。使用较粗的网格搜索更快，但是该算法将无法找到通过C_free 狭窄部分的路径。此外，网格上的点数在配置空间维度上呈指数级增长，这使得它们不适用于高维问题。

传统的基于网格的方法产生的路径的航向变化被限制在给定基点的倍数，通常导致次优路径。任意角度路径规划方法通过沿网格边缘传播信息来找到较短的路径(以快速搜索)，而不限制它们到网格边缘的路径(以找到较短的路径)。

基于网格的方法通常需要重复搜索，例如，当机器人对配置空间的知识发生变化或配置空间本身在路径跟踪过程中发生变化时。增量启发式搜索算法通过使用以前类似路径规划问题的经验来快速重新规划，以加快对当前路径规划问题的搜索。

2.2 基于区间的搜索

这些方法与基于网格的搜索方法相似，只是它们生成了一个覆盖整个配置空间的铺路，而不是一个网格。。^[2]铺路被分解成两个子空间 X⁻，X⁺，X⁻ ⊂ C_free ⊂ X⁺。表征 C_free 相当于解决一个集合反演问题。因此，当 C_free不能用线性不等式来描述时，可以使用区间分析来保证其封闭性。

这样，机器人就可以在X-内自由移动，并且不能超出X+。对于这两个子空间，构建一个邻居图，并使用 Dijkstra 或 A*等算法找到路径。当一条路径在x-中可行时，它在C_free 中也是可行的。当x+中不存在从一个初始配置到目标的路径时，我们可以保证cfree中不存在可行路径。对于基于网格的方法，区间方法不适合于高维问题，因为要生成的框的数量相对于配置空间的维数呈指数增长。

右边的三个图形提供了一个示例，其中具有两个自由度的挂钩必须从左向右移动，避免两个水平的小段。

使用区间分析的子空穴分解也使得描述C_free C_free 的拓扑结构成为可能，例如计算其连接组件的数量。^[3]

2.3 几何算法

多边形障碍物中的点机器人

• 可见性图表
• 细胞分解

在障碍中翻译对象

• 闵可夫斯基和

寻找建筑物的出路

• 最远光线轨迹

给定当前位置周围的一束光线（其长度与墙相撞），机器人将向最长光线的方向移动，除非识别出门。这种算法用来模拟建筑物的紧急出口。

2.4 基于奖励的算法

基于奖励的算法假设机器人在每个状态(位置和内部状态，包括方向)下可以在不同的动作(运动)之间进行选择。然而，每个行动的结果并不确定。换句话说，结果(位移)部分是随机的，部分是在机器人的控制下。机器人到达目标时获得正面奖励，而遇到障碍时获得负面奖励。这些算法试图找到一条最大化累积未来回报的路径。马可夫决策过程 (MDP)是一个流行的数学框架，用于许多基于奖励的算法。MDP相对于其他基于奖励的算法的优势在于，它们生成最佳路径。MDP的缺点是它们限制了机器人从有限的一组动作中进行选择。因此，路径不平滑(类似于基于网格的方法)。模糊马尔可夫决策过程(FDMPs)是MDPs的扩展，它使用模糊推理系统生成平滑路径。^[4]

2.5 人工势场

一种方法是将机器人的配置视为势场中的一个点，该点结合了对目标的吸引和对障碍物的排斥。结果轨迹作为路径输出。这种方法的优点是轨迹生成时计算量小。然而，它们可能被困在势场的局部最小值中，找不到路径，或者可能找到非最优路径。人工势场可以被视为类似于静电势场的连续方程(将机器人视为点电荷)，或者通过场的运动可以使用一组语言规则离散化。^[5]

2.6 基于采样的算法

基于采样的算法代表配置空间的采样配置的路线图。基本算法在C中对n个配置进行采样，并保留在Cfree中用作转折点的那些算法。然后，如果线段p q完全在C_free 中，则构建连接两个转折点p和q的路线图。再次，碰撞检测用于测试C_free 中的包含。为了找到连接s和g的路径，它们被添加到路线图中。如果路线图中的路径连接S和G，计划者就会成功，并返回该路径。如果不是，原因并不明确：要么C_free 没有路径，要么规划者没有取样足够的转折点。

给定C_free 上的基本可见性条件，已经证明，随着配置N的数量增加，上述算法找到的概率接近指数1。可见性不明显依赖于C的维数；有可能有一个高维空间与“好”的可见性或低维空间与“差”的可见性。基于样本的方法的实验成功表明，最常见的空间具有良好的可见性。

这个基本方案有许多变体:

• 通常，只测试附近转折点对之间的片段要快得多，而不是测试所有转折点对。
• 不均匀的采样分布试图在改善路线图连通性的领域设置更多转折点。
• 准随机样本通常比伪随机样本产生更好的配置空间覆盖，尽管最近的一些工作认为，与采样分布的影响相比，随机性来源的影响最小。
• 通过允许弯曲的视线(例如，通过在拦路位于两个转折点之间的障碍物上爬行)，可以显著减少解决给定问题所需的转折点的数量^[6]。
• 如果只需要一个或几个规划查询，并不总是需要构建整个空间的路线图。在这种情况下，树增长变体通常更快(单查询规划)。如果要在同一空间进行许多查询(多查询规划)，路线图仍然很有用

2.7 著名算法列表

• A*
• D*
• 快速探索随机树
• 概率路线图

如果运动规划者在有限的时间内产生解决方案或者正确地报告没有解决方案，那么运动规划者就是完整的。大多数完整的算法都是基于几何的。一个完整规划器的性能是通过其计算复杂性来评估的。

分辨率完整性是一种属性，如果底层网格的分辨率足够高，规划者就可以保证找到路径。大多数分辨率完整的规划者都是基于网格或间隔的。分辨率完全规划器的计算复杂性取决于底层网格中的点数，即O(1/h^d)，其中h是分辨率(网格单元一侧的长度)，d是配置空间维度。

概率完整性规划者未能找到路径的概率(如果存在路径的话)渐近地趋近于零。几种基于样本的方法可能是完整的。概率完全规划器的性能由收敛速度来衡量。

不完全的规划者并不总是能找到可行的路径。有时不完整的计划者在实践中做得很好。

已经开发了许多算法来处理这个基本问题的变体。

4.1 差分约束

完整的

• 机械手臂(带动力学)

非完整

• 汽车
• 独轮车
• 飞机
• 加速度有界系统
• 移动障碍物(时间不能倒退)
• 锥尖可控针
• 差动驱动机器人

4.2 最优性约束

4.3 混合系统

混合系统是那些混合离散和连续行为的系统。这种系统的例子有:

• 机器人操作
• 机械组件
• 腿型机器人运动
• 可重构机器人

4.4 不确定

• 运动不确定性
• 信息缺失
• 主动感应
• 无传感器规划

• 机器人导航
• 自动化
• 无人驾驶汽车
• 机器人手术
• 数字角色动画
• 蛋白质折叠
• 计算机辅助建筑设计中的安全性和可访问性