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.
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)
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:
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
go to bin folder and execute:
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
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
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
- 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.