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 the 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.
This paper proposes a tractable family of remainder-form mixed-monotone decomposition functions that are useful for over-approximating the image set of nonlinear mappings in reachability and estimation problems. In particular, our approach applies to
a new class of nonsmooth nonlinear systems that we call either-sided locally Lipschitz (ELLC) systems, which we show to be a superset of locally Lipschitz continuous systems, thus expanding the set of systems that are formally known to be mixed-monotone. In addition, we derive lower and upper bounds for the over-approximation error and show that the lower bound is achievable with our proposed approach. Moreover, we develop a set inversion algorithm that along with the proposed decomposition functions, can be used for constrained reachability analysis and interval observer design for continuous and discrete-time systems with bounded noise.
In this paper, we study the problem of designing a simultaneous mode, input, and state set-valued observer for a class of hidden mode switched nonlinear systems with bounded-norm noise and unknown input signals, where the hidden mode and unknown inpu
ts can represent fault or attack models and exogenous fault/disturbance or adversarial signals, respectively. The proposed multiple-model design has three constituents: (i) a bank of mode-matched set-valued observers, (ii) a mode observer, and (iii) a global fusion observer. The mode-matched observers recursively find the sets of compatible states and unknown inputs conditioned on the mode being the true mode, while the mode observer eliminates incompatible modes by leveraging a residual-based criterion. Then, the global fusion observer outputs the estimated sets of states and unknown inputs by taking the union of the mode-matched set-valued estimates over all compatible modes. Moreover, sufficient conditions to guarantee the elimination of all false modes (i.e., mode-detectability) are provided and the effectiveness of our approach is demonstrated and compared with existing approaches using an illustrative example.
We address the problem of designing simultaneous input and state interval observers for Lipschitz continuous nonlinear systems with rank-deficient feedthrough, unknown inputs and bounded noise signals. Benefiting from the existence of nonlinear decom
position functions and affine abstractions, our proposed observer recursively computes the maximal and minimal elements of the estimate intervals that are proven to contain the true states and unknown inputs. Moreover, we provide necessary and sufficient conditions for the existence and sufficient conditions for the stability (i.e., uniform boundedness of the sequence of estimate interval widths) of the designed observer, and show that the input interval estimates are tight, given the state intervals and decomposition functions.
This paper introduces control barrier functions for discrete-time systems, which can be shown to be necessary and sufficient for controlled invariance of a given set. Moreover, we propose nonlinear discrete-time control barrier functions for partiall
y control affine systems that lead to controlled invariance conditions that are affine in the control input, leading to a tractable formulation that enables us to handle the safety optimal control problem for a broader range of applications with more complicated safety conditions than existing approaches. In addition, we develop mixed-integer formulations for basic and secondary Boolean compositions of multiple control barrier functions and further provide mixed-integer constraints for piecewise control barrier functions. Finally, we apply these discrete-time control barrier function tools to automotive safety problems of lane keeping and obstacle avoidance, which are shown to be effective in simulation.
In this paper, we propose an incremental abstraction method for dynamically over-approximating nonlinear systems in a bounded domain by solving a sequence of linear programs, resulting in a sequence of affine upper and lower hyperplanes with expandin
g operating regions. Although the affine abstraction problem can be solved offline using a single linear program, existing approaches suffer from a computation space complexity that grows exponentially with the state dimension. Hence, the motivation for incremental abstraction is to reduce the space complexity for high-dimensional systems, but at the cost of yielding potentially worse abstractions/overapproximations. Specifically, we start with an operating region that is a subregion of the state space and compute two affine hyperplanes that bracket the nonlinear function locally. Then, by incrementally expanding the operating region, we dynamically update the two affine hyperplanes such that we eventually yield hyperplanes that are guaranteed to over-approximate the nonlinear system over the entire domain. Finally, the effectiveness of the proposed approach is demonstrated using numerical examples of high-dimensional nonlinear systems.
We study the problem of designing interval-valued observers that simultaneously estimate the system state and learn an unknown dynamic model for partially unknown nonlinear systems with dynamic unknown inputs and bounded noise signals. Leveraging aff
ine abstraction methods and the existence of nonlinear decomposition functions, as well as applying our previously developed data-driven function over-approximation/abstraction approach to over-estimate the unknown dynamic model, our proposed observer recursively computes the maximal and minimal elements of the estimate intervals that are proven to contain the true augmented states. Then, using observed output/measurement signals, the observer iteratively shrinks the intervals by eliminating estimates that are not compatible with the measurements. Finally, given new interval estimates, the observer updates the over-approximation of the unknown model dynamics. Moreover, we provide sufficient conditions for uniform boundedness of the sequence of estimate interval widths, i.e., stability of the designed observer, in the form of tractable (mixed-)integer programs with finitely countable feasible sets.
In this paper, we consider the data-driven model invalidation problem for Lipschitz continuous systems, where instead of given mathematical models, only prior noisy sampled data of the systems are available. We show that this data-driven model invali
dation problem can be solved using a tractable feasibility check. Our proposed approach consists of two main components: (i) a data-driven abstraction part that uses the noisy sampled data to over-approximate the unknown Lipschitz continuous dynamics with upper and lower functions, and (ii) an optimization-based model invalidation component that determines the incompatibility of the data-driven abstraction with a newly observed length-T output trajectory. Finally, we discuss several methods to reduce the computational complexity of the algorithm and demonstrate their effectiveness with a simulation example of swarm intent identification.
A simultaneous input and state interval observer is presented for Lipschitz continuous nonlinear systems with unknown inputs and bounded noise signals for the case when the direct feedthrough matrix has full column rank. The observer leverages the ex
istence of bounding decomposition functions for mixed monotone mappings to recursively compute the maximal and minimal elements of the estimate intervals that are compatible with output/measurement signals, and are proven to contain the true state and unknown input. Furthermore, we derive a Lipschitz-like property for decomposition functions, which provides several sufficient conditions for stability of the designed observer and boundedness of the sequence of estimate interval widths. Finally, the effectiveness of our approach is demonstrated using an illustrative example.
In this paper, we propose fixed-order set-valued (in the form of l2-norm hyperballs) observers for some classes of nonlinear bounded-error dynamical systems with unknown input signals that simultaneously find bounded hyperballs of states and unknown
inputs that include the true states and inputs. Necessary and sufficient conditions in the form of Linear Matrix Inequalities (LMIs) for the stability (in the sense of quadratic stability) of the proposed observers are derived for ($mathcal{M},gamma$)- Quadratically Constrained (($mathcal{M},gamma$)-QC) systems, which includes several classes of nonlinear systems: (I) Lipschitz continuous, (II) ($mathcal{A},gamma$)-QC* and (III) Linear Parameter-Varying (LPV) systems. This new quadratic constraint property is at least as general as the incremental quadratic constraint property for nonlinear systems and is proven in the paper to embody a broad range of nonlinearities. In addition, we design the optimal $mathcal{H}_{infty}$ observer among those that satisfy the quadratic stability conditions and show that the design results in Uniformly Bounded-Input Bounded-State (UBIBS) estimate radii/error dynamics and uniformly bounded sequences of the estimate radii. Furthermore, we provide closed-form upper bound sequences for the estimate radii and sufficient condition for their convergence to steady state. Finally, the effectiveness of the proposed set-valued observers is demonstrated through illustrative examples, where we compare the performance of our observers with some existing observers.
