I am trying to implement Graph Slam. For tutorial purpose I read the paper "The GraphSlam Algorithm with Application to Large-Scale Mapping of Urban Structures" by Sebastian Thrun. At the beginning of this paper in abstract portion there is a line which arise doubt. "It then reduces this graph using variable elimination techniques, arriving at a lowerdimensional problems that is then solved using conventional optimization techniques". What is that variable elimination technique? Which variable they want to eliminate?

In the same paper "Table 3. Algorithm for Reducing the Size of the Information Representation of the Posterior in GraphSLAM". What is the meaning of this algorithm? What kind of data we calculate here? Paper Link The GraphSLAM Algorithm

I am eagerly looking for the answer of those question because after read this paper it is very difficult to understand the theory of GraphSlam.


1 Answer 1


The variables being removed are the 'features', i.e.,the observations from the robot. Section 3.4 in the paper discusses the variable elimination in a good amount of detail (especially figure 3).

The reason for this elimination is to reduce the information representation from between poses and features to between poses. After the removal, the information matrix only propagates information between the poses,greatly reducing the size and complexity of the graph.

To put it very simply, imagine there are two poses $x_1$ and $x_2$ from both of which one feature $f$ is being observed. Now you have two links (edges), one between $x_1$ and $f$ and one between $x_2$ and $f$, representing the observation. The variable elimination technique will remove these two links and eliminate $f$ altogether, but whatever changes were being made to $x_1$ and $x_2$ will now instead be stored in the edge between $x_1$ and $x_2$. The way this change is performed inside the information matrix (which encodes these links) is shown in an algorithmic way in table 3. The data computed in table 3, thus, is a smaller information matrix and the corresponding information vector.

  • $\begingroup$ Thank You. I think features are the just another name of Landmarks. If I am right then removing features meaning we cannot generated the Map. Right? Second question in the above paper Table2: Line 7 How this equation is possible? Subtract 1 from Gt where Gt is a 3*3 Matrix. There dimension is mismatched here. $\endgroup$
    – Encipher
    Jul 6, 2018 at 18:01
  • $\begingroup$ If you read section 3.4 carefully, they mention how the features are recovered later. Remember that this "reduction" is only to make the pose graph optimization easier, it does not mean useful information is thrown away. I have answered your other question separately. $\endgroup$ Jul 6, 2018 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.