Micromouse - Making the Maze

 

A test maze is essential to fine tune all the various algorithms and control routines when making a micromouse. Without one, you cannot be sure your mouse will perform well on the day, if it performs at all.

 

There are detailed specifications of a competition maze at this website. Of course, we won't be building a 16x16 test maze, that would be silly. We are going to build a 5x5 maze, since its small enough to store in a bedroom, and all the different maze problems can be implemented in it. We will also make the walls reconfigurable, so we can see how our mice handle different types of mazes.

 

Tongue and Groove

To make the walls reconfigurable, we will use tongue and groove type of connections between the walls and posts.

 

 

 

 

The main board will have 16 holes drilles in a 4x4 grid spaced 180mm. The picture aove shows a 5x5 grid of holes because I forgot that the outer walls will need no reconfiguring.

 

16 posts will be made with 4 grooves on each one -

 

 

We also need to make some wall pieces -

 

 

Making the posts

 

The easiest way to make the posts is to cut a few long (about 1 m each) sticks with 12mm square cross section. Cut the grooves in the wood then chop them down to size.

 

  To cut the grooves, use a *name* -

 

 

Lay your stick sufficiently clamped down and configure the groove cutter to the right measurements -

 

 

Place the groove cutter on the wood and start working :D

 

When you have cut all your grooves. Measure out lots of 5cm long pieces and mark them. Leave a couple of mm between the measurings so you can sand them flat.

 

 

Cut the between the little markings (the ones with a couple of mm between)-

 

Then sand down to the markings to ensure a good finish.

 

 

 

 

 

Micromouse - Maze Solver - Theory

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
   
3. while(1){
4. for(x = 1; x <= 5; x++) { //Creating a loop which scans the whole maze
   
5. for(y = 1; y <= 5; y++) {
6. 
   
7. if(cell[x][y] != -1) //If the cell has already been reached, then continue to the next cell
8. continue;
9. 
   
10. if(highestNeighbourCell(x,y) != -1) //If there is a neighbouring cell which has been
    
11. cell[x][y] = currentPathDistance; //reached, then you have reached the current cell
    
12. //so give it a value
    
13. }
14. }
15. if(cell[dist_x][dist_y] != -1) //If the destination cell has a value after a sweep, the algorithm ends
    
16. break;
17. 
    
18. currentPathDistance++; //Increment the distance because we are scanning again.
    
19. }
21. //The highestNeighbouringCell(x,y) function returns the value of the highest, accessible (ie there
22. //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.5at²

 

 

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 * 3²

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.5at²

s = 0.5at² (because u = 0)

t² = 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.

 

 

 

Micromouse - The Electronics

 

The Part List

 

Here is a list of all the parts i needed to build the robot (excluding basic tools).

Part Description	Quantity	How much I paid	Where I got it	Extra Info
Nema 17 size stepper motor	2	£14 each	Rapid Components
Sharp IR GP2D120	2	£12 each	Active Robots	Make sure you get the cable with the JST connector. Some companies ship the sensors without.
Microchip PIC18F4525 microcontroller	1	Free Sample	Microchip Samples	You'll need an obscure email address to register. I used one from tranceaddict.net. This is a great source of chips, but don't abuse it. Only get what you need.
Connectors Sockets	4x3-way 1x5-way crimp terminals	~£2	CPC Farnell	You can buy crimping tools to make the cable making process easier. I managed with just pliers but it was sometimes quite unreliable. Check out the connector tutorial.
Connector Pins	1x5-way 4x3-way 2x6-way	~£2	CPC Farnell
ULN2803 chip	1	£1	CPC Farnell	Array of 8 transistors for driving the motors.
7-segment LED Display	1	£1	CPC Farnell	A tutorial for these is here.
7805 5V Voltage Regulator	1	50p	CPC Farnell
Resistors	1 x 10K 2 x 100R	Nearly nothing	I had them allready.	If you don't already have resistors and capacitors, you can find them at any hobby electronics store.
Capacitor	1 x 1mF10V 1 x 470uF16V 2 x 22pF	Nearly nothing	I allready had them.
10MHz Crystal		£1	CPC Farnell
Stripboard (Veroboard)	117x368mm	£5	CPC Farnell
5mm thick acrylic	about 25x35 cm	Not sure	School	If you can't find acrylic, there are many other types of material you can use. HDPE, plexiglass, maybe even MDF.

 

Making the main microcontroller board

 

UNFINISHED******************************

Micromouse - Videos

Here are some videos of the robot.

 

Moving

When the robot first started moving, i put some videos up on Youtube. Here they are-

Here it is just turning on the spot. This tests the motor driver board and the stepper motors to see how quickly they can run.

This video shows the stepper motor acceleration (explained in the Theory page).

 

Wall-Avoiding

Before I had a maze build, i made the robot into a wall avoider. Here are some videos -

 

This is the robot with very simple bang bang on-off control. When something gets too close to the robot, it stops one motor.

 

This is the robot with P Control. This time it speeds up and slows down the motors proportionally to the distance an object is away from the mouse.