Archive for the ‘Maze Solvers’ Category

1970-3 – Computer Maze – Johan de Boer (Dutch*)

Computer 1970 deBoer x640 1970 3   Computer Maze   Johan de Boer (Dutch*)

Computer 1970 insides deBoer x640 1970 3   Computer Maze   Johan de Boer (Dutch*)

Johan de Boer's description (from private correspondence 2010)

"A second project [ RH: to the Cybernetic Mouse] was the maze where a light was used to indicate the position of an imaginary mouse in the maze. The maze could be changed with small removable barriers. Each square had a small light bulb that would be on if the (imaginary) mouse would be in that square. This whole thing was a cube with sides of about 20 cm. Unfortunately there is no photo and this thing was lost (or scavaged, possibly).
This maze/mouse was controlled with a small especially designed and build computer. This was about 1970-1973. I still have the computer (two photos are attached), and I recently discovered that I still have the schematics for the computer (see pdf here). It was build with about 100 of the 74 series chips, set on 5 circuitboards with an aweful lot of wiring. It has a 1kb (kilobit, not kilobyte) memory chip into which a total of 64 instructions could be loaded. This would run programs at a speed of at most 200 instructions per second (illustrates my electronics skills, I guess). It would query the condition of the maze and sent instructions to the maze in order to change the light bulb that was illuminated. I could then alter the programming in order to come up with something that would learn its way through the maze. The computer, of course was a general purpose machine that could be used to control anything, even an elaborate electric trainset, I would think. "


(*-Johan de Boer currently lives in Canada.)

1981 – Quester Micromouse – David Buckley (British)

Quester maze runner x640 1981   Quester Micromouse   David Buckley (British)

See Quester details and other references in David Buckley's website here. Quester was originally designed to be a micromouse maze solver, and later converted into a general purpose robot with  added gripper (see above).

robot buckley quester x640 1981   Quester Micromouse   David Buckley (British)

David also has a reference to the history of Micromouse competitions here.

For the original Micromouse competition, "The Amazing MicroMouse Maze Contest" c1978, see article here by Donald Christiansen.

1977-79 – “Moonlight Special” Battelle Inst. (American)

Moonlight Special PMAug80 x640 1977 79   Moonlight Special  Battelle Inst. (American)

"Moonlight Special"

micromouse78 x640 1977 79   Moonlight Special  Battelle Inst. (American)

Photo at  Battelle Pacific Northwest Laboratories

micromouse78p2 x640 1977 79   Moonlight Special  Battelle Inst. (American)

 Top – "Moonlight Special" , Middle- "Moonlight Flash"  , Bottom Right – "Midnight Express" all in full dress.

battelle micromice 0001 x640 1977 79   Moonlight Special  Battelle Inst. (American)

battelle micromice x640 1977 79   Moonlight Special  Battelle Inst. (American)

In 1977, Machine Design sponsored yet another mouse contest, "The great Clock Climbing Contest", coupled with the rediscovered information of the 1972 "Le Mouse 5000" contest that spurred on the editors of the IEEE Spectrum magazine in their search for a truly electronic mouse. After much brain-racking and consultations with major manufacturers of microprocessors, they finally came up with the concept of a micromouse – a small microprocessor-controlled vehicle imbued with intelligence and capability to decipher and navigate a complicated maze. In May 1977, the first US contest, called the "Amazing Micromouse Maze Contest" was announced by Spectrum.

New York, June 5-7, 1979. A highlight at the National Computer Conference has 15 micromouse gathered, all poised for a go at the grand prize, of US$1000, and other prizes including an oscilloscope donated by Tektronix and a video computer system donated by Atari. It was the finals of the "Amazing Micromouse MazeContest", a fitting culmination since its first announcement in the May 1977 IEEE Spectrum magazine and four preliminary time trials later.

The final 15 pesky mice were part of the 6000 entries received, some from as far as Italy. Apparently, many failed to turn up – some reported "brain failure" while others claimed mouse "blow-up" and a variety of other reasons. While interest was high, evidently, the design and construction of an intelligent mouse was to be much tougher than most cared to think. Many contestants reported having spent 500 to 1000 hours, many of them off-work and up US$500 on materials and components. Obviously money was not the main reason for entering the contest.

Of the 15 mice, only 4 managed to solve the 8×8-foot maze during their first run and 2 more at their third attempts. The eventual winner was "Moonlight Flash", a mechanical non- intelligent mouse employing a wall- hugging strategy, romping home in a time of 30.04seconds. That a "dumb" mouse could outwit its electronically more sophisticated and supposedly more intelligent opponents then led to the rules being amended for subsequent contests. Instead of being along the perimeter, the goal was placed at the centre of the maze.


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

moonlight special 0014detail x640 1977 79   Moonlight Special  Battelle Inst. (American)

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.

(extract from ref. 2 above)

