Increasing the distance of the point the artificial driver aimed at made him tend to cut corners a bit more, and essentially hit the tires in the chicane or the tall curbing on the sharp 90 degree turn. Although you are correct looking too closely on a straight tends to make the driver wobble from left to right as it goes beyond the desired direction. Interestingly, I tried solving this problem much earlier in development by interpolating the actual steering input in a smooth step or inverse squared manner.

Essentially the idea was that the closer the driver already is to the desired direction, the less he would steer towards it in a non-linear fashion. This sounded pretty intuitive to me at the time, however it resulted in the artificial driver turning in far later than he should, because it takes longer for his steering angle to actually increase, I decided to remove that and simply steer linearly.

I'm taking a break from the project currently to do some other things in life, but it is only a matter of time before I get some thoughts jumping and wanting to be tested. It is really unfortunate that I can't get the predictions to be smooth enough for actual usage. I was hoping to get the artificial driver to change the inputs based on the predicted position/direction and desired direction/position. Theoretically, this will automatically look further ahead when travelling at speed and should, also theoretically, reduce weaving/wobble on a straight. I do see a slight potential that it could actually make the wobble worse.

I may work on a very small, two-dimensional racer project just to try out the genetic algorithms and possibly ANNs, they sound neat in concept, and it also sounds like one of those very rewarding things to create. Watching the cars get a little better would be super neat. I will not be using true physics in this project. That is actually quite advanced. I may simulate the engine, clutch, gearbox properly, but that force will then just move the vehicle forward, and turning will simply rotate the vehicle instead of applying torque with the front wheels and adhering to the ground with friction. Simplifying everything only to play around with learning algorithms.

Even two-dimensional racer designs can vary greatly in physics complexity though.

Of course, I'm thinking of pretty much the most basic of "simulations".

The world would not have gravity, but it would have a resistance to objects that are moving, pretty much air resistance. (No wind, slip streams or other effects), there would be no friction or any other objects besides the cars.

The track would be defined as a several curves linked together to create a circuit, and a constant track width. For visuals, this will allow me to draw the famous lines to outline the track.

The car would be defined as a world position (x,y) with a radius, so the car bodies are simple circles, and a direction (x, y) which way the car is facing / driving.

Once I get to a black screen with the ability to collect input from the user I will time myself to see how long it takes me to make a track representation, a car that can be controlled via the inputs: throttle (0 to 1), brake (0 to 1) and steering (-1 to 1).

I don't expect it would take too long, however I don't yet have working input in this project, so that comes first and that might take a little longer.

So I've created this, extremely simple, top down racing "simulation".

Screenshot

It is as I described in my post above, with the addition that anything off track adds a huge resistance, like a sand trap that you can get out of. It is complete with checkpoints and will time your laps. You can use the arrow keys to control the car, and console prompt that appears will show you the lap times. You must be on track when going through the checkpoints, there is no give with that at the moment.

Now I can use this simple simulation to attempt to create a genetic algorithm or artificial neural network and have several cars as well as speed up the time so everything runs much faster than real-time. Let me know what you guys think of the extremely simple simulation.

IMG link is broken so I'll just post it.

Off track sand trap can make learning much slower and more damages. Don't do it, at least not at this stage of the research.

Just force the car to stay on track and keep heading within an acceptable range, and use heavy penalty (or kill the search path) when the car touches the edge.


The inside line of the bottom corner on your track is overlapping.

I knew someone would pick on the messed up, sharp turn 1 where it overlaps. It shouldn't make much difference as those are there simply for our visual reference at this point. The track was defined by the center line and a width, of course that does mean that turn 1 has a radius that is tighter than the track width, hence the overlap.

I'm not sure the additional drag should slow the learning any more than just keeping the car on track? I could be wrong but I would think if the algorithm attempts to drive off track it will die out because the distance covered is to low, or a lap time is too slow. I suppose it is possible that an off track lap time results in a faster lap, but that can be thrown away by making sure the car was on track the entire lap.

I'm actually at quite a loss of where to go from here though. From my reading of GA I'm not quite sure how to apply it in this situation. I'll keep reading I guess!

If you want to disqualify any off track attempt, just stop the computation when the car hits the edge. Don't waste your machine time computing something you'll throw out anyway.

If you do allow the agents to wander off track, it will get messy. Sooner or later your AI will learn to cut corners or use sand traps for faster braking.

