FloodFill Maze Solving with Expected Toll of Penetrating Unknown Walls for Micromouse

Abstract

The maze solving has gained increasing attention in the field of Micromouse competition and Intelligent Robot. To be more intelligent is a trend of the relevant research. This paper begins with expounding the fundamental working logic and calculating procedure of traditional Floodfill Algorithm. After summarizing the Floodfill's intelligence in the information of known walls and its non-intelligence in the unreasonable assumptions about the unknown walls, this paper introduce a new conception and present a modified algorithm called ET-Floodfill. It is assumed that the unknown walls are penetrable and the penetrating causes extra expense, which is quantified by the expected toll value T. The toll value is an expectation value due to the uncertainty of the existence of unknown walls. With reasonable estimating and adjustment of the toll value, ET-Floodfill has a better performance than traditional Floodfill. Its intelligence reduced the turning times and the steps taken from starting cell to destination cell. Additionally, the computational complexity remains the same with Floodfill. For each step of the cell-exploration process, the worst case time complexity is O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ).