ICBV Project

Fall 2006

Evolving "elementary sight" strategies in predators

Via

Genetic programming

Submitted:

Lior Becker

ID: 052690849

Email:

Home page: http://www.cs.bgu.ac.il/~beckerli/

http://liorbecker.googlepages.com/


INDEX

Abstract 3

Introduction 4

Genetic Programming 5 - 9

Darwin's principles 5 - 6

Population 6

Individual 6

Cross over 7

Mutation 8

Fitness 8

Main algorithm 8 - 9

Predator strategy through GP

World simulator 10

Prey 10

Predator 11

Process of work 12

Results 13

Experiment 1, Static prey 14 - 15

Experiment 2, straight line prey 16 - 17

Experiment 3, circle prey 18 - 19

Experiment 4, random prey 20 - 21

Functions Analysis 22

Conclusions 23

Future Work 24

References 24


Abstract

Teaching a predator, using Genetic programming, to hunt different kinds of prey using his "elementary sight", that is 15 photo receptors.


Introduction

General idea:

In this work I will imitate a predator using Genetic programming (J.koza style).

The predator will have an underdeveloped eye (15 photo receptors only), which will give him a feedback from his surrounding area.

I will emulate evolution of the predator's "brain function" as a product of his success or failure in catching his prey.

This means the way that the creature can process and use his sight to gain the maximum profit.

The creature will be tested in means of the most basic need, eating!!

He will need to follow a variety of prey targets and capture them in the shortest time.

Motivation:

The motivation is to do a small research on the development of a predator "strategy" based on his "elementary sight".

I found some related article (Haynes, Sen: Evolving behavioral strategies in predators and prey (1996)) that tries to solve the same problem but they don't take the VISION as part of their work. So I decided to expand the subject to deal also with vision and sight.

Goals:

  1. Witness the evolution of the predator "strategy" (brain function).
  2. Imitate the evolution of the parts in the brain that handle the visual informal interpretation.
  3. Try to understand the development stages in the strategy (brain function)
  4. Try to analyze the usage of the photoreceptors as part of the brain function.
  5. Test if the development of sight strategy is a complex process or can be emulated in a computer.


Genetic Programming highlights

Genetic Programming (GP) is a bio-inspired programming, which absorbs its main principles from nature and biology.

The method of Genetic Programming (GP) I will use in the project is J. Koza's Style. In the next pages I will give a brief description of GP. See references for more information.

Most of the basic ideas are inspired by Charles Darwin’s principles, and his book "THE ORIGIN OF SPECIES".

Figure 1, 2: Charles Darwin, book and picture.

Darwin's theory is based on key observations and inferences drawn from them:

  1. Species have great fertility. They make more offsprings than can grow to adulthood.
  2. Populations remain roughly the same size, with modest fluctuations.
  3. Food resources are limited, but are relatively stable over time.
  4. An implicit struggle for survival ensues.
  5. In sexually reproducing species, generally no two individuals are identical.
  6. Some of these variations directly impact the ability of an individual to survive in a given environment.
  7. Much of this variation is inheritable.
  8. Individuals less suited to the environment are less likely to survive and less likely to reproduce, while individuals more suited to the environment are more likely to survive and more likely to reproduce.
  9. The individuals that survive are most likely to leave their inheritable traits to future generations.
  10. This slowly effected process results in populations that adapt to the environment over time, and ultimately, after interminable generations, the creations of new varieties, and ultimately, new species.


In brief there are four main principles:

·  Competition: a species lives in a given environment.

·  Variation: Each individual has unique attributes, which are being passed to his offspring's.

·  Overproduction: more individuals are born than can live.

·  Survival of the fittest: This leads to a struggle for existence.

According to these principles, the individuals whose attributes fit the environment will be able to reproduce; their offsprings will reflect some of these attributes, hence will be able to fit to the environment. On the long run, the species population will consist of individuals that are fitted to the environment.

Genetic Programming (GP) model is equivalent to Darwin's theory:

·  An individual is a candidate solution to the problem we wish to solve.

·  The population is a set of individuals.

·  We will assign fitness to each individual, based on his solution to the problem.

·  Individuals with high fitness will have high reproducing probability.

