当Vasileios Tzoumas，一位研究科学家麻省理工学院(麻省理工学院)，访问一个新的城市，他喜欢去跑步探索。有时他会迷路。几年前，在大阪参加一个长期会议时，不可避免的事情发生了。但后来Tzoumas发现了一家7- 11便利店，他记得这是他离开酒店后不久经过的。这种认知让他在精神上“闭合了回路”，将他的轨迹松散的一端连接到他知道并确信的某个地方，从而巩固了他的心理地图，让他能够走回酒店。
分级非凸性（GNC）算法可以帮助机器穿越陆地、水、天空和空间，然后回来讲述故事。
关闭循环实际上是机器人在导航新环境时经常要做的东西的技术术语。它是一个名为的过程的一部分同步定位和映射（SLAM）．SLAM并不是什么新事物。它被用于机器人真空吸尘器、自动驾驶汽车、搜救无人机以及工厂、仓库和矿山的机器人。随着自动驾驶设备和车辆导航到新的空间，从客厅到天空，它们在旅行时构建了一张地图。他们还必须利用相机、GPS和激光雷达等传感器来确定自己在地图上的位置。
随着SLAM得到越来越多的应用，确保SLAM算法在具有挑战性的现实世界条件下产生正确的结果比以往任何时候都更加重要。SLAM算法通常在完美的传感器或受控的实验室条件下运行良好，但在现实世界中使用不完美的传感器时很容易丢失。毫不奇怪，工业RIA客户经常担心他们是否能够信任这些算法。
麻省理工学院的研究人员开发了几种强大的庞大算法，以及数学上的方法，以便我们能够相信多少。Luca Carlone的实验室，Leonardo Career Development Assistant Partury Mit教授，发表论文该算法降低了SLAM结果的随机误差和不确定性。更重要的是，算法能在现有方法“迷失”的地方产生正确的结果。这篇由Carlone、Tzoumas和Carlone的学生Yang Heng和Pasquale Antonante撰写的论文在国际机器人与自动化会议(ICRA)上获得了机器人视觉领域的最佳论文奖。这种GNC算法将帮助机器穿越陆地、水域、天空和太空，然后再回来讲述故事。
一切都对齐了
机器人的感知依赖于传感器，这些传感器通常提供嘈杂或误导性的输入。麻省理工学院的GNC算法允许机器人决定哪些数据点值得信任，哪些数据点需要丢弃。GNC算法的一个应用程序称为形状对齐．机器人使用2D相机图像估计汽车的3D位置和方向。机器人接收具有通过特征检测算法标记的许多点的摄像机图像：前灯，轮子，镜子。它还具有内存中的汽车3D模型。目标是缩放，旋转，并放置3D模型，因此其功能与图像中的功能对齐。“如果特征检测算法完美地完成了这项工作，这很容易，但这很少是这种情况，”卡莱尔说。在实际应用中，机器人面临许多异常值误标定的特征 - 这可以占所有观察的90％以上。这就是GNC算法进入并优于所有竞争对手的地方。
机器人使用一个数学函数来解决这个问题，该函数考虑到每一对特征之间的距离，例如，图像中的右前照灯和模型中的右前照灯。他们试图“优化”这个函数——以使模型的方向最小化所有这些距离。特性越多，问题就越难解决。
解决问题的一种方法是尝试所有可能的解决方案，并查看哪一个最佳工作，但有太多尝试。金宝搏官方网站一种更常见的方法，杨和antonante解释说：“是尝试一种解决方案并继续努力制作，说，模型中的前灯与2D图像中的前灯相一致 - 直到你不能再改善它了。”给出嘈杂的数据，它不会是完美的 - 也许前灯对齐，但车轮没有 - 所以你可以用另一个解决方案开始并尽可能地改进一个，重复几次过程以找到最佳结果。尽管如此，寻找最佳解决方案的机会纤细。
在实际应用中，机器人面临许多异常值，这些异常值可以占所有观测值的90%以上。这就是GNC算法的优势所在，它的性能优于所有竞争对手。
GNC算法可在噪声测量值高达70–90%异常值的情况下找到最佳对齐方式。图片来源：麻省理工学院。
GNC背后的想法是首先简化问题。他们将试图优化的功能——描述3D模型和2D图像之间差异的功能——简化为只有一个最佳解决方案的功能。现在，当他们选择一个解决方案并推动它时，他们最终会找到最好的解决方案。然后他们重新引入一些原始功能的复杂性，并完善他们刚刚找到的解决方案。他们一直这样做直到得到原始函数及其最优解。车头灯对齐得很好，车轮和保险杠也是。
兜圈子
该论文将GNC算法应用于形状对齐和SLAM等问题。在SLAM的情况下，机器人使用传感器数据计算其过去的轨迹并绘制地图。例如，在大学校园漫游的机器人收集里程计数据，表明它在8:00之间走了多远，朝哪个方向走 a、 上午8点15分 a、 上午8点15分之间 a、 上午八点半到八点半 a、 它还有8点的激光雷达和摄像机数据 a、 上午8点15分 a、 偶尔，它会完成循环，在两个不同的时间看到相同的东西，就像祖马斯再次跑过7-11一样。
研究人员发现，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逐渐脱离杂乱数据。在相对较少的步骤中，该算法到达建筑物内部的准确图。图像信用：麻省理工学院。
与此同时，算法识别并丢弃异常值——它认为是在回溯自己的步骤，但并非如此的坏数据点——就像形状对齐时标签错误的特征一样。你不想错误地闭合一个循环。祖马斯回忆说，有一次他在缅因州的树林里跑步，经过一堆倒下的树干，看起来很熟悉。他以为他已经完成了循环，然后利用这个所谓的路标，他转了个弯。直到20分钟没有看到任何熟悉的东西后，他才怀疑自己的错误，并返回。
在优化之前被召回的轨迹可能看起来像一个缠结在一起的线球。解开后，它就像一组直角线，反映了机器人穿过的校园通道和走廊的形状。这种SLAM过程的技术术语是构成图优化．
在这篇论文中，研究人员将他们的GNC算法与其他算法在一些应用上进行了比较，包括形状对齐和姿势图优化。他们发现，他们的方法比最先进的技术更精确，可以处理更高百分比的异常值。对于SLAM，即使使用三合四的循环闭包，它也能工作e错了，这比在实际应用中遇到的异常值要多得多。此外，他们的方法通常比其他算法更有效，需要更少的计算步骤。Tzoumas说，“困难之一是找到一种在许多应用中都能很好地工作的通用算法。”杨说，他们已经在10多个地方试用过。祖马斯说，最后，他们找到了“最佳点”
MATLAB根据机器人割草时的数据生成地图。左：草坪原始地图。中：使用常见SLAM算法优化的地图，其中包括来自未知异常值循环闭包的错误标记数据。右：使用GNC算法优化的地图。
MathWorks的机器人研究科学家罗伯托·g·瓦伦蒂(Roberto G. Valenti)说，从研究到生产是研究成果大规模产生影响的重要一步。MathWorks一直在与Carlone的实验室合作，将GNC算法集成到MATLAB中，作为导航工具箱™的一部分，公司使用该工具箱在商业和工业自动化系统中实现SLAM。
脱离险境
Carlone的实验室正在研究扩展GNC算法能力的方法。例如，杨的目标是设计能够被证明是正确的感知算法。安东南特正在寻找方法来管理不同算法之间的不一致性：如果自动驾驶汽车的SLAM模块说道路笔直，但车道检测模块说它向右转弯，那么你就有问题了。
GNC算法是允许机器人捕捉自己错误的新基准。
Tzoumas正在研究如何扩大规模，不仅是一个机器人的多个算法之间的互动，而且是多个机器人之间的协作。在早期的工作中，他对无人机进行了编程，以跟踪目标，比如试图步行或开车逃跑的罪犯。未来，多台机器可能会共同运行GNC算法。每一个都将向它的邻国提供部分信息，它们将共同构建一个全球地图——包括地球或其他地方的位置。今年，他将转到密歇根大学航空航天工程系，致力于多机器人规划和自主导航的可靠自主研究——即使是在战场和其他星球这样的艰难环境中。
安东南特说：“不知道人工智能和感知算法将如何运行是使用它们的一个巨大障碍。”他指出，如果博物馆的机器人导游有可能撞上游客或《蒙娜丽莎》，他们将不被信任：“你希望你的系统对其环境和自身都有深入的了解，这样它就能捕捉到自己的错误。”GNC算法是允许机器人捕捉自己错误的新基准，最重要的是，正如祖马斯所说，“它帮助你走出困境。”
