Resampling-free Particle Filters in High-dimensions

Akhilan Boopathy, Aneesh Muppidi, Peggy Yang, Abhiram Iyer, William Yue, Ila Fiete

Introduction: The Challenge of High-Dimensional State Estimation

Particle filters are fundamental to robotics for non-linear state estimation tasks, such as tracking a robot arm's position. However, these filters suffer from the "curse of dimensionality." Traditional methods rely on a discrete resampling step—periodically deleting low-weight particles and duplicating high-weight ones. In high-dimensional spaces, this often leads to particle deprivation, where the filter collapses onto a few points and fails to represent the true state distribution. While existing resampling-free methods attempt to mitigate this, they frequently lack the theoretical convergence guarantees necessary for reliable engineering applications.

Methods: Resampling-free Filtering via Continuous Flow

This paper introduces a novel approach that replaces discrete resampling with a continuous-time vector field. Particles are treated as a fluid flowing toward the true posterior distribution. This flow is governed by two primary forces:

  1. Gradient Descent: Particles are pulled toward regions of higher likelihood based on current observations (negative log-likelihood).
  2. Attraction-Repulsion Force: Particles interact with one another. A particle with a high likelihood exerts an attractive force on its neighbors, while those with low likelihood exert a repulsive force.
Illustration of the proposed continuous flow where particles move according to attraction-repulsion forces to maintain diversity.

By utilizing the continuity equation and a kernel-based potential function, the authors ensure this ensemble "negotiation" accurately tracks the Bayesian posterior over time without the need for "kill-and-clone" operations.

Experimental Evaluation

The proposed method was evaluated on two benchmarks:

  • Synthetic High-Dimensional Localization: A controlled environment where dimensionality was scaled up to 10 to test performance limits.
  • YCB Video Dataset: A real-world 6D pose estimation task involving 1,912 frames of a "cracker box" model, requiring simultaneous tracking of 3D translation and 3D rotation.

Performance and Robustness

The experimental results demonstrate significant improvements over standard Monte Carlo Localization (MCL) and vanilla gradient descent.

KL Divergence comparison showing the proposed method's stability across iterations (left) and superior scaling as dimensions increase (right).

Key Findings:

  • Superior Scaling: In 10-dimensional tasks, the method achieved a 10x reduction in KL divergence compared to MCL. Notably, the error does not explode as dimensions increase, providing a rare dimension-independent convergence property.
  • Sample Efficiency: Unlike MCL, which degrades rapidly as the particle count ($n$) decreases, the resampling-free method remains robust even with fewer particles.
  • Real-World Efficacy: In the YCB 6D pose estimation task, the method converged faster and reached lower error states for both rotation and translation than vanilla gradient descent.

Discussion and Future Work

While the method offers a breakthrough in high-dimensional robustness, it introduces a computational complexity of $O(n^2)$ per timestep due to the all-to-all particle interactions. Future optimizations using spatial data structures like KD-trees could mitigate this bottleneck. Additionally, the theoretical guarantees assume a reasonable initial approximation of the prior; recovery from a completely incorrect initial guess remains a challenge in high dimensions. As robotic systems grow in complexity, these high-dimensional-friendly filters provide a critical path toward more reliable autonomous state estimation.

Summary updated

BibTeX
@inproceedings{boopathy2024resampling,
  author = {Akhilan Boopathy and Aneesh Muppidi and Peggy Yang and Abhiram Iyer and William Yue and Ila Fiete},
  title = {{Resampling-free Particle Filters in High-dimensions}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2024},
  doi = {10.1109/icra57147.2024.10611361},
}
Figure