Open access peer-reviewed chapter

Monte Carlo Set-Membership Filtering for Nonlinear Dynamic Systems

Written By

Zhiguo Wang, Xiaojing Shen and Yunmin Zhu

Submitted: 23 November 2017 Reviewed: 25 January 2018 Published: 18 July 2018

DOI: 10.5772/intechopen.74387

From the Edited Volume

Nonlinear Systems - Modeling, Estimation, and Stability

Edited by Mahmut Reyhanoglu

Chapter metrics overview

1,288 Chapter Downloads

View Full Metrics

Abstract

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.

Keywords

  • nonlinear dynamic systems
  • set-membership filter
  • randomization
  • semi-definite optimization
  • target tracking

1. Introduction

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) [1]. These methods are based on local linear approximations of the nonlinear system where the higher order terms are ignored. Most recently, [2] 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 [6]; then, [7] 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 [16] 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.

Advertisement

2. Preliminaries

2.1. Problem formulation

We consider a nonlinear dynamic system:

xk+1=fkxk+wk,E1
yk=hkxk+vk,E2

where xkRn is the state of system at time k and ykRn1 is the measurement. fkxk and hkxk are nonlinear functions of xk, wkRn is the uncertainty of process noises or system biases, and vkRn1 is the uncertainty of measurement noises or system biases. They are assumed to be confined to the specified ellipsoidal sets:

Wk=wk:wkTQk1wk1Vk=vk:vkTRk1vk1,

where Qk and Rk are the shape matrices of the ellipsoids Wk and Vk, respectively, which are known as symmetric positive-definite matrices. At time k given that xk belongs to a current bounding ellipsoid:

Ek=xRn:xx̂kTPk1xx̂k1=xRn:x=x̂k+EkukPk=EkEkTuk1E3

where x̂k is the center of ellipsoid Ek and Pk 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, fk and hk can be linearized to

fkx̂k+Ekuk=fkx̂k+JfkEkuk+Δfkuk,E4
hkx̂k+Ekuk=hkx̂k+JhkEkuk+Δhkuk,E5

where Ek and uk are defined in (3), Jfk=fkxkxx̂k and Jhk=hkxkxx̂k are Jacobian matrices, and Δfkuk and Δhkuk are high-order remainders, which can be bounded in an ellipsoid for all uk1, respectively, i.e.,

ΔfkukEfk=xRn:xefkTPfk1xefk1,E6
=xRn:x=efk+BfkΔfkPfk=BfkBfkTΔfk1,E7
ΔhkukEhk=xRn1:xehkTPhk1xehk1,E8
=xRn1:x=ehk+BhkΔhkPhk=BhkBhkTΔhk1,E9

where efk and ehk are the centers of the ellipsoids Efk and Ehk, respectively, and Pfk and Phk are the shape matrices of the ellipsoids Efk and Ehk, respectively. Note that we do not assume that the ellipsoids Efk and Ehk are given before filtering, and we will compute these ellipsoids online.

Suppose that the initial state x0 belongs to a given bounding ellipsoid:

E0=xRn:xx̂0TP01xx̂01,E10

where x̂0 is the center of ellipsoid E0 and P0 is the shape matrix of the ellipsoid E0 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 Ek+1k based on the measurement yk at time k, i.e., look for x̂k+1k,Pk+1k such that the state xk+1 belongs to

Ek+1k=xRn:xx̂k+1kTPk+1k1xx̂k+1k1,

whenever (i) xk is in Ek; (ii) the processes wk,vk are bounded in ellipsoids, i.e., wkWk, vkVk; and (iii) the remainders ΔfkukEfk and ΔhkukEhk. The robust measurement update step is aimed to determine a bounding ellipsoid Ek+1 based on the measurement yk+1 at time k+1, i.e., look for x̂k+1,Pk+1 such that the state xk+1 belongs to

Ek+1=xRn:xx̂k+1TPk+11xx̂k+11,

whenever (i) xk+1 is in Ek+1k; (ii) the measurement noises vk+1 is bounded in ellipsoid, i.e., vk+1Vk+1; and (iii) the remainders Δhk+1uk+1Ehk+1. The key issue is to determine two tight bounding ellipsoids Efk and Ehk in real time so that the filtering algorithm can be implemented online.

