Computation of maximal safe sets for switching systems

The problem of determining maximal safe sets and hybrid controllers is computationally intractable because of the mathematical generality of hybrid system models. Given the practical and theoretical relevance of the problem, finding implementable procedures that could at least approximate the maximal safe set is important. To this end, we begin by restricting our attention to a special class of hybrid systems: switching systems. We exploit the structural properties of the graph describing the discrete part of a switching system to develop an efficient procedure for the computation of the safe set. This procedure requires the computation of a maximal controlled invariant set. We then restrict our attention to linear discrete-time systems for which there is a wealth of results available in the literature for the determination of maximal controlled invariant sets. However, even for this class of systems, the computation may not converge in a finite number of steps. We then propose to compute inner approximations that are controlled invariant and for which a procedure that terminates in a finite number of steps can be obtained. A tight bound on the error can be given by comparing the inner approximation with the classical outer approximation of the maximal controlled invariant set. Our procedure is applied to the idle-speed regulation problem in engine control to demonstrate its efficiency.     

Enlarging the domain of attraction of MPC controllers

This paper presents a method for enlarging the domain of attraction of nonlinear model predictive control (MPC). The usual way of guaranteeing stability of nonlinear MPC is to add a terminal constraint and a terminal cost to the optimization problem such that the terminal region is a positively invariant set for the system and the terminal cost is an associated Lyapunov function. The domain of attraction of the controller depends on the size of the terminal region and the control horizon. By increasing the control horizon, the domain of attraction is enlarged but at the expense of a greater computational burden, while increasing the terminal region produces an enlargement without an extra cost.In this paper, the MPC formulation with terminal cost and constraint is modified, replacing the terminal constraint by a contractive terminal constraint. This constraint is given by a sequence of sets computed off-line that is based on the positively invariant set. Each set of this sequence does not need to be an invariant set and can be computed by a procedure which provides an inner approximation to the one-step set. This property allows us to use one-step approximations with a trade off between accuracy and computational burden for the computation of the sequence. This strategy guarantees closed loop-stability ensuring the enlargement of the domain of attraction and the local optimality of the controller. Moreover, this idea can be directly translated to robust MPC.     

Constrained piecewise linear systems with disturbances: Controller design via convex invariant sets

This paper presents two control strategies under the time optimal control and model predictive control frameworks for constrained piecewise linear systems with bounded disturbances (PWLBD systems). Each of the proposed approaches uses an inner convex polytopal approximation of the non‐convex domains of attraction and results in simplified control laws that can be determined off‐line via multi‐parametric programming. These control strategies rely on invariant sets of PWLBD systems. Thereby, approaches for the computation of the disturbance invariant outer bounds of the minimal disturbance invariant set, F_∞, and convex polytopal disturbance invariant sets are presented. The effectiveness of the approaches is assessed through numerical examples. Copyright © 2007 John Wiley & Sons, Ltd.     

Computation of Feasible and Invariant Sets for Interpolation-based MPC

The terminal invariant set plays a key role in the stabilizing MPC (Model Predictive Control) formulation. When control gains of the terminal local control laws and corresponding feasible and invariant sets are given, the existing interpolation methods unite them to enlarge the stabilizable region and enhance performance. In this paper, when an invariant set is given, an algorithm is proposed to find another invariant set such that their convex hull is maximized and also invariant. Numerical examples show that the set of the stabilizable initial state of the MPC is enlarged by the terminal constraint set computed by an interpolation-based approach.

     

Robust feedback model predictive control of constrained uncertain systems

We propose a novel procedure for the solution to the problem of robust model predictive control (RMPC) of linear discrete time systems involving bounded disturbances and model-uncertainties along with hard constraints on the input and state. The RMPC (outer) controller – responsible for steering the uncertain system state to a designed invariant (terminal) set – has a mixed structure consisting of a state-feedback component as well as a control-perturbation. Both components are explicitly considered as decision variables in the online optimization and the nonlinearities commonly associated with such a state-feedback parameterization are avoided by adopting a sequential approach in the formulation. The RMPC controller minimizes an upper bound on an H₂/H_∞-based cost function. Moreover, the proposed algorithm does not require any offline calculation of (feasible) feedback gains for the computation of the RMPC controller. The optimal Robust Positively invariant set and the inner controller – responsible for keeping the state within the invariant set – are both computed in one step as solutions to an LMI optimization problem. We also provide conditions which guarantee the Lyapunov stability of the closed-loop system. Numerical examples, taken from the literature, demonstrate the advantages of the proposed scheme.     

