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

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

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

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

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

Veys与麻省理工学院航空航天系研究生MartinaStadlerKurtz以及资深作者NicholasRoy(麻省理工学院航空航天教授、麻省理工计算机科学与人工智能实验室(CSAIL)成员)共同撰写了这篇论文。该研究将于5月13日至17日在日本横滨举行的国际机器人与自动化会议上发表。

生成图表

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

Veys和她的合作者使用了一种称为“加拿大旅行者问题”(CTP)的图形表示形式，该问题的名称来源于沮丧的加拿大驾车者，当前方道路被雪堵塞时，他们必须掉头寻找新路线。

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

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

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

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

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

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

选择快捷方式

通过仅选择可能可穿越的捷径，该算法可以防止规划过程变得不必要的复杂。

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

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

未来，他们希望增强该算法，使其可以在二维以上工作，这可以使其用于复杂的机器人操纵问题。他们还对研究CTP图与这些图所代表的现实世界环境之间的不匹配感兴趣。

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