Determinism of Spanning Tree Initialization

[mertkaraoglu]

Issue:

Spanning-tree initialization is not deterministic. iteration= -1 is almost always different at different runs, very rarely the same.

Test environment:

OS: Ubuntu 20.04, MacOs 11.5.2.
Tag: 20200410_git
CMake Settings:

    cmake \
        -DCMAKE_BUILD_TYPE=Release \
        -DBUILD_CSPARSE=ON \
        -DBUILD_LGPL_SHARED_LIBS=ON \
        -DBUILD_SHARED_LIBS=ON \
        -DG2O_BUILD_APPS=ON \
        -DG2O_BUILD_LINKED_APPS=OFF \
        -DG2O_USE_CSPARSE=ON \
        -DG2O_USE_CHOLMOD=OFF \
        -DG2O_USE_OPENGL=OFF \
        -DG2O_USE_OPENMP=OFF \
        -DG2O_BUILD_EXAMPLES=ON \
        ..

Test:

Testing with Luca Carlone's parking garage data, with the following command:
./g2o -v -guess ~/Desktop/parking-garage.g2o

Output:

Below are the two runs, what must be paid attention is iteration= -1.
Run 1:

# Used Compiler: AppleClang /Library/Developer/CommandLineTools/usr/bin/c++
# Using CSparse poseDim -1 landMarkDim -1 blockordering 0
Read input from /Users/mkaraoglu/Desktop/parking-garage.g2o
Loaded 1661 vertices
Loaded 6275 edges
# graph is fixed by node 1660
Initial chi2 = 16720.018301
iteration= -1	 chi2= 74.9255	 time= 0.0	 cumTime= 0.0	 (using initial guess from spanning tree)
iteration= 0	 chi2= 1.680485	 time= 0.0359463	 cumTime= 0.0359463	 edges= 6275	 schur= 0
iteration= 1	 chi2= 1.238691	 time= 0.0191692	 cumTime= 0.0551155	 edges= 6275	 schur= 0
iteration= 2	 chi2= 1.238691	 time= 0.0181383	 cumTime= 0.0732538	 edges= 6275	 schur= 0
iteration= 3	 chi2= 1.238691	 time= 0.0179828	 cumTime= 0.0912366	 edges= 6275	 schur= 0
iteration= 4	 chi2= 1.238691	 time= 0.0171863	 cumTime= 0.108423	 edges= 6275	 schur= 0

Run 2:

# Used Compiler: AppleClang /Library/Developer/CommandLineTools/usr/bin/c++
# Using CSparse poseDim -1 landMarkDim -1 blockordering 0
Read input from /Users/mkaraoglu/Desktop/parking-garage.g2o
Loaded 1661 vertices
Loaded 6275 edges
# graph is fixed by node 1660
Initial chi2 = 16720.018301
iteration= -1	 chi2= 45.8479	 time= 0.0	 cumTime= 0.0	 (using initial guess from spanning tree)
iteration= 0	 chi2= 1.595930	 time= 0.033302	 cumTime= 0.033302	 edges= 6275	 schur= 0
iteration= 1	 chi2= 1.238691	 time= 0.0183552	 cumTime= 0.0516573	 edges= 6275	 schur= 0
iteration= 2	 chi2= 1.238691	 time= 0.0177086	 cumTime= 0.0693659	 edges= 6275	 schur= 0
iteration= 3	 chi2= 1.238691	 time= 0.0185022	 cumTime= 0.0878681	 edges= 6275	 schur= 0
iteration= 4	 chi2= 1.238691	 time= 0.0172191	 cumTime= 0.105087	 edges= 6275	 schur= 0

This difference only happens with spanning tree initialization turned on. Is this an expected result, is this initialization scheme non-deterministic? If so can you lead me to a publication in which this is explained? And more preferred, is there a way to make it deterministic?

[RainerKuemmerle]

I would need to investigate this. It might be that some data structure in the search algorithm are still sorted by pointer address instead of deterministic values, e.g., vertex IDs.

Btw.: The data set you are referring to originates from here
http://ais.informatik.uni-freiburg.de/publications/papers/kuemmerle09icra.pdf
https://github.com/OpenSLAM-org/openslam_g2o/tree/master/data/3d/garage

[RainerKuemmerle]

