Search

This paper proposes a distributed model predictive control (MPC) approach for a family of discrete-time linear systems with local (uncoupled) and global (coupled) constraints. The proposed approach is based on the dual problem of an overall MPC optimization problem involving all systems, which is then solved distributively using a modified distributed Nesterov-accelerated-gradient algorithm. To further reduce the computational requirement, this approach allows for early termination of the distributed gradient algorithm. This is made possible via a consensus algorithm that determines the satisfaction of the termination condition and by appropriate tightening of the coupled constraints. Under reasonable assumptions, the approach is able to produce a suboptimal solution as long as the network of the systems is connected while ensuring recursive feasibility and exponential stability of the closed-loop system. The performance of the proposed approach is demonstrated by a numerical example. [ABSTRACT FROM AUTHOR]

The coverage control problem of a circle by a mobile sensor network affected by bounded measurement errors is addressed in this paper. The mobile sensors are assumed to have different maximum velocities. Our main objective is to study the effect of measurement errors on the coverage cost function, which is defined as the largest time for the sensor network to arrive at any point on the circle. Coverage control laws with input constraints are developed based on the noisy position measurements among sensors, under which the mobile sensor network converges to a neighborhood of the optimal configuration. Furthermore, the conditions for the sensors to preserve their spatial order on the circle are derived in order to avoid collision among sensors. An upper bound on the limit of the coverage cost function as time goes to infinity is also given. [ABSTRACT FROM AUTHOR]

Several optimization-based control design techniques can be cast in the form of parametric optimization problems. The multiparametric quadratic programming (mpQP) represents a popular class often related to the control of constrained linear systems. The complete solution to mpQP takes the form of explicit feedback functions with a piecewise affine structure, valid in polyhedral partitions of the feasible parameter space known as critical regions. The recently proposed combinatorial approach for solving mpQP has shown better efficiency than geometric approaches in finding the complete solution to problems with high dimensions of the parameter vectors. The drawback of this method, on the other hand, is that it tends to become very slow as the number of constraints increases in the problem. This paper presents an alternative method for enumerating all optimal active sets in an mpQP based on theoretical properties of adjacent critical regions and their corresponding optimal active sets. Consequently, it results in excluding a noticeable number of feasible but not optimal candidate active sets from investigation. Therefore, the number of linear programs that should be solved decreases noticeably and the algorithm becomes faster. Simulation results confirm the reliability of the suggested method in finding the complete solution to the mpQPs while decreasing the computational time compared favorably with the best alternative approaches. [ABSTRACT FROM AUTHOR]

For a system matrix $M$ , this paper explores the smallest (Frobenius) norm additive structured perturbation $\delta M$ for which a system property $\mathcal {P}$ (e.g., controllability, observability, stability, etc.) fails to hold, i.e., $\delta M$ is the structured perturbation with smallest Frobenius norm such that there exists a property matrix $R\in \mathcal {P}$ for which $M{-}\delta M{-}R$ drops rank. The Frobenius norm is used because of its direct dependence on the magnitude of each entry in the perturbation matrix. Necessary conditions on a locally minimum norm structured rank-reducing perturbation $\delta M$ and associated property matrix $R$ are set forth and proven. An iterative algorithm is also set forth that computes a locally minimum norm structured perturbation and associated property matrix satisfying the necessary conditions. Algorithm convergence is proven using a discrete Lyapunov function. [ABSTRACT FROM AUTHOR]

In this paper, we propose a distance-based formation control strategy for a group of mobile agents to achieve almost global convergence to a target formation shape provided that the formation is represented by a complete graph, and each agent is governed by a single-integrator model. The fundamental idea of achieving almost global convergence is to use a virtual formation of which the dimension is augmented with some virtual coordinates. We define a cost function associated with the virtual formation and apply the gradient-descent algorithm to the cost function so that the function has a global minimum at the target formation shape. We show that all agents finally achieve the target formation shape for almost all initial conditions under the proposed control law. [ABSTRACT FROM AUTHOR]

