I joined the Berkeley Formula Electric Autonomous team, so I’ll share what we did in Spring 2023:

There are 3 main parts of the autonomous pipeline:

  • Perception
  • SLAM
  • Planning and Control
  • Model Predictive Control (MPC)

Perception takes camera and LiDAR data and outputs where obstacles are detected and where they are. SLAM takes obstacle data from perception and predicts where the car is based on where obstacles are. Planning and Control takes the location of the car and location of obstacles, and determines the best path to follow.

I joined the Planning and Control team so I will elaborate on PNC:

Planning and Control (PNC) Link to heading

PNC can be divided into two tasks:

  • Path finding
  • Model Predictive control

Path finding finds a path from point A to B Model Predictive control optimizes the path so that we are driving close to the racing line (optimal path for racing).

Path Finding Link to heading

Why not A* Link to heading

We did consider algorithms like A* by using delauney triangulization to discritize the space, and then searching through for a path but triangulization did not guarentee the best path would be in the search space so we abondoned the idea.

Here is an example I tested out.

This is an example race track:

example track

Run delauney Triangulization:

delauney

Remove the middle:

remove middle

Run A*around the track, and apply interpolation.

final track

Notice how if triangulization returned the red line stead of the blue line overlapping the red line, the optimal path would not even be in the search space.

We have no guarentee about the shape of the track, so this uncertainty is not acceptable.

RRT* Link to heading

Here is our first version:

RRT stands for Rapidly-Exploring Random Tree. It is used in non-Descrete search spaces to find paths. It is usually tested in mazes like this:

Here is a good video explaining RRT*:

We wrote the code in Python, to be later translated into C for performance. Unit testing helped a lot in splitting up work and reaching goals.

Here is the documentation for our RRT algorithm

It is heavily based on this paper,

We still have optimizations for RRT*, like

  • limiting the space we randomly sample points from to in front of the car
  • punishing steep angle changes

MPC Link to heading

The subteam just finished RRT* so we have not implimented MPC yet, but we are learning the math behind it.

Some papers we are reading right now include: EECS127 course reader This Tutorial