Comparative analysis of the asymptotic dynamics of reachable sets to linear systems

Explicit asymptotic formulas for reachable sets of linear dynamic systems with two types of control bounds, geometric constraints and constraints on the total impulse of the control action, are compared. A detailed proof of asymptotic formulas for the case of geometric constraints was first given. It was shown that, despite the similarity of the problem statement and methods to study the asymptotics of reachable sets for the considered types of constraints, the results obtained are essentially different. For example, for the impulsive case in the space of shapes of reachable sets, a multidimensional attractor may arise, while, in the case of geometric constraints, the corresponding attractor is reduced to a single point.     

Control Time in Systems of Chaotic Behavior. II. Its Estimation

The control time of dynamic systems is estimated by a method based on the properties of a sequence of reachable sets. It is shown to depend on the rate of growth of the volume of reachable sets. The method for studying controllability is applicable to systems with chaotic behavior of trajectories. For control systems generated by neutral mappings, an asymptotic estimate for the control time is found under arbitrarily small controls.     

具有自适应噪声边界的Tube可达集鲁棒预测控制

针对过程噪声设定边界与真实噪声边界失配的有界干扰离散线性不确定系统,提出一种具有自适应噪声边界的Tube可达集鲁棒模型预测控制方法.首先,该算法引入基于MIT规则的自适应集员滤波在线估计系统状态和噪声边界.其次,基于估计值,通过迭代自适应集员滤波的时间更新部分计算出预测时域内闭环不确定系统状态的可达集.最后,用可达集代替不变集并根据Tube鲁棒模型预测控制策略,给出了实际不确定系统的控制律,确保系统状态鲁棒渐近稳定,并收敛于终端干扰不变集.仿真结果验证了该控制方法的有效性.     

Controllability and observability of Boolean control networks

The controllability and observability of Boolean control networks are investigated. After a brief review on converting a logic dynamics to a discrete-time linear dynamics with a transition matrix, some formulas are obtained for retrieving network and its logical dynamic equations from this network transition matrix. Based on the discrete-time dynamics, the controllability via two kinds of inputs is revealed by providing the corresponding reachable sets precisely. Then the problem of observability is also solved by giving necessary and sufficient conditions.     

Zonotopic reachable set estimation for linear discrete‐time systems with time delay

This article studies reachable set estimation for linear discrete‐time systems with time delay, which are influenced by unknown but bounded disturbances. We propose a novel reachable set estimation method based on zonotopes for the considered systems. The proposed method can estimate real‐time reachable set under nonzero initial conditions. In order to increase estimation accuracy, we propose an iterative method to reduce the conservatism caused by the couplings between reachable sets at different instants. The effectiveness of the proposed method is illustrated by three numerical simulations.     

不确定线性系统的可达集估计

本文针对线性不确定系统,研究了系统状态可达集估计问题.在已知参考输入,未知扰动有界的条件下,提出了一种新的可达集估计方法,并把所提方法推广到系统不稳定的情况,分别估计出不稳定系统的闭环可达集和开环可达集.通过分析动态系统的李雅普诺夫函数,将求取系统可达集的问题转化为线性矩阵不等式优化问题,并将可达集范围用椭球集形式表述.最后分别通过数值仿真分析,验证了所提出方法对线性系统可达集估计的有效性.     

带有运行成本函数的Hamilton-Jacobi可达性分析

水平集方法将可达集表示为Hamilton-Jacobi方程解的零水平集,保存多个不同时间范围的可达集则需要保存Hamilton-Jacobi方程在多个时刻的解,这不仅需要消耗大量的存储空间还为控制律的设计造成了困难.针对这些局限性,提出了一种改进的基于Hamilton-Jacobi方程的可达集表示方法.该方法在Hamilton-Jacobi方程中加入了一项运行成本函数,可以用同一个时刻的解的多个非零水平集表示多个不同时间范围的可达集,极大地节省了存储空间并为控制律的设计提供了便利.为了求解所构造的带有运行成本函数的Hamilton-Jacobi方程,采用了一种基于递归和插值的方法.最后,通过一些数值算例验证了所提出的方法的精确性、在存储空间方面的优越性以及设计的控制律的有效性.     

