# Guaranteed State Estimation via Indirect Polytopic Set Computation for
Nonlinear Discrete-Time Systems

Mohammad Khajenejad, Fatima Shoaib, Sze Zheng Yong
M. Khajenejad, Fatima Shoaib and S.Z. Yong are with the School for Engineering
of Matter, Transport and Energy, Arizona State University, Tempe, AZ, USA
(e-mail: {mkhajene, fshoaib, szyong}@asu.edu).This work is partially supported
by NSF grant CNS-1932066.

###### Abstract

This paper proposes novel set-theoretic approaches for state estimation in
bounded-error discrete-time nonlinear systems, subject to nonlinear
observations/constraints. By transforming the polytopic sets that are
characterized as zonotope bundles (ZB) and/or constrained zonotopes (CZ), from
the state space to the space of the generators of ZB/CZ, we leverage a recent
result on remainder-form mixed-monotone decomposition functions to compute the
propagated set, i.e., a ZB/CZ that is guaranteed to enclose the set of the
state trajectories of the considered system. Further, by applying the
remainder-form decomposition functions to the nonlinear observation function,
we derive the updated set, i.e., an enclosing ZB/CZ of the intersection of the
propagated set and the set of states that are compatible/consistent with the
observations/constraints. Finally, we show that the mean value extension
result in [1] for computing propagated sets can also be extended to compute
the updated set when the observation function is nonlinear.

##  I Introduction

State estimation is crucial in several research fields such as fault detection
and isolation [2], localization problem [3] and state-feedback control [4]. In
such settings, Bayesian/stochastic estimation approaches such as particle or
Kalman filtering can be applied if distributions/stochastic descriptions of
uncertainties are known. However, in bounded-error settings where
distribution-free set-valued uncertainties are considered, guaranteed sets of
true values of state trajectories which are compatible/consistent with
constraints/observations are desired. Obtaining the exact characterization of
such sets that contain the evolution of the system states is very complicated
and mostly intractable [5], hence developing set-theoretic approaches to
tractably derive enclosures to such sets, while trying to make the enclosing
sets as tight as possible, is critical.

_Literature review._ In the context of bounded-error settings, where dynamical
systems are subject to distribution-free and bounded uncertainties, several
seminal studies have proposed set-membership state estimation approaches for
discrete-time constrained systems, to compute enclosing sets to all possible
system trajectories [6, 7, 1]. A well-known strategy, which is common to all
these methods is finding an enclosing set to the image set of the dynamics
vector field, i.e., _propagation/prediction_ step, as well as refining the
obtained propagated set by finding an enclosure to its intersection with the
set of states that are compatible/consistent with the
observation/measurements, i.e., _update_ step.

In case of linear systems with polytopic initial set, it is theoretically
shown that tight (exact) enclosures can be obtained [8]. However, even for
linear systems, the computational complexity of polytopic propagation is
extensive and grows dramatically with time [9]. Hence, simpler sets such as
parallelotopes [10, 6], ellipsoids [11, 12, 13], intervals [14, 15, 16, 17] or
zonotopes [7, 18] have been used to characterize the enclosures. However,
structural limitations of these sets sometimes leads to conservative
enclosures. To address this, the work in [19] introduced _constrained
zonotpes_ to ease some of the limitations imposed by zonotopes, while
_zonotope bundles_ were proposed in [20] to describe the intersection of
zonotopes without explicit computations.

Regarding nonlinear systems, obtaining efficient set-valued estimates is still
very challenging, contrary to the linear case. A classical approach to tackle
this problem has been to use interval arithmetic-based inclusion functions
[21] to propagate the current enclosing sets through the nonlinear dynamics
and then to apply interval-based set inversion techniques (e.g., SIVIA) to
find upper approximations for the set of compatibles states with the current
measurements [3, 22]. These approaches are computationally very efficient, but
unfortunately, due to the nature of interval arithmetic, the resultant bounds
are mostly conservative.

Alternatively, given linear observation functions, zonotopic propagation
methods have been developed in [23, 24, 25], based on the first order Taylor
expansion, the mean value extension or DC programming. However, significant
errors are caused in update step due to the symmetry of zonotopes, even for
linear measurements [19]. More recently, the interesting work in [1] proposed
constrained zonotopic propagation and update algorithms for discrete-time
nonlinear systems with linear observation functions, based on mean value and
first order Taylor extensions.

_Contributions._ This paper proposes novel methods for recursive state
estimation (consisting of propagation and update steps) using polytopes
(equivalently, constrained zonotopes or zonotope bundles) for nonlinear
bounded-error discrete-time systems with nonlinear observation functions.
Leveraging remainder-form mixed-monotone decomposition functions [26] and
following the standard propagation and update approach, this paper bridges the
gap between constrained zonotope (CZ)/zonotope bundle (ZB)-based set-valued
state estimation and nonlinear observation/constrained functions. In
particular, for the propagation step, we transform the prior ZB/CZ’s into the
space of CZ/ZB generators, which are interval-valued, and further transform
the vector field into two components, one that is proven to attain tight image
sets, as well as a linear remainder function, for which a family of remainder-
form mixed-monotone decomposition functions [26] can be obtained. Each of the
decomposition functions produce enclosures of the state trajectories and thus,
we can intersect them to obtain the desired propagated ZB/CZ enclosures.

Moreover, we show that a similar idea, i.e., transformation from the
state+uncertainty space to the space of generators of CZ/ZB’s, can be used for
the update step to find a family of enclosures to the _generalized nonlinear
intersection_ of the propagated set with the set of states that is compatible
with the observations, where the final enclosures are proven to be ZB/CZ’s.
Furthermore, we prove that the mean value extension approach used in [1] to
enclose a multiplication of an interval matrix to a constrained zonotope, can
also be leveraged for the update step when the observation function is
nonlinear. Finally, we compare our proposed approaches together and with the
mean value extension-based approach in [1], implementing it on two examples,
one with a linear and the other with a nonlinear observation function.

##  II Preliminaries

In this section, we briefly introduce some of the main concepts that we use
throughout the paper, as well as some important existing results that will be
used for deriving our main results and for comparison.

_Notation._ $\mathbb{N},\mathbb{N}_{a},\mathbb{R}^{n}$ and
$\mathbb{R}^{m\times n}$ denote the set of positive integers, the first $a$
positive integers, the $n$-dimensional Euclidean space and the space of $m$ by
$n$ real matrices, respectively. For
$\mathcal{Z},\mathcal{W}\subset\mathbb{R}^{n},R\in\mathbb{R}^{m\times
n},\mathcal{Y}\subset\mathbb{R}^{m}$, and
$\mu:\mathbb{R}^{n}\to\mathbb{R}^{m}$,
$R\mathcal{Z}\triangleq\\{Rz|z\in\mathcal{Z}\\},\mathcal{Z}\oplus\mathcal{W}\triangleq\\{z+w|z\in\mathcal{Z},w\in\mathcal{W}\\}$,
$\mathcal{Z}\ominus\mathcal{W}\triangleq\\{z-w|z\in\mathcal{Z},w\in\mathcal{W}\\}$,
$\mu(\mathcal{Z})\triangleq\\{\mu(z)|z\in\mathcal{Z}\\}$ and
$\mathcal{Z}\cup_{\mu}\mathcal{Y}\triangleq\\{z\in\mathcal{Z}|\mu(z)\in\mathcal{Y}\\}$
denote the linear mapping, Minkowski sum, set subtraction, general (nonlinear)
mapping and generalized (nonlinear) intersection, respectively. Moreover, the
transpose, Moore-Penrose pseudoinverse and $(i,j)$-th element of $R$ are given
by $R^{\top}$, $R^{\dagger}$ and $R_{ij}$, while its row support is
$r=\textstyle{\mathrm{rowsupp}}(R)\in\mathbb{R}^{m}$, where $r_{i}=0$ if the
$i$-th row of $R$ is zero and $r_{i}=1$ otherwise, $\forall
i\in\mathbb{N}_{m}$. Furthermore,
$\mathbb{B}^{n}_{\infty}\triangleq\\{z\in\mathbb{R}^{n}|\|z\|_{\infty}\leq
1\\}$ and $\mathbf{0}_{n}$ denote the $\infty$-norm hyperball and the zero
vector in $\mathbb{R}^{n}$, respectively. For $z\in\mathbb{R}^{n}$,
$\textstyle{\mathrm{diag}}(z)$ is a diagonal matrix in $\mathbb{R}^{n\times
n}$, with its diagonal elements being the corresponding elements of $z$.
$\langle\cdot,\cdot\rangle$ denotes the inner product operator.

######  Definition 1 (Intervals, Polytopes, Constrained Zonotopes (CZ) and
Zonotope Bundles (ZB)).

A set $\mathcal{Z}\subset\mathbb{R}^{n}$ is a(n) (i) interval, (ii) polytope,
(iii) constrained zonotope (CZ), (iv) zonotope bundle (ZB), if

  1. (i)

$\exists\underline{z},\overline{z}\in\mathbb{R}^{n}$ such that
$\mathcal{Z}=[\underline{z},\overline{z}]\triangleq\\{z\in\mathbb{R}^{n}|\underline{z}\leq
z\leq\overline{z}\\}$. An interval matrix can be defined similarly, in an
element-wise manner.

  2. (ii)

$\exists A_{p}\in\mathbb{R}^{n_{p}\times n},b_{p}\in\mathbb{R}^{n_{p}}$ such
that
$\mathcal{Z}=\\{A_{p},b_{p}\\}_{P}\triangleq\\{z\in\mathbb{R}^{n}|A_{p}z\leq
b_{p}\\}$.

  3. (iii)

$\exists\tilde{G}\in\mathbb{R}^{n\times
n_{g}},\tilde{c}\in\mathbb{R}^{n},\tilde{A}\in\mathbb{R}^{n_{c}\times
n_{g}},\tilde{b}\in\mathbb{R}^{n_{c}}$ such that
$\mathcal{Z}=\\{\tilde{G},\tilde{c},\tilde{A},\tilde{b}\\}_{CZ}\triangleq\\{\tilde{G}\xi+\tilde{c}|\xi\in\mathbb{B}^{n_{g}},\tilde{A}\xi=\tilde{b}\\}$.
$n_{g}$ and $n_{c}$ are called the number of CZ’s generators and constraints,
respectively.

  4. (iv)

$\mathcal{Z}$ can be represented as an intersection of $S\in\mathbb{N}$
zonotopes, i.e.,
$\exists\\{{G}_{s}\in\mathbb{R}^{n\times\hat{n}_{s}},{c}_{s}\in\mathbb{R}^{n}\\}_{s=1}^{S}$
such that
$\mathcal{Z}=\bigcap\limits_{s=1}^{S}\\{{G}_{s},{c}_{s}\\}_{Z}\triangleq\bigcap\limits_{s=1}^{S}\\{{G}_{s}\zeta+{c}_{s}|\zeta\in\mathbb{B}^{\hat{n}_{g}}\\}$,
with $\hat{n}_{s},s=1,\dots,S$, being called the number of generators for each
zonotope.

It is worth mentioning that using CORA2020 [27], if a set $\mathcal{Z}$ has
each of the polytopic, CZ or ZB representations, it can be equivalently and
tightly transformed into the other two representations. This is represented
thorough this paper as:

$\textstyle\mathcal{Z}=\\{A_{p},b_{p}\\}_{P}\equiv\\{\tilde{G},\tilde{c},\tilde{A},\tilde{b}\\}_{CZ}\equiv\bigcap\limits_{s=1}^{S}\\{{G}_{s},{c}_{s}\\}_{Z}.$

######  Proposition 1.

Consider an interval vector
$\mathbb{IZ}\triangleq[\underline{z},\overline{z}]\subset\mathbb{IR}^{n}$ and
an interval matrix $\mathbb{J}\in\mathbb{IR}^{n\times m}$. Then, $\mathbb{IZ}$
and $\mathbb{J}$ can be equivalently represented as

