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

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

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.     

基于Hamilton-Jacobi方程的飞行器机动动作可达集分析

为了给驾驶员完成标准机动动作提供决策支持, 提出一种使用哈密尔顿-雅克比(Hamilton-Jacobi)方程求解机动动作可行状态空间的研究方法.使用关键点将机动动作划分为不同阶段, 将各关键点的标准状态约束作为目标集, 逆时间求解目标集对应的可达集得到各阶段的边界状态范围, 目标集和可达集均由零水平集表示.使用该方法得到斤斗动作三维度运动模型下各阶段的可达集及斤斗动作的可行状态空间, 为了使运动模型的控制量与驾驶员实际操纵更为接近, 构建了以迎角变化率为控制量的四维度运动模型, 在此基础上对斤斗动作各阶段的可达集进行了分析.     

A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games

We describe and implement an algorithm for computing the set of reachable states of a continuous dynamic game. The algorithm is based on a proof that the reachable set is the zero sublevel set of the viscosity solution of a particular time-dependent Hamilton-Jacobi-Isaacs partial differential equation. While alternative techniques for computing the reachable set have been proposed, the differential game formulation allows treatment of nonlinear systems with inputs and uncertain parameters. Because the time-dependent equation's solution is continuous and defined throughout the state space, methods from the level set literature can be used to generate more accurate approximations than are possible for formulations with potentially discontinuous solutions. A numerical implementation of our formulation is described and has been released on the web. Its correctness is verified through a two vehicle, three dimensional collision avoidance example for which an analytic solution is available.     

A proximal characterization of the reachable set

We show that the graph of the reachable set of a control system given by a differential inclusion is uniquely characterized by a Hamilton-Jacobi equation involving proximal normals.     

基于时序关系的系统失效可达图生成方法

针对状态事件故障树生成系统可达图过程中存在的状态空间爆炸问题,提出了一种基于时序关系的系统失效可达图生成方法。通过分析触发和被触发类型事件的时序关系,对存在时序关系的事件进行排序,根据时序关系获得系统构件间的所有不可同时到达状态对,对构件间的可同时到达状态建立笛卡尔积,获得系统的所有可同时到达状态对,根据连接表和最小割集获得系统失效的状态可达图,从而有效解决系统失效可达图生成过程中存在的状态空间爆炸问题。应用基于时序关系的系统失效可达图方法生成鱼攻系统失效可达图,实验结果 验证了该方法的可行性与稳定性; 同时也为表明其能有效地缓解状态空间爆炸问题,为状态事件故障树生成系统可达图提供了一种新的方法。     

Optimal technique for estimating the reachable set of a controlled n-dimensional linear system

The reachable set from a given point of a controlled dynamical system is the set of all states to which the system can be driven from that point in a finite time by the allowed controls. A technique is presented Tor estimating the reachable set from the asymptotically-stable origin of a class of n-dimensional linear systems under bounded control. The technique is an optimal version of a Lyapunov method, and provides an (over-)estimate of the full reachable set; it involves the minimization of a quadratic constraint, followed by the maximization of a quadratic form subject to this constraint. The non-linear optimization problems can be routinely solved by means of computer algebra and commonly available computer software. In general, the technique produces a much-improved estimate of the reachable set compared to that given by the standard Lyapunov method. Another advantage of the technique is that it is truly applicable to higher-dimensional systems (n ≥ 3). Since the estimate produced is in the convenient form of an n-dimensional ellipsoid, projections of the estimate onto any space of dimension ≤ n — 1 can be readily found. Problems of two, three, and four dimensions are solved to illustrate the technique.     

Feedback-reversibility and reachability of linear impulsive systems

For a linear impulsive system, the set of states that are reachable from the origin when the initial time, impulse times, and final time are fixed is contained in an invariant subspace determined by the system data. It is known that reversibility of the system is sufficient to yield, for a specified initial time, the existence of some impulse time set and final time for which the reachable set equals the invariant subspace. In this paper, we relax the reversibility requirement and present a condition that is necessary as well as sufficient under which this property holds. This new condition involves the property of achieving reversibility via feedback and admits an explicit geometric characterization. Moreover, this feedback-reversibility property only needs to hold for the subsystem defined as the full system restricted to the invariant subspace. We further show that feedback-reversibility of the restricted system ensures that the reachable set equals the invariant subspace for almost any impulse time set and final time for which the number of impulse times contained in the underlying time interval exceeds a lower bound.     

Time-scale decomposition of the reachable set of constrained linear systems

We consider a linear control system with a multiparameter singular perturbation representing multiple time scales and with constraints for the control and the slow state. The Hausdorff limit of the reachable set when the small parameters tend to zero is found. The result provides a basis for a time-scale approximation of the reachable set.on leave from the Institute of Mathematics, Bulgarian Academy of Sciences, Sofia, Bulgaria.     

On reachable sets for linear systems with delay and bounded peak inputs

