Chassis Layout

When you are planning your mouse, where are you going to put all the bits? There are a few key points to consider but, in the end, you are going to be constrained by the availability of parts and the available mechanical skills required to build the beast.

Centre of mass
You will need to keep the mass low for better acceleration with small motors. Keep the centre of mass low to improve cornering performance and to prevent excessive weight transfer off the wheels under acceleration and braking. Keep the components close to the centre of mass to avoid excessive moments of inertia for turns. In particular, look-down sensors on wings can contribute excessive moments, limiting your ability to start and end a turn.

The greatest mass is likely to come from your batteries and, if you are using stepper motors, from those. Stepper motors benefit from high voltages and that means more batteries. Remember that you mouse only needs to run for fifteen minutes or so. There is not much point in putting in, say, 1500mAh batteries if they will keep it running for an hour or two. Dry cells have a better energy storage density than NiCds or NiMH cells and, for the competition, may well be worth the expense although they have very poor voltage regulation. NiCds are, of course, much more cost effective for development. NiCd cells can be soldered together in any combination you want so you should be able to make conformal batteries that can be placed close to the motors. Make the batteries easy to replace and keep a set (or two) of fully charged spares to hand. Everyone forgets to turn things off sooner or later.

Planform
The main processor board may well turn out too large to make turning in the maze convenient. Make sure you mount it high enough (6cm or more) so that it can clear the tops of the walls during turns or near misses. A handy option is to make the circuit board part of the chassis construction. Use a multi-layer approach if you have to. Several small boards can be stacked together. An advantage of this approach is that you can modularise your mouse. Use a board for the processor, another for the sensors and a third for the motor drivers.

Strength
Some time or another, your mouse is likely to crash. It could do that at top speed into an immovable object. Will it survive? If not, making it stronger may not be the best answer. Weight (or mass anyway) is the enemy of acceleration. Build light and resilient. Allow things to bend or break off easily to absorb crash forces. Those forces are larger for heavy items. Have a look at Dave Woodfield's Voyager and you will see a mouse where the main chassis is strong but all the bits that stick out are held on with elastic bands. Make delicate parts easy to replace and keep spares handy. Put a fuse in your battery supply to prevent a crash shorting the battery. Nicads release huge amounts of energy when shorted. Once the smoke has been let out, it is very difficult to put it back.

Chassis Size

Is bigger better? Probably not.

The inside dimensions of a maze cell are just 168mm square. The cells are spaced at 180mm and the walls are 12mm thick. Make yourself a single cell with life size walls. Not only has your mouse got to fit in there it has to move and manoeuvre in that tiny space. Say you find yourself at the end of a 12 cell passage and it is a dead end. You either have to back out or turn around. The clever among you may build a bi-directional mouse, do a virtual about-face and drive on. The rest of us had best turn around. We don't really want to knock into the walls while doing it but we may not be able to guarantee our position that well. Ensure you have a healthy margin in all directions. If you ever hit a wall, you are in deep trouble. All you odometry data now becomes suspect. If the mouse cannot tell that it has hit anything, it will not know it is using suspect data. Even so, build crash recovery into your mouse software.

It may be better to accept a touch penalty and pick up your mouse, replacing it at the start, than trying to work out how to make it recover.

The entire mouse must fit into a 25cm square. While this sounds like a lot, you might want to have down-looking sensors that hang over the maze walls. Using the maximum available width allows about 35mm overhang beyond the walls on each side. This is fine if you are correctly positioned in the maze. Consider what happens if you are off centre with an offset error or have a severe heading error. How far out can you be and still have the ability to detect one or both walls. If you can't do that then you can't correct your error. The section on sensors has more to say on this.

Since excessive size carries a serious performance penalty for a racing mouse, there are those who think that the size limit should be scrapped as it has no point.

Here are some drawings showing he key domensions you will be working to:

Geometry

Geometry? Well I couldn't think of another single word that described the arrangement of the wheels and so on.

Basically you have a few choices when you come to decide things like how many driving wheels to have. Is more better? Will you be steering with the driving wheels? How are you going to go round corners and what do you do on an uneven surface.

To tackle the last point first you should note that any arrangement that has three wheels or points of contact will always have all of them on the ground at the same time. Assuming you don't have a high centre of gravity and fast turns that is.

The section on steering has some stuff to say about the arrangement of wheels for steering so lets think about a few other factors.

For stability, your wheels want to be a long way apart. Too far apart and they will make it difficult for you to navigate corners. If you ever want to travel along diagonals in the maze, the total track must not be more than about 110mm.

Big wheels make light work of irregularities in the maze floor. You don't have to turn them so fast to get a good turn of speed but small rotations of the wheels will correspond to relatively large distances on the ground. If you have shaft encoders on the driving wheels, can you get enough resolution out of them if those driving wheels are big? Don't gear up your distance sensors or slop in the gear train could finish you off.

What will happen when you hit a bump. As already pointed out, you could end up with the driving wheels suspended in the air. I have seen that happen, not funny really. Having four, driven wheels means that you can always drive out of trouble like that. If you have only three points of contact, you cannot suffer that problem. Small wheels or castors will have more trouble going over bumps. With some of the mouse weight resting on a castor, can your mouse push/drag it over any reasonable bump? Can it do so without losing track of where it is?

For a wheelchair mouse you might have a castor or some such front and back or just at one end. If the castor is only at one end, you must be sure that some of the weight of the mouse always rests on it. The more weight that rests on the castor, the more stable the mouse will be. There will also be less weight on the driving wheels and so less acceleration or a greater tendency for wheelspin.

As you accelerate, the weight distribution on the wheels will change due to reaction torque in the mouse body. Four wheel mice do better here. A wheelchair mouse with a rear castor will suffer a reduction in weight on the driving wheels as it accelerates. On the other hand, weight will be transferred forwards under braking. Either way, you don't really want to lose contact with the floor or you run the risk of tipping over. With only three points of contact, your mouse may tip alarmingly under heavy acceleration or braking.

As you accelerate and brake, there is the chance that your wall sensors will move up and down. Can you reliably detect the walls when this happens? Sprung suspension and a forward castor will eliminate this but is mechanically more complex.

Put the castor as far as you can from the driving wheels to minimise many of these effects. If you have a front and rear castor then spring one and/or ensure that you can't beach yourself on steps. The rules say steps should be no more than 0.5mm but take no chances.

What are you going to use for a castor. An actual castor wheel is a bit of a nuisance. Firstly, it needs room - both height for the wheel and space for the thing to rotate. It will need to rotate freely through a full 360 degrees. As they rotate, they change the distance from the drive wheels and thus the height of the wall sensors. Unless well made and mounted, they present lateral forces to the mouse as the castor rotates. This could upset navigation. If you want to make one, have a close look at the pinch roller from a personal cassette player. These are a very convenient size and preformed for the job.

Skids made from nylon or teflon are very effective. Relatively low friction, a convenient size and easy to mount. It took some searching out but I found a furniture skid that is just about perfect. The profile allows it to climb 1.5mm steps with very little resistance. Not as good as a wheel but very easy. Just make sure they carry the minimum amount of weight required to keep the mouse stable. If you have the tools, you can make skids from nylon rod that will have whatever profile you like.

A popular choice is the ball transfer unit. These are basically a large ball-bearing in a case with a lot of little bearings inside around them. They have very little friction and do not react poorly to changes in direction in the way that castors do. On the down side, they tend to be large, and you may have to hunt about for just what you want. A small unit is not necessarily better as the ball may make hard work of climbing steps. For example, a unit with a 12.5mm ball may be 20mm in diameter. Will you have room for this with the batteries?

DC Motors

DC motors will almost certainly give you the best combination of power to weight ratio and top speed.

A DC motor is intended to work from a direct current supply. Voltage is applied to the motor terminals and the motor begins to rotate. As the armature picks up speed, a voltage is induced in the windings that tries to oppose the current flowing in them. Quite quickly, a speed is reached where a balance is established and the motor speed stabilises. The speed at which this occurs is a function of the applied voltage and the motor characteristics. The amount of turning force, torque, that the motor can produce is a function of the current through the windings. As a load is applied to the motor, the speed drops and the current increases. A load just sufficient to stop the motor is the stall torque and will correspond to some particular (and fairly high) current through the windings. You don't want to do that to your motor, the energy can only appear as heat. Try to avoid letting the smoke out or it won't want to run again.

Motors run most efficiently at some relatively high speed (thousands of RPM) where the available torque will be significantly less than the stall torque. Since you want your wheels to turn at, perhaps, 1000 RPM, you will need to use gears. The effect of gears is to step down the output speed while multiplying the available torque. For example, ignoring losses, a 10:1 gear ratio will increase torque by a factor of 10 while reducing drive speed by the same factor.

You can choose to make a gearbox or buy one. Motors with gearboxes are available in the required sizes but are expensive. Think carefully about motor layout. Consider putting the motors side by side with a spur gear driving the wheels. A suitable right angle drive could allow the motors to sit along the axis of the mouse. Don't forget to include the ratio of the final drive gears in your calculations.

While these motors are expecting a direct current to drive them, it is much more efficient to use a supply that is switched on and off repeatedly. The width of the on pulses is varied so that the motor sees the average amount of energy flowing. Pulse width modulation (PWM) of the motors is not too complicated to achieve. The section of processors has more on this. You will need to select a pulse repetition rate that is quite high. A few hundred Hz is just not going to do it. However, a rate that is too high will be less efficient because of the inductance of the motor windings. Should you pick a frequency in the audible range, you will have to live with the motors whining at you (and everyone else) all the time. Somewhere in the range 20kHz - 40kHz will probably be fine. Try to ensure that the rate does not cause trouble by interfering or beating with other events. For example, I would expect trouble if the motor PWM repetition frequency was 20kHz and you had IR sensors modulated at 40kHz. Noise from the motors might find its way to the IR detectors. Change the frequency to, say, 23kHz where there are no simple common factors.

There will have to be some way to measure the speed of your motors. This may be the same as measuring the speed of the wheels but need not be. The wheel speed is really needed for working out position - absolute measures of speed are not really important except to tell if you can stop before some point. Slop in your gearbox may well mean that there is a pretty scruffy relationship between the motor speed/position and the wheel speed/position. Some motors are available with incremental encoders or other feedback devices built in. These tend to be more expensive. I did find some very nice Maxon motors with built in quadrature encoders at a ham radio rally for a few pounds but you rely a lot on luck in that sort of endeavour. They turn at about 9000RPM on a 9 volt supply and should be rather good geared down by about 6:1. Small incremental shaft encoders can be attached to the drive train - did I mention these were expensive? The Hewlett Packard HEDS9100 is a fairly compact encoder module. It requires a code wheel attached to the output shaft and give 1000 pulses per revolution. You can easily use this as a combined motor and wheel speed sensor. For a 35mm wheel, this will give you a positional accuracy in the order of a fraction of a millimetre.

While running, your motor speed will be controlled in a software feedback control loop. Regular measurements of wheel speed are taken and used to calculate a new value for the PWM pulse width. This is a classic control problem - solutions are available almost anywhere (except here - yet).

Gears

Sorry - this page is not yet ready

Motor Dynamics

Just how good do your motors need to be?

For the sake of this section we will have to make some gross simplifying assumptions. In particular, we shall assume that we can apply constant forces to the mouse and that there are simple, first order frictional effects at work and rolling friction is constant. In practice, motors vary, the available torque is not constant with speed, inertial effects limit how fast we can get motors turning, braking is not the same as accelerating, the floor surface varies quite a lot and gremlins upset everything at random. While these are gross simplifications, they will serve to get some kind of a feel for the problem. You can refine your model to suit your circumstances or you can live with whatever really happens. Like most people, you probably don't care and will only believe what actually happens when you switch on. If competition is your aim then winning surely is a (the?) goal. In that case, you will need to have some idea of how and where to optimise. For example, is it going to help to put in bigger motors, more batteries, different tyres, software changes...?

Try to remember that many mice don't even finish and any kind of result may well put you ahead of the rest. At least one UK prize has gone to the only mouse to find the centre while apparently 'better' or 'faster' mice failed or crashed.

Looking around other pages here, you will see that, for a reasonably competitive mouse, you will need to sustain an average speed, including bends, of about 0.8 m/s or better. Straights, especially long ones could get much faster. Dave Otten's MITEE mouse III, raced in 1990, boasted a top speed in excess of 3.5 m/s. You probably want to aim for a top speed of at least 1.5 m/s. The control problem starts to get much worse at high speeds. While you can almost certainly keep the wheels turning and drive in a straight line, you need time to respond to your sensors. Speed runs, will use slightly different rules to exploration runs. During exploration, the speed will have to be kept relatively low because you don't know what is ahead. When the speed run starts, your mouse should know exactly where it is going and can concentrate on not crashing.

The maximum rate of acceleration is constrained by two things - friction between the mouse wheels and the maze floor; and the rotational inertia of the mouse and motor.

Friction is easily dealt with. The mouse exerts a downward force on the maze floor equal to its weight. The weight of the mouse is the result of gravity acting on the mass of the mouse. The coefficient of static friction between mouse wheels and the floor, determines what proportion of that force can be exerted by the wheels to drive the mouse forwards.

Once we have an idea of the coefficient of friction, we can calculate the maximum force available to accelerate the mouse. Typical values for the coefficient of friction are about 0.7 or so giving a maximum acceleration of 0.7g or about 7 m/s/s. Note that the mass of the mouse cancels out in these calculations so that a heavy mouse exerts more downforce but is more massive and so resists acceleration better.

You can immediately see that there is a real advantage in selecting a good tyre if you want sparkling acceleration. Since the maximum accelerating force is a fraction of the downforce, increasing that downforce without increasing mass would be good. We can't make use of wings like formula 1 cars but at least one mouse has tried using a fan to create low pressure under the mouse.

You can't go on accelerating for ever. Sooner or later there must come a balance between driving force and friction, at which point your speed will be constant. If you have a motor powerful enough to push you along at a very high speed, you may find you have a problem reliably controlling it at low speed. There may well be a times when you would like your mouse to move at speeds of millimitres per second rather than meters per second. For example during crash recovery or to re-establish some benchmark position within the maze. So, for high positional accuracy, you will want a fast turning motor with a high reduction ratio. For speed, you will want a low ratio. Compromises, ever compromises.

How fast should it go? Here is a table showing the required wheel speed to achieve a given mouse speed for a range of wheel diameters:

Wheel speed (RPM)		Ground Speed (m/s)
		0.5	1.0	1.5	2.0
Wheel diameter	25	380	765	1146	1529
(mm)	35	273	546	819	1092
	45	212	425	637	850
	55	174	347	521	695

The page on gearing has more to say about motor and wheel speeds.

Motor Equations

A brushed DC motor of the type likely to be used in a micromouse is modeled as a combination of an ideal motor with a built in series resistance, R_motor.

The ideal motor turns at a speed determined by the voltage (emf) applied to it and provides a torque proportional to the current passing through it. Since the motor windings have a finite resistance, some energy is lost in the windings. There is also a limit to the current that can pass through the motor for a given applied voltage and hence the amount of torque that it can develop.

Motors have an armature that will have a particular moment of inertia. even with no outside load, a motor will take a finite amount of time to run up to speed because of that inertia and because of friction present in the bearings. For most purposes the frictional losses should be small enough to ignore.

Motor Equations

If you hold the shaft of a DC motor stationary and apply a voltage to the terminals a torque will be developed in the motor. The value of that torque is the stall torque for the motor and is dependent only upon the current flowing and the characteristics of the particular motor. Another way to examine the characteristic of a motor is to spin the armature at a known speed and measure the open circuit emf generated at the terminals.

These two tests allow us to write an important pair of equations that describe the behaviour of a DC motor:

Torque, T, is measured in Nm
Current, I, is in Amps
EMF, E, is in Volts and
Angular velocity, w, is in radians/sec

The units for K_T are Nm/Amp and for K_V, they are Volts per radian per second

If you are not happy with radians per second then multiply RPM by 2*pi/60 to get rad/sec. If you ensure that you use the correct units you will find that KE and KT have the same value. Thus, if you can measure one, you will know the value of the other.

Running at Constant Speed

If you connect a real motor to a battery, you will find that it will spin up to a speed that depends upon the battery voltage. It cannot just go faster and faster because the spinning of the armature generates a voltage, the back emf, that opposes the applied voltage. For the motor to spin at all, there must be some current flowing. That current must also flow in the motor resistance and so there will be a small voltage drop (IxR) across that internal resistance. Now we have an equation for the actual speed of the motor when a voltage is applied to it:

Consider an actual motor - the RF300 type common in cassette and CDROM players. At its rated voltage of 3V, the stall torque is given as 0.0024 Nm at a current of 0.265 Amps. Thus the value of K_T is 0.0024/0.265 = 0.0091 Nm/Amp. The motor resistance is R = V/I = 3/0.265 = 11.3 Ohms.

Now we connect the motor to a 3 Volt supply that has a negligible internal resistance. The motor spins up, drawing just enough current to proved sufficient torque to overcome internal losses. That current is measured at 0.022 Amps. Solving the motor equation (3) we get

3 = 0.022 *11.3 + 0.0091*w
w = (3-0.022*11.3)/0.0091
= 302 rad/sec.
= 2900 RPM

We can calculate the motor torque under these conditions from the equation above. In this case it will be T = K_TI = 0.0091*0.022 = 0.2mNm.

Suppose we load up the motor with some additional load, keeping the appled voltage the same. As the torque increases, the armature slows down, the back emf decreases and so the current rises. At some point the current rises sufficiently to generate a torque that exactly matches the load and the speed stabilises again. Now, however, there will be a higher current flowing through the internal resistance and power will be wasted just heating up the motor. In the ultimate case, the motor will be stalled and all the current will be heating the windings. For our example motor, at 3V the motor dissipates 0.8 Watts as heat. Not a great deal but the heating effect is one of the factors that will limit the top speed of the motor. Other factors include the frictional and dynamic losses in the motor (and any attached drive system), the quality of the bearings, the anticipated motor life as well as losses in the commutator. Should we wish to run this motor at 12 Volts, its stall current would become 1.06 Amps and the motor would dissipate nearly 13 Watts - as much as a night light. It would probably not last long under those circumstances

Still, free running at 12 volts (if the bearings are good for it) would, in principle, have the motor running at a fair speed. More torque is needed to overcome the mechanical losses and this particular motor draws 0.085 Amps at 12 Volts. Repeating the previous calculation indicates it should be running at about 11,600 RPM. I don't suppose it will last long but they are cheap and the average micromouse does not expect to run for hours.

Acceleration

There is a separate page about selecting an appropriate gear ratio for your mouse. Assume for now we have chosen a gear ratio and wheel size for the mouse. For the purpose of illustration we will use the following values:

Gear Ratio, G = 5
Gear efficiency, Eff = 0.8
Wheel Diameter, D = 0.035 m
Mass of mouse, M = 0.4 kg
Number of motors = 2
Intended acceleration, A = 4m/s/s

The torque at the wheels, T_W, required for this acceleration is readily calculated from Newtons equations

F = MA and T_W = F * D/2
F = 0.4*4 = 1.6 N
T_W = 1.6 * 0.035/2 = 0.028 Nm

The gearing means that the motors only need to provide a fraction of that, plus a bit to overcome efficiency losses in the gear train. There are two motors and they share the load equally. Thus the required torque for each motor, T_M, is

T_M = T_W/G/Eff/2
T_M = 0.028 / 5 / 0.8 / 2= 0.0035 Nm

From the earlier motor equations, we can calculate the current required for each motor, I_M, to provide that torque:

I_M = T_M/K_T
I_M = 0.0035 / 0.0091 = 0.385 Amps

Simply applying 4.5 Volts across the motor will produce that torque at startup. However, as the speed increases, the back emf also increases, the motor current drop and acceleration is reduced. We really want to be able to produce those kinds of accelerations even while travelling at speed.

A fairly typical NiMH, AAA cell of 750 mAhr might have an internal resistance of about 0.1 Ohm. A battery consists of a number of cells in series. A battery made from 10 of these cells would have a total internal resistance, R_batt, of 1 Ohm. Current flowing through the motor also flows through this resistance and so, the higher the current we want, the greater will be the loss due to the internal resistance of the battery so reducing the available voltage to drive the motor. Suppose for now that we have no additional losses in the motor driver, although a typical bipolar driver may cost us another Volt or two

So, we want to know how fast we can go while still accelerating at our nominal 4m/s/s. In order to produce the torque required, our motor needs 0.385 Amps. That current must flow through the motor resistance so we must have

(11.3 * 0.385) = 4.34 Volts

across the motor.

Both motors will be running so the loss from the battery will be

2 * R_batt * I_m Volts
= 2 * 1 * 0.385
= 0.77 Volts.

Now, the remaining voltage available from the battery can all be taken up by the back emf of the rotating motor. In this case it will be

(10 * 1.2 - 4.34 - 0.77) = 6.89 Volts

From the voltage constant equation for the motor we can calculate how fast the motor will be turning when the back emf is 6.89 Volts:

w = E/K_E = 6.89/0.0091 = 757 rad/sec = 120 revolutions per second

This means the wheels will be turning at 120/5 = 24 revolutions per second and with a wheel diameter of 0.035 m, our mouse should be doing

3.14 * 0.035 * 24 = 2.65 m/s

Which is pretty good

Top Speed

The final top speed of the mouse will be somewhat higher than this value and is a little more difficult to be confident of. Again, as the speed increases, the available current reduces until the system is in equilibrium with only just enough current being drawn to overcome losses in the mouse. Such losses are difficult to calculate and I would suggest that the only way to know would be to have the mouse monitor actual current and keep a record. This running current should be much less than the current required during acceleration but will be more than the unloaded current measured above. Suppose it is 0.120 mA for this particular configuration.

Each motor would then drop

0.120 * 11.3 = 1.35 Volts

as a result of its internal resistance.

Battery losses will be

2 * 0.12 * 1 = 0.24 Volts

leaving us with

12 - 1.35 - 0.24 = 10.41 Volts

for the motor back emf. This corresponds to a speed of 1144 rad/sec at the motor and (1144/5/6.28)*(3.14*0.035) = 4 m/s for the mouse.

I have made a spreadsheet in Excel with these calculations (and a few more) so that you can try out figures for your motors and mouse.

Download it as dcmotorcalcs.xls

Stepper Driving

So, lets assume you have a pair of suitable stepper motors for your micromouse. I have used the RS 440-420 steppers. these are a Nema17 size motors rated at 5V, 500mA drive.

The data sheet shows a winding resistance of 10 Ohm, inductance 6 mH and a holding torque of 70 mNm.

These will directly drive a wheel of outside diameter 50mm. Since the motor is a 200 step design, a single step will be 3.14*D/200 = 0.785 mm. However, I will drive it with a half stepping sequence giving me 400 steps per revolution with each step being about 0.39mm. the half-stepping sequence gives a smoother response and better performance at speed. The exact distance on the ground is not worth calculating up front. It is better to calibrate with your mouse by running, say, 5000 step (about 2m), measure the distance actually travelled and divide by 5000. For the micromouse, all distances are based on cells and steps. For the calculations below, I will assume a single cells is 450 steps long.

Driving Electronics
The drive electronics will be provided by an Allegro SLA7024 IC. This chip can drive a single motor in either unipolar or bipolar mode with chopper controlled current limiting. What this means in practice is that you provide as high a voltage as you can afford to carry in terms of batteries. The maximum current through the motor is limited by the driver and is easily set by a single potentiometer. The best performance from stepper comes from driving them in this way. A micromouse might carry 12 NiMH cells giving a nominal 14 Volts or so. Directly applying this to the 5V rated stepper will over heat it and reduce performance fairly quickly. A typical circuit for this chip is shown below.

You can check the data sheet here SLA7024. One annoyance of this chip is that the designers seem to have taken delight in making it hard to physically wire up. The lead spacings are inconvenient and the pin arrangements do not lend themselves to a neat circuit layout. however, it does its job very well and is popular for this application.

If you don't want the expense or complication of the specialist chip, you could use the simpler and cheaper UCN5804B stepper driver. This takes step and direction pulses and is much more convenient to use. However, if you are to run from a high battery voltage you will need a resistor in series with the windings to limit the motor current. Say you have a 14 Volt supply for these motors. The current limiting resistor can be placed in the common power supply and would need to be about 15 Ohm. With a current of 500 mA, the power dissipated in this resistor would be 3.75 Watts so you want at least a 5W rated resistor. This should, ideally, not be a wound type (the common one) at the inductance of the resistor may limit the start-up current in the motor. Now, not only is a suitable resistor a little hard to find, bulky and hot to the touch, you are wasting nearly two thirds of the energy in your batteries keeping the room warm. Compromises ever compromises.

Check out the data sheet to see just how easy the 5804 is to use UCN5804B.

Sequencing
If you use the 7024, you will need to provide a suitable set of signals at the inputs to the chip that will turn on and off the coils of the motor in the correct sequence. Check the data sheet for the appropriate sequence. Each motor needs one chip and each chip needs four signals. Thus you have a single port being used to control the two motors. The direction of the motor depends upon the order the coils are excited so by stepping up or down a table of values in the microprocessor, you can get full control. A bit of twiddling with the upper and lower four bits of data at the port gives independent control.

If you would rather not do this, you can use a sequencing chip like the L297. It takes step, direction and full/half signals and does all the sequencing for you. This is very convenient as your motor driver routine only has to worry about generating a single pulse on a single pin. The L297 works at normal logic levels and lives in a 20 pin DIL package.

There are other functions in this chip which are not used in this application.

You can have a look at the data sheet L297.

The 5804 driver also needs step and direction signals and is very easy to use.

Speed Control
You can't just bang away at stepper motors and expect them to do things. Steppers have a maximum torque at low speeds. the torque falls off quite dramatically with increasing speed. A high drive voltage helps to maintain the torque at higher speeds.

Because the motor is used in an open-loop configuration, you must, at all costs, avoid the motor stalling or missing a step. The key is a suitable acceleration and velocity profile.

At low speeds with the drive electronics shown, the motor might provide a torque of only about 50 mNm. That is about 2 N at the wheel rim, per motor. This is enough to accelerate a 1 kg mouse at about 4m/s/s or 0.4g. Now, 1m/s/s for our mouse is around 2500 steps/s/s.

The available torque will decrease quite rapidly with speed and so will our ability to accelerate and decelerate. Consequently, we are unlikely to see accelerations of 4 m/s/s in practice.

For calculations, work in steps. All the events in the control of a stepper occur at intervals of one step of the motor. As the motor changed speed, the time between steps changes. This is quite different from the way you would drive a DC motor where fixed time intervals are used.

To drive the motor, you need to emit pulses at decreasing intervals until you have reached some maximum rate and then increase the intervals again until you come to a halt. The intervals can be calculated from the acceleration and the step number by rearranging a bit of the common equations of motion.

s is the distance travelled, here in steps, a is the acceleration, in steps/s/s and t is the elapsed time, in seconds.

Rearrange this to give

Now we use a program or your favourite spreadsheet to generate a table of values. The elapsed time is not much use to us so we calculate the time difference between successive steps to get a table that will look something like this:

step	t	timer (s)	timer (us)	pulse rate
0	0.00000	0.0000	0
1	0.02828	0.0283	28284	35
2	0.04000	0.0117	11716	85
3	0.04899	0.0090	8990	111
4	0.05657	0.0076	7579	132
5	0.06325	0.0067	6677	150
6	0.06928	0.0060	6036	166
7	0.07483	0.0056	5551	180
8	0.08000	0.0052	5167	194
9	0.08485	0.0049	4853	206
10	0.08944	0.0046	4590	218
11	0.09381	0.0044	4366	229
12	0.09798	0.0042	4171	240
13	0.10198	0.0040	4001	250
14	0.10583	0.0038	3850	260
15	0.10954	0.0037	3714	269
16	0.11314	0.0036	3593	278
17	0.11662	0.0035	3482	287
18	0.12000	0.0034	3381	296
19	0.12329	0.0033	3288	304
20	0.12649	0.0032	3203	312
21	0.12961	0.0031	3124	320
22	0.13266	0.0031	3050	328
23	0.13565	0.0030	2982	335
24	0.13856	0.0029	2917	343
25	0.14142	0.0029	2857	350
26	0.14422	0.0028	2801	357
27	0.14697	0.0027	2747	364
28	0.14967	0.0027	2697	371
29	0.15232	0.0026	2649	377
30	0.15492	0.0026	2604	384
31	0.15748	0.0026	2561	390

The column that you would use in your code is the fourth one which shows the time between pulses needed to control the processor's timer. This example assumes that you have a 1MHz clock for the timer. The actual table may have as many entries as you like although beyond about 500, the numbers are beginning to differ only by a couple each time and so the granularity of your timer makes it not worth getting too carried away. With the figures shown above, your motor will be stepping at about 1500 steps per second. Each motor will be doing this so your processor will be handling 3000 interrupts per second. Be sure to keep the code for the interrupt routines small and efficient. You should also try to be sure that there are no interrupts with a higher priority than the stepper driver. Once they are up to speed, a missed pulse or two will send them out of synchronisation and the motor will stall. The usual result is the mouse doing a rapid, unexpected turn into a wall. Guess how I know that? At 1500 steps per second, our example mouse will be doing about 580 mm/s or a little more than 3 cells per second.

Software
Actually driving the motor is now fairly straightforward depending upon the resources available in your chosen processor. If you only have one timer on your processor, you are a bit limited. However, even if this is an eight bit timer, it is possible to run two motors independently. To do the job well, you will need a 16 bit timer which can be clocked at 1 MHz or faster. The simplest option, available on pretty well any processor, will be a single (16 bit) timer that can be programmed to give a single interrupt at a fixed frequency. A better alternative is to have two such timers that can be made to generate separate interrupts as the time out. Commonly available on most processors is a timer with some kind of output compare. the output compare allows the timer to run continuously. A register (one per channel) holds a value that is compared continually with the counter value. When they match an interrupt is generated. Many such counters also allow the automatic twiddling of an external bit on a port at the same time. From a programming point of view the two timer and the output compare method are similar and will be dealt with as one.

Single timer, single interrupt
Suppose you have a single timer. If it can be set to generate interrupts at some suitably high rate - say 5,000 per second - you can implement a version of direct digital synthesis to create a stream of events at any frequency up to the interrupt rate. In practice, you should only expect to be able to get to a fraction of the timer interrupt rate to avoid excessive jitter.

The trick here is to use a phase accumulator. This is a 16 bit value to which is added a constant at each interrupt. The result is allowed to overflow but we detect the presence of the overflow and use it to trigger our secondary event. For example, we start out with the phase accumulator at zero and add the value 5466 to it at each interrupt. After 12 interrupts, the accumulator overflows while changing from 60126 to 56 and we can send a pulse to the motor. After a further 12 interrupts, the accumulator once again overflows and we send another pulse. In this way, we get a motor pulse at 1/12 of the interrupt rate - about 417 pulses per second in this case.

The value for the constant, P, is readily calculated. Let F_T be the timer interrupt frequency and F_E be the desired event frequency, the accumulator is 16 bit so we have a further constant of 65536 to give:

