Celestial Collision Geometry for Reliable Crash Forecasting

Inspiration

What will a world be like, where self-driving technology has eclipsed the need for human performance? What will we have? A distributed system where we can predict the movements of every vehicle. Not with guesswork, but with precision. Our inspiration came from the way astronomers predict collisions between celestial bodies, using B-plane mapping to translate uncertainty into geometry. We thought, why can’t we do the same for cars? If we can forecast the path of an asteroid millions of miles away, we should be able to forecast a potential collision a few seconds ahead on Earth. By bringing celestial collision geometry into traffic modeling, we aim to create a system that can foresee crashes before they happen, even in the noisiest, most unpredictable conditions.

What it does

Our fundamental novelty is in applying celestial mechanics algorithms to car collision prediction. Our core algorithm is based on the Unscented Kalman Filter (UKF) method and b-planes, concepts and techniques used for the kinematics of asteroids and space objects along with the guidance and navigation of spacecraft. Decision-making by self-driving cars is based on an updated state vector (position, velocity, and heading or yaw) derived from potentially noisy measurements. Thus, on each time step, the algorithm uses a probability distribution to determine a set of sigma points (or possible state positions). These comprise an uncertainty ellipse of future states for the next time step, and are used to produce an expected future state along with a predicted covariance matrix that estimates uncertainty. Each car signals this internal state to other agents of a distributed system, which allows coordinated decision making based on universal information. Between each pair of cars, the expected velocities and positions are used to calculate a b-plane perpendicular to the expected velocity; the covariance is projected onto the b-plane, and the probability of collision is estimated within a confidence level. If two cars meet the threshold, then a collision alert is made.

To test our method's efficacy, we constructed a simulation of the downtown Austin road network and populated it with simulated self-driving agents. We tested our algorithm's ability to (1) successfully detect collisions when they occur (minimize false negatives), and (2) minimize false positives. We found an estimated >90% success rate in preventing false negatives, and an estimated >70% success rate in preventing false positives.

How we built it

We got the map data using a python library called OSMNX. This generated a GraphML file from the map data, which we then turned into JSON data. Using Pygame, we built up the map by calculating out where the building and roads would fall based on the coordinates. We then created vehicles that would drive on these roads, introducing a likeliness of collision geometry. The vehicles are instantiations of a Vehicle class, which contains an external state (sensor measurements, possibly noisy), an internal state (per-vehicle estimations of the true state, iteratively predicted and updated per time step using UKF), and covariances estimating uncertainty. All this information is available to a vehicle_simulation class, which determines if any two pairs of vehicles have a collision event between them.

Challenges we ran into

Initially we had decided to use Godot as our game engine, for its rendering ability. However, Godot provided too much overhead and too great of a learning curve for our time frame. To make up for this, we switch to using PyGame. A light weight python library for game development.

Accomplishments that we're proud of

Our method provides a novel and highly relevant approach to crash collision prediction in self-driving car systems, a problem that directly addresses the concerns of a wide section of the public about a new technology whose prevalence in everyday lives is increasing by the day. Thus, we are proud that our method may make a significant impact in the larger transition to completely automated ridesharing systems.

What we learned

We learned that seemingly disparate fields and methods (in our case, car collision prediction and celestial mechanics) can be combined in ways that we have never imagined. We also attained more experience in numerical linear algebra methods, overpass API, and Pygame.

What's next for Celestial Collision Geometry for Reliable Crash Forecasting

The most promising application of our project is in the design of networks of self-driving vehicles: our method, once developed to further decrease the false negative rate, may prove a promising infrastructural improvement for self-driving car systems like Waymo or Robotaxi, or perhaps form the basis for a new self-driving car company.