Generic Stability Implication from Full Information Estimation to Moving-Horizon Estimation

Optimization-based state estimation is an estimation approach which performs state estimation by solving an optimization problem. Compared to conventional approaches like Kalman filtering (KF) which deals with linear dynamical systems, and its extensions like extended KF and unscented KF which can deal with nonlinear dynamical systems based on linearization techniques, optimization-based approach has the advantage of handling linear and nonlinear dynamical systems directly and also including various physical or operational constraints [1]. The optimization formulation also admits flexible definition of the objective function to be optimized, which in some cases is necessary to accurately recover the state [2].

Optimization-based state estimation generally takes one of the two forms: full information estimation (FIE) which uses all past measurements to perform the estimation, and moving-horizon estimation (MHE) which uses most recent measurements of a limited length to perform the estimation. MHE is a practical approximate of FIE which is ideal and computationally intractable. The interest in FIE lies in two aspects: serving as a benchmark to MHE and providing useful insights for the stability analysis of MHE. Recent studies on FIE and MHE are concentrated on analyses of their stability and robustness, as are critical to guide the applications of MHE. While earlier literature assumes restrictive and idealistic conditions such as observability and/or zero or a priori known convergent disturbances [3, 4, 5, 6, 7, 8, 9], recent literature considers more practical conditions like detectability and/or in the presence of bounded disturbances [10, 11, 1].

An important progress was made in [11], which introduced the incremental input/output-to-state stability (i-IOSS) concept on detectability of nonlinear systems (as developed in [12]) to study robust stability of FIE and MHE. Given an i-IOSS system, it was shown that under mild conditions FIE is robustly stable and convergent for convergent disturbances. Whereas, conditions for FIE and MHE to be robustly stable under bounded disturbances were posted as an open research challenge. Reference [13] provided a prompt response to this challenge,¹¹1The main results were obtained in the late of 2012 though the paper was not able to be published until 2015. identifying a general set of conditions for FIE to be robustly stable for i-IOSS systems. Onwards, a series of researches have been inspired to close the challenge.

A particular type of cost functions with a max-term was investigated for a class of i-IOSS systems in [14], establishing robust stability of the FIE. The conditions were enhanced in [15], enabling robust stability also of MHE if a sufficiently long horizon is applied. The conclusion was extended to MHE without a max-term in the cost function [16]. Meanwhile, it was shown that MHE is convergent for convergent disturbances, with or without a max-term. On the other hand, reference [2] revealed an implication link from robust stability of FIE to that of MHE, and consequently identified rather general conditions for MHE to be robustly stable by inheriting conditions which ensure robust stability of the corresponding FIE. By making use of a Lipschitz continuity condition introduced in [2], reference [17] streamlined and generalized the analysis and results of [16], showing that the key is essentially to assume that the system satisfies a form of exponential detectability. When global exponential detectability is assumed, the MHE can further be shown to be robustly globally exponentially stable by implementing properly time-discounted stage costs [18].

The reviewed robust stabilities of FIE and MHE were concluded based on the concept defined in [11], which is however found to be flawed in that such defined robustly stable estimator does not imply convergence for convergent disturbances [19, 20]. This motivates a necessary modification of the stability concept in [19], which redefines the estimate error bound with a worst-case time-discounted instead of uniformly-weighted impact of the disturbances. The new concept is an enhancement of the old one, and was shown to be compatible with the original i-IOSS detectability of a system, which is necessary for establishing robust stability of both FIE and MHE. With this new concept, it becomes straightforward to understand the earlier robust local/global exponential stability results reported of FIE and MHE [16, 18]. It also motivates some new results as developed in [1, Ch. 4], which introduced a kind of stabilizability condition to establish robust stability of FIE and MHE. Despite conceptual elegance, the new condition involves an inequality which is uneasy to verify in general.

Motivated by the new and stronger concept of robust stability, this work aims to motivate general sufficient conditions for robust stability of MHE by firstly establishing a generic implication link from robust stability of FIE to that of MHE, and then transforming the challenge into identifying sufficient conditions for ensuring robust stability of FIE. While the reasoning approach is inspired by the ideas introduced in [2], the contributions of this work are three-fold:

• •

  A generic implication is established from robust stability of FIE to practical robust stability of the corresponding MHE, and the implication becomes stronger to robust stability of the MHE if the FIE admits a certain Lipschitz continuity property;

• •

  Explicit computations of sufficient MHE horizons are provided for the aforementioned implications to be effective in a local or global sense of robust stability. Analyses on two exemplary cases further illustrate that the upper bound of the MHE estimate error can eventually decrease with respect to (w.r.t.) the horizon size once it is large enough and satisfies certain conditions.

• •

  Given the revealed implications, new sufficient conditions are derived for robust stability of MHE by firstly developing those for the corresponding FIE. An interesting finding is that a system being i-IOSS is necessary but also sufficient for existence of a robustly stable FIE. Consequently is a similar but weaker conclusion applicable to MHE.

The remaining of this work is organized as follows. Sec. II introduces notation, setup and necessary preliminaries. Sec. III defines general forms of FIE and MHE, and introduces robust stability concepts. Sec. IV reveals the implication from global (or local) robust stability of FIE to that of the corresponding MHE. Sec. V applies the implication to establish robust stability of MHE, by firstly developing conditions for ensuring robust stability of the corresponding FIE. Finally, Sec. VI concludes the work.

The notation mostly follows the convention in [2, 1]. The symbols $\mathbb{R}$, $\mathbb{R}_{\geq 0}$ and $\mathbb{I}_{\geq 0}$ denote the sets of real numbers, nonnegative real numbers and nonnegative integers, respectively, and $\mathbb{I}_{a:b}$ denotes the set of integers from $a$ to $b$. The constraints $t\geq 0$ and $t\in\mathbb{I}_{\geq 0}$ are used interchangeably to refer to the set of discrete times. The symbol $\left|\cdot\right|$ denotes the Euclidean norm of a vector. The bold symbol $\boldsymbol{x}_{a:b}$, denotes a sequence of vector-valued variables $(x_{a},\,x_{a+1},\,...,\thinspace x_{b})$, and with a function $f$ acting on a vector $x$, $f(\boldsymbol{x}_{a:b})$ stands for the sequence of function values $(f(x_{a}),\,f(x_{a+1}),\,...,\thinspace f(x_{b}))$. Given a scalar function $f:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$, any $t\in\mathbb{R}$ and any scalar function $g$, the notation $f^{\circ n}(g(\cdot),t)$ refers to the $n$ fold composition of function $g$ by function $f$ subject to the given second argument $t$, and $f^{\circ 0}$ equals the identity function.

Throughout the paper, $t$ refers to a discrete time, and as a subscript it indicates dependence on time $t$. Whereas, the subscripts or superscripts $x$, $w$ and $v$ are used exclusively to indicate a function or variable that is associated with the state ($x$), process disturbance ($w$) or measurement noise ($v$). The symbols $\left\lfloor x\right\rfloor$ and $\left\lceil x\right\rceil$ refer to the integers that are closest to $x$ from below and above, respectively. Given two scalars $a$ and $b$, let $a\oplus b:=\max\{a,\,b\}$. The operator $\oplus$ is both associative and commutative, i.e., $(a\oplus b)\oplus c=a\oplus(b\oplus c)$ and $a\oplus b=b\oplus a$, and furthermore is distributive with respect to (w.r.t.) increasing functions. That is, $\alpha(a\oplus b\oplus c)=\alpha(a)\oplus\alpha(b)\oplus\alpha(c)$ if the function $\alpha$ is increasing in the argument. The frequently used $\mathcal{K}$, $\mathcal{L}$ and $\mathcal{KL}$ functions are defined as follows.

Consider a discrete-time system described by

where $x_{t}\in\mathbb{X}\subseteq\mathbb{R}^{n}$ is the system state, $w_{t}\in\mathbb{W}\subseteq\mathbb{R}^{g}$ the process disturbance, $y_{t}\in\mathbb{Y}\subseteq\mathbb{R}^{p}$ the measurement, $v_{t}\in\mathbb{V}\subseteq\mathbb{R}^{p}$ the measurement disturbance, all at time $t$. Here we study state estimation as an independent subject, and so control inputs (if there were any) known up to the estimation time are treated as given constants, which do not cause difficulty to later defined optimization and related analyses and hence are neglected in the problem formulation for brevity [11, 1]. The functions $f$ and $h$ are assumed to be continuous and known. The initial state $x_{0}$ and the disturbances $(w_{t},v_{t})$ are assumed to be unknown but bounded.

Consider two state trajectories. Let

for all $\tau\in\mathbb{I}_{0:t-1}$, where $\pi_{\tau+t+1}$ corresponds to $v_{\tau}^{(1)}-v_{\tau}^{(2)}$ if additive measurement noises are present while identical measurements are assumed. Hence $\boldsymbol{\pi}_{0:2t}$ collects a sequence of deviation vectors, and its domain is denoted as $\Pi$. Let $\iota(\pi_{\cdot})$ extract the time index (i.e., the original index $\tau$ above) of $\pi_{\cdot}$. Specifically, we have

Note that the time index of $\pi_{0}$ is defined as $-1$ which refers to the time associated with a priori information.

With the above notation, we can have a concise statement of the i-IOSS definition given in [1, 19].

As proved in [19], this definition of i-IOSS is equivalent to the original one introduced in [12] which applies $\mathcal{K}$ instead of $\mathcal{KL}$ function to each uncertainty $|\pi_{i}|$ for all $i\geq 1$.

The following defines Lipschitz continuity of a function at a given point, and presents a related proposition.

Consider the system described in (1). Given a present time $t$, the state estimation problem is to find an optimal estimate of state $x_{t}$ based on historical measurements $\{y_{\tau}\}$ for $\tau$ in a time set. Ideally, all measurements up to time $t$ are used, leading to the so-called FIE; and practically, only measurements are used within a limited distance backwards from time $t$, yielding the so-called MHE. Both FIE and MHE can be cast as optimization problems.²²2Readers are referred to [11] for a brief introduction of their connection to control problems and difference from probabilistic formulations. To be concise, we will first define MHE and then treat FIE as a variant.

Let MHE implement a moving horizon of size $T$. The decision variables are denoted as $(\boldsymbol{\chi}_{t-T:t},\boldsymbol{\omega}_{t-T:t-1},\boldsymbol{\nu}_{t-T:t-1})$, which correspond to the system variables $(\boldsymbol{x}_{t-T:t},\boldsymbol{w}_{t-T:t-1},\boldsymbol{v}_{t-T:t-1})$.³³3As in [1], the last measurement is not considered for ease of presentation, though the inclusion does not change the conclusions. And let the optimal decision variables be $(\hat{\boldsymbol{x}}_{t-T:t},\hat{\boldsymbol{w}}_{t-T:t-1},\hat{\boldsymbol{v}}_{t-T:t-1})$. Since $\hat{\boldsymbol{x}}_{t-T+1:t}$ is uniquely determined from $\hat{x}_{t-T}$ and $\hat{\boldsymbol{w}}_{t-T:t-1}$, the decision variables essentially reduce to $(\chi_{t-T},\boldsymbol{\omega}_{t-T:t-1},\boldsymbol{\nu}_{t-T:t-1})$.

In addition, let $\bar{x}_{t-T}$ be a priori estimate of $x_{t-T}$, and in particular $\bar{x}_{0}$ be bounded. Without loss of generality, the prior estimates of the disturbances are assumed to be zero. Denote the cost function as $V_{T}(\chi_{t-T}-\bar{x}_{t-T},\boldsymbol{\omega}_{t-T:t-1},\boldsymbol{\nu}_{t-T:t-1})$, which penalizes uncertainties in the initial state, the process and the measurements. Then, the MHE instance at time $t$ is defined by the following optimization problem:

As $\boldsymbol{\nu}_{t-T:t-1}$ is uniquely determined by $\chi_{t-T}$ and $\boldsymbol{\omega}_{t-T:t-1}$, it is kept mainly for the convenience of expressing the disturbance set and the objective function. Since the global optimal solution $\hat{x}_{\tau}$, for any $\tau\leq t$, is dependent on time $t$ when the MHE instance is defined, to be unambiguous we use $\hat{x}_{t}^{\star}$ to represent $\hat{x}_{t}$ that is solved from the instance defined at time $t$. This keeps $\hat{x}_{t}^{\star}$ unchanged, while the realization $\hat{x}_{t}$ varies as MHE renews itself in time.