P = 65536*F_E/F_T
P = 65535*417/5000
P = 5465

This is quite easy to calculate, especially if you do the multiplication first (as you should). There will always be some jitter in this arrangement. The higher your event frequency, the worse it will be. Increasing the interrupt rate may mean that you take up all your time processing interrupts. To drive two motors, use two phase accumulators and two event handlers. The data for the acceleration tables will need a little more care in generation than that shown above but is not impossible. Alternatively, you could have a third accumulator generating events at a lower rate of, say, 100 Hz and implement a more traditional motor control loop that operates in fixed time intervals. New motor velocities and steering corrections can be calculated at those rates rather than at each motor step. Now you can have very tight, fast events to put steps out to the motors. Remember to be sure that any changes to the values of the motor constants are atomic in as much as you must ensure that a value can not be used half way through a change made elsewhere. Remember also that you will have only 1/5000 second to do all this unless you implement a system of flags that allows the low frequency event handler to run asynchronously. You should not let the motor step event handler run asynchronously as it is important that the timing of the pulses is accurate.

One timer with output compare
Your chosen processor is very likely to have this option available to it in some form or another. The 16 bit timer counter free runs at some frequency chosen by you. For the sake of simplicity, we will assume it increments at a rate of 1 MHz. A higher frequency allows better control at high speed, a lower frequency gives the possibility of running the motor at lower speeds. Really low speeds are not so useful so go for a high rate if you can.

Each channel will have a register which can take a 16 bit value. as the timer counts through this value an interrupt is generated. Your code then steps the motor and fetches a new value for the compare register. The cunning part of this is that the new value is added to the old value because we are dealing in time intervals rather than absolute times. Thus, the next interval must occur after so many counts. You don't have to worry about overflow because both the timer and the compare register will be affected in the same way.

To accelerate the motor, just get the next value up from the acceleration table. Deceleration is a matter of getting the next value down. Be sure not to pass the bounds of the table and pick up rubbish. The table itself is conveniently held in flash/program memory.

Now we can describe the speed of the mouse in a particularly convenient way. We don't really care what the actual speed, in m/s, is. Instead, speed tells us how far up the table we are. A very useful benefit being that we always know exactly how many steps are needed to come to a halt.

Here is some sample code from a stepper application. It is written in C for the AVR processor:

// interrupt handler for one output compare channel
interrupt [TIM1_COMPA] void timer1_compa_isr(void){
   long remaining;
   if (stepper_enabled){      // a global flag can disable the steppers
   PORTC.1 = 1;		         // get the pulse done early to avoid jitter
   delay_us(10);              // it does not need to be long. The start of 
   PORTC.1 = 0;               // the pulse could be automatic if you want
   stepper_pos++;
   remaining = abs(stepper_target-stepper_pos);
   if (remaining > speed)	 // be sure there is time to stop
      speed++;
   else
      speed--;         
   if (speed > speed_max)     // not too fast 
      speed = speed_max;
   if (speed < 0)             // definitely not too slow
      speed = 0;
   OCR1A = OCR1A + timer_values[speed];
   }
}   

Each motor has a target distance to cover. You will see that there is no special need to see if we are past half way - only that we have room to stop.

The motors can be controlled independently or as a locked pair. Steering corrections can be fed in as changes in the speed of each wheel. Special movements like integrated turns can have their own acceleration tables.

A summary of this page is available as a powerpoint presentation

A simple spreadsheet for calculating the timer values is also available here .

Stepper Motors

A defining characteristic of a stepper motor is that, under normal circumstances, it is made to take up and hold one of a number of fixed positions. Movement from one of these positions to another is only by stepping it through a series of intermediate positions. A typical stepper motor might have 200 such positions in a single, complete rotation of the drive shaft. With little effort, this can be increased, on the same motor, to 400 steps. (Commercial drivers may increase this to thousands through microstepping).

Say we have a 400 step per revolution motor. Directly driving a 45mm diameter wheel, this corresponds to 0.35mm of ground travel per step. Trust me, it is remarkably easy to make the motor move a single step at a time.

Now, if we are able to make the motor move by, say, 5000 steps per second, we might achieve a ground speed of around 1.7m/s. Enough to be in with a chance in a serious competition. Much less than that will do to get started with.

So we have a motor that can be positioned to about 0.35mm as slowly as we want and yet might drive us forward at speeds approaching 2m/s. Surely there must be a catch. Well, yes there is.

First up, you may well find that you are unable to make a given motor run that fast. Better control electronics (all available as ICs so don't panic yet) and higher drive voltages might fix that.

Secondly, even if the motor can run that fast it may not have enough torque to push the mouse at those speeds. More drive voltage can help here and, of course, suitable drive electronics are available in the form of integrated circuits.

Thirdly, they are bulky and heavy. They also require relatively high capacity batteries - these are heavy too. Remember the need for higher voltages? More batteries. More weight.

There is no question about it, steppers are poor cousins in the power to weight contest. Nevertheless, they are worth looking at. And listening to - a stepper driven mouse makes a pleasing hum as the motors step at speed :)

Competitive mice can certainly be built with steppers, they are very easy to control and there is no messing around with motor control feedback loops and tacky arithmetic. A very large proporton of the SE Asian mice use stepper motors with great success.

A pair of NEMA17 size stepper motors glued back to back

For a micromouse, you are going to be looking for stepper motors in a NEMA type 17 body. All that means is that it will be about the right physical size. These are typically about 40mm square and can be mounted back to back with the wheels directly on the drive shaft to give a wheel track of around 90mm - just about perfect. This size of motor is what you can pull from old disk drives. Generally, although surplus motors like those will drive a mouse, they don't have enough of what it takes to run fast or deliver much torque.

Surplus disk drive motors look exactly like any other NEMA17 steppers but are designed to be used at 12Volts with a drive current of about 150mA. In contrast, the Vexta motors I recently found at a junk sale (yes - a matching pair!) are the same size but are rated at 4V, 950mA. These will give a lot more torque and can be driven at 12V with a current limiting driver to give good high-speed performance.

In the UK, at least, suitable motors can be obtained from RS Components, These are part number 440-420 and are rated at 5V, 500mA.

To make a stepper driver, you are going to need to generate two, independent pulse trains. The widths are not too critical but it would be good if your processor can be interrupted when each pulse is generated. On each interrupt, you load up the timer value required to set the time to the next pulse and you are done. Very low overhead stuff this should leave plenty of processor time for tricky stuff like mapping and not running into the walls.

It is possible to drive steppers together and make steering corrections by missing steps on one or the other motor. If you do that you will be limited as to the maximum speed of your mouse. Stepper motors are quite sensitive about getting smooth pulse trains. Once they get messed up at speed, they are likely to just stop turning rather than slowing down. The result will be a micromouse that suddenly swings around one wheel to examine the wall a bit more closely. It is unlikely that you will recover.

Steering is best done by slightly slowing down the pulse train for one wheel. A microcontroller with a pair of spare timers can do this easily. A number of controllers have flexible output compare functions or programmable counter arrays. If you want, you could use an external counter chip like the 8253 which has three timer channels.

With a little more cunning, I am told you can do all the necessary work with a single timer on an 8051 processor. As ever, you choose between hardware and software for you complexity.

Battery Types

Battery size is really going to be determined by your choice of motor. Steppers will need higher capacity batteries than DC motors.

Nickel Cadmium (NiCd) cells are rechargeable with a terminal voltage of 1.2v per cell. They are capable of quite high current delivery. Selecting the correct type can allow currents of several amps from an AA sized cell (not for long though). NiCds can be recharged between 500 and 1000 times with care and are cheap in the long run for the power to weight they offer. When selecting NiCds shop around as capacities vary quite considerable for similar looking cells. Typical high street shop AA cells may be only 600mAh capacity when you can find cells the same physical size with 950mAh capacity.

A selection of cells: AA alkalines AA NiMH AA NiCd PP3 NiCd

NiMH cells are like more expensive NiCds and have, perhaps, twice the capacity but cannot deliver such high currents. Nevertheless, an AA cell can still deliver a couple of amps without too much strain. This really should not be a problem in a micromouse even if you are driving powerful stepper motors.

In fact, if you need the full current delivery of a NiCd, you have probably got a drive system that runs on steam generated by an electric heater - now there's an idea :).

NiMH cells are available in all the same physical sizes as NiCd cells and can often be used as drop-in replacements. They share the same 1.2v terminal voltage per cell which is constant through most of the battery life the difference is in the capacity. It is not hard to find AA size NiMH cells with 1500mAh capacity and AAA cells at 700mAh.

Dry cells (alkaline) have higher voltages and relatively huge capacities - probably twice that of NiMH. Too expensive for use during development, they are not necessarily a bad choice for a competition run if you are desperate. Watch out for poor voltage regulation during discharge though. There are circumstances where dry cells, in spite of their apparent high capacity, appear to last less long than rechargeable cells.

Rechargeable alkaline manganese cells have recently become available at about twice the price of non-rechargeable alkaline cells. These boast at least 25 charge-discharge cycles - more if they are not allowed to completely discharge before being recharged. Terminal voltage is 1.5v rather than the 1.2v of NiCd and NiMH cells. Special chargers are needed for these cells.

Approximate sizes and capacities for a range of off-the-shelf NiCd cells:

A less common alternative is the sealed lead acid battery. These are most commonly used in burglar alarms and are available in a range of voltages and capacities. They can deliver very large currents but suffer an overwhelming disadvantage in terms of weight. Think of them as just like a small car battery and you will get the idea. In spite of the clear penalties, one of the UK's most well known mice, Maisie, uses a 12 volt sealed lead acid accumulator for energy storage.

More exotic technologies exist and are used in things like camera batteries. Ready assembled battery packs and fast chargers are available - at a cost.

A low current, DC motor driven mouse might be able to use the small but expensive non-rechargeable 6v Lithium Manganese Dioxide batteries used in some 35mm cameras. For example, the 2CR5 battery is 17mm x 34mm x 45mm, weighs only 37g and has a capacity of 1300mAh. Alternatively, a pair of CR2 cells at 3v 750mAh each. These are 16mm x 27mm and weigh only 11g. Finally, there is a PP3 package giving 9v 1200mAh

If you are really keen, you could try a couple of tagged Lithium Thionyl cells. These are very expensive but offer 3.7v per cell in a C size package (26mm dia x 50mm length) with a capacity of 8000mAh. While only good for about 180mA discharge rates, they will keep you mousing for about 44 hours non-stop at that rate.

Charging Batteries

Unless you insist on throwing money at alkaline cells, you will need to be able to recharge your mouse batteries.

It is a good idea, at the design stage, to make provision for recharging. You might want to incorporate a charging socket on your mouse so that you can keep the batteries topped up or even give them a fast charge between runs. Even if you do this, it is probably sensible to make it easy to change the batteries in an emergency. There are plenty of mice with battery packs glued in. I would not be comfortable with that as cells can fail leaving you with a potentially serious rebuild at a critical time.

Both NiCd and NiMH cells can be recharged with the same equipment if you are prepared to wait. The standard way of recharging these cells is with a constant current charger. They must not be plugged in to a car battery charger.

Standard charging of these cells is for 16 hours at a current of C/10 where C is the battery capacity. Thus, for a 700mAh battery pack, you would charge at 70mA for 16 hours. This is enough to bring the battery from fully discharged to fully charged. Clearly, partly discharged batteries will need less time. For all common NiCd and NiMH batteries, this charge rate can be maintained indefinitely without harming the battery.

When they reach full charge, the current going into the battery will just generate heat so a fairly easy way to see if your battery is recharged is to feel it. If it is noticeably warm, it is probably ready.

Constant current chargers designed for NiCd (and NiMH) charging are easy to find and relatively cheap. They do, however, expect to be used for removable cells which might not suit your needs.

Ideally, the charger will provide an electronically regulated current to the battery pack. If you are a little less loving of your batteries, you can make a charger from a plug-in 'wall wart' power supply. First, find a plug in supply which can comfortably give a voltage that is at least a couple of volts higher than the battery terminal voltage (1.2V per cell) at the desired charging current. You can pick a current that is up to about C/4 without too much danger so long as you don't leave the charger running too long. At C/4 the time for a full charge would be about 6 hours. Now add a series resistor between the power supply positive and the battery. This resistance will have to be calculated from:

R = (Vp - Vb) / Ic

where Vp is the power supply voltage under load, Vb is the battery terminal voltage and Ic is the charging current.

For example:

You have a 6 cell battery pack with a terminal voltage of 6 x 1.2V = 7.2 V and you want to charge it at 100mA. The power supply is rated at 9V at 100mA. The series resistor will be

R = (Vp - Vb) / Ic = (9 - 7.2) / 0.1 = 18 Ohm

Remember that the resistor will be generating heat. In this case about 180mW. Not too much but it would be sensible to choose a 1 Watt resistor to help ensure long life.

An LED placed in parallel with the current limiting resistor will provide a visual indication of charging. This can all be incorporated into the mouse electronics so that you can have the beast on charge while you are working with it. It would be sensible in this case to ensure that the charge rate is at least as great as the average current consumption of the mouse.

The circuit shown below is adapted from the Handyboard design. The bridge rectifier makes sure that there is no smoke if you get the wall-wart the wrong way round. R2 sets the charge current - you may want to mess with this. R1 and LED1 give a positive indication that the charger is on. D1 ensures that the battery can't drive the charging circuit and allows more than one charging point if you should want it. This should be a rectifier diode like the 1N4001 rather than a signal diode.

While your PC is talking to your mouse, you will have a cable connected to the mouse. Why do use the method employed by the Handyboard design and have the RS232 drivers off-board along with a simple charger circuit so that you only need one cable to the mouse.

Fast charging
If you are impatient, or just in a hurry, you might want to use a fast charger. These are readily available from model shops and can detect when the battery has been fully charged. This is possible because, during charging, the battery voltage rises steadily. At the point of maximum charge, the voltage starts to go down by a small amount. These chargers can detect the voltage peak and switch from high charge current to trickle charge. Such chargers are often called peak chargers or peak detecting chargers. A light on the charger tells you when it is ready.

This kind of charger is generally capable of fully charging a NiCd pack in 30 minutes or less. However, most rechargeable cells are not designed for this kind of abuse and may well give reduced life. To put it another way, mind out that they don't get too hot and let the smoke out.

NB - you cannot fast charge batteries in circuit. Without the peak detection, the charger will just keep on going and everything will get very hot. Similarly, you cannot have a diode in the fast charge circuit or the charger may not be able to detect the terminal voltage. They autodetect the number of cells when they start up.

Cells specially designed for fast charging are available from your local model shop and these should be used if you want to use a fast charger. Be sure to get a peak detecting charger and check that it will charge the number of cells you are using. Some chargers rely on a timer (bad) or can only handle a fixed number of cells (also bad).

My charger is made by Hitec. It can charge from 4 to 24 cells at currents of several amps. It also has a voltage display for those of you who just have to know. This charger can also manage NiMH. Not all chargers can as the voltage peak from these cells is much more subtle than that available from NiCds. If in doubt check with the supplier and don't just bash away with high charge currents.

Acceleration

Top speed and acceleration are clearly linked.

Ideally, you want to get up to speed as fast as possible, mindful of the need to brake again later.

Your grip on the floor and the power available from your motors will limit your maximum acceleration. To calculate this properly, you will need to know about the moment of inertia of the wheels, the motor and the mouse as well as the coefficient of friction of your tyres on the maze surface.

The maximum possible acceleration for a mouse that is not being sucked to the floor depends on the coefficient of friction between the tyres and the floor. You are unlikely to exceed 0.5g in a practical mouse and even 0.25g is probably quite reasonable.

