in machine learning, tutorial, Unity3D

Evolutionary Computation – Part 2

Share Button

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.

walker_8

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.

evolution

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 -1 (contracted) and +1 (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.

walker_4The 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 p, ranges from m to M and is shifted on the X axis by o. 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 -1 to +1:

Copy of Untitled drawing (1)

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.

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

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:

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

walker_1

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:

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.

walker_2

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

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

walker_3

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

📧 Stay updated

A new tutorial is released every week.

💖 Support this blog

This websites 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.

Paypal
Ko-fi
Twitter_logo

Write a Comment

Comment

12 Comments

    • 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!

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

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

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

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

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

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

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

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