Search

In model predictive control (MPC), the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem at each sample in the control loop. The main computational effort when solving the CFTOC problem using an active-set (AS) method is often spent on computing the search directions, which in MPC corresponds to solving unconstrained finite-time optimal control (UFTOC) problems. This is commonly performed using Riccati recursions or generic sparsity exploiting algorithms. In this paper, the focus is efficient search direction computations for AS type methods. The system of equations to be solved at each AS iteration is changed only by a low-rank modification of the previous one, and exploiting this structured change is important for the performance of AS-type solvers. In this paper, theory for how to exploit these low-rank changes by modifying the Riccati factorization between AS iterations in a structured way is presented. A numerical evaluation of the proposed algorithm shows that the computation time can be significantly reduced by modifying, instead of re-computing, the Riccati factorization. This speedup can be important for AS-type solvers used for linear, nonlinear, and hybrid MPC. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of a leader that seeks to optimally influence the opinions of agents in a directed network through connecting with a limited number of the agents (“direct followers”), possibly in the presence of a fixed competing leader. The settings involving a single leader and two competing leaders are unified into a general combinatoric optimization problem, for which two heuristic approaches are developed. The first approach is based on a convex relaxation scheme, possibly in combination with the $\ell _1$ -norm regularization technique, and the second is based on a greedy selection strategy. The main technical novelties of this work are in the establishment of supermodularity of the objective function and convexity of its continuous relaxation. The greedy approach is guaranteed to have a lower bound on the approximation ratio sharper than $(1-1/e)$ , while the convex approach can benefit from efficient (customized) numerical solvers to have practically comparable solutions possibly with faster computation times. The two approaches can be combined to provide improved results. In numerical examples, the approximation ratio can be made to reach ${\text{90}\%}$ or higher depending on the number of direct followers. [ABSTRACT FROM AUTHOR]

In this paper, we present complexity certification results for a distributed augmented Lagrangian (AL) algorithm used to solve convex optimization problems involving globally coupled linear constraints. Our method relies on the accelerated distributed AL (ADAL) algorithm, which can handle the coupled linear constraints in a distributed manner based on local estimates of the AL. We show that the theoretical complexity of ADAL to reach an $\epsilon$-optimal solution both in terms of suboptimality and infeasibility is O(\frac{1}{\epsilon }) iterations. Moreover, we provide a valid upper bound for the optimal dual multiplier, which enables us to explicitly specify these complexity bounds. We also show how to choose the step-size parameter to minimize the bounds on the convergence rates. Finally, we discuss a motivating example, a model predictive control problem, involving a finite number of subsystems, which interact with each other via a general network. [ABSTRACT FROM PUBLISHER]

This paper generalizes the well-known covariance intersection algorithm for distributed estimation and information fusion of random vectors. Our focus will be on partially correlated random vectors. This is motivated by the restriction of the standard covariance intersection algorithm, which treats all random vectors with arbitrary cross correlations and the restriction of the classical Kalman filter, which requires complete knowledge of the cross correlations. We first give a result to characterize the conservatism of the standard covariance intersection algorithm. We then generalize the covariance intersection algorithm to two random vectors with a given correlation coefficient bound and show in what sense the resulting covariance bound is tight. Finally, we generalize the notion of correlation coefficient bound to multiple random vectors and provide a covariance intersection algorithm for this general case. Our results will make the already popular covariance intersection more applicable and more accurate for distributed estimation and information fusion problems. [ABSTRACT FROM PUBLISHER]

In this paper, source localization by a network of primitive binary sensors under various imperfections are studied. Detailed analysis and mathematical modeling of imperfect binary sensors are presented. Imperfections include sensor failures of two types, drifting, uncertainty, and heterogeneity in binary sensor trigger thresholds, presence of noise, and nonradial symmetry of sensing ranges. Theoretical results, including asymptotical convergence, are established, in particular in the presence of substantial outliers due to sensor failure and large noise. Efficient numerical algorithms are proposed and simulated supporting the theoretical analysis. [ABSTRACT FROM PUBLISHER]

