Forward Inner approximated Reachability of Non linear Continuous Systems 1 10

Access throughyour institution

Journal of the Franklin Institute

Abstract

In this paper, a method to under-approximate finite-time reachable sets and tubes for a class of continuous-time linear uncertain systems is proposed. The class under consideration is the linear time-varying (LTV) class with time-varying integrable system matrices and uncertain initial and input values belonging to known convex compact sets. The proposed method depends upon the iterative use of constant-input reachable sets, which results in convergent under-approximations in the sense of the Hausdorff distance. As a consequence of the convergence, it is shown that interior points of reachable sets are attainable using piecewise constant inputs. The computational complexity of a zonotopic implementation of the proposed method is discussed and comparisons with existing under-approximation methods are established. Finally, the proposed approach is illustrated through two numerical examples.

Introduction

In recent years, the field of reachability analysis has received intensive research attention due to its significant role in formal verification and control synthesis [1], [2]. This resulted in a literature rich in various methods that approximate reachable sets and tubes for various classes of systems [3]. In the context of reachability analysis, approximation techniques can be classified into over-approximation approaches that envelope reachable sets and tubes (see, e.g., [1], [4], [5], [6]) and under-approximation approaches that inner-bound reachable sets and tubes (see, e.g., [7], [8], [9], [10]). Like over-approximation methods, under-approximation approaches have significant roles in synthesis and verification applications. For example, in the context of control synthesis, it is often preferred, when the input set is associated with control constraints, to under-approximate reachable sets to obtain the set of states that are guaranteed to be attainable [11]. Moreover, in the context of formal verification, under-approximations of 'backward' reachable sets, starting from unsafe sets, are usually computed to find the set of initial states with reachable sets that violate safety specifications [7], [10]. In comparison to over-approximation methods, under-approximation approaches are relatively underdeveloped due to the scarcity of mathematical tools that enable constructing useful inner-approximations of reachable sets and tubes. The goal of this paper is to develop an under-approximation method for a class of linear uncertain systems.

Up to the knowledge of the author, there have been very few works on under-approximation methods for linear systems with the first works dating back to the seventies, where tools from optimal control have been utilized to obtain tight polytopic under-approximations of reachable sets [12]. The polytopic approach relies on obtaining boundary points, associated with specified direction vectors, of reachable sets by feeding optimal control signals into the linear system and then computing the convex hull of the obtained boundary points. Similar optimal control tools, with time-varying direction vectors, have been utilized in [9] to obtain polytopic under-approximations. Convergence of the polytopic approach is attained by computing an increasing number of boundary points until the whole reachable set boundary is obtained. Besides the polytopic approach, an ellipsoidal method has been proposed in [8], which relies on solving initial value problems, derived from optimal control principles similar to those presented in [9], to obtain ellipsoidal subsets that touch reachable sets at some boundary points. Accuracy of the ellipsoidal method is increased by evaluating an increasing number of ellipsoids and then taking their union. Along with the mentioned techniques, approaches designed for general nonlinear systems can be used for linear systems, where interval arithmetic [7], [13], solutions to Hamilton–Jacobi partial differential equations [14], or coverings of boundaries of reachable sets [10] are utilized.

A very simple yet effective approach in reachability analysis is the use of set-based recursions, where constant-input reachable sets are used iteratively, resulting in reachable sets under piecewise constant inputs. This approach has been adopted, e.g., in [15], where second-order approximations of reachable sets for linear systems have been proposed. Moreover, the mentioned approach has been implemented in [1], [16], resulting in accurate over-approximations of reachable sets and tubes. Furthermore, approximations of trajectories of LTV systems, under relatively weak assumptions on the time-varying system matrices, using piecewise constant control signals have been investigated in [17]. Constant-input reachable sets are subsets of the actual reachable sets, which, besides their promising results in reachability analysis, inspires their use in this work as under-approximations for linear uncertain systems. The contribution of the current work over the works in [1], [15], [16], [17] is as follows: the proposed method in the current work is used to under-approximate both reachable sets and tubes, whereas, in the previous works, piecewise constant reachable sets are used to obtain over-approximations or mere approximations and. hence. the scope of the current study is different from the scope of the mentioned works. Moreover, the assumptions imposed on the linear systems under consideration in this work are significantly weaker than the ones in [1], [15], [16], [17]. The weakened assumptions are inspired by the promising convergence results of piecewise constant reachable sets and the eagerness to extend these results to more general classes of linear systems. Besides that, the proposed work is motivated by the need of convergent under-approximation methods that are applicable to a wide variety of linear systems. As will be discussed in this work, the applicability of existing under-approximation approaches to a wide variety of linear systems is restricted due to either theoretical or computational limitations.

