Genetic Programming for Racing Line Optimization- Part 1

Introduction to the problem and attempts thus far

The result of 50 generations of a genetic algorithm- the racing line turns close to the apexes of both turns

Problem Overview

Sampling boxes generated for a given track (black lines), shown in pixel space
Close up of sampling boxes around a curve- nearly every spot on the track is in a box
A cubic spline (blue) made from randomly sampled input points (orange) with a smoothness factor of 0.25

Genetic Programming

CMA-ES

My Implementation

Results

The fastest spline of the last generation of 100 trials of CMA-ES
Best (left) and average (right) time of current generation, orange line is fastest time in 10000 spline sampling
Velocity profile (left) and the solution path (right) where yellow is high velocity and purple is low

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Joe Auckley

Robotics Masters student and Autonomous Vehicle researcher at the University of Pennsylvania.