机器人/导航/避障

避障与碰撞检测相比，是在检测到可能发生碰撞后采取的行动。可能的碰撞将取决于物体和机器人的形状和大小，以及物体和机器人的位置和运动预测。当试图避开障碍物时，需要面对许多决定。可用的决策取决于机器人可以采取的避开障碍物的路径。这些路径可以由机器人意识到障碍物后决定，也可以在已知所有障碍物的位置的情况下，在加载地图后决定。找到“正确”的路径可能很麻烦，这取决于使用的算法及其相关粒度。

基本思想

如果机器人的路径上有物体，请避开它。

本质上，这是避障的基本思想。然而，对于人类来说很简单的事情，在计算机世界中却非常复杂。哪个算法在避开障碍物方面最有效？哪个算法最不复杂、最有效？哪个算法可以有效地利用机器人的全部功能？这些都是你在寻找有效的避障算法时应该问自己的问题。

示例算法

文件：Figure1.GIF

使用 Player/Stage 使用的示例算法

在右边的图中，一个简单的“坦克驱动”机器人被展示出来，它正在前往三个预先确定的路标。机器人的算法是本节开头给出的简单单行代码的尊贵版本

1. 如果有剩余路标，则转向最近的路标。
   1. 如果没有剩余路标，则停止。
   2. 向最近的路标移动。
2. 如果有东西挡道
   1. 绕过它。
   2. 每 1.5 个车身长度后，转到步骤 1。
3. 如果机器人到达了路标
   1. 从列表中删除已到达的路标。
   2. 转到步骤 1。

尽管该算法对于一个过于简化的地图（其中所有障碍物都是简单的几何形状）效果良好，但在更复杂的场景中，它可能无法发挥作用。例如，将路标嵌套在 U 形障碍物的中间会导致该算法永远不会结束。

主要问题

随着机器人在我们日常生活中的重要性越来越大，避障（特别是处理人类安全问题）越来越受到关注也就不足为奇了。这些问题不容忽视。已经有一起与机器人相关的死亡事件。

除了安全之外，还会产生其他问题

• 避障算法复杂性
• 计算机能力
• 传感器精度/吞吐量
• 传感器数据解释

当然，随着避障算法的算法复杂性增加，所需的计算机能力也会增加。一些研究人员甚至发现，使用多个处理器并行（并行处理）来“分而治之”这些问题是有益的。

传感器精度和吞吐量对成功避障的影响越来越小。然而，这并不意味着它不存在。在设计避障机器人的过程中，可以做出一些权衡，这可能会损害传感器在机器人行为方面的有效性。

检测与避障

碰撞检测只是对机器人已知区域进行调查并检测到可能发生碰撞（或没有发生碰撞）的行为。为了让机器人避开碰撞，必须首先检测到碰撞。如果没有碰撞检测，似乎没有理由进行避障，因为机器人范围内没有任何东西需要避开。

避障是机器人采取的规避即将发生的碰撞的行动计划。如前所述，如果没有碰撞需要避开，就没有必要进行避障。

避障算法

四叉树

使用四叉树可以实现一个简单的避障算法。这里使用的一种近似技术使用了一种名为四叉树的数据结构。四叉树类似于二叉树，不同之处在于四叉树每个父节点有四个子节点，而不是只有两个。

每个子节点由机器人周围景观的“自上而下”图像中的一个像素方块表示。每个方块只是对问题“该方块内部是否有发生碰撞的可能性？”的二进制答案。如果答案是肯定的，则避开该方块，否则，则记下该方块可以安全行驶。如下面的图所示。

文件：Figure3.PNG

使用方块近似三角形。

优点

使用该算法的一个优点是，可以相当容易地进行撤退——通过向上爬树并尝试不同的方法。当然，在所有障碍物都已找到的情况下，可以使用简单的距离算法轻松地创建最小路径。

缺点

使用该算法的一个缺点是，由于每个像素方块的粒度，障碍物可能非常接近，以至于机器人可能不会注意到它实际上可以穿过一个间隙。

参考文献

• Player/Stage Wiki 页面