Posts Tagged ‘Maze Solver’

1971 – Model 2004 Maze-Solving Computer – Richard Browne (American)


Source: Xenia Daily Gazette Mon, May 24, 1971

Computerized mouse maze first of 3 long-term projects for Xenian.

by Ward Pimley – Gazette staff writer

To a research psychologist, running a mouse through a maze to investigate behavior patterns is a common occurrence. But to an electronic engineering drawing specialist who wants to simulate the test, various alterations must be made.
Richard Browne, a drawing specialist in his seventh year with Systems Research Laboratories, Inc. (SRL), has recently finished a lengthy project designed to propel a wooden mouse through a maze with directions being supplied by a computer. He resides at 2004 Tahoe Dr.
COMMONLY, referred to as cybernetics, the system constructed by Browne uses a computer attachment which receives data from the mouse as to its location and the presence or absence of barriers, The computer then tells the mouse which direction to move based upon the data. While the mouse is searching for its "cheese," a metal block which short circuits the electric charge upon contact, the computer is storing in its "memory" information pertaining to the maze; that is, where the alley blocks are and what routes are beneficial to the mouse's search for the goal.
CYBERNETICS is a branch of science which mechanically and electronically attempts to reproduce the human thinking process into machines. Browne's computer, designed to comply with this principle, is programmed to receive information from the mouse, "analyze" the situation, then direct the mouse on its journey. The mouse, one-inch creature carved from balsa wood, has two copper whiskers which signal the computer when the mouse has bumped into a maze barrier.
Directional information is then sent back to the mouse whereupon an electromagnet beneath the aluminum maze moves the mouse in the direction indicated. The electromagnet is driven by two one tenth horsepower engines which control both north-south and east-west movements of the mouse.
THE COMPUTER, 600 pounds of wires and relays, has the capability of processing both partial and total accumulations of "knowledge." The partial knowledge refers to the store of information regarding the squares in which the mouse has investigated, while the total accumulation is the computer's memory of the correct path the mouse should take to solve the maze. After the mouse has found the goal, it may be placed anywhere along the proper path and it will move directly to the goal without either making detours or bumping into alley walls. There is an exploration strategy which the mouse follows, Browne explained, every time it enters a square. Five steps are involved, all occurring within one-tenth of a second. The procedure is repetitive and designed so that the mouse will examine all possible avenues of escape from a square. If the mouse should encounter a wall in one direction, it then turns 90 degrees clockwise. If there is no wall in that direction, the mouse will exit the square. Otherwise, it will turn again to check a new direction. There are 25 squares on the maze with removable walls for reshaping the maze. Browne, said there are 873 duodecillion/(873 followed by 12 zeroes) solvable maze patterns possible in his operation. Should the mouse solve one million maze patterns per second (clearly an impossible task), it would take the mouse 2.7 septillion (seven zeros) centuries to solve all possibilities, Browne said.
THE PROJECT took Browne 10 years to complete, working on and off, he said. The idea for the maze came from a May 1955 issue of Popular Mechanics where an article was printed about a man who had completed such a project. Browne decided to duplicate the feat, although he designed and constructed the computer by himself. While Browne built his unit with spare parts, he said that a computer and maze constructed from new parts (and including labor costs) would cost about $15,000. The present project is completed, Browne said, except for a couple of minor improvements to be made. One of these is to put wheels on the mouse to facilitate easier movements. The other is to replace the magnet in the mouse with a stronger one so that the mouse will not escape from the electromagnet's pull from under the table.

However, Browne is not quitting his dabbling with home made electronic projects. He presently has in mind two further projects to operate from the computer he has already built. One of these is a model railroad, which Browne estimates will take him 15 years to complete (working on and off of course). The other is an electromagnetic calculator which will perform complicated mathematics.

Man's creative urge, it seems, still lives in Richard Browne.

See other early Maze Solving Machines & Robots here.


Tags: , , , , ,

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

"Moonlight Special"

Photo at  Battelle Pacific Northwest Laboratories

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

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

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)

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).

    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)

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.

(Plate 4)

Tags: , , , , , , , , , , ,

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.

Tags: , , , , ,

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.
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.

Tags: , , , , , , , ,

1962 – Mechanical Maze with Memory – R.J. Curran (American)

Robert J. Curran's Mechanical Maze is included here as it is essentially a mechanical computer, exhibiting similar characteristics as other electro-mechanical maze solvers.

As the mouse travels a path, if it has to back out due to a dead-end, the return pass triggers a mechanical latch to give the maze a "memory". The patent description gives a more detailed account.

Patent number: 3087732
Filing date: Feb 15, 1962
Issue date: Apr 1963
See pdf here

Tags: , , , , , ,