In this blog post we will take a look at the new Loco positioning TDoA outlier filter, but first a couple of announcements.
Announcements
Crazyradio PA out of stock
Some of you may have noticed that there are a lot bundles out of stock in our store, the reason is the transition from Crazyradio PA to the new Crazyradio 2.0. Most bundles contain a radio and even though the production of the new Crazyradio 2.0 is in progress, the demand for the old Crazyradio PA was a bit higher than anticipated and we ran out too early. Sorry about that! We don’t have a final delivery date for the Crazyradio 2.0 yet, but our best guess at this time is that it will be available in about 4 weeks.
Developer meeting
The next developer meeting is on Wednesday, April 5 15:00 CEST, the topic will be the Loco positioning system. We’ll start out with around 30 minutes about the Loco Positioning system, split into a presentation and Q&A. If you have any specific Loco topics/questions you want us to talk about in the presentation, please let us know in the discussions link above.
The second 30 minutes of the meeting with be for general support questions (not only the Loco system).
The outlier filter
When we did The Big Loco Test Show in December, we found some issues with the TDoA outlier filter and had to do a bit of emergency fixing to get the show off the ground. We have now analyzed the data and implemented a new outlier filter which we will try to describe in the following sections.
Why outlier rejection
In the Loco System, there are a fair amount of packets that are corrupt in one way or the other, and that should not be part of the position estimation process. There are a number of reasons for errors, including packet collisions, interference from other radio systems, reflections, obstacles and more. There are several levels of protection in the path from when an Ultra Wide Band packet is received in the Loco Deck radio to the state estimator, that aims at removing bad packets. It works in many cases, but a few bad measurements still get all the way through to the estimator, and the TDoA outlier filter is the last protection. The result of an outlier getting all the way through to the estimator is usually a “jump” in the estimated position, and in worst case a flip or crash. Obviously we want to catch as many outliers as possible to get a good and reliable position estimate and smooth flight.
The problem(s)
The general problem of outlier rejection is to decide what is a “good” measurement and what is an outlier. The good data is passed on to the state estimator to be used for estimating the current position, while the outliers are discarded. To decide if a measurement is good or an outlier, it can be compared to the current position, if it is “too far away” it is probably an outlier and is rejected. The major complication is that the only knowledge we have about the current position is the estimated position from the state estimator. If we let outliers through, the estimated position will be distorted and we may reject good data in the future. On the other hand if we are too restrictive, we may discard “good” measurements which can lead to the estimator loosing tracking and the estimated position drift away (due to noise in other sensors). It is a fine balance as we use the estimated position to determine the quality of a measurement, at the same time as the output of the filter affects the estimated position.
Another group of parameters to take into account is related to the system the Crazyflie and Loco deck are used in. The over all packet rate in a TDoA3 system is changed dynamically by the anchors, the Crazyflie may be located in a place where some anchors are hidden, or the system may use the Long Range mode that uses a lower packet rate. All these factors change the packet rate and his means that the outlier filter should not make assumptions about the system packet rate. Other factors that depend on the system is the physical layout and size, as well as the noise level in the measurements, and this must be handled by the outlier filter.
In a TDoA system, the packet rate is around 400 packets/s which also puts a requirement on resource usage. Each packet will be examined by the outlier filter, why it should be fairly light weight when it comes to computations.
Finally there are also some extra requirements, apart from stable tracking, that are “nice to have”. As a user you probably expect the Crazyflie to find its position if you put it somewhere on the ground, without having to tell the system the approximate position, that is a basic discovery functionality. Similarly if the system looses position tracking, you might expect it to recover as soon as possible, making it more robust.
The solution
The new TDoA outlier filter is implemented in outlierFilterTdoa.c. It is only around 100 lines of code, so it is not that complex. The general idea is that the filter can open and close dynamically, when open all measurements are passed on to the estimator to let it find the position and converge. Later, when the position has stabilized, the filter closes down and only lets “good” measurements through. In theory this level of functionality should be be enough, after the estimator has converged it should never lose tracking as long as it is fed good data. The real world is more complex, and there is also a feature that can open the filter up again if it looks like the estimator is diverging.
The first test in the filter is to check that the TDoA value (the measurement) is smaller than the distance between the two anchors involved in the measurement. Remember that the measurements we get in a TDoA system is the difference in distance to two anchors, not the actual distance. A measurement that is larger than the distance between the anchors is not physically possible and we can be sure that the measurement is bad and it is discarded.
The second stage is to examine the error, where the error is defined as the difference between the measured TDoA value and the TDoA value at our estimated position.
float error = measurement - predicted;This error does not really tell us how far away from the estimated position the measurement is, but it turns out to be good enough. The error is compared to an accepted distance, and is considered good if it is smaller than the accepted distance.
sampleIsGood = (fabsf(error) < acceptedDistance);
The rest of the code is related to opening and closing the filter. This mechanism is based on an integrator where the time since the last received measurement is added when the error is smaller than a certain level (integratorTriggerDistance), and remove if larger. If the value of the integrator is large, the filter closes, and if it is smaller than a threshold it opens up. This mechanism implements a hysteresis that is independent on the received packet rate.
The acceptedDistance and integratorTriggerDistance are based on the standard deviation of the measurement that is used by the kalman estimator. The idea is that they are based on the noise level of the measurements.
Feedback
The filter has been tested in our flight lab and on data recorded during The Big Loco Test Show. The real world is complex though and it is hard for us to predict the behavior in situations we have note seen. Please let us know if you run into any problems!
The new outlier filter was pushed after the 2023.02 release and is currently only available on the master branch in github (by default). You have to compile from source if you want to try it out. If no alarming problems surface, it will be the the default filter in the next release.