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