Applying Evolutionary Engineering to the Design of Sensory-Motor Control Systems
for Non-holonomic Autonomous
By
Shahab Kalantar
Supervised
by
Dr. M.H. Zand
For the
partial fulfillment of the degree of Master of Science in
Electrical and Computer Engineering (Machine
Intelligence and Robotics)
Machine Intelligence and Robotics Group
Department of Electrical and Computer
Engineering
Faculty of Engineering
Abstract
To fulfill the need to develop robust control systems
for robots that need to operate autonomously in unknown and changing environments,
novel approaches have recently emerged, most notably behavior-based robotics
relying on reactive sensory-motor control systems, promising to overcome the
complexity of the magnitude encountered in mobile robotics. Unfortunately,
designing such systems is far from straightforward.
Several researchers have attempted to bypass the
difficulties of hand-coding these architectures, by using the so-called
evolutionary robotics approach. According to this approach, a robot’s
controller is progressively adapted to the specific environment it is
confronted with, through an artificial selection process that eliminates
ill-behaving individuals in a population while favoring the reproduction of
better-adapted competitors. This requires some form of evolutionary algorithm.
The overall aim of the research project reported
herein is to create an animat capable of evolving,
growing and learning along the phylogenic, ontogenetic and epigenetic axes.
This project was divided into three phases, the first of which was successfully
completed and is reported herein.
1.
Kinematical modeling of mobile
robots was based on the concept of minimal equivalent mechanical designs for
non-holonomic wheeled robots, which has sufficient generality to include a
large number of currently available realizations.
2.
Due to unfeasibility of carrying
out the evolutionary processes, on the one hand, and to reduce the
computational complexity involved in any evolutionary process, sophisticated
simulation tools were designed and implemented. Every effort was made to bring
the simulations as close to reality as possible. Modeling is based on polygons.
Besides geometric considerations, various computational processes (control,
dynamic and kinematical) are considered as well. New methods for detecting and
handling collisions are presented.
3.
Desirable behaviors (obstacle
avoidance, line tracking, wall following, and goal finding) are classified and
ad hoc reactive control architectures are designed for generating them. A
mathematical framework for representing behaviors is formulated. This framework
is based on the concept of elementary behaviours and behaviour learning as function approximation. Such a
framework is useful in many respects: quantizing the qualitative nature of behaviours, identification of evolved behaviours
and constituting components, Interpretation of control mechanisms, and
combining the basic blocks to achieve complex behaviours.
4.
Generic control systems
appropriate for realizing reactive behaviors were implemented.
5.
Many classes of evolutionary
algorithms were used in this research and their relative suitability assessed,
including genetic algorithms, evolution strategies, evolutionary programming
and population-based incremental learning.
6.
The EVO-ROB system was developed
to facilitate experimental research. It is composed of loosely coupled
components representing every aspect of each of the entities involved.
7.
Many experiments were conduced to
demonstrate the feasibility of this approach. Each experiment is uniquely
characterized by the robot, the evolutionary algorithm, the desired behaviour,
the control architecture used, the number of generations, the method of fitness
evaluation, population size, parameters of the algorithm, parameters of the
control system, the initial pose of the robot, the number of simulation steps,
the environment, the method of handling collisions, criteria for stopping the
evolution process, and finally fixed versus variable fitness function during
the process. The results of each experiment are interpreted and compared.
In many
cases the results from a number of runs were averaged. Many research reports
published previously were the result of just one run. This clearly showed that
many methods presented were not applicable in real situations.
8.
A hardware robot was designed,
specifically for ER experiments. This robot is equipped with an on-board
evolutionary module based on parallel GA.
9.
The pedagogical importance
of a simulation software package equipped with evolutionary modules together
with the accompanying hardware robot were discussed.
10.
Generalizability
and over-learning of the evolved robots were studied. Special stability criteria were designed to
facilitate the assessment of efficiency of individual robots.
11.
Providing guidelines for further
research in this area.
The robot Khepera was used
as a prototype for simulations.
Contents
1 Introduction
1.1.
Motivation
1.1.1.
Mobile Robotics
1.1.2.
Reactive Control Systems
1.1.3.
Autonomous Systems
1.1.4.
Sensory-Motor Control Systems
1.1.5.
Behaviour-Based Robotics
1.1.6.
Behaviour Emergence Phenomena
1.1.7.
Artificial Life
1.1.8.
Computation versus Cognition
1.1.9.
Artificial Evolution
1.1.10.
Evolvable Hardware
1.2.
Evolutionary Robotics
1.2.1.
The Robot
1.2.2.
The Control System
1.2.3.
The Environment
1.2.4.
The Evolutionary Algorithm
1.2.5.
Evolutionary Experiments
1.3.
Project Goals
1.3.1.
Modeling and Classification of
Wheeled
1.3.2.
Software Simulation
1.3.3.
Ethology Classification of
Behaviours
1.3.4.
Control Systems
1.3.5.
Evaluation of Evolutionary
Algorithms
1.3.6.
Studying Hardware Solutions
1.3.7.
Experimentation with a Real Robot
1.3.8.
Design and Construction of a
Special-Purpose Evolvable Robot
1.3.9.
Edutainment Robotics
1.3.10.
Experimental Study
2. Evolutionary Robotics
2.1.
Introduction
2.2.
Autonomous
2.3.
Coherence of
Robot-Control-Environment
2.4.
The Meaning of Autonomy
2.5.
Autonomous System Design
Methodologies
2.5.1.
Classical AI
2.5.2.
Neural Networks
2.5.3.
Subsumption
Architecture
2.5.4.
Potential Fields
2.5.5.
New Paradigms
2.6.
Evolutionary Algorithms
2.7.
Reactive Control
2.8.
Behaviour-Based Robotics
2.9.
Optimization and Adaptation
2.10.
Biologically-Motivated Systems
2.10.1.
The POE Model
2.10.2.
Phylogeny
2.10.3.
Ontogenesis
2.10.4.
Epigenesis
2.10.5.
Combining the Axes
2.11.
The Khepera
Robot
3. Modeling
3.1.
Introduction
3.1.1.
Manipulators
3.1.2.
Mobile Robots
3.1.3.
Legged Robots
3.1.4.
Jumping Robots
3.1.5.
Flying Robots
3.1.6.
Wheeled Robots
3.1.7.
Mixed-Locomotion Robots
3.2.
Anatomy of a
3.2.1.
Sensors
3.2.2.
Decision-Making Unit
3.2.3.
Controllers
3.2.4.
Actuators
3.2.5.
Locomotion Mechanisms
3.2.6.
Overall View
3.3.
Mathematical Framework
3.3.1.
Environment
3.3.2.
Sensors
3.3.3.
Perception and Decision Making
3.3.4.
Actuators
3.3.5.
Controllers
3.4.
Mechanical Models for Wheeled
3.4.1.
Model I
3.4.2.
Model II
3.4.3.
Model III
3.4.4.
Model IV
3.5.
Kinematics of
3.5.1.
Fundamental Concepts
3.5.2.
Non-Holonomic Systems
3.5.3.
Instantaneous Centre of Rotation
3.6.
Kinematical Modeling of a Wheeled
3.7.
Equivalent Minimal Kinematical
Models
3.7.1.
Model I
3.7.2.
Model II
3.7.3.
Model III
3.7.4.
Model IV
3.8.
Equivalence of Minimal Models
3.8.1.
Converting Model II to Model I
3.8.2. Converting
Model III to Model I
3.8.3.
Converting Model IV to Model I
3.8.4.
Other Methods
4. Simulating
4.1.
Introduction
4.2.
Simulation versus Real Robots
4.3.
Graphical Components for
Simulation
4.3.1.
Objects
4.3.2.
Convex Polygons
4.3.3.
Convex Closure
4.3.4.
Decomposing a Polygon into Convex
Polygons
4.3.5.
Intersection of Polygons
4.3.6.
Points Inside Polygons
4.3.7.
Collision of Polygons
4.3.8.
The Environment and its Components
4.3.9.
The Robot and its Components
4.4.
Simulating Computational Processes
4.4.1.
Dynamics and Control
4.4.2.
Kinematics
4.5.
Simulating Object Collisions
4.5.1.
t-Vectors
4.5.2.
Collision Detection (First Step)
4.5.3.
Collision Detection (Second Step)
4.5.4.
Observability using t-Vectors
4.5.5.
Using t-Vectors
for Collision Detection
4.5.6.
Handling Collisions
5.
Evolutionary Algorithms
5.1.
Introduction
5.2.
Mathematical Framework for
Evolutionary Algorithms
5.3.
Evolutionary Strategies
5.3.1.
Representation and Fitness
Evaluation
5.3.2.
Mutation
5.3.3.
Recombination
5.3.4.
Selection
5.3.5.
Standard Algorithm
5.4.
Evolutionary Programming
5.4.1.
Representation and Fitness
Evaluation
5.4.2.
Mutation
5.4.3.
Recombination
5.4.4.
Selection
5.4.5.
Standard Algorithm
5.5.
Population-Based Incremental
Learning
5.5.1.
Representation and Fitness
Evaluation
5.5.2.
Mutation
5.5.3.
Recombination
5.5.4.
Selection
5.5.5.
Standard Algorithm
5.6.
Genetic Algorithms
5.6.1.
Representation and Fitness
Evaluation
5.6.2.
Mutation
5.6.3.
Recombination
5.6.4.
Selection
5.6.5.
Standard Algorithm
6.
Behaviours
6.1.
Introduction
6.2.
Control Architectures and
Evaluation
6.3.
Gradual Fitness Computation
6.4.
A Mathematical Framework for the
Representation of Behaviours
6.5.
Behaviours and Internal Mechanisms
6.6.
Modeling the Interaction of the
Robot and the Environment
6.6.1.
The Environment
6.6.2.
The Robot
6.6.3.
Coupling
6.7.
Braitenburg Vehicles
6.7.1. Shadow Edge Detector
6.7.2. Paranoid
6.7.3. Obstacle Avoider
6.7.4. Light Seeker
6.7.5. Leader-Follower
6.7.6. Structures and Features
6.8.
Goal-Seeking Behaviour
6.9.
Wall-Following Behaviour
6.10.
Obstacle-Avoidance Behaviour
6.10.1. Braitenburg Architectures
6.11.
Line-Tracking Behaviour
6.11.1.
Sensor Topology
6.11.2.
Robot Diameters
6.11.3.
Line Widths
6.11.4.
Angled Sensors
6.11.5.
Symmetry
6.11.6.
Using Two Sensors
6.11.7.
Using Three Sensors
6.11.8.
More Sensors
6.11.9.
Logical Controller for Realizing
Line-Tracking Behaviour
7.
Control Architectures
7.1.
Introduction
7.2.
Braitenburg Architectures
7.3.
Radial-Basis Function Networks
7.4.
Logical Circuits
7.5.
Fuzzy Systems
7.6.
Function-Level Evolvable Hardware
7.7.
Adaptive Neuro-Fuzzy Inference
System
7.8.
Neural Networks
8.
Real Robots in Real World
8.1.
Introduction
8.2.
POE-Based Evolvable Robot
8.2.1.
Mechanical Design
8.2.2.
Other Components
8.2.3.
Connections Between Modules
8.3.
A Prototype Design for the
Experimental Robot
9.
Experiments
9.1.
Introduction
9.2.
Evolving Logic Circuits As Robot
Controllers
9.3.
Evolving Gate-Level Evolvable
Hardware
9.3.1.
The Robot and the Environment
9.3.2.
Reactive Scheme
9.3.3.
Implementing the Reactive Scheme
9.3.4.
Truth-Table Logic Controller
9.3.5.
Functional Controller
9.3.6.
Evolving the Functional Controller
9.3.7.
Comparing the Two Approaches
9.3.8.
The Genetic Algorithm
9.3.9.
Genetic Parameters
9.3.10.
Fitness Evaluation
9.3.11.
The Experiment
9.3.12.
Improving Robustness and
Generalization
9.4.
Evolving Function-Level Evolvable
Hardware
9.4.1.
Chromosomal Representation
9.4.2.
Reproduction and Mutation
9.4.3.
The Results of the Experiment
9.5.
Evolution Strategies and
Braitenburg Vehicles
9.5.1.
The Components of the Experiment
9.5.2.
The Results of the Experiment
9.5.3.
Analysis of Results
9.6.
Evolution Strategies and Receptive
Field Controllers
9.7.
Braitenburg Vehicles and Real
Genetic Algorithms
9.8.
Braitenburg Vehicles and
Population Based Incremental Learning
9.9.
Multi-layer Perceptrons and
Genetic Algorithms
9.10.
Line-Tracking and Genetic
Algorithms
9.10.1.
Control Architecture
9.10.2.
Sensor Configuration
9.10.3.
The Environment
9.10.4.
Coding Method
9.10.5.
Fitness Function
9.10.6.
Non-Symmetrical Systems
9.10.7.
Symmetrical Systems
9.10.8.
Optimal Sensor Configuration by
Evolution
9.10.9.
A Pre-Processing Algorithm for
Sensor Space Reduction
9.11.
Line-Tracking and Population Based
Incremental Learning
9.11.1.
Mathematical Description of the
Behaviour
9.11.2.
Stability Criteria
9.11.3.
Constrained Systems
9.11.4.
Non-Constrained Systems
9.11.5.
Optimal Sensor Configuration
9.11.6.
The Effects of Variations in
Parameters
9.12.
Evolving Fuzzy Systems for
Obstacle-Avoidance
9.13.
Comments on Generalizability of
Evolved Creatures
9.14.
Mixed Behaviours
10.
The EVO-ROB Systems
10.1.
Introduction and Motivation
10.2.
Inheritance Tree and Component
Interaction
10.3.
EVO-ROB Components
10.3.1.
Base Graphical Objects
10.3.2.
The Environment and its Components
10.3.3.
Evolutionary Algorithms
10.3.4.
Robots
10.3.5.
Robot Components
10.3.6.
Control Systems
10.3.7.
Fitness Evaluation
10.3.8.
Robot Simulator
11.
Conclusion
11.1.
A Review of What Has Been Done
11.2.
The Obtained Results
11.3.
Further Research
Appendices
Appendix
1. Representation Without
Knowledge
Appendix
2. The Real World Versus the
Virtual World
Appendix
3. Active Perception
Appendix
4. Artificial Life and Evolutionary Algorithms
Appendix
5. Artificial Life Neural Networks
Appendix
6. Evolvable Hardware
Appendix
7. Programmable Logic Devices
Appendix
8. Population Based Incremental Learning
Appendix
9. Continuous Real Genetic Algorithm
Appendix
10. Parallel Genetic Algorithm
Appendix
11. Hardware Issues in Evolutionary Robotics
Appendix
12. Animats and their Design
Methods
Appendix
13. Decentralized Adaptive Control
Appendix
14. Potential Field Controllers
Appendix
15. New Philosophies
Appendix
16. Geometric Model of Kinematics
Appendix
17. Structure of the Best RBF Evolved
Appendix
18. Evolving Adaptive Neuro-Fuzzy Inference Systems
Copyright © 1999, 2003, Shahab Kalantar. All rights reserved.
Created:
Last modified: