Experimental Results

Here, we present experiments where we compare Sparse Pose Adjustment (SPA) with state-of-the art approaches on 61 real world datasets. We considered a broad variety of approaches, including the best state-of-the-art.

• Information filter: DSIF [1]
• Stochastic gradient descent: TORO [2]
• Decomposed nonlinear system: Treemap [3]
• Sparse pose adjustment: SPA, with (a) sparse direct Cholesky solver, and (b) iterative PCG [4]

We updated the PCG implementation to use the same "continued LM" method as SPA; the only difference is in the underlying linear solver. The preconditioner is an incomplete Cholesky method, and the conjugate gradient is implemented in sparse matrix format.
We also evaluated a dense Cholesky solver, but both the computational and the memory requirements were several orders of magnitude larger than the other approaches. As an example, for a dataset with 1600 constraints and 800 nodes one iteration using a dense Cholesky solver would take 2.1 seconds while the other approaches require an average of a few milliseconds. All experiments are executed on an Intel Core i7-920 running at 2.67 Ghz.

Accuracy Measure

For these indoor datasets, there is no ground truth. Instead, the measure of goodness for a pose-constraint system is the covariance-weighted squared error of the constraints, or χ^2 error. If the scan matcher is accurate, lower χ^2 means that scans align better. In the following we present the detailed evaluation of the real world data sets. Each data set is accompanied by a details page which shows several plots about the data set and the performance of each of the above listed algorithms.

Real-World Experiments: Off-Line Optimization

To optimize a dataset off-line, we provide each optimizer with a full description of the problem. We leave out from the comparison DSIF and TreeMap, since they only operate incrementally (DSIF is equivalent to one iteration of SPA in batch mode). Since the success of the off-line optimization strongly depends on the initial guess, we also investigated two initialization strategies, described below.

• Odometry: the nodes in the graph are initialized with incremental constraints. This is a standard approach taken in almost all graph optimization algorithms.
• Spanning-Tree: A spanning tree is constructed on the graph using a breadth-first visit. The root of the tree is the first node in the graph. The positions of the nodes are initialized according to a depth-first visit of the spanning tree. The position of a child is set to the position of the parent transformed according to the connecting constraint. In our experiments, this approach gives the best results.

For each dataset and each optimizer we computed the initial guesses described above. Every optimizer was run for a minimum number of iterations or until a termination criterion was met. We measured the time required and the χ^2 error for each approach.

Real-World Experiments: On-Line Optimization

For the on-line comparison, we incrementally augment the graph by adding one node and by connecting the newly added node to the previously existing graph. We invoke the optimizer after inserting each node, and in this way simulate its behavior when executed in conjunction with a SLAM front-end. The optimization is carried out for a maximum number iterations, or until the error does not decrease. The maximum number of iterations for SPA/PCG is 1; for TreeMap, 3; and for TORO, 100. Since PCG iteratively solves the linear subproblem, we limited it to 50 iterations there. These thresholds were selected to obtain the best performances in terms of error reduction. We report the statistics on the execution time and on the error per constraint every time a new constraint was added.

Data sets

