# Evolutionary Computation – Part 2

In the first part of this tutorial we have explored what evolutionary computation is, and why it works. The rest of this tutorial will show how to set up a practical example and how to use evolution to solve a real problem. In our case, the problem is teaching a bipedal creature how to keep balance and how to walk effectively. Rather than evolving the body of the creature, we are interested in finding a strategy to make it walk as fast as possible.

#### The Body

The first step is to design the creature we will use. It is important to remember that evolution is a rather slow process. Starting with a human-like ragdoll might take way too long to reach a consistent and effective walking strategy. If we want to test out evolutionary software, we need to start with something easier.

The subject of our experiment is that very simple bipedal creature. It has two legs, L and R, which are hinged onto its body. They are able to rotate, thanks to two springs. When the springs extends and contracts, they pull and push the legs, causing them to rotate. The creature has no direct knowledge on how to rotate its legs, but it controls the length of the springs feeding them a value between (contracted) and (extended).

Note: Moving complex bodies is a challenging task. For the final project, I have replaced Unity’s `SpringJoint2D` with `DistanceJoint2D`, since they are more predictable. I will keep calling them springs, nonetheless. For the more complex ragdoll shown in the animation, limbs will be rotated directly by code.

#### The Brain

Walking is not just a matter of finding the right angles for L and R. Is a continuous task that requires equally continuous movements of the legs. If we want to walk, we need a way to provide the creature with a compact and meaningful way to move its legs. The list of choices here is endless. For the sake of simplicity, the relaxation and contraction of the springs is controlled by two sinusoidal waves.

The evolutionary process is going to fit the L and R sinusoids that make our creature walk. You can see an example in the animation on the side; the green and red sinusoid controls the L and R legs, respectively.

The springs are the entities that the creature controls, and will be the target of our evolutionary computation. Each sinusoid has period , ranges from to and is shifted on the X axis by . This means that the target of evolution is to find the two sets for these fours parameters which results in the best walking strategy.

#### The Controller

In our current setup, we already have several entities: the legs, the springs and the waves. To simplify the way we approach the problem, let’s create a class `LegController` that allows to control the contraction of the spring with a value from to :

We perform the rotation of the leg by changing the distance of the spring in `FixedUpdate`. This forces the joint to pull or push the leg until it reaches the desired destination.

```public class LegController : MonoBehaviour
{
public DistanceJoint2D spring;

private float contracted;
private float relaxed;

[Range(-1, +1)]
public float position = +1;

void Start () {
float distance = spring.distance;
relaxed = distance * 1.5f;
contracted = distance / 2f;
}

void FixedUpdate ()
{
spring.distance = linearInterpolation(-1, +1, contracted, relaxed, position);
}

public static float linearInterpolation(float x0, float x1, float y0, float y1, float x)
{
float d = x1 - x0;
if (d == 0)
return (y0 + y1) / 2;
return y0 + (x - x0) * (y1 - y0) / d;
}
}```

The two leg controllers are constantly updated by the `Creature` class:

```public class Creature
{
public LegController left;
public LegController right;

public void Update ()
{
left.position =  // ...
right.position = // ...
}
}```

We will see in the next part of this tutorial how the `Creature` class evolves to incorporate also the genome of the creature.

#### The Fitness Score

Evolution requires to evaluate the fitness of a creature. This step, which sounds trivial, is actually incredibly challenging. The reason is that the score we assign to each creature at the end of the simulation has to correctly capture what we want to learn. Failure to do so will inevitable yield poor results, keeping evolution stuck in local maxima.

My first attempt has been to evaluate the fitness of a creature depending on how far it travelled from its initial position:

```private Vector3 initialPosition;
public void Start ()
{
initialPosition = transform.position;
}

public float GetScore ()
{
return position.x - initialPosition.x;
}```

This converges to the walking strategy that requires less effort: dragging yourself on the floor:

I was rather unhappy with that solution, because it failed to capture one of the most important aspect of walking: keeping balance. As a second attempt, I gave a very strong bonus to all the creatures who managed to stay up on their feet:

```public float GetScore ()
{
// Walking score
float walkingScore = position.x - initialPosition.x;

// Balancing score

return
walkingScore
* (headUp   ? 2f   : 1f)	// Double score if UP
* (headDown ? 0.5f : 1f)	// Half score if DOWN
;
}```

