Particle Drift
For my grade 12 final, feeling ambitious, my friend and I decided to build a robot that maps rooms autonomously. Like a Roomba, but just the mapping part, not the cleaning. A SLAM algorithm from scratch. He knew hardware, so he built the car. I wrote the algorithm.
Here's how it works. Imagine a grid where each cell is about 5cm by 5cm. Each cell has a probability of being occupied (wall, furniture, whatever). When the LiDAR reads 100cm at some angle, every cell along that path gets less likely to be occupied, and the cell at 100cm gets more likely. You know, because there's something there. At the same time, the algorithm is trying to figure out where the car actually is by maintaining hundreds of "particles," each one a guess for the car's position. It nudges them based on how well their perspective matches what's been mapped so far, and the best guesses survive.
The reason you need the nudging is that encoder readings aren't perfect and sensors are noisy. So you keep randomly perturbing the particles to stay stable. All of this runs on probabilities, and this is where I learned about log odds. Using logarithms to represent probability is really clever. We built a simulation to test it, then tried it on the real hardware.