Teaching AI to race using NNs and genetic algorithms

by Halienja • 10 years ago

141 42 10 years ago

wjnc• 10 years ago

Been staring in awe at this with my little sons (2&3). We actually get enthusiastic when the first signs of understanding arise. Where can I begin learning about this? I've done several sklearn examples, but this application to 'a new world' (like a racing game), how do you build that?

With build I mean, how do you structure inputs and objects so that the goal is met? The goal for racing is both steering, braking, trottle...

aethertap• 10 years ago

I did something very similar to this for an artificial life class back in college. My nets took significantly longer to learn how to race for some reason, but in the end it worked out. What I did was start off as simple as possible, just using a circular track so that it's easy to test bounds on the inputs (position greater than inner diameter and less than outer). My nets would get their sensor inputs at each time step, and would output a steering angle and speed. The speed would basically just be directly added to their current position after pointing them in the chosen direction. The fitness function amounted to seeing which racers got around the track the fastest.

You can get some pretty interesting behavior if you start with a barebones model of the world like that. At one point my racers started teleporting around parts of the track by taking advantage of the fact that I wasn't doing continuous collision detection - they would detect a turn and then output a speed and direction that would cause them to instantly appear on the other side of the corner without navigating the curve on the way. It was interesting to watch them balance the ability to teleport against the range of their sensors.

This sort of thing really lends itself to incremental tinkering, especially with javascript as powerful as it is today for prototyping. That gives a lot of intermediate feedback that will give you chances for finding new strange things to investigate. Adding features like tricky track generation is a decision you can make along the way if it seems interesting.

whorleater2• 10 years ago

It's a genetic algorithm, which means that it has a fitness function for how close the goal is to being met (choosing the furthest traveled car), and a 'gene', which is a sequence of instructions. The game utilizes a Neural Network to classify when it should turn/which way it should turn/how it should steer/etc, and then this NN is adapted into the genetic algorithm, which effectively generates random genes, follows each of those genes, then chooses the best 'fit' one according to the fitness function. Next, the algorithm restarts with the exception of now it's randomness is slightly based on the best fit gene from the last epoch, and repeat until you've got a gene that works.

Imagine having a wall, and a certain portion of it is sticky (since it's covered in invisible glue), but you don't know which portion, and you certainly don't want to touch it to find out. So you throw spaghetti at the wall, and see which portions stick. Next, you throw more spaghetti at the part that seems to stick, and repeat until you've got the entire sticky portion mapped out.

There's an old genetic algorithms demo with smart rockets and path-finding here: http://www.blprnt.com/smartrockets/ [warning: requires flash].

If you're actually interested in building one of these, Daniel Shiffman wrote The Nature of Code: http://natureofcode.com/, which is an introductory level book for this kind of thing. He uses Processing in the book itself for modeling, but he also goes over the theories pretty well.

If you want some formal literature, I took a brain and behavioral processing class in college, and the professor still has his slides up here: http://www.life.illinois.edu/mcb/419/sessions/index.php, along with links to papers and homework scaffolding.

TFortunato• 10 years ago

From what I can see, the course you mentioned looks very cool, however it seems a lot of the slides and linked papers are password protected. Do you have copies mirrored and/or know if the professor would be OK with these being shared?

(Don't worry if not, As much as I'd love to browse some of whats on there, I don't want to make extra work for you or get anyone in trouble!)

GordonS• 10 years ago

Nice, I love the way the user can change the NN and genetic algorithm parameters!

There isn't much documentation though - is the genetic algorithm being used to evolve the NN somehow?

arnsholt• 10 years ago

Since all the NNs have the same architecture, the breeding is done by taking some parameters from one parent NN and some parameters from the other to populate the weights of the child NN (in this case, indices that are 1 mod 2 are taken from the first parent, the others from the second one). In addition to this there's some random tweaks of some parameters (20% chance that any given parameter will be changed, with the change being uniformly random from the range [-0.1,0.1]).

snorremd• 10 years ago

Edit: The other commenter actually bothered to look at the code. Scratch my comment.

Lord_Fixer12• 10 years ago

Thanks :)

Yup, I (as a developer of this thing) haven't created a documentation yet, but it's mostly due to the fact, that I have deployed this just yesterday and there are still many things that I'd like to change in it. But I will work on that :)

impostervt• 10 years ago

Source code: https://github.com/TomaszRewak/ML-games

Lord_Fixer12• 10 years ago

Thanks for sharing.

You can find here all of the code. Everything here is written (by me) from a scratch, beggining with game engine, and ending on ML algorithms. It's taken to the level where I even multiply matrixes for graphics transformation, operating on pure HTML5 canvas. So everyone should find there something interesting for him. Only editors are a great plugin for ace C9.

kevinwang2• 10 years ago

Hi, why did you have to make your own graphics engine? Does canvas not supply everything you need?

zer0gravity5• 10 years ago

Generation 50 but none of the cars has learned to pass more than 5-6 corners.

Also, changining the track from one interation to another I don't think it helps. The training should be done on the same track until at least one of the cars is able to complete it. Than it can be changed.

Sometimes some of the cars get stuck and the round doesn't finish, without having to click the "End round" button. There should be some mechanism that detects that cars are stuck and end the round automatically.

zer0gravity5• 10 years ago

Ok, generation 60 and now a huge progress has been made. More than 50% of the cars are now able to finish almost all of the tracks. Very cool!

Lord_Fixer12• 10 years ago

Thanks :)

