skip to main content

Search for: All records

Creators/Authors contains: "Yang, Liren"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Backward reachability analysis is essential to synthesizing controllers that ensure the correctness of closed-loop systems. This paper is concerned with developing scalable algorithms that under-approximate the backward reachable sets, for discrete-time uncertain linear and nonlinear systems. Our algorithm sequentially linearizes the dynamics, and uses constrained zonotopes for set representation and computation. The main technical ingredient of our algorithm is an efficient way to under-approximate the Minkowski difference between a constrained zonotopic minuend and a zonotopic subtrahend, which consists of all possible values of the uncertainties and the linearization error. This Minkowski difference needs to be represented as a constrained zonotope to enable subsequent computation, but, as we show, it is impossible to find a polynomial-size representation for it in polynomial time. Our algorithm finds a polynomial-size under-approximation in polynomial time. We further analyze the conservatism of this under-approximation technique, and show that it is exact under some conditions. Based on the developed Minkowski difference technique, we detail two backward reachable set computation algorithms to control the linearization error and incorporate nonconvex state constraints. Several examples illustrate the effectiveness of our algorithms.
    Free, publicly-accessible full text available August 26, 2023
  2. Zonotopes are widely used for over-approximating forward reachable sets of uncertain linear systems for verification purposes. In this paper, we use zonotopes to achieve more scalable algorithms that under-approximate backward reachable sets of uncertain linear systems for control design. The main difference is that the backward reachability analysis is a twoplayer game and involves Minkowski difference operations, but zonotopes are not closed under such operations. We underapproximate this Minkowski difference with a zonotope, which can be obtained by solving a linear optimization problem. We further develop an efficient zonotope order reduction technique to bound the complexity of the obtained zonotopic underapproximations. The proposed approach is evaluated against existing approaches using randomly generated instances and illustrated with several examples.
  3. In this paper, we first propose a method that can efficiently compute the maximal robust controlled invariant set for discrete-time linear systems with pure delay in input. The key to this method is to construct an auxiliary linear system (without delay) with the same state-space dimension of the original system in consideration and to relate the maximal invariant set of the auxiliary system to that of the original system. When the system is subject to disturbances, guaranteeing safety is harder for systems with input delays. Ability to incorporate any additional information about the disturbance becomes more critical in these cases. Motivated by this observation, in the second part of the paper, we generalize the proposed method to take into account additional preview information on the disturbances, while maintaining computational efficiency. Compared with the naive approach of constructing a higher dimensional system by appending the state-space with the delayed inputs and previewed disturbances, the proposed approach is demonstrated to scale much better with the increasing delay time.
  4. Mixed monotonicity is a property of a system’s vector field that says that the vector field admits a decomposition function, in a lifted space, that has some order preserving properties. It is recently shown that this property allows one to efficiently over-approximate the system’s onestep reachable set with a hyperinterval, which is obtained by evaluating the vector field’s decomposition function at two points. Such decomposition functions are usually not unique and some decompositions may not be tight in the sense that the resulting hyperintervals are not the smallest ones that contain the exact one-step reachable set, which leads to conservative over-approximation. In this paper, we show that for a general class of functions, there exists a tight decomposition, which can be implicitly constructed as the solution of certain optimization problems. This implies that any function from Rn to Rm (hence any forward complete system) is mixed-monotone. However, the usefulness of the constructed tight decomposition functions is limited by the fact that it might not be possible to evaluate them efficiently. We show that under certain conditions, the tight decompositions can reduce to a function with explicit expression, which can be directly evaluated. This result suggests that it is not mixedmore »monotonicity itself, but other extra properties, which lead to explicitly evaluatable decomposition functions, that enable efficient and tight hyperinterval over-approximationof reachable sets.« less