.:[ goki@e14:~/workspace/g2o/bin ]:. (git)-[tags/20200410_git] 
$ ./g2o -v -i 10 -guess /home/goki/workspace/data/3d/garage/parking-garage.g2o
# Used Compiler: GNU /usr/bin/c++
# Using CSparse poseDim -1 landMarkDim -1 blockordering 0
Read input from /home/goki/workspace/data/3d/garage/parking-garage.g2o
Loaded 1661 vertices
Loaded 6275 edges
# graph is fixed by node 1660
Initial chi2 = 16720.018301
iteration= -1	 chi2= 47.7908	 time= 0.0	 cumTime= 0.0	 (using initial guess from spanning tree)
iteration= 0	 chi2= 1.592548	 time= 0.0323352	 cumTime= 0.0323352	 edges= 6275	 schur= 0
iteration= 1	 chi2= 1.238691	 time= 0.0195532	 cumTime= 0.0518884	 edges= 6275	 schur= 0
iteration= 2	 chi2= 1.238691	 time= 0.0208577	 cumTime= 0.0727461	 edges= 6275	 schur= 0
iteration= 3	 chi2= 1.238691	 time= 0.0225519	 cumTime= 0.095298	 edges= 6275	 schur= 0
iteration= 4	 chi2= 1.238691	 time= 0.0216356	 cumTime= 0.116934	 edges= 6275	 schur= 0
iteration= 5	 chi2= 1.238691	 time= 0.0201909	 cumTime= 0.137125	 edges= 6275	 schur= 0
iteration= 6	 chi2= 1.238691	 time= 0.02169	 cumTime= 0.158815	 edges= 6275	 schur= 0
iteration= 7	 chi2= 1.238691	 time= 0.0213232	 cumTime= 0.180138	 edges= 6275	 schur= 0
iteration= 8	 chi2= 1.238691	 time= 0.0204731	 cumTime= 0.200611	 edges= 6275	 schur= 0
iteration= 9	 chi2= 1.238691	 time= 0.020508	 cumTime= 0.221119	 edges= 6275	 schur= 0
.:[ goki@e14:~/workspace/g2o/bin ]:. (git)-[tags/20200410_git] 
$ ./g2o -v -i 10 -guess /home/goki/workspace/data/3d/garage/parking-garage.g2o
# Used Compiler: GNU /usr/bin/c++
# Using CSparse poseDim -1 landMarkDim -1 blockordering 0
Read input from /home/goki/workspace/data/3d/garage/parking-garage.g2o
Loaded 1661 vertices
Loaded 6275 edges
# graph is fixed by node 1660
Initial chi2 = 16720.018301
iteration= -1	 chi2= 47.7908	 time= 0.0	 cumTime= 0.0	 (using initial guess from spanning tree)
iteration= 0	 chi2= 1.592548	 time= 0.0320037	 cumTime= 0.0320037	 edges= 6275	 schur= 0
iteration= 1	 chi2= 1.238691	 time= 0.020036	 cumTime= 0.0520397	 edges= 6275	 schur= 0
iteration= 2	 chi2= 1.238691	 time= 0.0204935	 cumTime= 0.0725332	 edges= 6275	 schur= 0
iteration= 3	 chi2= 1.238691	 time= 0.0206568	 cumTime= 0.09319	 edges= 6275	 schur= 0
iteration= 4	 chi2= 1.238691	 time= 0.0202813	 cumTime= 0.113471	 edges= 6275	 schur= 0
iteration= 5	 chi2= 1.238691	 time= 0.0199644	 cumTime= 0.133436	 edges= 6275	 schur= 0
iteration= 6	 chi2= 1.238691	 time= 0.0206355	 cumTime= 0.154071	 edges= 6275	 schur= 0
iteration= 7	 chi2= 1.238691	 time= 0.0207921	 cumTime= 0.174863	 edges= 6275	 schur= 0
iteration= 8	 chi2= 1.238691	 time= 0.0200617	 cumTime= 0.194925	 edges= 6275	 schur= 0
iteration= 9	 chi2= 1.238691	 time= 0.0208843	 cumTime= 0.215809	 edges= 6275	 schur= 0

I cannot reproduce on Ubuntu with

$ gcc --version
gcc (Ubuntu 11.2.0-7ubuntu2) 11.2.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

