机器人/导航/轨迹规划

轨迹规划

轨迹规划是指在一段时间内从点 A 移动到点 B 同时避免碰撞。这可以用离散和连续方法计算。轨迹规划是机器人领域的一个主要领域，因为它为自动驾驶车辆铺平了道路。

轨迹规划有时被称为运动规划，错误地被称为路径规划。轨迹规划不同于路径规划，因为它是由时间参数化的。本质上，轨迹规划包含路径规划，以及根据速度、时间和运动学规划如何移动。

问题约束

完整约束

完整约束是机器人可控自由度与机器人总自由度之间的关系。如果可控自由度的数量大于或等于机器人的总自由度，则该机器人被称为完整约束的。使用完整约束的机器人，许多移动更容易，返回到过去的姿态也更容易。

汽车是非完整约束的，因为它没有办法横向移动。这使得某些运动，如平行泊车，变得困难。完整约束车辆的例子是使用麦克纳姆轮的车辆，例如新的 Segway RMP。

动态环境

在动态环境中，例如现实世界中，许多可能的碰撞物体并非静止的。这使得轨迹规划更加困难，因为时间在不断变化，物体也在移动。机器人不能简单地倒退回时间，因为它可能只是从静止的碰撞中退回。除此之外，由于地形，许多选择是完全不可逆的，例如从悬崖上掉下来。

概念

轨迹规划的概念

轨迹规划给出一个从起始配置 S 到目标配置 G 的路径，在 2D 或 3D 空间中避免碰撞。

配置是描述机器人位置的姿态。配置空间 C 是所有配置的集合。例如，在二维空间中，机器人的配置将由坐标 (x, y) 和角度 θ 描述。而在三维空间中，机器人的配置将由坐标 (x, y, z) 和角度 (α, β, γ) 描述。

自由空间 C_free 是所有无碰撞配置的集合。计算 C_free 的形状效率不高，但是，计算给定配置是否无碰撞，只需使用来自传感器的运动学和碰撞检测即可。

目标空间是自由空间的线性子空间，我们希望机器人到达那里。在全局运动规划中，目标空间可以通过机器人的传感器观察到。然而，在局部运动规划中，机器人无法在某些状态下观察目标空间。为了解决这个问题，机器人假设了几个位于可观察区域（机器人周围）的虚拟目标空间。虚拟目标空间被称为子目标。

规划算法

人工势场

人工势场的例子

人工势场规划在映射上放置值，目标具有最低（最高）值，根据距离目标的距离增加（下降）值。障碍物被定义为具有极高（低）值。然后机器人只需移动到与其相邻的最低（最高）势值，这应该会引导它到达目标。然而，这种技术经常陷入局部最小值。可以使用某些技术来避免这种情况，例如波前势场规划。人工势场可以通过类似于静电势场的直接方程来实现，也可以通过一组语言规则来驱动。

基于采样的规划

路径图方法是一种基于采样的规划方法。首先，在 C 中对 N 个配置进行采样作为里程碑。然后，在所有里程碑之间形成一条直线 PQ，只要直线 PQ 完全位于 C_free 中。然后可以使用图搜索算法来找到从起点到目标的路径。随着 N 的增长，可以找到更好的解决方案，但这也增加了计算时间。

基于网格的规划

基于网格的规划的例子

基于网格的规划在映射上覆盖一个网格。然后，每个配置都对应一个网格像素。机器人可以从一个网格像素移动到任何相邻的网格像素，只要该网格像素位于 C_free 中。然后可以使用 A* 等搜索算法来找到从起点到目标的路径。这种方法的一个潜在权衡是，使用较低分辨率的网格（更大的像素），搜索速度会更快，但是它可能会错过 C_free 中狭窄空间的路径。此外，随着网格分辨率的增加，内存使用量呈指数级增长，因此，在较大的区域中，可能需要使用其他路径规划算法。

基于奖励的规划

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