低精度算法提升机器人定位效率
同步定位与地图构建（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，某中心硬件软件、机器学习和移动高级经理。