This chapter considers the nonlinear filtering problem involving noises that are unknown and bounded. We propose a new filtering method via set-membership theory and boundary sampling technique to determine a state estimation ellipsoid. In order to guarantee the online usage, the nonlinear dynamics are linearized about the current estimate, and the remainder term is then bounded by an optimization ellipsoid, which can be described as the solution of a semi-infinite optimization problem. It is an analytically intractable problem for general nonlinear dynamic systems. Nevertheless, for a typical nonlinear dynamic system in target tracking, some certain regular properties for the remainder are analytically derived; then, we use a randomized method to approximate the semi-infinite optimization problem efficiently. Moreover, for some quadratic nonlinear dynamic systems, the semi-infinite optimization problem is equivalent to solving a semi-definite program problem. Finally, the set-membership prediction and measurement update are derived based on the recent optimization method and the online bounding ellipsoid of the remainder other than a priori bound. Numerical example shows that the proposed method performs better than the extended set-membership filter, especially in the situation of the larger noise.
- nonlinear dynamic systems
- set-membership filter
- semi-definite optimization
- target tracking
Filtering techniques for dynamic systems are widely used in practiced fields such as target tracking, signal processing, automatic control, and computer vision. The Kalman filter is a fundamental tool for solving a broad class of filtering problems with linear dynamic systems. When dynamic systems are nonlinear, some well-known generalizations include the extended Kalman filter (EKF) and unscented Kalman filtering (UKF) . These methods are based on local linear approximations of the nonlinear system where the higher order terms are ignored. Most recently,  proposes box particle filter to handle interval data based on interval analysis and constraint satisfaction techniques. The advantage of the box particle filter against the standard particle filter is its reduced computational complexity [3, 4, 5]. However, most of Monte Carlo filtering techniques are based on the assumptions that probability density functions of the state noise and measurement noise are known.
Actually, when the underlying probabilistic assumptions are not realistic (e.g., the main perturbation may be deterministic), it seems more natural to assume that the state noise and measurement noise are unknown but bounded ; then,  proposed set-membership estimation technique. The idea of propagating bounding ellipsoids (or boxes, polytopes, simplexes, parallelotopes, and polytopes) for systems with bounded noises has also been extensively investigated (e.g., see recent papers [6, 8, 9, 10, 11, 12] and references therein). Most of these methods concentrate on the linear dynamic systems.
The set-membership filtering for nonlinear dynamic systems is known to be a challenging problem. Based on ellipsoid-bounded, fuzzy-approximated, or Lipschitz-like nonlinearities, several results have been made [13, 14, 15]. These results assume that the ellipsoid bounds, the coefficients of fuzzy-approximation, or Lipschitz constants are known before filtering, which limits them in real time implementation. For example, for a typical nonlinear dynamic system in a radar, the bounds of the remainder depend on the past estimates so that they cannot be obtained before filtering. Recently, the paper  gives an overview of recent developments in set-theoretic methods for nonlinear systems, with a particular focus on a two-reaction model of anaerobic digestion, and the key idea of [17, 18] consists in a combination of Bayesian and set-valued estimation concepts. To our knowledge, [19, 20] develop nonlinear set-membership filters which can estimate the bounding ellipsoid of nonlinearities in real time, and the filters are called the extended set-membership filter (ESMF) and set-valued nonlinear filter (SVNF), respectively. Both [19, 20] derive the bounds of the remainder by an outer bounding box. Actually, if the remainder can be bounded by a tighter ellipsoid and using some recent advanced optimization techniques for filtering, it should be able to derive a tighter set-membership filtering for the nonlinear dynamic system.
In this chapter, when the underlying state noises and measurement noises are unknown but bounded, we propose a tighter set-membership filtering methods via set-membership estimation theory and boundary sampling technique. In order to guarantee the online usage, the nonlinear dynamics are linearized about the current estimate, and the remainder terms are then bounded by an ellipsoid, which can be formulated as the solution of a semi-infinite optimization problem. In general, it is an analytically intractable problem when dynamic systems are nonlinear. The main contributions of the paper are summarized as follows:
For a typical nonlinear dynamic system in target tracking, we can analytically derive some regular properties for the remainder. Then, the semi-infinite optimization problem can be efficiently solved by using boundary sampling technique.
For some quadratic nonlinear dynamic systems, using the samples on all vertices of a polyhedron, we obtain a tight bounding ellipsoid, which can cover the remainder by solving a semi-definite program (SDP) problem.
The set-membership prediction and measurement update are derived based on the recent optimization method and the online bounding ellipsoid of the remainder other than a priori bound.
The rest of the paper is organized as follows. Preliminaries are given in Section 2. In Section 3, the bounding ellipsoid of the remainder set is calculated. In Section 4, the prediction step and the measurement update step of the set-membership filtering for nonlinear dynamic systems are derived, respectively. Examples and conclusions are given in Section 5 and Section 6, respectively.
2.1. Problem formulation
We consider a nonlinear dynamic system:
where is the state of system at time and is the measurement. and are nonlinear functions of , is the uncertainty of process noises or system biases, and is the uncertainty of measurement noises or system biases. They are assumed to be confined to the specified ellipsoidal sets:
where and are the
where is the center of ellipsoid and is a known symmetric positive-definite matrix. Moreover, we assume that when the nonlinear functions are linearized, the remainder terms can be bounded by an ellipsoid. Specifically, by Taylor’s theorem, and can be linearized to
where and are defined in (3), and are Jacobian matrices, and and are high-order remainders, which can be bounded in an ellipsoid for all , respectively, i.e.,
where and are the centers of the ellipsoids and , respectively, and and are the shape matrices of the ellipsoids and , respectively. Note that we do not assume that the ellipsoids and are given before filtering, and we will compute these ellipsoids online.
Suppose that the initial state belongs to a given bounding ellipsoid:
where is the center of ellipsoid and is the shape matrix of the ellipsoid which is a known symmetric positive-definite matrix.
The proposed set-membership filter mainly contains two steps: prediction step and measurement update step. The goal of prediction step is to determine a bounding ellipsoid based on the measurement at time , i.e., look for such that the state belongs to
whenever (i) is in ; (ii) the processes are bounded in ellipsoids, i.e., , ; and (iii) the remainders and . The robust measurement update step is aimed to determine a bounding ellipsoid based on the measurement at time , i.e., look for such that the state belongs to
whenever (i) is in ; (ii) the measurement noises is bounded in ellipsoid, i.e., ; and (iii) the remainders . The
3. Ellipsoidal remainder bounding
In this section, we discuss the key problem on how to adaptively determine a tighter bounding ellipsoid to cover the high-order remainders from the optimization point of view.
3.1. Ellipsoidal remainder bounding by sampling
whenever . Obviously, it is a hard problem to cover a remainder by an ellipsoid since and are generally nonlinear functions. The outer bounding ellipsoid for is not uniquely defined, which can be optimized by minimizing the size of the bounding ellipsoid. Thus, the optimization problem for the bounding ellipsoid of defined in (6) can be written as
where and and are decision variables. Since the optimization problem (11)–(12) has an infinite number of constraints, it is called a semi-infinite optimization problem in . In general, it is a NP-hard problem.
For a general nonlinear dynamic system, it is hard to solve the problem (11)–(12) . It is this reason that the literatures [23, 24] are sought to find the particular relaxations of the original optimization problem (11)–(12). One of the typical methods is based on randomization of the parameter . Specifically, to solve the problem (11)–(12), we may take some samples from the boundary and interior points of the sphere so that we can get a finite set of , and then the infinite constraint (12) can be approximated by constraints based on . Moreover, by Schur complement, an approximate bounding ellipsoid for can be derived by solving the following SDP optimization problem:
Although the randomized solution may not be feasible for all ,  has used statistical learning techniques to provide an explicit bound on the measure of the set of original constraints that are possibly violated by the randomized solution, and they prove this measure rapidly decreases to zero as is increasing. Therefore, the obtained randomized solution of the optimization problem (13)–(14) can be made approximately feasible for the semi-infinite optimization (11)–(12) by sampling a sufficient number of constraints.
Similarly, the outer bounding ellipsoid for can be derived by solving
3.2. Ellipsoidal remainder bounding by boundary sampling
In this subsection, for a typical nonlinear dynamic system in target tracking, we discuss that the remainder can be bounded by an ellipsoid via
Let us consider the following nonlinear measurement Eq. :
where is a four-dimensional state variable that includes position and velocity . Note that only depends on the first two dimensions and .
We discuss the relationship between the set and the remainder set .
The proof of Proposition 1 relies on the following three lemmas:
3.3. A tight solution
In this subsection, for some quadratic nonlinear dynamic systems, the semi-infinite optimization problem (11)–(12) may be equivalent to solving an SDP problem via sampling on all vertices of a polyhedron. Thus, we can obtain a tight bounding ellipsoid to cover the remainder.
We consider a quadratic nonlinear state equation:
where is the state of system at time , and denoted the component of ; are known parameters, .
where is the row and column of .
In summary, we can determine the remainder bounding ellipsoid by sampling as follows.
For general nonlinear functions, samples may be taken from the sphere .
For a typical nonlinear dynamic system in target tracking or nonlinear functions, samples may be taken on the boundary of the sphere .
For some quadratic nonlinear functions, samples only need vertices of a polyhedron.
4. Ellipsoidal state bounding via SDP
In this section, we present the prediction step and the measurement step of the set-membership filtering by extending El Ghaoui and Calafiore’s optimization method . The point is that when the nonlinear dynamics are linearized on the current estimate, the uncertainties of the new linearized dynamic system include the uncertain bounding ellipsoids of the remainder terms and the noises.
4.1. Prediction step
4.2. Measurement update step
Similarly, we can derive the measurement update step of the nonlinear filtering.
4.3. Sampling-based ellipsoidal bounding filter algorithm
• Step 1: (Initialization step) Set and initial values such that .
• Step 6: Set and go to Step 2.
5. Numerical example in target tracking
In this section, we compare the performance between the proposed set-membership filter and extended set-membership filter (ESMF) , which can also be implemented online for target tracking with a nonlinear dynamic system, when the state noises and measurement noises are unknown but bounded.
By considering a two-dimensional Cartesian, coordinate system as follows :
is a four-dimensional state variable that includes position and velocity , and s is the time sampling interval. The process noise and measurement noise assumed to be confined to specified ellipsoidal sets:
The target acceleration equals to 10. The parameter is used to control the uncertainty of the measurement noise. In the example, the target starts at the point with a velocity of . The center and the shape matrix of the initial bounding ellipsoid are and , respectively.
The following simulation results include three parts: the first part is about the size of the remainder bounding ellipsoid, the second part is about the root-mean-square error (RMSE) of the state estimation, and the third part is about the computation time. They are illustrated and discussed by the number of samples, the time steps, and the uncertain parameter of the measurement noise, respectively:
• In Figure 3, the log size of the remainder bounding ellipsoid is plotted as a function of the time steps with the uncertain parameter . It shows that the size of the new method is much smaller than that of the ESMF, i.e., the new method derives a tighter ellipsoid to cover the remainder. Moreover, we use 30 samples to calculate a remainder bounding ellipsoid on a time step based on solving the optimization problem (15)–(16). The corresponding bounding ellipsoid is presented in Figure 4. It shows that the bounding ellipsoid can cover all points of the remainder set with a very small size. In Figures 5 and 6, the average size of the remainder bounding ellipsoid through the time steps 1–20 is plotted as a function of the uncertain parameter of the measurement noise. The larger means that the measurement noise is more uncertain. Thus, Figures 5 and 6 show that when the uncertainty of the measurement noise is increasing, the size of the remainder bounding ellipsoid of ESMF is quickly increasing; however, that of the new method is slowly increasing and relatively stable.
• RMSE of the state estimation along the position direction is plotted as a function of the time steps in Figure 7. It shows that RMSE of the new method is less than that of ESMF. The reason may be that the new method derives a tighter ellipsoid to cover the remainder, which can be seen in the Figure 4. Figure 7 also shows that RMSEs of the proposed filter based on 30 and 40 samples are almost same. The reason may be that the remainder bounding ellipsoid is same when the number of samples is more than 30. In Figure 8, the average RMSE of the state estimation through the time steps 1 to 20 is plotted as a function of the uncertain parameter . It shows that the average RMSE of the state estimation based on the new method is also less than that of ESMF. The larger uncertain parameter is a better performance of the new method than that of ESMF. In summary, Figures 5–8 indicate that the new method performs much better than ESMF, especially in the situation of the larger noise.
• Since the predictive step and measurement update step of the new method are calculated by solving an SDP, the computation time of the new method is greater than that of ESMF, which can be seen in the right of Figure 9, but it may be tolerated and be done in polynomial time.
In order to deal with the nonlinear dynamic systems with unknown but bounded noise, we have proposed a new filtering method via set-membership theory and boundary sampling technique to determine a state estimation ellipsoid. To guarantee the online usage, the nonlinear dynamics are linearized about the current estimate, and the remainder terms are then bounded by an ellipsoid, which can be written as the solution of a semi-infinite optimization problem. For a typical nonlinear dynamic system in target tracking, the semi-infinite optimization problem can be efficiently approximated by a randomized method. Moreover, for some quadratic nonlinear dynamic systems, using the samples on all vertices of a polyhedron, we obtain a tight bounding ellipsoid, which covers the remainder by solving an SDP problem. Finally, the set-membership prediction and measurement update are derived based on the recent optimization method and the online bounding ellipsoid of the remainder other than a priori bound, so that a tighter set-membership filter can be achieved. Numerical example shows that the proposed method performs much better than ESMF, especially in the situation of the larger noise. Future work will include that the multisensor fusion, multiple target tracking, and various applications such as sensor management and placement for structures and different types of wireless networks.
This work was supported in part by the NSFC No. 61673282, the open research funds of BACC-STAFDL of China under Grant No. 2015afdl010, and the PCSIRT16R53.
Bar-Shalom Y, Li X, Kirubarajan T. Estimation with Applications to Tracking and Navigation. New York: Wiley; 2001
Abdallah F, Gning A, Bonnifait P. Box particle filtering for nonlinear state estimation using interval analysis. Automatica. 2008; 44:807-815
Gning A, Ristic B, Mihaylova L, Abdallah F. An introduction to box particle filtering. IEEE Signal Processing Magazine. 2013; 30:166-171
Freitas AD, Mihaylova L, Gning A, Angelova D, Kadirkamanathan V. Autonomous crowds tracking with box particle filtering and convolution particle filtering. Automatica. 2016; 69:380-394
Merlinge N, Dahia K, Piet-Lahanier H. A box regularized particle filter for terrain navigation with highly non-linear measurements. IFAC-Papers OnLine. 2016; 49:361-366
Polyak BT, Nazin SA, Durieu C, Walter E. Ellipsoidal parameter or state estimation under model uncertainty. Automatica. 2004; 40:1171-1179
Schweppe FC. Recursive state estimation: Unknown but bounded errors and system inputs. IEEE Transactions on Automatic Control. 1968; 13:22-28
Jaulin L. Nonlinear bounded-error state estimation of continuous-time systems. Automatica. 2002; 38:1079-1082
Rohou S, Jaulin L, Mihaylova L, Bars FL. Guaranteed computation of robot trajectories. Robotics and Autonomous Systems. 2017; 97:76-84
Calafiore G, El Ghaoui L. Ellipsoidal bounds for uncertain equations and dynamical systems. Automatica. 2004; 40:773-787
Shen X, Zhu Y, Song E, Luo Y. Minimizing Euclidian state estimation error for linear uncertain dynamic systems based on multisensor and multi-algorithm fusion. IEEE Transactions on Information Theroy. 2011; 57:7131-7146
Durieu C, Walter E, Polyak BT. Multi-input multi-output ellipsoidal state bounding. Journal of Optimization Theory and Applications. 2001; 111:273-303
Shamma JS, Tu K. Approximate set-valued observers for nonlinear systems. IEEE Transactions on Automatic Control. 1997; 42:648-658
Morrell DR, Stirlling WC. An extended set-valued Kalman filter. Proceeding of ISIPTA. 2003:396-407
Wei G, Wang Z, Shen B. Error-constrained filtering for a class of nonlinear time-varying delay systems with non-Gaussian noises. IEEE Transaction on Automatic Control. 2010; 55:2876-2882
Chachuat B, Houska B, Paulen R, Perić N, Rajyaguru J, Villanueva ME. Set-theoretic approaches in analysis, estimation and control of nonlinear systems. IFAC-PapersOnLine. 2015; 48:981-998
Noack B, Klumpp V, Hanebeck UD. State estimation with sets of densities considering stochastic and systematic errors. In: Proceedings of the IEEE International Conference on Information Fusion; 2009
Noack B, Klumpp V, Petkov N, Hanebeck UD. Bounding linearization errors with sets of densities in approximate Kalman filtering. Proceedings of the IEEE International Conference on Information Fusion. 2010
Scholte E, Campbell ME. A nonlinear set-membership filter for on-line applications. International Journal of Robust and Nonlinear Control. 2003; 13:1337-1358
Calafiore G. Reliable localization using set-valued nonlinear filters. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans. 2005; 35:189-197
Boyd S, Vandenberghe L. Convex Optimization. Cambridge, United Kingdom: Cambridge University Press; 2004
Ben-Tal A, Nemirovski A. Robust convex optimization. Mathematics of Operations Research. 1998; 23:769-805
Still G. Discretization in semi-infinite programming: The rate of convergence. Mathematical programming. 2001; 91:53-69
Calafiore G, Campi M. Uncertain convex programs: Randomized solutions and confidence levels. Mathematical Programming. 2005; 102:25-46
Spivak M. Calculus on manifolds. New York: Benjamin; 1965
El Ghaoui L, Calafiore G. Robust filtering for discrete-time systems with bounded noise and parametric uncertainty. IEEE Transactions on Automatic Control. 2001; 36:1084-1089
Nesterov Y, Nemirovski A. Interior point polynomial methods in convex programming: Theorey and applications. Philadelphia, PA: SIAM;1994
Vandenberghe L, Boyd S. Semidefinite programming. SIAM Review. 1996; 38:49-95
Lan G, Lu Z, Monteiro RD. Primal-dual first-order methods with iteration-complexity for cone programming. Mathematical Programming. 2011; 126:1-29