Hello, guys! I have created a kind of genetic algorithm which creates a control system for the car moving on a very curved track. We can say that a car gets a 'driver' as a result of the evolution search. I'm just interesting is it considerable task to solve genetically. Let me explain how it works. Before the evolution begins, the car has no control system. It can just stay on start position and do nothing. A car has one incoming property and three outgoing (control) properties. Incoming property is: 1. How far to the border of track straight ahead. It's like a laser beam estimating a distance to the border. Outgoing properties are: 1. Angle to turn a steering wheel 2. Acceleration 3. Strength of brakes pressure As you can see, a car has minimal information to decide where to turn to avoid a collision with a border. But I have supposed it's enough. Genes created randomly are randomly linked with each other, creating a net which gets an information from the incoming property (updating every moment) and calculates signals for outgoing properties to drive correctly. First generation of cars gets a random set of genes, and they drive worse than a drunk. But someone gets a little longer than others do. And then the evolution begins. Every next generation fills with descendants of the best cars of previous generation. Every descendant gets a copy of ancestor genes with a little mutation. After a few generations we can see cars can easily reach a finish line. It means they got a good 'driver' (genetically control system). Here is a program which demonstrates the evolution as well as shows a race process for each generation. Download GeneCarsE.rar [190 kb] When you run a program, it creates first generation of cars and let them drive. Then you just have to click the 'next generation' button to kill losers and to reproduce relatively winners and to start new race. Evolution algorithm gradually creates a structure of the control system, unlike traditional GAs which simply optimizes existed one. Just tell me please how do you think is it something considerable or trivial? Do you know any other examples of 'progressive' evolution algorithms? Can anyone propose any kind of game developing tasks like a 'automatically create a control system for the certain object acting in complex environment' which could be probably solved with progressive evolution faster than manually?

Quote: Original post by Ath
Just tell me please how do you think is it something considerable or trivial? Do you know any other examples of 'progressive' evolution algorithms? Can anyone propose any kind of game developing tasks like a 'automatically create a control system for the certain object acting in complex environment' which could be probably solved with progressive evolution faster than manually?

I dont want to be an -donkey-, but a few dozen lines of simple steering behaviors will make a car move to the finish line, in a more debuggable, managable, elegant and efficient way.

On a more cheerful side, google NEAT for the most popular example of GA that evolve the structure of a NN. The idea has been around for a long time.

I thought it was kind of neat that there was a strategy that worked using only the distance to the wall straight ahead of the car. It seems to be something along these lines:

if distance < a and distance > b: turn left
if distance <= b: turn right

Except that the turning angle is blended smoothly from one extreme to the other, using the evolved function.

This strategy is fragile. I noticed that hairpin turns gave it a lot of trouble, since if it didn't turn quickly enough it could become confused as it gets closer to the edge and then tries turning towards the wall. If the walls were different colors, and the car could see which color the wall in front of it was, it could find a much more effective strategy. Or if it had more than one sensor. Oh, here's an interesting one: what if it had an output to turn its sensor independently of the car? The sensor direction would probably need to be an input for that to be useful.

As far as evolving a neural network, yeah, a lot of people have done research in that, and other function approximators. There's even genetic programming, where the genetic algorithm manipulates things like mathematical operators and conditional statements to try to find a little program that works.

Is there a good reason why you are using only a single input?

..

I would have started with 3 inputs and evolved not only the control behavior but also what angles these sensors should be placed at .. I might have also consider a memory input (an output from the last frame which the "driver" has full control over)

This strategy (of using line of sight ahead of the vehicle) for avoidance of collisions with the walls/border of the track is just a common wall avoidance approach. Why would you want to use a GA to solve this problem when, as Steadtler pointed out, there are known algorithms for finding robust solutions.

In either case, you should do as Rockoon1 suggested. Your line of sight distance out the front of the vehicle corresponds to a forward 'feeler'. Clip its length and add two other feelers (usually at 45 degrees to the forward feeler) that are slightly shorter. The centre of mass of the vehicle and the ends of the 3 feelers should sit on an ellipse that bounds the volume of space the vehicle can traverse in the next AI iteration (the larger this ellipse is relative to this future space the more robust yet conservative your AI will be).

Given this setup, you can then use the first feeler to touch a wall to determine the vehicles behaviour (steer away from the predicted collision) and/or apply the brakes.

Cheers,

Timkin

Quote: Steadtler:
The idea has been around for a long time

Yes. But this one is not a sort of well-known GA-training NN algorithm, it’s growing gene network completely built upon the natural genetics to avoid imperfection of classical GAs.

Quote: Vorpy:
if distance < a and distance > b: turn left
if distance <= b: turn right

Absolutely right.

Sure, this task is simple. But it’s just example to see will the algorithm work or not. It works. Its advantage is an ability to construct a certain solution without any prompts, on empty place. It has found the same solution which a man could offer for this task like you did.

And i hope it will show its real power on some more complex problems where human could have a little trouble suggesting solution.

Quote: Rockoon1:
Is there a good reason why you are using only a single input?

The aim of this work was to test my GA: could it solve a problem with minimum input information. A lot of feelers pampers the algorithm.

Quote: Rockoon1:
a memory input

You right. I just passed around to mention about the inner properties. There are temporary properties dynamically creating by genes to sum integral and to calculate differential values of other properties.

Quote: Timkin:
Why would you want to use a GA to solve this problem when, as Steadtler pointed out, there are known algorithms for finding robust solutions

This work is a part of research to create more powerful instrument of genetically based search strategy with elements of constructing new systems like the natural evolution do.

Quote: Timkin:
Clip its length and add two other feelers (usually at 45 degrees…)

I think this algorithm could find the optimal lengths and angles of additional feelers if I would let him to search for these parameters. But seems like I should end with this model and start with another, more complex one.

Thank you guys again, now I see the situation clearly.

Sounds like a fun and pretty interesting project. Next step is to make it work with other cars on the track and avoid collisions with those while circuiting the track as fast as possible. As people suggest above, that will probably require an array of sensors.

Steadtler mentioned a 'progressive evolution' algorithm - NEAT - which evolves ANNs from scratch which become more complex and they approach a goal. The NEAT algorithm (among others) is currently being tested by a major car manufacturer for use in a "collision detection system" for real life cars. So keep up your research and maybe you can get a job doing something like that.

Some suggestions on the demo - make it windowed and make ESC exit. I couldn't figure out how to exit hehe.

I would suggest you make a racing line spline like Colin Mc Crae did (It used Neural Nets for it's AI). This will help you avoid problems on hairpins, etc.

I've done a few home projects using neural nets and genetic algorithms though it's much harder to find an applicable use at work. In professional game development usually AI is an endevour to make something that doesn't kill the player to often while looking like a constant lethal threat. The emergent behaviour of these algortihms is usually not good enough for AAA games.

While I haven't found much use for neural nets I have found that using genetic algortihms for balancing AI parameters for different fitness tests canbe an easy way to generate many good different AI types and balance games.