Population

In Genetic Programming (GP), population is a close set of in individuals.

It fulfills the Darwin's principles, since the population size remains the same and due to competition only the fittest will survive.

Individuals (Gene)

In Genetic Programming (GP), each individual is a computer program (function).

The representation I use (Koza's style) is a Scheme-like program, which can be written as a tree (Like AST in compilation).

The tree contains Function sets (nodes) and terminals sets (leaves).

The Function and terminal sets construct the tree.

For Example:

Function set {IF, >}.

Terminal set {1, 2, 3, 4, 10, TIME}.

Figure 3: Individual Tree Example.


Crossover (Reproduction)

In Genetic Programming (GP), in order to evolve we will reproduce two individuals in to two new offspring's.

The two new born individuals are (like in the real world) a recombination of their parents' DNA - in our case Trees.

The crossover is a simple routine (demonstrated below):

1) Taking two parents (a, b);

2) In each parent tree choosing a point (cross over point);

3) Replacing both of the sub trees;

4) The two new individuals (c, d) will continue to the next generation.

Figure 4: crossover.


Mutation

In nature we have an event that is called "mutation". It is a random change in the DNA of a creator.

In Genetic Programming (GP), we imitate this event by a simple routine (demonstrated below) of taking one individual, choosing a random node in this tree (DNA) cutting the sub tree and growing a sub tree instead.

Figure 5: mutation.

Fitness Assignment

Fitness is a character that measures the "suitability" of an individual to the environment.

We will assign fitness to an individual by evaluating the individual Tree (Function) in the environment.

After evaluating the individual we can now rank its "suitability" to the environment compared to all the other individuals.

Generation

In Genetic Programming (GP), Like in nature we have generations.

Passing from one generation to another is via reproduction.

Genetic Programming evolution:

First we need to define the Function and terminal set.

Process of work:

  1. Generate the initial population G0.
  2. Evaluate the fitness of each individual in the current generation.
  3. Create the next generation GN+1:
  4. Choose two random individuals based on their fitness rank.
  5. With the probability PC, apply the crossover operator on the two individuals, resulting in two child individuals. Pass these individuals to the next generation GN+1. Otherwise, pass the two original individuals to the next generation GN+1.
  6. With the probability PM, apply the mutation operator on the selected individuals.
  7. Repeat until GN+1 is full.
  8. Until (stop condition is done) Go back to step B.

Stop condition: when a fairly good individual is found, or after a predefined number of generations.

Figure 6: Illustrate the GP Koza's style.


Predator strategy through GP

World simulator – Environment

As we can recall we are trying to evolve a predator strategy.

In order to evolve the strategy, the prey and the predator must exist in simulated world.

I will simulate the world:

·  2D world.

·  100*100 matrix.

·  The prey and the predator can be at any real coordinate (X, Y) in R^2, {0 < X, Y < 100}.

We can compare this world to fish aquarium.

Prey

In our world we will have 4 types of prey.

Prey types:

A.  Static Prey: Randomly chosen point in the "world", the prey does not move (static).

B.  Straight Line Prey: Randomly chosen point in the "world", the prey moves up or down at a fixed rate, 0.3 or 0.2 steps of distance per time step. When reaching the end of the "world" it goes back in the opposite direction.

C.  Circle Prey: Randomly chosen point in the "world" and constant radius; the prey moves on the created circle at a constant rate.

  1. Random Movement Prey: Randomly chosen point in the "world", the prey moves per each time step to a nearby point.


Predator

The predator is Genetic Programming (GP) code.

It develops in the GP process, as described above.

Reminder: I am not developing the physical characters of the predator, just only the "brain function", i.e., the way it uses its sight to survive.

In order to define GP we need to define the following:

Functions:

Functions with arguments:

·  IFLTE (a1, a2, a3, a4), if less then equal, takes 4 arguments, if (a1 < a2) then a3 else a4.

·  PLUS (a1, a2), plus function, takes 2 arguments, add two numbers a1+a2 and return their sum.

·  PROGN2 (a1, a2), program with 2 arguments, run a1 & run a2, return the result of a2.

Functions without arguments: (All the movement functions take a 1 unit time step.)

