研究人员帮助机器人在不确定的环境中高效导航

如果前往目的地的机器人只有两条可能的路径，它只需要比较路线的旅行时间和成功概率。但是，如果机器人正在穿越具有许多可能路径的复杂环境，那么在如此多的不确定性中选择最佳路线很快就会成为一个棘手的问题。

麻省理工学院的研究人员开发了一种方法，可以帮助这个机器人有效地推理出到达目的地的最佳路线。他们创建了一种算法，用于构建不确定环境的路线图，以平衡路线图质量和计算效率之间的权衡，使机器人能够快速找到一条可穿越的路线，从而最大限度地减少旅行时间。

该算法从确定安全的路径开始，并自动找到机器人可以采取的捷径，以减少整体旅行时间。在模拟实验中，研究人员发现，与其他基线相比，他们的算法可以在规划性能和效率之间实现更好的平衡，这些基线优先考虑一个或另一个。

这种算法可以在探索等领域得到应用，也许可以帮助机器人规划出最佳方式，在火星不平坦的表面上到达遥远的陨石坑边缘。它还可以帮助搜救无人机找到被困在偏远山腰的人的最快路线。

“这是不现实的，尤其是在非常大的户外环境中，你会确切地知道你可以和不能穿越的地方。但是，如果我们只有一点关于环境的信息，我们就可以用它来构建高质量的路线图，“电气工程和计算机科学（EECS）研究生Yasmin Veys说，他是该技术论文的主要作者。

Veys与麻省理工学院航空航天系的研究生Martina Stadler Kurtz以及麻省理工学院航空航天学教授、麻省理工学院计算机科学和人工智能实验室（CSAIL）成员Nicholas Roy共同撰写了这篇论文。该研究将在机器人与自动化国际会议上发表。

生成图形

为了研究运动规划，研究人员经常将机器人的环境视为图形，其中一系列“边”或线段代表起点和目标之间的可能路径。

Veys和她的合作者使用了一种名为“加拿大旅行者问题”（CTP）的图形表示，它的名字来源于沮丧的加拿大驾车者，当前方的道路被雪阻挡时，他们必须回头寻找新的路线。

在 CTP 中，图形的每条边都有一个与之关联的权重，该权重表示该路径需要多长时间才能遍历，以及可遍历的可能性的概率。CTP 的目标是最大限度地减少到达目的地的旅行时间。

研究人员专注于如何自动生成有效表示不确定环境的CTP图。

“如果我们在一个环境中导航，我们可能有一些信息，所以我们不只是盲目地进入。虽然这不是一个详细的导航计划，但它让我们了解我们正在处理的内容。这项工作的关键是试图在 CTP 图中捕获这一点，“Kurtz 补充道。

他们的算法假设这些部分信息（可能是卫星图像）可以划分为特定区域（湖泊可能是一个区域，开阔的田野可能是另一个区域，等等）。

每个区域都有机器人穿越它的概率。例如，非水生机器人更有可能穿越田野而不是湖泊，因此田野的概率会更高。

该算法使用这些信息在开放空间中构建初始图，绘制出一条缓慢但绝对可遍历的保守路径。然后，它使用团队开发的指标来确定应将哪些边缘或通过不确定区域的捷径添加到图形中，以减少整体旅行时间。

选择快捷方式

通过仅选择可能可遍历的快捷方式，该算法可以防止规划过程变得不必要的复杂。

“运动计划的质量取决于图形的质量。如果该图中没有好的路径，那么算法就无法为您提供一个好的计划，“Veys 解释道。

在100多个模拟实验中测试了该算法，在日益复杂的环境中，研究人员发现，它可以始终优于不考虑概率的基线方法。他们还使用麻省理工学院的空中校园地图对其进行了测试，以表明它在现实世界的城市环境中是有效的。

未来，他们希望增强该算法，使其可以在两个以上的维度上工作，这可以使其能够用于复杂的机器人操作问题。他们还有兴趣研究 CTP 图与这些图所代表的真实环境之间的不匹配。

“在现实世界中运行的机器人受到不确定性的困扰，无论是在可用的传感器数据、关于环境的先验知识，还是关于其他智能体的行为方式方面。不幸的是，处理这些不确定性会产生高昂的计算成本，“佐治亚理工学院交互式计算学院机器人学教授兼KUKA主席Seth Hutchinson说，他没有参与这项研究。“这项工作通过提出一种巧妙的近似方案来解决这些问题，该方案可用于有效地计算不确定性容忍计划。

这项研究部分由分布式协作智能系统和技术合作研究联盟下的美国陆军研究实验室以及Joseph T. Corso和Lily Corso研究生奖学金资助。