At the finals in New York's Sheraton Centre, three engineers – two from Battelle Northwest and one from WED Enterprises – teamed up to score a sweep as two of their entries took prizes for fastest and smartest mouse, respectively. Four other micromice solved Spectrum's maze, and two won prizes. Of the 15 micromice entered, only six managed to solve the maze at least once. 

…….

 Learning by exploring was, in essence, the algorithm used by Moonlight Express (Fig. 1)

moonlight express 001detail x640 1977 79   Moonlight Special  Battelle Inst. (American)

as it negotiated the maze in record learning time. Designed and built by Art Boland and Ron Dilbeck of Battelle Northwest Laboratories, Richland, Wash., and Phil Stover of WED Enterprises, Glendale, Calif., it was an improved version of the Moonlight Special, a smart micromouse that had demonstrated its learning prowess at previous time trials of the contest as well as at the finals.
The major difference between the Express and the Special was in their foward speeds: the Express had stepping motors with four times the torque used on the Special. Top motor speeds of 52.07 cm/s for the Express vs 20.32 cm/s for the Special were made possible. In addition the motor-drive circuitry for the Express was strengthened to handle the increased load of the new motors, and the Special's gear train was entirely eliminated.
    Some of the hardware used in the Special – for example, interrupt logic – was eliminated by the use of IC devices that were exclusively from the Z-80A family of components (the Express was based on the Z-80A microprocessor, as was the Special). This represented only a slight modification of the earlier electronic circuitry in the Special (Fig. 2).

Moonlight express maze runner 1979 Fig2 x640 1977 79   Moonlight Special  Battelle Inst. (American)
    A distinguishing feature of the Special was that it looked like a real mouse. Everything else – the optical sensor arrangement, battery supply, and the high-level software – were the same in the Express as in the Special.
    The Moonlight Express and Special were equally intelligent. Both went through the maze on their first runs, exploring paths and mapping nodes (or three-way crossings) into their memories. Both solved the maze on each of their second and third tries, traveling the shortest possible maze routes, from entrance to exit.

The battle of the wall huggers

It was at the third time trial in Los Angeles last year that the Battelle team of Art Boland. Ron Dilbeck, and Phil Stover (Mr Stover is now with WED Enterprises), decided to build a wall hugger They had designed the Moonlight Special, the smartest micromouse observed, but at the time trial the team of Gary Gordon, Gary Sasaki, and Ken MacLeod of Hewlett-Packard, Santa Clara. Calif., Introduced Harvey Wallbanger (below). This right-wall-hugging mouse, with no electronic intelligence, made up with speed what it lacked in brains. It traversed the Spectrum maze in the third time trial In 41 s on its first run.
     Thus was born the Moonlight Flash, (right)

moonlight flash 0021detail x640 1977 79   Moonlight Special  Battelle Inst. (American)

an optical right-wall-hugging micromouse entered by the Battelle team. Moonlight Flash won the grand prize of $1000 with a first run of 30.04 s, beating out Harvey Wallbanger, whose first run was clocked at 41.68 s.
     Although the Moonlight Flash was not considered "intelligent," compared with the Moonlight Special and Moonlight Express — two other mlcromice designed by the same team — It did incorporate an 8748 microprocessor and memory that gave it just enough Intelligence for the winning margin For example, three forward optical sensors mounted on extended arms were used to provide "look ahead" capability to cut corners where possible. The microprocessor and optical sensors optimized the Moonlight Flash's turns at corners to cut down on running time. Whereas an ordinary wall hugger would make a turn at a corner, often slowing in the process and sometimes bouncing off walls, the Moonlight Flash did not require contact with the walls while rounding the corners and did not slow down.
     Another feature of the winner that was not used at the finals (insufficient time prevented the incorporation of this feature) was dead-end blocking. With it, the mouse would have been able to sense ahead dead ends and mousetraps and avoid them. Moonlight Flash was designed to operate from two small dc motors to achieve a top speed of 63.5 cm/s Power was provided by three sub-C Ni-Cd rechargeable and four AA batteries.

To negotiate the maze perfectly — that is, to solve the maze in the shortest run — a mouse would have had to travel but 8 m from entrance to exit. Right-wall huggers would have had to travel 15.83 m while left-wall huggers would have had to endure a more punishing distance of 30.05 m.
     In practice, only the Moonlight Express and Special made perfect runs (on their second and third trials). The $1000 grand-prize winner, the Moonlight Flash, solved the mazc in 30.04 s on the first run, 30.62 s on the second run and 29.78 s the third time around.
     "It's been quite an experience," said one of the three designers of the Flash, Art Boland. "As designers of wall followers, dead-end blockers and shortest-path computers, we know the difficulties encountered in making a transition from one level of intelligence to the next. The number of entrants with plans for intelligence that didn't succeed is evidence that these transitions are more difficult than some people realise. The problem essentially boils down to one of control. For a mouse to be truly capable of learning a maze and making smart decisions about solving the maze, physical control ol the mouse must be both accurate and repeatible. No attempt was made by us to implement our learning algorithms for our micromice until our control software was good enough to accept the learning algorithms."


The Battelle Micromouse (-from Robots and Robotology – R.H. Warring)
The 'Micromouse', shown on the front cover (and Plate 4), is an intelligent robot with a microcomputer 'brain' and an ability to work out how to traverse a maze after just two trial runs. On the third run it goes from start to finish without bumping into a wall, or making a wrong turn. In this respect it is more intelligent than human beings and robot designers are working on how this type of robot can be used in a more sophisticated way — perhaps domestic robots to vacuum carpets and even run household appliances.
The Micromouse was built by researchers at Battelle's Pacific Northwest Laboratories in the USA. Its grey glass fibre body houses about £100's worth of parts — but it took something like 500 man hours to assemble and `debug' this super-rodent so that it could make 33 decisions each time it ran its 20-foot-square maze.
The mouse glides along on two main wheels driven by stepping motors — or motors which rotate the wheels an exact distance for each electrical pulse supplied them. The 'brain' counts the pulses to keep track of the distance covered.
Infra-red beams from light emitters on the underpart of the body are aimed at five sensors attached to arms extending from the upper body. The computer 'brain' stops the mouse when approaching walls or obstacles that interrupt the light beams.
On the first and second runs through the maze, the `memory' capacity of the brain gathers data about the maze boundaries and identifies and enters the location of all obstructions. This is then `processed' automatically to ensure an error-free run on the third attempt, because the 'brain' also has a capacity to work out how to respond under given conditions. For example, it signals `left turn' if the mouse encounters a wall in front and a wall on the right. The `brain', in other words, teaches itself the correct programme to follow.
Switch the battery off, though, and the brain's memory goes
blank. It is then ready to re-learn the course, or another obstacle course, in the next two runs.
Basically, although the Micromouse is really a 'scientific toy', it is a true robot and one which effectively demonstrates the potential of intelligent robots.

moonlight special 0013 x640 1977 79   Moonlight Special  Battelle Inst. (American)

(Plate 4)

1957 – “Gizzmo” Maze-solving Robot – Lauren V. Merritt (American)

1957 Merritt Maze Solver p1 1957   Gizzmo Maze solving Robot   Lauren V. Merritt (American)

Oakland Tribune 22 Aug 1957

Lauren V. Merritt, 17, son of Mr. and Mrs. L.C. Merritt of El Cerrito, was concerned. "Gizzmo is acting up," he said.
"Gizzmo" is a maze-solving robot. Push a button anywhere and a light bounces through a ?complicated maze? and "Gizzmo" remembers the way out. Merritt is a student of El Cerrito High School.

1966 – Mechanical Rat – Meredith Thring (British)

Thring mechanical Rat maze R18p1 x640 1966   Mechanical Rat   Meredith Thring (British)

Pittsburgh Post-Gazette – Feb 1, 1967

……..  He [Professor Meredith Wooldridge Thring, 51, professor of mechanical engineering at London's Queen Mary College] suggested a trip to one of his laboratories.
"Here you see our mechanical rat," he explained. He pointed to a gadget about the size of a boy's electric train. Before it lay a series of little alleys, making up a maze.
"Now watch," he suggested.
The mechanical rat began moving forward, heading for the maze. It took the first turning on its left and headed into one of the alleys, coming to a halt at a wall at the top of the alleys. Reversing itself, the mechanical rat moved back to its starting point, then went forward again and entered the second alley on its left. Moving backward and forward, it explored seven [more] alleys, returned to its takeoff point and halted.
"Now watch closely," said the professor.
Another scientist placed a small piece of cheese at the end of an alley. Once again, the mechanical rat crept forward, took right and left turns and then headed smack up the alley that held the cheese. At the cheese, the mechanical rat halted.
The mechanical rat was being operated by a tiny computer brain built into it.
The hunk of cheese was removed.
The robot backed up, returned to its home base, and started searching the alleys again, going precisely from left to right.

The above description is a newspaper reporter's observation, and does not necessarily accurately depict why it performed the way it did.

Robots and Telechirs – M.W. Thring, 1983.
p184-9
The control sequencer or stepping switch receives a drive signal from the limit switch of the previous movement, or from an external signal which tells it to end the movement earlier. It then goes on to the next operation. In the case of a uniselector switch such as was used in thetable clearing robot (Mark I built 1962); Mark II, built 1962) or the rat in the maze a microswitch operated by an external contact can tell it to move to the same sequence or to a different one.

The 'rat' moved in sequence down each of the eight paths taking a choice of path at each junction but when a small object ('cheese') was clamped at the end of one path it locked onto this path and repeated it continually.


The dating of this entry has been difficult. The overseas reports are dated early February 1967, and the Telechirs report suggesta a date post 1964. It would have had to existed in 1966 so, for the moment, I've chosen that date.