$\displaystyle\mathbb{IZ}$
$\displaystyle\triangleq[\underline{z},\overline{z}]\equiv\textstyle{\mathrm{mid}}(\mathbb{IZ})\oplus\frac{1}{2}\textstyle{\mathrm{diag}}(\textstyle{\mathrm{diam}}(\mathbb{IZ}))\mathbb{B}^{n}_{\infty},$
(1) $\displaystyle\mathbb{J}$
$\displaystyle\triangleq[\underline{J},\overline{J}]\equiv\textstyle{\mathrm{mid}}(\mathbb{J})\oplus\mathbb{J}_{\Delta},$
(2)

where for $q\in\\{\mathbb{IZ},\mathbb{J}\\}$,
$\textstyle{\mathrm{mid}}(q)\triangleq\frac{1}{2}(\overline{z}+\underline{z})$,
$\textstyle{\mathrm{diam}}(q)\triangleq(\overline{z}-\underline{z})$, and
$\mathbb{J}_{\Delta}\in\mathbb{IR}^{n\times m}$ is an interval matrix that is
defined as
$[\mathbb{J}_{\Delta}]_{ij}\triangleq\frac{1}{2}[-\textstyle{\mathrm{diam}}(\mathbb{J})_{ij}\
\textstyle{\mathrm{diam}}(\mathbb{J})_{ij}],\forall i\in\mathbb{N}_{n},\forall
j\in\mathbb{N}_{m}$.

###### Proof.

To prove (1), consider $z\in\mathbb{IZ}\Leftrightarrow\underline{z}\leq
z\leq\overline{z}\Leftrightarrow\underline{z}-\textstyle{\mathrm{mid}}(\mathbb{IZ})\leq
z-\textstyle{\mathrm{mid}}(\mathbb{IZ})\leq\overline{z}-\textstyle{\mathrm{mid}}(\mathbb{IZ})\Leftrightarrow-\frac{1}{2}\textstyle{\mathrm{diam}}(\mathbb{IZ})\leq
z-\textstyle{\mathrm{mid}}(\mathbb{IZ})\leq\frac{1}{2}\textstyle{\mathrm{diam}}(\mathbb{IZ})\Leftrightarrow\textstyle{\mathrm{mid}}(\mathbb{IZ})-\frac{1}{2}\textstyle{\mathrm{diam}}(\mathbb{IZ})\leq
z\leq\frac{1}{2}\textstyle{\mathrm{diam}}(\mathbb{IZ})+\textstyle{\mathrm{mid}}(\mathbb{IZ})\Leftrightarrow\exists\xi\in\mathbb{B}^{n}_{\infty},s.t.\
z=\textstyle{\mathrm{mid}}(\mathbb{IZ})+\frac{1}{2}\textstyle{\mathrm{diag}}(\textstyle{\mathrm{diam}}(\mathbb{IZ}))\xi\Leftrightarrow
z\in\textstyle{\mathrm{mid}}(\mathbb{IZ})\oplus\frac{1}{2}\textstyle{\mathrm{diag}}(\textstyle{\mathrm{diam}}(\mathbb{IZ}))\mathbb{B}^{n}_{\infty}$.
The result in (2) is a straightforward extension of (1). ∎

######  Proposition 2.

[1, Theorem 1] Let $\mathcal{X}=\\{G,c,A,b\\}_{CZ}\subset\mathbb{R}^{m}$ be a
constrained zonotope with $n_{g}$ generators and $n_{c}$ constraints, and
$\mathbb{J}\in\mathbb{IR}^{n\times m}$ be an interval matrix. Consider the set
$S=\mathbb{J}\mathcal{X}\triangleq\\{Jx|J\in\mathbb{J},x\in\mathcal{X}\\}\subset\mathbb{R}^{n}$.
Let $\overline{\mathcal{X}}=\\{\overline{G},\overline{c}\\}_{Z}$ be a zonotope
satisfying $\mathcal{X}\subseteq\overline{\mathcal{X}}$ and
$\overline{c}\in\mathbb{R}^{\overline{n}_{g}}$. Let
$\mathbf{m}\in\mathbb{R}^{n}$ be an interval vector such that
$\mathbf{m}\supset(\mathbb{J}-\textstyle{\mathrm{mid}}(\mathbb{J}))\overline{c}$
and $\textstyle{\mathrm{mid}}(\mathbf{m})=\mathbf{0}_{n}$. Let
$P\in\mathbb{R}^{n\times n}$ be a diagonal matrix defined as follows. $\forall
i=1,\dots,n$:

$\displaystyle
P_{ii}=\frac{1}{2}\textstyle{\mathrm{diam}}(\mathbf{m}_{i})+\frac{1}{2}\sum_{j=1}^{\overline{n}_{g}}\sum_{k=1}^{m}\textstyle{\mathrm{diam}}(\mathbb{J}_{ik})|\overline{G}_{kj}|.$
(3)

Then,
$\mathcal{S}\subseteq\textstyle{\mathrm{mid}}(\mathbb{J})\mathcal{X}\oplus
P\mathbb{B}^{n}_{\infty}$

$\displaystyle\quad\quad\quad=\\{\begin{bmatrix}\textstyle{\mathrm{mid}}(\mathbb{J})G&P\end{bmatrix},\textstyle{\mathrm{mid}}(\mathbb{J})c,\begin{bmatrix}A&0_{n_{g}\times
n}\end{bmatrix},b\\}_{CZ}.$ (4)

######  Proposition 3 (RRSR Propagation Approach).

[1, Theorem 2] Let $f:\mathbb{R}^{n}\times\mathbb{R}^{n_{w}}\to\mathbb{R}^{n}$
be continuously differentiable and $\nabla_{x}f$ denote the gradient of $f$
with respect to its first argument. Let
$\mathcal{X}=\\{G_{x},c_{x},A_{x},b_{x}\\}_{CZ}\subset\mathbb{R}^{n}$ and
$\mathcal{W}\subset\mathbb{R}^{n_{w}}$ be constrained zonotopes. Choose any
$h\in\mathcal{X}$. If $\mathcal{Z}$ is a constrained zonotope such that
$f(h,\mathcal{W})\subseteq\mathcal{Z}$ and $\mathbb{J}\in\mathbb{IR}^{n\times
n}$ is an interval matrix satisfying
$\nabla^{\top}_{x}f(\mathcal{X},\mathcal{W})\subseteq\mathbb{J}$, then

$\displaystyle
f(\mathcal{X},\mathcal{W})\subseteq\mathcal{Z}\oplus\textstyle{\mathrm{mid}}(\mathbb{J})(\mathcal{X}-h)\oplus\tilde{P}\mathbb{B}^{n}_{\infty},$
(5)

where $\tilde{P}$ can be computed through (3), using $\mathbb{J}$ and an
enclosing zonotope to $\mathcal{X}-h$.

######  Definition 2 (Mixed-Monotone (One-Sided) Decomposition Functions For
Discrete-Time Systems).

[26, Definitions 3,4] A mapping
$f_{d}:\mathcal{Z}\times\mathcal{Z}\subset\mathbb{R}^{2n}\to\mathbb{R}^{m}$ is
a discrete-time mixed-monotone decomposition function with respect to
$f:\mathcal{Z}\subset\mathbb{R}^{n}\to\mathbb{R}^{m}$, over the set
$\mathcal{Z}$, if it satisfies the following: $f_{d}(x,x)=f(x),x\geq
x^{\prime}\Rightarrow f_{d}(x,y)\geq f_{d}(x^{\prime},y),y\geq
y^{\prime}\Rightarrow f_{d}(x,y)\leq f_{d}(x,y^{\prime}),\forall
x,y,x^{\prime},y^{\prime}\in\mathcal{Z}$. Further, if there exists two mixed-
monotone mappings
$\overline{f}_{d},\underline{f}_{d}:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}^{m}$,
such that for any $\underline{z},z,\overline{z}\in\mathcal{Z}$, the following
holds: $\underline{z}\leq
z\leq\overline{z}\Rightarrow\underline{f}_{d}(\underline{z},\overline{z})\leq
f(z)\leq\overline{f}_{d}(\overline{z},\underline{z})$, then $\overline{f}_{d}$
and $\underline{f}_{d}$ are called upper and lower decomposition functions for
$f$ over $\mathcal{Z}$, respectively.

It is trivial to see that $\forall
x\in[\underline{x},\overline{x}],f_{d}(\underline{x},\overline{x})\leq
f(x)\leq f_{d}(\overline{x},\underline{x})$, where $f_{d}$ is a decomposition
function of $f$.

######  Proposition 4 (Tight and Tractable Remainder-Form Upper and Lower
Decomposition Decomposition Functions).

[26, Theorems 1,2,3 ] Consider a locally Lipschitz vector field
${f}_{i}:\mathbb{IZ}\triangleq[\underline{z},\overline{z}]\subseteq\mathbb{IR}^{n_{z}}\to\mathbb{R}$.
Let $\mathbb{N}_{n_{z}}\triangleq\\{1,\dots,n_{z}\\}$ and
$\overline{{J}}^{\tilde{f}}_{i},\underline{{J}}^{\tilde{f}}_{i}\in\mathbb{R}^{n_{z}}$
denote the upper and lower bounds for the Jacobian matrix (vector) of
${f}_{i}$ over $\mathbb{IZ}$. Suppose that Assumption 2 in Section III holds.
Then, $f_{i}(\cdot)$ admits a family of mixed-monotone remainder-form
decomposition functions denoted as
$\\{{f}_{d,i}(z,\hat{z};m,h(\cdot))\\}_{\mathbf{m}\in\mathbf{M}_{i},h(\cdot)\in\mathcal{H}_{\mathbf{M}^{c}_{i}}}$,
that is parametrized by a set of supporting vectors
$\mathbf{m}\in\mathbf{M}^{c}_{i}$

$\displaystyle\mathbf{m}\in\mathbf{M}^{c}_{i}\triangleq\\{$
$\displaystyle\mathbf{m}\in\mathbb{R}^{n_{z}}|\mathbf{m}_{j}=\min(\underline{{J}}^{f}_{ij},{0})\
\lor$ $\displaystyle\mathbf{m}_{j}=\max(\overline{{J}}^{f}_{i,j},{0}),\forall
j\in\mathbb{N}_{n_{z}}\\}.$ (6)

and a locally Lipschitz remainder function
$h(\cdot)\in\mathcal{H}_{M^{c}_{i}}$, where

$\displaystyle
f_{d,i}(z,\hat{z};\mathbf{m},h(\cdot))=h(\zeta_{\mathbf{m}}(\hat{z},{z}))+f_{i}(\zeta_{\mathbf{m}}(z,\hat{z})))-h_{i}(\zeta_{\mathbf{m}}(z,\hat{z})),$
(7)

$\zeta_{\mathbf{m}}(z,\hat{z})=[\zeta_{\mathbf{m},1}(z,\hat{z}),\dots,\zeta_{\mathbf{m},n_{z}}(z,\hat{z})]^{\top}$,
$\forall j\in\mathbb{N}_{n_{z}}$:

$\displaystyle{\zeta}_{\mathbf{m},j}(z,{\hat{z}})=\begin{cases}\hat{z}_{j},\
\text{if}\ \mathbf{m}_{j}=\max(\overline{{J}}^{f}_{i,j},{0})\\\ {z}_{j},\
\text{if}\ \mathbf{m}_{j}=\min(\underline{{J}}^{f}_{i,j},{0})\end{cases},$ (8)

and
$\mathcal{H}_{\mathbb{M}_{i}}\triangleq\\{h:\mathbb{IZ}\to\mathbb{R}|[\underline{J}^{h}(z),\overline{J}^{h}_{C}(z)]\subseteq\mathbb{M}_{i},\forall
z\in\mathbb{IZ}\\}$. Moreover, search for the tightest mixed-monotone upper
and lower remainder-form decomposition functions in the form of (7) can be
equivalently restricted to the set of “linear remainders”, parametrized by
$\mathbf{m}\in\mathbf{M}^{c}_{i}$, i.e., linear remainders
$\\{{h}(\cdot)\\}_{\mathbf{m}\in\mathbf{M}^{c}_{i}}=\\{{\langle}\mathbf{m}^{i},\cdot{\rangle}\\}_{\mathbf{m}\in\mathbf{M}^{c}_{i}}$.

