Controlled linear perturbation

We present an algorithmic solution to the robustness problem in computational geometry, called controlled linear perturbation, and demonstrate it on Minkowski sums of polyhedra. The robustness problem is how to implement real RAM algorithms accurately and efficiently using computer arithmetic. Approximate computation in floating point arithmetic is efficient but can assign incorrect signs to geometric predicates, which can cause combinatorial errors in the algorithm output. We make approximate computation accurate by performing small input perturbations, which we compute using differential calculus. This strategy supports fast, accurate Minkowski sum computation. The only prior robust implementation uses a less efficient algorithm, requires exact algebraic computation, and is far slower based on our extensive testing.     

An auto-generated real-time iteration algorithm for nonlinear MPC in the microsecond range

In this paper, we present an automatic C-code generation strategy for real-time nonlinear model predictive control (NMPC), which is designed for applications with kilohertz sample rates. The corresponding code export module has been implemented within the software package ACADO Toolkit. It is capable of exporting fixed step-size integrators together with their sensitivities as well as a real-time Gauss–Newton method. Here, we employ the symbolic representation of optimal control problems in ACADO in order to auto-generate plain C-code which is optimized for final production. The exported code has been tested for model predictive control scenarios comprising constrained nonlinear dynamic systems with four states and a control horizon of ten samples. The numerical simulations show a promising performance of the exported code being able to provide feedback in much less than a millisecond.     

Observability of switching structured linear systems with unknown input. A graph-theoretic approach

This paper deals with the observability of the discrete mode, the internal state and the input of switching structured linear systems with unknown input. The proposed method, based on a graph-theoretic approach, assumes only the knowledge of the system’s structure. We express, in graphical terms, necessary and sufficient conditions for the generic observability of the discrete mode, the continuous internal state and the input of a switching structured linear system. These conditions can be implemented by classical graph theory algorithms based on finding particular paths and cycles in a digraph.     

Redesign of adaptive observers for improved parameter identification in nonlinear systems

We propose a method for redesigning adaptive observers for nonlinear systems. The redesign uses an adaptive law that is based on delayed observers. This increases the computational burden, but gives significantly better parameter identification and robustness properties. In particular, given that a special persistency of excitation condition is satisfied, we prove uniform global asymptotic stability and semi-global exponential stability of the origin of the state and parameter estimation error, and give explicit lower bounds on the convergence rate of both the state and parameter estimation error dynamics. For initial conditions with a known upper bound, we prove tunable exponential convergence rate. To illustrate the use of the proposed method, we apply it to estimate the unmeasured flow rate and the uncertain friction parameters in a model of a managed pressure drilling system. The simulation results clearly show the improved performance of the redesigned adaptive observer compared to a traditional design.     

Optimal memoryless control in Gaussian noise: A simple counterexample

In this paper, we investigate control strategies for a scalar, one-step delay system in discrete-time, i.e., the state of the system is the input delayed by one time unit. In contrast with classical approaches, here the control action must be a memoryless function of the output of the plant, which comprises the current state corrupted by measurement noise. We adopt a first order state-space representation for the delay system, where the initial state is a Gaussian random variable. In addition, we assume that the measurement noise is drawn from a white and Gaussian process with zero mean and constant variance. Performance evaluation is carried out via a finite-time quadratic cost that combines the second moment of the control signal, and the second moment of the difference between the initial state and the state at the final time. We show that if the time-horizon is one or two then the optimal control is a linear function of the plant’s output, while for a sufficiently large horizon a control taking on only two values will outperform the optimal affine solution. This paper complements the well-known counterexample by Hans Witsenhausen, which showed that the solution to a linear, quadratic and Gaussian optimal control paradigm might be nonlinear. Witsenhausen’s counterexample considered an optimization horizon with two time-steps (two stage control). In contrast with Witsenhausen’s work, the solution to our counterexample is linear for one and two stages but it becomes nonlinear as the number of stages is increased. The fact that our paradigm leads to nonlinear solutions, in the multi-stage case, could not be predicted from prior results. In contrast to prior work, the validity of our counterexample is based on analytical proof methods. Our proof technique rests on a simple nonlinear strategy that is useful in its own right, since it outperforms any affine solution.     

Analysis of autocatalytic networks in biology

Autocatalytic networks, in particular the glycolytic pathway, constitute an important part of the cell metabolism. Changes in the concentration of metabolites and catalyzing enzymes during the lifetime of the cell can lead to perturbations from its nominal operating condition. We investigate the effects of such perturbations on stability properties, e.g., the extent of regions of attraction, of a particular family of autocatalytic network models. Numerical experiments demonstrate that systems that are robust with respect to perturbations in the parameter space have an easily “verifiable” (in terms of proof complexity) region of attraction properties. Motivated by the computational complexity of optimization-based formulations, we take a compositional approach and exploit a natural decomposition of the system, induced by the underlying biological structure, into a feedback interconnection of two input–output subsystems: a small subsystem with complicating nonlinearities and a large subsystem with simple dynamics. This decomposition simplifies the analysis of large pathways by assembling region of attraction certificates based on the input–output properties of the subsystems. It enables numerical as well as analytical construction of block-diagonal Lyapunov functions for a large family of autocatalytic pathways.     

A global piecewise smooth Newton method for fast large-scale model predictive control

In this paper, the strictly convex quadratic program (QP) arising in model predictive control (MPC) for constrained linear systems is reformulated as a system of piecewise affine equations. A regularized piecewise smooth Newton method with exact line search on a convex, differentiable, piecewise-quadratic merit function is proposed for the solution of the reformulated problem. The algorithm has considerable merits when applied to MPC over standard active set or interior point algorithms. Its performance is tested and compared against state-of-the-art QP solvers on a series of benchmark problems. The proposed algorithm is orders of magnitudes faster, especially for large-scale problems and long horizons. For example, for the challenging crude distillation unit model of Pannocchia, Rawlings, and Wright (2007) with 252 states, 32 inputs, and 90 outputs, the average running time of the proposed approach is 1.57 ms.     

On singular perturbations due to fast actuators in hybrid control systems

A stability result is given for hybrid control systems singularly perturbed by fast but continuous actuators. If a hybrid control system has a compact set globally asymptotically stable when the actuator dynamics are omitted, or equivalently, are infinitely fast, then the same compact set is semiglobally practically asymptotically stable in the finite speed of the actuator dynamics. This result, which generalizes classical results for differential equations, justifies using a simplified plant model that ignores fast but continuous actuator dynamics, even when using a hybrid feedback control algorithm.     

Active learning paradigms for CBIR systems based on optimum-path forest classification

This paper discusses methods for content-based image retrieval (CBIR) systems based on relevance feedback according to two active learning paradigms, named greedy and planned. In greedy methods, the system aims to return the most relevant images for a query at each iteration. In planned methods, the most informative images are returned during a few iterations and the most relevant ones are only presented afterward. In the past, we proposed a greedy approach based on optimum-path forest classification (OPF) and demonstrated its gain in effectiveness with respect to a planned method based on support-vector machines and another greedy approach based on multi-point query. In this work, we introduce a planned approach based on the OPF classifier and demonstrate its gain in effectiveness over all methods above using more image databases. In our tests, the most informative images are better obtained from images that are classified as relevant, which differs from the original definition. The results also indicate that both OPF-based methods require less user involvement (efficiency) to satisfy the user's expectation (effectiveness), and provide interactive response times.     

Gender discriminating models from facial surface normals

In this paper, we show how to use facial shape information to construct discriminating models for gender classification. We represent facial shapes using 2.5D fields of facial surface normals, and investigate three different methods to improve the gender discriminating capacity of the model constructed using the standard eigenspace method. The three methods are novel variants of principal geodesic analysis (PGA) namely (a) weighted PGA, (b) supervised weighted PGA, and (c) supervised PGA. Our starting point is to define a weight map over the facial surface that indicates the importance of different locations in discriminating gender. We show how to compute the relevant weights and how to incorporate the weights into the 2.5D model construction. We evaluate the performance of the alternative methods using facial surface normals extracted from 3D range images or recovered from brightness images. Experimental results demonstrate the effectiveness of our methods. Moreover, the classification accuracy, which is as high as 97%, demonstrates the effectiveness of using facial shape information for gender classification.