·  TL ( ) , turn left 5 Deg, return RP resting potential

·  TR ( ) , turn right 5 Deg, return RP resting potential

·  MF ( ) , move forward 1.3 Dist, return RP resting potential

·  MB ( ) , move backward 1.3 Dist, return RP resting potential

Terminal:

·  RP, resting potential 1.0f.

·  AP, action potential 10.0f.

·  MAXPP, max value of Eye Sensor, 3 if one of them "sees" else -1

Sensors, take no arguments. If a sensor has an object in the sector: return 3 else return -1.

The predator has 15 sensors P1...P15.

Each sensor covers 2 Degrees, a total of 30 Degrees.

·  P1, sensor 1 range (345:347) Degrees.

·  P2, sensor 2 range (347:349) Degrees.

·  P3, sensor 3 range (349:351) Degrees.

. .

.

.

·  P14, sensor 14 range (11:13) Degrees

·  P15, sensor 15 range (13:15) Degrees.

Figure 7: predator.

Example to a predator Tree (Gene):

(PLUS(IFLTE(IFLTE P4 P5 P14 TL )(PROGN2 P15 MF )(IFLTE P5 P7 P13 TR )(IFLTE P3 MAXPP P14 P5 ))(PROGN2(PLUS TL P11 )(PROGN2 MF AP )))


Process of work

Main steps:

I will conduct four experiments, one for each type of prey, in order to check the development of the predator throughout time.

The evolvement of the predator will be monitored and recorded, and later will be analyzed.

1.  Evolution development of the predator in 51 generations.

Learning case: Static, Lines, Circle, Random preys.

2.  Test cases: testing the predator on the Learning case and also on new UNLEARNED cases!!!

3.  Plotting in a graph the development of the fitness during the generation.

4.  Recording a movie of live simulation of the predator from generations 0, 9, 20, 51.

5.  Taking samples of individuals from generations 0, 9, 20, 51; in order to analyze their development.

The most important step is the second step (test cases), which occurs after the end of the predator evolution stage. In this step we examine the ability of the evolved predator to cope with various kinds of predators which it has never met before.

This is an important test, because good test results, can show that the developed tactics isn't just a brute force solution for the specific prey it was developed for, but describes a more general and broad preying tactics.

GP technical data:

·  Gene: The gene is a tree of the functions and terminals as described above.

·  Crossover: Pc = 0.5.

·  Mutate: Pm = 0.05.

·  Population: Set of 100 individuals.

·  Selection method: Roulette wheel fitness proportion selection.

·  Init: For each individual G in the population build a random tree of depth 3.

·  Fitness Function:

Phase A: The Distance of the predator from the prey after simulating 400 time steps.

Phase B: Running Phase A 4 times on 4 different preys and return the Average distance.

One can think on more complicated fitness functions (for example the closing rate).

But the real test is if the predator captures its prey!!!(KISS)


Results:

I will present here the results of the 4 experiments I conducted.

A.  Static Prey.

B.  Straight Lines Prey.

C.  Circle Moving Prey.

D.  Random Moving Prey.

For each experiment I will present:

1.  Pictures that demonstrate the route of the predator (marked in light green) and the prey (marked in red). The pictures are taken in generations 0, 9, 20, 51 to demonstrate the improvement of the predator during the time. In some pictures I joint a few predators and preys. It will be shown as a collection of paths. In all pictures the predator's start point is in the upper right corner (coordinate (100,100)).

2.  Pictures of the test cases i.e. preys that this predator hasn't encountered for during the learning process. The pictures are the same type as (1).

3.  Functions that represent individual Gene (Tree) in generations 0, 9, 20, 51.

4.  Plots of generation vs. fitness; it will demonstrate the improvement of the population during the time. It will include average fitness of the population and the best individual of the population in the current generation.

5.  Movies of selected predators from different generations. The movies are in "wmv" format and can be found thru this link http://www.cs.bgu.ac.il/~beckerli/ICBV/Project/wmv/ .

Following the experiment I will analyze some functions (Trees) and show the distribution of terminals in the functions. I will focus on the vision role in the functions.


Static Prey Experiment 1: