A Grid Map Fusion Algorithm Based on Maximum Common Subgraph

Abstract

Grid map fusion is a key problem for multi-robot simultaneous localization and mapping (SLAM), and single robot graph-SLAM. To solve this problem, this paper proposes a novel approach to fuse maps based on maximum common subgraph without the requirements of any assumption on the robot's pose. In the approach, the problem of grid map fusion is transformed into an image registration problem, and then the objective function is established to calculate a transformation matrix. Firstly, a corner extraction algorithm is applied to extract corner points from grid maps. Secondly, according to the extracted corner points the isomorphism scheme of triangle is constructed, as a result the initial optimal transformation matrix to being calculated. Finally, the transformation matrix is optimized by finding a maximum common subgraph based on iterating the polygon isomorphism scheme with more corner points. Experimental results show that the proposed approach can solve the grid map merging problem high accurately and robustly.