The organization of this work is as follows: after the introduction, the necessary mathematical preliminaries are presented. Then, the LTV system under consideration, the associated assumptions, and the under-approximation problem statement are introduced. After that, the proposed method and its convergence and implementation are discussed thoroughly. An interesting consequent result related to the attainability of interior points of reachable sets using piecewise constant inputs is also deduced. Furthermore, comparisons between the proposed method and the existing under-approximation approaches are established. Finally, the proposed method is demonstrated through two numerical examples.

Section snippets

Preliminaries

$R,$ $Z,$ and $N$ denote the sets of real numbers, integers, and positive integers, respectively. Given $a, b \in R,$ with $a \leq b,$ $[a; b]$ denotes the discrete interval $[a, b] \cap Z$ . The set of interior points of a subset $X \subseteq R^{n}$ is denoted by $int (X)$ . Given $S \subseteq R,$ $m (S)$ denotes the Lebesgue measure of $S$ and $X_{S} : R \to {0, 1}$ denotes the characteristic function of $S$ , which is defined as $X_{S} (x) : = {\begin{matrix} 1, & x \in S, \\ 0, & elsewhere, \end{matrix}$ see, e.g., [18]. Arithmetic operations involving subsets of a linear space $X$ are defined point-wise, e.g., $α M : = {α y | y \in M}$

Problem formulation

In this section, we formulate and state the problem under consideration in this paper.

Under-approximations

In this section, we address the problem stated in the previous section by proposing a convergent under-approximation method.

Piecewise constant control

The under-approximation method proposed in this work depends upon the use of piecewise constant input signals, which are practical in control design (see, e.g., [27]) as control signals in real life applications are digital. The following result, which is based on Theorem 1, exhibits the ability to reach interior points of reachable sets by means of piecewise constant input signals. A similar result was introduced in [28] for smooth nonlinear time-invariant systems. The readers are referred to,

Comparison with existing approaches

The proposed under-approximation method in this paper is applicable to LTV uncertain systems with convex and compact initial and input sets and integrable time-varying system matrices. The proposed method is also convergent in the sense of the Hausdorff distance. The convergence rates of the proposed method are dependent on the regularity of the time-varying system matrices $A$ and $B$ as illustrated in Subsection 4.3.

When compared with the polytopic approach [9], [12], the proposed method is

Numerical examples

In this section, the proposed method is demonstrated via two numerical examples. For both examples, the closed-form formulas of the transition matrices are known exactly. The proposed method is implemented using zonotopes with the help of CORA software [32].

Conclusion

In this work, a method to under-approximate finite-time reachable sets and tubes for a class of LTV systems has been proposed. The assumptions on the LTV class are quite weak requiring only the convexity and compactness of the initial and input sets and the integrability of the time-varying system matrices. The proposed method utilizes piecewise constant reachable sets, which converge to the actual reachable sets in the sense of the Hausdorff distance. A drawback of the proposed method, which

Declaration of Competing Interest

No competing interests.

Acknowledgement

The author of this work sincerely thanks Dr. Jun Liu, from the Applied Mathematics Department at the University of Waterloo, for his valuable comments and discussions that contributed to improving the results of this work.

References (36)

Approximation of the attainable sets of the nonlinear control systems with integral constraint on controls

Nonlinear Anal.: Theory Methods Appl

(2009)
J.K. Scott et al.
Constrained zonotopes: a new tool for set-based estimation and fault detection

Automatica

(2016)
G.A. Anastassiou
Ostrowski and landau inequalities for Banach space valued functions

Math. Comput. Model.

(2012)
T. Pecsvaradi et al.
Reachable sets for linear dynamical systems

Inform. Control

(1971)
A.B. Kurzhanski et al.
Ellipsoidal techniques for reachability analysis: internal approximation

Syst. Control Lett.

(2000)
J.K. Scott et al.
Bounds on the reachable sets of nonlinear control systems

Automatica J. IFAC

(2013)
C. Le Guernic et al.
Reachability analysis of linear systems using support functions

Nonlinear Anal. Hybrid Syst.

(2010)
M. Althoff
Reachability analysis and its application to the safety assessment of autonomous cars

(2010)
G. Reissig et al.
Feedback refinement relations for the synthesis of symbolic controllers

IEEE Trans. Autom. Control

(2017)
E. Asarin et al.
Recent progress in continuous and hybrid reachability analysis

Proceedings of the IEEE Conference Computer Aided Control Systems Design (CACSD), Munich, Germany

(2006)

M. Serry et al.

Hyper-rectangular over-approximations of reachable sets for linear uncertain systems

Proceedings of the 57th IEEE Conference Decision and Control (CDC), Miami, FL, USA

(2018)

E. Goubault et al.