Consider a connected network of agents endowed with local cost functions representing private objectives. Agents seek to find an agreement on some minimizer of the aggregate cost, by means of repeated communications between neighbors. Consensus on the average over the network, usually addressed by gossip algorithms, is a special instance of this problem, corresponding to quadratic private objectives. Consensus on the median, or more generally, consensus on a given quantile, is also a special instance of this problem. In this paper we show that optimizing the aggregate cost function regularized by a total variation (TV) term has appealing properties. First, it can be done very naturally in a distributed way, yielding algorithms that are efficient on numerical simulations. Secondly, the optimum for the regularized cost is shown to be also the optimum for the initial aggregate cost function under assumptions that are simple to state. Finally, these algorithms are robust to unreliable agents that keep injecting some false value in the network. This is remarkable enough, and is not the case, for instance, of gossip algorithms that are entirely ruled by unreliable agents as detailed in the paper. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of distributed control for network systems aiming to achieve optimal steady-state performance. Motivated by recent research on reengineering cyber-physical systems, such as power systems and the Internet, we propose a two-step control retrofit procedure. First, we reformulate the dynamical system as an optimization algorithm to solve a certain optimization problem. Second, we combine a predefined steady-state optimization problem and the reformulated problem to systematically (re)design the control. As a result, the system automatically tracks the optimal solution of the predefined steady-state optimization problem and the control scheme can be implemented in a distributed and closed-loop manner. In order to investigate how general this framework is, we establish necessary and sufficient conditions under which a linear dynamical system can be viewed as an optimization algorithm. These conditions are characterized using properties of system matrices and related linear matrix inequalities. A practical example of frequency control in power systems shows the effectiveness of the proposed framework. [ABSTRACT FROM PUBLISHER]

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]

We consider the problem of designing static feedback gains subject to a priori structural constraints, which is a nonconvex problem in general. Previous work has focused on either characterizing special structures that result into convex formulations, or employing certain techniques to allow convex relaxations of the original problem. In this paper, by exploiting the underlying sparsity properties of the problem, and using chordal decomposition, we propose a scalable algorithm to obtain structured feedback gains to stabilize a large-scale system. We first extend the chordal decomposition theorem for positive semidefinite matrices to the case of matrices with block-chordal sparsity. Then, a block-diagonal Lyapunov matrix assumption is used to convert the design of structured feedback gains into a convex problem, which inherits the sparsity pattern of the original problem. Combining these two results, we propose a sequential design method to obtain structured feedback gains clique-by-clique over a clique tree of the block-chordal matrix, which only needs local information and helps ensure privacy of model data. Several illustrative examples demonstrate the efficiency and scalability of the proposed sequential design method. [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]

In this paper, we address the optimal control problem for Boolean control networks (BCNs). We first consider the problem of finding the input sequences that minimize a given cost function over a finite time horizon. The problem solution is obtained by means of a recursive algorithm that represents the analogue for BCNs of the difference Riccati equation for linear systems. We prove that a significant number of optimal control problems for BCNs can be easily reframed into the present setup. In particular, the cost function can be adjusted so as to include penalties on the switchings, provided that we augment the size of the BCN state variable. In the second part of the paper, we address the infinite horizon optimal control problem and we provide necessary and sufficient conditions for the problem solvability. The solution is obtained as the limit of the solution over the finite horizon [0,T], and it is always achieved in a finite number of steps. Finally, the average cost problem over the infinite horizon, investigated in “Optimal control of logical control networks” (Y. Zhao , IEEE Trans. Autom. Control, vol 56, no. 8, pp. 1766–1776, Aug. 2011), is addressed by making use of the results obtained in the previous sections. [ABSTRACT FROM AUTHOR]

This paper is an attempt to study the first passage optimality criterion for continuous-time Markov decision processes with state-dependent discount factors and history-dependent policies. The state space is denumerable, the action space is a Borel space, and the transition and reward rates are unbounded. Under suitable conditions, we show the existence of a deterministic stationary optimal policy, establish the Bellman (optimality) equation, to which the value function is the unique solution, and give the value and policy iteration algorithms for solving (at least approximating) the value function and an optimal policy. Furthermore, we give examples about reliability and controlled birth processes with killing to illustrate the potential applications of the results obtained here, and also to show the difference between the main results in this paper and those in the previous literature. [ABSTRACT FROM PUBLISHER]

There are only a few learning algorithms applicable to stochastic dynamic teams and games which generalize Markov decision processes to decentralized stochastic control problems involving possibly self-interested decision makers. Learning in games is generally difficult because of the non-stationary environment in which each decision maker aims to learn its optimal decisions with minimal information in the presence of the other decision makers who are also learning. In stochastic dynamic games, learning is more challenging because, while learning, the decision makers alter the state of the system and hence the future cost. In this paper, we present decentralized Q-learning algorithms for stochastic games, and study their convergence for the weakly acyclic case which includes team problems as an important special case. The algorithms are decentralized in that each decision maker has access only to its own decisions and cost realizations as well as the state transitions; in particular, each decision maker is completely oblivious to the presence of the other decision makers. We show that these algorithms converge to equilibrium policies almost surely in large classes of stochastic games. [ABSTRACT FROM AUTHOR]