Full‐complexity polytopic robust control invariant sets for uncertain linear discrete‐time systems

This paper presents an algorithm for the computation of full‐complexity polytopic robust control invariant (RCI) sets, and the corresponding linear state‐feedback control law. The proposed scheme can be applied for linear discrete‐time systems subject to additive disturbances and structured norm‐bounded or polytopic uncertainties. Output, initial condition, and performance constraints are considered. Arbitrary complexity of the invariant polytope is allowed to enable less conservative inner/outer approximations to the RCI sets whereas the RCI set is assumed to be symmetric around the origin. The nonlinearities associated with the computation of such an RCI set structure are overcome through the application of Farkas' theorem and a corollary of the elimination lemma to obtain an initial polytopic RCI set, which is guaranteed to exist under certain conditions. A Newton‐like update, which is recursively feasible, is then proposed to yield desirable large/small volume RCI sets.     

An Interpolation Technique for Input Constrained Robust Stabilization

This paper presents an interpolation technique of two given robust stabilizing gains for input constrained uncertain systems. The proposed interpolated feedback gain is computed at every sampling instance by solving an optimization problem with a single decision variable. Use of the interpolated feedback gain can bring about not only large invariant set but also good control performance. Moreover, it is shown that the feasible and invariant set yielded by the proposed control is the convex hull of the two invariant sets by the known controls. The simulation results show that the proposed interpolation based feedback gain indeed results in both large invariant set and good control performance.     

A predictor-corrector type algorithm for the pseudospectral abscissa computation of time-delay systems

The pseudospectrum of a linear time-invariant system is the set in the complex plane consisting of all the roots of the characteristic equation when the system matrices are subjected to all possible perturbations with a given upper bound. The pseudospectral abscissa is defined as the maximum real part of the characteristic roots in the pseudospectrum and, therefore, it is for instance important from a robust stability point of view. In this paper we present an accurate method for the computation of the pseudospectral abscissa of retarded delay differential equations with discrete pointwise delays. Our approach is based on the connections between the pseudospectrum and the level sets of an appropriately defined complex function. The computation is done in two steps. In the prediction step, an approximation of the pseudospectral is obtained based on a rational approximation of the characteristic matrix and the application of a bisection algorithm. Each step in this bisection algorithm relies on checking the presence of the imaginary axis eigenvalues of a complex matrix, similar to the delay free case. In the corrector step, the approximate pseudospectral abscissa is corrected to any given accuracy, by solving a set of nonlinear equations that characterizes the extreme points in the pseudospectrum contours.     

On invariant sets and closed‐loop boundedness of Lure‐type nonlinear systems by LPV‐embedding

We address the problem of achieving trajectory boundedness and computing ultimate bounds and invariant sets for Lure‐type nonlinear systems with a sector‐bounded nonlinearity. Our first contribution is to compare two systematic methods to compute invariant sets for Lure systems. In the first method, a linear‐like bound is considered for the nonlinearity, and this bound is used to compute an invariant set by regarding the nonlinear system as a linear system with a nonlinear perturbation. In the second method, the sector‐bounded nonlinearity is treated as a time‐varying parameterised linear function with bounded parameter variations, and then invariant sets are computed by embedding the nonlinear system into a convex polytopic linear parameter varying (LPV) system. We show that under some conditions on the system matrices, these approaches give identical invariant sets, the LPV‐embedding method being less conservative in the general case. The second contribution of the paper is to characterise a class of Lure systems, for which an appropriately designed linear state feedback achieves bounded trajectories of the closed‐loop nonlinear system and allows for the computation of an invariant set via a simple, closed‐form expression. The third contribution is to show that, for disturbances that are ‘aligned’ with the control input, arbitrarily small ultimate bounds on the system states can be achieved by assigning the eigenvalues of the linear part of the system with ‘large enough’ negative real part. We illustrate the results via examples of a pendulum system, a Josephson junction circuit and the well‐known Chua circuit. Copyright © 2015 John Wiley & Sons, Ltd.     