Index	Name	# Nodes	# Constraints	Download	Details
1	graph_001	28	28	graph_001.txt.gz	Details
2	graph_002	57	65	graph_002.txt.gz	Details
3	graph_003	87	90	graph_003.txt.gz	Details
4	graph_004	94	94	graph_004.txt.gz	Details
5	graph_005	231	231	graph_005.txt.gz	Details
6	graph_006	237	238	graph_006.txt.gz	Details
7	graph_007	237	238	graph_007.txt.gz	Details
8	graph_008	239	239	graph_008.txt.gz	Details
9	graph_009	210	288	graph_009.txt.gz	Details
10	graph_010	277	292	graph_010.txt.gz	Details
11	graph_011	311	313	graph_011.txt.gz	Details
12	graph_012	311	313	graph_012.txt.gz	Details
13	graph_013	311	313	graph_013.txt.gz	Details
14	graph_014	310	354	graph_014.txt.gz	Details
15	graph_015	448	456	graph_015.txt.gz	Details
16	graph_016	377	477	graph_016.txt.gz	Details
17	graph_017	263	480	graph_017.txt.gz	Details
18	graph_018	384	493	graph_018.txt.gz	Details
19	graph_019	384	494	graph_019.txt.gz	Details
20	graph_020	547	647	graph_020.txt.gz	Details
21	graph_021	387	668	graph_021.txt.gz	Details
22	graph_022	476	697	graph_022.txt.gz	Details
23	graph_023	590	709	graph_023.txt.gz	Details
24	graph_024	467	804	graph_024.txt.gz	Details
25	graph_025	512	865	graph_025.txt.gz	Details
26	graph_026	646	1077	graph_026.txt.gz	Details
27	graph_027	826	1114	graph_027.txt.gz	Details
28	graph_028	748	1122	graph_028.txt.gz	Details
29	graph_029	683	1183	graph_029.txt.gz	Details
30	graph_030	1224	1500	graph_030.txt.gz	Details
31	graph_031	808	1615	graph_031.txt.gz	Details
32	graph_032	791	1631	graph_032.txt.gz	Details
33	graph_033	724	1676	graph_033.txt.gz	Details
34	graph_034	828	1684	graph_034.txt.gz	Details
35	graph_035	1039	1960	graph_035.txt.gz	Details
36	graph_036	984	1979	graph_036.txt.gz	Details
37	graph_037	1117	2028	graph_037.txt.gz	Details
38	graph_038	1124	2312	graph_038.txt.gz	Details
39	graph_039	1406	2563	graph_039.txt.gz	Details
40	graph_040	1430	2688	graph_040.txt.gz	Details
41	graph_041	1303	2781	graph_041.txt.gz	Details
42	graph_042	1160	2811	graph_042.txt.gz	Details
43	graph_043	1404	3078	graph_043.txt.gz	Details
44	graph_044	1430	3156	graph_044.txt.gz	Details
45	graph_045	1680	3182	graph_045.txt.gz	Details
46	graph_046	1713	3302	graph_046.txt.gz	Details
47	graph_047	2673	3366	graph_047.txt.gz	Details
48	graph_048	1720	3742	graph_048.txt.gz	Details
49	graph_049	3885	4775	graph_049.txt.gz	Details
50	graph_050	2617	4793	graph_050.txt.gz	Details
51	graph_051	3349	4818	graph_051.txt.gz	Details
52	graph_052	2491	4986	graph_052.txt.gz	Details
53	graph_053	3603	4986	graph_053.txt.gz	Details
54	graph_054	2652	5017	graph_054.txt.gz	Details
55	graph_055	2653	5020	graph_055.txt.gz	Details
56	graph_056	2775	5106	graph_056.txt.gz	Details
57	graph_057	2462	6136	graph_057.txt.gz	Details
58	graph_058	6003	7182	graph_058.txt.gz	Details
59	graph_059	3386	7245	graph_059.txt.gz	Details
60	graph_060	3386	7281	graph_060.txt.gz	Details
61	graph_061	3755	7352	graph_061.txt.gz	Details

References

[1] R. M. Eustice, H. Singh, and J. J. Leonard. Exactly sparse delayed-state filters for view-based SLAM. IEEE Trans. Robotics, 22(6), 2006.
[2] G. Grisetti, C. Stachniss, and W. Burgard. Non-linear constraint network optimization for efficient map learning. IEEE Transactions on Intelligent Transportation Systems, 10:428–439, 2009. ISSN: 1524-9050.
[3] U. Frese. Treemap: An o(logn) algorithm for indoor simultaneous localization and mapping. Journal of Autonomous Robots, 21(2):103–122, 2006.
[4] K. Konolige. Large-scale map-making. In Proceedings of the National Conference on AI (AAAI), 2004.