Linear systems with constant coefficients and time-varying delays are considered. We address the problem of finding an ellipsoid that bounds the set of the states in the Euclidean space that are reachable from the origin, in finite time, by inputs with peak value that is bounded by a prechosen positive scalar. The system may encounter uncertainties in the matrices of its state space model and in the delay length. The Lyapunov-Razumikhin approach is applied and a bounding ellipsoid is obtained by solving a set of linear matrix inequalities that depend on the upper-bound of the delay length.     

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.     

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

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

The reachability problem for branching vector addition systems requires doubly-exponential space

Branching vector addition systems are an extension of vector addition systems where new reachable vectors may be obtained by summing two reachable vectors and adding an integral vector from a fixed finite set. The reachability problem for them is shown hard for doubly-exponential space. For an alternative extension of vector addition systems, where reachable vectors may be combined by subtraction, most decision problems of interest are shown undecidable.     

Elements of security: Closure,convergence, and protection

We argue that three concepts of stabilization theory are adequate to explain system security. Our argument is based on the assumption that the reachable states of a secure system can be partitioned into legitimate and illegitimate states such that three conditions hold. First, the set of reachable states is closed under both system execution and adversary interference, and the set of legitimate states is closed under system execution. Second, any system computation that starts at an illegitimate state eventually converges to a legitimate state. Third, the critical variables of the system are protected from being updated during any adversary interference and during any system transition that starts at an illegitimate state.     

The complexity of some reachability problems for a system on a finite group

We consider a system defined as the product of a finite set of periodic systems on cyclic groups. It is of interest to determine if certain subgroups and unions of subgroups of the state set are reachable from a specified initial state, and in particular to determine the computational complexity of verifying such reachability. These questions are motivated by certain problems that arise in the modelling and control of discrete event systems and certain forms of periodic scheduling. Our main result is that deciding whether or not the union of a certain set of subgroups is reachable or not is NP-complete.     

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.     

Termination of nondeterministic quantum programs

We define a language-independent model of nondeterministic quantum programs in which a quantum program consists of a finite set of quantum processes. These processes are represented by quantum Markov chains over the common state space, which formalize the quantum mechanical behaviors of the machine. An execution of a nondeterministic quantum program is modeled by a sequence of actions of individual processes, and at each step of an execution a process is chosen nondeterministically to perform the next action. This execution model formalize the users’ behavior of calling the processes in the classical world. Applying the model to a quantum walk as an instance of physically realizable systems, we describe an execution step by step. A characterization of reachable space and a characterization of diverging states of a nondeterministic quantum program are presented. We establish a zero-one law for termination probability of the states in the reachable space. A combination of these results leads to a necessary and sufficient condition for termination of nondeterministic quantum programs. Based on this condition, an algorithm is found for checking termination of nondeterministic quantum programs within a fixed finite-dimensional state space.     

Construction of switching sequences for reachability realization of switched impulsive control systems

This paper studies the construction of switching sequences for reachability realization of switched impulsive control systems. An approach is proposed to design switching sequences so that the reachable subspace of switched impulsive control systems is expressed in terms of the reachable state sets of the designed switching sequences. For a class of switched impulsive control systems, it is proved that a single switching sequence can be designed with its reachable state set coinciding with the reachable subspace. Periodic switching sequences are also constructed in this paper for the reachability realization problem. The results present a new way to exploit the switching mechanism to achieve the reachability and controllability of switched impulsive control systems. Copyright © 2007 John Wiley & Sons, Ltd.     

一种求解线性控制系统可达集的数值方法

针对线性控制系统,研究应用常微分方程数值方法和优化技术相结合的近似可达集的方法.首先,用常微分方程数值方法对系统进行离散化.然后,提出基于优化技术的外部投影法来近似离散系统的可达集.外部投影法构造有限多个投影问题,每个都对应一个凸优化问题,通过求解这些凸优化问题最终可以得到可达集的近似描述.最后,通过数值仿真结果验证了所提出方法的有效性.与文献中已有的方法相比,在求解相同数量凸优化问题的情况下,外部投影法的近似精度更高.     

Hybrid control synthesis for eventuality specifications using level set methods

This paper is concerned with the extraction of controllers for hybrid systems with respect to eventuality specifications. Given a hybrid system modelled by a hybrid automaton and a target set of states, the objective is to compute the maximal set of initial states together with the hybrid control policy such that all the trajectories of the controlled system reach the target in finite time. Due to the existence of set-valued disturbance inputs, the problem is studied in a game-theoretic framework. Having shown that a least restrictive solution does not exist, we propose a dynamic programming algorithm that computes the maximal initial set and a controller with the desired property. To implement the algorithm, reachable sets of pursuit-evasion differential games need to be computed. For that reason level set methods are employed, where the boundary of the reachable set is characterized as the zero level set of a Hamilton–Jacobi equation. The procedure for the numerical extraction of the controller is presented in detail and examples illustrate the methodology. Finally, to demonstrate the practical character of our results, a control design problem in the benchmark system of the batch evaporator is considered as an eventuality synthesis problem and solved using the proposed methodology.