Componentwise ultimate bound and invariant set computation for switched linear systems

We present a novel ultimate bound and invariant set computation method for continuous-time switched linear systems with disturbances and arbitrary switching. The proposed method relies on the existence of a transformation that takes all matrices of the switched linear system into a convenient form satisfying certain properties. The method provides ultimate bounds and invariant sets in the form of polyhedral and/or mixed ellipsoidal/polyhedral sets, is completely systematic once the aforementioned transformation is obtained, and provides a new sufficient condition for practical stability. We show that the transformation required by our method can easily be found in the well-known case where the subsystem matrices generate a solvable Lie algebra, and we provide an algorithm to seek such transformation in the general case. An example comparing the bounds obtained by the proposed method with those obtained from a common quadratic Lyapunov function computed via linear matrix inequalities shows a clear advantage of the proposed method in some cases.     

Constraint‐admissible sets for systems with soft constraints and their application in model predictive control

Constraint‐admissible sets have been widely used in the study of control systems with hard constraints. This paper proposes a generalization of the maximal constraint‐admissible set for constrained linear discrete‐time systems to the case where soft or probabilistic constraints are present. Defined in the most obvious way, the maximal probabilistic constraint‐admissible set is not invariant. An inner approximation of it is proposed which is invariant and has other nice properties. The application of this approximate set in a model predictive control framework with probabilistic constraints is discussed, including the feasibility and stability of the resulting closed‐loop system. The effectiveness of the proposed approach is illustrated via numerical examples. Copyright © 2011 John Wiley & Sons, Ltd.     

The directed Hausdorff distance between imprecise point sets

We consider the directed Hausdorff distance between point sets in the plane, where one or both point sets consist of imprecise points. An imprecise point is modelled by a disc given by its centre and a radius. The actual position of an imprecise point may be anywhere within its disc. Due to the direction of the Hausdorff distance and whether its tight upper or lower bound is computed, there are several cases to consider. For every case we either show that the computation is NP-hard or we present an algorithm with a polynomial running time. Further we give several approximation algorithms for the hard cases and show that one of them cannot be approximated better than with factor 3, unless P=NP.     

Polyhedral Feasible Set Computation of MPC-Based Optimal Control Problems

Feasible sets play an important role in model predictive control (MPC) optimal control problems (OCPs). This paper proposes a multi-parametric programming-based algorithm to compute the feasible set for OCP derived from MPC-based algorithms involving both spectrahedron (represented by linear matrix inequalities) and polyhedral (represented by a set of inequalities) constraints. According to the geometrical meaning of the inner product of vectors, the maximum length of the projection vector from the feasible set to a unit spherical coordinates vector is computed and the optimal solution has been proved to be one of the vertices of the feasible set. After computing the vertices, the convex hull of these vertices is determined which equals the feasible set. The simulation results show that the proposed method is especially efficient for low dimensional feasible set computation and avoids the non-unicity problem of optimizers as well as the memory consumption problem that encountered by projection algorithms.      

Output feedback receding horizon control of constrained systems

This paper considers output feedback control of linear discrete-time systems with convex state and input constraints which are subject to bounded state disturbances and output measurement errors. We show that the non-convex problem of finding a constraint admissible affine output feedback policy over a finite horizon, to be used in conjunction with a fixed linear state observer, can be converted to an equivalent convex problem. When used in the design of a time-varying robust receding horizon control law, we derive conditions under which the resulting closed-loop system is guaranteed to satisfy the system constraints for all time, given an initial state estimate and bound on the state estimation error. When the state estimation error bound matches the minimal robust positively invariant (mRPI) set for the system error dynamics, we show that this control law is time-invariant, but its calculation generally requires solution of an infinite-dimensional optimization problem. Finally, using an invariant outer approximation to the mRPI error set, we develop a time-invariant control law that can be computed by solving a finite-dimensional tractable optimization problem at each time step that guarantees that the closed-loop system satisfies the constraints for all time.     

Invariant approximations of the minimal robust positively Invariant set

