Evolving "elementary sight" strategies in predators Via GeneticProgramming

Final project by

Lior Becker

liorbecker@gmail.com

Introduction

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

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.

Approach and Method

Genetic Programming:

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".

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.

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.

Predator strategy through GP:

In this work I will imitate a predator using Genetic programming. The predator will have an underdeveloped eye (15 photo receptors only), which will give him a feedback from his surrounding area. He will also have the ability to move right/left back/forward.


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.
During the experiment the predator we have to deal with few types of preys each one with his unique behavior.
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.

Results

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

  1. Static Prey.
  2. Straight Lines Prey.
  3. Circle Moving Prey.
  4. Random Moving Prey.
In the web page i will present only the second experiment, Straight Lines Prey, in order to see the other experiments pleas refer to link of full document. The link is given in the Additional Information section.

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 Movie Data Base.

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

Straight Lines Prey Experiment 2:


Downloadable the live movie 1
Downloadable the live movie 2

Test cases: Unlearned preys

Predator Vs. prey path


Population improvement

Figure: Plot of the fitness improvement during the generations, red average fitness, and blue best fitness.

Function Analysis:
In this section I will analyze one function of a predator from the last generation. I will also present the distribution of using the photoreceptors.

Function Examination: The function is taken from the last generation of the straight line prey.

(IFLTE
(IFLTE P6 (PROGN2(IFLTE P3 P11 P13 P13 )(IFLTE P2 MAXPP MF P5 ))(PROGN2 P4 P6 )(IFLTE AP MB P5 MB ))
(PLUS MAXPP P15 )
(PLUS(IFLTE P3 P1 MF P14 )(IFLTE TR MF P1 P12 ))
(PROGN2(PLUS P12 P10 )(PLUS P11 TL )))

Mark in red is dead code, I will remove it. We will get the following code

(IFLTE
(IFLTE P6 (IFLTE P2 MAXPP MF P5) P6 (IFLTE AP MB P5 MB ))
(PLUS MAXPP P15 )
(PLUS(IFLTE P3 P1 MF P14 )(IFLTE TR MF P1 P12 ))
(PLUS P11 TL ))

Pi – photoreceptors; TL – turn left; TR – turn right; MF – move forward.

Some facts:

  • There are pieces of code that we will never be reached or are redundant. We might think that they are unnecessary, but like in the real world, a creature doesn’t use its entire DNA. One of its goals is to cause dissimilarity of the offsprings that will be caused by crossovers and mutates. This dead code might be the key to success of their offspring's.
  • As you can see it is very hard to examine and analyze the code. But what we can see is that it uses mostly the side photoreceptors, and it uses at any given time only one of the two: TL / TR turn left or turn right, and not both at the same time which is not efficient.
In the plot below we can see the distribution of the photoreceptors in the functions.


Figure: Average appearance of photoreceptor in the functions of the last generation.

Conclusions

  1. I believe that the experiment succeed to imitate an abstract evolution of predators strategy. We can see the evolvement of the predator over the generations. It is expressed by the development of the predator's strategy that can be seen very well in the pictures of paths and the plots of fitness vs. generations. We demonstrated that the ability to see (via only 15 photoreceptors) will give the predator an advantage in its habitat. This can result in a very good strategy after a reasonable time.
  2. None of the predators evolved to reach sophisticated strategies such as ambushing the prey or trying to anticipate the movement of the prey and wait for it. Instead all the strategies were based on quick and efficient chase. One reason for this could be the lack of necessity; the efficient chase strategy is good enough for catching all the preys after a reasonable time.
  3. Function and Vision analysis:
    • There are pieces of code that we will never be reached or are redundant. We might think that they are unnecessary, but like in the real world, a creature doesn’t use its entire DNA. One of its goals is to cause dissimilarity of the offspring's that will be caused by crossovers and mutates. This dead code might be the key to success of their offspring's.
    • It is very hard to analyze the code.
    • From the plot we can learn that the predators use mostly the external sensors. We need to remember that unlike human eye the predator eye is composed from equally spaced photoreceptors, and only one type. The observation that the predator sight function rely mostly on its side photoreceptors provides further evidence to support the theory explained in part 5.
  4. We can see that during the evolution, the predator's strategy is based on circling movement (for example in the circle movement prey). As time goes by and evolution takes its role, the circles tend to straighten out. Most of those circles appear to be redundant since they are causing the predator to waste valuable time on his goal. We can see that after evolution takes place, the predator moves in very small circles while searching for its prey, but once it spots the prey – it moves toward the prey in almost straight lines, therefore wasting less time and energy.
  5. I divided the strategies in to 4 categories:
    • Random strategy – the movement of the predator is chaotic. It seems to go with no purpose. A good example of this event can be seen in the static prey generation 0.
    • Left circle rotation strategy – the predator always moves in a left rotation circle until it sights the prey. Then it continues in the left rotation circle. The only difference is that it increases the radius of the circle, and it gives it the ability to approach the prey. If for some reason it looses the sight of the prey it reduces the radius of the circle, which will cause the redundant circles described in the former section. A good example of this event can be seen in the static prey generation 9, 20. We can also see the better control the predator has on the radius of those circles.
    • Right circle rotation strategy – same as the left circle strategy but turns are in the opposite direction (right rotation).
    • Combined (left & right) strategy –The last strategy (like its name) is a combination of the left and right circle rotation strategies. Like the left or right rotation strategy it can cause redundant circles behavior. Unlike the left/right rotation strategy the combined strategy predator can avoid losing the predator since it can follow the prey with left or right rotation, depending on the prey direction. The ability not to lose the prey will give predator a significant advantage on the other predators in the population. According to Darwin's principles "survival of the fittest" this predator will have high probability to bring more offspring's to the next generation. A good example of this event can be seen in the straight line prey - the picture of the test cases, where the predator rotates left and right on the same path.
    We can clearly see how the four strategies above are implemented during the evolution of the predator:
    • Random strategy generation 1 - 9.
    • Left / Right strategy generation 10 - 40.
    • Combined strategy generation 40 - 50.

Additional Information

References

  1. Darwin, Charles: On the origin of species by means of natural selection. London, John Murray. (1859)
  2. John R. Koza: Genetic Programming: On the programming of computers by natural selection. MIT Press, Cambridge, Mass. (1992)
  3. John R. Koza: Genetic Programming II: Automatic Discovery of Reusable Programs. MIT press, Cambridge, Mass. (1994)
  4. John R. Koza: Evolution of Subsumption Using Genetic Programming. MIT press, Cambridge, Mass. (1993)
  5. Holland, John H. Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press (1975).
  6. Haynes, Sen.: Evolving behavioral strategies in predators and prey, University of Tulsa (1996).