当Vasileios Tzoumas，一位在麻省理工学院(麻省理工学院)，访问一个新的城市，他喜欢去跑步探索。有时他会迷路。几年前，在大阪参加一个长期会议时，不可避免的事情发生了。但后来Tzoumas发现了一家7- 11便利店，他记得这是他离开酒店后不久经过的。这种认知让他在精神上“闭合了回路”，将他的轨迹松散的一端连接到他知道并确信的某个地方，从而巩固了他的心理地图，让他能够走回酒店。
渐变的非凸起（GNC）算法可以帮助机器穿越陆地，水，天空和空间 - 并回来讲述故事。
闭合循环实际上是一个技术术语，指的是机器人在新环境中导航时经常要做的事情。这是一个叫做同步定位和绘图(SLAM)．SLAM并不是什么新事物。它被用于机器人真空吸尘器、自动驾驶汽车、搜救无人机以及工厂、仓库和矿山的机器人。随着自动驾驶设备和车辆导航到新的空间，从客厅到天空，它们在旅行时构建了一张地图。他们还必须利用相机、GPS和激光雷达等传感器来确定自己在地图上的位置。
随着SLAM发现更多的应用，它比以往任何时候都更重要，以确保SLAM算法产生正确的结果挑战真实世界的条件。SLAM算法通常使用完美的传感器或受控实验室条件，但在现实世界中的不完美传感器实施时，它们很容易丢失。不出所料，工业客户经常担心他们是否可以信任这些算法。
麻省理工学院的研究人员已经开发了几个健壮的SLAM算法，以及数学上证明我们有多信任它们的方法。麻省理工学院莱昂纳多职业发展助理教授卢卡·卡隆的实验室，发表了论文该算法降低了SLAM结果的随机误差和不确定性。更重要的是，算法能在现有方法“迷失”的地方产生正确的结果。这篇由Carlone、Tzoumas和Carlone的学生Yang Heng和Pasquale Antonante撰写的论文在国际机器人与自动化会议(ICRA)上获得了机器人视觉领域的最佳论文奖。这种GNC算法将帮助机器穿越陆地、水域、天空和太空，然后再回来讲述故事。
一切都保持一致
机器人的感知依赖于传感器，这些传感器经常提供噪声或误导性的输入。麻省理工学院的GNC算法允许机器人决定哪些数据点可以信任，哪些数据点可以丢弃。其中调用了GNC算法的一个应用形状对齐．机器人利用2D摄像机图像估计汽车的3D位置和方向。机器人接收到摄像机图像，图像上有许多点，由特征检测算法标记:前灯、车轮、后视镜。它的内存中还有一个汽车的3D模型。目标是缩放、旋转和放置3D模型，使其特征与图像中的特征对齐。“如果特征检测算法完美地完成了它的工作，这是很容易的，但很少是这样的，”Carlone说。在实际应用中，机器人会面临许多异常值(错误标记的特征)，这些异常值可能占所有观测值的90%以上。这就是GNC算法胜出并超越所有竞争对手的原因。
机器人使用一个数学函数来解决这个问题，该函数考虑到每一对特征之间的距离，例如，图像中的右前照灯和模型中的右前照灯。他们试图“优化”这个函数——以使模型的方向最小化所有这些距离。特性越多，问题就越难解决。
解决这个问题的一种方法是尝试函数的所有可能的解，看看哪一个最有效，但有太多的方法可以尝试。万博 尤文图斯杨和安东内特解释说，一个更常见的方法是“尝试一种解决方案，并不断推动——比如，使模型中的前照灯与2D图像中的前照灯更一致——直到你无法再改进它。”考虑到嘈杂的数据，它不会是完美的——也许前灯对齐了，但车轮不对齐——所以你可以重新开始另一个解决方案，并尽可能地完善它，重复这个过程几次，以找到最好的结果。不过，找到最佳解决方案的可能性很小。
在实际应用中，机器人面临许多异常值，这些异常值可能占所有观测值的90%以上。这就是GNC算法胜出并超越所有竞争对手的原因。
GNC算法能在噪声测量值高达70-90%的情况下找到最优对齐。图片来源:麻省理工学院。
GNC背后的想法是首先简化问题。他们将试图优化的功能——描述3D模型和2D图像之间差异的功能——简化为只有一个最佳解决方案的功能。现在，当他们选择一个解决方案并推动它时，他们最终会找到最好的解决方案。然后他们重新引入一些原始功能的复杂性，并完善他们刚刚找到的解决方案。他们一直这样做直到得到原始函数及其最优解。车头灯对齐得很好，车轮和保险杠也是。
进入圈子
本文应用GNC算法以形状对齐并猛击其他问题。在SLAM的情况下，机器人使用传感器数据来弄错其过去的轨迹并构建地图。例如，在大学校园周围漫游的机器人收集了测量的数据，表明它在上午8点到上午8:15之间有多远和方向。和上午8:15之间，上午8:30。等等。它还在上午8点上午8点拥有LIDAR和相机数据。，上午8:15。等等。偶尔，它将完成循环，在两次不同的时间看到同样的事情，就像Tzoumas一样，当他再次跑过7-Eleven时。
研究人员发现，GNC算法比最先进的技术更准确，并且可以处理更高百分比的异常值。
就像形状对齐一样，有一个要解决的优化问题。杨是纸上的第一个作家，解释说：“对于猛烈，而不是排列的功能来匹配3D模型，而是弯曲轨迹它认为它遍历地图上的对象。”首先，该系统可用于最小化不同传感器的感知行程之间的差异，因为每个传感器可能在测量中具有错误。例如，如果机器人的里程表显示它在上午8点之间旅行100米。和上午8:15，基于激光雷达和相机测量更新的轨迹应该反映该距离，或靠近它的东西。该系统还会最大限度地减少似乎在位置之间的位置之间的距离。If the robot saw the same 7-Eleven at 8:00 a.m. and 10:00 a.m., the algorithm will try to bend the recalled trajectory—adjusting each leg—so that its recalled positions at times 8:00 a.m. and 10:00 a.m. align, closing the loop.
测绘建筑物内部的机器人。GNC逐渐揭开杂乱的数据。在相对较少的步骤中，算法得到了一个建筑物内部的精确地图。图片来源:麻省理工学院。
同时，该算法识别并丢弃异常值不好的数据点，以至于它认为它正在重新定步其步骤，但它不像形状对齐中的误标定功能一样。你不想诬陷一个循环。Tzoumas召回了一段时间，跑过缅因州的树林，当他跑过一系列看起来熟悉的堕落树干。他认为他已经关闭了循环，并使用这个假设的地标，他轮到了。只有在没有看到其他任何熟悉20分钟后，他才怀疑他的错误并回头。
在优化之前被召回的轨迹可能看起来像一个缠结在一起的线球。解开后，它就像一组直角线，反映了机器人穿过的校园通道和走廊的形状。这种SLAM过程的技术术语是姿态图优化．
在本文中，研究人员将其GNC算法与其他算法进行了若干应用，包括形状对准和姿势图优化。他们发现它们的方法比最先进的技术更准确，并且可以处理更高百分比的异常值。对于Slam，即使四个循环关闭中的三个误，它也会弄错了，这比在现实世界中遇到了更多的异常值。更重要的是，它们的方法通常比其他算法更有效，需要更少的计算步骤。Tzoumas说：“其中一个困难是在许多应用程序中找到良好的通用算法。”杨说他们已经尝试了超过10.到底，Tzoumas说，他们发现了“甜蜜的地方”。
MATLAB生成的地图从源自草坪的机器人派生的数据创建的地图。左：草坪的原始地图。中间：用公共SLAM算法进行优化地图，其包括来自未知异常循环闭环的错误标记数据。右：用GNC算法进行优化地图。
来自Mathworks的机器人研究科学家Roberto G. Valenti表示，从研究开始研究是研究结果的重要一步。MathWorks一直与Carlone的实验室合作，将GNC算法集成到Matlab中作为导航工具箱™的一部分，该公司用于在商业和工业自治系统上实施Slam。
走出树林
Carlone的实验室正在研究如何扩展GNC算法的功能。例如，杨的目标是设计能够被证明是正确的感知算法。Antonante正在寻找管理不同算法之间不一致性的方法:如果自动驾驶汽车上的SLAM模块说道路是直的，但车道检测模块说它是右弯的，那就有问题了。
GNC算法是允许机器人发现自己错误的新基准。
Tzoumas正在研究如何扩大规模，不仅是一个机器人的多个算法之间的互动，而且是多个机器人之间的协作。在早期的工作中，他对无人机进行了编程，以跟踪目标，比如试图步行或开车逃跑的罪犯。未来，多台机器可能会共同运行GNC算法。每一个都将向它的邻国提供部分信息，它们将共同构建一个全球地图——包括地球或其他地方的位置。今年，他将转到密歇根大学航空航天工程系，致力于多机器人规划和自主导航的可靠自主研究——即使是在战场和其他星球这样的艰难环境中。
Antonante说:“不知道人工智能和感知算法将如何表现是使用它们的一个巨大障碍。”他指出，如果机器人博物馆导游有可能撞到游客或蒙娜丽莎，那么他们就不会被信任:“你希望你的系统对环境和自身都有深刻的了解，这样它就能发现自己的错误。”GNC算法是允许机器人发现自己错误的新基准，最重要的是，正如Tzoumas所说，“它能帮助你走出困境。”