Classical methods for estimating additive faults are based on state-space models, e.g., moving horizon estimation (MHE) and unknown input observers (UIOs). This paper contributes new direct design methods from closed-loop I/O data for systems with stable inversion, which do not require building a state-space model by first principles, nor require identifying it. Inspired by subspace identification, we use the input and output (I/O) relationship of a plant in a Vector ARX (VARX) form to parameterize least-squares (LS) problems for estimating faults. We prove that with the order of the VARX descriptions tending to infinity, the fault estimates are unbiased. Under lower relative degrees, we prove that our new methods are equivalent to system-inversion-based estimation for both LTI and LTV systems. We will show more general unbiased estimation conditions for higher relative degrees. These require that the underlying inverted system from faults to outputs is stable. Algorithms of identifying unbiased fault estimation filters from data will be developed in this paper based on single LS. Moreover, covariance of the fault estimates can also be extracted from data. [ABSTRACT FROM AUTHOR]

In this paper, we present adaptive and distributed algorithms for motion coordination of a group of m vehicles. The vehicles must service demands whose time of arrival, spatial location, and service requirement are stochastic; the objective is to minimize the average time demands spend in the system. The general problem is known as the m-vehicle Dynamic Traveling Repairman Problem (m-DTRP). The best previously known control algorithms rely on centralized task assignment and are not robust against changes in the environment. In this paper, we first devise new control policies for the 1-DTRP that: i) are provably optimal both in light-load conditions (i.e., when the arrival rate for the demands is small) and in heavy-load conditions (i.e., when the arrival rate for the demands is large), and ii) are adaptive, in particular, they are robust against changes in load conditions. Then, we show that specific partitioning policies, whereby the environment is partitioned among the vehicles and each vehicle follows a certain set of rules within its own region, are optimal in heavy-load conditions. Building upon the previous results, we finally design control policies for the m-DTRP that i) are adaptive and distributed, and ii) have strong performance guarantees in heavy-load conditions and stabilize the system in any load condition. [ABSTRACT FROM AUTHOR]

Abstract-In this paper, the problem of designing robust supervisory controllers for uncertain discrete event systems is studied. It is assumed that both the plant behavior and the design specifications can be represented by regular languages. It is also assumed that the unknown model of the uncertain plant belongs to a finite set of possibilities. To solve the problem, a modular approach based on a general recursive robust control scheme is developed. The contribution of the present paper consists in deriving a maximally permissive modular robust supervisory controller for the case of prefix.closed languages, having the advantage of linear complexity in the number of models as opposed to the exponential complexity of the worstcase scenario in the direct implementation of standard supervisors for aug. mented systems. [ABSTRACT FROM AUTHOR]

This paper concerns decentralized control of a multi-agent stochastic queueing system. The system consists of two agents, a pricing agent and a service agent. The pricing agent controls the arrival rate by dynamically setting the fee that is paid by customers who would like to receive service, while the service agent controls the rate at which customers in the system are processed. Each agent optimizes his/her own objective subject to a model which accurately specifies the component of the system that he/she is controlling but potentially mis-specifies the component that is controlled by the other agent. We are interested in optimizing the efficiency of the aggregate system when control decisions are made in this way. Decentralized agents are coordinated using transfer contracts, which define a price for occupying unit of buffer space in the system as a function of time and available capacity. Transfer contracts lead to cash transfers between agents whenever a customer enters or departs, and serve to modify each of their incentives. We characterize the contract that maximizes the efficiency of the aggregate system under decentralized control, and show that it achieves the efficiency of a centralized agent who jointly optimizes over pricing and service policies with an accurate model of the integrated system. We also show that optimal centralized efficiency is robust to mis-specification by each agent of the dynamics induced by the other in his/her model. An iterative decentralized algorithm for constructing the optimal contract and a proof of convergence is also presented. [ABSTRACT FROM AUTHOR]

