Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration
本文介绍了中心路径认证器（Central-Path Certifier, CP-Cert），这是一种通过引导候选解沿中心路径进行运动，从而克服半正定规划松弛中退化问题，以快速验证全局最优性的高效方法，它实现了一个快速且可扩展的抗离群值位姿估计流水线，其性能比最先进的求解器快了高达三个数量级。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在现实世界中导航的机器人依赖于不断的感官数据流来理解自身的位置和周围环境的形状。为了构建地图或寻找位置，机器人必须解决一个复杂的谜题：它从摄像头获取一团点云，并试图将其与已知地图进行对齐。这个过程被称为位姿配准（pose registration），在数学上非常困难，因为可能解的景观中充满了陷阱。计算机很容易找到一个看起来正确但实际上错误的局部解，导致机器人误以为自己处于错误的位置。几十年来，工程师们一直依赖巧妙的猜测来正确启动这一过程，寄希望于计算机能找到真正的答案。然而，在涉及安全的关键应用中，仅仅依靠“希望”是不够的。该领域最近开发出了能够从数学上证明某个解是最佳解的方法，但这些证明对于实时使用来说速度太慢，尤其是在数据混乱或包含误差的情况下。
多伦多大学的一个研究小组引入了一种新方法，填补了这一空白，使机器人即使在数据不完美的情况下，也能快速验证其解是否为全局最优。他们的方法被称为 CP-Cert，旨在处理一种此前曾减缓这些验证过程速度的特定数学难题。在许多机器人问题中，用于证明最优性的数学松弛（mathematical relaxation）会变得“退化”（degenerate），这意味着用于检查答案的标准工具会陷入停滞或产生歧义的结果。研究人员发现了一种绕过这种退化的方法，即在解空间中寻找一条特定的、表现良好的路径。通过从一个候选解开始，并沿着这条路径轻轻移动，他们无需从头开始解决整个问题，即可提取出最优性证书。这使得系统能够在毫秒级时间内确认机器人的计算位置是最佳可能的解，而不仅仅是一个幸运的猜测。
研究人员将这种新的验证器应用于两个不同但相关的挑战：在两个 3D 扫描之间进行点匹配，以及通过配准这些扫描来确定机器人的位置。第一个挑战是数据关联（data association），本质上是决定一个点云中的哪个点对应于另一个点云中的哪个点。当机器人扫描场景时，它经常多次看到同一个物体，或者看到看起来像物体的噪声。团队将此建模为一个寻找最大且最一致的连接组的问题，即最大团问题（maximum clique problem）。他们开发了一个新的数学框架，用以证明机器人选择的连接组确实是最佳可能的集合，从而过滤掉由离群值或噪声引起的错误匹配。
一旦正确匹配了点，第二步就是计算对齐两个点云所需的精确运动。团队将他们的新验证器与矩阵加权法相结合，该方法考虑到了 3D 扫描中某些点比其他点更具不确定性的事实。通过验证匹配和对齐这两个步骤的最优性，他们创建了一个既对误差具有鲁棒性又具有数学保证的完整流水线。在利用模拟数据进行的测试中，这种新方法比现有技术快得多。虽然最先进的直接求解器在验证适中数量的点时可能需要数秒甚至数分钟，但新方法完成了同样的工作却仅用了毫秒级时间，实现了高达千倍的速度提升。这种性能提升使得在实时机器人应用中使用严谨的数学保证成为可能，而这在以前被认为计算成本过于昂贵。
研究人员不仅在计算机模拟上验证了他们的系统，还在从立体相机系统收集的真实世界数据上进行了验证。他们证明了该流水线能够成功处理嘈杂的现实环境，并依然能产生经过验证的全局最优解。这项工作强调了在机器人领域中，速度与确定性是可以兼得的。通过避免每次都从头开始解决整个复杂的难题，而是利用机器人的最佳猜测作为起点来寻找证书，该团队展示了我们可以信任自主系统，使其知道何时找到了正确答案。这项进展消除了现代机器人软件栈中的一个重大漏洞，确保当机器人声称知道自己在哪里时，这一说法是由数学证明而非充满希望的近似值所支撑的。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。