Using a center line and a track width has the benefit of being able to locate a vehicle by longitudinal distance and lateral offset, which makes it easier for the AI to know where to go. Like you said this system breaks when the center line radius is no higher than half width. If off track is allowed the offset can be infinite, so in theory this distance/offset system can always be broken. When your agent reaches the messed up area on turn 1, which way is forward? What if your agent simply cuts a big sections of the track and miss a series of corners?

If you really want to keep the sand trap, giving the track model two width values, one for tarmac, another (bigger value) for sand might be an option. The agent will be able to go off tarmac but not off the "sand belt". It's more complicated though.



I would suggest starting from a even more simplified model, a simple track with no width at all. The vehicle is simply riding on rails. The AI has only one output channel, the combined throttle/brake channel. It doesn't even control any steering. You goal is to minimize lap time while keeping acceleration under a threshold. With such a simple model it's trivial to brutal force it with A* search, and use that as a reference. If you can get close to A* with your GA or anything, move forward to a more complicated model.

I now understand what you mean a bit more with just killing off the genes that go off track, I will certainly look into that suggestion! I'm still not sure how to apply the GA to a driver, but am looking forward to the moment it clicks and will continue trying to understand it a bit, learning is fun.

In other news I was watching the artificial driver lap around FE1 while I was working today, working from home is great, and besides the fact that the driver was not staying on track due to my recent changes, and too much wobble, as Tood and I have discussed a few times not too long ago. In watching it some more I realized that he would start braking for the turn as expected, but then stop, then start, then stop. The reason then clicked...

I have several points ahead of the driver, soonToBe, farToBe and farFarAway. The driver scans the track at several distances ahead so that he can start braking earlier for a turn, and it was working, with the exception that he would immediately forget about it once the angle of the track at those points increased, even though he hadn't actually arrived at the turn. (So he detects turn 1 is coming a the point farFarAway and starts braking. Before he gets to turn 1 the farFarAway point goes well beyond onto another straight portion so he stops braking, because the other points were not at T1 yet)

I modified the code slightly so that if the angle at those points is greater than some value, he will remember the maximum value it was at, and the distance to travel before reaching it. That way he will continue braking until he reaches the point and not look too much further ahead. This, in combination with the stuff I did a few weekends ago to make him drive smoother, has resulted in MUCH lower lap times. A 1:03:66 was the first new PB shaving more than 6 seconds off!!!

The current problem I saw is the racing line isn't as smooth as it once was because I didn't let the iterations play out for a long time, it only has 5000 iterations where 100k would be much better. Before running the racing line computation again I decided to watch him do 5 laps so I could give you all this replay, attached. He still needs to tone down on the wobble, and I will look for a fitting way to do that (without messing with the distances too much). But in the replay the artificial driver hit the new low of 1:02 (Okay, to be fair it was a 1:02:990).

I'm going to let the track recompute and save out a better racing line and then will run the test again to see if it helps, it should help a little, especially in the final downhill chicane, where the current version tends to get a little wobbly and can sometimes lose control of the XRG.

Enjoy.

Edit

After running the racing line computation for 300k iterations, and saving the new copy again, I came up with the second replay and another new personal best on laps 4 and 5! I wonder a little bit if tire heat is playing a roll. But I know the wobblyness is certainly playing a roll, will keep pondering a way to reduce that without adjusting the distance and/or cutting corners, a previous problem. Both replays are attached. The new PB 1.02:12 is actually much better than I was expecting it would get. Going to attempt a really long run of 100+ laps to let it actually see what it will get down to, I suspect at least a 1:01:7x is possible.

Edit 2:

After running 70 laps, with a new PB of 1:01:81 on or before lap 6, (can currently be seen on LFS World for airs_artificial_driver ) I noticed a pattern. First, the wobbling that I've been talking about today is effecting laptimes, a lot. The first sector is consistently in the range of 28.4x to 28.7x and averaging low 28.6x's - which is not terrible consistency given the wobbly, lag, etc. However, the lap times on the other hand, were averaging the 1:04s, and could bounce from mid 1:02's to high 1:05's. Which shows how inconsistent the second sector is, mostly due to the wobble.

Unfortunately, this really sucks, I was an idiot and didn't look at the setup the car had on it before changing to the LX6 to see what would happen. This thought hit me immediately after selecting the LX6. Why couldn't it have happened before. So, I tried default and 3 other sets that I felt were likely candidates but none of them are producing similar results. This sucks, and it proves how much the personal best will come down to a setup. When I find it, or come across another decent set, I will give it a name that will be easy to find in the future. Unfortunately I can't test fixing the wobbly, or other things until I find the setup or make new benchmark numbers which might even be slower.