We present a nonsmooth output feedback framework for local and/or global stabilization of a class of nonlinear systems that are not smoothly stabilizable nor uniformly observable. A systematic design method is presented for the construction of stabilizing, dynamic output compensators that are nonsmooth but Hölder continuous. A new ingredient of the proposed output feedback control scheme is the introduction of a recursive observer design algorithm, making it possible to construct a reduced-order observer step-by-step, in a naturally augmented manner. Such a nonsmooth design leads to a number of new results on output feedback stabilization of nonlinear systems. One of them is the global stabilizability of a chain of odd power integrators by Hölder continuous output feedback. The other one is the local stabilization using nonsmooth output feedback for a wide class of nonlinear systems in the Hessenberg form studied in a previous paper, where global stabilizability by nonsmooth state feedback was already proved to be possible. [ABSTRACT FROM AUTHOR]

This paper presents a method for the identification of multiple-input-multiple-output (MIMO) Hammerstein systems for the goal of prediction. The method extends the numerical algorithms for subspace state space system identification (N4SID), mainly by rewriting the oblique projection in the N4SID algorithm as a set of componentwise least squares support vector machines (LS-SVMs) regression problems. The linear model and static none linearities follow from a low-rank approximation of a matrix obtained from this regression problem. [ABSTRACT FROM AUTHOR]

Abstracts are presented for papers published in the journal including for "Attack Detection and Identification in Cyber-Physical Systems," by F. Pasqualetti, F. Dörfler and F. Bullo, "Nonuniform Coverage Control On The Line," by N. E. Leonard and A. Olshevsky, and "Coordinated One-Step Optimal Distributed State Prediction For A Networked Dynamical System," by T. Zhou.

The representation of the uncertainty of a stochastic state by a Gaussian mixture is well-suited for nonlinear tracking problems in high dimensional data-starved environments such as space surveillance. In this paper, the framework for a Gaussian sum filter is developed emphasizing how the uncertainty can be propagated accurately over extended time periods in the absence of measurement updates. To achieve this objective, a series of metrics constructed from tensors of higher-order cumulants are proposed which assess the consistency of the uncertainty and provide a tool for implementing an adaptive Gaussian sum filter. Emphasis is also placed on the algorithm's potential for parallelization which is complemented by the use of higher-order unscented filters based on efficient multidimensional Gauss-Hermite quadrature schemes. The effectiveness of the proposed Gaussian sum filter is illustrated in a case study in space surveillance involving the tracking of an object in a six-dimensional state space. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present a framework for the design of sliding-mode based controllers for multi-input affine nonlinear systems. In this framework the control effort goes to zero as the state approaches the sliding surface, a key feature for practical implementation. The sliding surface is a submanifold with codimension equal to the dimension of the involutive distribution ɡ generated by the controlled vector fields rather than the dimension of their linear span. We also allow nonzero vectors in ɡ to be tangent to the sliding surface, the singular case in sliding-mode control. [ABSTRACT FROM AUTHOR]

It is well known that a nonlinear optimal control requires the solution to a two-point boundary value problem or to a nonlinear partial differential equation and that such a solution can only be obtained off line by numerical iteration. In this paper, a new and near-optimal control design framework is proposed for controlling any nonholonomic system in the chained form. The proposed design is based upon thorough study of uniform complete controllability of the corresponding linear time varying nominal System. It is shown that, no matter whether the first component u1d(t) of reference input vector is uniformly nonvanishing or simply nonconvergent to zero or vanishing or identically zero, uniform complete controllability of the (nominal) system can be recovered by employing the proposed time-folding/unfolding technique. Upon establishing the common property of uniform complete controllability, the proposed framework can be used to design both trajectory tracking control and regulation control in a systematic and unified manner. Using duality, uniform complete observability can also be established, a closed-form and exponentially convergent observer can be synthesized, and the controls designed using the proposed framework can be either state-feedback or output-feedback. The tracking controls are designed using the same three-step process. That is, design of the proposed controls starts with optimal control solutions to two linear nominal subsystems, one time-invariant and the other time varying. The two solutions combined together render a globally stabilizing suboptimal control for the overall system. Then, the optimality condition is invoked to determine the distance between the suboptimal control and the optimal one. Consequently, an improved control can be obtained by introducing a nonlinear additive control term in such a way that the distance aforementioned is minimized as much as possible in closed form. An example is used to show that regulation control can be designed similarly. All the controls designed are in simple closed forms and hence real-time implementable, they are time varying and smooth, globally and exponentially/asymptotically stabilizing, and they are near optimal since their closeness to the optimal control (attainable only offline) can be measured, monitored on line, and has been minimized. [ABSTRACT FROM AUTHOR]