Advertisement

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

By (4)(5), the high-order remainders are

Δfkuk=fkx̂k+Ekukfkx̂kJfkEkuk,Δhkuk=hkx̂k+Ekukhkx̂kJhkEkuk,

whenever uk1. Obviously, it is a hard problem to cover a remainder by an ellipsoid since fk and hk are generally nonlinear functions. The outer bounding ellipsoid for Δfkuk is not uniquely defined, which can be optimized by minimizing the size fP of the bounding ellipsoid. Thus, the optimization problem for the bounding ellipsoid of Δfkuk defined in (6) can be written as

minfPfkE11
subjecttoΔfkukefkTPfk1Δfkukefk1,foralluk1.E12

where Pfk=BfkBfkT and efk and Pfk are decision variables. Since the optimization problem (11)(12) has an infinite number of constraints, it is called a semi-infinite optimization problem in [21]. In general, it is a NP-hard problem.

Remark 1. In practice, we want to achieve a state estimation ellipsoid by minimizing its “size” at each time; it is a function of the shape matrix P denoted by fP. If we choose trace function, i.e., fP=trP, it means the sum of squares of semiaxes lengths of the ellipsoid E. The other common “size” of the ellipsoid is logdetP, which corresponds to the volume of the ellipsoid E.

For a general nonlinear dynamic system, it is hard to solve the problem (11)(12) [22]. 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 uk. Specifically, to solve the problem (11)(12), we may take some samples from the boundary and interior points of the sphere uk1 so that we can get a finite set of uk1,,ukN, and then the infinite constraint (12) can be approximated by N constraints based on uk1,,ukN. Moreover, by Schur complement, an approximate bounding ellipsoid for Δfkuk can be derived by solving the following SDP optimization problem:

minfPfkE13
subjectto1ΔfkukiefkTΔfkukiefkPfk0i=1,,N.E14

Although the randomized solution may not be feasible for all uk1, [24] 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 N 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 Δhkuk can be derived by solving

minfPhkE15
subjectto1ΔhkukiehkTΔhkukiehkPhk0,i=1,,N.E16

Remark 2. Note that the bounding ellipsoid of [19] is derived by interval mathematics. We derive the bounding ellipsoid by solving a semi-infinite optimization problem. Figure 1 illustrates the difference of two methods. It is obvious to see that the bounding ellipsoid derived by solving the SDP (13) is tighter than that obtained by interval mathematics. The cumulative effect of the conservative bounding ellipsoid at each time step may yield divergence of a filtering.

Figure 1.

(Top) The bounding ellipsoid is derived by covering the solid points of the remainder which are obtained by Monte Carlo sampling. (Bottom) The bounding ellipsoid is derived by covering the vertices of the rectangle obtained by interval mathematics [19].

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 boundary sampling for target tracking. Thus, the new method can reduce the computation complexity efficiently in the bounding step.

Let us consider the following nonlinear measurement Eq. [1]:

hx=x1a2+x2b2arctanx2bx1a,a,bRE17

where x is a four-dimensional state variable that includes position and velocity xyẋẏT. Note that hx only depends on the first two dimensions x1 and x2.

We discuss the relationship between the set uk1uk=uk1uk2 and the remainder set Δhk+1uk:uk1.

Proposition 1. If we let the remainder gu=hx̂+Euhx̂JhEu where hx̂ is defined in (17), E is a Cholesky factorization of a positive-definite P such that ellipsoid x=x̂+Eu:u1 does not intersect with the radial x:x1<=ax2=b, and then the boundary of the remainder set S=gu:u1 belongs to the set gu:u=1.

Remark 3. Note that the ellipsoid x=x̂+Eu:u1 does not intersect with the radial. x:x1<=ax2=b is a weak condition, which is in order to satisfy the continuity of gu, and we can verify the condition by using the distance from the ellipsoid center x̂ to the radial. Moreover, if the condition is violated, i.e., the true target is near the radial, we can transform the data to a new coordinate system where the target is far way the radial, and then the assumption can be satisfied.

The proof of Proposition 1 relies on the following three lemmas:

