A thesis submitted to The University of Kent at Canterbury in the subject of Electronic Engineering for the degree of Doctor of Philosophy

November 2000

Click here to download a compressed PDF B&W version of the Thesis

Click here to see the Abstract

Click here to see the Acknowledgements

Click here to see the Publications arising from this work

Click here to see the Table of Contents

This work studies evolutionary computation applied to robotics. It reports comparative studies between different of embedding an evolutionary control circuit in a population of six autonomous mobile robots. The reviewed architectures are: evolvable hardware; dynamic state machine; condition-behaviour mapping; pulse stream neural systems; and the chosen one – RAM neural networks. This thesis describes the techniques that could be adapted from the literature, the novel techniques developed to allow the design of the hardware and software necessary to embedding the distributed evolutionary system, and the environments where the experiments were carried out in real time and in simulation. These experiments test the influence of different parameters, such as different mutation rates, partner selection, crossover, and reproduction strategies. This work produced a genetic system where the population exists in a real environment, where they exchange genetic material and reconfigure themselves as new individuals to form the next generations, providing the means of running genetic evolutions in a real physical platform.

This work proposes and implements a fully embedded distributed evolutionary system that is able to achieve collision free-navigation in a few hundreds of trials. Evolution can manipulate the morphology of the robot: the configuration of the sensors and the motor speed levels. This thesis presents the first experimental proofs of the embedded evolution concept applied to the evolution of the morphology and control circuit of a population of real robots in real time. It proposes the Predation strategy that not only can improve the performance of the system but also prevents the population from being stuck in local optimum. It is demonstrated that evolution can help in the traditional design of robotic platforms, since it can suggest the best features a robot should incorporate to perform specific tasks. Finally, this work provides understanding on the implementation of real evolutionary systems and inspiring insights that have potential of application in the areas of automation and cybernetics.

Many people supported and helped during the completion of this work, and now it is time to find the right words to thank all of them.

I would like to express my deep gratitude to my very kind friend and supervisor Dr. Keith Dimond for his guidance, advice, and encouragement during the whole period of this work.

I am sincerely thankful for the help and assistance provided by the members of staff in the Electronic Engineering Laboratory. In particular to Harvey who has generously supplied his deep and diverse pool of knowledge in 68HC11 design and technologies; and to Clive and Terry, for all the guidance in manufacturing the robots; to Mr. Dave Smith and Gill for being so friendly every time I showed up with a list of hundreds of components to be ordered.

My sincere thanks also to my friends and colleges from the Department of Statistics Mr. and Mrs. Zimmerman for the for the inspiration and endless explanations on to analyse my experimental data.

During the development of my Ph.D., three colleges really stand out and marked this period with a special shine. This kind of people you do not even need to thank, because they already know… I would like to express my deepest affection to Anne, Dimitrios, and Rick, for all the unconstrained help, productive discussions, and friendship that I hope will last far beyond this Ph.D.

I am also very grateful to the CNPq, the Brazilian council for research, for providing the opportunity to study at the University of Kent.

I would also like to thank all my friends in the Electronics Laboratory, especially Alex, Shanta, Fuadd, Osama, Hossam, Samuel, Elina, Julia, and William for providing support and a friendly environment. Particularly to Jose for not touching the electrostatic sensitive robots, and last, but by no means least, to Dr. NG for helping so promptly.

Finally, I would like to thank my family for giving me the initial encouragement and tools to pursue my ambitions. In particular, I wish to thank my wife, Liane who, being a scientist herself, has directly and indirectly contributed to my work. Without her loving support and encouragement over the years I could never have managed to get this work done.

• Simões, E.D.V.; Dimond, K.R. An Evolutionary Controller for Autonomous Multi-Robot Systems. In IEEE International Conference on Systems, Man and Cybernetics, Tokyo, Japan, October, 1999, 6p, CDROM Proceedings, 1999, Invited Paper.
• Simões, E.D.V.; Dimond, K.R. Embedding a distribute evolutionary system into a population of autonomous mobile robots. submitted to IEEE International Conference on Systems, Man and Cybernetics, October, 2001, Tuscon, USA. Deadline: February 25, 2001.
• Simões, E.D.V.; Dimond, K.R. Predation: an approach to improving the evolution of real robots with an embedded evolutionary controller. In preparation to be submitted to IEEE / RSJ International Conference on Intelligent Robots and Systems (IROS 2001), October 2001, Maui, Hawaii, USA, Deadline: March 1, 2001.
• Simões, E.D.V.; Dimond, K.R. Inheritance Selection: inheriting fitness values in an embedded evolutionary system. in preparation to be submitted to IEE Proceedings: Computers and Digital Techniques.

