Posts Tagged ‘Maze Learner’

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: , , , , , , , , , , ,

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.

Tags: , , , , , , , ,

1962 – MELPAR Bionic Maze – R.J. Lee (American)


pdf – Popular Electronics October 1962

Bionics

Bionic "Mouse." As mentioned earlier, RCA is working on a far more complicated moving-target indicator containing hundreds of neurons which operates on the same principle. But perhaps the most important piece of neural-bionic hardware to come out of the laboratories so far is a "bionic mouse" built by the Melpar Corporation. The "mouse" is housed in a small red plastic case about the size of a matchbox, mounted on wheels. A thin umbilical cord of control wires, suspended from a freely moving arm above, allows complete freedom of move ment and connects the mouse with its "brain" mounted in a relay rack.
Although the mouse looks like a toy, U. S. Air Force scientists working with it aren't playing. They are convinced that the mouse is the first step toward a completely new kind of thinking machine, as different from today's conventional computers as a superhet from a crystal set.
Not long ago, in a laboratory at the Wright Air Development Center in Dayton, Ohio, the author saw this "mouse" put through its paces. A technician placed it in a maze and flipped a switch. The mouse ran down alleys, turned corners, came to dead ends and backtracked, and tried other routes. Forty-five minutes later, after exploring scores of wrong turns and dead ends, it reached the end of the maze. The operator picked it up, and set it back at the beginning.
The second time round the mouse made fewer mistakes, and covered the course in about half the time. On the third attempt it ran through in eight minutes. Six tries later, it whizzed through the course in 45 seconds flat without a single error. The mouse had learned the maze, just as a live mouse would!
Bionic devices display true—though limited—intelligence in the animal sense. The bionic mouse has only 10 neurons in contrast to our 10 billion, but like an animal it can adapt to changing conditions and learn from experience. Change the maze, and it's confused—at first. But then it settles down and learns the new pattern.
A bionic "brain," in other words, can operate from generalized instructions. In the case of the "mouse," the only command was "learn to run the maze." Scientists call the mouse a self-organizing system which, on the basis of generalized instructions, figures out how to do the job. Human beings are self-organizing, too. A computer, on the other hand, has to be "programmed"—instructed in detail on every step. It must be told when to turn, when to store correct steps in its memory, and so on.
 