Lemma 1. (Remainder lemma). The determinant of the derivative of the remainder gu is not less than 0, and the equality holds if and only if cu1+du2=0, where c=E11x̂2bE21x̂1a, d=E12x̂2bE22x̂1a, and Eij are the entries of the ith row and the jth column of the matrix E. Meanwhile, if cu1+du2=0, then gu=0.

Lemma 2. If the sets S1S2=S3S4, S3S4=, and S1S3, then S4S2.

Lemma 3. (Inverse function theorem [25]) Suppose that φ:RnRn is continuously differentiable in an open set containing u and detφu0, then there is an open set V containing u and open set W containing φu such that φ:VW has a continuous inverse φ1:WV which is differentiable and for all yW satisfies φ1y=φφ1y1.

Example 1. To illustrate Proposition 1, we give an example as follow: if a=50, b=100, x̂=80130T, and P=diag5001000, it is easy to check that gu is continuously differentiable in set S1=u:u1. We divide S1 into three parts, i.e., S1=A1B1C1, where A1=u:cu1+du2<0u1, B1=u:cu1+du2>0u1, and C1=u:cu1+du2=0u1. Meanwhile, we can also divide S into the corresponding parts, such that A=gu:uA1, B=gu:uB1, C=gu:uC1, and then S=ABC.

Figure 2 shows the separation area of the circle and their corresponding area of gu. Three observations can be made as follows:

• The remainder set is the union of two sets.

• The (red) line C1 is mapped to the point 0.

• The boundary of S belongs to the set gu:u=1.

In summary, when we take samples from the boundary, they are sufficient to derive the outer bounding ellipsoids of the remainder set. Therefore, based on Proposition 1, the computation complexity in the bounding step of the new method can be reduced much more.

Remark 4. In order to further reduce the samples and cover the remainder set at the same time, we can heuristically enlarge the sampling area, such as uk=1.1; then, the remainder set becomes a little larger. If we derive an ellipsoid to cover the little larger remainder, then this ellipsoid can cover the original remainder set Δhk+1uk:uk1.

Figure 2.

(Left) The separation of circle. (Right) The corresponding area of gu.

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:

fkxk=α10000α200000000αnxk12xk22xkn2E18

where xkRn is the state of system at time k, and xki denoted the ith component of xk; αi are known parameters, i=1,,n.

Proposition 2. If we let the high-order remainder Δfkuk=fx̂k+Ekukfx̂kJfkEkuk where uk1, assume that fkx̂k is a quadratic function defined in (18) and Ek is a diagonal matrix; then, a tight bounding ellipsoid can be derived to cover the high-order remainder Δfkuk by solving the following optimization problem:

minfPfkE19
E20
fori=1,2,,n.

where Ekii is the ith row and jth column of Ek.

In summary, we can determine the remainder bounding ellipsoid by sampling as follows.

  1. For general nonlinear functions, samples may be taken from the sphere uk1.

  2. For a typical nonlinear dynamic system in target tracking or nonlinear functions, samples may be taken on the boundary of the sphere uk1.

  3. For some quadratic nonlinear functions, samples only need vertices of a polyhedron.

Advertisement

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 [26]. 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

Proposition 3. At time k+1, based on measurements yk, the bounding ellipsoids of the state, and the remainders Ek, Efk, and Ehk, a predicted bounding ellipsoid Ek+1k=x:xx̂k+1kTPk+1k1xx̂k+1k1 can be obtained by solving the optimization problem in the variables Pk+1k and x̂k+1k and nonnegative scalars τu0,τw0,τv0,τf0,τh0:

minfPk+1kE21
subjecttoτu0,τw0,τv0,E22
τf0,τh0,Pk+1k0,E23
Pk+1kΦk+1kΨk+1kΦk+1kΨk+1kTΨk+1kTΞΨk+1k0,E24

where

Φk+1k=fkx̂k+efkx̂k+1kJfkEkI0Bfk0,0Rn,n1,E25
Ψk+1k=hkx̂k+ehkykJhkEk0I0Bhk.E26

Ψk+1k is the orthogonal complement of Ψk+1k. Ek is the Cholesky factorization of Pk, i.e., Pk=EkEkT. efk, ehk, Bfk, and Bhk are denoted by (7) and (9), respectively. Jfk=fkxkxx̂k and Jhk=hkxkxx̂k:

Ξ=diag1τuτwτvτfτhτuIτwQk1τvRk1τfIτhI.E27

Remark 5. The objective function (21) is aimed at minimizing the shape matrix of the predicted ellipsoid, and the constraints (22)(24) ensure that the true state is contained in predicted bounding ellipsoid Ek+1k. Notice that if fP=trP, the optimization problems (13)(16), (21)(24), and (28)(31) are SDP problems, which can be efficiently solved by modern interior-point methods [27]. According to the guidelines in [28], the computational complexity of solving an SDP problem is Omaxmn4n1/2log1/ϵ, where n is the number of the states. With the development of convex optimization technology technique, one can also use first-order optimizing algorithm. The computational complexity may be reduced further (see [29]).

4.2. Measurement update step

Similarly, we can derive the measurement update step of the nonlinear filtering.

Proposition 4. At time k+1, based on measurement yk+1, the predicted bounding ellipsoid Ek+1k, and the bounding ellipsoid of the remainder Ehk+1, an estimated bounding ellipsoid Ek+1=x:xx̂k+1TPk+11xx̂k+11 can be obtained by solving the optimization problem in the variables Pk+1 and x̂k+1 and nonnegative scalars τu0,τv0,τh0:

minfPk+1E28
subjecttoτu0,τv0,τh0,E29
Pk+10,E30
Pk+1Φk+1Ψk+1Φk+1Ψk+1TΨk+1TΞΨk+10,E31

where

Φk+1=x̂k+1kx̂k+1Ek+1k00,0Rn,n1,E32
Ψk+1=hk+1x̂k+1k+ehk+1yk+1Jhk+1kEk+1kIBhk+1.E33

Ψk+1 is the orthogonal complement of Ψk+1. Ek+1k is the Cholesky factorization of Pk+1k, i.e., Pk+1k=Ek+1kEk+1kT. x̂k+1k is the center of the predicted bounding ellipsoid Ek+1k. ehk+1 and Bhk+1 are denoted by 9 at the time step k+1. Jhk+1k=hk+1xkxx̂k+1k:

Ξ=diag1τuτvτhτuIτvRk+11τhI.E34

4.3. Sampling-based ellipsoidal bounding filter algorithm

• Step 1: (Initialization step) Set k=0 and initial values x̂0P0 such that x0E0.

• Step 2: (Bounding step) Take samples uk1,,ukN from the sphere uk1, and then determine two bounding ellipsoids to cover the remainders Δfk and Δhk by (13)(14) and (15)(16), respectively.

• Step 3: (Prediction step) Optimize the center and shape matrix of the state prediction ellipsoid x̂k+1kPk+1k such that xk+1kEk+1k by solving the optimization problem (21)(24).

• Step 4: (Bounding step) Take samples uk+1k1,,uk+1kN from the sphere uk+1k1, and then determine one bounding ellipsoid to cover the remainder Δhk+1 by (15)(16).

• Step 5: (Measurement update step) Optimize the center and shape matrix of the state estimation ellipsoid x̂k+1Pk+1 such that xk+1Ek+1 by solving the optimization problem (28)(31).

• Step 6: Set k=k+1 and go to Step 2.

Advertisement

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) [19], 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 [1]:

xk+1=10T0010T00100001xk+wk,E35
yk=xk12+xk22arctanxk2xk1+vk,E36

x is a four-dimensional state variable that includes position and velocity xyẋẏT, and T=1 s is the time sampling interval. The process noise and measurement noise assumed to be confined to specified ellipsoidal sets:

Wk=wk:wkTQk1wk1Vk=vk:vkTRk1vk1.

where

Qk=σ2T330T2200T330T22T220T00T220T,Rk=q320012.

The target acceleration σ2 equals to 10. The parameter q is used to control the uncertainty of the measurement noise. In the example, the target starts at the point 5030 with a velocity of 55. The center and the shape matrix of the initial bounding ellipsoid are x̂0=49.529.555T and P0=diag5,5,2,2, 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 q 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 q=0.01. 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 q of the measurement noise. The larger q 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.

Figure 3.

The log size of the remainder bounding ellipsoid is plotted as a function of time steps with q=0.01.

Figure 4.