This note provides results on approximating the minimal robust positively invariant (mRPI) set (also known as the 0-reachable set) of an asymptotically stable discrete-time linear time-invariant system. It is assumed that the disturbance is bounded, persistent and acts additively on the state and that the constraints on the disturbance are polyhedral. Results are given that allow for the computation of a robust positively invariant, outer approximation of the mRPI set. Conditions are also given that allow one to a priori specify the accuracy of this approximation.     

Noise Induced Transitions in a Stochastic Volterra-Hamilton Open System

A Volterra-Hamilton system describing the evolution of a dimorphic clone in the presence of inner developmental noise is considered as an open system in interaction with a fluctuating environment, subject to optimum growth conditions.In the case of constant environment considered previously by Antonelli and Kivan the system is confined to an invariant set of a stationary diffusion process, which provides a model of growth canalization. Different invariant sets can be identified with different clonal types of a given species. The probability distribution of the diffusion over an invariant set accounts for the variability within the corresponding clonal type.In this paper, the external noise in a non-constant environment is shown to trigger transitions between invariant sets as it interacts with the inner developmental noise. Such transitions from one clonal type to another, which do not involve any genetic alterations, are known in biology as plastic responses to the environment.This is an entirely different mechanism than genetic mutations, which can disturb the equilibrium of the system. If after such a mutation the system settles down in a new stationary state with its own invariant sets and probability distribution, then one or more new genetically altered species will emerge.     

基于样本选择的最近邻凸包分类器

最近邻凸包分类算法是一种以测试点到各类别样本凸包的距离为分类度量的最近邻分类算法。然而,该算法的凸二次规划问题优化求解的较高的计算复杂度限制了其在较大规模数据集上的应用。本文提出一种样本选择方法——子类凸包生长法。通过迭代,选择距离选出样本凸包最远的点,直到满足终止条件,从而实现数据集的有效约简。ORL数据库和MIT-CBCL人脸识别training-synthetic库上的实验结果表明,子类凸包生长法选出的少量样本生成的凸包能够很好的表征训练集,在不降低最近邻凸包分类器性能的同时,使得算法的计算速度大为提高。     

一种基于衰减集结的鲁棒预测控制器

高效鲁棒预测控制 (ERPC) 是一种在线计算量较小, 且控制性能较好的鲁棒预测控制算法. 但采用单一椭圆不变集的设计方法存在保守性. 本文采用衰减集结策略, 通过离线设计在系统状态空间中投影彼此正交的两个椭圆不变集, 在线进行凸组合的方法设计 ERPC 控制器, 使系统初始可行域进一步扩大, 并在一定程度上改善了控制性能.     

Cubic B-spline curve approximation by curve unclamping

A new approach for cubic B-spline curve approximation is presented. The method produces an approximation cubic B-spline curve tangent to a given curve at a set of selected positions, called tangent points, in a piecewise manner starting from a seed segment. A heuristic method is provided to select the tangent points. The first segment of the approximation cubic B-spline curve can be obtained using an inner point interpolation method, least-squares method or geometric Hermite method as a seed segment. The approximation curve is further extended to other tangent points one by one by curve unclamping. New tangent points can also be added, if necessary, by using the concept of the minimum shape deformation angle of an inner point for better approximation. Numerical examples show that the new method is effective in approximating a given curve and is efficient in computation.     

Controlled invariant feasibility — A general approach to enforcing strong feasibility in MPC applied to move-blocking

Strong feasibility of MPC problems is usually enforced by constraining the state at the final prediction step to a controlled invariant set. However, such terminal constraints fail to enforce strong feasibility in a rich class of MPC problems, for example when employing move-blocking. In this paper a generalized, least restrictive approach for enforcing strong feasibility of MPC problems is proposed and applied to move-blocking MPC. The approach hinges on the novel concept of controlled invariant feasibility. Instead of a terminal constraint, the state of an earlier prediction step is constrained to a controlled invariant feasible set. Controlled invariant feasibility is a generalization of controlled invariance. The convergence of well-known approaches for determining maximum controlled invariant sets, and j-step admissible sets, is formally proved. Thus an algorithm for rigorously approximating maximum controlled invariant feasible sets is developed for situations where the exact maximum cannot be determined.