导航和避免服务机器人遇到障碍的最佳方法是什么？
机器人是与现实世界互动的机械和软件系统。 对于服务机器人，了解您当前在太空中的位置，目标的位置以及绕过可能的障碍物建立通往目标的路线的能力非常重要。 我们正在开发一种
用于在练习场上收集高尔夫球的
机器人 。 我们考虑了不同的方法来构建一条路线，以便为自己找到最佳路线，也许此信息对某人会很有趣。
使机器人在二维空间中达到其最终目标的最简单方法。 在这里，流动站本身就是一个小障碍，前面没有障碍。 因此，在这种情况下，机器人会直线移动，并在达到目标时停止。
如果世界上只有一个机器人及其必须实现的目标，则此方法适用。 Direct将允许您尽快达到最终配置。
但是，如果在机器人前方突然出现障碍物，则无法应用该算法。 直线移动时，流动站将无法绕过或通过。 就这一点而言，他只是停在障碍物前面而不会继续前进。
如何避开障碍物？ 解决问题的最简单方法是称为“避免障碍”的行为选项。 实际上，它由各种算法表示。
步行到算法
如果未实现目标：
如果世界上只有一个机器人及其必须实现的目标，则此方法适用。 Direct将允许您尽快达到最终配置。 但是，如果在机器人前方的目标前方出现障碍物，应该使用哪种算法？
障碍物不允许机器人直线到达目的地，在这种情况下，流动站就停在其前方。 在这种情况下，您也可以使用“ Walk To”算法，但需要对其进行补充。
错误算法
在平常的生活中，一个人从一个点到另一点到达目标并遇到障碍时，只会绕过障碍。 这种行为称为“规避障碍”。 事实证明它将被机器人用来实现目标。 应用甲虫算法的最简单方法。
专家以这种方式调用Bug算法是因为甲虫的行为是作为基础的-如果甲虫看到障碍物，就会绕过它。
机器人在朝目标移动时（包括在障碍物周围行走时）采取的步骤称为轨迹。
错误算法是用于构造更复杂类型的路由的概念的基础。 这些包括：
轨迹的概念。 这是机器人的简单动作序列，他为了实现最终目标而执行该动作。 甲虫算法也是“轨迹规划器”。 接收到机器人及其目标所处的点的坐标后，该算法将开发出合适的运动轨迹。
政策理念 。 如果使用甲虫算法将某些运动指令发送到机器人，则这种构造路线的方法称为“管理策略”。
启发式的概念。 这是用于通知机器人有关算法下一阶段的规则的名称。 在这种情况下，试探法是对象沿其移动的线。 创建路径时，您需要正确确定启发式。 如果操作不正确，则构建的路线将无法使用。
但是，这样的算法限制了开发人员，因为借助它的帮助，有可能构建大小受限制的路线。 使用这种算法构造路径时，所有障碍物都必须采用凸多边形的形式。
Bug算法也有局限性：
- 障碍物应相互保持一定距离，不可能有共同点；
- 障碍物的边界是闭合曲线，但它们必须使机器人移动的直线与它们中的每一个相交有限的次数。
- 机器人是一个不成比例的小点，因此无论障碍物之间的通道如何，它都能在障碍物之间移动。
通过使用高级DH-Bug算法可以克服其中一些限制。 它的特点是借助它的帮助，机器人将能够应对移动中的障碍物。 而且，这种算法由两层组成。 首先是咨询。 它使您可以在不使用其他信息的情况下预先评估路线。 第二层是自适应的。 多亏了他，机器人能够及时响应程序中最初未设置的障碍。
CBUG算法
CBUG算法是一种考虑所有细节的方式的路径构造版本。 在开发过程中，专家们考虑了机器人的尺寸，并解决了与优化路径相关的问题。 这种改进算法的一个显着特征是，要生成路线，必须始终将起点保留在对象的内存中。 对于CBUG算法，始终不变，只是对于其应用，必须具有固定的内存量。
Dijkstra的算法
图上使用的算法由E. Dijkstroy在上个世纪下半叶创建。 有了它的帮助，将有可能确定从图的一个顶点到另一个顶点的最短路径。 当机器人访问了所有峰时，此类算法即告结束。 如果他还没有去过那些人，那么将选择一个带有最低标记的峰。
Deister算法的优点包括：- 注意路径的长度及其成本；
- 如果找到最佳节点，则更新节点。
这种构造路线的方法的缺点在于，它仅适用于没有负权重边的图形。 不方便的是他在搜索宽度时方向不佳。
Bellman-Ford算法
但是，在经常出现的情况下，有必要建立一条路线，使肋骨负重。 Bellman-Ford算法将有助于解决此类问题。 结果，如果最终路径的边缘权重之和为负值，则称为负周期。
约翰逊算法
该算法由数据库引入 约翰逊（Johnson）为了找出从一个高峰到另一个高峰的所有最短路线。 在这种情况下，该方法可用于权重为正和负的边。 该算法的唯一缺点是没有负周期。
算法A *
为了找到使用图的最佳方法，您需要应用A *算法。 它使您可以通过图形上的第一个匹配来确定从机器人到目标的最佳路线。 该算法的基础是启发式，其公式如下：
f(n)=g(n)+h(n).
f(n) - , n.
g(n) - n .
h(n) - .该算法允许您找到到达目标的最短路径，直到h（n）取最大允许值为止。 A *算法的一个特点是它的灵活性。 状态通常是机器人的单元或位置。 但也可以是速度或方向。
同时，附近的状态因具体情况而异。
该算法的灵活性还体现在以下事实上：机器人需要实现的目标可以一次包含多个位置。 在这种情况下，启发式近似值h（n）对于所有可用目的应立即有效。
算法A *的效果如何取决于指数h（n）。 启发式近似质量越好，效率越高。 同样，可用内存量和处理器时间也会影响算法的操作。
波形追踪算法
此外，波动算法通常用于在图形上绘制路线。 当以此方式构造路径时，使用广度优先搜索方法。
该算法本身包括以下步骤：- 初始化
- 波浪建设
- 路线恢复。
在初始阶段，将创建许多单元的图像，每个图像对于机器人而言都是可通过或不可通过的。
机器人从一个单元移动到另一个单元，依次确定是否可以通过它，以及是否之前没有标记过。
在那之后，从起始单元到最后一个单元的最短路径是通过蛮力创造的，实现这一目标是漫游者的目的。
离散空间算法
- 配置空间在所有维度上的大小都是恒定的。
- 离散化所有测量，以使它们具有恒定数量的像元。
- 位于障碍物内部配置空间中的所有单元都应标记为不可通行。
- 结果，所有可传递单元变成节点。
- 每个节点都连接到图中的所有邻居。
随机路径查找器
规划路线时最困难的方面是计算配置空间并确定通过此空间时最方便的路径。 由于有了路线图，将有可能解决这些问题。 该方法的本质是将空间划分为相同的正方形，连接所有最近的顶点。 遍历所有路径。 对所有路径进行排序，以找到值最小的路径。
概率路线图算法
- 1.创建一个空图G。
- 2.在图G中添加机器人的节点及其最终目标。
- 3.对于第N次集成：
- 查找配置空间的统一随机样本，并将其命名为R。
- 如果机械手与R配置冲突，则可以继续。
- 否则：将R添加到G列。
- 4.标识图中的所有节点d和R。
- 5.对于所有符合此参数的N个节点：
快速探索随机树算法
有时您需要构建一条路径而不应用先前的计划查询。 在这种情况下，您必须使用以下方法：
- 创建一个空的T.树
- 添加到T初始机器人配置。
- 在达到目标之前：
- 提取节点R。
- 在T中定义最接近R的节点。 给他起名字K。
- 将机器人从K移到R，直到满足以下条件：
- 如果发生碰撞，请继续定义随机样本。
- 否则：在此配置中将新节点添加到T。
- 如果达到d和K之间的最大距离，请再次开始进行随机采样。
- 如果链结节点位于距任何节点T的距离d之内，则可获得解。
结论
对我们来说，将路线建设问题分为全球和本地是最佳选择。 全局路线是绕过野外目标或返回基地的目标点的列表。 当超声波传感器或保险杠检测到障碍物时，将开始本地路线。
由于在我们的细节中所有障碍都是凸面的，因此我们使用最简单的BUG算法，甚至更简单。 一种特定的“男孩式”导航方法。 当超声波检测到障碍物时，流动站顺时针旋转90度，行驶1 m，逆时针旋转90。 如果保险杠检测到障碍物，则将机器人向后旋转0.5米。
计划
在2018年夏季项目开始期间。 发生了很多事件。 我们正在准备一个有关我们项目开发的帖子。 感谢您的关注！
参考文献