|main site > home > Micromouse||28 May 2007|
Microcomputers: The Great Electronic Mouse Race
Apart from the experimental psychology community, racing mice through a maze has never caught on as a popular pastime. Microelectronics, which makes it possible to pack the essential elements of a computer on one or a few chips of silicon, could turn this situation around. A contest sponsored by the Institute of Electrical and Electronics Engineers (IEEE) by way of its Spectrum and Computer magazines is under way which offers $1000 to the builder of the self-contained electronic mouse that can negotiate a maze in the shortest time. Although no one knows what will come of it all, Spectrum's Roger Allan noted that some 6000 persons from around the world were interested enough to pay a $3.95 entry fee by the March deadline.James Hamblen's mouse tries the maze.
The contest consists of a series of trial runs to be held at computer conferences and electronic trade conventions. Entries that successfully negotiate a maze at one or more of the trial runs (a different maze will be used at each trial) are scheduled to compete in a final race-off next June at the National Computer Conference in New York City. The first trial has already been held at a personal computing conference this past June in California. Of six entries, two mice managed to complete the course.
The rules of the contest are designed to emphasize microelectronics. Mice are allowed three passes through the maze. Thus, by using a microcomputer to "remember'* where it has been, an electronic mouse can "learn" the vagaries of the maze on its first two trips and select an optimum path on the last pass. Furthermore, the mouse must be completely self-contained, although it need not physically look like a real animal. Live mice are not prohibited, but a rule outlawing the deposition of any material substances on the race course strongly discourages their use. Finally, radio-controlled mice are barred.
Basic elements of the maze include straightaways, U's, T's, L's, and dead ends (mousetraps). These are connected to form a maze of up to 20 feet square. The width of the pathway is 61/2 inches, and the height of the walls is 2 inches. There is no ceiling, so that the mice can be tall enough to look over the walls, but they cannot be so tall that they tip over. Neither can they step or fly over the walls.
Winning mice in the first trial run negotiated a 5- by 10-foot maze of this type in 51.4 seconds and 4 minutes 32.5 seconds, respectively. The large time difference was primarily due to the different strategies devised by the "trainers" of the mice. Surprisingly enough, the four non-finishers failed not because of poor learning ability but because they could not make 90-degree turns - the only kind in the maze - when they bumped into the walls of a corner.
The fastest mouse was built by Art Boland, Phil Stover, and Ron Dilbeck of the BattelLe Northwest Laboratories in Richland, Washington. According to Boland, they built their entry around a microcomputer with enough memory to store the information needed to make decisions at 99 different positions in the maze. The general strategy adopted was, for the first of the three allowed passes through the maze, to allow the mouse to make random choices at each decision point. For the second pass, the mouse was made to try new paths that it "knew" it had not tried on the first. The information collected was then used to compute the best course to follow on the third run.
The Battelle engineers used a number of infrared emitting light diodes (LED's) coupled with photodetectors as sensors to monitor the white walls of the maze and to locate the holes in the walls at corners or where new paths began. The mouse, measuring 5 inches long by 5 inches wide by 7 inches tall, was powered by alkaline cells.
James Hamblen of Martin Marietta Aerospace, Denver, designed the second place finisher. Hamblen's mouse was not as smart as the Battelle entry; it was programmed simply to follow the left wall of the maze. As long as the entry and exit slots are on the outside perimeter of the maze, such a strategy guarantees a solution, even if it takes a while to find it. Another difference was that Hamblen's mouse was cylindrical; thus, it could always manage a turn, even after running into a wall. The Battelle mouse's sensing system was designed to prevent the square mouse from getting too close to a wall. In other respects the two mice were similar. In particular, the use of separate stepper motors to drive a wheel on each side of the mouse permitted both to make sharp turns - one wheel could be driven forward and the other in reverse, for example.
Both mice took considerable effort to build. Boland estimates his group put in about 500 man-hours, all after hours, while Hamblen guesses he spent approximately 1000 hours on his project.
According to Allan, the reason for the "Amazing Micro-Mouse Maze Contest" is twofold. The first is promotional, to give the society a bridge to the general public. The trial run held this June, for example, appeared on a Los Angeles news telecast. The trial also attracted strong spectator interest; particularly popular was one Italian entry that appeared lifelike but which failed to solve the maze. A second goal was to present a challenge to engineers that might ultimately have an impact elsewhere, although exactly where is not clear. Credit for coming up with the contest idea is given to the editor of Spectrum, Donald Christiansen.
It is said that no matter what new idea one comes up with, a thorough search of the literature will reveal that it has already been published. The electronic mouse is no exception. It turns out that in the early 1950's Claude Shannon, now retired from Bell Laboratories, demonstrated a maze-solving mouse. What Shannon did not emphasize, however, was that under the maze, connected to the mouse by a magnet and surrounded by curtains, was a device driven by instructions from a large electromechanical (no solid state electronics in those days) computer. As it happens, Shannon's maze-solving mouse was using a program based on those being developed for the electronic switching machines that route calls through the maze of the telephone network.
- Arthur L. Robinson
SCIENCE, VOL. 201, page 800, 1 SEPTEMBER 1978
Just to remind readers what this is all about, the "mice" were small robotic vehicles which had to escape from a maze without any previous knowledge of it and without human intervention. The idea was to encourage engineers to make use of the latest electronics devices, particularly sensing, logic and memory circuits. In the event, although US companies had contributed $250 000 worth of devices the only entrant, Ernest Kalbfleisch, had chosen a basic design with his mouse relying on sensors which allowed it to "feel" its way along the wall of the maze.
But anyway all this is much more important than another topic reported alongside the mouse story: this occupied 14 column inches in the International Herald Tribune of 27 August; just below it was a report about the Bikini Islanders accepting plans to evacuate them because of lingering radiation. Its length? Just over one column inch.
Last-week the 15 electronic survivors from 6000 original entrants slipped and slithered their way through the maze or, in the case of nine entrants, failed to make it to the finish. The winner was Moonlight Express, a robot designed by three experts from the Battelle Northwest Laboratories, a truly intelligent robot that reduced its time from 100 seconds on the first try to just over 30 on the third and final run.
Unfortunately for the hopes of electronic engineers, the fastest robot over-all was a totally intelligent (sic) one, that raced around in less than half a minute by the simple strategy of sticking close to the right wall of the maze. Because it showed not an iota of intelligence, that entry was adjudged ineligible for the top prize of $1000.