Week 12: October 17 to October 23, 2011

Methodology

The Software

The algorithm can be developed independently according to each subsystems, however many interconnection considerations must be made upon integration of the whole system. The basic flow of the algorithm design processes will be as follows:  

 

1. Basic motion

• The microcontroller board will be programmed to control the rotation of the motors precisely.

2. Straight-line and turning movement

• The microcontroller board and motors are attached to the chassis. The control system algorithm will be developed to move the Micromouse either in straight line or turning right or left. The Micromouse must be able to complete both a 90º and 180 º turn.

3. Basic sensor data acquisition, verify correct interpretation of data

• The sensors will be attached to the chassis and microcontroller board. The sensors will be tested to ensure the Micromouse is reading the correct values under various operating conditions.

4. Maze-solving algorithm

• Maze-solving algorithm is a technique to solve a maze quickly and efficiently. Modified Flood-Fill algorithm is the most common technique currently used by Micromouse designer which has proven to be successful. Thus, Modified Flood-Fill algorithm will be the basis of the maze algorithm.

The Modified Flood-Fill Algorithm

The modified flood-fill algorithm is similar to the regular flood-fill algorithm in that the mouse uses distance values to move about the maze. The distance values which represent how far the mouse from the destination cell, are followed in descending order until the mouse reaches its goal.

 

 

As the MicroMouse finds new walls during its exploration, the distance values need to be updated. Instead of flooding the entire maze with values, as is the case with the regular flood-fill, the modified flood-fill only changes those values which need to be changed. Let's say our mouse moves forward one cell and discovers a wall:

 

The robot cannot go west and it cannot go east, it can only travel North or South. But going North or South means going up in distance values which we do not want to do. So the cell values need to be updated. When we encounter this, we follow this rule:

If a cell is not the destination cell, its value should be one plus the minimum value of its open neighbours.

In the example above, the minimum value of its open neighbours is 3. Adding 1 to this value results in 3 + 1 = 4. The maze now looks like this:

There are times when updating a cell's value will cause its neighbours to violate the "1 + minimum value" rule and so they must be checked as well. We can see in our example above that the cells to the North and to the South have neighbours whose minimum value is 2. Adding a 1 to this value results in 2 + 1 = 3 therefore the cells to the North and to the South do not violate the rule and the updating routine is done.

Now that the cell values have been updated, the mouse can once again follow the distance values in descending order. So our modified flood-fill procedure for updating the distance values is:

Update the distance values (if necessary) Make sure the stack is empty Push the current cell (the one the robot is standing on) onto the stack Repeat the following set of instructions until the stack is empty: { Pull a cell from the stack Is the distance value of this cell = 1 + the minimum value of its open neighbors? No -> Change the cell to 1 + the minimum value of its open neighbors and push all of the cell's open neighbors onto the stack to be checked Yes -> Do nothing }

 

Reference:

http://www.micromouseinfo.com/introduction/mfloodfill.html