In this paper, a time-varying distributed convex optimization problem is studied for continuous-time multi-agent systems. The objective is to minimize the sum of local time-varying cost functions, each of which is known to only an individual agent, through local interaction. Here, the optimal point is time varying and creates an optimal trajectory. Control algorithms are designed for the cases of single-integrator and double-integrator dynamics. In both cases, a centralized approach is first introduced to solve the optimization problem. Then, this problem is solved in a distributed manner and a discontinuous algorithm based on the signum function is proposed in each case. In the case of single-integrator (respectively, double-integrator) dynamics, each agent relies only on its own position and the relative positions (respectively, positions and velocities) between itself and its neighbors. A gain adaption scheme is introduced in both algorithms to eliminate certain global information requirement. To relax the restricted assumption imposed on feasible cost functions, an estimator based algorithm using the signum function is proposed, where each agent uses dynamic average tracking as a tool to estimate the centralized control input. As a tradeoff, the estimator-based algorithm necessitates communication between neighbors. Then, in the case of double-integrator dynamics, the proposed algorithms are further extended. Two continuous algorithms based on, respectively, a time-varying and a fixed boundary layer are proposed as continuous approximations of the signum function. To account for interagent collision for physical agents, a distributed convex optimization problem with swarm tracking behavior is introduced for both single-integrator and double-integrator dynamics. It is shown that the center of the agents tracks the optimal trajectory, the connectivity of the agents is maintained, and interagent collision is avoided. [ABSTRACT FROM AUTHOR]

Diagnosability is an important property that determines at the design stage how accurate any diagnosis algorithm can be on a partially observable system and thus has significant economic impact on the improvement of performance and reliability of complex systems. Very recently distributed approaches for diagnosability began to be investigated since centralized approaches are not realistic for large systems due to the combinatorial explosion of the search space. In this paper, we propose a new optimized algorithm for pattern diagnosability analysis of distributed systems with modular structure, where we obtain the original pattern diagnosability information from the relative components before abstracting the sufficient and necessary information to be propagated to other connected components. Then, the diagnosability decision can be made after global consistency checking at the proper level of the subsystem involved. Our experimental results and complexity analysis illustrate the correctness and efficiency of our approach both in a practical and theoretical way. Finally, we distinguish our work by presenting related works before the conclusion. [ABSTRACT FROM AUTHOR]

In this paper, we address robust static anti-windup compensator design and performance analysis for saturated linear closed loops in the presence of nonlinear probabilistic parameter uncertainties via randomized techniques. The proposed static anti-windup analysis and robust performance synthesis correspond to several optimization goals, ranging from minimization of the nonlinear input/output gain to maximization of the stability region or maximization of the domain of attraction. We also introduce a novel paradigm accounting for uncertainties in the energy of the disturbance inputs. Due to the special structure of linear static anti-windup design, wherein the design variables are decoupled from the Lyapunov certificates, we introduce a significant extension, called scenario with certificates (SwC), of the so-called scenario approach for uncertain optimization problems. This extension is of independent interest for similar robust synthesis problems involving parameter-dependent Lyapunov functions. We demonstrate that the scenario with certificates robust design formulation is appealing because it provides a way to implicitly design the parameter-dependent Lyapunov functions and to remove restrictive assumptions about convexity with respect to the uncertain parameters. Subsequently, to reduce the computational cost, we present a sequential randomized algorithm for iteratively solving this problem. The obtained results are illustrated by numerical examples. [ABSTRACT FROM PUBLISHER]

Average consensus is a widely used algorithm for distributed computing and control, where all the agents in the network constantly communicate and update their states in order to achieve an agreement. This approach could result in an undesirable disclosure of information on the initial state of an agent to the other agents. In this paper, we propose a privacy preserving average consensus algorithm to guarantee the privacy of the initial state and asymptotic consensus on the exact average of the initial values, by adding and subtracting random noises to the consensus process. We characterize the mean square convergence rate of our consensus algorithm and derive the covariance matrix of the maximum likelihood estimate on the initial state. Moreover, we prove that our proposed algorithm is optimal in the sense that it does not disclose any information more than necessary to achieve the average consensus. A numerical example is provided to illustrate the effectiveness of the proposed design. [ABSTRACT FROM PUBLISHER]

Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods. [ABSTRACT FROM PUBLISHER]