pdf – Generalisation Of Learning In A Machine – R. J. Lee (Maze learning machine) [I'm not sure where I sourced this from – It was downloaded quite some time ago].


SELF-SYNTHESIZING MACHINE R. J. LEE
Patent number: 3327291
Filing date: Sep 14, 1961
Issue date: Jun 1967   – find patent pdf here.


Although I've attributed this maze to Lee, the pictured version may actually have been made by E. B. Carne – see document ref below:

Title : ELECTRONIC REALIZATION OF FUNCTIONAL NERVE NETS.
Descriptive Note : Final rept., Dec60-Jan 62,
Corporate Author : MELPAR INC FALLS CHURCH VA
Personal Author(s) : Carne,E. B.
Report Date : JUN 1962
Pagination or Media Count : 80
Abstract : The self-organizing Binary Logical Network, a learning system using the reinforcement principal, is developed and used to formulate models of neurological subsystems. One of these systems, a maze running vehicle, has been constructed as an experimental and demonstration device. A detailed description of the maze system is provided. (Author)
 


MELPAR Maze:

From Man, Memory and Machines: An Introduction to Cybernetics by Corrine Jacker 1964. p71 [Note: If article is from Electronics World, then this is dated at 1963.] 

The bottom article has it that the word artron was a re-name of reron (relay neuron 1955) done in 1960.

“There are various kinds of artificial neuron. One, Artron (RH-Artificial Neuron), built by the Melpar Corporation of Falls Church, Virginia, is a component of a very interesting bionic computer that operates a mouse who can learn to run a maze. This miraculous mouse is now being studied by the Air Force at their Wright-Patterson Air Force Base near Dayton, Ohio.  The mouse begins its first time through the maze with no special instructions or tendencies to follow one part of the maze more than another.  It finds its way through by a process of trial and error, bumping into blind alleys, retracing its path, and beginning over and over again.
Each time the mouse begins the maze again it has learned something about how the paths are laid out, and gets through in less time. Finally, it can make its way through the maze with no errors in a matter of seconds. This device is only one of a series of maze-running machines that have been constructed.
One interesting refinement that is being worked on now will teach the mouse to associate colors with right and wrong turns. Green will indicate a right turn, red a wrong one. After the mouse “learns” what the colors mean, it could be put into any maze and, if the turnings are marked, run through it quickly and without error the first time.
The practical applications of such a machine are numerous. It is possible that a bionic control system may eventually be able to pilot planes and function in any way where it can be guided by signposts such as colored lights.”

Book references an article, but it may not be the source.
Gilmore, Ken, “Bionic Computers.” Electronics World, March 1963.  Pp 25-28, 63-64.

The mouse is tethered via an umbilical cord. The Brand name on the controller is “MELPAR”, and the inscription on the controller says “Artificial Nerve Network Maze Vehicle”.
 


Perceptrons, Regression,
and Global Network Optimization
John F. Elder IV
IPC-TR-92-10
9/4/92

(Extract from above pdf reference)
3.3. Smooth Logic as an Alternative
The path from perceptrons to polynomial nodes can be traced from the history of an early
“neuromime” company: Adaptronics, Inc. of McLean, Virginia. Adaptronics was formed in the early 60s by four young researchers from Melpar, Inc. (shortly after Air Force funding for “bionics” research jumped by a factor of 25 — see the survey of early techniques by Corneretto, 1960). One of the founders, R. J. Lee, inspired by (Ashby, 1952), had devised an artificial neuron called the “reron” (for “relay neuron”), descriptions of which were only privately published (Lee, 1954, 1955). The reron employed a noise source to switch between circuit states corresponding to six transfer functions, and biased the noise to reward (spend more time in) states with good error feedback. That is, the discrete logic function selected inside the reron was simply conditioned on the training data.
Use of a noise source, or random element, was apparently controversial to the scientific
community of the day. In fact, the idea first saw print as a Letter to the Editor in the July 1953 issue of (that "over the leading edge" monthly) Astounding Science Fiction! The letter was, however, recommended for publication by C. E. Shannon, who had explored a similar idea for "machine learning" (Shannon, 1951), though abandoned it 34 Perceptrons, Regression, and Global Network Optimization "… chiefly because it is rather difficult to trouble-shoot machines containing random elements. It is difficult to tell when such a machine is misbehaving if you can't predict what it should do!" (Shannon, 1953).
(Still, the controversial noise element was perhaps not really a factor in practical implementations, as the reron could have been set to the state most representative of the training data set.).
Given inputs a and b, the possible reron transfer functions were {0, a-, b-, ab- , ab,ab-}
(where “#- ” represents the NOT operation). In 1956, the other ten possible logic functions (including the notorious parity function, XOR(a, b)) were added at the suggestion of R. A. Kirsch (Gilstrap and Lee, 1960), and the node was renamed an "artron" for "artificial neuron". Shortly after starting Adaptronics, Lee's colleagues R. L. Barron and L. O. Gilstrap (living off savings for months) apparently discovered that bilinear multinomials (z = w0 + w1a + w2b + w3ab) could match all 16 logic functions of an artron. Not only that, but the polynomials provided a mechanism for interpolating and for using real-valued, rather than strictly binary, inputs. Hence, discrete computational elements were abandoned in favor of the richer real-valued polynomial nodes.

1959 – Labyrinth solver with Ariadne’s Thread – Zemanek & Eier (Austrian)

Now in the Vienna Technical Museum.

Period photo showing Richard Eier opening the covers of the Labyrinth.


Zitat:  Gerhard Chroust, "Cybernetic Animals at the Technical University of Vienna" , in IFSR Newsletter, Vol. 18, Nummer 2, Seite(n) 2, 1999 

CYBERNETIC ANIMALS AT THE TECHNICAL UNIVERSITY OF VIENNA
G. Chroust
Around 1960 Cybernetics was the path into the future. Numerous cybernetic machines, usually names after animals were being constructed to study phenomena of artificial intelligence.

Claude E. Shannon built a maze-solving mouse to study a labyrinthian problem – telephone switching systems: A call must make its way to its destination by the shortest possible path. The device contains a maze with fences that could be arranged to create various paths. The finder, built as mouse named ‘Theseus’, is moved by a magnet. It gropes its way from field to field and stores the direction, if it is possible to step on a field. If there is a wall, it will turn around and will try the next direction. Unless the mouse comes in a loop it will find the goal. It escapes from a loop through a pedometer which counts to the highest possible number of steps. The way from the entrance to the goal is stored in form of the direction in which the mouse left the field. One can put the mouse everywhere in the maze, it will follow the stored direction to the goal. Only if it comes to a new field or if the maze is changed, it will use a search algorithm, otherwise it will use the stored information.

At the Technical University of Vienna Richard Eier, one of the assistants of Heinz Zemanek re-build the maze-solving mouse around 1959. He improved Shannon’s method by applying the idea of  Ariadne’s thread. The mouse marks each field with the path information, using the concept of Ariadne’s thread. When winding up in a dead end it retraced, duplicating Ariadne’s thread: Whenever the mouse finds an exit from field where one tread leaves and another returns, it recognises a dead end. Similarly the mouse is able to detect circles in its path.
 


Richard Eier studied Schwachstrom-Technology at the Technical University of Vienna. As a thesis he built 1958 Under the auspices of Professor Dr. Zemanek his "mouse in the Labyrinth," by the automated search in a way Free plug a maze learning through success and failure simulated. The idea is to C. E. Shannon, The 1952 is one of the labyrinth to solve problems presented. Richard Eier developed their own ideas and visited the search algorithm with a virtual Ariadne-
Silly, so that at the end Both the successful way From start to the target as well as the Back shortest recorded. In the following
Years ago, the "mouse in the maze" A Vorzeigeobjekt for Vienna Kybernetischen models of Heinz Zemanek. It was in Austrian And several German television Demonstrated and was star guest at the "Micro Mouse Maze Contest "of the Euro Micro You, dear readers, some high points in life's work
My father and his father's doctor friend Mr. Em O. Univ .- Prof. Ing. Dr. Richard Eier to make is special to me Honor and joy. Galt my admiration of his first "in the mouse
Labyrinth "and his juggling with matrices, but soon outshined its people love everything. Professor Eier is Enabler, An individually Fördernder, he often appears modest in the background and waives his rightful glory. His scientific work has weight, shine through precise wording And the highest quality. On this basis is reliable today.


Richard Eier: Gedächtnissteuerung zur Orientierung in einem Labyrinth. Staatsprüfungsarbeit am Institut für Schwachstromtechnik der Technischen Hochschule Wien. Wien 1958.
[Mnemonic Control in a Maze] Diploma thesis of Richard Eier.  [ Unfortunately I do not have a copy of this document].


Automatic Path-finding in the Maze – R. Eier and H. Zemanek [ Automatische Orientierung im Labyrinth ] – pdf in German – no English translation.


It may not be obvious to readers that in implementing Ariadne's Thread, the mouse can escape the maze on the shortest path out by following the "thread" just "laid".  Other maze solvers are placed at the start and stop at the "cheese". A re-run of these mazes are all from the start position.


Selected images from my visit in June 2009 with David Buckley  [Photos by Reuben Hoggett and David Buckley]

Underside of mouse showing two imbedded magnets. Above it is the re-locatable goal (i.e. the "cheese").

Eier's Labyrinth now operated by a microprocessor – the relays are bypassed.

Front panel – detail.

Front panel outlining configured maze layout.

External relay covers.

Carriage mechanism.

Table-top with maze and mouse.

Internals showing one of the carriage motors.

Internal photo showing the wiring of the relays.

Thanks to Heinz Zemanek, and also Peter Schoen and Dr Otmar Moritsch of the Vienna Technical Museum who allowed David and Imyself to study and photograph the Labyrinth,  June 2009.  

Tags: , , , , , , , ,

1933 – Maze Learning Machine – Thomas Ross (American)

The Thomas Ross Maze Learning Machine showing its feeler tracking the slots of this comb-shaped maze.

See complete Scientific American 1933 article titled "Machines That Think" – pdf here.