方法快速验证机器人是否能避免碰撞

在机器人从架子上拿起盘子摆放桌子之前，它必须确保它的抓手和手臂不会撞到任何东西，并可能打碎精美的瓷器。作为其运动规划过程的一部分，机器人通常会运行“安全检查”算法，以验证其轨迹是否无碰撞。

然而，有时这些算法会产生误报，声称当机器人实际与某物碰撞时，轨迹是安全的。对于现实世界中的机器人来说，其他可以避免误报的方法通常太慢了。

现在，麻省理工学院的研究人员开发了一种安全检查技术，可以100%准确地证明机器人的轨迹将保持无碰撞（假设机器人和环境的模型本身是准确的）。他们的方法非常精确，可以区分仅相差几毫米的轨迹，只需几秒钟即可提供证据。

但用户不需要相信研究人员的话——这种技术生成的数学证明可以通过相对简单的数学快速检查。

研究人员使用一种称为平方和编程的特殊算法技术实现了这一点，并对其进行了调整以有效解决安全检查问题。使用平方和编程使他们的方法能够推广到各种复杂的运动。

这种技术对于必须快速移动以避免在拥挤的物体空间中发生碰撞的机器人特别有用，例如商业厨房中的食物准备机器人。它也非常适合机器人碰撞可能导致伤害的情况，例如照顾虚弱患者的家庭健康机器人。

“通过这项工作，我们已经证明你可以用概念上简单的工具解决一些具有挑战性的问题。平方和编程是一个强大的算法思想，虽然它不能解决所有问题，但如果你谨慎地应用它，你可以解决一些非常不平凡的问题，“电气工程和计算机科学（EECS）研究生Alexandre Amice说。

Amice 与 EECS 研究生 Peter Werner 和资深作者 Russ Tedrake 一起发表了这篇论文，Russ Tedrake 是 EECS、航空航天和机械工程的丰田教授，也是计算机科学和人工智能实验室 （CSAIL） 的成员。这项工作将在机器人与自动化国际会议上发表。

安全认证

许多现有的检查机器人计划运动是否无碰撞的方法都是通过模拟轨迹并每隔几秒钟检查一次机器人是否撞到任何东西来实现的。但这些静态安全检查无法判断机器人是否会在中间几秒钟内与某物发生碰撞。

对于在几乎没有障碍物的开放空间中徘徊的机器人来说，这可能不是问题，但对于在狭小空间中执行复杂任务的机器人来说，几秒钟的运动可以产生巨大的影响。

从概念上讲，证明机器人不会发生碰撞的一种方法是举起一张纸，将机器人与环境中的任何障碍物分开。从数学上讲，这张纸被称为超平面。许多安全检查算法通过在单个时间点生成此超平面来工作。然而，每次机器人移动时，都需要重新计算一个新的超平面来执行安全检查。

取而代之的是，这项新技术生成了一个与机器人一起移动的超平面函数，因此它可以证明整个轨迹是无碰撞的，而不是一次工作一个超平面。

研究人员使用了平方和编程，这是一种算法工具箱，可以有效地将静态问题转化为函数。此函数是一个方程，用于描述超平面在计划轨迹中每个点的位置，以便保持无碰撞。

平方和可以推广优化程序，以找到一系列无碰撞的超平面。通常，平方和被认为是一种只适合离线使用的繁重优化，但研究人员已经证明，对于这个问题，它是非常有效和准确的。

“这里的关键是弄清楚如何将平方和应用于我们的特定问题。最大的挑战是提出最初的配方。如果我不想让我的机器人碰到任何东西，这在数学上意味着什么，计算机能给我一个答案吗？艾米斯说。

最后，顾名思义，平方和产生一个函数，该函数是几个平方值的总和。该函数始终为正数，因为任何数的平方始终为正值。

信任但要验证

Amice 解释说，通过仔细检查超平面函数是否包含平方值，人类可以很容易地验证该函数是否为正，这意味着轨迹是无碰撞的。

虽然该方法以完美的精度进行认证，但这假设用户拥有机器人和环境的准确模型;数学证明器与模型一样好。

“这种方法的一个非常好的地方是，证明真的很容易解释，所以你不必相信我编码正确，因为你可以自己检查它，”他补充道。

他们在仿真中测试了他们的技术，证明单臂和双臂机器人的复杂运动计划是无碰撞的。在最慢的情况下，他们的方法只需要几百毫秒就可以生成证明，这使得它比一些替代技术快得多。

“这一新结果提出了一种新的方法来证明机器人机械手的复杂轨迹是无碰撞的，优雅地利用数学优化的工具，变成令人惊讶的快速（和公开可用）软件。虽然尚未为杂乱环境中的快速轨迹规划提供完整的解决方案，但这一结果为进一步研究的几个有趣方向打开了大门，“特拉维夫大学计算机科学教授Dan Halperin说，他没有参与这项研究。

Amice说，虽然他们的方法足够快，可以在一些现实世界中用作最终的安全检查，但它仍然太慢，无法直接在机器人运动规划循环中实施，需要在几微秒内做出决定。

研究人员计划通过忽略不需要安全检查的情况来加速他们的过程，例如当机器人远离任何可能与之碰撞的物体时。他们还想尝试使用运行速度更快的专用优化求解器。

“由于在生成路线时做出的近似值不佳，机器人经常会因为刮擦障碍物而陷入困境。Amice、Werner 和 Tedrake 通过一种强大的新算法来救援，通过仔细利用计算代数几何的先进方法，快速确保机器人永远不会越界，“芬兰奥卢大学信息技术和电气工程学院教授 Steven LaValle 补充道，他没有参与这项工作。

这项工作在一定程度上得到了亚马逊和美国空军研究实验室的支持。