Since falling is incredibly easy, that fitness function promoted creatures which are able to keep a good balance. However, it doesn’t really encourage them to walk. Failing is judged too severely, and evolution doesn’t feel brave enough to risk it.

To compensate for this, I tried to give an incentive for staying balanced that was independent of the walking score.

```return
walkingScore
* (headDown ? 0.5f : 1f)
+ (headUp ? 2f : 0f)
;```

In all my attempts, creatures converged towards a sloppy, yet very functional solution:

#### Conclusion

This post introduces the body of the creature we are going to use for our simulation. As long as you’re sensible with your design choices, evolution will work regardless of the body type. It’s worth noticing that my first attempt used a much more sophisticated body, which used four interconnected springs. That did not work very well, since evolution exploited Box2D’s constraint instabilities to make the creature fly at high speed. Yes, evolution likes to cheat. A lot.

The third part of this tutorial will focus on how to correctly represent and mutate the genome of our creature. Using a form that is amenable to evolutionary computations is at the heart of this technique.

#### Other resources

##### 💖 Support this blog

This website exists thanks to the contribution of patrons on Patreon. If you think these posts have either helped or inspired you, please consider supporting this blog.

You will be notified when a new tutorial is released!

##### 📝 Licensing

You are free to use, adapt and build upon this tutorial for your own projects (even commercially) as long as you credit me.

You are not allowed to redistribute the content of this tutorial on other platforms, especially the parts that are only available on Patreon.

If the knowledge you have gained had a significant impact on your project, a mention in the credit would be very appreciated. ❤️🧔🏻

1. Geoff

Alan, has the humanoid pictured in walker_8.gif (top of page) ever learned to walk?

• Hey!
YES. The physics of the ragdoll is not very good, so the final result doesn’t look that natural. This was an intermediate step to show you the type of strategy it has adopted: https://twitter.com/AlanZucconi/status/720181349903167492

I’ve evolved it a little bit more, tweaking the fitness score, end ended up with slightly better results.

• Geoff

That’s awesome!

2. DrFear

Is it possible to share the Unity project? I’m finding hard time reproducing the same physics setup, Thanks!

• Hey! Sure, I will share the full Unity project! I think this will happen with the last part of the tutorial. I want to add some more stuff so that people can have something nice to play with!

3. Artūras

What about using a score function that would return higher scores for faster walking? I wonder how would that look like 😃

• Hey! In a way this is what is already doing. If the time of the simulation stays constant, the distance walked already contains information about the speed. I think there are faster solutions, but they probably use only one leg. :p

4. CptBonex

I cant wait for the rest of the tutorial. I have always wanted to learn how to make more advanced AI that can learn and evolve and this is such a good start.

5. What is the code for the sine wave used for the left.position and right.position?

• Hey! 🙂

It will be published next week in Part 3! 😀 It’s already available on Patreon if you can’t wait! :p

6. Desoxi

Hey Alan,
would you mind explaining the linear interpolation part of the example code a bit? What exactly are you interpolating there..? And which meaning do the parameters have? Relaxed, contracted, position etc.

• Hey!
The evolutionary algorithm uses the range [-1,+1] for its calculation.
However, the actual spring that moves the legs uses a physical parameter that goes from [contracted, relaxed]. This represents the “length” of the “tendon” the controls the leg. When it’s shorter, it contracts the leg.

When you want to map an interval to another one, such as [-1,+1] to [contracted, relaxed], you can do it with a process called “linear interpolation”.

So:
linearInterpolation(-1, +1, contracted, relaxed, position);
means:
take the current value generated by the evolution algorithm (which is in range [-1,+1]) and convert it into another value ranged [contracted, relaxed].

### Webmentions

• Evolutionary Computation – Part 4 – Alan Zucconi February 12, 2017

[…] Part 2. Evolutionary Computation: Phenotype […]

• Evolutionary Computation - Part 3 - Alan Zucconi February 12, 2017

[…] Part 2. Evolutionary Computation: Phenotype […]

• Evolutionary Computation - Part 1 - Alan Zucconi February 12, 2017

[…] Part 2. Evolutionary Computation: Phenotype […]