void ANN::mutate(double probablilty, double strength)
{
for each parameter:
{
if(rand()/(double)RAND_MAX < probablilty)
parameter += rand()/(double)RAND_MAX * strength;
}
}
Evolving ANN controlled racing bots
Author
Hello
This post turned out to be pretty long, so for the people who dont want to read it all the actual questions are at the bottom of the post.
Im working on a small car racing game and im trying to implement bots using NNs trained using a genetic algorithm. Im pretty new on this subject, but i have read about it on various forums and in articles.
About the game: Its an implementation of a paper/pencil racing game. You race cars around a track (only one lap though). The game is turn based. Every turn you can chose to accelerate, decelerate, turn or keep your speed. Acceleration/deceleration is pretty slow. Also you can only be on integer positions (as it's usually played on a grid paper)
The NN has 4 inputs. 3 feelers pointing forward and to the sides (at pi/7 angle from the forward feeler), and one input for its current speed. It has a 10 neuron hidden layer and 4 outputs. The outputs represent accelerate, decelerate, turn right and turn left. Please note that if for example both the turn right and turn left outputs fire, its interpreted as keep the current direction.
For training i use a genetic algorithm that trimms the input weights to the neurons and their threshold values. I use a population of 500 bots each generation. Ive only implemented mutation so far, which i do like this:
To accuire the next generation of bots i chose the 10% best bots, mutate each of these into 9 new ones. The remaining 10% are completly random bots (to introduce "new blood").
The probability of mutation is controlled by a "staleness" value, that measures how many individuals in the population has the same fitness value as each others. This counters a total domination of a specific individual.
Fitness is calculated based on how far on the track the bot came before crashing (if it crashed). If the bot finnishes a whole lap it gets a big fitness bonus. Alse the nr. of turns taken to make it around is subtracted from the fitness, to promote faster bots.
And now for the actual problems:
The bots arent getting very smart :)
They make it around some simpler tracks, but get confused as the complexity increases. I anticipated it would, given the inputs, be pretty easy for the bots to evolve some kind of strategy to stay away from the walls, go slower as the distance to the walls decreases etc. Instead they go really slow all the time, bump on the walls, and sort of get around this way.
Also the bots arent very general ie a bot evolved on a couter-clockwise track wount make it around a clock-wise track. I guess i could circulate tracks between generations to counter this?
The genetic algorithm gets stuck alot. It usually reaches some local maximum after about 20 generations, and then stay there for the following 20000 gens (this was before i implemented the "staleness" parameter mentioned above though, its better now but not great). Could this be because i havent implemented crossover yet? Would another mutation function help? (the current one always adds a number to the parameter, regardless of the parameter size, so when the parameter is very big the relative differens would be very small).
Maybe my net is too complex/not complex enough or have poor choises of inputs/outputs?
Please dont tell me that i should chose another algorithm for this problem. I dont really need good bots, and ive wanted to try this out for some time.
I know its possible to create bots this way, as ive seen some examples of it. Recently here on gamedev someone posted an application named genecars.exe which (i think) did this, and it worked great. With only one feeler to. My game has much slower acceleration/deceleration the this app though.
Any and all idees and comments are welcome. Like i said, im pretty inexperienced with these things.
Thanks in advance!
//Emil
I tried getting an AI to come up with a general way to land a lunar lander using a similar technique, and I never was particularly successful(my best one would just flip over and land slowly directly beneath where it started with no attempt to move toward the landing platform). However, I do have some suggestions:
1. Keep the best bots from each generation without mutating them. When you mutate the best bots it's quite possible that you'll only get bots that are worse.
2. Don't allow multiple outputs to fire at once. Just use whichever one has the highest output. It's easier for the AI to learn to fire left harder then right then it is for it to learn to fire left, but not right.
3. If you want a general solution for multiple tracks then you'll have to evaluate the fitness of all bots over all tracks(ie the fitness is the sum of the bots fitness on each track).
4. I would decrease the mutation rate over time. GAs are always going to be prone to local maximums, but decreasing the mutation rate over time should allow your AI to get closer to the actual local maximum.
5. Having the side feelers that close to the forward feeler is probably a good thing if you have smooth wide turns, but if you have sharp or jagged turns then you'll probably want to increase the feeler angle or distance. Consider the case where you have a 90 degree angle and the AI runs directly toward it. If the left and right feeler are close to the forward one then they will both hit the wall at the same time(and neither will hit the side wall), and the AI will have no idea which direction to turn in. I'd experiment with different feeler angles and lengths or better yet put those as parameters for your GA to tweak.
1. Keep the best bots from each generation without mutating them. When you mutate the best bots it's quite possible that you'll only get bots that are worse.
2. Don't allow multiple outputs to fire at once. Just use whichever one has the highest output. It's easier for the AI to learn to fire left harder then right then it is for it to learn to fire left, but not right.
3. If you want a general solution for multiple tracks then you'll have to evaluate the fitness of all bots over all tracks(ie the fitness is the sum of the bots fitness on each track).
4. I would decrease the mutation rate over time. GAs are always going to be prone to local maximums, but decreasing the mutation rate over time should allow your AI to get closer to the actual local maximum.
5. Having the side feelers that close to the forward feeler is probably a good thing if you have smooth wide turns, but if you have sharp or jagged turns then you'll probably want to increase the feeler angle or distance. Consider the case where you have a 90 degree angle and the AI runs directly toward it. If the left and right feeler are close to the forward one then they will both hit the wall at the same time(and neither will hit the side wall), and the AI will have no idea which direction to turn in. I'd experiment with different feeler angles and lengths or better yet put those as parameters for your GA to tweak.
Along with the above suggestions, you might try a NeuroEvolution technique. That's where your Neural Network is not fixed, and your mutatation functions not only changes weights, but also have a chance of adding nodes and connections. It could be that your fixed neural network is not capable of enough complexity.
http://en.wikipedia.org/wiki/NeuroEvolution_of_Augmenting_Topologies
http://en.wikipedia.org/wiki/NeuroEvolution_of_Augmenting_Topologies
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
