## 3 System Overview
### Global SLAM Loop Closure
#### 3.5.1 Optimization Problem  
The optimization problem is based on loop closure detection, which is a process to recognize previously visited areas by matching sensor scans against the accumulated submap. The optimization problem is formulated as nonlinear squares. Every few seconds, the Ceres scan matcher is utilized to compute (5). \[ \begin{array}{c}\underset{\mathbf{P}^{M}\mathbf{P}^{S}}{argmin}\frac{1}{2} \underset{ij}{\sum}\rho(E^{2}(\mathcal{F}_{i}^{m},\mathcal{F}_{j}^{s};\sum_{ ij},\mathcal{F}_{ij}))^{2}\end{array}  \tag{5}\]  
where the scan pose, \({}^{S}~{}=~{}\left\{\mathcal{F}_{i}^{m}\right\}_{j~{}=~{}1,\ldots,n}\), and submap poses, \({}^{M}~{}=~{}\left\{\mathcal{F}_{i}^{m}\right\}_{i~{}=~{}1,\ldots,m}\), in the world are optimized with some constraints. These constraints are in relative pose form \(\mathcal{F}_{ij}\), and their covariance matrices, \(\sum_{ij}\). For a pair of submap \(i\) and \(j\), the pose \(\mathcal{F}_{ij}\) describes the coordinate of the submap frame where the scan was matched. The residual, \(E\), for such a constraint is computed by:  
\[E^{2}\left(\mathcal{F}_{i}^{m},\mathcal{F}_{j}^{s};\sum_{ij^{\prime}}~{} \mathcal{F}_{ij}\right)~{}=~{}e\left(\mathcal{F}_{i}^{m},\mathcal{F}_{j}^{s}; \mathcal{F}_{ij}\right)^{T}\sum\
olimits_{ij^{\  
The BBS scan matcher algorithm tries to compute matched scan with the best score by iterating the scan under search window inside map. The search window iteration contains finite step \(\delta_{\theta}\), for rotation and, \(r\), for translation (9). The detailed process of scan matcher iterations can be seen in Table 2.  
\[w_{x}\ =\ \ \frac{Wx}{r},w_{y}\ =\ \ \frac{Wy}{r},w_{\theta}\ =\ \frac{W_{\theta}}{\delta_{\theta}} \tag{9}\]  
As described in Table 2, each step of translations and rotations within the search window is tested one by one for evaluation. When the scan matcher finds the matched pair with better score, it will replace the previous matched scan pair with lower score. This technique has a downside where a large sized search window required for SLAM global map will result in quadratic growth of iterations. The Cartographer technique tries to eliminate the iteration needed for BBS scan matcher using a method called depth first search branch and bound scan matching (DFS BBS) which is resolved by finding a good subsets of search window (\(W\)) possibilities expressed as nodes in tree. The algorithm of DFS BBS can be seen in Table 3. It is done by computing a good upper bound node with multi-resolution grid maps. The DFS BBS work by downscaling existing submap to several resolution factors of one-quarter and one-half map size, etc., which are then, used as scan matcher inputs. Each selection of search window node will depend on previous node result. The scan matching process uses several layers of node, which starts from lower resolution for preliminary low accuracy computation of estimated translation and rotation. Then, the preliminary result with the best score is used to bypass many iterations of possible translation rotation in higher resolution. This process is repeated until the highest layer node on full resolutions map is reached. \begin{table}
\begin{tabular}{l} _best\_score_ **\(\leftarrow\)Null** \\
**for**\(jx\) = -\(w_{x}\) to \(w_{x}\)**do** \\
**for**\(jy\) = -\(w_{y}\) to \(w_{y}\)**do** \\
**for**\(j\theta\) = -\(w_{\theta}\) to \(w_{\theta}\) \\ _score_ \(\leftarrow\sum_{k=1}^{K}M_{\textit{nearest}}(T_{\mathcal{F}}h_{\mathcal{F}})\) \\
**if**\(score>best\_score\)**then** \\ match \(\leftarrow\mathcal{F}+(rjx,\ rjy,\ rj\theta)\) \\ _best-score_ \(\leftarrow\)_score_ \\
**end if** \\
**end for** \\
**return**\(best\_score\) and _match_ \\ \end{tabular}
\end{table} 
Table 2: Description of the native algorithm of branch and bound scan matcher.