The PageRank algorithm employed at Google assigns a measure of importance to each web page for rankings in search results. In our recent papers, we have proposed a distributed randomized approach for this algorithm, where web pages are treated as agents computing their own PageRank by communicating with linked pages. This paper builds upon this approach to reduce the computation and communication loads for the algorithms. In particular, we develop a method to systematically aggregate the web pages into groups by exploiting the sparsity inherent in the web. For each group, an aggregated PageRank value is computed, which can then be distributed among the group members. We provide a distributed update scheme for the aggregated PageRank along with an analysis on its convergence properties. The method is especially motivated by results on singular perturbation techniques for large-scale Markov chains and multi-agent consensus. A numerical example is provided to illustrate the level of reduction in computation while keeping the error in rankings small. [ABSTRACT FROM AUTHOR]

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]

This paper addresses the problem of robust identification of a class of discrete-time affine hybrid systems, switched affine models, in a set membership framework. Given a finite collection of noisy input/output data and some minimal a priori information about the set of admissible plants, the objective is to identify a suitable set of affine models along with a switching sequence that can explain the available experimental information, while minimizing either the number of switches or subsystems. For the case where it is desired to minimize the number of switches, the key idea of the paper is to reduce this problem to a sparsification form, where the goal is to maximize sparsity of a suitably constructed vector sequence. Our main result shows that in the case of \ell \infty bounded noise, this sparsification problem can be exactly solved via convex optimization. In the general case where the noise is only known to belong to a convex set \cal N, the problem is generically NP-hard. However, as we show in the paper, efficient convex relaxations can be obtained by exploiting recent results on sparse signal recovery. Similarly, we present both a sparsification formulation and a convex relaxation for the (known to be NP hard) case where it is desired to minimize the number of subsystems. These results are illustrated using two non-trivial problems arising in computer vision applications: video-shot and dynamic texture segmentation. [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]

It is known that a stochastic approximation (SA) analogue of the deterministic Newton-Raphson algorithm provides an asymptotically optimal or near-optimal form of stochastic search. However, directly determining the required Jacobian matrix (or Hessian matrix for optimization) has often been difficult or impossible in practice. This paper presents a general adaptive SA algorithm that is based on a simple method for estimating the Jacobian matrix while concurrently estimating the primary parameters of interest. Relative to prior methods for adaptively estimating the Jacobian matrix, the paper introduces two enhancements that generally improve the quality of the estimates for underlying Jacobian (Hessian) matrices, thereby improving the quality of the estimates for the primary parameters of interest. The first enhancement rests on a feedback process that uses previous Jacobian estimates to reduce the error in the current estimate. The second enhancement is based on an optimal weighting of per-iteration Jacobian estimates. From the use of simultaneous perturbations, the algorithm requires only a small number of loss function or gradient measurements per iteration-independent of the problem dimension-to adaptively estimate the Jacobian matrix and parameters of primary interest. [ABSTRACT FROM AUTHOR]

This paper presents Markov chain Monte Carlo data association (MCMCDA) for solving data association problems arising in multi-target tracking in a cluttered environment. When the number of targets is fixed, the single-scan version of MCMCDA approximates joint probabilistic data association (JPDA). Although the exact computation of association probabilities in JPDA is NP-hard, we prove that the single-scan MCMCDA algorithm provides a fully polynomial randomized approximation scheme for JPDA. For general multi-target tracking problems, in which unknown numbers of targets appear and disappear at random times, we present a multi-scan MCMCDA algorithm that approximates the optimal Bayesian filter. We also present extensive simulation studies supporting theoretical results in this paper. Our simulation results also show that MCMCDA outperforms multiple hypothesis tracking (MHT) by a significant margin in terms of accuracy and efficiency under extreme conditions, such as a large number of targets in a dense environment, low detection probabilities, and high false alarm rates. [ABSTRACT FROM AUTHOR]

All agents being informed and the virtual leader traveling at a constant velocity are the two critical assumptions seen in the recent literature on flocking in multi-agent systems. Under these assumptions, Olfati-Saber in a recent IEEE TRANSACTIONS ON AUTOMATIC CONTROL paper proposed a flocking algorithm which by incorporating a navigational feedback enables a group of agents to track a virtual leader. This paper revisits the problem of multi-agent flocking in the absence of the above two assumptions. We first show that, even when only a fraction of agents are informed, the Olfati-Saber flocking algorithm still enables all the informed agents to move with the desired constant velocity, and an uninformed agent to also move with the same desired velocity if it can be influenced by the informed agents from time to time during the evolution. Numerical simulation demonstrates that a very small group of the informed agents can cause most of the agents to move with the desired velocity and the larger the informed group is the bigger portion of agents will move with the desired velocity. In the situation where the virtual leader travels with a varying velocity, we propose modification to the Olfati-Saber algorithm and show that the resulting algorithm enables the asymptotic tracking of the virtual leader. That is, the position and velocity of the center of mass of all agents will converge exponentially to those of the virtual leader. The convergent rate is also given. [ABSTRACT FROM AUTHOR]

