HD地图的可扩展图形SLAM

HD地图的可扩展图形SLAM

　　相关申请的交叉引用

　　本申请要求Irion等人于2018年2月23日提交的题为“SCALABLE GRAPH SLAM FOR HDMAPS”的美国临时申请序列号62/634,327的优先权，所述美国临时申请的公开内容特此通过引用以其整体并入本文中。

　　技术领域

　　本公开涉及用于解决图形SLAM问题的系统和方法，并且特别地涉及用于解决HD地图的图形SLAM问题的系统和方法。

　　背景技术

　　图形SLAM的目标是要找到使如下代价函数最小化的姿态集合

　　

　　其中。这典型地以迭代的方式来解决，由此每次迭代k需要近似代价函数，从而找到最优的姿态更新集合，并且经由下式（2）来计算下一个姿态集合

　　

　　其中标示姿态合成操作符。让d标示姿态更新的维数（即）。将（2）代入（1），我们将误差的梯度和黑塞（Hessian）矩阵计算为

　　。

　　通过将边如下线性化来获得更新

　　

　　并且代入（3），得到二次近似

　　

　　这通过下式（8）被最小化

　　。

　　大多数先前已知的解算器在单个节点上迭代求解该线性系统。然而，这样的单节点解算器并不很好地适应建图区的大小。这使对于用来为更大的区域构建HD地图的可扩展系统和算法的需要成为必需。

　　发明内容

　　根据本公开的一个实施例，一种使用计算系统解决HD地图的图形同时定位和建图（图形SLAM）的方法包括将图形分区成多个子图，所述子图中的每个具有图形的所有顶点以及图形的边的子集。定义子图的受约束顶点和非约束顶点。使用分区的图形定义图形SLAM的交替方向乘子法（ADMM）公式。然后，基于ADMM公式，根据受约束顶点和非约束顶点定义分布式图形SLAM算法。然后使用分布式图形SLAM算法来解决针对HD地图的图形SLAM问题。

　　附图说明

　　图1（a）示出了如何定义图形的子图和的顶点；

　　图1（b）示出了子图和的受约束顶点；

　　图2是用于实现本文中所述的HD地图的分布式图形SLAM算法的计算系统的示意性描绘。

　　具体实施方式

　　出于促进对本公开原理的理解的目的，现在将参考在附图中图示并且在以下书写的说明书中描述的实施例。应当理解，并不旨在由此对本公开的范围进行限制。应当进一步理解，本公开包括对所图示实施例的任何变更和修改，并且包括如本公开所属领域的普通技术人员通常将想到的本公开原理的进一步的应用。

　　存在可用于大规模计算和存储的各种框架。这样的框架可以宽泛地被分类为；

　　a.单节点内存系统，其中整个数据在单个计算机的存储器中被加载和处理；

　　b.磁盘中系统，其中整个数据驻留在磁盘中，并且大块数据在存储器中被加载和处理。尽管不存在许多采用该方法来解决（1）的可用工具，但是大多数单节点解决方案可以通过标准计算平台中可用的标准磁盘中能力进行扩展。例如，MATLAB中的内存映射文件（memmapfile），Python中的内存映射（mmap），等；

　　c.数据库中系统，其中数据存储在数据库中，并且处理被带到数据驻留在其中的数据库；

　　d.分布式存储装置和计算系统，其中数据驻留在多个节点中，并且计算分布在那些节点之中。典型的框架牵涉Hadoop、Apache Spark（分布式内存分析，其存储在HDFS上）。

　　在一个实施例中，具有存储在HDFS中的数据的Apache Spark计算框架被用于实现可扩展的图形SLAM系统。这提供若干个优点。首先，与现有的基于单节点的解决方案相比，分布式架构允许对大规模建图的计算进行扩展。进一步地，与像Hadoop的其它分布式解决方案相比，Spark提供了具有延迟执行的分布式内存计算。这使得它与需要将所有中间数据写入磁盘的Hadoop（映射-归约（Map-Reduce））相比是非常快速并且具有容错性的，尤其对于迭代任务而言。在替代实施例中，可以使用任何合适的计算框架。

　　利用这样的分布式架构必需采用能够大规模处置问题（1）的先进优化算法。基本上，（1）中的问题需要迭代地求解二次规划（QP）。最近对于在分布式环境中解决这样的QP的研究典型地采用以下方法中的一个：

　　a.一阶方法，其使用来自目标的一阶信息，像梯度估计、割线近似等。这样的方法招致低的每次迭代计算复杂度，并且提供了独立于维数的收敛性。然而，收敛速率在很大程度上取决于对步长的选择和问题的条件性；

　　b.二阶方法，其使用附加的曲率信息，像黑塞（或像L-BFGS之类的近似），并且改进了问题的条件性。这样的方法提供了提高的收敛速率，但导致更坏的每步计算成本；

　　c.随机化算法，其使用原始大规模数据的二次抽样或低秩表示来解决小规模等价问题。

　　另一类更广泛的算法采用拆分技术，其将目标函数解耦成更小的子问题，并且迭代地对它们求解。所得到的子问题是更容易解决的，并且可以使用上面讨论的方法以分布式方式容易地解决。一些这样的流行算法是近端梯度法、近端（拟）牛顿法、交替方向乘子法（ADMM）等。在这些方法中，已经广泛地采用ADMM来解决若干个大规模的实际问题。为了利用问题的结构，定制了对ADMM的若干种适配。非常适合于并行和分布式环境的一个这样的版本是一致性ADMM。

　　一致性ADMM以其基本形式解决了以下问题：

　　

　　服从。

　　一致性ADMM步骤是

　　

　　这里，。