######  Corollary 1.

Consider a locally Lipschitz mapping
$\tilde{f}(\cdot):{\mathbb{I}\Xi}\triangleq[\underline{\xi},\overline{\xi}]\subseteq\mathbb{IR}^{n_{\xi}}\to\mathbb{R}^{n_{x}}$
that satisfies the assumptions in Proposition 4. Let us define:
$\mathbb{N}_{n_{x}}\triangleq\\{1,\dots,n_{x}\\}$ and

$\displaystyle\mathbf{H}_{\tilde{f}}\triangleq\\{H\in\mathbb{R}^{n_{x}\times
n_{\xi}}|H^{\top}_{i,:}\in\mathbf{M}^{c}_{i},\forall
i\in\mathbb{N}_{n_{x}}\\},$ (9)

where $\mathbf{M}^{c}_{i}$ is defined in (6). Then,
$\forall\xi\in\mathbb{I}\Xi,\forall
H\in\mathbf{H}^{\tilde{f}},\tilde{g}^{H}(\xi)\triangleq\tilde{f}(\xi)-H\xi$ is
proven to be a Jacobian sign-stable (JSS) function, i.e., $\forall
i\in\mathbb{N}_{n_{x}},\forall
j\in\mathbb{N}_{n_{z}},J^{H}_{ij}(\xi)\triangleq\frac{\partial
f_{i}}{\partial\xi_{j}}(\xi)\geq 0,\forall\xi\in\mathbb{I}\Xi$ or
$J^{H}_{ij}(\xi)\triangleq\frac{\partial\tilde{g}^{H}_{i}}{\partial\xi_{j}}(\xi)\leq
0,\forall\xi\in\mathbb{I}{\Xi}$.. Consequently, $\tilde{g}^{H}(\cdot)$ can be
tightly bounded in each dimension $i\in\mathbb{N}_{n_{x}}$ by remainder-form
decomposition functions $\tilde{g}_{d,i}(\cdot,\cdot;H^{\top}_{i,:},\langle
H^{\top}_{i,:},\cdot\rangle)$, constructed using (7)–(8), as follows:

$\displaystyle\tilde{g}_{d,i}(\underline{\xi},\overline{\xi};H^{\top}_{i,:},\langle
H^{\top}_{i,:},\cdot\rangle)\leq\tilde{g}_{i}(\xi)\leq\tilde{g}_{d,i}(\overline{\xi},\underline{\xi};H^{\top}_{i,:},\langle
H^{\top}_{i,:},\cdot\rangle),$

where, by [26, Lemma 3] and defining $m\triangleq H^{\top}_{i,:}$, we obtain
$\tilde{g}_{d,i}(\overline{\xi},\underline{\xi};{m},\langle{m},\cdot\rangle)=\tilde{f}_{i}(\zeta^{+}_{m})+{m}^{\top}(\zeta^{-}_{{m}}-\zeta^{+}_{{m}})$,
$\tilde{g}_{d,i}(\underline{\xi},\overline{\xi};{m}^{\top},\langle{m},\cdot\rangle)=\tilde{f}_{i}(\zeta^{-}_{{m}})+{m}^{\top}(\zeta^{+}_{{m}}-\zeta^{-}_{{m}})$,
$\zeta^{+}_{m}\triangleq\zeta_{m}({\xi},\underline{\xi})$,
$\zeta^{-}_{m}\triangleq\zeta_{m}(\underline{\xi},\overline{\xi})$, with
$\zeta_{m}(\cdot,\cdot)$ given in (8).

###### Proof.

The proof follows the lines of the proof of [26, Lemma 1, Proposition 10 and
Corollary 2]. ∎

##  III Problem Formulation

_System Assumptions._ Consider the following bounded-error nonlinear
constrained discrete-time system:

$\displaystyle\begin{array}[]{ll}x_{k+1}&=\hat{f}(x_{k},w_{k},u_{k})=f(z_{k}),\\\
\hat{\mu}(x_{k},u_{k})&=\mu(x_{k})\in\mathcal{Y}_{k},\
x_{0}\in\hat{\mathcal{X}}_{0},w_{k}\in\mathcal{W}_{k},\end{array}$ (12)

where $z_{k}\triangleq[x^{\top}_{k}w^{\top}_{k}]^{\top}$,
$x_{k}\in\mathbb{R}^{n_{x}}$ is the state vector,
$w_{k}\in\mathcal{W}_{k}\subset\mathbb{R}^{n_{w}}$ is the augmentation of all
the exogenous uncertain inputs, e.g., bounded process disturbance/noise and
internal uncertainties such as uncertain parameters and
$u_{k}\in\mathcal{U}_{k}\subseteq\mathbb{R}^{n_{u}}$ is the _known_ input
signal. Furthermore, $f:\mathbb{R}^{n_{z}}\to\mathbb{R}^{n_{x}}$ (with
$n_{z}\triangleq n_{x}+n_{w}$) and
$\mu:\mathbb{R}^{n_{x}}\to\mathbb{R}^{n_{\mu}}$ are nonlinear state vector
field and observation/constraint mapping, respectively, which are well-
defined, given $\hat{f}(\cdot,\cdot)$ and $\hat{\mu}(\cdot,\cdot)$, as well as
the fact that $u_{k}$ is known. Note that the mapping $\mu(\cdot)$ along with
the set $\mathcal{Y}_{k}$ characterize all the existing and/or a prior known
or even manufactured/redundant constraints over the states, observations and
measurement noise signals or uncertain parameters at time step $k$..

The initial state estimate $\hat{\mathcal{X}}_{0}$ is assumed to be a known
set a prior. Moreover, we assume the following assumptions.

######  Assumption 1.

The sets $\hat{\mathcal{X}}_{0}$, as well as
$\mathcal{W}_{k},\mathcal{U}_{k},\forall k\geq 0$ are prior known polytopes,
or equivalently constrained zonotopes or zonotope bundles (cf. Definition 1).

######  Assumption 2.

The nonlinear vector fields $f(\cdot)$ and $\mu(\cdot)$ are locally Lipschitz
on their domains. Consequently, they are differentiable and have bounded
Jacobian matrix elements, almost everywhere. We further assume that given any
$\mathcal{Z}\subset\mathbb{R}^{n_{z}}$ and
$\mathcal{X}\subset\mathbb{R}^{n_{x}}$, some upper and lower bounds for all
elements of Jacobian matrices for $f(\cdot)$ and $\mu(\cdot)$ over
$\mathcal{Z}$ and $\mathcal{X}$ are available or can be computed. In other
words,
$\exists\underline{{J}}^{f},\overline{{J}}^{f}\in\mathbb{R}^{n_{x}\times
n_{z}},\underline{{J}}^{\mu},\overline{{J}}^{\mu}\in\mathbb{R}^{n_{\mu}\times
n_{x}}$, such that:
$\underline{{J}}^{f}\leq{{J}}^{f}(z)\leq\overline{{J}}^{f},\underline{{J}}^{\mu}\leq{{J}}^{\mu}(x)\leq\overline{{J}}^{\mu},\forall
z\in{\mathcal{Z}},\forall x\in\mathcal{X}$, where ${J}^{f}(z)$ and
${J}^{\mu}(x)$ denote the Jacobian matrices of the mappings $f(\cdot)$ and
$\mu(\cdot)$ at the points $z$ and $x$, respectively.

In this paper, we aim to propose novel set-membership approaches for obtaining
set-valued state estimates for bounded-error nonlinear systems in the form of
(12). More formally, proceeding the well-known two-step i) Propagation
(prediction), ii) update (refinement) approach and given the initial
uncertainty set $\hat{\mathcal{X}}_{0}$, we seek to solve the following
corresponding problems at each time step $k\in\mathbb{N}$ (where
$\mathcal{Z}_{k}\triangleq\mathcal{X}^{u}_{k}\times\mathcal{U}_{k},\mathcal{X}^{p}_{0}\triangleq\hat{\mathcal{X}}_{0}$):

######  Problem 1 (Propagation).

Find the “propagated set” $\mathcal{X}^{p}_{k}$ that satisfies

$\displaystyle
f(\mathcal{Z}_{k-1})\triangleq\\{\hat{f}(x,w,u_{k-1})|x\in\mathcal{X}^{u}_{k-1},w\in\mathcal{W}_{k}\\}\subseteq\mathcal{X}^{p}_{k}.$
(13)

######  Problem 2 (Update).

Find the updated set $\mathcal{X}^{u}_{k}$ that satisfies

$\displaystyle\mathcal{X}^{p}_{k}\cap_{\mu}\mathcal{Y}_{k}\triangleq\\{x\in\mathcal{X}^{p}_{k}|\mu(x)\in\mathcal{Y}_{k}\\}\subseteq\mathcal{X}^{u}_{k}.$
(14)

##  IV Main Results

To address the above problems, we propose set-theoretic approaches which are
based on our recently developed tight remainder-form mixed-monotone
decomposition functions [26] (also cf. Proposition 4 and Corollary 1), to
compute supersets of i) $f(\mathcal{Z})$, and ii)
$\mathcal{Z}_{f}\cap_{\mu}\mathcal{Z}_{\mu}$, given locally Lipschitz
functions $f,\mu$ that satisfy Assumption 2 and arbitrary sets
$\mathcal{Z},\mathcal{Z}_{f},\mathcal{Z}_{\mu}$ that satisfy Assumption 1.
Then, armed with the aforementioned proposed set-membership approaches, we
sequentially apply the one-step operations in (13) and (14) at each time step
$k\in\mathbb{N}$ to system (12), with the purpose of computing i) the
propagated set $\mathcal{X}^{p}_{k}$ that satisfies the inclusion in (13), and
ii) the updated set $\mathcal{X}^{u}_{k}$ that satisfies the inclusion in
(14), respectively.

###  IV-A Decomposition-Based ZB/CZ propagation

In this section, we address Problem 1, assuming that the initial set is a
zonotope bundle (Lemma 1) or a constraint zonotope (Lemma 2). The main idea is
to “lift up” the initial ZB/CZ’s from the $z$-space, i.e., the space of
augmented state $x$ and process uncertainty $w$, to intervals in the
$\xi$-space, i.e., the space of ZB/CZ generators. Then, based on our recent
results in [26], we decompose the transformed vector fields in the $\xi$-space
into two components, a Jacobian sign stable (JSS) and a linear remainder
mapping (cf. Corollary 1). Finally, we apply our recently developed family of
mixed-monotone remainder-form decomposition functions to find enclosures to
the JSS components, with interval domains, which are proven to be tight by
Corollary 1. Using these tight obtained bounds and thanks to linearity of the
remainders, we show that by augmenting and intersecting all the obtained
enclosures, the resultant set is a ZB/CZ. We formally summarize our proposed
Decomposition-Based ZB/CZ approach through the following Lemmas 1 and 2.

######  Lemma 1 (Decomposition-Based ZB Propagation).

Let $f:\mathcal{Z}\subset\mathbb{R}^{n_{z}}\to\mathbb{R}^{n_{x}}$ satisfies
Assumption 2. Let $\mathcal{Z}$ be a ZB in $\mathbb{R}^{n_{z}}$, i.e.,
$\mathcal{Z}=\bigcap\limits_{s=1}^{S}\\{G_{s},c_{s}\\}_{Z}$, and $\forall
s\in\mathbb{N}_{S}\triangleq\\{1,\dots,S\\}$, $n_{s}$ be the number of
generators of the corresponding zonotope. Then, the following set inclusion
holds:

$\displaystyle
f(\mathcal{Z})\subseteq\mathcal{ZB}_{f}\triangleq\bigcap\limits_{s=1}^{S}\bigcap\limits_{H_{s}\in\mathbf{H}_{\tilde{f}_{s}}}\\{G^{H_{s}}_{s},c^{H_{s}}_{s}\\}_{Z},$
(15)

where $G^{H_{s}}_{s}\triangleq[H_{s}\
\frac{1}{2}\textstyle{\mathrm{diag}}(\overline{g}^{H_{s}}_{s}-\underline{g}^{H_{s}}_{s})],\
c^{H_{s}}_{s}\triangleq\frac{1}{2}(\overline{g}^{H_{s}}_{s}+\underline{g}^{H_{s}}_{s})$,

$\displaystyle\overline{g}^{H_{s}}_{s,i}\triangleq
g^{s}_{i,d}(\mathbf{1}_{n_{s}},-\mathbf{1}_{n_{s}};{H_{s}^{\top}}_{(i,:)},\langle{H_{s}^{\top}}_{(i,:)},\cdot\rangle),$
(16) $\displaystyle\underline{g}^{H_{s}}_{s,i}\triangleq
g^{s}_{i,d}(-\mathbf{1}_{n_{s}},\mathbf{1}_{n_{s}};{H_{s}^{\top}}_{(i,:)},\langle{H_{s}^{\top}}_{(i,:)},\cdot\rangle),$
(17)

$g^{s}_{i,d}(\cdot,\cdot;{H_{s}^{\top}}_{(i,:)},\langle{H_{s}^{\top}}_{(i,:)},\cdot\rangle)$
is the tight mixed-monotone decomposition function (cf. Proposition 4) for the
JSS mapping
$g^{H_{s}}_{s,i}(\xi)\triangleq\tilde{f}_{s,i}(\xi)-\langle{H_{s}^{\top}}_{(i,:)},\xi\rangle:\mathbb{B}^{n_{s}}_{\infty}\to\mathbb{R}^{n_{x}}$,
$\mathbf{H}_{\tilde{f}_{s}}$ is defined in Corollary 1 (with the corresponding
function being $\tilde{f}_{s}$) and $\tilde{f}_{s}(\xi)\triangleq
f({c}_{s}+{G}_{s}\xi)$.

###### Proof.

To show (15), $\forall s\in\mathbb{N}_{S}$, consider the zonotope
$\mathcal{Z}_{s}\triangleq\\{G_{s},c_{s}\\}_{Z}\triangleq\\{z=G_{s}\xi+c_{s}|\xi\in\mathbb{B}^{n_{s}}_{\infty}\\}$
and let us define
$\tilde{f}_{s}(\xi):\mathbb{B}^{n_{s}}_{\infty}\to\mathbb{R}^{n_{x}}\triangleq
f(G_{s}\xi+c_{s})$ that implies

$\displaystyle
f(\mathcal{Z}_{s})\subseteq\tilde{f}_{s}(\mathbb{B}^{n_{s}}_{\infty}),\forall
s\in\mathbb{N}_{S}.$ (18)

On the other hand, note that by Corollary 1, $\forall
H_{s}\in\mathbf{H}_{\tilde{f}_{s}}$, $\tilde{f}_{s}(\cdot)$ can be decomposed
as

$\displaystyle\tilde{f}_{s}(\xi)=g^{H_{s}}_{s}(\xi)+H_{s}\xi,\forall
s\in\mathbb{N}_{S},\forall\xi\in\mathbb{B}^{n_{s}}_{\infty},\forall
H_{s}\in\mathbf{H}_{\tilde{f}_{s}}$ (19)

where $g^{H_{s}}_{s}(\xi)$ is a JSS function in $\mathbb{B}^{n_{s}}_{\infty}$
and $\mathbf{H}_{\tilde{f}_{s}}$ can be computed from (9), with the
corresponding function being $\tilde{f}_{s}$. Now (18) and (19) together
imply:

$\displaystyle f(\mathcal{Z}_{s})\subseteq
g^{H_{s}}_{s}(\mathbb{B}^{n_{s}}_{\infty})\oplus
H_{s}\mathbb{B}^{n_{s}}_{\infty},\forall s\in\mathbb{N}_{S},\forall
H_{s}\in\mathbf{H}_{\tilde{f}_{s}}.$ (20)

Again, it follows from Corollary 1 and the fact that $g^{H_{s}}_{s}(\xi)$ is a
JSS function that in each dimension $i\in\mathbb{N}_{n_{x}}$,
$g^{H_{s}}_{s,i}(\xi)$ can be tightly bounded as
$\underline{g}^{H_{s}}_{s,i}\leq
g^{H_{s}}_{s,i}(\xi)\leq\overline{g}^{H_{s}}_{s,i},\forall\xi\in\mathbb{B}^{n_{s}}_{\infty},\forall
H_{s}\in\mathbf{H}_{\tilde{f}_{s}}$, with
$\overline{g}^{H_{s}}_{s,i},\underline{g}^{H_{s}}_{s,i}$ given in (16) and
(17), respectively. Augmenting all these $\mathbb{N}_{nx}$ one-dimensional
inequalities yields the following set inclusion for all $s\in\mathbb{N}_{S}$
and all $H_{s}\in\mathbf{H}_{\tilde{f}_{s}}$:
${g}^{H_{s}}_{s}(\mathbb{B}^{n_{s}}_{\infty})\subseteq[\underline{g}^{H_{s}}_{s},\overline{g}^{H_{s}}_{s}]=\frac{1}{2}((\underline{g}^{H_{s}}_{s}+\overline{g}^{H_{s}}_{s})\oplus\textstyle{\mathrm{diag}}(\overline{g}^{H_{s}}_{s}-\underline{g}^{H_{s}}_{s})\mathbb{B}^{n_{x}}_{\infty})$,
where the last equality follows from Proposition 1. This, (20) and the fact
that the inclusion in (20) holds for all $s\in\mathbb{N}_{S}$ and all
$H_{s}\in\mathbf{H}_{\tilde{f}_{s}}$ and hence for the intersection of all of
them, return the result in (15). ∎

######  Lemma 2 (Decomposition-Based CZ Propagation).

Let $f:\mathcal{Z}\subset\mathbb{R}^{n_{z}}\to\mathbb{R}^{n_{x}}$ satisfies
Assumption 2. Let $\mathcal{Z}$ be a CZ in $\mathbb{R}^{n_{z}}$, i.e.,
$\mathcal{Z}=\\{\tilde{G},\tilde{c},\tilde{A},\tilde{b}\\}_{CZ}$, and $n_{g}$
be the number of generators of $\mathcal{Z}$. Then, the following set
inclusion holds:

$\displaystyle
f(\mathcal{Z})\subseteq\mathcal{CZ}_{f}\triangleq\bigcap\limits_{H\in\mathbf{H}_{\tilde{f}}}\\{\tilde{G}^{H},\tilde{c}^{H},\mathbb{A},\tilde{b}\\}_{CZ},$
(21)

where $\tilde{G}^{H}\triangleq[H\ \
\frac{1}{2}\textstyle{\mathrm{diag}}(\overline{g}^{H}-\underline{g}^{H})],\mathbb{A}\triangleq[\tilde{A}\
\ 0_{n_{g}\times n_{x}}]$,

$\displaystyle\overline{g}^{H}_{i}$
$\displaystyle\triangleq\tilde{g}_{i,d}(\overline{\mathbf{l}}_{n_{g}},\underline{\mathbf{l}}_{n_{g}};H^{\top}_{i,:},\langle
H^{\top}_{i,:},\cdot\rangle),\tilde{c}^{H}\triangleq\frac{1}{2}(\overline{g}^{H}+\underline{g}^{H}),$
(22) $\displaystyle\underline{g}^{H}_{i}$
$\displaystyle\triangleq\tilde{g}_{i,d}(\underline{\mathbf{l}}_{n_{g}},\overline{\mathbf{l}}_{n_{g}};H^{\top}_{i,:},\langle
H^{\top}_{i,:},\cdot\rangle),$ (23)
$\displaystyle\overline{\mathbf{l}}_{n_{g}}$
$\displaystyle\triangleq\min(\mathbf{1}_{n_{g}},\tilde{A}^{\dagger}\tilde{b}+\kappa\mathbf{r}_{n_{g}}),\underline{\mathbf{l}}_{n_{g}}\triangleq\max(-\mathbf{1}_{n_{g}},\tilde{A}^{\dagger}\tilde{b}-\kappa\mathbf{r}_{n_{g}})$

$\tilde{g}_{i,d}(\cdot,\cdot;H^{\top}_{i,:},\langle
H^{\top}_{i,:},\cdot\rangle)$ is the tight mixed-monotone decomposition
function (cf. Proposition 4) for the JSS mapping
$\tilde{g}_{i}(\xi)\triangleq\tilde{f}_{i}(\xi)-\langle
H^{\top}_{i,:},\xi\rangle:\mathbb{B}^{n_{g}}_{\infty}\to\mathbb{R}^{n_{x}}$,
$\mathbf{H}_{\tilde{f}}$ is defined in Corollary 1 and
$\tilde{f}(\xi)\triangleq f(\tilde{c}+\tilde{G}\xi)$,
$\mathbf{r}_{n_{g}}\triangleq\textstyle{\mathrm{rowsupp}}(I_{n_{g}}-\tilde{A}^{\dagger}\tilde{A})$
and $\kappa$ is a very large positive real number (infinity).

###### Proof.

To prove the inclusion in (21), consider the constrained zonotope
representation of the set $\mathcal{Z}$, i.e.,
$\mathcal{Z}\triangleq\\{\tilde{G},\tilde{c},\tilde{A},\tilde{b}\\}_{CZ}\triangleq\\{z=\tilde{G}\xi+c|\xi\in\mathbb{B}^{n_{g}}_{\infty},\tilde{A}\xi=\tilde{b}\\}$.
Using similar notation as in the proof of Lemma 1, let us define
$\tilde{f}(\xi):\mathbb{B}^{n_{g}}_{\infty}\to\mathbb{R}^{n_{x}}\triangleq
f(\tilde{G}\xi+\tilde{c})$ that consequently return

$\displaystyle
f({\mathcal{Z}})\subseteq\\{\tilde{f}(\xi)|\xi\in\mathbb{B}^{n_{g}}_{\infty},\tilde{A}\xi=\tilde{b}\\}.$
(24)

Note that by [28, Theorem 2],
$\tilde{A}\xi=\tilde{b}\Rightarrow\xi\in\mathbb{I}{\Xi}\triangleq[\tilde{A}^{\dagger}\tilde{b}-\kappa\mathbf{r}_{n_{g}},\tilde{A}^{\dagger}\tilde{b}-\kappa\mathbf{r}_{n_{g}}]$,
where
$\mathbf{r}_{n_{g}}\triangleq\textstyle{\mathrm{rowsupp}}(I_{n_{g}}-\tilde{A}^{\dagger}\tilde{A})$
and $\kappa$ is a very large positive real number. This, in addition to the
fact that $\xi\in\mathbb{B}^{n_{g}}_{\infty}$ (cf. (24)), imply that
$\xi\in\mathbb{I}\tilde{\Xi}\triangleq\mathbb{I}{\Xi}\cap\mathbb{B}^{n_{g}}_{\infty}=[\underline{\mathbf{l}}_{n_{g}},\overline{\mathbf{l}}_{n_{g}}]$,
where $\underline{\mathbf{l}}_{n_{g}},\overline{\mathbf{l}}_{n_{g}}$ are
defined below (23). On the other hand, similar to the proof of Lemma 1, using
Corollary 1 we conclude that $\forall H\in\mathbf{H}_{\tilde{f}}$,
$\tilde{f}(\cdot)$ can be decomposed as

$\displaystyle\begin{array}[]{rl}\tilde{f}(\xi)&=\tilde{g}^{H}(\xi)+H\xi,\ \ \
\forall H\in\mathbf{H}_{\tilde{f}},\forall\xi\in\mathbb{I}\tilde{\Xi},\\\
\Rightarrow\tilde{f}(\mathbb{I}\tilde{\Xi})&\subseteq\tilde{g}^{H}(\mathbb{I}\tilde{\Xi})\oplus
H\mathbb{I}\tilde{\Xi},\forall H\in\mathbf{H}_{\tilde{f}},\end{array}$ (27)

where $\tilde{g}^{H}(\xi)$ is a JSS function in $\mathbb{I}\tilde{\Xi}$ and
$\mathbf{H}_{\tilde{f}}$ is given in (9). Also, by Corollary 1, in each
dimension $i\in\mathbb{N}_{n_{x}}$, $\tilde{g}^{H}_{i}(\xi)$ can be tightly
bounded as
$\underline{{g}}^{H}_{i}\leq\tilde{g}^{H}_{i}(\xi)\leq\overline{{g}}^{H}_{i},\forall\xi\in\mathbb{I}\tilde{\Xi},\forall
H\in\mathbf{H}_{\tilde{f}}$, with
$\overline{{g}}^{H}_{i},\underline{{g}}^{H}_{i}$ given in (22) and (23),
respectively. Augmenting all these $\mathbb{N}_{nx}$ one-dimensional
inequalities, as well as Proposition 1 yield the following set inclusion:
$\forall H\in\mathbf{H}_{\tilde{f}}$:

$\displaystyle\tilde{g}^{H}(\mathbb{I}\tilde{\Xi})\subseteq[\underline{g}^{H},\overline{g}^{H}]=\frac{1}{2}((\underline{g}^{H}+\overline{g}^{H})\oplus\textstyle{\mathrm{diag}}(\overline{g}^{H}-\underline{g}^{H})\mathbb{B}^{n_{x}}_{\infty}).$

