Ancestry Tree Clustering for Particle Filter Diversity Maintenance

Abstract--We propose a method for linear-time diversity maintenance in particle filtering. It clusters particles based on ancestry tree topology: closely related particles in sufficiently large subtrees are grouped together . The main idea is that the tree structure implicitly encodes similarity without the need for spatial or other domain-specific metrics. This approach, when combined with intra-cluster fitness sharing and the protection of particles not included in a cluster, effectively prevents premature convergence in multimodal environments while maintaining estimate compactness. We compare the performance to several diversity maintenance algorithms from the literature, including Deterministic Resampling and Particle Gaussian Mixtures. Our algorithm achieves high success rates with little to no negative effect on compactness, showing particular robustness to different domains and challenging initial conditions. These samples are propagated using system motion dynamics and weighted based on measurements. Resampling typically follows to produce uniform weights and concentrate computation on high-likelihood areas. Although PFs can, in principle, represent distributions of any shape, their stochastic, sample-based nature often makes it difficult to maintain the correct density over time [1], [2]. Loss of diversity is referred to as particle degeneracy when it occurs in the weights, and particle impoverishment when it occurs in the states. Diversity can be lost on a micro (local) or macro (global) level. Local loss can often be mitigated by local refinement [2].