Resamplers
One of the easiest performance mistakes to make when first implementing particle filters is inefficient resampling. Using off-the-shelf functions that sequentially draw samples from a categorical distribution can easily result in $O(n^2)$ or even $O(n^3)$ resampling. Fortunately simple $O(1)$ algorithms exist for this task.
In particular the algorithm described on page 110 of Probabilistic Robotics by Thrun, Burgard, and Fox has this property and also produces a low-variance set of samples distributed throughout the collection. This algorithm is implemented by the LowVarianceResampler
. Additionally ParticleFilters.jl contains the ImportanceResampler
for comparison.
ParticleFilters.ImportanceResampler
— TypeImportanceResampler(n)
Simple resampler. Uses alias sampling to attain O(n log(n)) performance with uncorrelated samples.
ParticleFilters.LowVarianceResampler
— TypeLowVarianceResampler(n)
Low variance sampling algorithm on page 110 of Probabilistic Robotics by Thrun Burgard and Fox. O(n) runtime, correlated samples, but produces a useful low-variance set.
New resamplers can be created by implementing the resample
function for a new type. This is especially important for handling particle depletion.