The Experiment

The circuit to be evolved was the onboard controller for the robot shown in Fig. 4 [37]. This two-wheeled autonomous mobile robot has a diameter of 46cm, a height of 63cm, and was required to display simple wall-avoiding/room-centering behaviour in an empty 2.9m$\times$4.2m rectangular arena. For this scenario, the dc 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, returning to 0 when the first echo is sensed at its transducer.

Figure 4: 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 by implementing the next-state and output functions as look-up tables held in an off-the-shelf random access memory (RAM) chip; this is the well-known `Direct Addressed ROM' implementation of an FSM [38]. 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. Such evolution would still be subject to the constraints of digital design: all of the signals are synchronised to a global clock to give clean, deterministic state-transition behaviour as predicted by an abstracted Boolean model.

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 (Fig. 5), is a machine of a different nature. Not only is the global clock frequency placed under evolutionary control, but the choice of whether each signal is synchronised (latched) by the clock or whether it is asynchronous (directly passed through as an analogue voltage) is also determined by evolution. These relaxations of temporal constraints -- constraints necessary for a designer's abstraction but not for unconstrained evolution -- offer a rich range of potential dynamical behaviour to the system, 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 5: The hardware implementation of the evolvable DSM robot controller. `Optional latches' (O.L.) control whether each signal is passed straight through asynchronously as an analogue voltage, or whether its digital value is latched according to the global clock of evolved frequency. Each optional latch was implemented using an analogue switch chip able to bypass a clocked latch. A full circuit diagram is given in [39].

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 a 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 role 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 the outer two of the eight feedback paths seen in Fig. 5 were enabled, feeding the RAM chip's two least-significant data bits back to its two least-significant address inputs. The resulting DSM can be viewed as the fully connected, recurrent, mixed synchronous/asynchronous logic network shown in Fig. 6, 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 could not be simulated in software easily, because the effects of the asynchronous variables and their interaction with the clocked ones depend upon the characteristics of the hardware: metastability [40,41] and glitches will be rife, and the behaviour will depend upon physical (analogue) properties of the implementation, such as propagation delays, metastability constants, and the behaviour of the RAM chip when connected in this unusual way. 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: An alternative representation of the evolvable Dynamic State Machine, as used in the experiment. Each file=gl.eps,width=0.7cm is an `optional latch' (see previous figure).

A simple GA was used, with a linear bit-string genotype, point-mutations, single-point crossover, linear rank-based selection, and elitism [42]. The contents of the RAM (only 32 bits required for the machine with two feedback paths), the period of the clock (16 bits in a Gray code, giving a clock frequency from around 2Hz to several kHz) and the clocked/unclocked condition of each signal (1 bit per signal) were directly represented as contiguous segments of the genotype. The population size was 30, probability of crossover 0.7 per offspring, and the bit-wise mutation probability was set such that the expected number of mutations per offspring was one [43].

If the distance of the robot from the centre of the arena in the $x$ and $y$ directions at time $t$ was $c_{x}(t)$ and $c_{y}(t)$, then after an evaluation for $T$ seconds, the robot's fitness was a discrete approximation to the integral:

$$\mbox{fitness} = \frac{1}{T} \int_{0}^{T} \left( e^{-k_{x}c_{x}(t)^{2}} + e^{-k_{y}c_{y}(t)^{2}} - s(t) \right) \mbox{d$t$}$$ (1)

$k_{x}$ and $k_{y}$ 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 arena) to a minimum of 0.1 when the robot was touching a wall in their respective directions. The function $s(t)$ encourages continual movement, having the value 0 when the robot is moving, but 1 otherwise. 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 [44]. 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 reconfigurable DSM circuit controlled the real motors, but the wheels were just spinning in the air. The photograph of Fig. 4 was taken during an actual evolutionary run of this kind. The wheels' angular velocities were measured, and used by a real-time simulation of the motor characteristics to calculate how the robot would move if on the ground. 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 stochastic model for specular sonar reflections. Full details are given in [39]. The GA and the virtual environment simulation were performed by a laptop PC onboard the robot, and a pair of microcontrollers synthesised the sonar and clock waveforms. The real DSM hardware connected to the real motors was used at all times. For operation in the real world, the real sonars were simply connected in place of the simulated ones, and the robot placed on the ground.

Fig. 7 shows the excellent performance 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 (1) a picture of the robot at its starting position, with (2) 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. 7 were deliberately chosen to illustrate this.

Figure 7: 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 seconds.

Given 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), the performance is 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' [45]), because the sonar pulses are too short to provide enough torque. Additionally, such naive strategies would fail in the symmetrical situations seen at the top of Fig. 7. One of the evolved wall-avoiding DSMs was analysed (below), and 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.