This paper is concerned with the identification of static nonlinear components in a complex interconnected system. These nonlinear components are treated nonparametrically, in the sense that no natural parameterization is assumed to be available. A unified framework based on linear fractional transformations for exploring these identification problems is developed. Two key assumptions are made: the linear components of the interconnection are known, and the inputs to all the nonlinear components are available. Under these assumptions, a novel identification algorithm is offered. This algorithm estimates the nonlinear components by minimizing a quadratic cost function. A critical component of this cost function is the inclusion of a dispersion function that captures the requirement that the estimated nonlinearities be static. It is shown that the estimated nonlinearities converge asymptotically to their "true" values under certain identifiability and persistence of excitation conditions. Computable tests for identifiability and sufficient conditions for persistence of excitation are offered. The results in this paper strongly suggest that the most tractable identification problems for nonlinear interconnected systems are those where the inputs to all the nonlinear blocks are measured. [ABSTRACT FROM AUTHOR]

Abstract-In this paper, we propose a general methodology for designing fixed order controllers for single-input single-output plants. The controller parameters are classified into two classes: randomized and deterministically designed. For the first class, we study randomized algorithms. In particular, we present two low-complexity algorithms based on the Chernoff bound and on a related bound (often called "log-over-log" bound) which is generally used for optimization problems. Secondly, for the deterministically designed parameters, we reformulate the original problem as a set of linear equations. Then, we develop a technique which efficiently solves it using a combination of matrix inversions and sensitivity methods. A detailed complexity analysis of this technique is carried on, showing its superiority (from the computational point of view) to existing algorithms based on linear programming. In the second part of the paper, these results are extended to H∞ performance. One of the contributions is to prove that the deterministically designed parameters enjoy a special convex characterization. This characterization is then exploited in order to design fixed order controllers efficiently. We then show further extensions of these methods for stabilization of interval plants. In particular, we derive a simple one-parameter formula for computing the so-called critical frequencies which are required by the algorithms. [ABSTRACT FROM AUTHOR]

The paper studies asynchronous consensus problems of continuous-time multi-agent systems with discontinuous information transmission. The proposed consensus control strategy is implemented based on the state information of each agent's neighbors at some discrete times. The asynchrony means that each agent's update times, at which the agent adjusts its dynamics, are independent of others'. Furthermore, it is assumed that the communication topology among agents is time-dependent and the information transmission is with bounded time-varying delays. If the union of the communication topology across any time interval with some given length contains a spanning tree, the consensus problem is shown to be solvable. The analysis tool developed in this paper is based on nonnegative matrix theory and graph theory. The main contribution of this paper is to provide a valid distributed consensus algorithm that overcomes the difficulties caused by unreliable communication channels, such as intermittent information transmission, switching communication topology, and time-varying communication delays, and therefore has its obvious practical applications. Simulation examples are provided to demonstrate the effectiveness of the theoretical results. [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 presents a framework for studying the centralized optimal multi-agent coordination problem under tree formation constraints. The geodesic equations characterizing the optimal coordinated motions are derived in a suitably chosen coordinate system for general tree formation constraints. The solutions to these equations, however, may fail to be optimal once extended beyond certain points called the conjugate points due to the failure of the second-order optimality condition. For the particular class of star formations, two methods for computing the conjugate points along a natural candidate solution are introduced. Using these methods, we derive analytically the conjugate points, as well as the better solutions once the candidate solution is extended beyond its first conjugate point. The optimal centralized coordinated motions derived in this paper will yield a performance lower bound for those generated by decentralized algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new approach to the theory of finite multichain Markov decision processes (MDPs) with different performance optimization criteria. We first propose the concept of nth-order bias; then, using the average reward and bias difference formulas derived in this paper, we develop an optimization theory for finite MDPs that covers a complete spectrum from average optimality, bias optimality, to all high-order bias optimality, in a unified way. The approach is simple, direct, natural, and intuitive; it depends neither on Laurent series expansion nor on discounted MDPs. We also propose one-phase policy iteration algorithms for bias and high-order bias optimal policies, which are more efficient than the two-phase algorithms in the literature. Furthermore, we derive high-order bias optimality equations. This research is a part of our effort in developing sensitivity-based learning and optimization theory. [ABSTRACT FROM AUTHOR]

This paper addresses the design of gradient-based search algorithms for multivariable system estimation. In particular, the paper here considers so-called "full parametrization" approaches, and establishes that the recently developed "data-driven local coordinate" methods can be seen as a special case within a broader class of techniques that are designed to deal with rank-deficient Jacobians. This informs the design of a new algorithm that, via a strategy of dynamic Jacobian rank determination, is illustrated to offer enhanced performance. [ABSTRACT FROM AUTHOR]

