Genetic Programming for Racing Line Optimization- Part 1
Introduction to the problem and attempts thus far
The optimal racing line is the path around a track that allows the racer to traverse the course in the minimum time possible. Competitive racing drivers strive to perceive this optimal trajectory and stick to it the best they can. I’ve decided to implement various ways to compute this optimal path as well as the ideal speed at each point for the F1/10 cars, given a bird’s eye view of the track’s boundaries.
Problem Overview
The optimal racing line is neither the shortest path around a track nor the path with the highest average velocity. To solve this problem, I am searching over many potential paths and evaluating them by finding the fastest possible velocity profile (velocity at each point on the path) and then computing the time to traverse the path. To search for paths, I computed sampling boxes throughout the track that cover the entirety of the track’s feasible space. (Note- I’m using an adaptation of OpenAi Gym’s random track generator)
I randomly select a point in each box and fit a cubic spline to the array of points. I then check every point on the spline to see if it is inside the track (valid) or on one of the black track lines (invalid). Invalid tracks are rejected. I experimented with combining boxes on the straightaways to decrease the dimension of the search space, but found that this decreases the chance of randomly generating a valid spline- as bad as 1 in 100. After experimenting with the smoothing factor of the spline (best found was 0.25) I am able to obtain a valid spline once in every 3.62 random samples, despite the substantial overlap between boxes.
Now that I’ve described my sampling method, I’ll explain the approach I’ve tried so far. These sampling boxes may seem a bit elaborate for standard genetic programming, but I made them with several approaches to this problem in mind, so it should be useful later on as well.
Genetic Programming
To start, I’ve explored various genetic algorithms for optimization problems. A genetic algorithm is an iterative algorithm inspired by natural selection, where an initial population of solutions is evolved to optimize some criterion. A fitness function must be defined to evaluate the solutions- this is usually the objective function of the optimization problem. Each iteration, the “fittest” members of the population are selected to be the basis of the next generation. The features of the fittest solutions are combined (like genes) through a crossover operation and mutated stochastically to form a new set of solutions. There are many ways to define the fitness function, selection process, and crossover and mutator operations, which is explored in the field of genetic programming. More on these concepts linked in a good read here.
CMA-ES
I decided to start with implementing the Covariance-Matrix Adaptation Evolution Strategy (CMA-ES). A good description of this algorithm (and others) is covered here. In short, the algorithm adaptively adjusts the search space depending on the variance of the “fit” members of the population from the rest of the population. So, when the best solutions in the population are far from the generation’s mean, the variance for the next generation is increased, and vice versa.
My Implementation
The fitness function I am using is just the time to traverse the track. To calculate this, I needed to compute the velocity profile for the given path. For now, I’m using a simple method using the instantaneous radius of curvature at each point of the spline. I calculate this using the equation for a parametric curve described here. I then calculated the fastest possible speed using the radius of curvature, maximum lateral gripping force (downforce multiplied by coefficient of friction), and mass of the car, and capped the speed at a maximum value. The resulting velocity profile is very jagged and not physically possible — it needs to be adjusted for the amount of acceleration and braking that the car can actually provide.
For selection, I am selecting the top 25% of the current generation to be the basis for the next generation, and I implemented mutation and crossover in the standard CMA-ES fashion. Lastly, I’m using a population size of 100, and it stops computing new generations after 50 generations.
Results
As an easy benchmark, I generated 10000 random feasible splines and calculated statistics based off their performance:
Average time: 20.852 seconds
Fastest time: 18.956 seconds
Slowest time: 25.646 seconds
Standard deviation of times: 0.751 seconds
I ran my implementation of CMA-ES 100 times, and calculated statistics based off the last generation of each trial:
Average mean time: 18.632 seconds
Average fastest time: 18.628 seconds
Average slowest time: 18.683 seconds
Average standard deviation: 0.0129 seconds
The last generation of my CMA-ES is on average entirely faster than the 1 in 10000 spline by nearly 3 tenths of a second (which is a long time in racing). However, there is still room for improvement. The CMA-ES algorithm is pretty good at finding the global optimum, however in this nearly 200 dimensional space, it has not been able to do so. This image shows that it converges to a variety of local optima.
Here are images from a particularly good output from the algorithm, which was evaluated at just 18.482 seconds:
From these images, you can see that the algorithm converges very quickly. However, the path is still a ways from being globally optimal, as it still does not entirely hug the apexes as expected and make full use of the track’s width on the straights. Also, you can see how the velocity profile is far from physically possible.
Next Steps
- More realistic dynamics: The velocity profile needs to be corrected using details about the car’s acceleration and braking, and I need to reject spline samples that contain a turning radius less than the car is capable of
- Tune parameters: Changing parameters like population size, generation number, and population selection cutoff could improve results
- Get out of local optima: A feature of this algorithm is that the population’s diversity decreases quickly as it converges to a solution. If that solution is not globally optimal, we want to maintain diversity. One way to do that is to cluster solutions into “species” and keep a portion of each species between generations, and I will be exploring this approach
- Other approaches: I’m not planning on solely using CMA-ES on this problem- I am reading about other genetic algorithms and will implement a few more to see what works best
Stay tuned to the F1/10 blog for updates!
