Archive for the ‘Maze Solvers’ Category

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

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

1955 – Electronic Mouse Maze Solver – Harry Rudloe (American)

The original article appeared in Scientific American, The Amateur Scientist,  An Electronic Mouse That Learns From Experience by Harry Rudloe, 1955 Mar, pg 116 .
 

This copy from C. L. Stong.  The Amateur Scientist.  Ill. by Roger Hayward.  S&S, 1960.  The Electronic Mouse That Learns From Experience, pp. 394-398.  Harry Rudloe describes a relay circuit for solving a simple maze being his variation of Claude Shannon's celebrated robot. See pdf here.