AISB Quarterly issue 39 Dec.1980
ON MICROMICE AND THE FIRST EUROPEAN MICROMOUSE COMPETITION
Wayne H. Caplinger, Department of Artificial Intelligence, Edinburgh University, Edinburgh EH8 9NW, U.K.
A micromouse is a mobile robot containing its own sensors, power source, logic and steering, designed to negotiate a rectangular maze of corridors 16.5 centimeters wide. The first micromouse contests were held in the U.S. during 1978 as preliminaries for the first finals, in 1979. The maze used was 13 by 13 units, with an entrance and an exit. It is shown in . This sort of maze can be solved by a "wall hugger." That is, by staying in contact with say the left wall while moving forward, one will always come out the first exit [13,19] . Although early mouse designs were ambitious and clever, the unexpected difficulties of implementing intelligence in hardware of this size caused the winning entries to be wallhuggers.
The first European contests were a Portsmouth preliminary on 1st July 1980, and the London finals on 17th September at EuroMicro 80. The European mazes were 16 by 16 units, and had a centre goal. In each it is possible to navigate around the centre back to the starting point. This moat prevents a wall-hugger from reaching the goal. The Portsmouth maze is given in , and the London practice maze is shown here.
At the London finals there were to be four catagories: best first run, best learning, cat-hunt, and virtuoso. In first run, a mouse enters a previously unknown maze, and is timed to the goal. The learning catagory allows ten minutes of maze exploration before the timed run. A cat hunt occurs in a maze with the walls removed, but corner pegs remaining. The mouse is to topple ten egg-like "cats", without moving any from its square. This event was cancelled, having only one entrant. For virtuoso display the mouse may do anything in a free-world environment, being judged on originality and entertainment value. Nine mice arrived for the finals. Each was entitled to spend thirty minutes in the maze: ten on first run, ten learning, and ten timed after learning. In the potential four and a half hours, only once did a mouse reach the centre, and this only after some human handling. Upon arrival, one contestant said that given a week they would be ready. By the contest evening two days later, the estimate had become three weeks.
In the table of scores, the order of running is given for each event with the time-in-maze and the judges' penalty times for handling. Where a mouse was unable to make its timed run after learning, the time during learning is given with an "L". A "*" marks the one successful run.
- First Run - Mouse Order Time Penalty Amcomical 8 1:30 ---- Brainy Bricks 2 10:00 1:30 Fred 1 4:40 :30 LAMI 3 3:30 ---- Meryl 4 1:45 4:00 Midnight Sun 5 1:29 2:00 Pascal 5 2:07 1:00 Stirling Mouse 7 3:49 * 2:00 Yamabiko - ---- ---- - Learning - Mouse Order Time Penalty Amcomical 2 4:11 L 7:00 Brainy Bricks 1 3:42 7:30 Fred 3 5:00 7:00 LAMI 4 3:49 L ---- Meryl 5 1:28 L ---- Midnight Sun 6 0:15 L 6:00 Pascal - ---- ---- Stirling Mouse 7 2:50 6:00 Yamabiko - ---- ----
Each mouse is described here individually to illustrate design principles, problems and terminology. Although the comments are sometimes critical, the amount of time and skill that went into these mice should not be underestimated.
AMCOMICAL used a single stepping motor and two steerable front wheels. The forward-mounted ultrasonic sensor had cancellation problems, and so was only able to detect local walls, rather than measure the length of the corridor. At each corner was a row of four LED pairs, perpendicular to the line of motion, for both detecting side walls and steering corrections. An LED (Light Emitting Diode) pair consists of an emitter shining down at a 45 degree angle, and a perpendicular detector so that if a wall is present the reflection of the infra-red light is seen. A consequence of the drive configuration was that it could not turn around in a dead end. Further, while reversing out, it could not steer around corners, needing to do a three-point "star turn". In a star turn, a vehicle goes as far around a corner as possible, then changes direction and steering, going back until near contact, and finally onward out of the turn. This is a "three-point" star; five-points may be required by some drive configurations. The design team, from ICL Amcom, came with an amazing array of hardware. They would wire the mouse into a test apparatus for simulating algorithms and testing sensors. During the three days of practice, there was always at least one team erasing or burning an EPROM.
BRAINY BRICKS, built by Phil Yeardley and Pete Gissig of Sheffield, resembled an office block built of Lego. Since distance travelled was computed from output commands rather than measured, distance errors could accumulate on a long corridor. One centimeter error is enough to strike a wall on a corner, and this then causes further directional and distance errors. Like several other mice, it would travel some distance down previously seen corridors, and then reverse direction and return. During its first run it actually returned to the start. Whenever it angled into the wall of a corridor, it would reverse away. LED position detectors were used, but the presence of walls was tested by wire feelers on microswitches. These feelers would occasionally get caught on the joins between walls or masking tape maze repairs.
FRED  was a grey furry mouse with glowing eyes. It used horizontal mounted LEDs on all four sides, and moved very fast. This gave it humorous anthropomorphic behavior, as it sped down a straight, turned, and convinced of the absence of a wall, repeatedly bashed it until wheel slip had turned it away from the wall. During development, it was discovered that the rate of deceleration caused the wheels to skid. The distance of skid was measured, and the algorithm modified to compensate. However, when the friction coefficient was different on the official maze floor, they could not re-compensate. A better strategy would have been to check position after skidding. LEDs always have a problem of receiving signal from camera flashes and maze illumination. However, there were also fundamental design difficulties. First, environment testing was not nearly frequent enough to compensate for the unreliable sensors. Second, the side sensors were mounted on the axis of rotation, thus it could measure distance from a wall, but had no information about the relative angle .
LAMI was a high precision, innovative entry from the Laboratoire de Microinformatique, Swiss Federal Institute of Technology of Lausanne. Rather than turning, it could move its square symetrical body equally well in all four directions, due to a special wheel design by Jacques Virchaux. There is a wheel in the centre of each side, parallel to that side. Each wheel has 16 tiny wheels spaced around its perimeter, each axis tangential to the rim. The large wheels are powered, while the tiny wheels rotate freely. To move forward, the two side wheels propel, while the tiny wheels on the front and back are turned by the floor. To adjust sideways in the passage, the front and back large wheels are turned slightly. The sensors were five LEDs on each corner, set up to find walls and correct position whether moving forward or sideways. It would move rapidly to the centre of a square, and then oscillate a bit to check its readings before dashing to the next square. The team claimed that it could explore a 16 by 16 maze in about fifteen minutes, and then would run the shortest path in thirty seconds. The usual starting sequence was that the "mouse trainer" aligned the mouse, and then counted down from five, so that the timing official could synchronize the clock. When LAMI was about to start, the official thought there was a language problem, and so repeated the instructions. The trainer, standing several feet from the mouse, then counted down, and the mouse started without being touched. The audience liked that! It turned out that a ten second initialization period was a side effect of the software. The problem with precision-built LAMI was that it was built for equally precise mazes. On the first run it moved twenty squares, and then became confused on a taped floor seam. On its second, it touched a side wall and in the trainer's words: "lost synchronization".
MERYL, like several others, had a wheelchair configuration, where power and steering are both provided by two wheels at the centre of the sides. Casters at front and back maintain balance. At each of Meryl's corners was a row of four LED pairs. Directional control consisted of trying to keep the centre two above the wall, and the others outboard. It is not clear why the directional system failed during contest conditions.
MIDNIGHT SUN was the product of the Electronics Laboratory of Tampere University of Technology, Finland, and was the largest and heaviest mouse, cantilevered over the square in front. The LEDs that test whether a wall exists were well designed. A pole holds the emitter beyond the wall, and points it diagonally down through the wall location. There are two detectors on the mouse base, one to see if the light path has been broken, and the other to measure background light. This mouse failed four re-starts, probably because the other LEDs, used for steering, were mounted co-linearly with the wheels. When this or any other mouse would get in trouble, a handler would pick it up and turn it in the right direction. This would permanently confuse the mouse, since every maze feature had magically changed.
PASCAL MOUSE ENGINE  was another novel design, created in a month for only $50 of parts. The chassis was from a child's toy car. One rear wheel was driven, while the othermeasured distance travelled. Pascal was longer than a maze square, and so had to reverse out of dead ends and do star turns at corners. Sensing was done by a sonar pair mounted on a front pivot so that it could be pointed forward or to either side. Two problems occur with sonar. If the wall is close, the signal from the emmiter has not finished when the echo arrives, producing interference through the frame. IE the wall is further away, there are so many bounce paths on floor and walls that the echo is too muddy. Pascal solved the first by feeding an inverse emmiter signal to the detector. The second was solved in software, and allowed the mouse to measure the distance to a far wall. Unfortunately, the result was not particularly accurate, and failed beyond about 1.6 meters. The mouse was programed in the high-level language Pascal, and like the others, only remembered the maze junctions rather than the walls and corridors. It had fallen off a table just before the contest, and retired after touching the corner in a turn.
STIRLING MOUSE, built in Stirling, Scotland, was the most primitive and the most successful. A nose switch detects walls in front, while a brass wing on each side provides directional stability and detects side walls. These wings ride on top of the walls, and by the height of the wing, distinguish three conditions: no wall, wall in place, too close to wall. However, when passing through a junction there is only one wall and no way to prevent it from straying off that wall. Sterling Mouse also had no way to recover if it scraped into a wall. It was centre-seeking, as appropriate to this style of maze. However, the mouse sometimes spiralled outward, retraced its path, and showed apparently erratic behavior. Simulations of several centre-seeking algorithms have shown similar problems. Since orientation at a junction is independent of global path orientation, this is to be expected. A good fix may be to incorporate knowledge about moats.
YAMABIKO 4 arrived from the University of Tsukuba, Japan without completed software. There was front and back sonar so that it could move equally well forward and backward, saving time at dead ends. It was wheelchair mount, but unlike most wheelchairs which turn by going to the centre and rotating, this mouse slowed the inside wheel while accelerating the outside. This is smoother and accumulates significant time savings. A previous, non-maze robot is described in .
There were four virtuoso entrants. Amcomical entered a seperate mouse that used sonar to recognise a large cloth mouse. Pascal had a more sophisticated trick of preferring a large cheese to a small cat. Unfortunately both failed due to sonic clutter. In the finals were Fred, which sung two songs off key, dancing to the first, and Midnight sun, which wrote its name and a picture and then sang rather better. Both slipped quite a bit on the performing surface, and shy Fred made repeated dashes off stage. The result, determined by audience vote was a tie.
This contest has shown that micromice may be a good testing arena for AI techniques. Research can be done on maze search heuristics, reliable sensors, optimal sensor configurations, and control problems associated with accurate positioning and straight-line travel. However, it is necessary to have a strong technical team to electrically isolate the drive motors from the logic, provide power supply, and solve many similar problems.
The next European finals will be held in Paris at Euromicro '81, 7-10 September. National preliminaries are being scheduled. The rules  have already been released, and are obtainable from: Micromouse contest, Euromicro, 18 rue Planchat, 75020 Paris, France. The same maze and mouse dimensions will be used, but there is some refinement of the contest structure. Each mouse will be allowed a single 15 minute period. Whenever it reaches the centre the run time will be noted, and it may be restarted. Thus a mouse may be learning on each run. For less intelligent mice, trying different paths will reduce the luck element. It is unclear whether a distinction will be made between first-run times and the others. This distinction would acknowledge that there is skill involved in the heuristics of path choice in a novel maze. There will also be a virtuoso display, but no cat-hunt.
Maze and Micromouse Bibliography
Essential background to studying or designing micromice are articles , , ,  and  or . [1) discusses three mice: Moonlight Special, Microbet and Charlotte after the three U.S. preliminary contests. [21 reports on the first U.S. finals, discussing Moonlight Express, Dudley, Mushka, Cattywumpus, Harvey Wallbanger, and Moonlight Flash. Popular electronic and computing magazines occasionally produce applicable hardware articles, such as [16) and , and individual mouse projects sometimes release their internal papers ,  and  .
The first use of the term "micromouse" was in the announcement of the first contest . The rules of the competitions are in  for 1983 and  for 1981.  is a whimsical press release on the Portsmouth preliminary, while  provides important insights on the failures of the mice in that event. Dr. Bi11ingsley's papers should be available from the Euromicro office, or from the author at Dept. of Electrical & Electronic Engineering, Portsmouth Polytechnic, Anglesey Road, Portsmouth P01 3DJ, England.
Basic maze theory is presented in , , , and . The remaining articles are of specialist or historical interest,
1. Allan, Roger "Three Amazinq Micromice: hitherto undisclosed details. A closer look at some of the 'smart' electonic micromice that have participated in the Spectrum/Computer Amazing Micro-Mouse Maze Contest.", IEEE Spectrum Vol. 15:11 November 1978
2. Allan, Roger "The Amazing Micromice: See how they Won. Probing the innards of the smartest and fastest entries in the Amazing Micro-Mouse Contest.", IEEE Spectrum Vol.16:9 September 1979 pp62-65.
3. Billingsley, John "Micromice on Trial", 6 pages unpublished.
4. Billingsley, John "The best laid plans of mice and men gang aft agley", 3 pages July 1980, unpublished.
5. Billingsley, John "Micromouse Maze Contest Euromicro '81", 3 pages October 1980, unpublished.
6. Billingsley, John "Amazing Revelations - More about the Micromouse Maze Contest", 4 pages unpublished.
7. Buchland, M. & Caplan, I "Project F.R.E.D.", Plessey internal document, Ilford, Essex, England 6 pages and 5 color plates.
8. Christiansen, Donald "Announcing the Amazing Micro-Mouse Contest", IEEE Spectrum Vol.14:5 May 1977 page 27.
9. Deutsch, J.A. "A Machine with Insight", Quarterly Journal of Experimental Psychology Vol.6 part I pp 6-11.
10. Deutsch, J.A. "The Insightful Learning Machine", Discovery 16:12 1955 pp 514-517.
11. Dudeney, H.E. "Mazes and how to Tread Them", Amusements in Mathematics Dover 1959.
12. von Eier, R. & Zemanek, H. "Automatische Orientierung im Labyrinth. Automatic path-finding in the maze", Sonderdruck aus 'Electonische Rechenanlagen' Heft 1 (1960), Seite 23-31. Verlag und Druch: Oldenbourg, Munchen. (in German)
13. Gardner, Martin "Mazes", Chapter 10 of More Mathematical Puzzles and Diversions 1961 pp77-82. (edited reprint of )
14. Gardner, Martin "About Mazes and how they can be Traversed", Scientific American Vol.200:1 January 1959 pp132-137.
15. Gardner, Martin "The Games and Puzzles of Lewis Carroll", Scientific American Vol.202:3 March 1960 pp172-176.
16. Hobby Electronics "Hebot", November 1979 pp10-15.
17. Hobby Electronics "Hebot II", December 1979 pp25-29.
18. Kanayama, Yutaka Iijima, Jun'ichi & Yuta, Shin'ichi "How does a Mobile Robot Understand its World?", EIS-TR-79-11 Institute of Information Sciences and Electronics, University of Tsukuba, Japan. December 7,1979. 17 pages.
19. Lucas, Edouard "Le Jeu des Labyrinthes", Recreations Mathematiques Volume I, Paris 1882 pp39-55 and 240. (in French)
20. Mathews, W.H. Mazes and Labyrinths (Longmans, Green & Co: 1922).
21. Micro Systemes "Des concours des souris est une invitation a construire un robot capable d'apprendre", Sept-Oct 1979 pp79-85. (in French)
22. Ore, Oystein "Excursions into Labyrinths", The Mathematics Teacher May 1959 pp367-370.
23. de Polignac, Camille "Sur la theorie des ramifications", Bulletin de la Soc. Math. VIII 1880 p180. (in French)
24. Practical Computing "Micromouse Maze Contest", reprinted in AISB Quarterly, Issue 35, October 1979 p38.
25. Robinson, Peter "The Pascal Mouse-Engine", Lancaster University (England) Computer Services Department internal document, 8 pages.
26. Shannon, C.E. "Presentation of a Maze Solving Machine", Trans. Eighth Conference on Cybernetics 1951 ed.Heinz von Foerster pp173-180.
27. Tighe, M.F. "Maze Search: A program that solves N dimensional Mazes", Computers and Automation Vol.19:2 February 1970 pp22-24.
28. Wallace, Richard A. "The Maze Solving Computer", Proceedings of the ACM May 1952 pp119-125.