livn

The goal is to simulate a self-piloting spaceship that can navigate through an asteroid field without collisions. I implemented a Kalman filter that estimates the state of the system — the asteroids’ future positions. Knowing where each asteroid is heading, I then programmed the spaceship to choose the best heading and velocity at each time step as not to crash into any asteroids.

Estimating future locations of asteroids is the most important part of the project and is calculated through Kalman filtering. This is a technique to estimate the state of a system given measurements over time. For this project, the measurements are the asteroids’ coordinates (with measurement noise) and the state we estimate are the coordinates of each asteroid in the next time step.

The Pilot class controls the spaceship’s flight path and contains three methods:

1. observe_asteroids is called once per time step and informs the spaceship of the latest asteroid measurements.
2. estimate_asteroid_locs predicts the location of each asteroid in the next time step after observing asteroids.
3. next_move chooses the best move given the current state of the spaceship and system.

The Pilot class is provided an array of asteroid coordinates that are currently in the field. In a real-life scenario, we can imagine the spaceship having a sensor or radar to make these measurements. All measurements, including the one passed into the Pilot class, come with noise from the sensors, meaning these measurements may not be 100% accurate. We have to take this error into account as Gaussians when calculating our Kalman filter.

In a Kalman filter, every new measurement, observe_asteroids, makes us more confident about the asteroid coordinates. However, every prediction step, estimate_asteroid_locs, throws some uncertainty into the equation. The Kalman filter continually cycles through these two steps to produce the best estimate of where each asteroid could be at the current time step, but this is merely a guess and can be off.

The recording above shows red dots floating around the asteroids. These red dots are estimates that are too far away from the asteroid’s actual location to be accurate. Notice how the estimates get more accurate over time as state measurements accumulate.

To mitigate uncertainty, I have my spaceship wait at the starting area for a few time steps while the Kalman filter calibrates. Once I am confident that I have localized all the asteroids in the field to a certain margin of error, I let loose the spaceship to fly itself. The Pilot then calls next_move at each time step while considering the coordinate estimates given by the Kalman filter.

These test runs show exciting results as the spaceship zips around, narrowly avoiding catastrophic collisions.