I actually have had inactivity detection implemented at some point, but I've resigned of this in favor for user-defined stop condition. But you are right, I will bring that back.

It's actually expected that in some cases it might take many generations to learn, as the population is rather small. In other attempts they can do this in like 5 generations, so please, tray to restart the whole process.

Keeping one track untill at least one car is able to finish it is not as good idea as it seems due to ovefritting. The will simply memorize all the moves depending on some insigificant factors and they won't be albe to finish any other track. I have tested that :D

retbull• 10 years ago

Took me to gen 11 and I only lost 1 car after that they all completed.

pmontra• 10 years ago

I clicked End Race in the first few generations when all the cars got stuck in the middle of the road. I think that by the fifth one at least one car was able to complete a lap.

max_• 10 years ago

"It is not the strongest that survive, but those that adapt to change " -- Charles Darwin

sidarape• 10 years ago

I was at Generation 47 and all cars (almost, depending on the new genetic modifications) were able to finish the lap.

cyrusaf• 10 years ago

I disagree about changing the track. It should be changed every iteration. If the track is not changed every iteration, the NN might develop to work in specific scenarios (only turning left for example) and when run on a different track, might fail miserably.

zer0gravity5• 10 years ago

On a track with both right and left turns that wouldn't have been the case.

While I agree that exposing the NN to diverse tracks each iteration asures a thorough learning, I was kind of curios how susceptible the algorithm is to exploit irelevant particularities of a track instead of finding the general rule.

I wish the creator will add the posiblity to chose if the track should be changed each iteration or only after at least one car completed it.

Rhapso• 10 years ago

http://www.cs.ucf.edu/~kstanley/neat.html

skykooler• 10 years ago

This is really amazing how fast they learn! It seems to make a lot more progress than, for example, that genetic car evolver that at generation 200 is still trying to decide whether to put the wheels on the bottom.

Lord_Fixer12• 10 years ago

Actually when I was designing this, I thought that it will take at least 100 generations to learn some simple moves. But NN are powerful indeed.

soared• 10 years ago

Another awesome one for the collection! It would be interesting to compare this and the RC car: https://www.youtube.com/watch?v=1AR2-OHCxsQ

r/WatchMachinesLearn

kyberias• 10 years ago

So is the genetic algorithm used to mutate the neural network weights?

Lord_Fixer12• 10 years ago

Yes, that's correct.

brilee• 10 years ago

Neat!

It should be noted that the genetic algorithm used is not the same as reinforcement learning, in which the entire history of decisions leading up to a success is fed back to the NN as training examples.

Lord_Fixer12• 10 years ago

I might be wrong, but isn't it? I think, that in fact it is, and what you are talking about is reinforcement learning with tabu search, or something.

EDIT: Sorry, I've understood you wrong, what you are describing is, of course, not a tabu search, but still I believe that this GA is a reinforcement learning.

EDIT2: After some research I can say, that opinions are divided :D

breckinloggins2• 10 years ago

I observed something interesting: when I changed the number of hidden layers from 100 to 1, almost nothing changed.

It took slightly more generations to learn how to race, but not that many more (~80 generations vs ~90 generations). In addition, I thought I observed a small difference in behavior, but nothing I could explicitly measure.

Lord_Fixer12• 10 years ago

It might be that in the process of learning, algorithm decided, that it can pass a constant value at the speed output and use this one node just to steer.

But I'm testing this scenario right now, and all I can get are cars going on different curves. Are you sure, that you have restarted the process after making changes to the script?

Lord_Fixer12• 10 years ago

After 100 generations thay actually have learned to move correctly, that's impresive. But they move very slowly. But for 100 nodes in a single hidden layer it takes them only around 10-20 generations to learn for me (not 80), and they race really fast.

eutectic• 10 years ago

Setting the hidden layer activation function to

    value => value >= 0 ? value : 0.5 * value;

seems to improve convergence a lot.

ronald_raygun• 10 years ago

I've found some tricks to get it to learn really well (by gen 20 they all finish really fast) 1. Using a relu, return value => value >= 0 ? value : 0.0; 2. Bumping it up to 30 cars (if you use too many, it slows down, and you dont get as good of results because each iteration takes ages) 3. Changing the lap condition to c.lap < 5 and the time to 30 s. This lets each race go longer and widens the discrepancy between the best and worst racers - which improves selection

Teaching AI to race using NNs and genetic algorithms

Related Stories