Micromouse - Maze Solver - Theory

Submitted by hazzer123 on February 28, 2008 - 1:03pm.

In the theory section we will cover:

  • Maze Solving Algorithms
  • P Control
  • Stepper Motor Theory



Maze Solving Algorithms

 

Solving mazes has been studied for years and years in mathematics, which means there are too many algorithms to name here.

An algorithm is a set of instructions that, when carried out, produce a certain result. The result in our case, is a route to the target destination of the maze.

 

The simplest maze solving algorithm is the random algorithm, which just goes forward in the maze until it comes to a wall. It then randomly chooses right or left and then goes forward again. With this algorithm, the mouse will always find the destination (if there is no time limit), but it will almost definately use a very inefficient route to get there.

 

The next algorithm is based on quite an ingenious thought. Imagine you are stood in a maze which has non-permeable walls and flat, level floors. You also have a hosepipe. If you turn the hosepipe on, the water will start filling the maze. The shortest route to the target destination will be taken by the first drop of water that arrives there. This is why it is called the 'flooding' algorithm. This algorithm ensures you get the shortest route (not necessarily the fastest though).

We will use the flooding algorithm since its a fairly easy concept and produces more than sufficient results.

 

The Flooding Algorithm

 

Here is an example of the flooding algorithm in action:

 

So in the animation, you can see the maze is first flooded. In our hosepipe analogy, the numbers represent the distance the 'water' has travelled.

Then the route is found by starting at the destination cell and following the path of decreasing numbers. This method ALWAYS finds the shortest route. It is not always the fastest route though, since a short route may have many more turns in it, which take longer. But it will do for now.

 

Now, you might say "But the mouse doesn't know where the walls of the maze are when it starts". That is true. But if you just use the algorithm with the walls which the mouse knows about, and then update the map everytime a new wall is found, it works fine.

Here is an example of a mouse doing just that -

 

(I sped up the animation after a bit because it was taking ages to make, but the concept is clear)


The black walls represent actual maze walls, the green walls are ones which the mouse knows about.

 

When the target is reached, the mouse will remember its route and be able to travel back up and down it (required in the micromouse competition).

 

So now we know how the algorithm works, lets see how we will implement it in software.

 

 

Software Implementation

 

Here is the code for the flooding part of the algorithm -

 

  1. currentPathDistance = 1; // This is how far the 'water' has flowed
  2. while(1){
  3. for(x = 1; x <= 5; x++) { //Creating a loop which scans the whole maze
  4. for(y = 1; y <= 5; y++) {

  5. if(cell[x][y] != -1) //If the cell has already been reached, then continue to the next cell
  6. continue;

  7. if(highestNeighbourCell(x,y) != -1) //If there is a neighbouring cell which has been
  8. cell[x][y] = currentPathDistance; //reached, then you have reached the current cell
  9. //so give it a value
  10. }
  11. }
  12. if(cell[dist_x][dist_y] != -1) //If the destination cell has a value after a sweep, the algorithm ends
  13. break;

  14. currentPathDistance++; //Increment the distance because we are scanning again.
  15. }
  16. //The highestNeighbouringCell(x,y) function returns the value of the highest, accessible (ie there
  17. //are no separating walls) neighbouring cell.

Initially, all the cells are given a value of -1, except the micromouse's current cell, which is given value 0.

Then the grid of cell values is scanned. On the first scan, only the cells next to, and accessible to the cell where the micromouse is, will be given a (non '-1') value. That value is 1. This is repeated untill the destination cell has been given a (non '-1') value.

 


P Control

 

When the robot is roaming the maze, the wheels will slip. Even though we can be sure the left and right wheels are turning at the same speed, we cannot be sure that the robot is going in a straight line. To compensate for the errors that appear, we use a sort of feedback control system. The control system we will use is called P Control.

 

P stands for proportional

The idea behind P Control is to have an output, in this case our motors, and a feedback input, our IR sensors, and use the data from the feedback to change the output value accordingly and proportionally.

 

Here is a scenario where the robot is not central in the pathway -

 

 

The output of the left-looking sensor will be less than the output of the right looking sensor because it is further away from the wall (IR sensors decrease their output when the object goes away).

If we take away the value of the right-looking sensor from the value of the left-looking sensor, we will get an answer which is positive. It will also be proportional to the distance away from the sensor. We will call this our error.

Now if we add this error to the speed of the right motor, and subtract it from the speed of the left motor, it will cause the robot to turn left. This will reduce the error since the robot will go towards the centre of the pathway.

 

Here is a scenario where the robot is on the left of the pathway -

 

Here our sensors have different values again. But this time our right looking sensor value is smaller than the left-looking one. So when we do the same calculation (right - left) we get a negative value for the error.

When we add this to the right motor speed (which is actually slowing it down - its a negative error) and subtract it from the left motor speed, the robot will turn right. This again reduces our error by moving the robot to the centre.

 

Here is a scenario where the robot is in the middle of the pathway -

 

 

Now, let's analyse this situation using P control.

The output of the left-looking sensor will be the same as the right looking sensor because they are equal distances away from their opposite walls.

If we take away the value of the left-looking sensor from the value of the right-looking sensor, we will get an answer of 0.

Now the motor speeds are unaffected by any additions or subtractions of the error. The robot continues as it is, at the centre of the pathway.

 


Stepper Motor Theory

 

I have written a member tutorial here, which explains how a stepper motor works and how to drive it.

The aim of this section is to explain how to acheive acceleration with stepper motors.

 

With DC Motors, when you apply a voltage, the motors will automatically accelerate to a speed proportional to the voltage. Stepper motors don't do this. Acceleration with steppers requires a pulsing signal in which the pulses become increasingly shorter each time.

 

In order to create these pulses we need to look at the maths of linear motion -

If

s = distance travelled (m)

u = initial velocity (ms-1)

 

a = acceleration (ms-2)

t = time (s)

Then

s = ut + 0.5at2

 

 

Example Problem 1 - If an object starts at 3 ms-1 and accelerates for 5 seconds at 2.5 ms-2, what is its final distance travelled?

u = 3ms-1

a = 2.5ms-2

t = 5s

 

s = 3*5 + 0.5 * 2.5 * 32

s = 15 + 11.25

s = 26.25 m

The distance is 26.25m. Easy Peasy

 

Example Problem 2 - How long would it take an object to move 20m if it accelerated at 3ms-2 from rest.

 

u = 0ms-1

a = 3ms-2

s = 20m

 

s = ut + 0.5at2

s = 0.5at2 (because u = 0)

t2 = 2s/a

t =?(2s/a)

 

t = ?(40/3)

t = 3.65s

 

To use these formulae for our stepper motor acceleration we will use the equation in Problem 2. We will calculate how long it takes for the stepper to take 1 step, to take 2 steps, to take 3 steps, to take 4 steps and so on... The time delay between consecutive steps will then be calculated by finding the difference between the two steps. Since lots of calculations are required, excel is the best for this. Here is my Stepper Acceleration Calculator.

 

 

 

AttachmentSize
Stepper Acceleration Calculator.xls22 KB

general comments

First, I'd like to say that I really like those path planning animations you made. I will definitely link to them in my pathplanning tutorials I have planned.

 

Next, for your P control section, you should comment on what happens if your robot is not parallel to the walls (at some angle to the wall), or if the wall separation distance is unknown. Basically, funny stuff will happen that needs to be accounted for.

 

Lastly, I recommend adding a distance vs time graph into your Stepper Acceleration Calculator (is that a good name for it?) just to make it easier to visualize.