Main contents

Branch And Bound Global Localization

Authors: Jari Saarinen, Janne Paanajärvi and Pekka Forsman

Key words: Localization, Mapping, SLAM, Scan matching, Scan Registration, Global localization, ROS, Open Source

In this page you find our implementation which is based on the publication:

  • Jari Saarinen, Janne Paanajärvi and Pekka Forsman, "Best-first branch and bound search method for map based localization," in Proc. IEEE/RJS International Conference on Intelligent Robots and Systems, San Francisco, Sep 25-30, 2011, San Francisco: 2011, pp. 59-64. IEEE explore link

The basic algorithm is a global localization algorithm, that does an efficient discrete search and provides globally optimal pose estimate and computes an estimate of full posterior for the search space. The package provided here is a standalone library with source codes wrapped into a ROS package.

The package includes the basic algorithm, SLAM/scan matching application, occupancy map implementation, an efficient version of distance transformation (used by the SLAM implementation), and some examples of usage. I have also added a log file for testing. '

Licensing follows standard ROS license (BSD), so you are free to use the implementation, as long as you realize that we are not responsible for the functionality of the implementation. Moreover, if you find it useful in your research, we would appreciate if you would cite the publication.

Download link:

The structure of the package is:

bb_registration/bin  : Contains compiled binaries
bb_registration/data : Contains one test dataset (please unpack first) 
bb_registration/lib  : Contains compiled libraries
bb_registration/map  : Contains map related files
bb_registration/registration : Contains the registration algorithm
bb_registration/test         : Test code 
bb_registration/utils        : Utilities
bb_registration/video        : Two videos demonstrating the test data

Dependencies The actual algorithm depends only few libraries, but the test code and wrappers depend on a few external libraries:

  • ROS (tested on Fuerte)
  • OpenGL, GLU, GLUT (just install freeglut)
  • MRPT-gui
  • Open-MP

ROS dependencies are listed in manifest.xml.

Compile First unpack the package and make sure it is somewhere in ROS path. Having installed all the required dependencies it should be enough to type:

cmake .

and then ./plotDataSet output.bag


This compiles the library files and creates two executables:

bin/testRegistration  :: Runs the Scan matching/ SLAM demo
bin/plotDataSet       :: Plots a bag file outputted by testRegistration

I will in future add more examples and add them to the package.

To run the examples unpack the data

bunzip data/test_data.bag.bz2

go to bin folder and execute:

./testRegistration ../data/test_data.bag 

This runs the registration example and visualizes the result. The behavior of the algorithm can be tuned with


After you have run the data set you can see the total output by typing

./plotDataSet output.bag

Dataset The dataset is from a real industrial setup. It is safety laser data recorded from an AGV. I chose to pick this example because this is pretty challenging dataset and one needs a robust algorithm to work with.

data/README  :: explains more details about the set

Important files

Registration Files:

BBMultiEngine.cpp/h :: The algorithm   
BBSlammerWrapper.cpp/h :: Wrapper, which does SLAM  
EnvironmentMeasurement2D.cpp/h :: An observation (sort of Poincloud definition)
MatchStorage.cpp/h :: Output of the algorithm


LikelihoodTransformation.cpp/h :: Fast distance transform
TOccupancyGrid.cpp/h           :: Standard occupancy grid 

Future issues

  • The aspect ratio of that the visualizer is not right at the moment.
  • There is currently no example of global localization application
  • Pointcloud matcher implementation
  • There is no node yet for direct online use with ROS.