This project was developed in collaboration with the CITE group at Universidad Simón Bolívar for a maze‐solving robotics competition held from November 7 to 9, 2016.
The core of this implementation is a flood‐fill algorithm designed for a micromouse (robot) to navigate a maze. The robot always starts at one corner of the maze, and its goal is to reach the center. 1. Initialization • At the very beginning, we assume that no walls exist anywhere in the maze. • Each cell is assigned a predefined “distance” or “cost” value. • With every cell initialized in memory, the robot (micromouse) is ready to begin exploring. 2. Exploration Loop • The robot moves forward into the next adjacent cell. • As it moves, it detects any walls in its immediate surroundings and updates its internal map (memory) accordingly. • After entering a new cell, the robot checks whether that cell is the target (i.e., one of the four center cells). • If the robot has not yet reached the center, it recalculates the distance values for its current cell and any other cells affected by newly discovered walls—even if those cells have not yet been visited. • This recalculation ensures that the robot always knows the shortest remaining path to the goal given its current knowledge of the maze. 3. Completion • Once the robot has fully explored and updated its internal representation of the maze, it possesses the optimal path to the center. • Using that information, the micromouse can then traverse directly to the center along the shortest route.
1. Flood‐Fill Algorithm
• Assign every cell a numeric value proportional to its Manhattan distance from the center (e.g., cells adjacent to the center start with lower values).
• As the robot explores, it updates wall information and adjusts the distance values (or “wavefront”) accordingly, always propagating new costs outward from the center.
• By always moving toward the adjacent cell with the lowest updated value, the robot effectively “follows the gradient” toward the center, even as it discovers previously unknown walls.
2. Real‐Time Mapping
• The micromouse maintains a 2D grid in memory where each position holds:
• Whether a wall exists on each of its four sides (north, south, east, west).
• The current distance value from that cell to the center.
• Whenever a sensor detects a wall, the corresponding edges on adjacent cells are flagged, and the algorithm propagates updated distance values to reflect that new obstacle.
3. Recalculation Strategy
• After each move, only cells whose shortest‐path distances might have changed—because a wall was discovered—are recalculated.
• This avoids recalculating the entire maze on every step, improving efficiency while still guaranteeing an optimal path to the center as soon as the robot has enough information.
1. Place the micromouse at the starting corner of the physical maze.
2. Power on the robot so that it begins executing the flood‐fill routine.
3. The robot will explore, map walls, and update its internal grid until it can identify the shortest path to one of the center cells.
4. Once the optimal route is known, the robot will promptly navigate to the maze’s center.
firmware, logic modules, and sensor configurations are included in the repository to interface with the micromouse’s distance sensors and motor controllers.
⸻
Although this code was written specifically for the 2016 Universidad Simón Bolívar competition, the flood‐fill approach and mapping strategy can be adapted to any standard grid‐based maze of similar dimensions.