By using a delay line as a signal generator, we design a simple robust controller for the approximate regulation (i.e., approximate asymptotic tracking and rejection) of almost periodic signals for linear systems. As opposed to the related existing results, our controller design does not require online parameter tuning. Besides the usual assumptions about stabilizability, detectability, and nonexistence of transmission zeros for the plant, the controller design algorithm of this paper only requires knowledge of the desired tracking accuracy ϵ > 0. Based on this information alone, we can only design a robust controller achieving, in the presence of unknown trigonometric polynomial disturbances and additive perturbations to the plant and the controller, lim supt→ ∞ ∥ y(t) - yref(t) ∥ < ϵ ∥ yref ∥. Here, y is the output of the plant and yref is an arbitrary almost periodic reference signal taken from an infinite-dimensional generalized Sobolev space of almost periodic functions. In this paper, we also study robust output regulation in the limiting case where ϵ → 0. It turns out that, due to the general loss of exponential closed loop stability, asymptotic tracking/rejection can also be lost as ϵ → 0, unless the exogenous signals are smooth enough. This last result extends some recent theorems on (nonrobust) open loop output regulation for infinite-dimensional exosystems. The results of this paper are new and potentially useful for finite-dimensional plants, but the main results are also true for infinite-dimensional systems with bounded control and observation operators. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the relation between a recently proposed subspace method based on predictor identification (PBSID), known also as ‘whitening filter algorithm,’ and the classical CCA algorithm. The comparison is motivated by i) the fact that CCA is known to be asymptotically efficient for time series identification and optimal for white measured inputs and ii) some recent results showing that a number of recently developed algorithms are very closely related to PBSID. We show that PBSID is asymptotically equivalent to CCA precisely in the situations in which CCA is optimal while an ‘optimized’ version of PBSID behaves no worse than CCA also for nonwhite inputs. Even though PBSID (and its optimized version) are consistent regardless of the presence of feedback, in this paper we work under the assumption that there is no feedback to make the comparison with CCA meaningful. The results of this paper imply that the ‘optimized’ PBSID, besides being able to handle feedback, is to be preferred to CCA also when there is no feedback; only in very specific cases (white or no inputs) are the two algorithms (asymptotically) equivalent. [ABSTRACT FROM AUTHOR]

This paper describes the computation of reach sets for discrete-time linear control systems with time-varying coefficients and ellipsoidal bounds on the controls and initial conditions. The algorithms construct external and internal ellipsoidal approximations that touch the reach set boundary from outside and from in- side. Recurrence relations describe the time evolution of these approximations. An essential part of the paper deals with singular discrete-time linear systems. [ABSTRACT FROM AUTHOR]

Arbitrary high precision output tracking is one of the most desirable control objectives found in industrial applications regardless of measurement errors. The main purpose of this paper is to supply to the iterative learning control (ILC) designer guide- lines to select the corresponding learning gain in order to achieve this control objective. For example, if certain conditions are met, then it is necessary for the learning gain to converge to zero in the learning iterative domain. In particular, this paper presents necessary and sufficient conditions for boundedness of trajectories and uniform tracking in presence of measurement noise and a class of random reinitialization errors for a simple ILC algorithm. The system under consideration is a class of discrete-time affine non-linear systems with arbitrary relative degree and arbitrary number of system inputs and outputs. The state function does not need to satisfy a Lipschitz condition. This work also provides a recursive algorithm that generates the appropriate learning gain functions that meet the arbitrary high precision output tracking objective. The resulting tracking output error is shown to converge to zero at a rate inversely proportional to square root of the number of learning iterations in presence of measurement noise and a class of reinitialization errors. Two illustrative numerical examples are presented. [ABSTRACT FROM AUTHOR]

In this paper, we present a hierarchical method that decomposes a discrete-event system (DES) into a high-level subsystem which communicates with n ⩾ 1 parallel low-level subsystems, through separate interfaces which restrict the interaction of the subsystems. It is a generalization of the serial case (n = 1) described in Part I of this paper, where we define an interface and a set of interface consistency properties that can be used to verify if a DES is nonblocking and controllable. Each clause of the definition can be verified using a single subsystem; thus the complete system model never needs to be stored in memory, offering potentially significant savings in computational resources. We provide algorithms for verifying these new properties, and briefly discuss the computational complexity of the method. Finally, we present an application to a large manufacturing example with an estimated worst-case closed-loop state-space size of 2.9 × 1021. [ABSTRACT FROM AUTHOR]