Consider: from basic equations of motion starting at rest

v=at

s = 0.5at^2

With an acceleration of 0.25g (approx. 2.5m/s/s), you will be able to reach 1m/s after 0.4seconds over a distance of 200mm or about 1 cell.

This is not too shabby and will certainly do as a goal for now.

Try not to get too despondent over the fact that top-class mice now seem to be able to attain accelerations well in excess of 1g.

Corners

When you turn corners in the maze, you can do so with an in-place turn or an integrated or smooth turn.

In-place Turns An in-place turn means coming to a halt, spinning on the spot and setting off again. All this will tend to be time-consuming although relatively easy to perform. The rate at which your mouse can spin will depend upon the available torque, wheel friction and the inertia in your mouse design.

Integrated Turns Integrated turns are rather more difficult to do well. Approach and exit speeds must be carefully calculated and the velocity profiles for the two wheels is far from obvious and not too easy to calculate. In return for the extra complexity, you get smooth, fast turns which look really good and give you real competitive advantage.

How fast? If you go too fast around a corner, two things are possible. First you might lose grip with the maze floor and skid. Clearly, this is less than good. You can no linger rely upon your odometry data. The situation may be recoverable if you have not overdone it. Nevertheless, you don't see many mice doing handbrake turns around tricky corners. The second outcome is that you may tip over. Now this is would be the end of the race for you so it would be best avoided. Automatic recovery from such an accident would be pretty clever.

Lets have a look at the two possibilities, and decide which is the more likely and what the consequences are for the race. Bear in mind that these are models - simplifications to give some idea of the numbers.

Skidding Your mouse exerts a force on the floor due to gravity. When it corners there is an additional force due to centripetal acceleration. Just at the instant of a skid, these forces will be equal. The centripetal force depends upon the mass of the mouse, the square of the velocity and the radius of the turn:

The opposing force is determined by the mass of the mouse and the coefficient of static friction of the tyres on the floor

Equate these and rearrange to find the maximum velocity at which you can get around a constant radius turn without skidding.

ote that the mass of the mouse is not a factor here. Assume we have a right angle turn with radius 0.09m and a coefficient of friction of 0.7 (not too far out for rubber on wood - check yours). This gives us a maximum velocity of about 0.78m/s. The distance around the turn is 0.141m and so the turn will take 0.18 seconds.

With the coefficient of friction at 1.0, the maximum speed around a 0.09m bend would be 0.94m/s before you get to slide out. While increasing the coefficient of friction for your tyres has great benefits, you are chasing a law of diminishing returns in terms of cornering speed. It has been said however that the race is in the turns. Racing down the straights is relatively simple.

Don't worry about the outer wheel travelling faster. During the turn, weight is transferred more to the outer wheel and the equations all work out just the same. Remember how the mass of the mouse was not present in the equation?

Tipping

So, weight gets transferred to the outer wheel. What happens if we try and corner so fast that we are in danger of tipping up. How easy this is will depend upon how high your centre of mass is. It should be apparent that a tall mouse with a narrow wheel track will be more likely to tip over. Call the height of the centre of mass H and the wheel track (distance between the wheels) D. The weight of the mouse, W, acts downward through the centre of mass and the centrifugal force, F, acts radially outwards through the centre of mass, parallel to the maze floor.

o long as the resultant, R, of the two forces is within the wheel track, we will not tip over. We have already seen that the value of F is given by

and W is given by

By examining similar triangles, you should be able to see that, at the moment of tipping over

Rearranging gives

As an example, my mouse has a wheel track, D, of 75mm and the centre of mass is about 45mm above the ground. Substituting into the equation we get

Which give v = 0.86m/s (the inappropriate units cancel out)

Since I should only be able to do about 0.78m/s before the tyres slip, falling over will not be a problem for me. To be honest, if I could make it go fast enough so that I was anywhere near either limit I would be very happy indeed. A rather better built mouse with a centre of mass, say , 25mm from the floor and a wheel track of 90mm might be able to manage 1.26m/s before tipping.

Before your mouse gets to tip over, even if it does not slide on the ground, you may lose traction on the inner wheel with pretty disastrous consequences for your odometry.

Or, to summarise,With a moderately sensible mouse design, you will not tip over before you skid out of control (unless you hit something...). If you want a real speed machine, you will need to get the centre of mass down as far as possible. It should not be too hard to get it down to 30mm or so which, for the example above, improves your maximum cornering speed to about 1m/s

Smooth Corners

Although easy to calculate and easy to perform, an in-place turn with your micromouse is a big time waster. That type of turn generally requires that the mouse comes to a complete halt, turns around and then sets off again. While this is probably the sensible thing to do in a dead end, most turns will be a lot quicker (and draw admiring sighs from the audience) if you can perform a smooth, coordinated turn with the mouse not seeming to pause. This type of turn may be called a smooth, integrated, coordinated or slalom turn. Whatever you call it, you should certainly try and do one.

If you have a tricycle mouse, the soloution to these turns can be a bit more simple as the primary mechanism for generating the turn is the steering wheel. Indeed, if you also put a differential on the driving wheels, the steering wheel will do the work. Two-wheel, wheelchair mice, must perform the turn by careful coordination of the speeds of the two driving wheels.

Have a look at this picture showing the track of a mouse performing a simple 90 degree, right turn in the maze. The coloured lines show the track of the wheels, blue for the outer wheel, green for the inner wheel. The black curve is the path taken by the centre of mass of the micromouse. The radius of the turn is shown as R and will be 90mm assuming we get properly lined up in the first place.

The distance of the wheels from the mouse centre (half the track width) is shown as W. For the examples below, I shall assume a track width of 80mm so that W has the value 40mm.

The thin red lines are the cell entry and exit points and the turn has been divided into five segments

Segments A and E:
Since both wheels cross the entry and exit points at the same time, they will need to be going at the same speed when they do so. This speed is the entry velocity (V_e). It could be anything that suits but I will assume it is the same as the average cornering speed. That is, the speed of the centre of mass of the micromouse as it follows the black path. In practice, you are likely to have come thundering down a straight and will want to decelerate the mouse in a straight line to some suitable cornering speed.

Segment C:
For at least part of the turn, the mouse will be turning at a constant rate and the centre of mass will follow a segment of an arc with constant radius R. Although I have shown R to be half a cell width, it could be larger or smaller. The smaller R is, the greater the forces acting on the mouse. A large value for R give a more gentle turn but you run the risk of clipping the inside corner or over-running the outside. To work with a larger R, you may decide to have your mouse move towards the outside as it aproached the bend and come as close as you dare to the inside corner on the way through. this is how you would do the turn if you were in a racing car.

Segments B and D:
Clearly, during segment A, the wheels are turning at the same speed, equally, during segment C, they are turning at a constant speed that is different for each wheel. To get from segment A to segment C, the outer wheel must accelerate while the inner wheel decelerates.

We can draw a graph showing the wheel speeds as the mouse goes through the turn.

As before, the green line show the velocity profile for the inner wheel, the blue line that for the outer wheel.

As a useful simplification, I have used a constant acceleration for the wheels and applied the same value for each wheel. Also, the entry and exit segments are show as at some constant speed, equal to the average cornering velocity.

Calculating the values
First you will need to decide upon a safe average cornering speed for your mouse. This will depend upon a num,ber of factors. For example, the widthm height, mass, motor power, tyre material, recklessness, desperation and so-on. Speed runs will use higher speeds and accelerations, exploration will want to be pretty safe. Let us assume we want to be able to corner at a fairly modest (and easy to work with) 100mm/s.

The actual path taken by the wheels will not be perfect sections of a circle except during segment C. However, you will see later that the difference is small so I shall ignore it for now.

The average path length for this turn will be a quarter of the circumference of a circle with radius R:

P = 2*pi*R/4 = 3.14*90/2 = 141.3mm

At 100mm/sec, we would complete the curve part of the turn in 1.4 seconds. The outer wheel has to cover a distance of

P_o=2*pi*(R+W)/4 = 3.14*(90+40)/2 = 204.1mm.

Since we have to cover that distance in 1.4 seconds, the velocity (V_o) will be 144.4mm/sec

For the inner wheel, we only have to travel a distance of

P_i=2*pi*(R-W)/4 = 3.14*(90-40)/2 = 78.5mm.

This we can do at a velocity (V_i) of only 55.6mm/sec

The transition phases (segments B and D) mean that we must accelerate or decelerate the wheels as appropriate. Suppose we have set our maximum acceleration to be 0.1g which is nearly 1000mm/s/s (and is not terribly high).

The outer wheel must accelerate from 100mm/s to 144.4mm/s. This will take only about 0.044 seconds, during which time the wheel will have travelled a mere 5.4mm. At the end of the turn, segment D takes the same time and distance. So when I assumed the path was essentially circular, it turns out to be circular for all but 11mm. Close enough.

It is not quite true to say that the inner and outer wheels accelerate and decelerate at the same rates or that they take the same amounts of time to do so. However, it is a good enough approximation for now and the differences are small compared to the other errors present in a real mouse.

Implementation
Well, how does this work out for a real mouse. In general, you will need path-planning outines that can control the motors during each phase of the motion, ensuring that the wheels achieve target positions and velocities at the appropriate times. You task is made easier by the relative symmetry of the problem. Not only does the inner wheel slow down by about the same amount as the outer wheel speeds up, the turn is in two symmetrical halves. Once you are half way, you can reverse the procedure on the way out. Similarly, left turns are the same as right turns with the wheels reversed. Since we always cross the cell boundary with the wheels going at the same speed, combining turns is quite easy.

The simplest example is for a stepper driven mouse. Here, we do not have infinitely variable speeds and accelerations in most cases without a lot of real-time calculations. Instead, the steppers are likely to be driven from timing tables. For a given acceleration, there will be a fixed table of values determinnig the time between steps and hence the velocity. If you were to do the calculations properly, you would need to rearrange things to work in the distance domain as steppers move in fixed size steps. This is not worth the effort if you dont want to do it.

Instead, I will give you an example using the speeds calculated above and the values from the tables on one of my mice. This mouse can accelerate at 2.5m/s/s and is happy to turn the wheels at speeds of up to 500mm/s.

Here is the first part of the acceleration table calculations done in Excel:

Cornering at 100 mm/s average speed means that my motors will be doing about 224 steps per second with timing values coming from entry 5 in the table. The closest I can get to the calculated speeds will be 149.1 mm/s (entry 10) for the outer wheel and 58 mm/sec (entry 2) for the inner wheel.

Once I am at the appropriate point to begin the turn, travelling at 103 mm/s, I arrange for the inner wheel to decelerate for 3 steps and the outer wheel to accelerate for 5 steps. These take approximately the same amount of time and the transition is over in less than 3 mm of travel. Now I run at those speeds for a suitable number of steps - about 440 for the outer wheel and 170 for the inner - before allowing them to work their way back to their previous speeds and we will be travelling straight again.

Suppose testing showed I had miscalculated slightly? If it is a small problem, the turn can be tightened or loosened by having the outside wheel accelerate my one more or one less step respectively. With a stepper mouse and fixed acceleration tables, all actual travelling speeds are an approximation.

With a stepper mouse and taking a simple approach, I do not have to construct special acceleration tables for turns, I just need to precalculate the speeds and distances for each phase and work through the segments until I am done.

Printermouse uses this approach and seems to work just fine.

Speed

Pure speed is not the primary aim when building a micromouse. On the other hand, it is a race so, if you want to win, you have to be quicker than the rest.

It is worth making the point here that you must find the centre. Without that you might as well just bat about the maze at breakneck speed, hoping to stumble into the centre by chance. A strategy but not the best.

Unfortunately, just about all your problems get worse as your mouse runs faster. To start with, you are better off with a 'slow but sure wins the race' philosophy.

Wen you are confident that your basic algorithms all work and that you can reliably find the centre and the best route for your mouse dynamics, by all means turn up the volume.

A common strategy with competition mice is to map out the maze and find an appropriate maze then run the route faster and faster. It is best to stop before you crash as the consequences of a crash could be pretty severe.

Maximum speed is likely to be limited by one or more of a number of factors:

How far ahead can you see a wall. The further away you can see a wall, the more time you have to stop before hitting it.

How good are your brakes. Related to the previous item good brakes will mean you can afford to detect a wall at a closer distance and still be able to stop. Test away but remember that you will not know how much grip is available until you are actually on the competition maze which may be dry and dusty just where you wish it were not.

Correcting for steering errors. It is a rare mouse that can travel unaided along a corridor. The faster you go, the harder that task becomes. You cannot just increase the corrective action to compensate for speed. That way lies disaster. Just think of how many cars you have seen in ditches where the driver tried just that technique.

Can you see side passages? Slick exploration will allow you to detect turnings and decide, on-the-fly, whether you are better off going straight on or following the turning. This is best done without stopping. Can you recalculate the route, decide and make the appropriate manoeuvre in the time between detecting an opening and having to start the manoeuvre?

How fast is your processing loop. The basic processing loop that runs when your mouse is travelling should not be wasting too much time. This is unlikely but keep processor-bound delays to a minimum. For example, don't get caught reflooding the maze, updating an LCD display or making some (supposedly) cool sound effect when your mouse should be looking where it is going.

Tricycles

NB: there seems to be an error in these calculations. ...

In a normal tricycle mouse, the driving force will come through the rear wheels and a single front wheel will be used for steering. To a certain extent this can allow you to decouple the steering from the drive mechanism and control loops. Tricycles can be good for acceleration. As the power is applied, reaction torque will transfer weight to the rear, driving wheels giving you an increase in traction. If you overcook it however, the steering wheel may lift off the ground and your steering is gone. on the other hand, deceleration is a bit of a problem as weight transfers to the front of the mouse and the available braking force from the drive train is reduced. Remember that you cannot brake as hard as you can accelerate and all the bits of your mouse are more likely to stay attached.

Here is a diagram of a tricycle mouse:

• The red dot is the centre of gravity, distances are in green.
• m is the mass of the mouse
• Rr and Rf are the reaction forces for the rear and front wheels. That is, the weight on the wheels. The rear wheels are treated as one for now.
• F is the force applied to accelerate the mouse. It points that way to represent a restraining force that would hold the mouse stationary for the purposes of analysis
• g is the acceleration due to gravity.

So, lets see what the mouse can do.

Assume for the time being that we have plenty of friction between the driving wheels and the floor, what is the maximum acceleration that we can apply before the front wheel leaves the ground in a spectacular display of foolishness.

At that point, the sum of the moments about the point of contact between the ground and the rear wheels will be zero. Thus:

Fb - mgc = 0

From Newton, F = ma, where a is the acceleration of the mouse

mab - mgc = 0
ab = cg
a = cg/b

For my mouse (litmus), b = 24mm, c = 10mm so

a = (10/24)g
a = 0.42g
a = 4.1m/s/s

This is not world class performance but is more than the existing motors can manage and would be quite satisfactory for now. Later we shall see if there is enough friction for this acceleration anyway. When I first put it together, I put the batteries over the motors. That reduced c to about 3mm and the maximum acceleration to about 0.125g. Well, there was certainly enough motor torque and more than enough friction as litmus did an instant wheelie across the floor with me in frantic pursuit. As ever, there are confilicting design requirements. The CG needs to be low. That can be achieved and I may be able to reduce it to about 20mm which would increase the maximum acceleration to around 0.5g. To allow it to turn in the maze, the mouse needs to be short. However, for best acceleration (and worst deceleration), the CG needs to be well forward. If you place the CG a long way from the driving wheels, the moment of inertia becomes large and you need bigger motors

