Monte Carlo Set-Membership Filtering for Nonlinear Dynamic Systems

Zhiguo Wang, Xiaojing Shen, Yunmin Zhu, Jianxin PanarXiv 2016 · DOI · arXiv

Abstract

In nonlinear dynamic systems where the underlying probability density functions (PDFs) of noise are unknown, traditional filtering methods often struggle to provide reliable state estimates. This paper proposes a novel filtering class, the Monte Carlo Set-Membership Filter (MCSMF), designed for environments with bounded noise. By integrating set-membership theory with a Monte Carlo boundary sampling technique, the MCSMF derives state predictions and measurement updates through convex optimization methods, specifically the S-procedure and Schur complement. To ensure online feasibility, nonlinear dynamics are linearized, and the resulting remainder terms are bounded by optimization ellipsoids. Numerical simulations in target tracking scenarios demonstrate that the MCSMF provides superior robustness and tighter uncertainty bounds compared to traditional Particle Filters and Extended Set-Membership Filters when noise statistics are unknown.

Introduction

Target tracking in real-world environments—such as radar systems or autonomous navigation—frequently relies on filters like the Kalman Filter or the Particle Filter. These methods are highly effective when the noise affecting sensors follows a known probability distribution. However, in many practical applications, the exact PDF of the noise is unknown, though its maximum magnitude may be bounded.

Traditional Set-Membership Filtering (SMF) addresses this by propagating uncertainty ellipsoids that guaranteed to contain the true state. However, applying SMF to nonlinear systems introduces significant mathematical challenges. Linearizing nonlinear equations produces remainder terms that are difficult to bound tightly; existing methods often use conservative "interval mathematics" (bounding errors with boxes), which can lead to uncertainty estimates that grow too large to be useful. The MCSMF aims to bridge this gap by providing a tighter, computationally efficient bounding method.

Methodology

1. Linearization and Remainder Bounding

The MCSMF approaches nonlinear dynamics by performing a Taylor expansion. Unlike standard filters that might discard higher-order terms as negligible noise, the MCSMF explicitly accounts for the "remainder" of the expansion. To maintain a deterministic guarantee that the true state remains within the estimate, the filter seeks a tight ellipsoid that encapsulates these remainder terms.

2. Monte Carlo Boundary Sampling

Finding the optimal bounding ellipsoid for a nonlinear remainder is typically an analytically intractable semi-infinite optimization problem. The authors overcome this by utilizing a Monte Carlo sampling approach. A key theoretical contribution of this work is the proof that for typical tracking sensors (e.g., range and bearing), the maximum linearization error occurs on the boundary of the uncertainty set. This "boundary shortcut" allows the filter to sample only the edges of the uncertainty ellipsoid, drastically reducing the number of samples required and making the algorithm suitable for real-time applications.

3. Convex Optimization Framework

The prediction and measurement update steps are formulated as Semi-Definite Programming (SDP) problems. By applying the S-procedure and Schur complement, the filter ensures that the resulting state ellipsoid is the smallest possible volume that still contains all feasible states given the noise bounds. This optimization is performed online using standard solvers like SeDuMi.

Experimental Setup

The algorithm was evaluated using a simulated 2D Cartesian target tracking scenario. A single sensor provided range and angle measurements of a moving target. To simulate a "messy" real-world environment where noise statistics are unknown, the authors used truncated Gaussian noise with shifted distributions and unknown means. This setup specifically challenged the filters to perform without accurate knowledge of the noise's internal PDF. The simulations were implemented in Matlab using the YALMIP toolbox.

Key Results and Discussion

Superior Robustness

The MCSMF significantly outperformed the Particle Filter in scenarios where noise PDFs were unknown. While the Particle Filter's performance degraded because its internal probabilistic assumptions were violated, the MCSMF remained stable.

Guaranteed Containment and Tightness

In trajectory analysis, the MCSMF successfully contained the true state within its uncertainty bounds at every time step. In contrast, the Particle Filter's confidence intervals occasionally failed to include the actual target. Furthermore, the MCSMF produced much tighter (less conservative) ellipsoids than the Extended Set-Membership Filter (ESMF), which relies on less precise interval mathematics.

Computational Efficiency

Despite the requirement of solving an SDP at each time step, the computational overhead of the MCSMF was found to be comparable to that of standard particle filters. This suggests that the boundary sampling technique effectively mitigates the complexity usually associated with nonlinear set-membership approaches.

Conclusion

The Monte Carlo Set-Membership Filter offers a robust alternative for nonlinear state estimation when noise distributions are poorly defined but bounded. By leveraging the geometric properties of linearization errors and efficient convex optimization, it provides deterministic guarantees that are often missing in probabilistic frameworks. Future research will explore extending this framework to multi-sensor fusion, multi-target tracking, and the optimization of sensor placement in complex networks.

Summary updated

Abstract

When underlying probability density functions of nonlinear dynamic systems are unknown, the filtering problem is known to be a challenging problem. This paper attempts to make progress on this problem by proposing a new class of filtering methods in bounded noise setting via set-membership theory and Monte Carlo (boundary) sampling technique, called Monte Carlo set-membership filter. The set-membership prediction and measurement update are derived by recent convex optimization methods based on S-procedure and Schur complement. To guarantee the on-line usage, the nonlinear dynamics are linearized about the current estimate and the remainder terms are then bounded by an optimization ellipsoid, which can be described as a semi-infinite optimization problem. In general, it is an analytically intractable problem when dynamic systems are nonlinear. However, for a typical nonlinear dynamic system in target tracking, we can analytically derive some regular properties for the remainder. Moreover, based on the remainder properties and the inverse function theorem, the semi-infinite optimization problem can be efficiently solved by Monte Carlo boundary sampling technique. Compared with the particle filter, numerical examples show that when the probability density functions of noises are unknown, the performance of the Monte Carlo set-membership filter is better than that of the particle filter.
BibTeX
@misc{wang2016monte,
  author = {Zhiguo Wang and Xiaojing Shen and Yunmin Zhu and Jianxin Pan},
  title = {{Monte Carlo Set-Membership Filtering for Nonlinear Dynamic Systems}},
  year = {2016},
  eprint = {1606.05046},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1606.05046},
}
Figure