当Vasileios Tzoumas，一位在麻省理工学院(麻省理工学院)，访问一个新的城市，他喜欢去跑步探索。有时他会迷路。几年前，在大阪参加一个长期会议时，不可避免的事情发生了。但后来Tzoumas发现了一家7- 11便利店，他记得这是他离开酒店后不久经过的。这种认知让他在精神上“闭合了回路”，将他的轨迹松散的一端连接到他知道并确信的某个地方，从而巩固了他的心理地图，让他能够走回酒店。
梯度非凸度(GNC)算法可以帮助机器穿越陆地、水、天空和太空，然后返回来讲述故事。
闭合循环实际上是一个技术术语，指的是机器人在新环境中导航时经常要做的事情。这是一个叫做同步定位和绘图(SLAM)．Slam并不新鲜。它用于机器人吸尘器，自动驾驶汽车，搜索和抢救空中无人机，以及工厂，仓库和矿山的机器人。作为自主设备和车辆导航新空间，从起居室到天空，他们在旅行时构建地图。它们还必须弄清楚它们在地图上使用相机，GPS和LIDAR等传感器。
随着SLAM的应用越来越多，确保SLAM算法在具有挑战性的现实环境中产生正确的结果比以往任何时候都更加重要。SLAM算法通常在完美的传感器或受控的实验室条件下工作得很好，但在现实世界中使用不完美的传感器时，它们很容易丢失。不出所料，工业客户经常担心他们能否信任这些算法。
麻省理工学院的研究人员已经开发了几个健壮的SLAM算法，以及数学上证明我们有多信任它们的方法。麻省理工学院莱昂纳多职业发展助理教授卢卡·卡隆的实验室，发表了一篇论文关于它们渐变的非凸性（GNC）算法，从而减少了SLAM结果中的随机误差和不确定性。更重要的是，该算法产生正确的结果，其中现有方法“丢失”。本文，由Carlone，Tzoumas和Carlone的学生衡阳和Pasquale Antonante，在机器人和自动化国际会议（ICRA）中获得了机器人愿景的最佳纸张奖。该GNC算法将有助于机器穿越陆地，水，天空和空间 - 并回来讲述故事。
一切都保持一致
机器人的感知依赖于传感器，这些传感器经常提供噪声或误导性的输入。麻省理工学院的GNC算法允许机器人决定哪些数据点可以信任，哪些数据点可以丢弃。其中调用了GNC算法的一个应用形状对齐．机器人利用2D摄像机图像估计汽车的3D位置和方向。机器人接收到摄像机图像，图像上有许多点，由特征检测算法标记:前灯、车轮、后视镜。它的内存中还有一个汽车的3D模型。目标是缩放、旋转和放置3D模型，使其特征与图像中的特征对齐。“如果特征检测算法完美地完成了它的工作，这是很容易的，但很少是这样的，”Carlone说。在实际应用中，机器人会面临许多异常值(错误标记的特征)，这些异常值可能占所有观测值的90%以上。这就是GNC算法胜出并超越所有竞争对手的原因。
机器人使用数学函数解决此问题，该函数考虑了每对特征之间的距离 - 例如，图像中的右前灯和模型中的正确前灯。他们试图“优化”这个功能 - 以定向模型，以便最小化所有距离。功能越多，问题越难。
解决这个问题的一种方法是尝试函数的所有可能的解，看看哪一个最有效，但有太多的方法可以尝试。金宝搏官方网站杨和安东内特解释说，一个更常见的方法是“尝试一种解决方案，并不断推动——比如，使模型中的前照灯与2D图像中的前照灯更一致——直到你无法再改进它。”考虑到嘈杂的数据，它不会是完美的——也许前灯对齐了，但车轮不对齐——所以你可以重新开始另一个解决方案，并尽可能地完善它，重复这个过程几次，以找到最好的结果。不过，找到最佳解决方案的可能性很小。
在实际应用中，机器人面临许多异常值，这些异常值可能占所有观测值的90%以上。这就是GNC算法胜出并超越所有竞争对手的原因。
GNC算法能在噪声测量值高达70-90%的情况下找到最优对齐。图片来源:麻省理工学院。
GNC背后的想法是首先简化问题。它们减少了他们尝试优化的功能 - 将3D模型与2D图像之间的差异的函数与单一最佳解决方案进行了优化。现在，当他们选择一个解决方案并轻推它时，他们最终会发现最好的解决方案。然后他们重新引入了一点原始功能的复杂性并改进了他们刚发现的解决方案。他们继续这样做，直到它们具有原始功能及其最佳解决方案。前灯良好对齐，轮子和保险杠也是如此。
在圈子里
本文将GNC算法应用于形状对齐和SLAM等问题。在SLAM中，机器人使用传感器数据来计算过去的轨迹，并建立地图。例如，一个在大学校园里漫游的机器人会收集里程表数据，显示它在 早上8点之间走了多远和方向。和15 点。之间,15 点。和8:30 点。，等等。它还拥有上午8点 的激光雷达和摄像机数据。, 15 点。，等等。偶尔，它会完成循环，在两个不同的时间看到同样的事情，就像Tzoumas再次跑过7- 11便利店时所做的那样。
研究人员发现，GNC算法比最先进的技术更精确，可以处理更高比例的异常值。
就像形状对齐一样，还有一个优化问题需要解决。杨是这篇论文的第一作者，他解释说:“对于SLAM，系统不是通过排列特征来匹配3D模型，而是弯曲它认为它穿过的轨迹，以便在地图上对齐物体。”首先，该系统的工作原理是尽量减小不同传感器感知行程的差异，因为每个传感器在测量时都可能存在误差。例如，如果机器人的里程表显示它在 上午8点之间走了100米。和15 点。在美国，基于激光雷达和相机测量更新的轨迹应该反映出这个距离，或接近这个距离的东西。该系统还将看起来相同的地点之间的距离最小化。如果机器人在 早上8点看到了同一家便利店。和10点 点。，该算法将尝试弯曲被召回的轨迹——调整每条腿——以便在上午8:00 时被召回的位置。 and 10:00 a.m. align, closing the loop.
测绘建筑物内部的机器人。GNC逐渐揭开杂乱的数据。在相对较少的步骤中，算法得到了一个建筑物内部的精确地图。图片来源:麻省理工学院。
同时，该算法识别并丢弃异常值的数据点，它认为它正在重新撤回其步骤，但它不像形状对齐中的误标定功能一样。你不想诬陷一个循环。Tzoumas回忆起一次，穿过缅因州的树林，当他跑过一系列看起来熟悉的堕落树干。他认为他已经关闭了循环，并使用这个假设的地标，他轮到了。只有在没有看到别人熟悉20分钟后，他才怀疑他的错误并回头。
优化前的召回轨迹可能看起来像一个缠结的麻线球。在解开后，它类似于镜像机器人遍历的校园途径和走廊形状的一套右倾角线。这个奴役过程的技术术语是姿态图优化．
在本文中，研究者比较了他们的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所说，“它能帮助你走出困境。”