Counting the solutions of Presburger equations without enumerating them

The number decision diagram (NDD) has recently been introduced as a powerful representation system for sets of integer vectors. NDDs can notably be used for handling sets defined by arbitrary Presburger formulas, which makes them well suited for representing the set of reachable states of finite-state systems extended with unbounded integer variables. In this paper, we address the problem of counting the number of distinct elements in a set of numbers or, more generally, of vectors, represented by an NDD. We give an algorithm that is able to produce an exact count without enumerating explicitly the vectors, which makes it capable of handling very large sets. As an auxiliary result, we also develop an efficient projection method that allows to construct efficiently NDDs from quantified formulas, and thus makes it possible to apply our counting technique to sets specified by formulas. Our algorithms have been implemented in the verification tool LASH, and applied successfully to various counting problems.     

Convexity of reachable sets of nonlinear ordinary differential equations

A necessary and sufficient condition for the reachable set, i.e., the set of states reachable from a ball of initial states at some time, of an ordinary differential equation to be convex is presented. In particular, convexity is guaranteed if the ball of initial states is sufficiently small, an upper bound on the radius of that ball being obtained directly from the right hand side of the differential equation. In finite dimensions, the results cover the case of ellipsoids of initial states. A potential application of the results is inner and outer polyhedral approximation of reachable sets, which becomes extremely simple and almost universally applicable if these sets are known to be convex. An example demonstrates that the balls of initial states for which the latter property follows from the results are large enough to be used in actual computations.     

Overapproximating Reachable Sets by Hamilton-Jacobi Projections

In earlier work, we showed that the set of states which can reach a target set of a continuous dynamic game is the zero sublevel set of the viscosity solution of a time dependent Hamilton-Jacobi-Isaacs (HJI) partial differential equation (PDE). We have developed a numerical tool—based on the level set methods of Osher and Sethian—for computing these sets, and we can accurately calculate them for a range of continuous and hybrid systems in which control inputs are pitted against disturbance inputs. The cost of our algorithm, like that of all convergent numerical schemes, increases exponentially with the dimension of the state space. In this paper, we devise and implement a method that projects the true reachable set of a high dimensional system into a collection of lower dimensional subspaces where computation is less expensive. We formulate a method to evolve the lower dimensional reachable sets such that they are each an overapproximation of the full reachable set, and thus their intersection will also be an overapproximation of the reachable set. The method uses a lower dimensional HJI PDE for each projection with a set of disturbance inputs augmented with the unmodeled dimensions of that projection's subspace. We illustrate our method on two examples in three dimensions using two dimensional projections, and we discuss issues related to the selection of appropriate projection subspaces.     

Information-Theoretic Distance Measures for Clustering Validation: Generalization and Normalization

This paper studies the generalization and normalization issues of information-theoretic distance measures for clustering validation. Along this line, we first introduce a uniform representation of distance measures, defined as quasi-distance, which is induced based on a general form of conditional entropy. The quasi-distance possesses three properties: symmetry, the triangle law, and the minimum reachable. These properties ensure that the quasi-distance naturally lends itself as the external measure for clustering validation. In addition, we observe that the ranges of the distance measures are different when they apply for clustering validation on different data sets. Therefore, when comparing the performances of clustering algorithms on different data sets, distance normalization is required to equalize ranges of the distance measures. A critical challenge for distance normalization is to obtain the ranges of a distance measure when a data set is provided. To that end, we theoretically analyze the computation of the maximum value of a distance measure for a data set. Finally, we compare the performances of the partition clustering algorithm K-means on various real-world data sets. The experiments show that the normalized distance measures have better performance than the original distance measures when comparing clusterings of different data sets. Also, the normalized Shannon distance has the best performance among four distance measures under study.     