To define FIE, it suffices to adapt the horizon size $T$ in the MHE formulation to taking the time-varying value $t$. The yielded FIE has the form of an MHE but with complete data originating from the zero initial time. To link them easily, an FIE is called the corresponding FIE of an MHE based on which the FIE is derived, and conversely is the MHE called a corresponding MHE of the FIE. Since it becomes computationally intractable as time elapses, FIE is studied mainly for its theoretical interest: its performance is viewed as a limit or benchmark that MHE attempts to approach, and its stability can be a good start point for analysis of MHE.

An important issue in designing FIE or MHE is to identify conditions under which the associated optimization admits optimal estimates that satisfy a robust stability property defined below. Let $\boldsymbol{x}_{0:t}(x_{0},\boldsymbol{w}_{0:t-1})$ denote a state sequence generated from an initial state $x_{0}$, and a disturbance sequence $\boldsymbol{w}_{0:t-1}$. In addition, define a bounded set for any given $\delta_{0}>0$:

The last measurement $y_{t}$ and hence the corresponding noise $v_{t}$ is not considered in the above inequality, to keep the definition consistent with the formulations of FIE and MHE. Here the definition of RGAS strengthens the one introduced in [11] which applies $\mathcal{K}$ instead of $\mathcal{KL}$ functions to the disturbances. This change is necessary to enable a desirable feature that a state estimator which is RGAS must be convergent under convergent disturbances [1, 19]. The next definition presents a weaker alternative of the above robust stability, which will also be needed in later analysis.

The adverb “practically” before RGAS is employed to keep it in line with the practical stability concept developed in control literature (e.g., [21]). Compared to an RGAS estimate, the pRGAS estimate admits a looser bound with a non-vanishing constant term $\epsilon$. As will be shown later, this term can be made arbitrarily small if MHE implements a long enough horizon. In addition, it is worthwhile to remark that there is no need to define such stability variant for the case of RES or RGES because in either case the exponential property ensures that the $\epsilon$ term will be fully tempered and removed.

By applying the notation used in the concise definition of i-IOSS in (6), conciser forms of the above stability definitions can also be obtained, which will be useful to convey stability conditions for both FIE and MHE later on. Towards that, let $x_{0}^{(1)}:=x_{0}$, $w_{\tau}^{(1)}:=w_{\tau}$, $h(x_{\tau}^{(1)}):=y_{\tau}-v_{\tau}$, $x_{0}^{(2)}:=\bar{x}_{0}$, $w_{\tau}^{(2)}:=0$, and $h(x_{\tau}^{(2)}):=y_{\tau}$ for all $\tau\in\mathbb{I}_{0:t-1}$. Consequently, the notation $\boldsymbol{\pi}_{0:2t}$ defined in (4) has a new realization, and its corresponding domain is denoted as $\Pi$ if $\chi_{0},\,\bar{x}_{0}\in\mathbb{X}$ or $\Pi_{\delta_{0}}$ if $(\chi_{0},\,\bar{x}_{0})\in\mathbb{X}_{\delta_{0}}$.

With the new notation, it is straightforward to prove the following equivalent definition of robust stabilities.

Similar concise definitions of pRAS and pRGAS can both be obtained by adding a constant $\epsilon>0$ to the right hand side of (11), in which the $\mathcal{KL}$ function $\beta$ will then be dependent on $\epsilon$. For brevity, we do not state them with another lemma.

At any discrete time, an MHE instance can be interpreted as the corresponding FIE initiating from the start of the horizon over which the MHE instance is defined. Thus, the corresponding FIE being robustly stable implies that each MHE instance is robustly stable within the time horizon over which the instance is defined. If we interpret this as MHE being instance-wise robustly stable, then the challenge reduces to identifying conditions under which instance-wise robust stability implies robust stability of MHE. This observation was made in [2], and the challenge was solved there for a weaker definition of RGAS. This section resolves the challenge subject to the stronger stability concept given by Definition 4.

To that end, as in [2], we apply an ordinary assumption on the prior estimate $\bar{x}_{t-T}$ of the initial state $x_{t-T}$ of an MHE instance.

The assumption is obviously true if $\bar{x}_{t-T}$ is set to $\hat{x}_{t-T}^{\star}$, which is the MHE estimate obtained at time $t-T$. Alternatively, a better $\bar{x}_{t-T}$ might be obtained with smoothing techniques which use measurements both before and after time $t-T$ [22, 1].

Next, we present an important lemma which links global robust stability of MHE with that of its corresponding FIE.