　　注意的是，这样的形式非常适合于在Spark中使用映射-归约范例的分布式环境。在这种情况下，w步骤牵涉将计算分布（映射）在若干个节点之上。并且（一致性）z-步骤牵涉在主节点处聚集（归约）分布式计算。进一步地，对于（1），更新需要闭式解，并且可以使用标准线性解算器来被高效地计算。虽然（10）保证收敛，但是算法的收敛速率很大程度上取决于问题（1）的条件性和参数的选择。

　　为了利用用于图形SLAM的一致性ADMM，将图形分成一组子图，其中每个子图包括多个顶点，使得，并且如果，则边的集合满足并且。定义

　　。

　　观察到梯度和黑塞矩阵分别由下式给出

　　。

　　在的条件下，观察到（17）等于（7）。因此，我们的用于图形SLAM的一致性ADMM公式是

　　

　　服从，并且所得到的超松弛ADMM更新是

　　

　　

　　此后，ADMM变量、z和u上的上标k将被省略，并且应当理解的是，ADMM迭代作为第k次图形SLAM迭代的一部分来执行。

　　虽然每个子图都包含所有的N个顶点（即，），但是它仅包含边的子集（即，）。考虑到这一点，我们定义了三种不同的顶点类（参见图1a的图示）。

　　1）子图的受约束顶点是受至少一条边约束的顶点。让标示子图中受约束顶点的数量。对应于受约束顶点的和中的条目分别被标示为和，并且中的对应条目和中的行/列由和标示。更进一步地，让标示对子图中受约束条目进行下采样的矩阵（即，和）。

　　2）子图的非约束顶点是不受中任何边约束的顶点，让标示对子图中非约束条目进行下采样的矩阵。让标示由中的非约束条目假定的值；换言之，对于所有s，。

　　3）当对图形进行分区时，每个顶点被指定为恰好一个子图的原生（native）顶点，对于该子图它是受约束顶点；当多个子图包含约束顶点的边时，必须决定选取它的原生子图。标示对于子图而言是原生的顶点的集合。

　　图1中描绘了图形分区的简化示例。图G被分区成子图和。图形G包括四列和四行。参考图1（b），第一子图贡献于黑塞的行和列1-3，并且第二子图贡献于行和列3和4。较暗的阴影区指示对于子图的原生的受约束顶点，并且较亮的阴影区指示对于子图的原生的受约束顶点。子图的非约束顶点未被标记。

　　为了简化符号，让我们将和分别定义为对和的条目的限制；它们被约束在子图中。让我们把子图的原始残差定义为

　　

　　并且，如之前一样，让

　　

　　标示对对应于受约束顶点的条目的限制。

　　在具有这些定义在位的情况下，我们现在可以根据受约束顶点和非约束顶点来分解更新，并且经由ADMM呈现我们的分布式算法以用于解决图形SLAM：

　　

　　。

　　以上呈现的算法将收敛。为了获得对称的正定矩阵，其可以用于将（18）的目标函数预处理为

　　。

　　应当选择矩阵，使得使用子图以分布式方式对它进行计算和应用。优选地，项。为了实现此，对于每个子图，仅使用与对该子图而言原生的顶点相对应的对黑塞的行和列中的贡献来针对每个子图近似黑塞（参见图1（b））。例如，假设是约束顶点和的二元边。让，其中标示逐元素乘法，并且标示向量，该向量在对应于顶点的条目中为1，并且在别处为0，并且相应地定义。边可以被定义为

　　

　　

　　其中是克罗内克增量（Kronecker delta）。注意到，，因此误差和优化问题保持不变。针对子图的原生黑塞被定义为

　　。

　　注意到，的载体是不相交的。这允许快速的分布式计算，并且因此预处理矩阵被定义为

　　

　　通过如在（33）中那样重新定义边，可以计及更多的约束，这转而使得黑塞能够成为更好的近似，从而产生更好的预处理矩阵。

　　值得提及的是，子图的黑塞和其原生黑塞都可以包含其它子图所缺少的贡献。这在图1中图示，其中边约束顶点和。黑塞包含来自边在（2，2）、（2，3）、（3，2）和（3，3）块中的贡献，但仅贡献于的（2，2）块。另一方面，原生黑塞包含来自的（3，3）块贡献，但不包含来自的任何贡献。由于顶点和是不同子图的原生顶点，所以来自边的（2，3）和（3，2）块贡献不贡献于任何原生黑塞——这是为了确保算法保持分布式而必须付出的代价。这也证明了以最小化跨越不同子图的边的数量的这种方式对图形进行分区的重要性。

　　图2描绘了用于实现上述可扩展图形SLAM框架的示例性系统100。系统100包括可操作地连接到存储器系统104的处理系统102。处理系统102包括一个或多个处理器，所述一个或多个处理器可以位于相同设备/位置中，或者可以跨一个或多个位置处的多个设备分布。可以使用任何合适类型的（一个或多个）处理器。

　　处理系统可操作地连接到存储器系统104。存储器系统104可以包括任何合适类型的非暂时性计算机可读存储介质。存储器系统104可以跨多个设备和/或位置分布。编程指令存储在存储器系统中。编程指令包括用于实现操作系统和系统的各种功能的指令。编程指令还包括用于实现本文中描述的可扩展图形SLAM和ADMM算法的指令。

　　系统的组件可以通过一个或多个网络106通信地连接。可以使用任何合适类型的（一个或多个）网络，包括有线和无线类型的网络。计算设备包括使得能够经由（一个或多个）网络传输和接收数据的适当的网络接口设备。

　　虽然已经在附图和前面的描述中详细图示和描述了本公开，但是应当认为它们在符号方面是说明性的，而不是限制性的。应当理解的是，仅呈现了优选实施例，并且在本公开的精神内的所有改变、修改和进一步的应用都希望受到保护。