My old boss, Dr Gordon Wyeth from the University of Queensland has implemented a 100 point particle filter onboard the NXT.Basically the particle filter realizes that you won't have perfect odometery readings all the time, and so uses 3 ultrasonic sensors to 'correct' errors and stay on track.
"Localisation is the process of working out where you are, so localisation for a robot is having the robot work out where it is using the readings from its own sensors. Sounds easy, but it can be surprisingly challenging. The big problem stems from the fact that the robot's wheels have to slip to make the robot move (a fact of physics), so careful measurement of the motors' rotation sensors is not going to help you. Fitting streams of range readings from ultrasound or infrared sensors has problems with noise and error, too. So, over the last decade or so, roboticists have pretty well agreed that the best way to localise is to combine the all of robot's sensor readings over time using probability theory. Sounds challenging, but it can be surprisingly easy.
I've been using a probabilistic filter called a particle filter to localise a robot built around the NXT. The other name for this style of probabilistic localisation is Monte-Carlo Localisation, so called because it relies on finding the best odds from a series of seemingly random outcomes. All of the code is written in Robot-C and runs on-board the NXT in real time. This surprised me. Particle filters are supposed to be horribly computationally intensive with lots of floating point math, so surely you can't expect it to run on a LEGO brick ... but run it did."
He gives a great explanation of particle filters along with video of it in operation.
Source code in RobotC is provided for those that want to look under the hood.
--
Damien Kee