Right, what is the maximum acceleration we could achieve for a given coefficient of friction? Now, the maximum force that can be applied to accelerate the mouse is:

F=µRr

To find the value of Rr, we take moments about the front wheel. These will sum to zero:

mgd - Rr(c+d) + mab = 0

Substitute

Rr = F/µ
Rr = ma/µ

to get

mgd - ma(c+d)/µ + mab = 0
µgd - a(c+d) + µab = 0
µgd = a(c+d-µb)
a =µgd/(c+d-µb)

Rather than solve for µ, we can draw a graph of a as a function of µ, given d = 40mm, c = 10mm, b = 24mm

You can see that, to get an acceleration of 0.4g only requires a coefficient of friction of about 0.4. This should be easily obtainable with rubber tyres on painted wood. Usable coefficients of friction for rubber tyres on paint are in the range 0.5 to 0.8 giving us a potential acceleration range of around 0.5 to 1.0g for litmus (if we can keep the front wheel down).

From these calculations, I conclude that:

• I am more likely to flip this mouse over than suffer wheelspin when accelerating
• My maximum acceleration should not exceed 4.1m/s²
• I could do with getting the center of gravity lower
• A shorter mouse is easier to accelerate and turn but runs the risk of a wheelie
• As the CG moves forward, we get less chance of a wheelie but poorer acceleration due to reduced grip by the driving wheels.
• Short, small tricycles will have performance limitations that may make them uncompetitive at top level

Wheelchairs

A typical wheelchair driven mouse has a pair of drive wheels and skids, rollers or castors of some kind in front of and behind the wheels. For most of the time, three points of contact are used and the weight of the mouse is shared between the wheels and one or the other skid. The more weight you have on the skid, the less there is available to provide accelerating and decelerating forces through the wheels. Furthermore, as you accelerate or decelerate, there will be some weight transfer to the skid, reducing the down force through the wheels and reducing their grip. If you have a combination of low coefficient of friction and large weight transfers, there is the possibility that your mouse will skid under heavy acceleration of braking.

For the least weight transfer, the Center of mass of your mouse should be a low as possible. To allow symmetrical acceleration and deceleration, the Center of mass should be over the drive wheels. Weight transfer will be reduces if the skids ar as far away from the drive wheels as possible. Below is a representation of a wheelchair mouse. This one is Florence.

Distances are shown in green, forces are shown in red. The Center of mass is the red blob. the mass of the mouse is m and the acceleration due to gravity is g. The acceleration of the mouse is a.

The force F represents the accelerating of decelerating force. It is pointing backwards in this drawing to represent a restraining force while the mouse is acceleration. By restraining the mouse with the force F, we can use simple moments and equations from statics to see what is going on. Florence would normally travel to the left as seen in this drawing. The battery pack has been placed to keep the Center of mass near the wheels. The distances to the skid has been shown to the actual point of contact rather than the Center

Edgar

Edgar is my first real micromouse. An unbelievably long period of thinking and wishing eventually resulted in a mouse that is pretty much a UK version of all the mice you will see on the various south-east asian micromouse sites. Imagination and originality failed me utterly and they will get a stern talking to just as soon as I can find them. Still, you have to start somewhere and it has been hard enough making this work without coming up with every detail from scratch.

This is a tried and tested style of mouse with a pair of steppers for the drive train in a wheelchair configuration and a relatively powerful 80C196 processor to look after it. Plenty of batteries (12 at the moment) ensure a respectable performance from the steppers.

For a neat, compact design, the sensors are side-looking and fairly minimal with just three emitter-detector pairs in use at the moment. while they are capable of accurately measuring wall distance over a range of about 2-13cm, they are pretty sensitive to the reflectivity of the walls and need calibrating for the actual maze in use. I need to work on autocalibration which will be complicated by the non-linear response of the system. A surprising difficulty arises from the fact that they are very directional with beamwidths of only about 7 degrees. This is fine for detecting wall ends, but means they are very sensitive to being pointed in exactly the right direction. The next build will have to have them put into alignment blocks. to ensure accuracy and repeatability. As it is, a slight knock on the way to the maze or an unfortunate contact with the wall can result in mis-alignment.

EdgarB gets its name from being a development of Edgar which I guess could be called EdgarA but wasn't. It also does a bit of a waggle down the straights a bit like the dance that bees do in their hives.

The rest of the page will take a while to load. There is nothing here but a bunch of pictures for now.

I will be putting up a full description of Edgar sooner or later. All the design details will be here.

Edgar pictures

		The two motors joined for the first time. No going back now.
		Edgar is basically a pair of stepper motors glued back-to-back and screwed to a length of kitchen worktop joiner strip.
		The aluminium extrusions are ideal for this job.
		The size of the motors is just right to allow standard AA sized rechargable batteries to fit. The finished beast has twelve cells altogether - they do fit though.
		The 80C196 circuit board forms the basic shape and size of the mouse. This board came from Australia. It was the only ready-made board I could find for this processor. I did not want to hand-wire a board (too lazy) and did not want to design a 'proper' DSPTH PCB (too lazy and incompetent)
		Don't you love it when everything works out?
		Plenty of space for now but it soon goes when we want lots of batteries for those hungry steppers.
		Unfortunately, the stepper drivers will not fit on the processor board so we need another board for them. All that elegant sizing just went down the drain for the sake of the world's most ugly daughter board.
		Suddenly everything looks a lot less pretty.
		In case you are wondering, that thing at the back is a heatsink for the 5V supply - not a phased array radar. Now there's an idea - millimetric, side-looking radar. That should make all those optical mice look silly. You know, I really should get more sleep...
		One motor driver channel using the Allegro 7024 stepper driver chip. I really have to get that more compact.
		An early test setup to see if the dimensions were OK and to test an early, low-tech driver using 5804 driver chips. These are very easy to use but can not get the best from the motors which really need overdriving with current controlled drivers.

Minimus

A very simple scrap-box stepper mouse. Oh! Turns out I have no pictures of it. I shall have to remedy that.

Other mice

Depending on how you look at things, there are either a lot of other mice out there or there are surprisingly few.

In the UK there are a few regulars that can be seen at most gatherings and contests. Overcrowding on the race schedule is not, generally, a problem.

If you were to look at the south east asian area, you would find an enormous number of mice. It seems that every college and many schools have an entry along with a significant number of individuals.

I have collected a few details about mice. Many of these will be well-known in the UK. Some are from abroad. ather than carry over the older content from the previous site, I will update this section with a gallery of mice in due course.

Fee free to send in details of any mouse you would like to have included.

Differential Sensors

The simple kind of reflective wall sensors have a number of limitations. Chief among these is that they are very dependent upon the reflectivity of the walls. When you watch a mouse that uses these sensors, you can sometimes see it stear around dark or light patches. This is not very robust behaviour - especially at speed.

It would be nice if we could somehow eliminate this variability. Dave Otten's sensor design used a Position Sensitive Device of the kind specifically designed for this task. These are very effective albeit somewhat more complicated to construct and use.

A little thought will reveal that, if we can compare two sensors pointing at the same bit of wall but seeing different amounts of light, the ratio of the two readings should eliminate variability due to reflectivity. There are still plenty of problems to overcome but it was not unitl Duncan Louttit presented a paper on this kind of sensor at Minos'04 that I thought very seriously about them.

The basic arrangement would be something like this:

Sensor a is closer to the wall than sensor b. The difference in the amount of light seen by each will depend upon the distance, x, from the wall.

If we can combine the two readings in a suitable manner, the effect of reflectivy will go away. The question is how do we do that.

Duncan's paper can be found here:

Optical range sensing without lenses

I have been playing around with the maths to try and make the process a bit simpler. My observations are in a PDF file here.

Differential Optical Sensors

I have dumped it into a PDF because it is full of unpleasant formulas. I will turn it back into a web page one day.

The long and short of it is that I think you can obtain a linear function of distance by using differential sensors and only one multiply, one divide and a subtraction per measurement.

Where a(x) and b(x) are the sensor readings, and d is a constant, nominally the distance between the sensors. In practice, d would be chosen to produce an appropriate output scale.

There are still plenty of things that will make this kind of sensor unreliable. Not the least of them is the actual A/D sampling process. Since the samples are unlikely to be taken simultaneously, there will be some error due to both incident light modulation and simply because the mouse will have moved between samples. Or at least, it better had.

InfraRed Sensors

Many mice use Infrared reflective sensors. They are relatively easy to design and build and the parts are easy to come by. There are, of course, pitfalls. A competition maze is likely to be extremely well lit. It will be even better lit if there are film or TV crews present. If your sensors will not work in this environment give some thought to building them some appropriate shades. There may be other IR devices out there, some of them surprisingly powerful. Autofocus from cameras has been known to upset the odd mouse.

While I refer to IR here, some folk prefer visible light as they can at least see what is going on. It probably makes little enough difference - just be sure that the detectors are suitably matched for wavelength.

A major problem with any reflective sensor is that the nature of the surface can have a large effect on the size of the reflected signal. I read of one maze where the posts were significantly less reflective than the walls and some mice that relied on detecting the edges of cells got lost as a consequence. In another case, the red paint on the top of the walls turned out to be quite a good absorber of IR.

Reflective sensors really need to be AC coupled and synchronously detected to avoid problems caused by high ambient light levels, flashguns and the like. All this means is that you fire off the emitter, wait a bit an then read the detector. The output of the detector goes through a capacitor to filter out any steady state levels.

Suitable circuits can be found in the sections on each type of sensor.

Side-looking sensors really need to return an analogue signal whereas top-down sensors are more likely to produce a digital output. There is no reason why you cannot quantise side-looking sensor outputs to emulate the action of top-down sensors.

There are two particularly unpleasant aspects to the use of reflected light for detecting and sensing the positions of objects.

The radar equation
The first of these is the fact that light spreads out from the emitter. It also spreads out from the reflector. The result is that the returned intensity is significantly less than that radiated. Best case, it will be proportional to the inverse square of the emitted signal if reflected from a plane reflector, directly toward the receiver. Worst case is an inverse fourth power response.

It is not hard to detect weak IR signals - after all, your TV remote has no trouble most of the time and can even be bounced of the walls. The problem lies in the non-linearity of the response. If you can detect weak signals from distant walls you may be swamped by the strong response of nearby walls. Non-linear amplifiers can be used to overcome this. Alternatively, you could measure and use a lookup table in software to linearize your readings. Remember the aim is to get a reliable, repeatable and accurate measure of distance.

The cosine law
The second problem is the cosine law. This is just a way of saying that the level of reflected light depends strongly upon the angle at which it is reflected. The shinier the surface, the worse this problem becomes as more light is reflected and less is scattered. In the extreme, a mirror will only reflect in one direction.

The result of all this is that any measurement of distance (or even existence) can be hopelessly affected by the angle of the sensors. This is dealt with a little more in the section of side-looking wall sensors.

Odometry

Odometry deals with how far and how fast the mouse has travelled. If you are feeling brave, you might want to consider dead-reckoning as a means of navigation. here, you rely on information about how far each wheel has moved to calculate your position and orientation in the maze. This is almost certainly not a good idea. Small errors will soon accumulate into fatal miscalculations. Arrange for you distance sensors to recalibrate at appropriate points while running the maze. A good place is at the end of a straight. You know how far you should have travelled and how far you think you travelled. Reconcile these values and keep track of relative errors.

If you are using steppers, you command the wheels to take so many steps and expect them to do as they are told. Generally, this will be a fair assumption. There are ways for things to go wrong though. Wheel slip, caused by dirt or over-enthusiastic acceleration and braking, is one of them. Resonannce and mis-stepping is another. Steppers give you open-loop control. there is no way to know how far you have actually travelled until you find yourself in a position, such as up against a wall, which will allow you to calculate where you actually are. Consequently, you will need to take extra care with stepper motors to ensure that commanded steps are turned into actual steps without slippage or missed steps.

So long as you dont miss steps, stepper motors do give good absolute positionng. The error after a thousand steps will be the same as the error after two steps, and is generally small. Let us say, however, that you are using a typical stepper set up - 400 steps per revolution, 55mm wheels, 0.43mm per step. If every start/stop sequence loses you two steps and you hop from square to square down a 16 cell straight, you might find yourself about 14mm out of position at the end.

DC motors present a couple of challenges all their own. These motors are geared. Backlash in the gear train can cause havoc if you have a shaft encoder on the motor rather than the driving wheel. however, cheap/easy encoders with a few tens of sectors need to be placed at the motor to get sufficient resolution for good navigation. To achieve the same resolution directly from the driving wheels will require relatively high resolution, expensive encoders.

A good alternative, albeit mechanically more difficult, is to use a pair of wheels with encoders attached. Four wheel mice commonly use these. Positioned in the middle of the chassis they are mounted to maintain contact with the floor in spite of minor irregularity in the maze floor. The motor driver routines then close the loop between encoders and motors as part of a position control system.

Remember that your main aim is position control rather than velocity control. Your software will adjust motor speeds to achieve a given mouse position. There is a likely to be a tradeoff between good positional control and high speed - even before you get to the stage of skidding out of control on the corners.

Other Sensors

Quite a few other sensing schemes have been used.

A simple variation on the top-down sensor might be to have a row of sensors hanging over the walls and a light source shining up at them from below. The number of occluded sensors tells you your position. This will, of course, not allow you to detect walls in the next cell.

Mechanical devices have included wings that sit on the walls and rotate according to distance. These are coupled to the processor and are robust, effective and relatively simple. They are also clumsy and prone to collision problems. An elegant solution though and not to be underestimated. Nick Smith made the first mouse to find the centre of a maze in the UK and that used metal wings.

Laser diodes and position sensitive detectors have been experimented with although there do not seem to be many mice using them.

A line-scan camera could be constructed. Either a scanning laser spot or a scanning photosensor could be used to look for the high contrast between wall and floor. While mechanically relatively complex, the signal processing should be well within the capabilities of modern microcontrollers.

I recently took apart a hand scanner and found an ideal looking linear optical array with only ten or so connections that should be easy enough to use. So far, I can't find any data for it though.

A number of attempts have been made at full vision systems. There does not seem to have been a really successful solution - presumably due to the relatively high processing load such systems generate. I did read of a mouse that was supposed to raise a camera on a stalk an examine the maze from the start. I have no idea what happened to that idea but the possibilities are particularly intriguing. Imagine a couple of seconds to raise the camera, allow a (hopeful) five seconds to process the image, another couple to lower the mast and you are off. Home and dry in, perhaps, twenty seconds. It will be some time before the micromouse competition fails to find ways to challenge builders.

The GameBoy camera seems to have potential. It is small, has appropriate optics and can do some form of edge detection inside the device.

Sharp make a position sensitive detector, the GP2D12, which produces an Alan voltage proportional to distance. This is intended for use over a distance of 10 to 80 cm and would make an excellent detector of walls up to 4 cells ahead of the mouse as well as looking down side passages on the way past openings. I recently saw a calibration curve for one of these devices which noted that users should be careful not to confuse distances less than 10cm with longer distances. The reason is that output falls off below 10cm. It may be possible to use these devices for close-in wall measuring with some care. The main disadvantage appears to be the measurement rate of only a couple of hundred samples per second. This might not be much use in steering a mouse at 2m/s - you may only get a sample every centimetre or so. Worth experimenting with however.
[NOTE: a new mouse from Derek Hall uses this type of sensor with great results]

Ultrasonic devices can be power hungry and difficult to use over the short distances in the maze. At 40kHz, the wavelength of the sound is going to be about 7.5mm. This is going to be too small for phase measurements and, with time of flight around 160us, tricky to measure. There may be some clever signal processing hardware out there that can do it though

