Best-first branch and bound search method for map based localization

To know the pose of the robot is one of the central requirements in many applications. A localization algorithm should be robust, it should give the estimate of unreliability and it should be able to recover from errors. The above requirements are often trade offs with the computational complexity. This paper presents a global localization algorithm that matches a local point map (acquired e.g. with a laser range finder) to a global map. The algorithm makes a discrete search using a best-first branch and bound method to efficiently compute the globally optimal pose estimate. Moreover, the degree of ambiguity of the pose estimate can be determined as the algorithm yields all potential pose solution candidates within the search space. Experimental results are given to show the behavior and performance analysis of the algorithm.