参考：周治国 等: 3D 激光雷达 SLAM 算法综述
我想知道 cartographer分支定界是怎么回事？
图优化 SLAM 研究基础是基于图论( graph) 由顶点组成的数据结构( vertex) 连接顶点的边缘( edge) 组成表示为 G( V，E) ，其中 G 表示图，顶点的集合表示为 V，边缘集合表示为 E，它的思想是用顶点来表示事物，而连接不同顶点之间的边缘则用来表示事物之间的关系，如果在图 G 中存在一个顶点上连接两个以上的边，则称该图为超图，在 SLAM 根据现有的观测数据，实现超图的构建和优化过程。 假设移动载体的位置节点使用 μ = { μ1，μ2，…，μn} 将环境中的地标(如垃圾桶)表示为 S = { S1，S2，…，Sn} ，移动平台的位置和地标可以用下图表示。 
如果某时刻 k，移动载体在位置 μk通过激光传感器扫描观测(观测垃圾桶)获取数据 Sk，则传感器的观测方程为: Sk= F(μk) 由于系统参数和传感器观测存在误差，上述公式不能准确相等，因此误差 ek= Sk－ F( μk) 如果把，便存在 minFk( μk) = ‖ek‖ 找到目标函数作为目标函数ek最小的 μk，那这个 μk是机器人k时刻位置的估计值，可以一点一点获得移动轨迹。 顶点是激光雷达的位置或特征点(垃圾桶)的位置，代表观测方程，即约束，可以有很多约束，比如imu约束，gps限制越准确，机器人的位置就越准确。
基于图优化slam方案可分为、、、 4 个部分。 扫描匹配和闭环检测是根据观测信息建立节点和节点之间的约束，即完成图的构建，优化图 SLAM 的前端部分。
是前端构建的图形信息，取得，最终输出姿态估计结果和全局点云地图，也称为 SLAM 后端，与 SLAM 前端共同构成整个图优化 SLAM 框架。
分类如下： 基于特征的方法的关键部分是：关键点检测、特征描述符提取、真实匹配、异常值消除和转换估计。 基于全局数据关联的闭环检测是鲁棒的实现 SLAM 核心步骤，通过促进地图闭环的能力可以纠正累积误差，从而产生全局一致性的映射地图。 闭环检测的主要体现在：
- 感知歧义。比如长廊、隧道、楼梯等结构化非常相似的场景，会加剧判断难度。
- 由于激光传感器本身的稀疏性，观测数据鲁棒性和区分性有限，即如何建立易于处理的有效环境表 征方式。
- 随着运行时间的增加，需要判断的帧数据将继续增加，这将降低构图的实时性。 目前闭环检测技术主要包括： 基于 MonteCarlo 节点搜索算法 依据 GPS 辅助闭环判断辅助法； 局部描述子代表算法是基于描述子的回环检测算法 FPFH， 基于 Gasalt3D 描述符的概率投票方法…
基于图优化 SLAM 后端优化方法可以概括为 4 类: 基于优化方法，基于优化方法，基于优化方法和方法。目前基于图优化的开源优化库有 iSAM( incremental smoothing and mapping)、GTSAM ( georgia tech smoothing and mapping )、G2O( general graph optimization )、Ceres、BA ( bundle adjustment)等，这些优化库可以节省后端迭代求解优化值的时间。
最后，、 激光雷达最容易获得点云地图，但由于点云数量太大，需要进行体素滤波采样)才能正常显示。
（ 小tips：体素滤波的原理是基于输入点云，首先，然后根据，将大立方体分为不同的小立方体。计算每个小立方体的质地，并计算每个小立方体的点。）
简单的点云地图不能直接用于定位。因此，有了它 稀疏点云地图（分离特征，重定位特征）、网格地图（网格地图、导航避障和路径规划）、八叉树地图（八叉树地图是一种特殊的网格地图，结构可以合并，从而减少存储地图的空间，具有更好的压缩性能。）更高层次：语义地图。
3. 分支定界
回到最初的问题，关系是什么？分支定界cartographer怎么用？
一般来说，它是一棵树，把它的根、枝、叶分开。A是树的根，也就是原问题，绿色字母JKLMNOPQ一片一片的叶子，即解，BCDEFGHI中间的枝可以理解为根问题的一系列子问题。 这样的树分枝叶后，在F上计算JKLM选择得分最高的解，记为best1。返回上一层G，计算G的目标函数值(得分)best2，与best1比较，若best1仍然是最大的，然后对G进行剪枝，继续计算H的目标函数值。若best2大于best一、分枝GNOPQ，计算NOPQ与best2比较，更新best。.
4. cartographer分支定界！
在cartographer里 分支定界，
Cartographer 生成地图由两部分组成。第一部分是基于局部坐标系标系的子图，第二部分是生成由子图组成的全局地图，在识别回环时进行校正。激光雷达的扫描提供了一帧点云，Cartographer 的子图用表示占用每个像素存储网格点的概率值。根据子图坐标系中每个点的位置，点对应子图中的像素更新概率值，使用与原点连接对应的子图中像素(排除点命中的像素)更新概率值 Ceres 激光雷达扫描计算激光雷达扫描点云在子图中的位置，将位置求解转换为非线性最小二乘问题，。 在局部 SLAM 由于地图分辨率、传感器噪声等原因，计算位置的过程总是会产生误差。因为位置的计算是基于每个平移和旋转的总和，点云只匹配子图，包括最近几次扫描。随着行驶距离的增加，漂移误差越来越大。因此，全局 SLAM 采用稀疏位置调整消除累积误差。全局优化也被建模成非线性最小二乘问题。基于回环检测法，，将相应的相对位置添加到非线性最小二乘问题的优化约束中。每插入一定数量的点云，解决优化问题，计算整体位置的最佳解决方案。 基于(Depth Frist Search，DFS)加快回环检测，。该算法实现的关键思路是建立搜索窗口。这与上面的根、枝、叶有关！根节点是搜索窗口中的所有位置。每个叶节点都表示搜索窗口中的位置。算法是基于给定的搜索高度h， 将根节点分支到高度h 初始子节点集 C ，并计算 C 每个子节点的匹配分数。若子节点集C 回环检测到最高匹配分数高于设定的分数阈值，，否则为未检测回环。