Most verification techniques for highly populated discrete systems suffer from the state explosion problem. The ‘fluidification’ of discrete systems is a classical relaxation technique that aims to avoid the state explosion problem. Continuous Petri nets are the result of fluidifying traditional discrete Petri nets. In continuous Petri nets the firing of a transition is not constrained to the naturals but to the non-negative reals. Unfortunately, some important properties, as liveness, may not be preserved when the discrete net model is fluidified. Therefore, a thorough study of the properties of continuous Petri nets is required. This paper focuses on the study of deadlock-freeness in the framework of mono-T-semiflow continuous Petri nets, i.e., conservative nets with a single repetitive sequence (T-semiflow). The study is developed both on untimed and timed systems. Topological necessary conditions are extracted for this property. Moreover, a bridge relating deadlock-freeness conditions for untimed and timed systems is established. [ABSTRACT FROM AUTHOR]

In this paper, we present a new way to control linear stochastic systems. The method is based on statistical bootstrap techniques. The optimal future control signal is derived in such a way that unknown noise distribution and uncertainties in parameter estimates are taken into account This is achieved by re-sampling from existing data when calculating statistical distributions of future process values. The bootstrap algorithm takes care of arbitrary loss functions and unknown noise distribution even for small estimation sets. The efficient way of utilizing data implies that the method is also well suited for slowly time-varying stochastic systems. [ABSTRACT FROM AUTHOR]

We present a computational framework for automatic synthesis of a feedback control strategy for a discrete-time piecewise affine (PWA) system from a specification given as a linear temporal logic (LTL) formula over an arbitrary set of linear predicates in the system's state variables. Our approach consists of two main steps. First, by defining appropriate partitions for its state and input spaces, we construct a finite abstraction of the PWA system in the form of a control transition system. Second, by leveraging ideas and techniques from LTL model checking and Rabin games, we develop an algorithm to generate a control strategy for the finite abstraction. While provably correct and robust to state measurements and small perturbations in the applied inputs, the overall procedure is conservative and expensive. The proposed algorithms have been implemented as a software package and made available for download. Illustrative examples are included. [ABSTRACT FROM AUTHOR]

We consider projected equations for approximate solution of high-dimensional fixed point problems within low-dimensional subspaces. We introduce an analytical framework based on an equivalence with variational inequalities, and algorithms that may be implemented with low-dimensional simulation. These algorithms originated in approximate dynamic programming (DP), where they are collectively known as temporal difference (TD) methods. Even when specialized to DP, our methods include extensions/new versions of TD methods, which offer special implementation advantages and reduced overhead over the standard LSTD and LSPE methods, and can deal with near singularity in the associated matrix inversion. We develop deterministic iterative methods and their simulation-based versions, and we discuss a sharp qualitative distinction between them: the performance of the former is greatly affected by direction and feature scaling, yet the latter have the same asymptotic convergence rate regardless of scaling, because of their common simulation-induced performance bottleneck. [ABSTRACT FROM AUTHOR]

