低精度算术使机器人定位更高效

通过为不同算术任务采用不同精度级别，可以在不影响性能的情况下减少计算负担。

同步定位与建图（SLAM）是自主移动机器人的核心技术。它涉及同时构建机器人环境地图并确定机器人在地图中的位置。SLAM计算密集，在资源受限的机器人（如消费级家用机器人）上部署通常需要使计算更易处理的技术。

其中一种技术是使用低精度浮点算术，即减少用于表示带小数点数字的位数。该技术在深度学习中很流行，将位数减半（从标准32位到16位）可使计算效率加倍，而对准确性影响很小。但将低精度算术应用于SLAM更为复杂。基于深度学习的分类模型是离散值的，而SLAM涉及解决具有连续值函数的非线性优化问题，需要更高的准确性。

某中心通过设计一种新颖的混合精度求解器来解决这个问题，该求解器结合了64位（fp64）、32位（fp32）和16位（fp16）精度，用于SLAM算法中的非线性优化问题。这一创新为更快、更环保的设备上导航铺平了道路。

通用框架

SLAM算法有两个关键组件：视觉里程计和闭环。视觉里程计基于最新观测实时估计机器人的位姿（即其在地图中的方向和位置）。当机器人识别出它到达了先前访问过的地方时，它通过全局校正其地图和位置估计来闭合循环。

视觉里程计和闭环都涉及解决非线性优化问题——分别是束调整（BA）和位姿图优化（PGO）。为了高效解决它们，SLAM系统通常使用近似方法，将它们重新构造为线性化优化问题的序列。如果目标是找到位姿估计x，那么每个线性问题最小化线性化误差函数，该函数是当前误差函数及其一阶校正的总和。一阶校正是雅可比矩阵（函数一阶导数的矩阵）与位姿估计更新的乘积。线性问题通常通过分解方法（如Cholesky或QR方法）解决。每个线性化优化问题的解是当前位姿估计的更新。

通用程序是从x的当前近似开始，计算误差函数和雅可比矩阵，解决线性优化问题，并相应地更新x，重复该过程直到满足某些停止标准。在每次迭代中，误差函数的值被称为残差，因为它是前一次迭代留下的残余误差。

在BA和PGO的非线性优化中，最昂贵的计算是雅可比矩阵的计算（约占总优化时间的15%）和线性问题的解决（约60%）。简单地从头到尾以半精度（fp16）解决任一问题会导致准确性降低，有时还会导致数值不稳定。

为了缓解这些困难，对矩阵进行正则化和缩放以避免溢出和秩不足。秩不足发生在雅可比矩阵的列线性相关时。通过仔细实验，进一步确定了需要在高于fp16的精度下进行的计算，并提出了一种混合精度非线性优化求解器。

发现为了匹配纯双精度解的准确性，以下两个组件必须在高于fp16的精度下计算：

• 残差必须在单精度或更高精度下评估；
• x的更新（一个六自由度位置-角度更新）必须在双精度下完成。

尽管这个通用优化框架适用于BA和PGO，但由于线性问题中矩阵的不同结构和属性，两个应用的细节各不相同。因此，提出了两种混合精度求解策略用于相关的线性系统。

视觉里程计

对于视觉里程计，传统上使用基于滤波器的方法，这些方法可能遭受较大的线性化误差。基于非线性优化的方法近年来变得更流行。这些方法通过最小化误差函数来估计机器人的位置和方向，误差函数是地标重投影与其在图像帧中观测之间的差异。这个过程称为束调整，因为正在调整一束光线以匹配投影与观测。

基于BA的视觉里程计在包含固定数量（关键）帧的滑动窗口上操作。平均而言，新的关键帧以10Hz到来。挑战是在给定的时间预算内解决BA问题。一种流行的方法是解决等同于线性化优化问题的正规方程；这涉及Hessian矩阵（残差的二阶导数矩阵）的近似。

BA问题涉及两组未知状态变量：一组指示机器人的位姿，另一组指示地标位置。减少BA问题计算负担的一种方法是将相机位姿和地标之间的约束边缘化，并首先关注相机位姿。在SLAM社区中，这个过程称为Schur消除或地标边缘化。

这个边缘化步骤可以大大减小需要解决的线性系统的大小。对于一个50帧的BA问题，雅可比矩阵通常大小为5,500 x 1,000，Hessian大小为1,000 x 1,000。解耦约束将线性系统的大小减小到300 x 300，小到足以用直接或迭代求解器解决。然而，这个策略需要Hessian矩阵的公式化和部分消除步骤，这些在实践中使用昂贵。

基于共轭梯度正规方程残差（CGNR）方法的混合精度线性求解器混合了单精度和半精度，这是一种直接应用于线性优化问题的迭代方法，无需显式公式化Hessian。

如在通用框架中，将所有计算简单转换为半精度会导致准确性降低。在实验中，发现如果在半精度下计算矩阵-向量乘积，并在单精度下进行所有其他操作，将保持SLAM管道的整体准确性。

矩阵-向量乘积是CGNR迭代中的主要计算，通常占计算成本的83%（就浮点操作次数而言）。这意味着，如果在NVIDIA V100 GPU上运行，混合精度求解器与单精度线性求解器相比可以节省至少41%的解决时间。

闭环

在SLAM管道中，来自视觉里程计的局部位姿估计通常表现出较大的漂移，尤其是在长期运行中。闭环校正这种漂移。

对于真实世界的地图估计，没有闭环校正，平均轨迹误差可能在0.1米量级，这在实践中不可接受。应用闭环校正后，该误差减小到10^-4米。

闭环调整涉及解决全局PGO问题。与BA问题一样，它是一个非线性优化问题，可以在相同的混合精度框架内解决。但来自PGO问题的线性系统比BA问题的线性系统大得多且更稀疏。

随着越来越多的循环闭合，问题大小可能从几百个位姿增长到几千个位姿。如果通过行数衡量矩阵的大小，在闭环期间，大小可能从100量级增长到10,000量级。在双精度下直接解决这种大小的稀疏矩阵具有挑战性，特别是考虑到设备上应用的时间和计算约束。对于真实世界的轨迹估计，PGO问题的解决时间可能长达八秒，且CPU使用率满负荷。

这导致设计PGO问题的混合精度求解器需要不同的策略。由于雅可比矩阵的稀疏性，混合精度方法仍然基于迭代CGNR方法。但为了加速CGNR迭代的收敛，在每次迭代中应用静态不完全Cholesky预条件子。Cholesky分解将对称线性系统分解为两个三角矩阵的乘积，意味着所有非零值集中在矩阵对角线的同一侧。这个分解步骤昂贵，因此只对整个问题执行一次。计算成本主要由预条件子的应用主导，这涉及解决两个三角系统。在时间分析中，这一步消耗每次线性解决中约50%的计算。

为了加速优化，不是在半精度下计算矩阵-向量乘积，而是在半精度下解决三角系统，保持所有其他操作在单精度下。使用这种混合精度求解器，几乎可以匹配全精度求解器的准确性，同时平均减少计算时间26%。

在视觉里程计和闭环应用中的结果表明，由于半精度算术的高效和低能耗特性，混合精度求解器可以使设备上SLAM更快、更环保。

致谢

以下人员对这项工作贡献相等：某硬件机构的应用科学家Tong Qin；某硬件机构的应用科学经理Sankalp Dayal；某设备机构的软件开发工程师Joydeep Biswas；某硬件机构的副总裁和杰出工程师Varada Gopalakrishnan；某设备机构的高级首席工程师Adam Fineberg；某硬件机构的软件、机器学习和移动高级经理Rahul Bakshi。