Posts Tagged ‘Maze Solver’

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

pdf – Popular Electronics October 1962


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

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:

Descriptive Note : Final rept., Dec60-Jan 62,
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)


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

(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 

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.

1955-57 – Maze Solver – M. Gavrilova (М.А.Гаврилова) (Russian)

Maze currently found in Polytechnic Museum of Science and Technology , Moscow.

Cybernetic model "Mouse in the maze" (see video clip here)

[Thanks Joseba Arruabarrena as the video clip is now on youtube.] 

One of the first developments in the field of cybernetics in the Soviet Union. Modeling ability to learn the simplest living creature – to search for goals, followed by memorizing the shortest path to that goal. The model is a black box, with illuminated circuit labyrinth. Lighting simulates the movement of the mouse through the maze in search of food, which is set by switching toggle switches on the ends of individual sections of the path of the labyrinth. When you first run into a maze of "mouse" should be the rule of "one hand" – consistently ignores all the corridors is strictly in one direction. Following the discovery of "food" – remembers the shortest path to the goal and the next time you start moving to it on the way to the shortest. Logic circuit and memory models are based on telephone relays. The model was developed and manufactured in 1955-1957. the Institute of Automation and robot USSR in the laboratory of Professor M. Gavrilova (1903-1979). 
1. Кибернетическая модель "Мышь в лабиринте" (видеофрагмент)

Одна из первых разработок в области кибернетики в СССР. Моделирует способность к обучению простейшего живого существа – поиск цели, с последующим запоминанием кратчайшего пути к этой цели. Модель представляет собой черный ящик, с подсвечиваемой схемой лабиринта. Подсветка имитирует движение по лабиринту мыши в поисках корма, который устанавливается переключением тумблеров на концах отдельных участков пути лабиринта. При первом запуске в лабиринт "мышь" следует правилу "одной руки" – последовательно обходит все коридоры строго в одном направлении. После обнаружения "корма" – запоминает короткий путь до цели и при последующем запуске движется к ней по пути самому короткому. Логическая схема и память модели построены на телефонных реле. Модель разработана и изготовлена в 1955-1957 гг. в Институте Автоматики и телемеханики АН СССР в лаборатории профессора М.А.Гаврилова (1903-1979).

Below are a series of still images from the above video clip, showing internals as well as a sequence of maze learning followed by the running of a learned maze. The throwing of a branch switch tells the machine if a branch or 'gate' has been blocked or allowed for passage..

[I need a translation to describe the above component and how it works.]

Internals showing the relay memory.

Behind the front panel whowing the wiring to the switches and lamps.

The start of the maze learning which gates are passable.

This switch is the start position of the maze.

 Labyrinth – a working model of a learning machine-type mouse in the maze (Fig. 13.4, b).  Labyrinth has one input and eleven dead ends.  Each pin has stalled – "bait" for the mouse, which here replaces the light beam.

 (ris.13.4) E-maze: a – an artificial mouse "Theseus", b – light-maze (1 – the first call, 2 – follow-up visits. C – Start, F – Finish, A – "memory", in – circuit breaker)
Principle of
 Principle of action.  The closure of the switch "Request" and pressing "Search" (Figure 13.5) leads to the fact that the ray of light "rounds" all the corridors and dead ends, until you reach the place where we placed a "bait".  Search stops.  Last impasse remains lit.  If we disconnect switch "request", the lamp goes out, but will remain in the memory cell information about the shortest path from the entrance to the impasse with the "bait".  Time of storage of information in memory is 30 seconds.  During this time, mice can get to "bait", avoiding unnecessary deadlocks.  If within 30 seconds the machine will not get repeated requests, it "forgets" has studied the way and it all starts again.
 If you try to deceive the mouse and put "bait" in any of the nests, then after the command "Search" light beam obezhit entire maze and stop.  At the same time spreads the inscription "The Labyrinth is empty.  Within half a minute can be any number of times lock switch "request", and despite this, the light beam will remain stationary.  Only 30 to go off control lamp "Memory", informing them that the car had forgotten "about the" deception ".
 While searching for ways to "bait" the light beam is delayed by 2 s in each transition.  When the path of "known", he has only half a second to the entrance to get to "bait".  Knowing the way, the mouse runs faster.
 The device consists of a time relay (storage multivibrator. Search "bait" is with a telephone selector (the seeker).
 He switched with a frequency of 0.5 Hz when searching and much faster when re-run of the famous road.

 (ris.13.5) Schematic diagram of the light maze
Design details and
 Details and design.  Telephone stepper seeker with 27 contacts, telephone relays, such as MT60 with coils (resistance 700Om), incandescent lamps 24 … 36 V. The power supply – 24 V battery or AC mains (via a rectifier).  If there is a step seeker, who works at a voltage of 6 … 12 V or achieved self-powered, all other elements may be powered by batteries 4,5 … 12 V. In this case, suit miniature incandescent lamps 3,5 or 6, 3 B.
 The front panel of the maze made of plywood or plastic (Figure 13.6, b).  Its dimensions are 250 X 250 mm or 150 X 250 mm.  The corridors of the labyrinth of normal shape (Figure 13.6, a) can be covered with frosted acrylic or white plastic.  You can just put under the transparent acrylic tracing paper on which the black ink marked pattern of the labyrinth.  Near the front panel of the labyrinth located switches and alarm devices.  Lamps "Labyrinth is empty, you can connect the CO call or sound generator.
 All the device is a small suitcase.  Its front panel is connected by wires with steel ustroystvami.Esli not in the presence of 16 relays and stepper seeker for 27 contacts, should reduce the number of lanes and alleys of the labyrinth, and thus the ramifications of light paths.  If there is a sufficient number of relays, and appropriate steps seeker, you can build a more complex maze.

 (ris.13.6) Structures of the light of the labyrinth: a – a modernized, b – Summary  Labyrinth

Tags: , , , ,

1953 – “Franken” Maze-Solving Machine – Ivan and Bert Sutherland


The original Franken maze solver was designed and built by Bert and Ivan Sutherland. I suspect it was built for Edmund C. Berkeley.  Berkeley , it appears, had used the early version as a prototype, and engaged his other associates, namely Bob Jensen, Juli Skalski and Stan Skalski in drawing up a revised document suitable for sale as plans, kits, or small-scale production in 1957.

Above pdf has notes Franken made by Bert Sutherland as sent to Ed Berkeley.

Berkeley's internal memorandum on Franken, The Maze-Solving, Food-Getting, Learning Beast was based on Claude Shannon's earlier 1951 Maze solver using a sensing-finger rathjer than a magnetically controlled mouse.

Ivan and Bert Sutherland first started designing Franken in 1951. The prototype appears to have been built around 1953, if not earlier, according to a letter by Bert Sutherland to Ed Berkeley.. Improvements were was later suggested by Ivan Sutherland (see pdf below). 

It was finally handed over to Ed Berkeley in May, 1955.

[Note: Claude Shannon was later Ivan Sutherland's Thesis supervisor.]

See Claude Shannon's note on Maze construction considerations to Ed Berkeley here.

From Edmund C. Berkeley's SMALL ROBOTS — REPORT, 1956

5. Franken (named after Frankenstein) is a maze-solving robot. The maze consists of an aluminum board with 32 squares, around which partitions may be set up in any desired pattern by a member of the audience so as to make a maze. The searching and moving element which explores the maze is a wooden mouse or rat containing a permanent magnet. This is moved by four electromagnets themselves moved by machinery underneath the aluminum surface of the maze. The computing unit consists of some 60 relays; the memory consists of a magnetic drum (called Magdum; see below).

When Franken is completed, a member of the audience will be able to go up to Franken, mark one square with "Food", another square with "Latch One" and another square with "Latch Two". The machine will then be able to learn successively that "Food" is in the "Food" square, and that it has to go to "Latch Two" first and then to "Latch One" so as to "unlock" the "Food" and satisfy its hunger. The machine will also learn the maze, discovering the path to each of the three special squares after exploration. The machine will not be able to distinguish a shortest path from the path which it first finds, but it willbe able to eliminate all blind alleys. Data: 75% complete; finish, laboratory style; reliability, not known; maintenance, will be difficult; our costs so far, about $4,000.

6. Magdum (from "magnetic drum") is a small magnetic drum (materials cost about $50) and associated circuits including some 60 electronic tubes, constructed in order to be the memory for Franken. It has one timing channel and one information channel, and at present can store 128 numbers of 2 binary digits. A member of the audience can select any one of the 126 registers, enter a two-binary-digit number (one of 00, 01, 10, or 11) and find some time later that that number is still there, seeing the number in two neon tubes. This machine was constructed by Ivan Sutherland, age 16, for science fair competitions; and from it he won a $3,000 scholarship to Carnegie Institute of Technology. Data: 99% complete; finish, professional style; reliability, about 97%; maintenance, difficult; our costs so far, about $1,500.


Tags: , , , , , , ,