Return to List of Reports
Highlights from |
|
Volume 15 ---- Spring 1986 |
Contents of Highlights
The maze consists of 16 x 16 squares, each 18cm on a side. The walls are 12mm thick, 5cm high, painted white with red tops. The target is the center, and the start is at the 'bottom left' corner. The running surface is chipboard, painted black with non-gloss emulsion paint. The walls are composed of removable segments connecting posts at the corners of the squares, so that mazes can readily be changed.
What is a Micromouse?
A micromouse is a mobile sensing robot that can negotiate a maze. The contest rules state that the mouse must be self-contained, cannot use combustion as an energy source and cannot leave part of its body behind while in the maze. It cannot jump over, climb, scratch, damage or destroy the maze walls. It must be less than 25cm in both length and width; there is no height restriction.
Most mice use active infrared sensors to locate the walls. A pulse of 1000 nanometer infrared is shone downwards from a vane that extends over the walls adjacent to the mouse. The red top of a wall sends back a strong reflection, while the black floor does not. Some mice, notably the Finnish team have used acoustic sensors. The Noriko mice used the position gyroscope as an additional sensing device to preserve accurate control during rapid cornering.
The most popular microprocessor used to control the mice is the Z80. In 1981, Alan Dibley went so far as to saw off the keyboard of a Sinclair ZX80 computer and use it intact to control his Euromicro finalist, 'Thezeus'. Indeed, the 'Thezeus' series were largely built out of bits of junk-piano wire, rubber bands (for tires), and parts from radio-controlled models.
Championship Rules similar to rules applied at the Museum Mouseathon)
Each mouse has 15 minutes in the maze. It can make as many runs as it likes, and the fastest 'inward' run from the start to the center is recorded. If a mouse 'gets into trouble', it must be taken out of the maze and restarted at the beginning. No information on the maze can be fed to the micromouse. For full rules see IEEE Micro, Vol 4 No 6, (1984) pg 86; for information about future contests, contact Micromouse Committee, IEEE Computer Society, 1730 Massachusetts Avenue NW, Washington, DC 20036.
Origins
It all began with a 1977 announcement in Spectrum magazine that the time was ripe for microprocessors to put on wheels for a self-controlled ride. The challenge was to build a mouse that could find its way to the heart of a maze, remember it, and then run the course as fast as possible. The IEEE Computer Society formalized the competition, specifying maze and mouse dimensions, and trials took place throughout 1978 with a final race at the National Computer Conference in 1979. The winner was the only mouse among the 24 entrants that made it to the finish! The rest of the entrants got stuck or confused, or just failed to start. But the contest looked like fun. These small mobile robots require hardware for propulsion, steering, guidance, wall and track sensing and software for mapping and strategy The fixed set of rules constrains the problem and the contest provides a quantitative measure of progress.
International Micromouse Racing
The idea has taken off in Europe and Japan. Under the impetus of Dr. John Billingsley, mice from the UK, Finland, West Germany Switzerland have competed in European championships held every year since 1980.
Since the first Japanese micromouse contest in 1980, the Japan Micromouse Association has grown to 800 members spread throughout the country. The association has a permanent board of directors, consisting of senior academics, industry executives and officials of the Japan Science Foundation. A bimonthly magazine 'Mouse' is published, covering micromouse events worldwide.
In 1985 the Japan Micromouse Association held a World Micromouse Contest coinciding with the World Expo in Tsukuba City, Japan. With support from the Japan Science Foundation and NAMCO Ltd., the Japan Micromouse Association invited teams from Britain, Finland, Germany,
South Korea and the United States to compete. It soon became clear that the visiting mice were no match for the Japanese entrants. The first five prizes all went to mice from a single Japanese microcomputer club-the Fukuyama Club, from Hiroshima Prefecture.
Micromice in the US
Although the idea originated in the United States in 1977, it has not caught on. In 1984, in an effort to rekindle US interest, the Japan Micromouse Association presented the IEEE Computer Society with an official micromouse maze for use in the US contest where participants in the world contest would be selected. Mappy, the official mouse of the Japan Micromouse Association was loaned together with the maze. In the Spring of 1985, The Computer Museum and the IEEE Computer Society agreed to site the maze at the Museum, develop a micromouse exhibit and hold a special inaugural event.
The Museum Event
Dr. Peter Rony of the IEEE Computer Society and Dr. John Billingsley from Portsmouth, England kicked off the Museum's race week with a lecture/ demonstration on Sunday, November 17. Dr. Billingsley demonstrated three mice he had brought from England.
A group from The Japan Science Foundation, NAMCO and the Fukuyama Club were also invited. Mr. Hirofumi Tashiro, Secretary General of the Japan Micromouse Association and Manager of the Director's Office at NAMCO Ltd. led the group. Three members of the Fukuyama club came: Mr. Masanori Nomura, a trained veterinarian, Mr. Masaru Idani, system technical researcher for Japan System Design Co. Ltd. and Mr. Eiichi Fujiwara. The IEEE Computer Society arranged for Mr. Key Kobayashi, an interpreter to attend.
The Inaugural Run
John Billingsley's three English mice rapidly cleared customs at Logan airport in Boston where they are used to seeing weird electronic contraptions. 'Thumper', the 1981 European champion by David Woodfield, runs on four wheels and turns by swivelling his wheels, not by rotating the whole body. His large and heavy frame tends to thump the walls, hence the name. His ability to talk, apart from being very funny, is used for diagnosis. 'T6; the latest in a series of 'Thezeus' mice by Alan Dibley, and 'Enterprise; the 1984 European Champion by David Woodfield are both three-wheeled mice with DC motors to provide propulsion on the back wheels and an optical distance counter on the steered front wheel. All three use the Z80 microprocessor.
The 1985 World Micromouse Contest at Tsukuba Fifteen contestants from 5 overseas countries and 120 from Japan competed.
Though delicate, the mice survived the journey intact, and they were checked out on a trial maze. It soon became apparent that Thumper was most confused, and T6 was steering straight into the walls. Preferring not to attribute this performance to jet lag, we suspected that the maze itself was not giving the infrared signature required by the mice. The mice detect the walls by using active infrared sensors that stick out above the walls of the maze and look down. The tops of the walls are meant to be reflective in infrared (around one micron wavelength) and the black floor of the maze is meant to absorb infrared. However, the floor of the maze, though black, looked rather shiny in the infrared, so after obtaining permission from the IEEE Computer Society, we covered the maze floor with a thick coat of the mattest black emulsion we could find. Thumper and T6 still occasionally went 'blind; so we began to suspect the walls. Using Thumper as an infrared reflectometer, we found that the dull red plastic layer that covered the tops of the walls was actually a very poor reflector of infrared. So we covered all the wall tops with strips of highly infrared reflective red sticky paper, and this solved the problem.
At the start of the Sunday lecture, Peter Rony spoke on behalf of the IEEE Computer Society, presenting the Museum with the loan of the official maze, and encouraging future mousebuilding activities in the US. John Billingsley then described the history of European micromouse events and demonstrated the three English mice. Thumper, though slow and lumbering, makes up for it by his speech, saying "I will find the shortest route" as he pulls off from the start. Apparently at random, he sings out with a repertoire consisting of remarks such as 'I hope there are no cats in here; 'my work is never done' and'I could do with a restmy wheels are killing me!' When comparing Thumper to the later mice, it's hard to believe that he is more than all talk and no action-he was actually the European champion in 1981.
Enterprise and T6 learn the maze after relatively little exploration and take advantage of the straight passages with bursts of acceleration.
The Mouseathon
After 21 hours in the air, the Japanese participants arrived late on the Thursday before the Saturday event. Refreshed the following morning, they unpacked their mice-all members of the 'Noriko' series. The older X1 and X2 performed well at once, but X3 and X4 seemed a bit worse off for the long travel, and needed some attention from the chief engineer, Mr. Idani.
After a burst of speed down a straight,
T6
brakes just in time to round a corner.
Mr. Tashiro watches Mappy at the maze's start NAMCO, a large manufacturer of computerised games and toys, built 10 identical show mice in 1981 to promote interest in micromouse racing. Modelled after a popular Japanese cartoon character, Mappy plays the role of a mouse policeman, scouring every alleyway of the maze to find a troublesome stray cat. With siren blaring and baton waving, he bears down on the center of the maze where he spins around to burst a balloon with a pin mounted on his tail. Then he - races back to the starting square, sirens still blaring and lights flashing, and shouts "I got 'em!" in Japanese.
Mappy will be demonstrated regularly at the Museum while on loan from NAMCO.
An enthusiastic crowd of over 400 people showed up for the event. Throughout the morning and early afternoon time-trials were held. Each mouse had fifteen minutes in which to make its best run to the center (see rules box). All mice completed the maze, except for Noriko X4 which never really got going. Noriko X1 came in fastest, at 14.8 seconds in contrast to Thumper who managed to talk his way through the maze in 3 minutes. Mappy performed a couple of his noisy runs, greatly entertaining the audience.
The race's judges then took their places: Susan Rosenbaum, governing body member of the IEEE Computer Society and volunteer in charge of US micromouse activities, affectionately known as 'micromom; Gwen Bell, the Museum's president, Hirofumi Tashiro and John Billingsley.
The maze was changed to make sure that memories of the time-trial maze could not give any mouse an unfair advantage and the race then began with the mice competing in the order in which they qualified.
Noriko X4 still failed to wake up, but X3 completed a run in just over 13 seconds. Next, Thumper talked his way into the corners, so badly out of alignment that he had to be retired. T6, which must be the quietest mouse ever built, came in at 37.2 seconds. Enterprise performed reliably again, never slipping or needing any kind of adjustment. But his time of 28.1 seconds proved no match for the Japanese.
Now the two fastest Noriko's battled it out. Although the Noriko mice carry out a lot of apparently redundant maze exploration at the outset, they make up for it with speed and cornering agility once they find the shortest routes. It was breathtaking to watch the slalom as they swung aroung the final zig-zaps towards the finish. Several times the Noriko's got stuck a hair's breadth from the finish and had to be carried back to the start. In the end, powered by a freshly inserted heavy duty Nicad battery pack, Xl made a lightning fast run of only 10.85 seconds, just over half a second faster than X2's best run of 11.55 seconds.
Judges Susan Rosenbaum (left), Gwen Bell (center), and Hirofumi Tashiro with john Billingsley commentating.
Gwen Bell awarded the prizessilicon wafer pendants, hung around the necks of the human participants, not the mice.
The Future
The Museum will hold more races when new mice come forward to challenge the Japanese and Europeans. There are encouraging signs-several groups took notes at the races, saying they planned to build micromice with better maze-solving strategies. For those who want to try their hand at the software side of micromouse racing, NAMCO Ltd. makes a kit that can be purchased via the IEEE Computer Society.
John Billingsley is now promoting robot ping-pong, or 'robat'. Contestants mount their payers at either end of a special table with controlled lighting and a mechanism to serve the ball. The players essentially consist of a bat fixed to an x-y plotter mounted vertically together with a vision system.
The Museum plans to collect micromice and provide a venue for future international sporting events!
After the award giving, from left to right: Eiichi Fujiwara, Masanori Nomura, John Billingsley, Oliver Strimpel, Masaru Idani. Mr. Idani and Mr. Fujiwara hold 1st and 3rd place winners, Norikos XI and X3. The Noriko series employs a 'wheelchair' drive: two wheels have drive motors and steering is accomplished by driving them at different speeds. Fore and aft are wheels, castors or skids to provide stability. The newer Noriko's are DC motor driven, the older ones using stepper motors. A home-made position gyroscope with its axis mounted horizontally gives the mouse an accurate measure of how much it has turned, a critical piece of information when the wheels are liable to skid during very rapid cornering. These mice also have easily inserted ROMS, used to give the mouse different strategies, depending on the maze. ROM- swapping and tweaking of potentiometers is not allowed in European contests where a more rigorous criterion of micromouse self-sufficiency is applied.
Throughout my career as a computer designer, I have set out on explorations into the unknown. Over and over again I undertook the design of new computers without the foggiest idea of how to do it. Over the last twenty years, I was involved with-three different machines at three different companies. In what follows, I have corrected all the dollar amounts for inflation so that direct comparisons can be made.
By August 1964, the specs had been completed
on the
DDP-116.
In October the machine was
announced and the first shipment was in March
of 1965. Only 200 were ever sold.
In 1965, CCC announced a new logic family called the Micropac using integrated circuits. These were the first commercially available integrated circuits that were designed by CCC and subcontracted to semiconductor manufacturers. The most reliable manufacturer for these flat packs was Westinghouse. CCC had also by this time designed a less than one microsecond cycle time memory.
When the 116 was shipped in March, 1965, we immediately started to work on a low cost version, the 416, and a higher cost version, the 516. Shipped in September, 1966, the 516 had a .96 microsecond cycle time and sold for $82,000. The 416 built with a hobbled 116 instruction set was supposed to cost $5,000 and sell in large quantities. While it was estimated that only 130 of the more expensive 516s would be sold. Very few 416s were ever bought, but over 2000 516s. Then a 316, lower-cost, slower machine was built to compete with DEC's lower cost 12-bit machines that seemed to be flooding the world.
After CCC was bought by Honeywell a process of decay had set in. I stayed at Honeywell working as an engineering manager and then as a product manager in marketing. Prime was formed to step into the vacuum that Honeywell left in getting out of the minicomputer market. Every machine up through the Prime 750 was object code compatible with the DDP-116 and 516.
1973: The Advent of Microprocessors
In 1973, I had the opportunity to join Data General to design a microprocessor-based computer. They had a successful 16-bit minicomputer line based on the NOVA and they wanted a NOVA on an MOS chip. My only problem with this opportunity was that I didn't know what an MOS transistor was or how it worked. And once again I was off on a new odyssey: I didn't have the foggiest idea of how you did logic with microprocessors. Otherwise, I was excited about the challenge and took the job.
The first microprocessor, Intel's 8008, a P-channel, 8-bit device, had an accidental birth. It was the outgrowth of a contract with Datapoint who had specified the architecture for a microprocessor. After the contract period had expired and both Texas Instruments (the alternate supplier) and Intel had not delivered, the contract was cancelled. TI dropped the project but Intel chose to continue it and fund it internally. The rest is history in the microprocessor business.
Data General decided to use the newest technology: n-channel processing, which produced much faster MOS transistors, and silicon gates which provided additional interconnect capability. The decision was made to build the machine in-house at DG's own semiconductor facility, which had been operational for about a year. The hardest part of designing a 16-bit computer on a single chip at a time when 8bit computers represented the state of the art, was fitting it all onto the available area of silicon. The first decision was to use an internal 8-bit data path and arithmetic unit. I also decided to go to a serial i/o bus to solve some of the pin limitation problems. The adder would be the slowest part, even with carry predict circuits.
A second person was added to the project: a circuit designer in Sunnyvale. He showed me that registers are cheap and random logic terrible. With that information we decided to make a micro-coded machine, even though I had never done that before. In the process I picked up a Fairchild application book that had a picture of a PLA (programmed logic array) in the back. It looked like a nifty idea for instruction decoding. It also occurred to me that if you put a second PLA on the rear end of the first, all the decision making could be done by looking at the results of operations and deciding what to do next. An area efficient design was developed with two PLAs for the sequencing. The chip also had a real-time clock in it and generated refresh addresses and refresh timing for the dynamic namic rams during periods when memory was idle and internal processing was going on in the chip.
It took me about a year to get educated and design the chip. Then we hired a technician to build a TTL simulator who put 1,000 i.c.s on wire wrap boards. He hand wired 20,000 connections to build the simulator and had it running in six months. It then took eight months to hand draw the IC layout. Because of the difficulties of the new process and the large line size, another year was consumed in getting all the details ironed out in order to make production units. Thus, it didn't ship until early 1976.
DG's single-board $1,500 computer with the 8-K bytes of memory on a single board was equivalent to the DDP-516 that sold for $82,000 a decade before. Adding a card cage and i/o, the price of the micro-Nova increased to $8,300; one-tenth of the price of the previous decade.
1980: Fault-Tolerant Computers
The decision to start Stratus in 1980 was based on the apparent need for fault-tolerant computers in commercial on-line data processing environments as opposed to those built for scientific ones. This led to a new exploration since I didn't know anything about the subject. When I went to the MIT library I was surprised to find volumes one through nine of the Proceedings of the Conferences on Fault-tolerant Computing oriented toward research and aerospace applications. The 1962 Apollo Guidance Computer built for NASA (that can be seen at the Museum) was a fault-tolerant machine. Only Tandem Computers had moved the technology to the commercial world.
Starting in 1974, Tandem had a 100 million dollar software intensive business by 1979. Any fault-tolerant system needs to be redundant until somebody invents parts that can heal themselves. The basic principle of Tandem was two computers side by side that could work with common mass storage. Errors are detected through memory parity or a stall alarm. A failure would restart the program at the last checkpoint on the backup machine.
This software intensive approach could be a major problem with many terminals involved in online data processing applications. If the system could allow some slowing down when a failure occurred, then the backup machine could be doing something useful driving normal operation. This solution had been invented in days of expensive hardware in 1974.
Stratus decided to build fault-tolerant hardware and not software. We chose a technique that required each element of the machine, such as the cpu board, to be able to detect its own failures. The simplest way to do this is to build two sets of everything and just before anything is sent out on the system bus, a comparator checks the two. If they aren't the same, the board is broken. With two boards, the work goes to the other board. This requires four sets of logic, which sounds expensive, but it isn't. I guess I should point out that we didn't figure out the scheme we used until after we raised the money for our startup.
One of the first things we did after the architecture was determined, was to put a red light on the end of a board to signal failure. Then field service didn't have to figure out what was wrong, but just take out the board and send it to the factory. Then we asked ourselves, "If field service isn't needed for fault detection, why are they needed on the customer site at all? Have the customer do it without a service call." This creates a new problem. The replacement has to be a fool proof insertion, without any special switches or an umbilical cord which might confuse the customer. In the final design, any board could be pulled out of a running machine and put in another one without anything happening.
Another problem was uncovered. How would we know what board to send to the customer for replacement? Could we depend on a secretary to pull out a bad board, read the model number, and accurately repeat it on the telephone? We thought that would be too much to ask. We added a feature that let the system read the slot location, the error state, the model number, revision level, and serial number of the bad board, finally throwing in a modem so that the computer could report the bad board directly to field service at Stratus. The electronic mail message to the Stratus computer reports what failed and all the details of the occurrence. The typical scenario is that the Stratus home office then calls up the customer and tells him that his machine has a failure. The customer doesn't know it until he's told. By then, the replacement board is on its way by Federal Express.
We also decided that there was no benefit in designing your own instruction set. It's fun, but a fool's errand if the objective is to make money. So we used commercially available microprocessors. We chose the 68000, the best machine in late 1979. Since we wanted to make a virtual machine, we found that the 68000 could not cope both with a page fault and restart, and at the same time go out and get a page from disk and lead it into memory. So two 68000s were put on each cpu board. The next step was to have part of the operating system run in the second 68000 in addition to the page fault handler. Then more and more processors were put in the system to run both operating system code and user code.
The second Stratus multiprocessor system has six microprocessors running concurrently out of a very large shared memory. The four microprocessor version has a .125 microsecond memory cycle time and sells for $200,000 with 4,000K bytes of main memory and a 400 megabyte disk.
A Continuing Odyssey?
It has been an adventure for me to be associated with all these computer projects. Once again I'm on a quest and will only be able to describe the avenues I explored when it is all behind me.
A Set of Classic Film Clips Showing
Computing From 1920 to
1980
This film about data processing before the computer illustrates one of its clearest antecedents.
Automatic Computing With EDSAC, 1951
Whirlwind I: Programming at 3:00 A.M., 1953 From "Making Electrons Count"
Ellis D. Kroptechev and Zeus, A Marvelous Time-Sharing System, 1967
STRETCH: The IBM 7030, 1960-1981
This unique film, produced for the Museum, shows one of the first supercomputers ever built.
Only seven STRETCH's were ever built.
When he joined the young company in 1958, Seymour Cray tried to persuade president William Norris that there was a market for a low-cost, high-speed computer designed for scientific applications. Norris was sufficiently convinced to let Cray develop the Little Character. The machine used a small number of standard circuits made by loading transistors onto small circuit boards. These in turn were connected via a hand-wired backplane.
The Little Character vindicated Cray's modular design and Norris was convinced. The company then used the ideas embodied in the Little Character to build the Control Data 1604, a computer aimed at the low-priced scientific market.
On loan from Control Data Corporation, Minneapolis, Minnesota
Return to List of Reports