UPDATE: Those clever folk at the Technology Innovation Centre in Birmingham have a micromouse which uses ultrasonic sensors to great effect. It turns out that the time of flight is very measurable with a micro. I hope to have details about their mouse in the Other Mice pages soon.

Over the Wall wings

A popular choice is sensors that live on booms or wings and look down at the walls from above. These can be simple reflective switches connected to an eight-bit port on the micro. A perfectly adequate mouse can be constructed using eight of these on each side. Say, seven for the walls and one each shared to detect the forward wall.

The wing must be placed well forward of the wheels. You will need to see where the walls are before you get to them or the control problem is impossible.

As for other IR sensors these should really be AC coupled and synchronously read. You might like to just use ready-made reflective switches designed to work in adverse conditions.

The main problem with these arrangements are to do with the rotational inertia they present to the mouse. However light you make them, they have to live a relatively long way from the center of mass and so contribute a relatively large component of the total inertia. As long as you are prepared for that and don't expect breathtaking turn performance, they can have a lot going for them. Build them light and there will still be plenty of other things to worry about before rotational inertia becomes a limiting factor in performance.

These types of sensors can have a huge advantage in that they are able to detect walls in adjacent cells. Since they must overhang the maze walls, when you get to a post position, the outermost sensors will be able to see any walls perpendicular to the direction of travel. This may save you a lot of exploring - up to 50% if you are lucky.

Even though the sensors themselves are likely to be positioned quite a long way apart - say 5-10mm - it is possible to get slightly better resolution if you can get an analogue reading from them and interpolate the distances.

If you have already decided that you want to run diagonally, ensure that the sensors extend far enough to cover the walls in this mode.

Side-Looking Sensors

A good side-looking wall sensor will return an analogue value representing distance to the wall. The simple presence or absence of a wall is inadequate for steering. The greater the level of accuracy, the better. In principle a sideways looking, reflective sensor will give better results than a top-down sensor. However, variations in wall reflectivity, from cell to cell and maze to maze can make this difficult to use. You could try some kind of auto calibration while the mouse is running although it is likely that you will need manual calibration at the start of a run.

One of David Otten's mice was observed to have suffered from this kind of reflectivity problem. If I remember correctly, in one competition maze, the posts had different properties to the walls. Thus, the mouse was not able to reliably detect wall edges and had serious navigational problems. The sensors i use have to be calibrated for the actual maze it runs in. Some time I may get round to some kind of autocalibrate.

The simplest sensor is going to measure the intensity of light reflected from the wall and use it as a measure of distance. Even if you have a consistent reflective surface there will be problems.

The amount of reflected light will change non-linearly with distance. This is the result of the inverse square law. The intensity is proportional to one divided by the square of the distance. A non-linear amplifier could be used to compensate for that. If you don't then accuracy will become a function of distance - it will be better for a close wall than a far wall.

The cosine law determines the amount of reflected light in terms of the angle of incidence. Now the intensity is proportional to the cosine of the angle. This effect is not as marked as that for distance. For example the intensity may only change by 10% or so with angles up to plus or minus 25 degrees. The problem comes with smooth, shiny surfaces. Essentially, the more shiny the surface, the worse the problem. Don't paint your maze walls with gloss paint. Think of a mirror. When the light is perpendicular to the mirror, all of it is reflected back at the source. Change the angle just a little and all the light will be reflected away from the source.

You may overcome some of the limitations of the inverse square law by using more directional light sources and sensors, and devices are available with lenses for this purpose. Focussing the light may make the cosine law problems worse without some extra care regarding alignment.

Combinations of cosine and inverse square law effects may make it difficult to adequately determine offset and heading errors in your mouse. Many mice that employ reflective sensors point them a little forwards.

perpendicular sensors		angled sensors

The effect of this is that a mouse with a heading error only will still see a big difference in sensor readings from left to right whereas perpendicular sensors will show the same reading as if the walls had receded on both sides. Another advantage is that you move the sensing point further forward which will help with the dynamics of the steering control.

The following circuit is pretty much lifted from the circuitry of GENESIS 2.

Tests with a static set-up on a breadboard give encouraging results with surprisingly little variation from angle of incidence. (The cosine rule is moderately forgiving after all). The composite oscilloscope trace illustrates its use. A 7 microsecond burst on the emitter would be followed 10us later by capturing the analogue value at the output of the amplifier

Maze Files

No, not where to put it when you need the garage floor back...

One of the more useful properties of the maze is its size. At 256 cells, the whole thing was clearly designed to be convenient for microcontrollers. A single byte can be used to tell you which cell you are in and an array of 256 bytes can hold all you need to know about the maze.

For your micromouse controller, it is most convenient to use a single bit to indicate the presence or absence of a wall in the maze. Four bits per cell is easiest although you need only store two walls per cell if space is tight since the walls are all shared.

The most obvious solution is to arrange the bits like this:

----WSEN        

Using the binary bit value for each wall position, we have:

NORTH = 1
EAST = 2
SOUTH = 4 
WEST = 8

Now any combination of walls in a cell can be represented by a number in the range 0 to 15. Thus, the start cell would contain the value 14 which is 0x0E in hex or 00001110 in binary.

Adding and removing walls is a simple process of using bitwise and and or operations to directly manipulate the wall data. This is safer that adding and subtracting. In fact - don't do it by adding and subtracting - you will be asking for trouble somewhere along the line.

Say you want to add a wall to the North of cell 23. The operation would be something like this:

cell[23] = cell[23] or NORTH

Remember that whenever you add a wall to a cell, there is a corresponding wall in the neighbouring cell. The mouse generally does not remove walls from its map so you always modify the neighbouring cell. There is no need to worry about what happens at the map edges. the Northern row of cells all have a North wall and the Southern row of cells all have a South wall.

Make sure that the index that you keep for the cell number is an unsigned byte. That way, you can refer to the cell above as cell+16. This will always work. For example, cell 250 is on the top row. 250+16=266. Since the index is an unsigned byte, the value will wrap around to give you cell 10 on the bottom row.

Here is a code fragment for adding walls which should illustrate the idea (it is in no particular language):

addwall(cell,direction)
  maze[cell] = maze[cell] or direction
  if (direction = NORTH){
     cell = cell+16
     maze[cell] = maze[cell] or SOUTH
     }
  if (direction = EAST){
     cell = cell+1
     maze[cell] = maze[cell] or WEST
     }
  if (direction = SOUTH){
     cell = cell+240
     maze[cell] = maze[cell] or NORTH
     }
  if (direction = NORTH){
     cell = cell+255
     maze[cell] = maze[cell] or EAST
     }
end

In assembly language this is very compact and quick.

On your PC, you can save this as a binary file, 256 bytes long, on disk. Your mouse can transmit a 256 byte block representing the maze to your monitor program.

One variation which can make things convenient is to use this bit pattern for the walls:

-W-S-E-N

The advantage of this is that two rotate instructions have the effect of taking a quarter turn. This makes it easy to translate between the local view seen by the mouse and the world view of the maze solver.

You have used four bits to stare mapping information. What are you going to do with all those extra bits?

One option is to use them to store other flags. You might choose to remember whether a cell has been visited or to keep a 'no entry' flag to save looking at dead ends. Your maze solving routine might use these bits to indicate a direction for the speed run. I am sure you will come up with other uses.

Solving the maze

No use having a micromouse that can't solve mazes. Although it seems central to the task of creating a micromouse, actually solving the maze is possibly the easiest part of the entire job. Here are a couple of ideas.

There are many ways to solve the kind of maze found in micromouse competitions. A naive approach would be to follow the left or right wall in the expectation that it will eventually lead to the goal. This is only true for some, especially simple kinds of maze. Micromouse mazes are designed specifically so that this is not possible. Here the goal is in the centre of the maze and not connected to the outside of the maze by a wall. Thus, any attempt to follow the walls will just bring you back to where you started.

Many mouse builders have their mouse follow rules that, for example, ensure all four quadrants are searched or that turns are made preferentially in one or another direction depending on where you are. Some of these search algorithms can find themselves caught in loops and need special tests to detect problems. I can't think of a compelling reason to search in this way. Apart from the primary goal of finding the route to the centre which has the smallest number of steps, you might wish to at least circle the centre to try and be sure you have not missed any longer but quicker routes. Remember that the shortest path may well not be the fastest path for your mouse.

I believe the simplest method available to a micromouse is some variation on the flood-fill or Bellman algorithm. The idea is to start at the goal and fill the maze with values which represent the distance from each cell to the goal. When the flooding reaches the starting cell then you can stop and follow the values downhill to the goal.

The simple flooding algorithm works like this:

• Start with an array of bytes with one byte representing each cell in the maze.
• Put the value 0 into the cell that you are aiming for.
• Go through all the cells and make sure that each one has a value that is just one more than its smallest accessible neighbour.
• Repeat that last step until you have not changed the value in the starting cell.

Notice that there is no need to pre-initialise the map contents. This algorithm can take a considerable number of iterations. Worst case would see you doing all 256 cells a couple of hundred times. Say that it took you ten instructions per cell (it would be more than that I expect) and each one takes 0.5 microseconds, you might need around 0.25 seconds to solve the maze. In practice, the algorithm will run for as many iterations as there are cells in the longest path. This is likely to be only 20 to 50 cells and so you should be done in much less time. Even so, you don't want to be doing that any more often than you have to. In practice, you only have to when you come to a junction - i.e. a cell with three or four exits. At all other times, your action is predetermined and there is no decision to make.

To save a bit of time, a number of designers divide up their flooding algorithm and do just a bit of it as a time delay routine. Dealing with just one cell is a simple enough task and could be made to run in a fixed time regardless of content. Use this as a time delay in your speed control loop and with any luck, by the time you get to a junction, the maze has been solved in the background. If the solver has not finished then just finish the job while you are waiting to see which way to go.

Faster Maze Solving

While the in-place flooding method is reliable and easy both to understand and implement, you may want to opt for a faster algorithm.

You can create a queue in memory and deal with each cell once only. The code to do this is a little more complicated and you will need up to 256 bytes of additional memory. The payoff is in performance. The method described below will be 20 to 50 times faster for typical mazes.

There is no absolute need for fast solving but I can see how cutting the total time for a solve cycle from, say 0.5 seconds to 10 milliseconds would be a worthwhile improvement.

We will call the queue the frontier. You will see why when you look at the sequence shown below. As the maze is flooded, a wave front expands outwards from the target cell. It is only these cells that we actively deal with in the queue. As soon as the frontier reaches the starting cell, we are done flooding.

In general, the starting cell is any cell. To solve the whole maze, set the starting cell to the first cell in the maze. To reverse your path, set the target to the first cell and the starting cell to be the centre or your current location.

	Using the second method, first mark any cells that are adjacent to and reachable from the goal as frontier cells. Flag them and added to a queue of cells to be processed.		While there are cells in the frontier queue, process each one. The contents of each is replaced with the distance to the goal (either stored in the frontier queue or calculated from the neighbours as you go.
	The replaced cell then has its neighbours marked and placed in the frontier queue.		The frontier moves toward the start and the visited cells fill with numbers.

The next sequence shows the rest of the maze being flooded.

		You can clearly see how dead ends are handled and what happens when there is more than one way through. You will need to be careful about not adding a cell twice to the frontier list.
Once the frontier reaches the start cell you are done. The shortest route that you know of is now traced by simply moving to the neighbouring cell with the lowest value.

The algorithm will look something like this:

       create and initialise a queue with 256 elements
       create a routing map as an array of 256 bytes
       fill the array with the value 255
       fill the target cells(s) with the value 0
       add the target cell locations to the queue
       while there are items in the queue
         get a location from the tail of the queue
         if the cell does not contains the value 255 then
           for each accessible, unfilled neighbour
             put in it a value one more than the current cell
             add it to the queue
           end for
         end if
       end while
       

You can run this algorithm as often as you have processor time for.

There is actually no need to run it any more often than when you are in a junction cell and you want to decide which way to go.

One way to optimise your route for a speed run is to assign different weights to the neighbouring cells depending on whether you will have to turn to get to them and so on. With a fast flooder/solver, your mouse could try several strategies with test fills to determine the best possible route.

Other ways to Solve a Maze

Solving mazes is a problem that is ancient. At least as old as the stories of the minotaur and Theseus from Greek mythology.

It is hardly surprising then that there are a number of ways to go about solving a maze and that a lot of people have put work into maze solving.

What may surprise you is just how important the problem is, even in current times. Essentially the same problem occurs in routing printed circuit boards, sending network traffic around the Internet, autonomous agents and the artificial intelligence of game opponents.

Wall Following

Ask almost anyone how to get out of a maze and they will describe some form of wall following. Keep your hand on one wall and keep going, sooner or later you will get to the exit. This would be fine except for two things. Firstly, you may have to visit almost the entire maze before you find the exit so this can be a very slow technique. Secondly, the maze may have islands in it. Unless all the walls are eventually connected to the outside, you may wander around forever without reaching the exit.

There is a competition for wall-followers but you certainly will not succeed at the normal competition by following a wall. The maze designers will have made sure of that.

Bellman

This is the name of the flooding approach. Imagine pouring water into the maze. The water will fill the maze and the best route to where you want to be can be found by riding on the wavefront. Although this algorithm is generally called Bellman's algorithm, there are a number of variations developed by other people such as Lee. I have been unable to find a really good chronology of these method and so I cannot really be sure who did what. As far as the micromouse builder is concerned, these algorithms are the simplest to understand and to implement.

Look elsewhere on here for some practical methods for solving the maze in a micromouse.

Tremaux

In about 1882, a fellow called Tremaux described a process for solving any maze. It was described in terms of a physical maze and I have made no attempt to put it into any machine related form. What he said was this.

• As you walk down the maze, draw a line on one side, say the left, of the path.
• When you come to a new junction, take any path.
• At a dead end, or a previously visited junction, turn around and walk back the way you came.
• If you are on a previously walked path and you come to a previously visited junction, take any new path if there is one available.
• Never go down a paths marked on both sides.

Tarry

In 1895, Tarry published a method for solving mazes. You will need a sack of rocks.

• When entering a cell for the first time, place three rocks at the entrance.
• If this is not your first visit, place only one rock
• Pick an exit according to the following rules, in order:
  0 rocks - not been there before, drop two rocks and carry on
  1 rock - we have come in from there and we can leave that way. Drop one rock and leave.
  3 rocks - This is how we got here in the first place. Only leave that way if there is no other choice.
  2 rocks - We have been out that way before so don't go that way again.
• Only drop rocks if there are none already except as directed above.

This method will find a route but not all routes. It may not visit all the maze and will not automatically find the shortest route.

Theseus

A long time ago in a land far away...

The secret to this method is to enlist the assistance of a friend who has a long ball of string. Don't forget to go appropriately armed.

Examples

Here are a couple of example mazes. These come from old competitions and will give you some idea of what is going on. The numbers are created using the flooding algorithm described on the maze solving page. The highlighted path is the shortest route in terms of cells but may well not be the fastest for a smart mouse.

It would seem that you could chart the growing sophistication of competitive mice from the maze designs used in the competitions. For example, when mice began to do diagonal runs, mazes started to test that ability.

This maze seems to have taken little imagination to create. It comes from the early days of the competition and was used in a competition in the US in 1982. There seems to be little that can be done to optimise the route beyond that highlighted. I would guess that, at the time, most mice were concerned with the apparently simple task of running down a corridor. A task which is fundamental to the operation of a mouse and which is not as easy as it looks.

The next maze, on the other hand, was used in Japan in 1991. You can see several opportunities for a mouse that can run diagonally through the maze to improve its run beyond the highlighted selection. Notice that the diagonal improvements take just as many cells. I suppose that is by design rather than by accident. There is also the chance for a mouse with good straight-line speed to take a slightly longer path around the edge of the maze. How would you know you have found the 'best' route? Your searching algorithm may well miss the fast outside run. You should also see that some cells are inaccessible.

A good maze this one.

There have been many competitions over the years and so there are a good few examples of competition mazes. I have shown here a few more examples with possible routes marked on them. Remember that these are the simple flooded route and do not take into account the advantages of different styles of turn, diagonal running etc.

A note of caution is in order. I have no idea if these mazes are true representations of the actual mazes used. Other people have collected them and there are occasional differences in the drawings from different sources. You are also pretty well on your own when it comes to deciding exactly where which competition is referred to. You will need to make an educated guess from the file name.

Japan 1983:

USA 1983:

London 1992:

APEC 1993:

(APEC seem to specialise in hard mazes.)

Construction

So, you want to build your own maze. Well, you have to really want to. Many people have built full or partial mazes. A competition quality maze is going to be time-consuming and/or costly to produce. Remember that the finished article would be 3m square - I would have to remove all of the furniture in my living room if I wanted to put one in there. Imagine how well that idea would go down.

If you have the facilities, you can make one from 12mm fibreboard. It is called MDF in the UK and probably nowhere else. One of the benefits of MDF is that it leaves a very good surface which will need little or no preparation for painting. Chipboard needs the edges filling. You may be able to trust your timber merchant to slice a sheet up into suitable strips.

there is definately some 12mm laminated white chipboard (particle board) available somewhere. haven't found a supplier yet. I will put the name of a source here if I find one.

Use a jig to cut the walls to length (168mm). There should be no holes in the maze floor so the best way to join walls to posts is with a tongue on the wall and a slot on the post. The post will need fixing into a hole on the base. Since there should be a post at every lattice point you will need to drill a lot of holes accurately in the base. Use a jig for this as well.

A full size maze will measure 2.9m square (nearly ten feet). This is irritatingly just a bit too big to be made conveniently out of standard (in the UK) 8' x 4' sheets. Can anyone tell me why they chose such an arbitrary size? The original maze specifications had cells 7" wide. Another oddity. Why not 6 inches?

How big should I make it?
As a competitor, you may not have access to a full size maze and you are probably unlikely to have enough room for one anyway. Try building a couple of sections that you can put together in different ways. I have seen at least one mouse that could not cope with a full 15 cell run as it had never run over a distance greater than a quarter of the maze. Many builders manage an 8x8 practice maze. Even that will require about 5 foot square, similar to the space taken up by a typical double bed. Similarly, your searching algorithm had better not have any hidden bugs brought on by not expecting a full-size maze.

Accuracy
Notice that the rules give some fairly specific guidance relating to tolerances and imperfections in the maze. Try and ensure that you can cope with worse than those given. While you are searching and travelling relatively slowly this should not be too hard. The problems accumulate very quickly at speed.

Since the rules generally state that every lattice point must have at least one wall attached to it, you can build a maze using 180mm walls with a peg at one end with slot to make an integrated post. The other end will just have a tongue. An alternative is to just put pins on the lower edge of the walls and drill four holes at each lattice point.

The real bad news is that you are going to want to make 300-400 walls for a full sized maze. A single 8x4 sheet of material may yield nearly 100 walls. If you can cut these carefully enough, paint the sheets first, then cut them. This is a simple but tedious job. For my practice area, I used planed softwood. This measured up at 12mm x 47mm. The loss of height was no big deal because I use side-looking sensors. However, this material is far from stable and my walls are now all curved in one or more directions. I like to tell myself that, if my mouse can cope with these, it can cope with anything. Of course, I also like to tell myself that I will win on the lottery.

[As it turned out, when placed in a 'proper' maze, my mouse was delightfully smooth as it no longer had to try and follow the variations in paint colour on my low-grade walls. While I had the right idea, I had spent ages trying to get a smooth response to poor workmanship.]

Painting
Ensure that the paint you use holds no nasty surprises. Some black paints can be good IR reflectors and some white paints will absorb IR. Don't imagine that, just because the wall tops are red, that they are good IR reflectors. Remember that the maze you compete it is likely to have very different properties.

If you really want to get a feel for a competition run, make sure you have some very bright lights to simulate the lighting conditions of the competition. Oh, and try to have a number of autofocus cameras firing IR at your mouse as well :)