The remainder bounding ellipsoid on a time step based on 30 samples from the boundary.

Figure 5.

The average size of the remainder bounding ellipsoid is plotted as a function of the uncertain parameter q by ESMF.

Figure 6.

The average size of the remainder bounding ellipsoid is plotted as a function of the uncertain parameter q by the new method.

• 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 q. 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 q is a better performance of the new method than that of ESMF. In summary, Figures 58 indicate that the new method performs much better than ESMF, especially in the situation of the larger noise.

Figure 7.

The RMSE of the state estimation is plotted as a function of time steps with q=0.01.

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 q.

• 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.

Figure 9.

The computation time of the proposed state bounding filter and ESMF at each time step.

Advertisement

6. Conclusion

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.

Advertisement

Acknowledgments

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.

References

  1. 1. Bar-Shalom Y, Li X, Kirubarajan T. Estimation with Applications to Tracking and Navigation. New York: Wiley; 2001
  2. 2. Abdallah F, Gning A, Bonnifait P. Box particle filtering for nonlinear state estimation using interval analysis. Automatica. 2008;44:807-815
  3. 3. Gning A, Ristic B, Mihaylova L, Abdallah F. An introduction to box particle filtering. IEEE Signal Processing Magazine. 2013;30:166-171
  4. 4. 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
  5. 5. 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
  6. 6. Polyak BT, Nazin SA, Durieu C, Walter E. Ellipsoidal parameter or state estimation under model uncertainty. Automatica. 2004;40:1171-1179
  7. 7. Schweppe FC. Recursive state estimation: Unknown but bounded errors and system inputs. IEEE Transactions on Automatic Control. 1968;13:22-28
  8. 8. Jaulin L. Nonlinear bounded-error state estimation of continuous-time systems. Automatica. 2002;38:1079-1082
  9. 9. Rohou S, Jaulin L, Mihaylova L, Bars FL. Guaranteed computation of robot trajectories. Robotics and Autonomous Systems. 2017;97:76-84
  10. 10. Calafiore G, El Ghaoui L. Ellipsoidal bounds for uncertain equations and dynamical systems. Automatica. 2004;40:773-787
  11. 11. 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
  12. 12. Durieu C, Walter E, Polyak BT. Multi-input multi-output ellipsoidal state bounding. Journal of Optimization Theory and Applications. 2001;111:273-303
  13. 13. Shamma JS, Tu K. Approximate set-valued observers for nonlinear systems. IEEE Transactions on Automatic Control. 1997;42:648-658
  14. 14. Morrell DR, Stirlling WC. An extended set-valued Kalman filter. Proceeding of ISIPTA. 2003:396-407
  15. 15. 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
  16. 16. 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
  17. 17. 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
  18. 18. 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
  19. 19. Scholte E, Campbell ME. A nonlinear set-membership filter for on-line applications. International Journal of Robust and Nonlinear Control. 2003;13:1337-1358
  20. 20. 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
  21. 21. Boyd S, Vandenberghe L. Convex Optimization. Cambridge, United Kingdom: Cambridge University Press; 2004
  22. 22. Ben-Tal A, Nemirovski A. Robust convex optimization. Mathematics of Operations Research. 1998;23:769-805
  23. 23. Still G. Discretization in semi-infinite programming: The rate of convergence. Mathematical programming. 2001;91:53-69
  24. 24. Calafiore G, Campi M. Uncertain convex programs: Randomized solutions and confidence levels. Mathematical Programming. 2005;102:25-46
  25. 25. Spivak M. Calculus on manifolds. New York: Benjamin; 1965
  26. 26. 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
  27. 27. Nesterov Y, Nemirovski A. Interior point polynomial methods in convex programming: Theorey and applications. Philadelphia, PA: SIAM;1994
  28. 28. Vandenberghe L, Boyd S. Semidefinite programming. SIAM Review. 1996;38:49-95
  29. 29. Lan G, Lu Z, Monteiro RD. Primal-dual first-order methods with O1/ϵ iteration-complexity for cone programming. Mathematical Programming. 2011;126:1-29

Written By

Zhiguo Wang, Xiaojing Shen and Yunmin Zhu

Submitted: 23 November 2017 Reviewed: 25 January 2018 Published: 18 July 2018