This, (24), (27) and the fact that the inclusion in (27) holds for all
$H\in\mathbf{H}_{\tilde{f}}$ and hence for the intersection of all of them,
return: $\forall
H\in\mathbf{H}_{\tilde{f}}:f({\mathcal{Z}})\subseteq\\{H\xi+\textstyle{\mathrm{diag}}(\overline{g}^{H}-\underline{g}^{H})\theta+\frac{1}{2}((\underline{g}^{H}+\overline{g}^{H})|\xi\in\mathbb{B}^{n_{g}}_{\infty},\theta\in\mathbb{B}^{n_{x}}_{\infty},\tilde{A}\xi=\tilde{b}\\}$,
where the set on the right hand side of the inclusion is equivalent to the
intersection of the CZs on the right hand side of (21). ∎

Finally, for further improvement, we can take the intersection of the
resultant propagated sets in Lemmas 1 and 2. This, is formally summarized in
the following Theorem 1.

######  Theorem 1 (Decomposition-Based ZB/CZ Propagation).

Suppose all the assumptions in Lemmas 1 and 2 hold. Then,
$f(\mathcal{Z})\subseteq\mathcal{ZB}_{f}\cap\mathcal{CZ}_{f}$, where
$\mathcal{ZB}_{f},\mathcal{CZ}_{f}$ are computed in Lemmas 1 and 2,
respectively.

###### Proof.

It follows from Lemmas 1 and 2 that $f(\mathcal{Z})\subseteq\mathcal{ZB}_{f}$
and $f(\mathcal{Z})\subseteq\mathcal{CZ}_{f}$, and so
$f(\mathcal{Z})\subseteq\mathcal{ZB}_{f}\cap\mathcal{CZ}_{f}$. ∎

###  IV-B Decomposition-Based CZ/ZB update

In this section, we address Problem 2, given a locally Lipschitz nonlinear
vector field $\mu(\cdot)$ and assuming that the initial propagated and the
observation/constraint sets are zonotope bundles (Lemma 3) or constraint
zonotopes (Lemma 4). Using similar idea as in Section IV-A, i.e, lifting to
the space of generators, decomposing the transformed observation function into
a JSS and a linear component, applying the tight remainder-form decomposition
functions [26] to bound the JSS component, augmenting and intersecting, as
well as taking the advantage of linear remainder functions, we obtain ZB/CZ
enclosures to the nonlinear generalized intersection in (14). The results of
this section are summarized in Lemmas 3 and 4 and Theorem 2.

######  Lemma 3 (Decomposition-Based ZB Update).

Let $\mu:\mathbb{R}^{n_{x}}\to\mathbb{R}^{n_{\mu}}$ satisfies Assumption 2.
Let $\mathcal{Z}_{f}\subset\mathbb{R}^{n_{x}}$ and
$Z_{\mu}\subset\mathbb{R}^{n_{\mu}}$ be two ZB sets, i.e.,
$\mathcal{Z}_{f}=\mathcal{ZB}_{f}=\bigcap\limits_{r=1}^{R}\\{G_{f}^{r},c_{f}^{r}\\}_{Z}$
and
$\mathcal{Z}_{\mu}=\mathcal{ZB}_{\mu}=\bigcap\limits_{t=1}^{T}\\{G_{\mu}^{t},c_{\mu}^{t}\\}_{Z}$,
and $\forall r\in\mathbb{N}_{R}\triangleq\\{1,\dots,R\\},\forall
t\in\mathbb{N}_{T}\triangleq\\{1,\dots,T\\}$, $n_{r},n_{t}$ be the number of
generators of the corresponding zonotopes, respectively. Then, the following
set inclusion holds:

$\displaystyle\mathcal{ZB}_{f}\cap_{\mu}\mathcal{ZB}_{\mu}\subseteq\mathcal{ZB}_{u}\triangleq\bigcap\limits_{r=1}^{R}\bigcap\limits_{t=1}^{T}\bigcap\limits_{Q_{r}\in\mathbf{Q}_{\tilde{\mu}_{r}}}\\{\hat{G}^{t}_{r},\hat{c}_{r},\hat{A}^{Q_{r}}_{r,t},\hat{b}^{Q_{r}}_{r,t}\\}_{CZ},$
(28)

where $\hat{G}^{t}_{r}\triangleq[{G}^{r}_{f}\
\mathbf{0}^{t}],\hat{c}_{r}\triangleq c^{r}_{f},\
\hat{b}^{Q_{r}}_{r,t}\triangleq
c^{t}_{\mu}-\frac{1}{2}(\overline{p}^{Q_{r}}_{r}+\underline{p}^{Q_{r}}_{r})$,

$\displaystyle\hat{A}^{Q_{r}}_{r,t}$
$\displaystyle\triangleq\begin{bmatrix}Q_{r}&-G^{t}_{\mu}&\frac{1}{2}\textstyle{\mathrm{diag}}(\overline{p}^{Q_{r}}_{r}-\underline{p}^{Q_{r}}_{r})\end{bmatrix},$
$\displaystyle\overline{p}^{Q_{r}}_{r,i}$ $\displaystyle\triangleq
p^{r}_{i,d}(\mathbf{1}_{n_{r}},-\mathbf{1}_{n_{r}};Q^{\top}_{r(i,:)},\langle
Q^{\top}_{r(i,:)},\cdot\rangle),$ (29)
$\displaystyle\underline{p}^{Q_{r}}_{r,i}$ $\displaystyle\triangleq
p^{r}_{i,d}(-\mathbf{1}_{n_{r}},\mathbf{1}_{n_{r}};Q^{\top}_{r(i,:)},\langle
Q^{\top}_{r(i,:)},\cdot\rangle),$ (30)

$p^{r}_{i,d}(\cdot,\cdot;Q_{r},\langle Q^{\top}_{r(i,:)},\cdot\rangle)$ is the
tight mixed-monotone decomposition function (cf. Proposition 4) for the JSS
mapping $p^{Q_{r}}_{r,i}(\alpha)\triangleq\tilde{\mu}_{r,i}(\alpha)-\langle
Q^{\top}_{r(i,:)},\alpha\rangle:\mathbb{B}^{n_{r}}_{\infty}\to\mathbb{R}^{n_{\mu}}$,
$\mathbf{Q}_{\tilde{\mu}_{r}}$ is defined similar to $\mathbf{H}_{f}$ in
Corollary 1 (with the corresponding function being
$\tilde{\mu}_{r}(\alpha)\triangleq\mu(c^{r}_{f}+G^{r}_{f}\alpha)$) and
$\mathbf{0}^{t}$ is a zero matrix in
$\mathbb{R}^{n_{x}\times(n_{t}+n_{\mu})}$.

###### Proof.

Suppose $z\in\mathcal{ZB}_{f}\cap_{\mu}\mathcal{ZB}_{\mu}$. Then by definition
of the operator $\cap_{\mu}$ (cf. (14)), $z\in\mathcal{ZB}_{f}$ and
$\mu(z)\in\mathcal{ZB}_{\mu}$. The former implies that $\forall
r\in\mathbb{N}_{R},\exists\alpha\in\mathbb{B}^{n_{r}}_{\infty}$ such that
$z=G^{r}_{f}\alpha+c^{r}_{f}$, while it follows from the latter that
$\mu(z)=\mu(G^{r}_{f}\alpha+c^{r}_{f})\triangleq\tilde{\mu}_{r}(\alpha)\in\mathcal{ZB}_{\mu}\Rightarrow\forall
t\in\mathbb{N}_{T},\exists\zeta\in\mathbb{B}^{n_{t}}_{\infty}$, such that
$\tilde{\mu}_{r}(\alpha)=c^{t}_{\mu}+G^{t}_{\mu}\zeta$. Putting these two
results in a set representation form, we obtain:

$\displaystyle
z\in\bigcap\limits_{r=1}^{R}\bigcap\limits_{t=1}^{T}\\{G^{r}_{f}\alpha+c^{r}_{f}|\tilde{\mu}_{r}(\alpha)=c^{t}_{\mu}+G^{t}_{\mu}\zeta,\alpha\in\mathbb{B}^{n_{r}}_{\infty},\zeta\in\mathbb{B}^{n_{t}}_{\infty}\\}$
(31)

On the other hand, using Corollary 1, $\tilde{\mu}_{r}(\cdot)$ can be
decomposed into a JSS and a linear mapping as follows: $\forall
r\in\mathbb{N}_{R},\forall
Q_{r}\in\mathbf{Q}_{\tilde{\mu}_{r}},\forall\alpha\in\mathbb{B}^{n_{r}}_{\infty}$:

$\displaystyle\tilde{\mu}_{r}(\alpha)=p^{Q_{r}}_{r}(\alpha)+Q_{r}\alpha.$ (32)

Moreover, by the same corollary, the JSS component $p^{Q_{r}}_{r}(\cdot)$ is
tightly bounded as follows: $\forall i\in\mathbb{N}_{n_{\mu}},\forall
Q_{r}\in\mathbf{Q}_{\tilde{\mu}_{r}},\underline{p}^{Q_{r}}_{r,i}\leq
p^{Q_{r}}_{r.i}(\alpha)\leq\underline{p}^{Q_{r}}_{r,i},\forall\alpha\in\mathbb{B}^{n_{r}}_{\infty}$,
with $\underline{p}^{Q_{r}}_{r,i},\overline{p}^{Q_{r}}_{r,i}$ given in (29)
and (30), respectively. This, as well as (32) and Proposition 1 imply $\forall
r\in\mathbb{N}_{R},\forall
Q_{r}\in\mathbf{Q}_{\tilde{\mu}_{r}},\forall\alpha\in\mathbb{B}^{n_{r}}_{\infty},\exists\theta\in\mathbb{B}^{n_{\mu}}_{\infty}$
such that
$\tilde{\mu}_{r}(\alpha)=\frac{1}{2}(\underline{p}^{Q_{r}}_{r,i}+\overline{p}^{Q_{r}}_{r,i})+\frac{1}{2}\textstyle{\mathrm{diag}}(\overline{p}^{Q_{r}}_{r,i}-\underline{p}^{Q_{r}}_{r,i})\theta+Q_{r}\alpha$,
that along with (31) returns
$z\in\bigcap\limits_{r=1}^{R}\bigcap\limits_{t=1}^{T}\bigcap\limits_{Q_{t}\in\mathbf{Q}_{\tilde{\mu}_{t}}}\\{G^{r}_{f}\alpha+c^{r}_{f}|\frac{1}{2}(\underline{p}^{Q_{r}}_{r,i}+\overline{p}^{Q_{r}}_{r,i})+\frac{1}{2}\textstyle{\mathrm{diag}}(\overline{p}^{Q_{r}}_{r,i}-\underline{p}^{Q_{r}}_{r,i})\theta+Q_{r}\alpha=c^{t}_{\mu}+G^{t}_{\mu}\zeta,\alpha\in\mathbb{B}^{n_{r}}_{\infty},\zeta\in\mathbb{B}^{n_{t}}_{\infty},\theta\in\mathbb{B}^{n_{\mu}}_{\infty}\\}$,
where the set on the right hand side is equivalent to the one on the right
hand side of (28). ∎

######  Lemma 4 (Decomposition-Based CZ Update).

Let $\mu:\mathbb{R}^{n_{x}}\to\mathbb{R}^{n_{\mu}}$ satisfies Assumption 2.
Let $\mathcal{Z}_{f}\subset\mathbb{R}^{n_{x}}$ and
$\mathcal{Z}_{\mu}\subset\mathbb{R}^{n_{\mu}}$ be two CZ sets, i.e.,
$\mathcal{Z}_{f}=\mathcal{CZ}_{f}=\\{\tilde{G}_{f},\tilde{c}_{f},\tilde{A}_{f},\tilde{b}_{f}\\}_{CZ}$
and
$\mathcal{Z}_{\mu}=\mathcal{CZ}_{\mu}=\\{\tilde{G}_{\mu},\tilde{c}_{\mu},\tilde{A}_{\mu},\tilde{b}_{\mu}\\}_{CZ}$,
and $n_{c},n_{\tau}$ be the number of generators of
$\mathcal{Z}_{f},\mathcal{Z}_{\mu}$, respectively. Then, the following set
inclusion holds:

$\displaystyle\mathcal{CZ}_{f}\cap_{\mu}\mathcal{CZ}_{\mu}\subseteq\mathcal{CZ}_{u}\triangleq\bigcap\limits_{\Omega\in\mathbf{\Omega}_{{\lambda}}}\\{\mathbb{G},\tilde{c}_{f},\mathbb{A}_{\Omega},\tilde{b}_{\Omega}\\}_{CZ},$
(33)

where $\mathbb{G}\triangleq[\tilde{G}_{f}\ {0}\ 0],\
\tilde{b}_{\Omega}\triangleq[\tilde{b}^{\top}_{f}\ \tilde{b}^{\top}_{\mu}\
(\tilde{c}_{f}-\frac{1}{2}(\overline{\nu}^{\Omega}+\underline{\nu}^{\Omega}))^{\top}]^{\top}$,

$\displaystyle\mathbb{A}_{\Omega}$
$\displaystyle\triangleq\begin{bmatrix}\tilde{A}_{f}&0&0\\\
0&\tilde{A}_{\mu}&\\\
\Omega&-\tilde{G}_{\mu}&\frac{1}{2}\textstyle{\mathrm{diag}}(\overline{\nu}^{\Omega}-\underline{\nu}^{\Omega})\end{bmatrix},$
$\displaystyle\overline{\nu}^{\Omega}_{i}$
$\displaystyle\triangleq{\nu}_{i,d}(\overline{\mathbf{l}}_{n_{c}},\underline{\mathbf{l}}_{n_{c}};\Omega^{\top}_{(i,:)},\langle\Omega^{\top}_{(i,:)},\cdot\rangle),$
(34) $\displaystyle\underline{\nu}^{\Omega}_{i}$
$\displaystyle\triangleq{\nu}_{i,d}(\underline{\mathbf{l}}_{n_{c}},\overline{\mathbf{l}}_{n_{c}};\Omega^{\top}_{(i,:)},\langle\Omega^{\top}_{(i,:)},\cdot\rangle),$
(35) $\displaystyle\overline{\mathbf{l}}_{n_{c}}$
$\displaystyle\triangleq\min(\mathbf{1}_{n_{c}},\tilde{A}_{f}^{\dagger}\tilde{b}_{f}+\kappa\mathbf{r}_{n_{c}}),\underline{\mathbf{l}}_{n_{c}}\triangleq\max(-\mathbf{1}_{n_{c}},\tilde{A}_{f}^{\dagger}\tilde{b}_{f}-\kappa\mathbf{r}_{n_{c}})$

${\nu}_{i,d}(\cdot,\cdot;{\Omega}^{\top}_{(i,:)},\langle\Omega^{\top}_{(i,:)},\cdot\rangle)$
is the tight mixed-monotone decomposition function (cf. Proposition 4) for the
JSS mapping
$\nu^{\Omega}_{i}(\beta)\triangleq{\lambda}_{i}(\beta)-\langle\Omega^{\top}_{(i,:)},\beta\rangle:\mathbb{B}^{n_{c}}_{\infty}\to\mathbb{R}^{n_{\mu}}$,
$\mathbf{\Omega}_{{\lambda}}$ is defined similar to $\mathbf{H}_{f}$ in
Corollary 1 (with the corresponding function being
${\lambda}(\beta)\triangleq\mu(\tilde{c}_{f}+\tilde{G}_{f}\beta)$),
$\mathbf{r}_{n_{c}}\triangleq\textstyle{\mathrm{rowsupp}}(I_{n_{c}}-\tilde{A}_{f}^{\dagger}\tilde{A}_{f})$
and $\kappa$ is a very large positive real number (infinity).

###### Proof.

Suppose $z\in\mathcal{CZ}_{f}\cap_{\mu}\mathcal{CZ}_{\mu}$. Then by definition
of the operator $\cap_{\mu}$ (cf. (14)), $z\in\mathcal{CZ}_{f}$ and
$\mu(z)\in\mathcal{CZ}_{\mu}$. The former implies that
$\exists\beta\in\mathbb{B}^{n_{c}}_{\infty}$ such that
$\tilde{A}_{f}\beta=\tilde{b}_{f}\land z=\tilde{G}_{f}\beta+\tilde{c}_{f}$,
while it follows from the latter that
$\mu(z)=\mu(\tilde{G}_{f}\beta+\tilde{c}_{f})\triangleq{\lambda}(\beta)\in\mathcal{CZ}_{\mu}\Rightarrow,\exists\gamma\in\mathbb{B}^{n_{\tau}}_{\infty}$,
such that
$\tilde{A}_{\mu}\gamma=\tilde{b}_{\mu}\land{\lambda}(\beta)=\tilde{c}_{\mu}+\tilde{G}_{\mu}\gamma$.
Putting these two results into a set representation form, we obtain:

$\displaystyle
z\in\\{\tilde{G}_{f}\beta+\tilde{c}_{f}|\lambda(\beta)=\tilde{c}_{\mu}+\tilde{G}_{\mu}\gamma,\tilde{A}_{f}\beta=\tilde{b}_{f},\tilde{A}_{\mu}\gamma=\tilde{b}_{\mu},\beta\in\mathbb{B}^{n_{c}}_{\infty},\gamma\in\mathbb{B}^{n_{\tau}}_{\infty}\\}$
(36)

On the other hand, using Corollary 1, $\lambda(\cdot)$ can be decomposed into
a JSS and a linear mapping as follows:

$\displaystyle\forall\Omega\in\mathbf{\Omega}_{\lambda},\forall\beta\in\mathbb{B}^{n_{c}}_{\infty}:\lambda(\beta)={\nu}^{\Omega}(\beta)+\Omega\beta.$
(37)

Further, note that by [28, Theorem 2],
$\tilde{A}_{f}\beta=\tilde{b}_{f}\Rightarrow\beta\in\mathbb{IB}\triangleq[\tilde{A}_{f}^{\dagger}\tilde{b}_{f}-\kappa\mathbf{r}_{n_{c}},\tilde{A}_{f}^{\dagger}\tilde{b}_{f}-\kappa\mathbf{r}_{n_{c}}]$,
where
$\mathbf{r}_{n_{c}}\triangleq\textstyle{\mathrm{rowsupp}}(I_{n_{c}}-\tilde{A}_{f}^{\dagger}\tilde{A}_{f})$
and $\kappa$ is a very large positive real number, which given that
$\beta\in\mathbb{B}^{n_{c}}_{\infty}$, results is
$\beta\in\mathbb{IB}\cap\mathbb{B}^{n_{c}}_{\infty}=[\underline{\mathbf{l}}_{n_{c}},\overline{\mathbf{l}}_{n_{c}}]$.
This and Corollary 1 imply that the JSS component ${\nu}^{\Omega}(\cdot)$ is
tightly bounded as follows: $\forall
i\in\mathbb{N}_{n_{\mu}},\forall\Omega\in\mathbf{\Omega}_{\lambda},\underline{\nu}^{\Omega}_{i}\leq{\nu}^{\Omega}_{i}(\beta)\leq\underline{\nu}^{\Omega}_{i},\forall\beta\in\mathbb{B}^{n_{c}}_{\infty}$,
with $\underline{\nu}^{\Omega}_{i},\overline{\nu}^{\Omega}_{i}$ given in (34)
and (35), respectively. This, (37) and Proposition 1 imply
$\forall\Omega\in\mathbf{\Omega}_{\lambda},\forall\beta\in\mathbb{B}^{n_{c}}_{\infty},\exists\rho\in\mathbb{B}^{n_{\mu}}_{\infty}$
such that
$\lambda(\beta)=\frac{1}{2}(\underline{\nu}^{\Omega}+\overline{\nu}^{\Omega})+\frac{1}{2}\textstyle{\mathrm{diag}}(\overline{\nu}^{\Omega}-\underline{\nu}^{\Omega})\rho+\Omega\alpha$,
which along with (36) returns
$z\in\bigcap\limits_{\Omega\in\mathbf{\Omega}_{\lambda}}\\{\tilde{G}_{f}\beta+\tilde{c}_{f}|\frac{1}{2}(\underline{\nu}^{\Omega}+\overline{\nu}^{\Omega})+\frac{1}{2}\textstyle{\mathrm{diag}}(\overline{\nu}^{\Omega}-\underline{\nu}^{\Omega})\rho+\Omega\beta=\tilde{c}_{\mu}+\tilde{G}_{\mu}\gamma,\tilde{A}_{f}\beta=\tilde{b}_{f},\tilde{A}_{\mu}\gamma=\tilde{b}_{\mu},\beta\in\mathbb{B}^{n_{c}}_{\infty},\gamma\in\mathbb{B}^{n_{\tau}}_{\infty},\rho\in\mathbb{B}^{n_{\mu}}_{\infty}\\}$,
where the set on the right hand side is equivalent to the one on the right
hand side of (28). ∎

We conclude this subsection by combining the results in Lemmas 3 and 4 via the
following Theorem 2.

######  Theorem 2 (Decomposition-Based ZB/CZ Update).

Suppose all the assumptions in Lemmas 3 and 4 hold. Then

$\mathcal{Z}_{f}\cap_{\mu}\mathcal{Z}_{\mu}\subseteq\mathcal{ZB}_{u}\cap\mathcal{CZ}_{u},$

where $\mathcal{ZB}_{u},\mathcal{CZ}_{u}$ are given in Lemmas 3 and 4,
respectively.

###### Proof.

By Lemmas 3 and 4:
$\mathcal{Z}_{f}\cap_{\mu}\mathcal{Z}_{\mu}\subseteq\mathcal{ZB}_{u}$ and
$\mathcal{Z}_{f}\cap_{\mu}\mathcal{Z}_{\mu}\subseteq\mathcal{CZ}_{u}$, and
hence
$\mathcal{Z}_{f}\cap_{\mu}\mathcal{Z}_{\mu}\subseteq\mathcal{ZB}_{u}\cap\mathcal{CZ}_{u}$.
∎

###  IV-C Modifications to The Approach in [1]

The purpose of this subsection is twofold. i) We make a potential
refinement/improvement to the propagation approach in [1, Theorem 2] (recapped
in Proposition 3) through the following Proposition 5, by applying our
previously developed remainder-form decomposition functions to compute
potentially tighter enclosing intervals to Jacobian matrix of $f(\cdot)$. ii)
We propose an update method via Lemma 5, that is based on the “CZ-inclusion”
introduced in [1, Theorem 1] (recapped in Proposition 2). The proposed update
method is applicable to general nonlinear observation functions (similar to
the proposed methods in Lemmas 3 and 4), as opposed to the update (i.e, linear
intersection) approach in [1] that is only applicable when the observation
function is linear.

######  Proposition 5 (Refinement to The Propagation Approach in [1]).

Suppose all the assumptions in Proposition 4 (i.e, [1, Theorem 2]) hold. Then
the set inclusion in (5) holds also with replacing $\mathbb{J}$ with
$\tilde{\mathbb{J}}$ (or the best (tightest) of them), where
$\tilde{\mathbb{J}}$ is an enclosing interval to
$g(x)\triangleq\nabla^{\top}_{x}f(X,W)$ that can be computed by applying
Proposition 4 to the function $g(\cdot)$.

###### Proof.

Directly follows from Proposition 4. ∎

######  Lemma 5 (Update Based on “CZ-Inclusion” in [1]).

Suppose all the assumptions in Lemma 4 hold. Let $x_{0}\in\mathcal{CZ}_{f}$
and $\mathbb{J}^{\mu},\mathbb{J}^{\mu}_{\Delta}\in\mathbb{R}^{n_{\mu}\times
n_{x}}$ be interval matrices satisfying
$J^{\mu}(\mathcal{CZ}_{f})\subseteq\mathbb{J}^{\mu}$ and $\forall
i\in\mathbb{N}_{n_{\mu}},\forall
j\in\mathbb{N}_{n_{x}},[\mathbb{J}^{\mu}_{\Delta}]_{ij}\triangleq\frac{1}{2}\begin{bmatrix}-\textstyle{\mathrm{diam}}(\mathbb{J}^{\mu})_{ij}&\textstyle{\mathrm{diam}}(\mathbb{J}^{\mu})_{ij}\end{bmatrix}$,
where $J^{\mu}$ denotes the Jacobian of $\mu(\cdot)$. Let
$\overline{\mathcal{Z}}_{f}=\\{\overline{G}^{f},\overline{c}^{f}\\}_{Z}$ be a
zonotope satisfying $\mathcal{CZ}_{f}\ominus
x_{0}\subseteq\overline{\mathcal{Z}}_{f}$, with
$\overline{c}^{f}\in\mathbb{R}^{\overline{n}}$. Let
$\mathbf{m}^{\mu}\in\mathbb{R}^{n_{\mu}}$ be an interval vector such that
$\mathbf{m}^{\mu}\supset\mathbb{J}_{\Delta}^{\mu}\overline{c}^{f}$ and
$\textstyle{\mathrm{mid}}(\mathbf{m}^{\mu})=\mathbf{0}_{n_{\mu}}$. Let
$P^{\mu}\in\mathbb{R}^{n_{\mu}\times n_{\mu}}$ be a diagonal matrix defined as
follows: $\forall i=1,\dots,n_{\mu}$:

$\displaystyle
P^{\mu}_{ii}=\frac{1}{2}\textstyle{\mathrm{diam}}(\mathbf{m}^{\mu})_{i}+\frac{1}{2}\sum_{j=1}^{\overline{n}}\sum_{k=1}^{n_{x}}\textstyle{\mathrm{diam}}(\mathbb{J}^{\mu}_{\Delta})_{ik}|\overline{G}^{f}_{kj}|.$
(38)

Then, the following set inclusion holds:

$\displaystyle\mathcal{CZ}_{f}\cap_{\mu}\mathcal{CZ}_{\mu}\subseteq\mathcal{CZ}^{R}_{u}\triangleq\\{{G}_{u},{c}_{u},{A}_{u},{b}_{u}\\}_{CZ},$
(39)

where
${b}_{u}\triangleq[(\tilde{c}_{\mu}-\mu(x_{0})+\textstyle{\mathrm{mid}}(\mathbb{J}^{\mu})(x_{0}-\tilde{c}_{f})-c_{R})^{\top}\
\tilde{b}^{\top}_{f}\ \tilde{b}^{\top}_{\mu}\ {b}^{\top}_{R}]^{\top}$

$\displaystyle{A}_{u}$
$\displaystyle\triangleq\begin{bmatrix}\textstyle{\mathrm{mid}}(\mathbb{J}^{\mu})\tilde{G}_{f}&-\tilde{G}_{\mu}&G_{R}\\\
\tilde{A}_{f}&0&0\\\ 0&\tilde{A}_{\mu}&0\\\ 0&0&A_{R}\end{bmatrix},\
{G}_{u}\triangleq[\tilde{G}_{f}\ {0}\ 0],$ $\displaystyle G_{R}$
$\displaystyle\triangleq[0\ P^{\mu}],\ c_{R}\triangleq 0,\
A_{R}\triangleq[\tilde{A}_{f}\ 0],\ b_{R}\triangleq\tilde{b}_{f}.$ (40)

###### Proof.

Suppose $z\in\mathcal{CZ}_{f}\cap_{\mu}\mathcal{CZ}_{\mu}$. Then by definition
of the operator $\cap_{\mu}$ (cf. (14)), $z\in\mathcal{CZ}_{f}$ and
$\mu(z)\in\mathcal{CZ}_{\mu}$. Note that by Proposition 1 and the mean value
theorem,
$z\in\mathcal{CZ}_{f}\Rightarrow\mu(z)\in\mu(\mathcal{CZ}_{f})\subseteq\mu(x_{0})\oplus\mathbb{J}^{\mu}(\mathcal{CZ}_{f}\ominus
x_{0})=\mu(x_{0})\oplus(\textstyle{\mathrm{mid}}(\mathbb{J}^{\mu})+\mathbb{J}^{\mu}_{\Delta})(\mathcal{CZ}_{f}\ominus
x_{0})=$

$\displaystyle\mu(x_{0})-\textstyle{\mathrm{mid}}(\mathbb{J}^{\mu})\oplus\textstyle{\mathrm{mid}}(\mathbb{J}^{\mu})\mathcal{CZ}_{f}\oplus\mathbb{J}^{\mu}_{\Delta}(\mathcal{CZ}_{f}\ominus
x_{0}).$ (41)

On the other hand, by Proposition 2 :

$\displaystyle\mathbb{J}^{\mu}_{\Delta}(\mathcal{CZ}_{f}\ominus
x_{0})\subseteq\mathcal{CZ}_{R}\triangleq\\{G_{R},c_{R},A_{R},b_{R}\\}_{CZ},$
(42)

with $G_{R},c_{R},A_{R},b_{R}$ given in (38) and (40) (note that
$\textstyle{\mathrm{mid}}(\mathbb{J}^{\mu}_{\Delta})=0$ by its definition) and
where $\mathcal{CZ}_{R}$ has $n_{R}$ generators. Then, the facts that
$z\in\mathcal{CZ}_{f}\triangleq\\{\tilde{G}_{f}\beta+\tilde{c}_{f}|\tilde{A}_{f}\beta=\tilde{b}_{f},\beta\in\mathbb{B}^{n_{c}}_{\infty}\\}$,
$\mu(z)\in\mathcal{CZ}_{\mu}\triangleq\\{\tilde{G}_{\mu}\gamma+\tilde{c}_{\mu}|\tilde{A}_{\mu}\gamma=\tilde{b}_{\mu},\gamma\in\mathbb{B}^{n_{\tau}}_{\infty}\\}$,
(41) and (42) imply that
$z\in\\{\tilde{G}_{f}\beta+\tilde{c}_{f}|\tilde{c}_{\mu}+\tilde{G}_{\mu}\gamma=\mu(x_{0})+\textstyle{\mathrm{mid}}(\mathbb{J}^{\mu})(\tilde{c}_{f}-x_{0})+\textstyle{\mathrm{mid}}(\mathbb{J}^{\mu})\beta+C_{R}+G_{R}\xi_{R},\tilde{A}_{f}\beta=\tilde{b}_{f},\tilde{A}_{\mu}\gamma=\tilde{b}_{\mu},A_{R}\xi_{R}=b_{R},\beta\in\mathbb{B}^{n_{c}}_{\infty},\gamma\in\mathbb{B}^{n_{\tau}}_{\infty},\xi_{R}\in\mathbb{B}^{n_{R}}_{\infty}\\}$,
where the set on the right hand side is equivalent to the CZ on the right hand
side of (39). ∎

##  V Simulations

In this section we compare the performance of five approaches to guaranteed
state estimation: i) RRSR, i.e., the mean value extension-based propagation
introduced in [1] (recapped in Proposition 3) in addition to the update
approach in [1] for the case when the observation function is linear (e.g.,
Example I below) and its extension in Lemma 5 to nonlinear measurements (e.g.,
Example II below), ii) D-RRSR, i.e, a modification to RRSR where the bounds
for Jacobian matrices are computed using the reminder-form decomposition
functions (cf. Proposition 5), iii) D-ZB, i.e., decomposition-based
propagation and update with ZBs (cf. Lemmas 1 and 3), iv) D-CZ, i.e.,
decomposition-based propagation and update with CZs (cf. Lemmas 2 and 4) and
v) COMB, i.e., a combination of i)–v) via intersection.

###  V-A Example I

Consider the following discrete-time system [1, Section]

$\displaystyle\begin{array}[]{rll}x_{1,k}&=3x_{1,k-1}-\frac{x_{1,k-1}^{2}}{7}-\frac{4x_{1,k-1}x_{2,k-1}}{4+x_{1,k-1}}+w_{1,k-1},\\\
x_{2,k}&=-2x_{2,k-1}+\frac{3x_{1,k-1}x_{2,k-1}}{4+x_{1,k-1}}+w_{2,k-1},\\\
\begin{bmatrix}y_{1,k}\\\ y_{2,k}\end{bmatrix}&=\begin{bmatrix}1&0\\\
-1&1\end{bmatrix}\begin{bmatrix}x_{1,k}\\\
x_{2,k}\end{bmatrix}+\begin{bmatrix}v_{1,k}\\\
v_{2,k}\end{bmatrix},\end{array}$

with $\left\lVert w_{k}\right\rVert_{\infty}\leq 0.1$, $\left\lVert
v_{k}\right\rVert_{\infty}\leq 0.4$, and an initial zonotopic enclose for the
initial state: $\mathcal{X}_{0}=\\{\begin{bmatrix}0.1&0.2&-0.1\\\
0.1&0.1&0\end{bmatrix},\begin{bmatrix}0.5\\\ 0.5\end{bmatrix}\\}$.

Figure 1: Results from the first five time steps of set-valued state
estimation, using five different approaches, noticeable from the label on the
figure. Black dots are obtained from uniform sampling of $X_{0}$ propagated
through the vector field in Example I

As can be seen from Figure 1, D-ZB provides less conservative enclosures
compared to the other individual approaches, and further, the COMB approach
results in significant improvement, taking the advantage of intersection.
Moreover, a comparison between corresponding average times and the enclosure
set volumes to the five approaches shown in Table I. As it can be observed,
D-ZB gives the fastest responses, while combination of all, as expected, took
the longest, while RRSR and D-RRSR took approximately the same time on
average. In terms of volume, D-ZB and D-RRSR generate the least conservative
enclosures compared to the other individual approaches, while a further
improvement is obtained using the the intersection of all the individual
approaches, i.e., COMB.