Generating Random Mazes

If you are able to do software development on your PC, you will probably be tempted to use or write a simulator of some kind. At a basic level these are not too hard to write. Probably, you want to be able to test search and solving algorithms. While there are a number of examples of actual mazes about, you may want to generate your own.

Drawing a maze on-screen is not too taxing in terms of software but rapidly becomes a pain as you carefully draw in all those walls. I have a program that automatically generates random mazes for me to use for testing. Before going any further, you need to be aware that random mazes are very unlikely to have those particular challenges that competition maze designers love.

There are several approaches to generating a maze. Perhaps the simplest and most reliable is to start with all the walls in place. Knock down the walls around the centre peg and place all the neighbouring cells into a queue, having marked them as visited. Now you work your way through the queue. All the cells in the queue are neighbours of a cell that has already been examined. Every time you take a cell from the queue, you remove the wall that joins it to a visited cell and add any new neighbours to the queue. When the queue is empty you are done.

What you have now is a so-called perfect maze with a single fully connected path. To make it more useful, you need to knock down some extra walls. The easiest approach is to remove a fixed percentage of wall at random. To be a little more rigourous, yu might like to consider removing a number of dead ends. This seems to work quite well most of the time. If your software allows it, you could display the fully connected maze and them tweak it by hand, adding and removing walls to make it more interesting.

Make sure you save any mazes that you generate so that you can make changes to the searching and solving code to try out again on the same maze.

Printing Mazes

While the size of the maze makes it particularly convenient for storage and manipulation inside the controller, it is not the most friendly thing for people to work with.

If you want to print a copy of a maze to fill in by hand (hey - it passes time :) or if you want to post a maze to a newsgroup or send it to a friend, then you will need to convert it to printable characters.

There are several schools of though on the best printed representation. If you don't like mine then you are free to pick an alternative.

Using a single character for a post and another character for a wall will get the job done but it doesn't look too good as the characters have different heights and widths. You must use a fixed pitch font or there is no guarantee that the characters will all turn out the same width anyway. My preference is to use two characters for the NORTH/SOUTH walls and just one for the EAST/WEST walls.

A typical maze might look like this:

   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
F0 |                                               |
   +  +--+--+--+--+--+--+--+--+--+--+--+  +--+  +--+
E0 |     |                          |              |
   +  +  +  +--+--+--+--+--+--+--+  +--+--+--+  +  +
D0 |  |  |                                   |  |  |
   +  +  +  +--+--+--+--+--+--+--+--+--+--+  +  +  +
CO |  |  |     |  |                       |  |  |  |
   +  +  +  +  +  +  +--+--+--+--+--+  +  +  +  +  +
B0 |  |  |  |  |  |  |              |  |  |  |     |
   +  +  +  +  +  +  +  +  +--+--+  +  +  +  +  +  +
A0 |     |        |  |  |                 |     |  |
   +  +--+  +  +  +  +  +  +--+--+  +--+--+  +--+  +
90 |  |  |  |  |  |  |  |           |        |  |  |
   +  +  +  +  +  +  +  +--+--+  +  +  +--+--+  +  +
80 |  |  |  |  |  |  |  |     |  |  |     |  |  |  |
   +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +
70 |  |  |           |  |     |     |  |     |  |  |
   +  +  +  +--+--+--+  +--+  +--+--+  +  +  +  +--+
60 |  |  |  |        |              |  |  |     |  |
   +  +  +--+  +--+  +  +--+--+--+  +  +  +--+  +  +
50 |  |  |  |  |     |              |        |     |
   +  +  +  +  +  +  +--+  +--+  +--+--+--+  +  +  +
40 |  |     |     |  |           |              |  |
   +  +  +  +  +--+  +--+--+  +--+  +--+--+--+--+  +
30 |     |     |     |        |                 |  |
   +--+--+--+--+  +--+--+  +--+--+--+--+--+  +--+  +
20 |                 |                 |           |
   +  +--+--+  +--+  +--+--+  +--+--+  +--+--+  +  +
10 |  |                    |                    |  |
   +  +  +--+--+--+--+--+  +  +--+--+--+--+--+--+  +
00 |  |                    |                       |
   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

The code needed to create this view of the maze is not too complicated. All you have to do is run through the maze from top to bottom, row by row. Each row is used to generate two strings -one for the north walls and posts, the other for the west walls. At the end of the row, add on the last post and wall to each string. Output the two strings and move on to the next row. You will need to add the southern most wall as a special case at the end.

Reading a text maze is not too hard either. It is worth taking the trouble to handle common formats. The very first character will be the one used for posts, the next character will be the one used for N/S walls. The character after that will tell you if one or two characters are used per cell. The first character of the next line tells you what is being used for the W/E walls. After that, treat the file as pairs of lines. Examine each one at predetermined positioned to check for the presence/absence of walls.

Calculations

What do you need to calculate? Well, there is the velocity/position thing for a start.

If you are using DC motors, you may well feel the need to create clever control loops to govern the velocity and position of the wheels. Your goal is to put the wheels into a known position. The constraints include the available acceleration and the desired velocity or acceleration profile.

Simple motion in a straight line requires that you accelerate the wheels as hard as you dare. Both wheels will need the same acceleration if the mouse is to go straight. Controlled deceleration will be needed toword the end of the run to ensure that we come gently to a rest in the desired position without over or undershooting the target.

Rotation about the centre of the mouse is a similar operation except that the accelerations will be different and one of the motors will be driving backwards. The accelerations will be different because the rotational inertia of the mouse will have a more pronounced effect when spinning on the spot compared to straight line motion.

A common technique for creating this kind of control is to create a PID controller system. PID stands for Proportional, Integral, Derivative. All that means is that we want to know how far we are away from the goal (integral), how fast we are moving (proportional) and how much acceleration we are using (derivative). These control systems are common and can be quite simple to write. They need tuning for the actual device they are used in. References and descriptions are widely available.

Input and Output

Your processor must be able to talk to the outside world. In particular, you will need to be able to control the motors, listen to any odometry sensors, drive the sensor emitters and read the sensor results.

When you choose your processor, you might be constrained by the amount of I/O that your micromouse needs. If, however, you are dead set on using a particular controller, you might have to exercise a bit of care in getting enough functionality out of the available pins.

There are a number of tricks for saving precious I/O pins. you can multiplex functions to pins. For example, the same pins can be used for reading a keyboard and driving an LCD display. Some other ideas are shown below.

Motors
For convenience, you might want three or four bits to control the motors. For analogue motors, each will need a bit for direction and each will probably need at least one bit for power. More sophisticated designs might use an entire byte to specify speed and direction for each wheel - perhaps using a (weighted) 2's complement value. With latches for the driver circuits, you could use the same port for two such channels.

Steppers can be driven with four bits. One for each motor for direction and one each for stepping direction. Alternatively you could use four bits each to generate the phase drive signals directly from the processor. Since stepper drivers wth all the clever bits are not more expensive or complicated to use than direct drive, I don't think there is much to be gained here.

With either drive option, it is probably a good idea to be able to isolate the motors from the battery. Not only will this save a lot of power in stepper designs, it could stop all that smoke from escaping after a crash. You really should put a fuse in the power line to the motor by the way. Resettable polyswitches are just fine.

Overall, reckon on at least four bits and possibly eight or sixteen if you are keen. Five is, perhaps, best.

Odometry
With DC motors, you will need some kind of counter or counters to see how far you have gone. Tricycle mice can get away with just one on the steering wheel if they don't want to have closed loop control for the motor speeds.. Wheelchair mice need one on each that can do both odometry and closed-loop speed control. Those clever four-wheel mice tend to need lots of sensors - perhaps six for many designs.

Counters are best if they are directional and that will need two lines per counter. Ideally, your mouse will have built-in counters and you canconcentrate on signal conditioning with the sensor lines going straight to the counter inputs. Without that, you will have to poll the sensors. This can be time-consuming as you will have to check the encoder often enough to be sure of not missing a count. Yet another task for an interrupt service routine.

If you want to show off with multi-proccessor mice, how about using a PIC (or whatever) to look after odometry. It could present the controller with a distance travelled as a serial or parallel loaded value on demand.

Steering
Tricycle mice and those four-wheel micromouse designs need some way to know where the wheels are pointing. Encoders can work here but they represent yet more time-critical work for the processor. If you have analogue sensors, you can use a feedback pot and build a software controlled servo loop for the steering. Among other odd advantages, you could create software controlled Ackerman steering geometry. If you wanted.

Wall sensors
The emitters for you IR sensors will need to be flashed on and off. Leaving them on permanently will drain the battery and deprive you of the benefits of AC coupled sensors.

If you have look-down arrays, join them in banks. Eight emitters can be driven using a single pin and a couple of transistors or part of a driver chip. Bear in mind that LEDs may have a forward voltage drop of 1.2 to 2.2 volts so you will need a high supply voltage to drive many in series. They may also need a considerable current for reliable reflective detection.

The receivers can all be connected in parallel to a single port so eight pins will probably be plenty. Parallel-in-serial-out shift registers can be used where there are a lot of sensors and not many input pins. there are lots of ways to arrange this. Sixty four inputs can be read in eight operations using an eight pin input port and a single output pin to clock the registers. AC coupling the pins means the results are very time sensitive. You might use latches or careful interleaving of sensor banks.

Analogue wall distance sensors pretty well demand analogue inputs but you could achieve a similar result with an analogue comparator. You could build an A/D convertor in hardware or software. Analogue results can be obtained by timimg the length of a pulse - simple enough but time critical so watch what your interrupt service routines are doing.

Summary
There are plenty of pins on just about any processor if you are careful enough. However, you might want to pick a processor with all the necessary I/O on board and save a lot of design effort. Your choice.

Memory

OK - so it is a poor title for the page...

Your controller will need memory to store, probably, three things:

• Some kind of monitor to communicate with a host computer for downloading new software.
• The actual micromouse code itself
• Working information such as variables and maps of the maze.

Depending upon your controller design, you might do without a monitor program. If you keep all code in an EPROM, you can burn in revisions, plug them into the controller board and off you go. The advantage of this approach is that EPROM is non-volatile. If you lose the power, the code stays put. It would be embarrassing to accidentaly kill the power to your mouse as you approach the maze and have to run back for a reload. Another plus is the relatively limited battery power you may have available. With you code in EPROM, you can ust leave your mouse switched off until it is ready to go. Similarly, a battery change is no big deal, the code will still be there when you have finished.The disadvantage is that EPROMs need programmers and these can be expensive. Erasing EPROMs also requires a special eraser and this can take some time. If you have all these things (programmer, eraser and time) then you may well want to go for this option.

Monitors often come with ready-made controller boards or are available for simple reference designs for a number of controllers. The monitor software will probably live in an EPROM which you may not even have to program. Your code will then live in RAM. Remember that this is likly to be volatile - lose the power and your code goes with it. You can buy or make non-volatile RAM devices to overcome this problem. The advantage in terms of development is that the monitor comes with a number of handy routines. These may include facilities to communicate with a host while the program is running and to download new versions of your software. The communications features can be particularly useful during development as your program could send a stream of diagnostic data back to a PC so that you can see what is going on. Software changes can be very rapid - a new version of your code may take a second or two to download to the controller. This is ideal if you want to fine-tune some parameters on the day.

