This experiment takes a standard electronic architecture, removes some of the dynamical constraints used to make conventional design tractable, and subjects the resulting dynamical electronic system to intrinsic hardware evolution. The result was the first evolved hardware control system for a real robot, reported in [26].
The EHW circuit was the on-board controller for the robot shown in
Fig. 3. This two-wheeled autonomous mobile robot has a
diameter of 46cm, a height of 63cm, and was required to display simple
wall-avoidance behaviour in an empty 2.9m 
4.2m rectangular arena. For
this scenario, the d.c. motors were not allowed to run in reverse and the
robot's only sensors were a pair of time-of-flight sonars rigidly mounted on
the robot, one pointing left and the other right. The sonars fire
simultaneously five times a second; when a sonar fires,
its output changes from
logic 0 to logic 1 and stays there until the first echo is sensed
at its transducer, at which time its output returns to 0.
Figure 3: The robot known as ``Mr Chips.''
Conventional electronic design would tackle the control problem along the following lines: For each sonar, a timer would measure the length of its output pulses -- and thus the time of flight of the sound -- giving an indication of the range to the nearest object on that side of the robot. These timers would provide binary-coded representations of the two times of flight to a central controller. The central controller would be a hardware implementation of a finite-state machine (FSM), with the next-state and output functions designed so that it computes a binary representation of the appropriate motor speed for each wheel. For each wheel, a pulse-width modulator would take the binary representation of motor speed from the central controller and vary the mark:space ratio of pulses sent to the motor accordingly.
It would be possible to evolve the central controller FSM as intrinsic EHW by
implementing the next-state and output functions as look-up tables held in an
off-the-shelf random access memory (RAM) chip.
The FSM
would then be specified by the bits held in the RAM, which could be
reconfigured under the control of each individual's genotype in turn. There
would be no benefit in evolving this architecture as hardware, however,
because the electronics is constrained to behave in accordance with the FSM
design abstraction: all of the signals are synchronised to a global clock to
give clean, deterministic state-transition behaviour as predicted by the
model. Consequently, the hardware would behave identically to a software
implementation of the same FSM.
What if the constraint of synchronisation of all signals is relaxed and placed under evolutionary control? Although superficially similar to the FSM implementation, the result (shown in Fig. 4), is a machine of a fundamentally different nature. Not only is the global clock frequency placed under genetic control, but the choice of whether each signal is synchronised (latched) by the clock or whether it is asynchronous is also genetically determined. These relaxations of temporal constraints -- constraints necessary for a designer's abstraction but not for intrinsic EHW -- endow the system with a rich range of potential dynamical behaviour, to the extent that the sonar echo pulses can be fed directly in, and the motors driven directly by the outputs, without any pre- or post-processing: no timers or pulse-width modulators. (The sonar firing cycle is asynchronous to the evolved clock).
Figure 4: The hardware implementation of the evolvable DSM. `G.L.' stands for
a bank of genetic latches: it is under genetic control whether each signal is
passed straight through asynchronously, or whether it is latched according to
the global clock of evolved frequency.
Let this new architecture be called a Dynamic State Machine (DSM). It is not a finite-state machine because a description of its state must include the temporal relationship between the asynchronous signals, which is an real-valued analogue quantity. In the conventionally designed control system there was a clear sensory/control/motor decomposition (timers/controller/pulse-width-modulators), communicating in atemporal binary representations which hid the real-time dynamics of the sensorimotor systems, and the environment linking them, from the central controller. Now, the evolving DSM is intimately coupled to the real-time dynamics of its sensorimotor environment, so that real-valued time can play an important rôle throughout the system. The evolving DSM can explore special-purpose tight sensorimotor couplings because the temporal signals can quickly flow through the system being influenced by, and in turn perturbing, the DSM on their way.
For the simple wall-avoidance behaviour, only two of the possible eight feedback paths seen in Fig. 4 were enabled. The resulting DSM can be viewed as the fully connected, recurrent, mixed synchronous/asynchronous logic network shown in Fig. 5, where the bits stored in the RAM give a look-up table implementing any pair of logic functions of four inputs. This continuous-time dynamical system cannot be simulated in software, because the effects of the asynchronous variables and their interaction with the clocked ones depend upon the characteristics of the hardware: meta-stability and glitches will be rife, and the behaviour will depend upon physical properties of the implementation, such as propagation delays and meta-stability constants. Similarly, a designer would only be able to work within a small subset of the possible DSM configurations -- the ones that are easier to analyse.
Figure 5: An alternative representation of the
evolvable Dynamic State Machine, as used in the experiment. Each
is a `Genetic Latch' (see previous
figure).
The genetic algorithm was the same as that described in
Section 15.2, with the contents of the RAM (only 32 bits
required for the machine with two feedback paths), the period of the clock (16
bits, giving a clock frequency from around 2Hz to several kHz) and the
clocked/unclocked condition of each signal all being directly encoded onto the
linear bit-string genotype. The population size was 30, probability of
crossover 0.7, and the mutation rate was set to be approximately 1 bit per
genotype. If the distance of the robot from the centre of the room in the x
and y directions at time t was 
and 
, then after an
evaluation for T seconds, the robot's fitness was a discrete approximation
to the integral:
and 
were chosen such that their respective Gaussian terms fell
from their maximum values of 1.0 (when the robot was at the centre of the
room) to a minimum of 0.1 when the robot was actually touching a wall in their
respective directions. The function s(t) has the value 1 when the robot is
stationary, otherwise it is 0: this term is to encourage the robot always to
keep moving. Each individual was evaluated for four trials of 30 seconds each,
starting with different positions and orientations. The worst of the four
scores was taken as the fitness [28]. For the final few
generations, the evaluations were extended to 90 seconds, to find controllers
that were not only good at moving away from walls, but also staying
away from them.
For convenience, evolution took place with the robot in a kind of `virtual reality.' The real evolving hardware controlled the real motors, but the wheels were just spinning in the air. The wheels' angular velocities were measured, and used by a real time simulation of the motor characteristics and robot dynamics to calculate how the robot would move. The sonar echo signals were then artificially synthesised and supplied in real time to the hardware DSM. Realistic levels of noise were included in the sensor and motor models, both of which were constructed by fitting curves to experimental measurements, including a probabilistic model for specular sonar reflections. The photograph of Fig. 3 was taken during an evolutionary run of this kind.
Fig. 6 shows the excellent performance which was attained after 35 generations, with a good transfer from the virtual environment to the real world. The robot is drawn to scale at its starting position, with its initial heading indicated by the arrow; thereafter only the trajectory of the centre of the robot is drawn. The bottom-right picture is a photograph of behaviour in the real world, taken by double-exposing a picture of the robot at its starting position, with a long exposure of a light fixed on top of the robot, moving in the darkened arena. If started repeatedly from the same position in the real world, the robot follows a different trajectory each time (occasionally very different), because of real-world noise. The robot displays the same qualitative range of behaviours in the virtual world, and the bottom pictures of Fig. 6 were deliberately chosen to illustrate this.
Figure 6: Wall avoidance in virtual reality and (bottom right) in the real
world, after 35 generations. The top pictures are of 90 seconds of behaviour,
the bottom ones of 60.
Figure 7: A representation of one of the wall-avoiding DSMs. Asynchronous
transitions are shown dotted, and synchronous transitions solid.
The transitions are labelled with (left, right) sonar input
combinations, and those causing no change of state are not shown. There is
more to the behaviour than is seen immediately in this state-transition
diagram, because it is not entirely a discrete-time system, and its dynamics
are tightly coupled to those of the sonars and the rest of the environment.
When it is remembered that this miniscule electronic circuit receives the raw echo signals from the sonars and directly drives the motors (one of which happens to be more powerful than the other), then this performance in surprisingly good. It is not possible for the DSM directly to drive the motors from the sonar inputs (in the manner of Braitenberg's `Vehicle 2' [29]), because the sonar pulses are too short to provide enough torque. Additionally, such naıve strategies would fail in the symmetrical situations seen at the top of Fig. 6. One of the evolved wall-avoiding DSMs was analysed (see below), and was found to be going from sonar echo signals to motor pulses using only 32 bits of RAM and 3 flip-flops (excluding clock generation): highly efficient use of hardware resources, made possible by the absence of design constraints.
Fig. 7 illustrates the state-transition behaviour of one of the wall avoiders. This particular individual used an evolved clock frequency of 9Hz (about twice the sonar pulse repetition rate). Both sonar inputs evolved to be asynchronous, and both motor outputs clocked, but the internal state variable that was clocked to become the left motor output was free-running (asynchronous), whereas that which became the right output was clocked. In the diagram, the dotted state transitions occur as soon as their input combination is present, but the solid transitions only happen when their input combinations are present at the same time as a rising clock edge. Since both motor outputs are synchronous, the state can be thought of as being sampled by the clock to become the motor outputs. This state-transition representation is misleadingly simple in appearance, because when this DSM is coupled to the input waveforms from the sonars and its environment, its dynamics are subtle, and the strategy being used is not at all obvious. It is possible to convince oneself that the diagram is consistent with the behaviour, but it would have been very difficult to predict the behaviour from the diagram, because of the rich feedback through the environment and sensorimotor systems on which this machine seems to rely. The behaviour even involves a stochastic component, arising from the probabilities of the asynchronous echo inputs being present in certain combinations at the clocking instant, and the probability of the machine being in a certain state at that same instant (remember that one of the feedback loops is unclocked).
Even this small system is non-trivial, and performs a difficult task with
minimal resources, by means of its rich dynamics and exploitation of the real
hardware. After relaxing the temporal constraints necessary to support the
designer's finite-state model, a tiny amount of hardware has been able to
display rather surprising abilities. FPGAs are undoubtedly
very much more powerful than the DSM. It is left to the reader to speculate on
the potential capabilities of an evolvable chip containing many hundreds of
logic gates, bearing in mind the power released by unconstrained evolution
from the equivalent of only two gates in the DSM described above.