We formulate the Lebesgue-sampling-based optimal control problem. We show that the problem can be solved by the time aggregation approach in Markov decision processes (MDP) theory. Policy-iteration-based and reinforcement-learning-based methods are developed for the optimal policies. Both analytical solutions and sample-path-based algorithms are given. Compared to the periodic-sampling scheme, the Lebesgue sampling scheme improves system performance. [ABSTRACT FROM AUTHOR]

The purpose of this note is to point out that the result in the above paper is incomplete, and to give a complete and improved result,. [ABSTRACT FROM AUTHOR]

Analyzes the output error convergence of a nonlinear stochastic gradient algorithm based on the use of a Wiener model. Details on the estimate of the parameters of a linear finite impulse response (FIR) model; Interpretation of the algorithm as a normalised least mean square; Information on global output error convergence.

We consider the class of o-minimally definable hybrid automata with a bounded discrete-transition horizon. We show that for every hybrid automata in this class, there exists a bisimulation of finite index, and that the bisimulation quotient can be effectively constructed when the underlying o-minimal theory is decidable. More importantly, we give natural specifications for hybrid automata which ensure the boundedness of discrete-transition horizons. In addition, we show that these specifications are reasonably tight with respect to the decidability of the models and that they can model modern day real-time and embedded systems. As a result, the analysis of several problems for these systems admit effective algorithms. We provide a representative example of a hybrid automaton in this class. Unlike previously examined subclasses of o-minimally defined hybrid automata with decidable verification properties and extended o-minimal hybrid automata, we do not impose re-initialization of the continuous variables in a memoryless fashion when a discrete transition is taken. Our class of hybrid systems has both rich continuous dynamics and strong discrete-continuous coupling, showing that it is not necessary to either simplify the continuous dynamics or restrict the discrete dynamics to achieve decidability. [ABSTRACT FROM AUTHOR]

We study distributed consensus problems of multi-agent systems on directed networks and subject to quantized information flow. For the communication among component agents, particular attention is given to the gossip type, which models their asynchronous behavior; for quantization effect, each agent's state is abstracted to be an integer. The central question investigated is how to design distributed algorithms and what connectivity of networks that together lead to consensus. This investigation is carried out for both general consensus and average consensus; for each case, a class of algorithms is proposed, under which a necessary and sufficient graphical condition is derived to guarantee the corresponding consensus. In particular, the obtained graphical condition ensuring average consensus is weaker than those in the literature for either real-valued or quantized states, in the sense that it does not require symmetric or balanced network topologies. [ABSTRACT FROM AUTHOR]

This note introduces a model of a generic team formation problem. We derive general conditions under which a group of scattered decision-making agents converge to a particular distribution. The desired distribution is achieved when the agents divide themselves into a fixed number of sub-groups while consenting on “gains” which are associated to every subgroup. The model allows us to quantify the impact of limited sensing, motion, and communication capabilities on the rate at which the distribution is achieved. Finally, we show how this theory is useful in solving a cooperative surveillance problem. [ABSTRACT FROM AUTHOR]

We derive here an algorithm for a complete square root implementation of the modified Bryson–Frazier (MBF) smoother. The MBF algorithm computes the smoothed covariance as the difference of two symmetric matrices. Numerical errors in this differencing can result in the covariance matrix not being positive semi-definite. Earlier algorithms implemented the computation of intermediate quantities in square root form but still computed the smoothed covariance as the difference of two matrices. We show how to compute the square root of the smoothed covariance by solving an equation in the form CC^T=AA^T-BB^T using QR decomposition with hyperbolic Householder transformations. [ABSTRACT FROM AUTHOR]

This note presents a novel model predictive control (MPC) strategy for input-saturated nonlinear systems having a polynomial structure. The results here proposed are a significant generalization w.r.t. similar existing algorithms which are tailored only for linearized or multi-model plant descriptions. A first key aim is to present sum-of-squares (SOS) conditions under which off-line one-step controllable sets for nonlinear polynomial systems can be derived. A second relevant contribution is to describe an on-line MPC strategy that leads to less conservative performance w.r.t. most existing methods based on global linearization approaches. An illustrative example is finally provided in order to show the effectiveness of the proposed SOS-based MPC algorithm. [ABSTRACT FROM AUTHOR]