Variable storage will be in RAM. Don't skimp on this. Not only is RAM cheap, you may actually find it hard to get hold of small RAM devices. Without a good search, however, you are unlikely to find many microcontrollers with enough on-chip memory to satisfy the needs of your mouse. While you can store a maze in about 64 bytes (how is left as an exercise for the reader :), there will be a considerable overhead in terms of the code needed to process that. Leave aside for a moment the general variables that you need such as location, speed, heading and so on, what about the maze?

The simplest approach would be to store the maze in a 256 byte block of memory with each byte representing a single cell. One such memory block could store all the data about the presence of walls along with other flags such as whether or not that cell had been visited before. Single bits are enough for these items and are easily enough to encode.

Another such block could be used to calculate the routes to the goal for algorithms like the flood-fill. This block should be regarded as temporary so that it can be re-used frequently to optimise the route. Yet another block might be used along with it to calculate or store the best (not necessarily the shortest) route for the speed run. A memory block may be set aside to store hints for the searching algorithm to try and ensure an effective search of the maze.

If you decide to do a more classic tree search, you may well find that you need a large stack - especially if you write a recursive maze searcher. Other methods of finding the goal may require a stack or queue while they run.

IOn a typical microprocessor, 32k EPROM and 32k RAM requires two memory devices and probably an address latch. For relatively little circuit complexity (apart from all those wires if you are wiring by hand) you get plenty of memory to do with as you please.

Naturally, the hairy chested types (of either gender) who fancy a go at a vision guided mouse may have other problems - good luck to them.

Processor

Which processor should you use? In many ways it is not too critical but not all processors are well suited to driving a mouse. In particular, the small, cheap, easy to use PICs are not your best choice. They can certainly do the job but they will need that bit of extra cunning to build a maze solving mouse with adequate performance. Their main constraint is memory. There is plenty of program space but life is made much easier if there is at least 1k of RAMto store the map, routing table and other data. In fact, you can do this in rather less memory. 64 bytes is sufficient to store the map if you want as you only need to keep track of less than 512 walls. However, the penalty for this is the overhead needed to decode the data into a more usable form as you run around the maze.

Few processors and microcontrollers have this much memory on the chip and so you will probably need to add external RAM. Since these are usually a minimum of several kilobytes these days, there is little point in skimping on RAM. You will save very little on board space, wiring or cost so just go for whatever is convenient.

Your choice of sensors may have an impact on your processor - or vice versa. Analogue sensors will need some form of analogue to digital conversion. While this is readily available as a separate device, it would be much more convenient if A to D were a function on the microcontroller. Digital sensors, such as the common top-down type, are readily interfaced to most microcontrollers.

At least one timer will be useful. You can do all your calculations and timings in software with cunningly designed delay loops and subroutines. Many of these things become much easier if there is a timer running that can give easy delays and/or regular interrupts for your main control functions. Typical timing functions might include periodinc calculations for the PID algorithm controlling DC motors or the tight timing requirements of high-speed stepper motors.

Many processors have several independant timers available, others require a more complex setting of just one or two timers. An attractive feature is some kind of programmable counter or timer array that can perform bit orientated operations on output pins with no processor intervention.

Counters might be needed to keep track of wheel sensors. Again, you can manage without by making use of interrupts or by polling the pins in software loops. Hardware counters are much more convenient. Sometimes you will find that timers can be used as counters. often these functions are mutually exclusive.

Speed

So, the question again is - how fast is fast enough?

To an extent, the answer depends upon your skills and ambitions as a programmer. With stepper motors, simple sensors, integer arithmetic and an uncomplicated maze solver, competitive mice have been build with simple eight-bit microprocessors such as the Z80 or 6502 running at a couple of MegaHertz.

Let's assume you are tearing along at 3m/s down a straight. You have an interrupt generated every millisecond which corresponds to 3mm of travel. In that time, even on an ancient Z80, you could execute 1000 instructions. Now that is a lot of computation for the relatively simple tasks that are likely to have to be carried out in a simple mouse.

On the other hand, say you are using DC motors, analogue wall sensors and a cunning PID control loop to keep you going in the right direction. Now you have to do some real sums during each cycle. Avoid dividing because it is no fun and keep to integer arithmetic. How fast can you perform a 16bit signed multiply and how many do you need?

Of course, in days of old, programmers knew all sorts of tricks for getting the maximum performance from sluggish processors. These days (aaah the youth of today...) you are probably going to rely on a processor with a good set of arithmetic instructions, a 16 bit architecture and oodles of bus speed. For example, I am using the intel 80C196KC which has adequate amounts af all of these.

In general, you can get the job done with some rough old eight bit device and a bit of cunning, or you can go for a sexy fast processor and a bit of programmatic idleness.

While there aren't many out there, there is some scope for multiprocessor micromouse designs. Perheaps a maze solving processor talking to a motion control processor and a sensor processor. Divide and conquer is perfectly feasible with easily programmable and cheap devices like the IC and AVR processors.

Diagonals

Diagonal runs are a great way to save time - and crash.

If you want to run down the diagonals of a maze, you must be skinny. The equivalent width of the passage running along a diagonal is only about 114mm. Clearly, you had better be thinner than this. The closer you are to this width, the more accurately you must position yourself. Equally, you don't want to be too narrow or there may be stability problems on high speed curves. There is more on this in the section on smooth turns. Skinny also means that steering is more sensitive.

Sensors will have to work extra hard during diagonal runs. You no longer have those nice perpendicular reflecting surfaces if you use side-looking sensors. The sensing points are in different places that they were on straight runs. The variation on wall distance is greater and the optimum sensing points are asymmetric so you don't get simultaneous left and right information.

All in all diagonal running is a lot more complex. So what can you gain?

Consider a series of steps in a maze. A left-right pair might require two smooth turns at, say 140mm each at a maximum of 0.7m/s and will take 0.4 seconds. The same pair on the diagonal, without the entry and exit quarter turns, takes a ground track of 250mm or so. Not much of a distance saving but you may be able to cover this at a speed of, say 1m/s, in only 0.25 seconds. Now that is a saving worth having. In a maze designed to reward diagonal runners you might shave as much as 30% of your running time through these sections.

As with smooth turns, you will need to do some sums and plenty of experiments. There are three kinds of turn associated with diagonal runs, each with an entry and exit phase. You will need velocity/position profiles for each of these.

Smooth Turns

Elsewhere , we have looked at how fast you can go around a turn. For the purposes of this section, assume that your best possible speed is 0.75m/s. Now that is the average speed of the mouse. The outer wheel must be going faster than the inner wheel. However, when we approach the turn, both wheels are going the same speed. You can't instantaneously change the wheel speeds so, if you approach the turn already doing your maximum turn speed, the outer wheel will need to speed up and the inner wheel will need to slow down. During this period, the mouse will not be describing a constant radius turn. Rather, the turn radius will get smaller, down to some minimum and then get larger until we are going straight again. If you can complete a turn entirely within a cell, then it will be a relatively simple matter to perform any combination of turns.

Calculating the velocity of the wheels during the turn is a bit tricky. In fact, so far, I have not been able to do it.

I do know that it is a goal worth chasing. Best case for a 90 degree smooth turn is about 0.18 seconds.

To stop and turn in place will take much longer.

Assume you have a best acceleration (and thus deceleration) of 0.7g, say 6.8m/s/s. You need to be stationary at the centre of the cell where you are going to turn. You can enter the cell at a higher speed of 1.1m/s and come to a halt in 0.163 seconds. Ignore the rotational inertia of the mouse for a moment and limit ourselves only by friction. Given a wheel track of 9cm, a quarter turn in place at maximum acceleration (6.8m/s/s) would take 0.2 seconds. You then need another 0.163 seconds to get to the edge of the cell, again doing about 1.1m/s.

OK, so you can enter the cell faster and leave it going faster. The entire operation took 0.526 seconds - nearly three times as long as the smooth turn. In a maze with a lot of turns (there will be), the overall effect will be disastrous. No competitive mice turn in place on a speed run.

Steering

Well, how are you going to get around corners? Perhaps the simplest solution, used by many mice, is a wheelchair drive where a pair of wheels are driven independently on either side of the mouse. Turn one of them faster than the other and your mouse will execute a turn. Turns of any radius are possible and the mouse will be able to turn about its own centre. Bear in mind that the part of the mouse that lives in the maze below wall height (5cm) had best not hit the walls when you spin on the spot.

NOTE - about trikes. Sharp turns need inside wheel going backwards. two motors at rear can sort this out.

Tricycle mice have a single steering wheel which may or may not also be the driving wheel. If the steering wheel is not also driving then you will need some kind of differential on the driven wheels if you are to prevent them from skidding on turns. With a non-driven steering wheel, you are limited in terms of the minimum turning circle. Clearly, it will not be possible to turn the steering wheel through 90 degrees and then start the driving wheels. Turns will have to be entered gently. With a driven steering wheel, turns can be as small as your mouse footprint. It is probably better not to try and drive backwards with a tricycle mouse as the steering problem is much harder even though the turning circles are smaller. Another problem you will face with the tricycle is the speed at which you can turn the steering wheel. If you are tempted to use a standard RC servo, remember that these are not that fast. Even a quick servo will take about 100ms to turn through 60 degrees. In a competitive mouse, an entire right angle turn will need to be complete in under 250ms. I am not sure it will be possible with RC servos. You could make your own steering servo. Steal the potentiometer, motor and control board from a servo and make a new gearbox with a more suitable gear ratio. There are likely to be problems because the control circuits is probably optimised for the dynamics of the servo as made. You may have settling, overshoot or even oscillation problems to fix. In either case, where are you going to get data about distance travelled in a tricycle mouse. A couple of tricycle mice exist and run very successfully.

There are a number of four (and more) wheel mice about. These are mechanically complex and require small (expensive) components and good engineering skills. Why bother? To be honest I am not sure but here are some thoughts. With a wheel at each corner, steering has both wheels on the same side electronically or mechanically coupled. Turn the wheels so that their axles all pass through an imaginary radius drawn through the centre of a single circle and you have excellent, smooth cornering. Both inside wheels travel at the same speed as do both outside wheels. Odometry is a relatively simple problem. Put encoders an all wheels and you can use ABS and traction control to get the highest performance from you motors. Reduce the mechanical complexity a little by putting a pair of driving wheels in the middle for a six-wheel mouse. I expect the driving wheels would need to be independently mounted so that you can get sufficient traction without lifting any other wheels off the ground on bumpy circuits. Just using the front wheels to steer is surprisingly tricky. For that you need to create or emulate Ackerman steering. The inner wheel needs to point in a slightly different direction to the outer wheel. When turning, the rear wheels describe a slightly different arc so you can't cut your corners too close. Reversing is a nightmare. For the same reason, steering with the rear wheels is no fun either. If you have access to the components and appropriate skills, I expect a well-built four or six wheeled mouse could be very competitive.

Straights

Navigation down a straight run may appear simple enough but has many pitfalls for the unwary.

Consider first that left to itself, it is actually quite unlikely that you mouse will be able to travel in a perfectly straight line anyway. If you use stepper motors, can you be sure that the tyres are exactly the same diameter? With DC motors are you sure you have all the motor control loops properly set up?

OK, so you can do all that and you have a mouse that does not drift off course in free space. What if it hits some dust on the maze or a wheel skids or hits a bump. What will that do to the path of your mouse? Don't be surprised to see competitors cleaning wheels and sweeping mazes before their run.

Sooner or later you will need to correct the position of the mouse. There are three basic positional errors to worry about:

	Forward Error is where your mouse is too close to or too far from the wall ahead. The mouse in the picture may think it is in the middle of the cell but is too far back. This should be easy enough to correct. Assuming you are sensing the posts for positional information, you are likely to get a transition before too long and can use that and your current position to recalibrate. Remember that there is nothing absolute about this kind of update. Each post may cause a sensor transition at a different time because of things like its reflectivity, the direction and intensity of the ambient light or because of a coincident heading or offset error. To guard against this you can look for leading and trailing edges where those are available - such as at a post with no walls. Large forward errors might mean that you start looking for posts too soon or too late so allow a goodly margin here. The only absolute available is encountering a wall ahead of you (or behind if you can do that). An accurate but time consuming method of calibration is to have a microswitch or short range IR sensor mounted at the forward (or rear) edge and drive carefully up to the wall. Then you will have a pretty good idea of your forward error and can do something about it. Watch out for accumulating forward errors. These may be caused, for example, by rounding errors in DC motor control loops. Worst case, a forward error of about 2cm over a 15 cell straight represents an error of 0.7% and may be enough to cause a crash when you turn. Even if it does not cause a crash, you will be left with an offset error of 2cm after a 90 degree turn. A half-stepped stepper motor might have an error of, say plus or minus 1 step representing an forward error of about 0.4mm. Accumulate this error over 15 cells and you will be less than 6mm out at the end of the run. This should be correctable. Really though, a forward error that requires major correction is simply a sign that something is badly wrong. But you knew that already didn't you.
	Offset Error is a question of being too far to the left or right as you pass through a cell. You will get offset errors after a turn if there was a forward error before the turn. A heading error may temporarily cause an offset error while it is being corrected. When you correct an offset error you must automatically create a heading error to do so. Bear in mind your sensor resolution. Accuracy beyond that is somewhat pointless. However, say you change your sensor scheme and get more resolution? How much reprogramming do you want to do?

Heading Error amounts to pointing at the walls rather than down the middle of the cell. Left uncorrected it will almost certainly cause a crash. After a turn it will still be there. If it was caused by sloppy turning, it will probably be worse. Correction means slowing down one wheel. In general, don't assume you can correct by speeding up a wheel as they may already be at full speed. If you are going so slowly that you cannot slow down a wheel, you are not moving. In this case a partial turn in-place is called for. The degree of correction depends upon things like how fast you are going, where you are in the cell, how bad the error is and how far in front of you the sensors are. You can write down transfer functions to describe all this and calculate a correction. Alternatively, you could try some experiments and make a small table of corrective actions to get you out of foreseeable problems. This will be a computationally cheaper but less flexible solution.

Naturally, these errors can occur in combinations although that will only normally happen when it is most inconvenient for your software.. If the mouse is stationary, it can align itself with a series of turn and shuffle moves. Drive systems with DC motors will soon show up any backlash in the gear trains when you try this. Stepper driven mice should be able to position themselves to within a millimetre.

Heading and offset errors can be corrected continuously only as long as your mouse has reliable adjacent walls. Since there may be sections of the maze where there are no such walls, it would be foolish to rely too much on them. What you can rely on is the presence of the posts. The rules stipulate that there must be a post at each wall intersection. Use these to measure you errors and you will always have some data to work on.

Turns

The simplest type of turn your mouse can make is an in-place turn where both wheels rotate in opposite directions. Once you have your motors calibrated you can peform accurate in-place turns through 90 or 180 degrees. The 180 degree turns are, of course, needed to get out of dead ends. Reversing direction like this should only be needed during searching and can be eliminated with some cunning if your mouse is bidirectional.

A turn in-place will want velocity profiles for each wheel. The rotational inertia of the mouse will now become important to you. Keep as much mass as possible near the centre of the mouse and keep the mass as small as you can. Wall sensors on booms can contribute surprisingly large amounts to the moment of inertia due to the distance-squared term in the equations.

A wide track helps to get good accuracy in the turns. Narrow tires will help give better repeatability.

You might want to consider turning about one wheel. Since the single whhel that does turn has to travel twice as far, there is probably little to be gained in terms of speed. Also, the inertia problems will be worse for this type of turn than for an in-place turn.

Positional accuracy is, as ever, important. If you begin a turn with a heading error, you will finish it with the same heading error. However, start with an offset error and you turn it into a forward error ande vice versa. The forward error may be the hardest to detect as it may be several cells before you get a good reference point to recalibrate from.