Multiple-model approach provides the state-of-the-art solutions to many problems involving estimation, filtering, control, and/or modeling. One of the most important problems in the application of the multiple-model approach is the design of the model set used in a multiple-model algorithm. To our knowledge, however, it has never been addressed systematically in the literature. This paper deals with this challenging topic in a general setting. General problems of model-set design are considered. A concept of a random model is introduced. In other words, modeling of models used in a multiple model (MM) algorithm as well as the true model as random variables is proposed. Three classes of general methods for optimal design of model sets—by minimizing distribution mismatch, minimizing modal distance, and moment matching, respectively—are proposed. Theoretical results that address many of the associated issues are presented. Examples that demonstrate how some of these theoretical results can be used as well as their effectiveness are given. Many of the general results presented in this paper are also useful for performance evaluation of MM algorithms. [ABSTRACT FROM AUTHOR]

This paper addresses the challenging problem of designing an adaptive feedback strategy for simultaneous identification and stabilization for a class of nonlinearly parameterized uncertain systems in discrete time. The Nonlinear Least Squares (NLS) algorithm is applied to estimate the unknown parameters, and it turns out to be the standard Least Squares (LS) algorithm whenever the model is linearly parameterized. Based on this algorithm, both the strong consistency of the estimator and the global stability of the system are achieved with the output feedback design for the scalar-parameter case. [ABSTRACT FROM PUBLISHER]

This paper presents a geometric transversals approach for representing the probability of track detection as an analytic function of time and target motion parameters. By this approach, the optimization of the detection probability subject to sensor kinodynamic constraints can be formulated as an optimal control problem. Using the proposed detection probability function, the necessary conditions for optimality can be derived using calculus of variations, and solved numerically using a variational iteration method (VIM). The simulation results show that sensor state and control trajectories obtained by this approach bring about a significant increase in detection probability compared to existing strategies, and require a computation that is significantly reduced compared to direct methods. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a systematization of the (discrete-time) Unscented Kalman Filter (UKF) theory. We gather all available UKF variants in the literature, present corrections to theoretical inconsistencies, and provide a tool for the construction of new UKF's in a consistent way. This systematization is done, mainly, by revisiting the concepts of Sigma-Representation, Unscented Transformation (UT), Scaled Unscented Transformation (SUT), UKF, and Square-Root Unscented Kalman Filter (SRUKF). Inconsistencies are related to 1) matching the order of the transformed covariance and cross-covariance matrices of both the UT and the SUT; 2) multiple UKF definitions; 3) issue with some reduced sets of sigma points described in the literature; 4) the conservativeness of the SUT; 5) the scaling effect of the SUT on both its transformed covariance and cross-covariance matrices; and 6) possibly ill-conditioned results in SRUKF's. With the proposed systematization, the symmetric sets of sigma points in the literature are formally justified, and we are able to provide new consistent variations for UKF's, such as the Scaled SRUKF's and the UKF's composed by the minimum number of sigma points. Furthermore, our proposed SRUKF has improved computational properties when compared to state-of-the-art methods. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of localizing disturbance inputs in first-order linear time-invariant (LTI) consensus networks using measurement-based graph-theoretic methods. We consider every node and edge of the network graph to be characterized with physical weights, and show that the resulting system dynamics can be represented in terms of an asymmetric Laplacian matrix Lm. Assuming the network graph to be divided into $p$ coherent clusters, we next propose an input localization algorithm based on the properties of the weak nodal domains corresponding to the first $p-1$ slow eigenvalues of Lm. The algorithm takes in sensor measurements of the states from selected nodes, runs a system identification routine to construct the input-output transfer matrix, and compares the signs of the residues of the component transfer functions to a nominal localization key to determine in which cluster(s)the disturbance input may have entered. We prove that for systems defined over a specific class of graphs, referred to as $p$-area complete graphs, the localization is unique. We also state the extension of this result for second-order synchronization networks. We illustrate the algorithms by applying them to large-scale power system networks. [ABSTRACT FROM PUBLISHER]

This paper deals with the update step of Gaussian MAP filtering. In this framework, we seek a Gaussian approximation to the posterior probability density function (PDF) whose mean is given by the maximum a posteriori (MAP) estimator. We propose two novel optimization algorithms which are quite suitable for finding the MAP estimate although they can also be used to solve general optimization problems. These are based on the design of a sequence of PDFs that become increasingly concentrated around the MAP estimate. The resulting algorithms are referred to as Kalman optimization (KO) methods. We also provide the important relations between these KO methods and their conventional optimization algorithms (COAs) counterparts, i.e., Newton's and Levenberg-Marquardt algorithms. Our simulations indicate that KO methods are more robust than their COA equivalents. [ABSTRACT FROM AUTHOR]

