We present a scalable set-valued safety-preserving controller for constrained continuous-time linear time-invariant (LTI) systems subject to additive, unknown but bounded disturbance or uncertainty. The approach relies upon a conservative approximation of the discriminating kernel using robust maximal reachable sets---an extension of our earlier work on computation of the viability kernel for high-dimensional systems. Based on ellipsoidal techniques for reachability, a piecewise ellipsoidal algorithm with polynomial complexity is described that under-approximates the discriminating kernel under LTI dynamics. This precomputed piecewise ellipsoidal set is then used online to synthesize a permissive state-feedback safety-preserving controller. The controller is modeled as a hybrid automaton and can be formulated such that under certain conditions the resulting control signal is continuous across its transitions. We show the performance of the controller on a twelve-dimensional flight envelope protection problem for a quadrotor with actuation saturation and unknown wind disturbances.
A classification technique based on support vector machines (SVMs) is presented in @cite_35 that approximates the viability kernel and yields an analytical expression of its boundary. A sequential minimal optimization algorithm is solved to compute the SVM that in turn forms a barrier function on or close to the boundary of the viability kernel in the discretized state space. While the method successfully reduces the computational time for the synthesis of control laws when the dimension of the input space is high, its applicability to systems with high-dimensional is limited. The method does not provide any guarantees that the synthesized control laws are safety-preserving.
@cite_35
1982613542 2096989899 2128529555 2137346077
We propose an algorithm which performs a progressive approximation of a viability kernel, iteratively using a classification method. We establish the mathematical conditions that the classification method should fulfil to guarantee the convergence to the actual viability kernel. We study more particularly the use of support vector machines (SVMs) as classification techniques. We show that they make possible to use gradient optimisation techniques to find a viable control at each time step, and over several time steps. This allows us to avoid the exponential growth of the computing time with the dimension of the control space. It also provides simple and efficient control procedures. We illustrate the method with some examples inspired from ecology Effective use of support vector machines (SVMs) in classification necessitates the appropriate choice of a kernel. Designing problem specific kernels involves the definition of a similarity measure, with the condition that kernels are positive semi-definite (PSD). An alternative approach which places no such restrictions on the similarity measure is to construct a set of inputs and let each example be represented by its similarity to all the examples in this set and then apply a conventional SVM to this transformed data. Dynamic time warping (DTW) is a well established distance measure for time series but has been of limited use in SVMs since it is not obvious how it can be used to derive a PSD kernel. The feasibility of the similarity based approach for DTW is investigated by applying the method to a large set of time-series classification problems. Linear support vector machines (SVM) are useful for classifying large-scale sparse data. Problems with sparse features are common in applications such as document classification and natural language processing. In this paper, we propose a novel coordinate descent algorithm for training linear SVM with the L2-loss function. At each step, the proposed method minimizes a one-variable sub-problem while fixing other variables. The sub-problem is solved by Newton steps with the line search technique. The procedure globally converges at the linear rate. As each sub-problem involves only values of a corresponding feature, the proposed approach is suitable when accessing a feature is more convenient than accessing an instance. Experiments show that our method is more efficient and stable than state of the art methods such as Pegasos and TRON. The Support Vector Machine (SVM) is a new and very promising classification technique developed by Vapnik and his group at AT &T Bell Labs. This new learning algorithm can be seen as an alternative training technique for Polynomial, Radial Basis Function and Multi-Layer Perceptron classifiers. An interesting property of this approach is that it is an approximate implementation of the Structural Risk Minimization (SRM) induction principle. The derivation of Support Vector Machines, its relationship with SRM, and its geometrical insight, are discussed in this paper. Training a SVM is equivalent to solve a quadratic programming problem with linear and box constraints in a number of variables equal to the number of data points. When the number of data points exceeds few thousands the problem is very challenging, because the quadratic form is completely dense, so the memory needed to store the problem grows with the square of the number of data points. Therefore, training problems arising in some real applications with large data sets are impossible to load into memory, and cannot be solved using standard non-linear constrained optimization algorithms. We present a decomposition algorithm that can be used to train SVM''s over large data sets. The main idea behind the decomposition is the iterative solution of sub-problems and the evaluation of, and also establish the stopping criteria for the algorithm. We present previous approaches, as well as results and important details of our implementation of the algorithm using a second-order variant of the Reduced Gradient Method as the solver of the sub-problems. As an application of SVM''s, we present preliminary results we obtained applying SVM to the problem of detecting frontal human faces in real images.