1 Introduction 1

1.1 Problem Delimitation 6

1.2 Objective 8

1.3 Thesis Organisation 10

2 Evolutionary Robotics 13

2.1 Evolutionary Computation 13

2.1.1 Genetic Algorithms 14

2.2 Evolutionary Robotic Systems 19

2.2.1 Issues on Using Simulators 21

2.2.2 Embedded Evolution 23

2.2.3 Encoding the Characteristics of the Robot 25

3 Robot Control Circuit 30

3.1 Embodying an Evolvable Control Circuit 30

3.2 Alternatives for the Controller Architecture 34

3.2.1 Evolvable Hardware 35

3.2.2 Dynamic State Machine 39

3.2.3 Condition-Behaviour Mapping 41

3.2.4 Pulse Stream Neural System 47

3.2.5 Boolean Neural Network 48

4 The Evolutionary System 54

4.1 Individual Control Strategy 55

4.1.1 The Navigation Control Circuit 58

4.2 Evolutionary Control System 65

4.2.1 Fitness Evaluation 69

4.2.2 Partner Selection 71

4.2.3 Crossover Strategy 73

4.3 System Specification 78

4.3.1 Overview 78

4.3.2 Introduction to the Robot Architecture 81

4.3.3 Computing System 86

4.3.4 Communication Module 88

4.3.5 Sensor Module 92

4.3.6 Motor Drive Module 95

4.3.7 Power Management 97

5 Robot Design 98

5.1 The Chassis Design 99

5.1.1 Organisation of the Robot 99

5.1.2 Shape and Size 99

5.2 Computing System 101

5.3 Motor Drive Circuit 106

5.4 Sensors Circuit 107

5.5 Communication Circuit 108

6 Preliminary Experiments 111

6.1 Environment Organisation 112

6.1.1 Data Monitoring 113

6.2 Experiment 1: The influence of the Lifetime 116

6.2.1 Experiment 1.1: the Simple Environment 121

6.2.2 Experiment 1.2: the Complex Environment 125

6.2.3 Discussion of the Experimental Results 129

6.3 Experiment 2: Evolving the Sensor Configuration 130

6.3.1 Discussion of the Experimental Results 139

6.4 Experiment 3: Evolving an Unstructured Controller 140

6.4.1 Experiment 3.1: Evolving with a Simple Fitness Function 147

6.4.2 Experiment 3.2: Evolving a Biasing Fitness Function 151

6.4.3 Experiment 3.3: Evolving a Strongly Biasing Function 154

6.4.4 Discussion of the Experimental Results 157

6.5 Experiment 4: Inheritance 157

6.5.1 Experiment 4.1: Inheritance and a Biasing Fitness Function 159

6.5.2 Discussion of the Experimental Results 164

7 Simulated Experiments 166

7.1 The Simulator 167

7.2 Experiment S1: Simulated Evolution 169

7.2.1 Discussion of the Experimental Results 175

7.3 Experiment S2: Asexual Reproduction 176

7.3.1 Discussion of the Experimental Results 180

7.4 Experiment S3: A Different Way to Evolve 181

7.4.1 Discussion of the Experimental Results 183

7.5 Experiment S4: Disabling Back Mutation 184

7.5.1 Discussion of the Experimental Results 186

7.6 Experiment S5: The Neural Network Controller 187

7.6.1 Discussion of the Experimental Results 190

7.7 Experiment S6: Predation 191

7.7.1 Discussion of the Experimental Results 194

8 Embedded Evolution 196

8.1 Evolving with a Black Box Controller 197

8.1.1 Discussion of the Experimental Results 204

8.2 Evolving with a Neural Network 206

8.2.1 Discussion of the Experimental Results 211

9 Conclusion 214

9.1 Conclusions Arising From the Experimental Results 215

9.2 Principal Achievements 221

9.3 Suggestions for Future Research 224