Our autonomous path planning subsystem determines how to navigate through a track. This can be broken down into two subproblems: how to navigate through an unknown track, and how to navigate a known track as fast as possible.

When navigating through an unknown track, we receive information about where cones are located, and our task is to define the track using this limited information. To do this, we build and manage two sorted arrays of cones defining the left and right sides of the track, which orders the cones to determine the track boundaries. An original algorithm is used to sort cones into either array by using a cost function to select the best pair of left and right cones to append to the arrays, which takes advantage of how sides of the track are parallel and of a constant known width. This approach is robust to various track features including hairpins, and functions even when cone types cannot be determined. Once we have defined the two sides of the track, we can use spline interpolation to find a centreline for the vehicle to follow.

Discovery Lap

Path Planning on a discovery lap

Once the track layout is known, we can calculate a path through the track which allows the car to navigate the track in the minimum amount of time. We begin by discretizing the track into a set of transverse lines. For each transverse line, we assign a target position and velocity for the car to reach as it passes through this line. Using leapfrog integration, we find the time taken to move between each transverse line, which we can use to define the cost function as the total sum of these time deltas. The cost function also includes soft constraints on parameters such as acceleration and jerk to ensure the calculated path is within the physical capabilities of our car. Finally, we use the Levenberg-Marquardt optimisation algorithm to solve for the optimal transverse line parameters, and hence an optimal racing line for any given discretized track.

M19-D Path Planning

Path Planning on a known track

Overall, the path planning algorithm obtains information about cones and the car state from the perception algorithms, and processes and reorganises the data to determine the path the car should follow. Ultimately, this is the beginning of the car’s decision-making process, and it is vital that we get this correct so that we do not misinterpret the track and drive off course.

by Kerry He