CAOS Group. IDI, NTNU
Evolvable Hardware
Adaptive and Fault Tolerant Hardware

If a design which meets specified goals is created and the evolution process is designed to be triggered by changes in the surrounding environment so as to restart evolution, then a flexible design may be found i.e. an adaptive design. Adaption to hardware failure may be found today but mainly in a more traditional sense where adaptivity is built into the design at design time. That is, failure cases are identified and adaption to these specific failures is built into the design. Research into adaptive machines takes a slightly different approach in that adaption to failure may be learned. These failures may be due to external influences, for example changes in the environment, requiring an adaptive hardware solution or in the form of internal influences i.e. circuit failures which require fault tolerant hardware solutions.

In evolvable hardware, the evaluation of how well the proposed design solves the specified task is done by fitness evaluation. Exploration of a new design proposal can be started up when the current design no longer solves its task satisfactory. If the evolution process is on the same chip or on a local microprocessor, adaption does not need to be decided at design time but the required change in the circuit is free to evolve dynamically with changing external factors.

Robustness is a key to reliable hardware. This may be achieved through various means of fault detection and repair or through fault tolerance. Our work focusses on the fault tolerance aspect and in particular a methodology termed messy gates.

Participants
 

Faculty
Pauline Haddow, Assoc. Professor, Department of Computer and Information Science, NTNU

Students
Frode Eskelund, PhD student, Department of Computer and Information Science, NTNU
Morten Hartmann, PhD student, Department of Computer and Information Science, NTNU

[top]

Current Projects

        Messy Gates

The messy gate concept is based on non-perfect digital gates. That is the gates may operate outwith their digital thresholds, their non-perfect digital outputs being allowed to propogate through a circuit. Robust circuits, which not only tolerate this non-perfect functionality but infact exploit the messyness, are achieved through the help of evolution techniques. As such, evolution is used to evolve architectures for circuits using messy gates which are tolerant to a given level of both gate failures and noise. 

 
Adaptivity

Digital Filtering
One important feature of signal processing is coping with noise. In a non-adaptive filter, characteristics of the filter may be refined to remove noise. One method of achieving this is to use evolution to decide the filter characteristics. However, if the noise level is sufficient or the input signal is not of the required type for the output signal required, then a satisfactory output signal may not be achievable. To be able to achieve the required output signal for a wide range of input signals and noise, it is desirable to be able to adjust both the characteristics and the type of the filter. In this way the resulting filter may be said to be an adaptive filter.

We have implemented an on-chip solution for an adaptive digital filter using our Complete Hardware Evolution method i.e. an on.chip evolution solution.

This work highlighted a challenge within evolvable hardware for adaptive designs and that is to find efficient ways in which sufficient genetic material will be available to the evolution process. This problem appears when the evolution process is automatically restarted so as to adapt to a change in the environment. Our current solution to this problem involves a simple introduction of random individuals to the population when evolution restarts. These individuals are individuals stored from the randomly generated first population. Current work in this area involves consideration of other solutions to this problem.
 

Robotics

A robot controller is a sufficiently complex design to benefit from an evolutionary approach. In our approach,  the
evolution process and the robot controller itself are implemented on a single FPGA chip i.e. Complete Hardware Evolution. One of the advantages of a single chip implementation is the close proximity of the evolution process to the evolving design --- in this case a robot controller.

In the current work we consider fault tolerance, studying the controller's adaptivity to failure with respect to one of the robot's components --- a motor. The experiments are conducted in a real environment.  That is, each individual of the evolution process is
tested out in hardware while the robot is physically moving around it's environment.
 

Relevant Publications
 
       "Achieving Complex, Reliable Distributed Circuits"
       by Pauline C Haddow and Morten Hartmann, submitted to NIK 2002

        "Evolving Robust Digital Designs"
         by Morten Hartmann, Pauline C. Haddow and Frode Eskelund to appear in EH'02

         "Evolving Fault Tolerance on an Unreliable Technology Platform"
         by Morten Hartmann, Frode Eskelund, Pauline C. Haddow and Julian F. Miller to appear in GECCO'02

         "Untidy Evolution: Evolving Messy Gates for Fault Tolerance", abstract,  postscript, pdf
          by Julian F. Miller and Morten Hartmann, 4th International Conference on Evolvable Systems:
          From Biology to Hardware,  ICES2001, 14-25

         "From Here to There: Future Robust EHW Technologies for Large Digital Designs", abstract, postscript, pdf
          by Pauline C Haddow and Piet van Remortel, The Third NASA/DoD Workshop on Evolvable
          Hardware, EH 2001, pp 232-239

          "Evolving Messy Gates for Fault Tolerance: some Preliminary Findings", abstract,postscript, pdf
          by Julian F. Miller and Morten Hartmann, The Third NASA/DoD Workshop on Evolvable Hardware,  EH'01, 116-123

"An Evolvable Hardware FPGA for Adaptive Hardware", abstract, postscript
by Pauline Haddow and Gunnar Tufte, CEC'00, pp 553-560

"Evolving an Adaptive Digital Filter",abstract, postscript
by Gunnar Tufte and Pauline Haddow, EH'00, pp 143-150

"Evolving a Robot Controller in Hardware", abstract, postscript
by Pauline Haddow and Gunnar Tufte, NIK'99, pp 141-150