TABLE I: Average total times (second) and average total volumes ($10^{-4}$) at each time step of the estimators is calculated. Each average is taken over $50$ separate simulations. Methods: | $k=0$ | $k=1$ | $k=2$ | $k=3$ | $k=4$
---|---|---|---|---|---
RRSR | Time: | $0.087$ | $0.250$ | $0.193$ | $0.196$ | $0.204$
Vol.: | $0.5196$ | $2.3522$ | $3.6224$ | $3.0243$ | $1.8968$
D-RRSR | Time: | $0.022$ | $0.225$ | $0.181$ | $0.198$ | $0.201$
Vol.: | $0.5196$ | $2.1062$ | $3.2979$ | $1.3811$ | $0.6320$
D-ZB | Time: | $0.192$ | $0.095$ | $0.091$ | $0.091$ | $0.123$
Vol.: | $0.5196$ | $0.7974$ | $0.9918$ | $0.8316$ | $0.6170$
D-CZ | Time: | $0.065$ | $2.825$ | $2.920$ | $2.118$ | $3.318$
Vol.: | $0.5196$ | $1.8857$ | $2.1534$ | $1.7924$ | $1.3764$
COMB | Time: | $0.063$ | $6.193$ | $6.882$ | $6.278$ | $6.951$
Vol.: | $0.5196$ | $1.4226$ | $1.8399$ | $1.0038$ | $0.6387$

###  V-B Example II (The Unicycle System)

Now consider the following discretized unicycle-like mobile robot system [29]
in the form of (12):

$\displaystyle\begin{array}[]{rlll}s_{x,k+1}&=s_{x,k}+T_{0}\phi_{w}\cos(\theta_{k})+w_{1,k},\\\
s_{y,k+1}&=s_{y,k}+T_{0}\phi_{w}\sin(\theta_{k})+w_{2,k},\\\
\theta_{k+1}&=\theta_{k}+T_{0}\phi_{\theta}+w_{3,k},\\\ y_{k}&=[d_{1,k}\
\phi_{1,k}\ d_{2,k}\ \phi_{2,k}]^{\top}+v_{k},\end{array}$ (47)

where $x_{k}\triangleq[s_{x,k}\ s_{y,k}\ \theta_{k}]^{\top}$, $w_{k}=[w_{x,k}\
w_{y,k}\
w_{\theta,k}]^{\top},\phi_{\omega,k}=0.3,\phi_{\theta,k}=0.15,w_{x,k}=0.2(0.5\rho_{x_{1,k}}-0.3),w_{y,k}=0.2(0.3\rho_{x_{2,k}}-0.2)$
and $w_{\theta,k}=0.2(0.6\rho_{x_{3,k}}-0.4)$, with $\rho_{x_{l,k}}\in[0,1]$
$(l=1,2,3)$ and initial state $x_{0}=[0.1\ 0.2\ 1]^{\top}$. Moreover, $\forall
i\in\\{1,2\\}$,
$d_{i,k}=\sqrt{(s_{x_{i}}-s_{x,k})^{2}+(s_{y_{i}}-s_{y,k})^{2}}$ and
$\phi_{i,k}=\theta_{k}-\arctan(\frac{s_{y_{i}}-s_{y,k}}{s_{x_{i}}-s_{x,k}})$,
with $s_{x_{i}},s_{y_{i}}$ being two known values. Furthermore,
$v_{1,k}=0.02\rho_{{y_{1}},k}-0.01$, $v_{2,k}=0.03\rho_{{y_{2}},k}-0.01$,
$v_{3,k}=0.03\rho_{{y_{3}},k}-0.02$, $v_{4,k}=0.05\rho_{{y_{4}},k}-0.03$ and
$\rho_{{y_{k}},k}\in[0,1]$ $(k=1,2,3,4)$. Applying all the methods, one can
observe from Figure 2 that the resultant set estimates are very comparable for
all the different five approaches. In terms of computation time, Table II
shows that D-CZ takes minimum computation time followed by RRSR, D-RRSR, COMB
and D-ZB. In terms of set volumes, the COMB approach takes minimum volume
followed by D-ZB, D-CZ, RRSR and D-RRSR. Note that the computation time for
D-ZB’s is exceptionally large, presumably because the conversion of a polytope
to a zonotope bundle in CORA usually results in a higher number of zonotopes
than the needed minimal number of zonotopes in the zonotope bundle. The
reduction of this number of zonotopes in the bundle could be an interesting
topic to explore in the future, which could significantly decrease the
computation time of our D-ZB approach.

Figure 2: Results from the first five time steps of set-valued state estimation, using five different approaches, noticeable from the label on the figure. Black dots are obtained from uniform sampling of $X_{0}$ propagated via (47) TABLE II: Average total times (second) and average total volumes ($10^{-4}$) at each time step of the estimators is calculated. Each average is taken over $20$ separate simulations. Methods: | $k=0$ | $k=1$ | $k=2$ | $k=3$ | $k=4$
---|---|---|---|---|---
RRSR | Time: | $0.772$ | $4.256$ | $4.188$ | $2.995$ | $3.675$
Vol.: | $1.7309$ | $1.0293$ | $5.528$ | $1.377$ | $1.413$
D-RRSR | Time: | $1.669$ | $42.90$ | $45.57$ | $28.64$ | $50.53$
Vol.: | $1.279$ | $9.717$ | $5.654$ | $1.978$ | $1.888$
D-ZB | Time: | $1.397$ | $34.20$ | $163.08$ | $147.75$ | $131.75$
Vol.: | $0.042$ | $0.030$ | $0.013$ | $0.043$ | $0.042$
D-CZ | Time: | $0.602$ | $2.182$ | $2.016$ | $2.228$ | $2.591$
Vol.: | $0.073$ | $0.072$ | $0.030$ | $1.261$ | $0.091$
COMB | Time: | $0.236$ | $34.90$ | $65.50$ | $62.37$ | $57.73$
Vol.: | $0.041$ | $0.028$ | $0.012$ | $0.041$ | $0.040$

##  VI Conclusion

New set-membership methods were presented in this paper for state estimation
in bounded-error discrete-time nonlinear systems, subject to nonlinear
observations/constraints. By transforming ZB/CZ uncertainty sets from the
state space to the space of ZB/CZ’s generators, our recently developed tight
remainder-form mixed-monotone decomposition functions were applied to compute
enclosures that were guaranteed to enclose the set of the state trajectories
of the system. Further, remainder-form decomposition functions were leveraged
to bound the nonlinear observation function to derive the updated set, i.e.,
to return enclosures to intersection of the propagated set and the set of
states that are consistent with the measurements. Finally, the mean value
extension-based approach in [1] was also generalized to compute the updated
set for nonlinear observations.

## References

  * [1] B.S. Rego, G.V. Raffo, J.K. Scott, and D.M. Raimondo.  Guaranteed methods based on constrained zonotopes for set-valued state estimation of nonlinear discrete-time systems.  Automatica, 111:108614, 2020.
  * [2] C. Combastel, Q. Zhang, and A. Lalami.  Fault diagnosis based on the enclosure of parameters estimated with an adaptive observer.  IFAC Proceedings Volumes, 41(2):7314–7319, 2008.
  * [3] L. Jaulin.  A nonlinear set membership approach for the localization and map building of underwater robots.  IEEE Transactions on Robotics, 25(1):88–98, 2009.
  * [4] M.A. Dahleh and J.B. Pearson.  $\ell_{1}$-optimal feedback controllers for MIMO discrete-time systems.  IEEE Transactions on Automatic Control, 32(4):314–322, 1987.
  * [5] M. Kieffer and E. Walter.  Guaranteed nonlinear state estimator for cooperative systems.  Numerical algorithms, 37(1-4):187–198, 2004.
  * [6] L. Chisci, G.A., and G. Zappa.  Recursive state bounding by parallelotopes.  Automatica, 32(7):1049–1055, 1996.
  * [7] V.T.H. Le, C. Stoica, T. Alamo, E.F. Camacho, and D. Dumur.  Zonotopic guaranteed state estimation for uncertain systems.  Automatica, 49(11):3418–3424, 2013.
  * [8] A. Girard and Le G.C.  Efficient reachability analysis for linear systems using support functions.  IFAC Proceedings Volumes, 41(2):8966–8971, 2008.
  * [9] J.S. Shamma and K. Tu.  Set-valued observers and optimal disturbance rejection.  IEEE Trans. on Automatic Control, 44(2):253–264, 1999.
  * [10] A. Vicino and G. Zappa.  Sequential approximation of feasible parameter sets for identification with set membership uncertainty.  IEEE Transactions on Automatic Control, 41(6):774–785, 1996.
  * [11] M. Khajenejad and S.Z. Yong.  Simultaneous input and state set-valued $\mathcal{{H}}_{\infty}$-observers for linear parameter-varying systems.  In American Control Conference (ACC), pages 4521–4526. IEEE, 2019\.
  * [12] B.T. Polyak, S.A. Nazin, Cé. Durieu, and E. Walter.  Ellipsoidal parameter or state estimation under model uncertainty.  Automatica, 40(7):1171–1179, 2004.
  * [13] M. Khajenejad and S.Z. Yong.  Simultaneous mode, input and state set-valued observers with applications to resilient estimation against sparse attacks.  In Conference on Decision and Control (CDC), 2019.
  * [14] G. Zheng, D. Efimov, and W. Perruquetti.  Design of interval observer for a class of uncertain unobservable nonlinear systems.  Automatica, 63:167–174, 2016.
  * [15] M. Khajenejad and S.Z. Yong.  Simultaneous input and state interval observers for nonlinear systems with full-rank direct feedthrough.  In 2020 59th IEEE Conference on Decision and Control (CDC), pages 5443–5448. IEEE, 2020.
  * [16] Y. Wang, D.M. Bevly, and R. Rajamani.  Interval observer design for LPV systems with parametric uncertainty.  Automatica, 60:79–85, 2015.
  * [17] M. Khajenejad and S.Z. Yong.  Simultaneous input and state interval observers for nonlinear systems with rank-deficient direct feedthrough.  In European Control Conference, 2021, accepted.
  * [18] C. Combastel.  Merging kalman filtering and zonotopic state bounding for robust fault detection under noisy environment.  IFAC-PapersOnLine, 48(21):289–295, 2015.
  * [19] J.K. Scott, D.M. Raimondo, G.R. Marseglia, and R.D. Braatz.  Constrained zonotopes: A new tool for set-based estimation and fault detection.  Automatica, 69:126–136, 2016.
  * [20] M. Althoff and B.H Krogh.  Zonotope bundles for the efficient computation of reachable sets.  In 2011 50th IEEE conference on decision and control and European control conference, pages 6814–6821. IEEE, 2011.
  * [21] R.E. Moore, R.B. Kearfott, and M.J. Cloud.  Introduction to interval analysis.  SIAM, 2009.
  * [22] L. Jaulin.  Inner and outer set-membership state estimation.  Reliable Computing, 22:47–55, 2016.
  * [23] C. Combastel.  A state bounding observer for uncertain non-linear continuous-time systems based on zonotopes.  In Proceedings of the 44th IEEE Conference on Decision and Control, pages 7228–7234. IEEE, 2005.
  * [24] T. Alamo, J.M. Bravo, and E.F. Camacho.  Guaranteed state estimation by zonotopes.  Automatica, 41(6):1035–1043, 2005.
  * [25] T. Alamo, J.M. Bravo, M.J. Redondo, and E.F. Camacho.  A set-membership state estimation algorithm based on DC programming.  Automatica, 44(1):216–224, 2008.
  * [26] M. Khajenejad and S.Z. Yong.  Tight remainder-form decomposition functions with applications to constrained reachability and interval observer design.  IEEE Transactions on Automatic Control, submitted, 2021, https://arxiv.org/pdf/2103.08638.pdf.
  * [27] M. Althoff.  https://tumcps.github.io/cora/data/cora2020manual.pdf.
  * [28] M. James.  The generalised inverse.  The Mathematical Gazette, 62(420):109–114, 1978.
  * [29] B. Chen and G. Hu.  Nonlinear state estimation under bounded noises.  Automatica, 98:159–168, 2018.