Cyrill Stachniss

TORO - News and Updates

2008-01-26
New version of TORO has been released that fixes some convergence problems in 3D datasets (the distribution of the rotation error in 3D has changed).

What is TORO - a Tree-based netwORk Optimizer

(logo artwork by Christian Plagemann)

Abstract

TORO is an optimization approach for constraint-network. It provides a highly efficient, gradient descent-based error minimization procedure.
In 2006, Olson et al. presented a novel approach to solve the graph-based SLAM problem by applying stochastic gradient descent to minimize the error introduced by constraints. TORO is an extension of Olson's algorithm. It applies a tree parameterization of the nodes in the graph that significantly improves the performance and enables a robot to cope with arbitrary network topologies. The latter allows us to bound the complexity of the algorithm to the size of the mapped area and not to the length of the trajectory.

Papers

	Giorgio Grisetti, Cyrill Stachniss, Slawomir Grzonka, and Wolfram Burgard A Tree Parameterization for Efficiently Computing Maximum Likelihood Maps using Gradient Descent. Robotics: Science and Systems (RSS), Atlanta, GA, USA, 2007. paper (8 pg, pdf)

	Grisetti Giorgio, Slawomir Grzonka, Cyrill Stachniss, Patrick Pfaff, and Wolfram Burgard Efficient Estimation of Accurate Maximum Likelihood Maps in 3D. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2007. paper (7 pg, pdf)

Get the Source Code!

The source code is available via svn:

svn co https://www.openslam.org/data/svn/toro

The software is written in C++ (GNU C++ compiler, developed under Linux) and requires no additional libraries or has any other dependency than the standard template library. A doxygen documentaion is available.

Datasets

Here you find some small and large scale dataset for constraint optimizationm approaches. The data file has a very simple structure. It mainly consists of two (or three) message, one for describing the nodes of a graph and one for describing the edges.

A set of simple text messages to represent nodes
(VERTEX) and edges (EDGE) of the graph.

VERTEX id x y orientation
(A 2D node in the graph - toro(2d))

EDGE observed_vertex_id observing_vertex_id forward sideward rotate cov_ff cov_fs cov_ss cov_rr cov_fr cov_sr
(A 2D-edge in the graph. cov_xx are the covariance entries of the constraint - toro(2d))

EQUIV id1 id2
(Equivalence constraints between nodes. It merges the node id1 and id2 wrt to the constraint between both vertices.
(toro(2d) and toro3d)

VERTEX3 id x y z phi theta psi
(A 3D-node in the graph - toro3d)

EDGE3 observed_vertex_id observing_vertex_id x y z roll pitch yaw cov_11 cov_12 .. cov_16 cov_21 .. cov_66
(A 3D-edge in the graph. cov_xx are the covariance entries of the constraint - toro3d)

Images and Video Material

	Corrected network Method: Our 3d approach (3d tree parameterization), no node reduction Result after 100 iterations
	Corrected network Method: Our approach (tree parameterization), no node reduction Size: 500.000 nodes/2 million constraints Noise: sigma-x/y=0.05, sigma-theta=0.02 Result after 100 iterations
	Corrected network Method: Our approach (tree parameterization), no node reduction Size: 200.000 nodes/1 million constraints Noise: sigma-x/y=0.01, sigma-theta=0.005 Result after 100 iterations
	Video of the individual iterations Method: Our approach (tree parameterization), no node reduction Size: 5.000 nodes/30.000 constraints
	Real world dataset: Intel Research Lab Video of the individual iterations Constraints are obtained via pair-wise scan-matching
	Comparison of the error per link per iteration Method: Olson's algorithm, our approach (tree parameterization) with and without node reduction Size: 5000 nodes Noise: sigma-x/y = 0.1, sigma-theta = 0.05 Confidence: 0.05 Note: Using the node reduction technique, the error per iteration decreases slower compared to the pure tree approach (it is log-scale). Each iteration, however, can be executed significantly faster (see Fig.6 in the RSS paper).
	Average path length for random networks of different size (Operations per constraint and iteration)