NOTES
from
Evolutionary Robotics:
The
Biology, Intelligence, and Technology of Self Organization
Chapter 1:
The role of self-organization for the synthesis and the understanding of behavioral
systems
- automatic creation of autonomous robots.
- inspired by the darwinian principle of selective reproduction of fittest.
- developing its own skills, without human intervention
versus Behaviored Based Robots
- global behavior of the robot emerges from interaction between
basic behaviors and environment. behaviors are implemented in
seperate subparts of control system, and there must be a mechanism to
detemine the priority of the behavior. 1- competitive basis 2-
cooperative basis.
- different from evalutionary robotics, desired global behavior is
tried to be obtained in the individual level, by breaking down into
a set of behavior manually. like building maps and obstacle avoidance
may be seperated in 2 different behaviors.
versus Robot Learning
- a control system can be trained using incomplete data and then
allowed to rely on its ability to generalize the acquired knowledge
to novel circumstances.
- different learning algorithms may be used in robot learning
(reinforcement)
- it differs from robot learning in 2 ways:
1- amount of supervision is lower
2- the evolutionary principle does not introduce any constraint in
principle on what can be pat of the self-organization process.
Incremental Evaluation
- for complex tasks, ll individuals in the first generations are
scored with the same null value, and as a consequence the selection
process cannot operate. bootstrap problem. one possible solution is to
start evalutionary process with a simplified version of the task and
progessively increase its comlexity by modifying the selection
criteria. .... **** for clustering problem...
Competing Species
- the computing populations might reciprocally drive one another
to increasing levels of complexity by producing an evolutionary "arms
race". Prey and predator is a good example for this alternative approach
to bootstrap problem...pg 15.
- at a high level of description , what can be obtained with evolution and
learning can also be obtained with evolution alone.At lower level of description,
they are organized in different ways.
- My problem, in determining motor actuators: the argument can beb
used, in Evolutaionary robotics, pg 12:
In particular, it is hard to design systems that exploit sensory-motor
coordination. For agents which interact with and external environment,
in fact, each motor action has two different effects: (a) it
partially determines how well the agent performs with respect to a
given task (b) it partially determines the next sensory patternthat
the agent should perform will receave from the environment.........
Chapter 2: Evolutionary and Neural Techniques
- evolutionary systems is based on the evalutionary techniques for
developong robotic systems.
- artificial evolution of robotic control systems are applied to 3
types of structures:
1- neural controllers
2- parameters of predefined control programs
3- computer porgrams itself
Genetic Algorithms:
- a genetic algorithm operates on a polulation of artificial
chromosomes by selectively reproducing the chromosomes of
individuals with higer performance and applying random changes.
- genotype-> artificial chromosome is a string that encodes the
characteristics of an individual(phenotype).
- the fitness function is a performance criterion that evaluates
the performance of each individual phenotype.
- the basic cycle consists of : 1- selective reproduction, 2-
cross-over, 3- mutation
- selective reproduction consists of making copis of the best
individuals in the population. (which have higher fitness values)
- Genetic Drift:genetic drift refers to the fact that
genetic traits can reach fixation in a population even if thay do
not provide any adaptive advantage.
- the simple selection may break down for
1- all individuals may obtains same fitness value. -> genetic
drift
2- when one or two individuals have much higher fitness values
- among lots, one of the alternatives is, tournament based
selection, where an offspring is the result of fitness values
tournament between 2 randomly selected individuals. randomly, one is
selected and reproduced, then inserted back to the population. But it
is really useful to preserve the best individual for the next
generation. this strategy, known as elitisim, ensures that, the best
solution found so far is not lost and usually generates more gradual
improvements of population fitness.
- After selection, offsprings are randomlay paired, crossed over
and mutated. differen types of cross-overs. Mutation is applied with a
given probability to each location of chromosome.
- Distributed Genetic Algorithms: can be used to allow
occurance of subpopulations, exploring different solutions for
fitness value and preventing a premature convergence of the
population on a local minima.
- in general mutations have o more important role when compared
with cross-over operation.
- artificial evolution of autonomous systems are differ from
genetic algorithms in some ways:
- it is difficult to establish a priori what abilities and
achivements are necessary to abtain a higher fitness.
- it is important to mention that a detailed fitness function and
agent-environment interaction are 2 different notions in the sense of
emergency.
- Species Adaptation Genetic Algorithms: a form of artificial
evolution characterized by variable length genotypes and a fairly
genetically converged population that moves in genetic space through
gradual mutations rather than by the effect of cross-over.
- Neutral Networks: the fitness landscape as a surface of
peaks and valleys on which evalution performs hillclimbing driven by
selective reproduction may not be a faithful representation of
natural evolution. There is now biological evidence that "neutal
evolution", that is random changes in the genotype that fo not affect
fitness values, can move the population in genotype space, possibly
taking it to areas with higher fitness values.
Artificial Neural Networks:
- An artificial neural network is a collection of units connected by weighted
links used to transmit signals.
- In some systems a theshold is included in the outputs function.
The threshold is an activity level beyond which a neuron becaomes active.
- Commonly used function are "the step function", "the linear
function", and "the sigmoid function".
- In the case of the continuos output function, the threshold is
mathematically equivalent to the weight of an additional incoming
connection from a unit constant value.This weight is called somtimes
"bias" and its input unit is called the "bias unit".
- There are 2 large families for architectures:
1- feedforward: signal travel from input units to output units.
2- recurrent architectures: there may be feedback connections from
neuron in the upper layer or in the same layer...
- Neural networks can learn a mapping automatically frinding the
appropriate set of connection weights.2 broad types of learning:
1- supervised learning: synaptic strengths are modified using the
error between desired output and the output given by the network for a
given input pattern. Reinforcement learning...
2- unsupervised learning: the network updates the weights on the
basis of the input patterns only? Here the learning rule and the
architecture chosen to determine how the network self-organizes the
behavior.
- in order to prevent wide oscillations, a small rate known as
learning rate of the modification is added to the previos weights.
- Learning Techniques:
- Hebbian learning.
- Supervised error based learning.for one layer: delta rule.
- Reinforcement Learning.It includes a class of algorithms for the
situations which are "coarse" and "sparse". with "coarse",
reinforcement must not provide much information. with "sparse",
reinforcement may not always available.
- Learning in recurrent networks.In some cases, such as in time series prediction,
it is important to detect time dependent fetatures in the sequence of input
patterns.
Evolving Neural Networks:
- while evolving the neurals, one problem may be, same behavior can be obtained
by different (for example inverted hidden units) genotype and weights. This
may result in the formation of 2 peaks in genotype space for fitness value.
This problem can be come overed by giving less importance and probability
to cross-overs.
- first to determine initial weights, evolution may be used, and
then supervised is used with this initial weighted network.
Genetic Programming:
- In this approach, we directly evolve a computer program from a set of predefined
terminals and functions in a tree structure. Cross-overs and mutations take
place for the branches of genotypes which are encoded as trees, in the large
population of programs.
Chapter 3: How to evolve robots
- Khepea concept: an integrated methodology based on hardware and software
originally developed in order to investigate adaptive and evolutionary algorithms
in robotic
- while real time simulations may speed up the operation, when it does not
pay attention to some small details, it may be useless in real robots:
1- you may try to solve problems that will not come up in the real world
with the loss of very few details
2- differences of simulated and real sensing/actuating may become a real
problem, and evolved robot behaviors may be simply useless in these conditions,
it is hard to simulate the real dynamics of the real.
- extracting the evolved neural network from the robot and studying it in
isolatio often tells little about the behavior of the robot.
- intoduction of noise i nall levels of sensing and actuating may
reduce the drop in performance observed when individuals are
transfered from simulated environment to real world. This is caused by
the fact that in real robots physical sensors deliver uncertain values
and commands to actuators have uncertain effects. (pg 60)
- fitness functions for autonomous robots usally include variables
and constraints that rate the performance with respect to the expected
behavior, but these variables and constraints are difficult to choose
because the behavior evolved by the robot is not fully known in
advance.
- Variables that objectively measure the fitness of a fully
functional behavior may be incapable of rating the primordial
appereances of that behavior in earl stages of evolution.
- the fitness function plays a major role in evolving th system.
- Fitness space is proposed as an objective framework for
describing and comparing varios fitness functions for autonomous
systems. This is a 3 dimensional space:
1- the dimension functional-behavioral. for example
functional is computing the oscillations on the wheel while behavioral
views and grades as the ditance that a robot move.
2- the dimension explicit-implicit defines the amount of
variables and constraints included in the function.
3- the dimension of external-internal indicates whether
variablesand constraints included in the fitness function are computed
using information available to the evolving agent.
- "subjective fitness": is the name used for the case where human observers
rate the performance of evolving individuals by visual inspection.
Chapter 4: Evolution of Simple Navigation
- Braitenberg's vehicle are conceptual robots whose wheels are directly linked
to the sensors through weighted connections very similar to the writing neural
networks. If connection is positive (excitatory), the rotation speed of the
wheel is propotional to the activation sensor of the sensor. Instead, if the
connection is negative (inhibitory), the rotation speed of the wheel is inversely
propotional to the sensor activation, possibly reversing its direction of
rotation.
- Artificial evolution can thus automatically generate a control system competitive
with hand designed solution without requiring as many assumptions and knowledge
about robot and the environment. It is the result of the comparing Bratenberg's
vehicle and evolved individual. Evolved solutions emerge from the interaction
with the physics of the environment in ways that are difficult to analyze
a priori, but are important for the good functioning of the robot.
- Although in fitness function, speed of same direction wheels is very important,
meaning when speed of th robot is increased its fitness wil increase; the
speed of the robot does not exceed to some value, does not approach the maximum
speed. This is because the charactristic of robot where it is evoved in. If
it was not a maze but a very large arena without any obstacle it would speed
up to the maximum speed. One other reason it, sensor and motors updated in
some time, it adjust itself not to crash into. As a result, evolved individuals
have adapted their behavior to te physical chracteristics of their own sensory
system and of the environment where they operate.
- It is very imporant all the properties of the environment in which you evolved
the robot, it has a direct affect on the behaviors of the robot.
- When the selection criterion changes (either because of the environment
or the fitness function change), some individuals that were not among the
best may be selected for reproduction and pull the population towards a new
area of the genetic space. The concept of adaptation as displacement of a
partially converged population in genetic space has been first proposed by
Harvey(1992b,1993) as a powerful strategy for incremental open ended evolution
and is behind the experiment on visually guided navigation described above.
Chapter 5:
Power and Limits of Reactive Intelligence
- Within the traditional Artificial Intelligence approach, in fact, there
is a tendency to view internal representations as explicit representations
of external world, while those who emrace the embodied and situated approach
tend to view the internal representations as partial models of the world which
include only those aspects that are necessary to allow agents to achieve their
goal.(Brooks), pg93
- Perceptual Aliasing Problem: refers to the situation wherein two ro more
objects generate the same sensory pattern, but require different responses.ps94
Chapter 9:
Encoding, Mapping and Development
- Genotype: what is inherited from parents
- Phenotype: complete individual, interaction with environment, driven
by instructions specified by the genotype.
- Genotype-to-phenotype encoding importance.
- Darwinian process may not be effective for computer programs. For adaptation
to occur, systems should possess evolvability.
- Evolvability: The ability of random variations
to sometimes produce improvement. It is directly lead by representation problem
(mapping).
- Mapping is organized:
- In nature, mapping is organized to ensure evolvability.
- In artificial, mapping rules are decided arbitrarily. not under genetic
control. THIS CHAPTER DEALS WITH THIS PROBLEM.
- Main goal of this chapter and the models is to identify a set of general
mechanisms that might capture some key aspects of development in natural organisms
and, consequently, might enhance the adaptive power of artificial evolution.
Genetic encodings
- In direct encoding schemes, there is one-to-one correspondence between genes
and the phenotypical chaacters subjected to the evolutionary process. Problems:
- Scalability : Space inreased exponentially with the increment of the
number of phenotypical characters.
- Impossibility or difficulty of encoding repeated structures in a compact
way.
- A good genetic encoding requires,
- expressive power: The possibility to encode many different
characteristics such as
- the architecture of the controller,
- the morphology of the robot,
- the rules that control the plasticity of the indicvidual,
- and the rules that determine the genotype-to-phenotype process itself.
- compactness : mappings where the length of the genotype only
weakly reflects the complexity of the corresponding phenotype.
- A mechanism may be the usage of varying length genotypes
- evolvability: the ability to produce improvements through the
application of genetic operators., which depends on
- the shape of the fitness surface,
- the genetic operators,
- and genotype-to-phenotype mapping
- An aspect that negatively affects evolution is pleiotropy.
- Pleiotropy: the fact that a single gene
can affect several different phenotypical characters.
- A good mapping therefore, should reduce pleiotropic effects among characters
serving different adaptive functions. Independent functions, in other words,
should be encoded as independently as possible so that improvements of each
function can be realized with minimal interference to other structures serving
other functions.
- A good genotype-to-phenotype mapping should allow the emergence of modular
organization. Important for re-using...
Growing methods
- Instead of encoding the entire phenotypical structure in the genotype, one
may encode growing instructions. The growing process occurs during individual's
lifetime. During the growing process, whe a growing axonal branch of a particular
neuron reaches another neuron,, a connection between neurons is established.
- In the experiments, both the synaptic weights and the neural architecture
are evolved. Moreover, some aspects of the sensory-motor system of evolving
individuals are under genetic control, such as the number and the type of
sensory-motor neurons.
Cellular encodings