[mertkaraoglu]

Very interesting, I have just compiled again with gcc-11 but the results are still not consistent.

holt g2o/bin ‹6759465*› » ./g2o -v -i 10 -guess ~/Desktop/parking-garage.g2o
# Used Compiler: GNU /usr/local/bin/g++-11
# Using CSparse poseDim -1 landMarkDim -1 blockordering 0
Read input from /Users/mkaraoglu/Desktop/parking-garage.g2o
Loaded 1661 vertices
Loaded 6275 edges
# graph is fixed by node 1660
Initial chi2 = 16720.018301
iteration= -1	 chi2= 48.8527	 time= 0.0	 cumTime= 0.0	 (using initial guess from spanning tree)
iteration= 0	 chi2= 1.600632	 time= 0.0374498	 cumTime= 0.0374498	 edges= 6275	 schur= 0
iteration= 1	 chi2= 1.238691	 time= 0.019038	 cumTime= 0.0564878	 edges= 6275	 schur= 0
iteration= 2	 chi2= 1.238691	 time= 0.0209448	 cumTime= 0.0774326	 edges= 6275	 schur= 0
iteration= 3	 chi2= 1.238691	 time= 0.020016	 cumTime= 0.0974486	 edges= 6275	 schur= 0
iteration= 4	 chi2= 1.238691	 time= 0.0209932	 cumTime= 0.118442	 edges= 6275	 schur= 0
iteration= 5	 chi2= 1.238691	 time= 0.0273271	 cumTime= 0.145769	 edges= 6275	 schur= 0
iteration= 6	 chi2= 1.238691	 time= 0.0192649	 cumTime= 0.165034	 edges= 6275	 schur= 0
iteration= 7	 chi2= 1.238691	 time= 0.023073	 cumTime= 0.188107	 edges= 6275	 schur= 0
iteration= 8	 chi2= 1.238691	 time= 0.0191479	 cumTime= 0.207255	 edges= 6275	 schur= 0
iteration= 9	 chi2= 1.238691	 time= 0.021162	 cumTime= 0.228417	 edges= 6275	 schur= 0
holt g2o/bin ‹6759465*› » ./g2o -v -i 10 -guess ~/Desktop/parking-garage.g2o
# Used Compiler: GNU /usr/local/bin/g++-11
# Using CSparse poseDim -1 landMarkDim -1 blockordering 0
Read input from /Users/mkaraoglu/Desktop/parking-garage.g2o
Loaded 1661 vertices
Loaded 6275 edges
# graph is fixed by node 1660
Initial chi2 = 16720.018301
iteration= -1	 chi2= 70.7267	 time= 0.0	 cumTime= 0.0	 (using initial guess from spanning tree)
iteration= 0	 chi2= 1.616153	 time= 0.03351	 cumTime= 0.03351	 edges= 6275	 schur= 0
iteration= 1	 chi2= 1.238691	 time= 0.0200531	 cumTime= 0.0535631	 edges= 6275	 schur= 0
iteration= 2	 chi2= 1.238691	 time= 0.0348942	 cumTime= 0.0884573	 edges= 6275	 schur= 0
iteration= 3	 chi2= 1.238691	 time= 0.0202732	 cumTime= 0.108731	 edges= 6275	 schur= 0
iteration= 4	 chi2= 1.238691	 time= 0.026165	 cumTime= 0.134896	 edges= 6275	 schur= 0
iteration= 5	 chi2= 1.238691	 time= 0.019695	 cumTime= 0.154591	 edges= 6275	 schur= 0
iteration= 6	 chi2= 1.238691	 time= 0.0244799	 cumTime= 0.17907	 edges= 6275	 schur= 0
iteration= 7	 chi2= 1.238691	 time= 0.0189497	 cumTime= 0.19802	 edges= 6275	 schur= 0
iteration= 8	 chi2= 1.238691	 time= 0.0216949	 cumTime= 0.219715	 edges= 6275	 schur= 0
iteration= 9	 chi2= 1.238691	 time= 0.019206	 cumTime= 0.238921	 edges= 6275	 schur= 0

Can you share your CMake options?

[github-actions]

This issue is stale because it has been open 60 days with no activity. Remove stale label or comment or this will be closed in 14 days.