A consensus problem consists of a group of dynamic agents who seek to agree upon certain quantities of interest. This problem can be generalized in the context of convex metric spaces that extend the standard notion of convexity. In this paper we introduce and analyze a randomized gossip algorithm for solving the generalized consensus problem on convex metric spaces, where the communication between agents is controlled by a set of Poisson counters. We study the convergence properties of the algorithm using stochastic calculus. In particular, we show that the distances between the states of the agents converge to zero with probability one and in the r^th mean sense. In the special case of complete connectivity and uniform Poisson counters, we give upper bounds on the dynamics of the first and second moments of the distances between the states of the agents. In addition, we introduce instances of the generalized consensus algorithm for several examples of convex metric spaces together with numerical simulations. [ABSTRACT FROM AUTHOR]

For communities of agents which are not necessarily cooperating, distributed processes of opinion forming are naturally represented by signed graphs, with positive edges representing friendly and cooperative interactions and negative edges the corresponding antagonistic counterpart. Unlike for nonnegative graphs, the outcome of a dynamical system evolving on a signed graph is not obvious and it is in general difficult to characterize, even when the dynamics are linear. In this paper, we identify a significant class of signed graphs for which the linear dynamics are however predictable and show many analogies with positive dynamical systems. These cases correspond to adjacency matrices that are eventually positive, for which the Perron–Frobenius property still holds and implies the existence of an invariant cone contained inside the positive orthant. As examples of applications, we determine cases in which it is possible to anticipate or impose unanimity of opinion in decision/voting processes even in presence of stubborn agents, and show how it is possible to extend the PageRank algorithm to include negative links. [ABSTRACT FROM AUTHOR]

It is by now well-known that wireless networks with file arrivals and departures are stable if one uses $\alpha$-fair congestion control and back-pressure based scheduling and routing. In this paper, we examine whether $\alpha$-fair congestion control is necessary for flow-level stability. We show that stability can be ensured even with very simple congestion control mechanisms, such as a fixed window size scheme which limits the maximum number of packets that are allowed into the ingress queue of a flow. A key ingredient of our result is the use of the difference between the logarithms of queue lengths as the link weights. This result is reminiscent of results in the context of CSMA algorithms, but for entirely different reasons. [ABSTRACT FROM AUTHOR]

Multi-process networks figure in many engineering applications. Parameterized discrete event systems provide a convenient means of modeling such networks when the number of subprocesses is arbitrary, unknown or time-varying. Unfortunately, some key properties of these networks, such as nonblocking and deadlock-freedom, are undecidable. Moreover, mathematical tools supporting analysis of these networks are limited. This paper introduces a novel mathematical notion, weak invariant simulation, which is adapted to the analysis of synchronous products of discrete event systems. Furthermore, it proposes an efficient method to check whether a finite-state generator weakly invariantly simulates another finite-state generator with respect to a specific subalphabet. This new simulation relation is used to define a tractable subclass of parameterized ring networks of isomorphic subprocesses in which deadlock-freedom is decidable. Within this framework, a procedure is given to determine the reachable deadlocked states of the network. The effectiveness of the procedure is demonstrated by the deadlock analysis of a version of the dining philosophers problem. [ABSTRACT FROM AUTHOR]

In this paper, we develop a method to automatically generate a control policy for a dynamical system modeled as a Markov Decision Process (MDP). The control specification is given as a Linear Temporal Logic (LTL) formula over a set of propositions defined on the states of the MDP. Motivated by robotic applications requiring persistent tasks, such as environmental monitoring and data gathering, we synthesize a control policy that minimizes the expected cost between satisfying instances of a particular proposition over all policies that maximize the probability of satisfying the given LTL specification. Our approach is based on the definition of a novel optimization problem that extends the existing average cost per stage problem. We propose a sufficient condition for a policy to be optimal, and develop a dynamic programming algorithm that synthesizes a policy that is optimal for a set of LTL specifications. [ABSTRACT FROM AUTHOR]

In this paper, we present the globally optimal distributed Kalman filtering fusion with singular covariances of filtering errors and measurement noises. The following facts motivate us to consider the problem. First, the invertibility of estimation error covariance matrices is a necessary condition for most of the existing distributed fusion algorithms. However, it can not be guaranteed to exist in practice. For example, when state estimation for a given dynamic system is subject to state equality constraints, the estimation error covariance matrices must be singular. Second, the proposed fused state estimate is still exactly the same as the centralized Kalman filtering using all sensor raw measurements. [ABSTRACT FROM AUTHOR]