Adaptive GridMap Building Algorithm for Mobile Robot Based on Multiway Tree

Abstract

In order to solve the problem that uniform grid map occupies large storage space in the process of large-scale map creation, a new adaptive grid map building algorithm based on multiway tree is proposed. The environment map is divided into nine grids. The algorithm determines whether the grid is completely occupied, partially occupied or vacant. Then the part occupied gridsare further subdivided into smaller grids. The algorithm continues to determine whether the smaller grid is completely occupied, partially occupied or vacant.Repeat the above segmentation process until the entire map search is completed and the accuracy requirements are met. Finally, the scale of grid map does not depend on human experience but presenting adaptive characteristics. The algorithm is compared with the uniform grid method.The simulation results show that the algorithm has convergence.Andcompared with the uniform scale raster map, itgreatly saves the storage space.