On the other hand, given the behavior I did notice I could make the driver brake later than he does. I haven't done it yet, I wanted to remove wobbly steering first. But with a little tweaking of the speeds, I am sure sub one minute times are possible. Lets hope I can find the setup again, otherwise I'll need to redo the benchmarks before moving on. :-(

Edit 3:
Still looking for the setup. None of them seem to be reproducing the results I was seeing earlier, which is - super annoying. I haven't seen a single 1:02, or even a mid or low 1:03 for that matter, if I have even seen a 1:03... Most of the sets seem to be braking too hard on T1 locking the tires. I did some investigating watching the replay and was able to figure out that the set is using plain and normal tires, so I've been attempting to go through all XRG sets that meet that standard and I have like 10 of them. I'm just thankful it wasn't using Bridgestone as there are many more sets there. The crappy part is my choosing of the set is based on my memory of what was happening and what is happening, and the circumstances are different every lap anyway due to slight discrepancies in the lag/timing. I almost wonder if I've dismissed the good setup already, but I honestly hope I did not.

Edit 4:
I think I've found the set. This one seems to have lap times between mid 1:03's and mid/high 1:05's. Considering those fast laps earlier didn't appear more often in the 75 laps, I guess they are more like lucky laps than anything else. Still, 1.01:81 is nearly 2 seconds faster than what the artificial driver is doing, but this set feels fairly consistent with what I remember seeing earlier. Not exactly watching it full time, but the lap times are within the correct range. I suspect the 1:01s are possible when the "wobble" effect is minimized by chance, allowing better ending. As I saw before the first split is reasonably consistent, although it appears to be slightly slower at 28.6x to 28.8x but maybe that happens as fuel wears? I'm letting him run a long distance again, and will make sure to keep this set marked.

Using the tiny/simple two-dimensional simulation I've created above, which is playable, I will dabble with the idea of using a Genetic Algorithm to create an AI that can drive around the track, hopefully reasonably well. I actually have a feeling that it should end up becoming much better than a human... I've never tried creating a genetic algorithm and a few things are still a bit fuzzy. If you (looks at Todd and maybe Keling) have any help to offer that would be super useful for my attempt this weekend.

The following is a very rough outline of what I have planned out.


This is a basic skeleton of what I understand, my implementation would have each gene have a meaning, and skip the 'random bits' because I don't find it useful to manipulate values by flipping the bit, there is more control over the step size by using the maxMutation in each gene.

The genes I have planned as items that will control the algorithm, but I haven't fully planned this out. For example, one gene might represent a maximum angle (from driver direction to desired direction) that the driver will use to control the steering input. That in combination with another gene that might represent the maximum speed at that angle might control the throttle / braking response.

The idea is to have some basic logic which the genes then control the values for this logic. I may be thinking about this the wrong way, my brain is hardwired for thinking about things in terms of IF a THEN b, and it has been a bit challenging to get thinking about how best to use the GA. This is so far an approach I am at least happy with trying, although if anyone has advice before the weekend, I'd like to hear it and think it over!

Either way the results should be neat, and maybe after I get the GA I can think about adding an artificial neural network as has been suggested also. This could remove the logic and the inputs would be things such as currentSpeed, currentDirection, desiredDirection with the outputs being throttle, braking and steering responses. This would take the logic described above and put it in a black box of magic that I would no longer have control over, but in theory should still produce very good results. One step at a time though.

Learning happens all the time ...

Sometimes I am an idiot. Someone very recently mentioned just using the PTH files to determine track edges, rather than placing the cones all around the track by hand in a layout file like I did when I first started the project. This came up recently when I was adding a new track and failed by making the corner too sharp for the center line algorithm to work. I proceeded to continue by creating curves from these points that would theoretically remove the problem entirely...

Well, a new problem seems to appear. I have not yet narrowed it down, but it is caused by creating the curve, especially during a straight portion of track, or a portion of track immediately after a long straight. I'm not entirely sure. I was however attempting to create a layout on the drag strip, to improve the artificial drivers shifting and acceleration/launch from a standstill. I attempted this three times however it all failed due to the curves, so I gave up and moved on with other things.

I recently started the tiny simulation for playing with a Genetic Algorithm, as some of you have downloaded and tried and hopefully had some mild entertainment with. I had also read through the entire thread, for the most part, and noticed that before I even started using layout files (although the idea was there) someone had mentioned the I could get the track information from the PTH files. So this has been mentioned recently and was mentioned a long, long, time ago as well.

I was considering giving back to the community a little bit, with an idea the Dygear had last year when I was working on the Racing Line computations. He had mentioned I load the LFS PTH for comparison, and then hinted that it would be neat to see those paths edited. At the time I agreed but was focused on the racing line. Today I decided to look into modifying those files for laughs and have not yet found out how. The AI path seems to be stored somewhere besides the PTH files, which is a little evident since LFS does not contain the PTH files during an initial install.

So unfortunately I failed to modify the path the LFS drivers take. But I decided since I had changed some code to see how difficult it would be to use the PTH files for creating a track... So I added an additional left/right/center of track lines and loaded them from the PTH file and it was extremely easy, takes the time of editing away.

Pros and Cons ...

So, an obvious advantage to using the PTH files is no longer needing to edit the track layout by hand, this should reduce or remove entirely the chance for something to go wrong during computation. Actually the center line algorithm is much more simpler this way, so those problems are automatically removed. This would allow the artificial driver to know ANY track in LFS that has a PTH file immediately without anything except a few moments to compute the racing line.

However nothing comes for free and there are a few disadvantages to using the PTH files. First, the track edges are defined by LFS and while this reduced errors and effort, in some places the edges may not be where desired, say a chicane/curbing that would typically be used for faster laps. It would also eliminate the possibility to create auto cross layouts for the artificial driver, or allow him to drive on the drag strip - without creating special cases.

Now even though I have all this information now, and probably should have just done that to begin with I am unsure whether or not it is a good idea to use the PTH files or not. It wouldn't be hard, but it would take a little bit of time to change the use of Layouts and start using the PTH file, and with the other limitations of the PTH file I'm not entirely convinced it is worth it. Although the prospect of having the driver on more than just FE1 is certainly welcomed.

Can anyone let me know if ...

Does anyone know how to get LFS to use the modified PTH files, which is likely impossible? Or to modify the LFS AI path? Has anyone attempted this before? I won't be looking into it any more than I have already but if someone knows what file to modify and the specified format of that file I would be interested to know it.

Back to the simple two-dimensional simulation... (downloadable here)

hi blackbird04217


regarding the pth files would it not be aslong as the pth file stays the same size then it would be ok. you most likely have the following information which im going to post so if you have i applogise

1st thing i found is the following - https://www.lfsforum.net/showthread.php?t=66809

also the replay analyzer has the source code included which it gives some info regarding the pth files

https://www.lfsforum.net/showthread.php?t=20056


num unit offset description
--- ---- ------ -----------
HEADER BLOCK :
6 char 0 LFSPTH : do not read file if no match
1 byte 6 version : 0 - do not read file if > 0
1 byte 7 revision : 0 - do not read file if > 0
1 int 8 num nodes : number
1 int 12 finish line : number
......NODE BLOCKS

NODE BLOCK :


1 int 0 centre X : fp
1 int 4 centre Y : fp
1 int 8 centre Z : fp
1 float 12 dir X : float
1 float 16 dir Y : float
1 float 20 dir Z : float
1 float 24 limit left : outer limit
1 float 28 limit right : outer limit
1 float 32 drive left : road limit
1 float 36 drive right : road limit

bishtop - Yea I did indeed have that information, but thanks for searching around. I've loaded the PTH file correctly, and it works for the purposes of my AI collecting information about the track edges. I wouldn't use the racing line from it just because I wanted (and now have the ability) to have the artificial driver compute it.

I am more curious about where the AI driver paths actually get stored in LFS, as I was attempting to modify it so I could share that with other players, but it wasn't as straightforward as modifying the PTH files, which is a little obvious since they don't come with LFS on an initial install.

-------------------------------

Genetic Algorithm

Back to my focus for today, with the simple two dimensional simulation, last night was a fairly sleepless night as I was pondering how best to make the genes work in the genetic algorithm. Actually I got a very basic, first attempt of a genetic algorithm coded up last night. It remains currently untested and still needs to make use of the genes and create a fitness as well as iterate through several attempts.

My original thought in my long post above was to use bits of logic. Such as get a point ahead of the driver, and using some of the genes make comparisons with track edges and apply steering. This would probably work pretty well and would likely evolve to work better, but it is still based on logic that I put in place. Then I had a breakthrough and I am not sure what caused it.

Lets use reference points!

Calling these reference points for the first pass will be a little more difficult, but the general idea is the driver can see a reflector, a painted line, a change in pavement, or whatever it is, a reference point, at the center of the track every X distance. This should be extremely easy to setup from my track curve, although this is a simplified version of the initial plan where the reference points were randomly placed away from the center-line. Then each of the drivers in the population would use genes to figure out what to do.

In my first implementation of a GA each gene has a value from -1 to 1. I may later change this to be from 0 to 1, but it seems like a reasonable approach. If the application of a particular gene needs a larger range it can always be multiplied later. If there are 100 reference points along the track, then there would be 200 genes in each chromosome which the driver gets. One for steering input, one for brake/throttle input where negative is braking.

Taking this approach I will then compute the current and next reference points and interpolate their genes for the input of the car. I like the approach because it doesn't have me working on any logic, it represents a more genetic approach and should produce some interesting results, including going off track, just spinning in a circle, just stopping. However, the drivers should get better over time, theoretically even becoming faster than a human.

The approach for fitness

The drivers would not get faster, and would seem rather dumb, if they never mutated or crossed genes with other drivers. The genes of two drivers will be mixed at random, with more fit drivers having a much better chance of getting picked. The drivers fitness will be determined by a few things. At the start of each generation they will all start in exactly the same place as the player does, and all fitness levels will start at 0.

As the drivers move around the track (in the correct direction) the fitness level will increase to whatever the maximum distance reached is. Once a lap is complete 100 will be added. Anyone who finishes a lap will have the exact same value 100 + track distance for a fitness. It will then add another 100 points that gets scaled by lap time, so that a lap-time of 10 seconds (theoretically impossible with the current settings as my lap times are ~17 seconds) will give all 100 points, while a lap time of 30 seconds might give 20 points.

Any driver that falls off the track will stop moving, and fitness will remain the distance where they went off the track.

Next generation

After 30 seconds or when every driver has fallen off track, which ever comes first, the generation will spawn a new generation. The new generation will start all the cars back at the same exact starting position, and start the timer for 30 seconds, letting the cars start racing and repeat by spawning a new generation after the condition is reached.

I am looking forward to watching the results. Although I am not convinced this will be usable in the airs project, it is still neat to create, and learn, and watch.

ahh sorry i was of no help, I wont pretend to know much about programming ect, wouldnt the ai use the same pth files and just be coded/programmed to return to the pth line when they are knocked off it

So you feed (relative?) ref point coordinates to the system and then what? How exactly do you go from a point input to an controller output?

No, actually I don't necessarily feed inputs to get outputs. The artificial drivers in this simulation know about their car position in the world, and several reference points that happen to be on the center line of the track. Using this the driver will choose the current reference point, and the next reference point and get a value t where 0 <= t <= 1. When t is near 0, the car is closer to the current reference point and nearer to the next reference point when t is near 1.

The genes in the genetic algorithm then control what input the drivers have/use at each reference point and the system will interpolate between the current/next using t. It is fairly simple in implementation, and so far is not working so well. I'm not entirely sure why. In theory the drivers that make it the longest distance should survive on and continue to mutate their genes ahead until they can drive a full lap, however I am not seeing that happen in practice.

I'm not yet sure what the problem might be, possibly too many genes that make the mutation too random? Too low of a mutation chance? Too high a mutation chance? Is it the fitness function of distance? There are so many variables in this system it is difficult to place blame. Another possibility has been swarm size too small? I've allowed this swarm to run for a really long time with a population of 50, but it doesn't seem to be doing much better either.

The computation to find the correct referencePoints and value of T is actually taking a fair bit of processing time, so much so that with more than 6 artificial drivers the player can no longer play. I know the location of the problem spot and am looking for a way to change it. Ultimately it comes down to computing the closest location on the curve of the track, which is a fairly intense iterative process and using less iterations causes inaccurate validation checks.

I certainly expected to watch the artificial drivers fall off the track, and even take some time to figure out to turn left, but I did assume they would mutate towards the correct point and make it beyond each turn. I've tried 25 reference points (50 genes) and I've tried 125 reference points (250 genes) and neither seemed more or less successful.

i see what you mean now,il see if i can find anything that will be of any help. with the variables am i right that would include tyre heat/wear ect which would then alter the cars handling at which then a human would try to adapt to that scenario


good luck with this project and its good to see people that stay dedicated to something they started to make

Well that was certainly a demoralizing day. It happens. I've spent all day attempting to adjust the fitness function, the population size, the mutation rate, crossover rate, etc etc to attempt to get the genetic algorithm working. I've even attempted to make the track wider.

In some way you can watch it improve, but then they get to the hairpin known as turn 1 and don't make around the bend. I did see a few times where one or two drivers made a fair attempt and became more fit, but randomly died out. I have found I can run it in release mode with a population of about 200 before it slows down tooo much, so maybe I'll just let it run overnight, and see if anything interesting happens. I suspect I will come back and they will still be falling off turn 1.

I've gone ahead and attached the current version of this project, it is really nothing amazing, I will let it run all night here to see what comes out, but I suspect the drivers will be falling off T1 when I wake up. There are 100 drivers and 40 reference points (80 genes).

@bishtop - Yea that would be nice but LFS does not give me that information so the artificial driver won't get that as an input. That said I am not specifically working on the LFS AIRS project at the current moment, but instead the Genetic Algorithm / 2D simulation project for testing some other thoughts out.

Edit

So after leaving it running all night, for just under 2500 generations with a population of 500, as expected they did not make it beyond turn 1. I was a little hopeful that I was wrong with my prediction and that when coming back they would be getting further along on the track. I'm writing that off as a failed attempt at a genetic algorithm for the moment. I may attempt to do the "logic controlled genetic algorithm" that I described several posts back, however as I said initially that feels like a bit of cheating. I would basically be giving the drivers a guideline that they then modify the limits of to go faster.

good luck with the project and im sure you will overcome any obstacles on the way. I really appreciate the way that you write the information here on the forum as its quite educating to people such as myself


thanks

Can I turn off the rendering? Should make things a bit faster.

No, you can't. And the bottle neck is not the rendering, the rendering take such a small amount of time (it shouldn't be vsync'd). The slow down is caused by the computing the closest point on the track, which is required for validating the lap and the interpolation between current and next reference points.

It is only called once per step per car, instead of two, which obviously helped significantly, but this is the current problem. Making it faster is possible as I stated above, but it then gets sloppy and the validation is not as accurate. Ultimately it comes down to an iterative process that happens a lot. Even if that were removed, the artificial drivers don't get much better, they never make it around turn one.

Quote from blackbird04217 :

In my first implementation of a GA each gene has a value from -1 to 1. I may later change this to be from 0 to 1, but it seems like a reasonable approach. If the application of a particular gene needs a larger range it can always be multiplied later. If there are 100 reference points along the track, then there would be 200 genes in each chromosome which the driver gets. One for steering input, one for brake/throttle input where negative is braking.

Taking this approach I will then compute the current and next reference points and interpolate their genes for the input of the car.

[...]

Any driver that falls off the track will stop moving, and fitness will remain the distance where they went off the track.

Just a few thoughts... A combination of GAs and racing seems interesting^2.

The approach you described could maybe slightly improve a prescription for already good lap around a track, but I don't think it has a chance to work from a random population. The desired steering inputs at any situation are strongly dependent on the lateral position on the track, car heading (relative to the road axis) and its current speed, not only on the reference points which you use. The "genes" should somehow express this dependence on many parameters. In this way virtual drivers evolved by the GA could be able to recover from errors. This is needed because at the beginning they will almost always be far from the perfect line and speed.

Regarding the fitness function, there should be a penalty for driving off the track, but the simulation of a single driver should not be stopped then. By stopping you are not allowing off-track virtual drivers recover and potentially shine in other places on the track.

@w126 - Yes you do have a point that drivers that fall off the road and die off do not have a chance to continue if by chance they would. Initially I was going to allow them to do this, and since it is easy to try I try to do it sometime when I get back around to it. As Keling was mentioning though, it is undesirable for the drivers to drive off track and killing them off helps with this while reducing wasted training cycles.

I do understand that the inputs do depend on the location of the driver, but in this 'simulation' with the fixed setup and all, I still feel, it should have still found a way around the track. The problem almost certainly belongs with the fitness function. Currently the fitness is based on furthest distance reached along the track. This can, and does, cause a slight issue with the hairpin turn, where the "most fit" drivers will cut as closely to the left edge without even turning...

I attempted to correct this by also adding a modifier to the fitness function that accumulated as time went on, the closer the cars direction is to the desired direction (next reference point) the more accumulated. This was added with the distance. This would reward the driver more for remaining close to the centerline while nearly always aiming at the next reference point and driving...

This failed too. The first method I thought about doing was a little more logical, where: IF distance to leftEdge < geneA THEN steering = -geneB * distance ... or something to the effect of making the genes have some modifying behavior over a logical algorithm, I chose not to go this way because it felt a little cheap to me, not quite like the AI really figured out anything except more optimal parameters for the given logic, which I found limiting.

Another thought I've had recently, is possibly to make a combination of these. Perhaps I work on the logic idea, and then instead of using the next reference point directly (as I talked about above), the driver would store in genes the desired location (left or right) of each reference point. The algorithm would then steer and accelerate toward that desired point. Essentially the genes then control the logic for the "racing line" and controls based on angle toward next point and current speed.

This again still feels a little limited, and I can already imagine the first many generations are going to be zig zagging around left and right of each reference point, but it should eventually straighten out, and likely even make a better racing line than my geometric attempt last year- because they would account for speed and braking. Not sure, it still feels slightly limited, although less so than the pure algorithmic approach.

I tried your top down racer program. Neat. It's good to start simple like this.

First, a quick symmantic matter: The term "swarm" is used in particle swarm algorithms, not genetic algorithms like you're using here. Your group of cars is a "population" or a "generation," not a "swarm."


Ok, moving along. From post 391:

Quote from blackbird04217 :

No, actually I don't necessarily feed inputs to get outputs. The artificial drivers in this simulation know about their car position in the world, and several reference points that happen to be on the center line of the track. Using this the driver will choose the current reference point, and the next reference point and get a value t where 0 <= t <= 1. When t is near 0, the car is closer to the current reference point and nearer to the next reference point when t is near 1.

The genes in the genetic algorithm then control what input the drivers have/use at each reference point and the system will interpolate between the current/next using t. It is fairly simple in implementation, and so far is not working so well. I'm not entirely sure why. In theory the drivers that make it the longest distance should survive on and continue to mutate their genes ahead until they can drive a full lap, however I am not seeing that happen in practice.

This description doesn't really say much to me about how the system is working. I assume your outputs are steering (-1 to 1) and throttle/brake (-1 to 1)? Something like this? What are your inputs? Is it the "t" value alone? Are you simply using the "t" value to come up with a new interpolated world position for a target point the car is chasing and this is all the algorithm is trying to evolve? The "t" prediction?

If you had a perfect "t" there's no guarantee the car would even know whether it should be turning left or right, so there's no point in trying to get that accurate to a zillion decimal places. You might be barking up the wrong tree on that one. If you can get more specific about how the controller is working, perhaps I can help, but it's quite nebulous at this point. Maybe it's time to post some code?

Quote from blackbird04217 :

I'm not yet sure what the problem might be, possibly too many genes that make the mutation too random? Too low of a mutation chance? Too high a mutation chance? Is it the fitness function of distance? There are so many variables in this system it is difficult to place blame. Another possibility has been swarm size too small? I've allowed this swarm to run for a really long time with a population of 50, but it doesn't seem to be doing much better either.

If a circle track racing sim only had "turn right" values available (0 to 1) and used the angular position of the right rear wheel to decide how much to turn right, it would never learn how to turn left, much less figure out when to use the brakes or throttle, regardless of the mutation rate or anything else. And because the angular position of the right rear wheel was used, it might just swerve left and right every time the wheel makes a revolution. That's not going to learn to do what you want because the wiring simply isn't there to do it. If the system isn't progressing, that's a sure sign something is fundamentally not right or there's a bug.

Quote from blackbird04217 :

No, you can't. And the bottle neck is not the rendering, the rendering take such a small amount of time (it shouldn't be vsync'd). The slow down is caused by the computing the closest point on the track, which is required for validating the lap and the interpolation between current and next reference points.

It is only called once per step per car, instead of two, which obviously helped significantly, but this is the current problem. Making it faster is possible as I stated above, but it then gets sloppy and the validation is not as accurate. Ultimately it comes down to an iterative process that happens a lot. Even if that were removed, the artificial drivers don't get much better, they never make it around turn one.

I'd think about trying to simplify that iterpolation stuff on the "t" value to speed this all up if that's really where all the work is being done. You might be overly concerned with the accuracy of the target point the cars are shooting for.

At this stage I'd suggest simply treating it as if there's a straight line segment between each reference point in the center of the track. You can generate those initial points with your bezier or whatever, but let the AI use simplified line segments connecting them all to chase after. Then use the car's relative position along a line perpendicular to that so they know how far to the left/right they are from track center. A cross and dot product or two should do the trick. Don't worry about getting 99.999999% accurate, you're just trying to find some basic wiring at this point. Compute it once very simply and forget the iterative stuff just to see if things start steering in the correct direction at some point at least.

Use that left/right "distance to center line" to compute a steering angle and forget the logic. You could also use the velocity component along that line to modify/damp it as I described earlier, but I'd start without it just to see if they at least start swerving back and forth across the centerline however chaotically. Make sure the distance to centerline computation comes out negative on one side and positive on the other so you can avoid logic flips like you mentioned.

I'd start by just picking the "current segment." When it gets close enough to the end of one segment you just switch to the next one. In fact you might as well just use the "next point" as a target. Either way, keep the cars slow enough so they can make the turns easily and just see if you can get them following that centerline somewhat well. I'm not sure, but it sounds like your learning algorithm is focused on that magical "t" point, as though if you got that point infinitely accurate the cars would all start turning left instead of right after a few minutes.

From watching the top down racer prog run while writing that last post, it looks almost like you might have a bug somewhere because it seems the population just splits in two, one turning left and one turning right. The ones that turn right aren't being eliminated from the population, and none of the little guys seem to stick that centerline worth a darn. To me it looks like they just diverge and it just so happens that there's a left turn there so some of them are correctly turning left. If this were my program I'd be looking for a negative sign where it should or shouldn't be, maybe in a logic block. I.e., do you do something different if it's on the left or right side of center, because none of the cars appear to steer toward the centerline.


To get into AI like this I'd recommend starting even simpler than you're starting. Just run constant speed "cars" that use the segment approach described earlier where you have a cross track (left/right) distance as an input into a very simple steering controller like this:

steeringAngle = k * leftRightDistance

For starters I'd leave out the AI entirely and see if you can tune that k value by hand just to see what kind of number range you're looking at for it. Then you'll see it swerving a little bit so add in the damping with the leftRightVelocity, something like this:

steeringAngle = k1 * leftRightDistance + k2 * leftRightVelocity

I would see if I can tune that reasonably well by hand just to get the little cars driving a full lap. Nevermind if they're perfect or fast.

Once I had that, I'd reintroduce the AI whose sole purpose would then be to evolve k1 and k2 values. Nevermind the logic. You already have a genetic algo in place, so if you like that you might as well stick with it. I personally prefer particle swarm because it doesn't get stuck so easily and can change a bit more fluidly. In fact just as I write this, all of your AI's except for one suddenly began turning left and are slowing down for the corner. You might just need a higher mutation rate.

What happens in a genetic algorithm is that you might have a generation where all agents' k1 = 5 when it really needs to be -1.25. The only way it'll hit k1 = -1.25 is almost blind luck, a huge number of generations made even larger by a low mutation rate. With a particle swarm algorithm you might have a bunch of agents with k1 values like this:

k1[0] = 4
k1[1] = 5
k1[2] = 6
k1[3] = 7

In a particle swarm algorithm, the entire group has a "best ever recorded for any particle of all time" k1 value which is used to push all of the agents' k1 values in that direction. Each individual agent also has it's own best k1 value. The k1 values then are nudged in the direction of both of those best values (one best for group history and one best for individual agent history). Each k1 has a velocity which is also random, so all of the k1 values will change every single generation instead of getting stuck at k1 = 5 or something while waiting for a mutation to happen. Make sense? It converges a lot faster usually with stuff like this and is simpler to write than a genetic algorithm.

In this example, the k1[0]=4 value was the best of the group, so all of the values get pushed in that direction. It's been so many years since I've done this that I forget the exact computation (I'll look it up if you want it), but basically each of those k1's has a velocity too which changes a bit in the direction that pushes them all toward 4. So on the very next step without waiting around for mutations or anything you might get this:

k1[0] = 3.9
k1[1] = 4.5
k1[2] = 5
k1[3] = 5.2

Now you have a new group best, probably a few individual bests, and things keep moving in the direction of hitting k1 = -1.25 or whatever. Suddenly all of the agents have a decent chance of improving each generation. This group of values might be completely unique in the history of the population, and they aren't sitting there for 100 generations waiting for a mutation that might just set k1[0] = -5897345 or something equally useless. What if the range of k1 values that's actually good is just between 0.02 and 0.03? With a random population of numbers between 0 and 58945 or something you'll be waiting a very long time, and if the mutations happen to not allow two places after the decimal, it will never get there anyway.

Anyway, a genetic algorithm can still work, you just might see what I'm seeing where the simulation runs huge numbers of generations and basically gets stuck until a favorable mutation happens, and depending on how the controller itself is working you might never get convergence (maybe steering left is not really possible, etc.). With particle swarm every agent is pretty much nudged in the right direction every generation. At the same time every generation is unique from every previous generation, so it's like you get the randomness without worrying about how much randomness to build into the system. You don't have to fiddle with mutation rates and that sort of stuff.