This note proposes a novel algorithm for robust partial eigenvalue assignment (RPEVA) problem for a cubic matrix pencil arising from modeling of vibrating systems with aerodynamic effects. The RPEVA problem for a cubic pencil is the one of choosing suitable feedback matrices to reassign a few (say κ < 3n) unwanted eigenvalues while leaving the remaining large number (3n — κ) of them unchanged, in such a way that the the eigenvalues of the closed-loop matrix are as insensitive as possible to small perturbation of the data. The latter amounts to minimizing the condition number of the closed-loop eigenvector matrix. The problem is solved directly in the cubic matrix polynomial setting without making any transformation to a standard first-order state-space system. This allows us to take advantage of the exploitable structures such as the sparsity, definiteness, bandness, etc., very often offered by large practical problems. The major computational requirements are: i) solution of a small Sylvester equation, ii) QR factorizations, and iii) solution of a standard least squares problem. The least-squares problem result from matrix rank-two update techniques used in the algorithm for reassigning complex eigenvalues. The practical effectiveness of the method is demonstrated by implementational results on simulated data provided by the Boeing company. [ABSTRACT FROM AUTHOR]

Here we consider the problem of providing near optimal performance (in this context, ‘near optimal performance’ means performance as close to optimality as desired) for a large set of possible models. We adopt the linear quadratic regulator (LQR) framework in the single-input-single-output (SISO) setting, and prove that given a compact set of controllable and observable plant models of a fixed order, we can construct a single linear periodic controller (LPC) which provides near optimal LQR performance. Since the controller is linear, it automatically has the nice feature that there is some degree of tolerance to unmodeled dynamics. The approach is also shown to work if the goal is the more modest one of pole placement, and it can be simplified if there is additional structure to the plant model. [ABSTRACT FROM AUTHOR]

We investigate a network routing problem where a probabilistic local broadcast transmission model is used to determine routing. We discuss this model's key features, and note that the local broadcast transmission model can be viewed as soft handoff for an ad-hoc network. We present results showing that an index policy is optimal for the routing problem. We extend the network model to allow for control of transmission type, and prove that the index nature of the optimal routing policy remains unchanged. We present three distributed algorithms which compute an optimal routing policy, discuss their convergence properties, and demonstrate their performance through simulation. [ABSTRACT FROM AUTHOR]

In spite of their potential to reduce computational complexity, the use of probabilistic methods in robust control has been mostly limited to parametric uncertainty, since the problem of sampling causal bounded operators is largely open. In this note,we take steps toward removing this limitation by proposing a computationally efficient algorithm aimed at uniformly sampling suitably chosen subsets of H∞. As we show, in note, samples taken from these sets can be used to carry out model (in)validation and robust performance analysis in the presence of structured dynamic linear time-invariant uncertainty, problems known to be NP-hard in the number of uncertainty blocks. [ABSTRACT FROM AUTHOR]

Provides information on the presentation of a robust adaptive state-feedback control algorithm. Detailed information on the algorithm; Conclusions reached.

Presents a study which developed an algorithm to solve algebraic Riccati equations through the Hamiltonian Schur form. Information on the development of the algorithm; Comparison of the convergence performance of the algorithm with the Hamiltonian-Jacobi algorithm of Byers [12]; Details on the numerical experiments which were carried out.

Focuses on the problem structure of the mixed problem to develop a polynomial time algorithm that will give good answer. Notation and preliminaries of the problem; Lower bound for the mixed case; Characterization of a maximum point; Conclusions.

Provides information on the modified adaptive output error algorithm, proving that the solution is biased for more practical types of disturbance noise, including the white noise case. Information on the presence of a disturbance term; Details on the standard estimated output; Examples of the algorithm; Conclusion reached on the investigation.