Reachable Set Estimation for Discrete‐Time Singular Systems

This paper is concerned with the problem of reachable set estimation for discrete‐time singular systems with bounded input disturbances. Based on the Lyapunov method, a new sufficient condition is established in terms of linear matrix inequality (LMI) to guarantee that the reachable set of discrete‐time singular system is bounded by the intersection of ellipsoids. Then the result is extended to the problem for discrete‐time singular systems with time‐varying delay by utilizing the delay‐dependent approach and free weighting matrices. Two numerical examples are provided to demonstrate the effectiveness of the obtained results proposed in this paper.     

基于可达集的鲁棒模型预测控制

设计了一种基于可达集的鲁棒模型预测控制算法.首先确定了一个鲁棒不变集,并将此不变集用作模型预测控制的终端约束集;接着采用终端约束集对可达集的包含度作为优化指标;最后,采用预测时域逐渐减小的控制策略以保证在线优化存在可行解.从理论上证明了吸引域内的任意点在有限时域内都会被引导至终端约束集并始终停留在此集之内,并由仿真算例验证了本文所设计鲁棒模型预测控制算法的可行性.     

Reachable set estimation for discrete‐time switched system with application to time‐delay system

This paper addresses the problem of reachable set estimation and synthesis for a class of discrete‐time switched linear systems with time delay and bounded peak disturbance. Combined with the feature of mode‐dependent average dwell time switching, a new algorithm is developed to estimate the reachable set of switched system, which is both quasi‐time‐dependent and mode‐dependent. Then, the proposed method is applied to time‐delay system and a sufficient condition is presented to guarantee the asymptotic stability and estimate the bounding ellipsoid. Furthermore, the quasi‐time‐dependent controller is designed to stabilize the system and restrict the closed‐loop system states to an ellipsoidal bound. Examples are presented to illustrate the effectiveness and advantages of the obtained theorems.     

Determination of reachable set for a linear discrete system

An easily implemented method for obtaining the reachable setR_{N}, N > n, of annth-order discrete system with constraints on the input is described. This method uses elementary matrix calculations at each step to construct the boundary hyperplanes of the reachable set. The result can be applied to determine the minimum control time required for a given terminal state. IfN leq n, the method of echelon matrix analysis is employed to solve the same problem.     

Robust MPC of constrained discrete-time nonlinear systems based on approximated reachable sets

A robust MPC for constrained nonlinear systems with uncertainties is presented. Outer bounds of the reachable sets of the system are used to predict the evolution of the system under uncertainty. A method that uses zonotopes to represent the approximated reachable sets is proposed. The closed-loop system is ultimately bounded thanks to a contractive constraint that drives the system to a robust invariant set.     

Reachability analysis of continuous-time piecewise affine systems

This paper proposes an algorithm for the characterization of reachable sets of states for continuous-time piecewise affine systems. Given a model of the system and a bounded set of possible initial states, the algorithm employs an LMI approach to compute both upper and lower bounds on reachable regions. Rather than performing computations in the state-space, this method uses impact maps to find the reachable sets on the switching surfaces of the system. This tool can then be used to deduce safety and performance results about the system.     

Asymptotic theory of attainable sets to linear periodic impulsive control systems

In this paper, asymptotic large-time dynamics of attainable sets to linear periodic control systems with bounded total impulse of control is studied. Asymptotic formulas for attainable sets and their shapes, i.e., the same sets considered up to an arbitrary nonsingular linear transformation, are found. It is shown that all limit shapes are obtained as the join of the limit shapes for neutral, stable-neutral, and unstable-neutral system components.     

On the asymptotic stability of boundary trajectories

For a class of dynamical systems, it is shown that trajectories which remain on the boundary of a non-empty, connected subset of a reachable set must be asymptotically stable. Using this result and a reachability maximum principle, we obtain a control law which will drive the system from the origin to the boundary of the reachable set for a class of two-dimensional linear control systems. Using this control law, the reachable set is easily constructed.