Online Constraint Network Optimization
for Efficient Maximum Likelihood Map Learning
Giorgio Grisetti∗

Dario Lodi Rizzini‡

Cyrill Stachniss∗

Abstract— In this paper, we address the problem of incrementally optimizing constraint networks for maximum likelihood
map learning. Our approach allows a robot to efficiently
compute configurations of the network with small errors while
the robot moves through the environment. We apply a variant
of stochastic gradient descent and use a tree-based parameterization of the nodes in the network. By integrating adaptive
learning rates in the parameterization of the network, our algorithm can use previously computed solutions to determine the
result of the next optimization run. Additionally, our approach
updates only the parts of the network which are affected by the
newly incorporated measurements and starts the optimization
approach only if the new data reveals inconsistencies with
the network constructed so far. These improvements yield an
efficient solution for this class of online optimization problems.
Our approach has been implemented and tested on simulated and on real data. We present comparisons to recently
proposed online and offline methods that address the problem
of optimizing constraint network. Experiments illustrate that
our approach converges faster to a network configuration with
small errors than the previous approaches.

I. I NTRODUCTION
Maps of the environment are needed for a wide range of
robotic applications such as search and rescue, automated
vacuum cleaning, and many other service robotic tasks.
Learning maps has therefore been a major research focus in
the robotics community over the last decades. Learning maps
under uncertainty is often referred to as the simultaneous
localization and mapping (SLAM) problem. In the literature,
a large variety of solutions to this problem can be found.
The approaches mainly differ in the underlying estimation
technique. Typical techniques are Kalman filters, information
filters, particle filters, network based methods which rely on
least-square error minimization techniques.
Solutions to the SLAM problem can be furthermore divided into online an offline methods. Offline methods are
so-called batch algorithms that require all the data to be
available right from the beginning [1], [2], [3]. In contrast to
that, online methods can re-use an already computed solution
and update or refine it. Online methods are needed for
situations in which the robot has to make decisions based on
the model of the environment during mapping. Exploring an
unknown environment, for example, is a task of this category.
Popular online SLAM approaches such as [4], [5] are based
on the Bayes’ filter. Recently, also incremental maximumlikelihood approaches have been presented as an effective
alternative [6], [7], [8].
∗ Department of Computer Science, University of
† MIT, 77 Massachusetts Ave., Cambridge, MA

Freiburg, Germany.
02139-4307, USA.
‡ Department of Information Engineering, University of Parma, Italy.

Edwin Olson†

Wolfram Burgard∗

robot

trajectory

matching
constraints

Fig. 1.

Four snapshots created while incrementally learning a map.

In this paper, we present an efficient online optimization
algorithm which can be used to solve the so-called “graphbased” or “network-based” formulation of the SLAM problem. Here, the poses of the robot are modeled by nodes
in a graph and constraints between poses resulting from
observations or from odometry are encoded in the edges
between the nodes. Our method belongs to the same class of
techniques of Olson’s algorithm or MLR [8]. It focuses on
computing the best map and it assumes that the constraints
are given. Techniques like the ATLAS framework [9] or
hierarchical SLAM [10], for example, can be used to obtain
the necessary data associations (constraints). They also apply
a global optimization procedure to compute a consistent
map. One can replace these optimization procedures by our
algorithm and in this way make them more efficient.
Our approach combines the ideas of adaptive learning
rates with a tree-based parameterization of the nodes when
applying stochastic gradient descent. This yields an online
algorithm that can efficiently compute network configurations with low errors. An application example is shown in
Figure 1. It depicts four snapshots of our online approach
during a process of building a map from the ACES dataset.
II. R ELATED W ORK
A large number of mapping approaches has been presented
in the past and a variety of different estimation techniques
have been used to learn maps. One class of approaches uses
constraint networks to represent the relations between poses
and observations.