Search

This paper studies consensus problems of multi-agent systems with binary-valued communications. Different from most existing works, the agents considered in this paper can only get binary-valued observations of its neighbors’ states with random noises. A consensus algorithm is proposed: first, each agent estimates its neighbors’ states by the recursive projection algorithm; then, each agent designs the control timely based on the estimates. It is proved that the estimates of the states can converge to the true states with a faster convergence rate than that in the parameter estimation. Moreover, the states of the agents can achieve mean-square consensus, and the corresponding consensus speed can achieve $O(1/t)$ under certain conditions. Finally, simulations are given to demonstrate the theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the proper orthogonal decomposition (POD) method to numerically solve the forward Kolmogorov equation (FKE). Our method aims to explore the low-dimensional structures in the solution space of the FKE and to develop efficient numerical methods. As an important application and our primary motivation to study the POD method to FKE, we solve the nonlinear filtering (NLF) problems with a real-time algorithm proposed by Yau and Yau combined with the POD method. This algorithm is referred as POD algorithm in this paper. Our POD algorithm consists of offline and online stages. In the offline stage, we construct a small number of POD basis functions that capture the dynamics of the system and compute propagation of the POD basis functions under the FKE operator. In the online stage, we synchronize the coming observations in a real-time manner. Its convergence analysis has also been discussed. Some numerical experiments of the NLF problems are performed to illustrate the feasibility of our algorithm and to verify the convergence rate. Our numerical results show that the POD algorithm provides considerable computational savings over existing numerical methods. [ABSTRACT FROM AUTHOR]

This paper proposes scalable, distributed algorithms for solving linear equations by integrating two mechanisms, termed consensus and conservation, in double-layered multiagent networks. The multiagent network considered in this paper is composed of clusters and each cluster consists of an aggregator and a subnetwork of agents. By achieving consensus and conservation through agent–agent communications in the same cluster and aggregator–aggregator communications among different clusters, respectively, distributed algorithms are devised for agents to cooperatively achieve a solution to the overall linear equation. These algorithms outperform existing algorithms, including but not limited to the following aspects—first, each agent does not have to know as much as a complete row or column of the overall equation; second, each agent only needs to control as few as two scalar states when the number of clusters and the number of agents are sufficiently large; third, the dimensions of agents’ states in the proposed algorithms do not have to be the same (while in contrast, algorithms based on the idea of standard consensus inherently require all agents’ states to be of the same dimension). Both analytical proof and simulation results are provided to validate exponential convergence of the proposed distributed algorithms in solving linear equations. [ABSTRACT FROM AUTHOR]

This paper considers the problem of learning the unknown structure of a network with the underlying topology given by a polyforest (a collection of directed trees with potentially multiple roots). The main result is an algorithm that consistently learns the network structure using only second-order statistics of the data. The methodology is robust with respect to the presence of unmeasured (latent) nodes: the algorithm detects the exact number and location of the latent nodes, when they satisfy specific degree conditions in the actual network graph. It is shown that the same degree conditions are also necessary for a consistent reconstruction. Thus, the proposed reconstruction algorithm achieves the fundamental limitations in learning the structure of a polyforest network of linear dynamic systems in the presence of latent nodes. This paper overcomes the limitations of previous results that only addressed single-rooted trees, tackling the problem in an efficient way since the computational complexity of the derived algorithm is proven to be polynomial in the number of observed nodes. [ABSTRACT FROM AUTHOR]

This paper studies linear stochastic approximation (SA) algorithms and their application to multiagent systems in engineering and sociology. As main contribution, we provide necessary and sufficient conditions for convergence of linear SA algorithms to a deterministic or random final vector. We also characterize the system convergence rate, when the system is convergent. Moreover, differing from non-negative gain functions in traditional SA algorithms, this paper considers also the case when the gain functions are allowed to take arbitrary real numbers. Using our general treatment, we provide necessary and sufficient conditions to reach consensus and group consensus for first-order discrete-time multiagent system over random signed networks and with state-dependent noise. Finally, we extend our results to the setting of multidimensional linear SA algorithms and characterize the behavior of the multidimensional Friedkin–Johnsen model over random interaction networks. [ABSTRACT FROM AUTHOR]

In this paper, we consider the distributed filtering problem for continuous-time stochastic systems over sensor networks subject to Markovian switching topologies. Due to limited communication energy and bandwidth, an event-based communication scheme is proposed with the aim to decrease the transmission frequency. An individual triggering condition is put forward to regulate the communication rates for each component of the system state in order to better reflect the engineering requirements. The aim of this paper is to design a distributed filter over sensor networks with Markovian switching topologies such that the dynamics of the estimation error is exponentially mean-square bounded. It is shown that, with the proposed event-based distributed filtering algorithm, the exponential mean-square boundedness of the estimation errors is guaranteed if the sensor network is distributively detectable and the combined communication topology is strongly connected. A numerical example is presented to illustrate the usefulness of the developed algorithm. [ABSTRACT FROM AUTHOR]

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]

In this paper, we study how to utilize forecasts to design online electrical vehicle (EV) charging algorithms that can attain strong performance guarantees. We consider the scenario of an aggregator serving a large number of EVs together with its background load, using both its own renewable energy (for free) and the energy procured from the external grid. The goal of the aggregator is to minimize its peak procurement from the grid, subject to the constraint that each EV has to be fully charged before its deadline. Further, the aggregator can predict the future demand and the renewable energy supply with some levels of uncertainty. We show that such prediction can be very effective in reducing the competitive ratios of online control algorithms, and even allow online algorithms to achieve close-to-offline-optimal peak. Specifically, we first propose a 2-level increasing precision model (2-IPM), to model forecasts with different levels of accuracy. We then develop a powerful computational approach that can compute the optimal competitive ratio under 2-IPM over any online algorithm, and also online algorithms that can achieve the optimal competitive ratio. Simulation results show that, even with up to 20% day-ahead prediction errors, our online algorithms still achieve competitive ratios fairly close to 1, which are much better than the classic results in the literature with a competitive ratio of $e$ . The second contribution of this paper is that we solve a dilemma for online algorithm design, e.g., an online algorithm with good competitive ratio may exhibit poor average-case performance. We propose a new Algorithm-Robustification procedure that can convert an online algorithm with good average-case performance to one with both the optimal competitive ratio and good average-case performance. We demonstrate via trace-based simulations the superior performance of the robustified version of a well-known heuristic algorithm based on model predictive control. [ABSTRACT FROM PUBLISHER]

This paper investigates the secure state estimation problem of multiagent systems with misbehaving agents. Compared with the existing works which only consider malicious behaviors generated elaborately, a class of faulty behaviors generated randomly is also taken into account. By assuming that faulty behaviors cannot be altered by the adversaries, the notion of orthogonal complement matrix is introduced to characterize the state observability of the multiagent systems with both faulty and malicious agents. It is shown that more misbehaving agents can be tolerated by distinguishing faulty agents from malicious ones. Then, for single agent, two algorithms are provided to estimate the state based on its own value and the measurements obtained from its neighbors. Finally, two simulations are provided to illustrate the correctness and effectiveness of the proposed conditions and methods. [ABSTRACT FROM AUTHOR]

In this paper, two control schemes producing a continuous control signal are presented for a perturbed triple integrator: The continuous twisting algorithm (3-CTA) and the output feedback continuous twisting algorithm (3-OFCTA). The first one is a state feedback controller that ensures global finite-time stability of the origin, despite of Lipschitz, nonvanishing, and matched disturbances. It provides steady-state precision of fourth order of the output w.r.t. sampling step. The second one is an output feedback controller, which uses a third-order robust and exact differentiator as an observer. By requiring only information of the measurable output, the 3-OFCTA preserves all features of robustness, convergence, and precision of the state feedback 3-CTA. Moreover, it is proven that a separation principle applies, so that the gains of the controller and of the observer can be selected independently to assure stability. [ABSTRACT FROM AUTHOR]

This paper presents a novel method to compute the distance to instability for linear time-invariant delay systems with multiple delays, subjected to combined uncertainties on the system matrices and the delay parameters. The method is able to fully exploit structure and possible interdependencies between the uncertainties affecting the coefficient matrices, the property that realistic perturbations are real valued, and the structure of the delay equation. The resulting algorithm relies on a characterization in terms of the pseudospectral abscissa and on techniques from optimization over manifolds of matrices. [ABSTRACT FROM AUTHOR]

This paper proposes a continuous-time distributed algorithm for multiagent networks to achieve a solution with the minimum $l_1$ -norm to underdetermined linear equations. The proposed algorithm comes from a combination of the Filippov set-valued map with the projection-consensus flow. Given the underlying network is undirected and fixed, it is shown that the proposed algorithm drives all agents’ individual states to converge in finite time to a common value, which is the minimum $l_1$ -norm solution. [ABSTRACT FROM AUTHOR]

Despite the correct-by-construction property, one of the major drawbacks of supervisory control synthesis is state-space explosion. Several approaches have been proposed to overcome this computational difficulty, such as modular, hierarchical, decentralized, and multilevel supervisory control synthesis. Unfortunately, the modeler needs to provide additional information about the system's structure or controller's structure as input for most of these nonmonolithic synthesis procedures. Multilevel synthesis assumes that the system is provided in a tree-structured format, which may resemble a system decomposition. In this paper, we present a systematic approach to transform a set of plant models and a set of requirement models provided as extended finite automata into a tree-structured multilevel discrete-event system to which multilevel supervisory control synthesis can be applied. By analyzing the dependencies between the plants and the requirements using dependence structure matrix techniques, a multilevel clustering can be calculated. With the modeling framework of extended finite automata, plant models and requirements depend on each other when they share events or variables. We report on experimental results of applying the algorithm's implementation on several models available in the literature to assess the applicability of the proposed method. The benefit of multilevel synthesis based on the calculated clustering is significant for most large-scale systems. [ABSTRACT FROM AUTHOR]

We consider distributed computation of generalized Nash equilibrium (GNE) over networks, in games with shared coupling constraints. Existing methods require that each player has full access to opponents’ decisions. In this paper, we assume that players have only partial-decision information, and can communicate with their neighbors over an arbitrary undirected graph. We recast the problem as that of finding a zero of a sum of monotone operators through primal-dual analysis. To distribute the problem, we doubly augment variables, so that each player has local decision estimates and local copies of Lagrangian multipliers. We introduce a single-layer algorithm, fully distributed with respect to both primal and dual variables. We show its convergence to a variational GNE with fixed step sizes, by reformulating it as a forward–backward iteration for a pair of doubly-augmented monotone operators. [ABSTRACT FROM AUTHOR]

Many problems of interest for cyber-physical network systems can be formulated as mixed-integer linear programs in which the constraints are distributed among the agents. In this paper, we propose a distributed algorithmic framework to solve this class of optimization problems in a peer-to-peer network with no coordinator and with limited computation and communication capabilities. At each communication round, agents locally solve a small linear program, generate suitable cutting planes, and communicate a fixed number of active constraints. Within the distributed framework, we first propose an algorithm that, under the assumption of integer-valued optimal cost, guarantees finite-time convergence to an optimal solution. Second, we propose an algorithm for general problems that provides a suboptimal solution up to a given tolerance in a finite number of communication rounds. Both algorithms work under asynchronous, directed, unreliable networks. Finally, through numerical computations, we analyze the algorithm scalability in terms of the network size. Moreover, for a multi-agent multi-task assignment problem, we show, consistently with the theory, its robustness to packet loss. [ABSTRACT FROM AUTHOR]

We investigate the problem of synthesizing dynamic masks that preserve the infinite-step opacity in the context of discrete-event systems. Dynamic mask is an information acquisition mechanism that controls the observability of the system's events dynamically online, e.g., by turning sensors on/off. A system equipped with a dynamic mask is said to be infinite-step opaque if an outside intruder that can access all acquired information can never infer that the system was at some secret state for any specific previous instant. Existing works on the dynamic mask synthesis problem can only preserve the current-state opacity. However, synthesizing dynamic masks for the infinite-step opacity, which is stronger than the current-state opacity, is much more challenging. The main reason is that the delayed information is involved in this problem and whether or not a current secret can be revealed depends on sensing decisions to be synthesized in the future. In this paper, a new type of information state is proposed to capture all the delayed information in the infinite-step opacity synthesis problem. An effective algorithm is then presented to solve the synthesis problem, which extends existing dynamic mask synthesis techniques from the current-state opacity to infinite-step opacity. Additionally, an information-state-reduction-based approach is proposed to further mitigate the computational complexity of the synthesis procedure. Finally, we discuss how to generalize our results to a class properties with delayed information including infinite-step $K$ -anonymity and infinite-step indistinguishability. [ABSTRACT FROM AUTHOR]

This paper considers an unconstrained collaborative optimization of a sum of convex functions, where agents make decisions using local information in the presence of random interconnection topologies. We recast the problem as minimization of the sum of convex functions over a constraint set defined as the set of fixed-value points of a random operator derived from weighted matrices of random graphs. We show that the derived random operator has nonexpansivity property; therefore, this formulation does not need the distribution of random communication topologies. Hence, it includes random networks with/without asynchronous protocols. As an extension of the problem, we define a novel optimization problem, namely minimization of a convex function over the fixed-value point set of a nonexpansive random operator. We propose a discrete-time algorithm using diminishing step size for converging almost surely and in mean square to the global solution of the optimization problem under suitable assumptions. Consequently, as a special case, it reduces to a totally asynchronous algorithm for the distributed optimization problem. We show that fixed-value point is a bridge from deterministic analysis to random analysis of the algorithm. Finally, a numerical example illustrates the convergence of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of achieving average consensus over a random time-varying sequence of directed graphs by extending the class of so-called push-sum algorithms to such random scenarios. Provided that an ergodicity notion, which we term the directed infinite flow property, holds and the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. Moreover, for a random sequence of graphs generated using a so-called time-varying $B$ -irreducible probability matrix, we establish convergence rates for the proposed push-sum algorithm. [ABSTRACT FROM AUTHOR]

This paper presents an optimal data fusion formulation and algorithm in the sense of minimum mean-square error when some or all cross covariances are unknown. This algorithm is generic in that it is capable of processing any number of measurement vectors of any dimension with any pattern of unknown cross covariances. Closed-form solution is provided for the case when all cross covariances are unknown and all measurement covariance matrices are diagonal. Numerical projected subgradient optimal fusion algorithm is provided for the most generic case. The well known covariance intersection method is shown to have a weaker upper bound of this formulation. [ABSTRACT FROM AUTHOR]

This paper proposes an iterative learning control (ILC) algorithm with gain adaptation for discrete-time stochastic systems. The algorithm is based on Kesten's accelerated stochastic approximation (SA) algorithm. The gain adaptation uses only tracking error information, and, hence, is a data-driven adaptation approach. If stochastic noises account for a small proportion of the tracking error, the learning gain matrix remains constant with a high probability. If stochastic noises dominate the tracking error, the learning gain matrix is decreasing. Therefore, the new ILC algorithm converges more quickly than existing SA-based algorithms. In addition, the classic P-type ILC law for noise-free systems is a special case of the new ILC algorithm. The behaviors of the proposed ILC algorithm are demonstrated through examples. [ABSTRACT FROM AUTHOR]

In this paper, a numerically robust solver for least-square problems with bounded variables (BVLS) is presented for applications including, but not limited to, model predictive control (MPC). The proposed BVLS algorithm solves the problem efficiently by employing a recursive QR factorization method based on Gram–Schmidt orthogonalization. A reorthogonalization procedure that iteratively refines the QR factors provides numerical robustness for the described primal active-set method, which solves a system of linear equations in each of its iterations via recursive updates. The performance of the proposed BVLS solver, which is implemented in C without external software libraries, is compared in terms of computational efficiency against state-of-the-art quadratic programming solvers for small- to medium-sized random BVLS problems and a typical example of embedded linear MPC application. The numerical tests demonstrate that the solver performs very well even when solving ill-conditioned problems in single-precision floating-point arithmetic. [ABSTRACT FROM AUTHOR]

This paper investigates an adaptive sliding-mode controller design problem for a class of Markov jump systems with actuator faults. First, a more extensive faults model, which includes actuator loss of effectiveness, outage and stuck, is established. Moreover, a novel sliding surface function is designed and sufficient conditions are established to ensure stochastic stability of the Markov jump systems with known transition probability. Second, based on the adaptive sliding-mode algorithm and the fault compensation algorithm, a comprehensive control law is synthesized not only to overcome the boundary restrictions of actuator loss effectiveness and external disturbances, but also to ensure the properties of stochastic stability and the reachability of the sliding-mode dynamics. Third, an improved stochastically stability criterion, in the case of Markov jump system with uncertain transition probability, is derived based on the homogeneous polynomial matrix technique. Finally, two simulation examples are provided to support the feasibility and effectiveness of the proposed control algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of minimizing the global energy cost for multiagent systems to achieve consensus over undirected network topologies. Conventional optimization problems so defined require all-to-all network topologies for interagent communications, which precludes the use of distributed control or otherwise demands that the network be complete. To circumvent this difficulty, we introduce a network approximation (NA) scheme in the optimization criterion, which tends to render the optimization problem to one seemingly over a complete graph network, thus removing the all-to-all communication requirement. With the NA cost, we show that a distributed optimal consensus algorithm always exists for any given connected network topology, which can be determined by solving a single-agent-level parametric algebraic Ricatti equation (PARE). We also investigate the performance of the optimal consensus algorithm, focusing on the minimal energy cost required to achieve consensus optimally, and the speed at which consensus is achieved. Furthermore, for certain more special yet worthy cases, such as single-integrator, double-integrator, and first-order unstable agents, we derive explicit expressions for the energy cost and the consensus speed. It can be seen from these results that the energy cost can be made arbitrarily small for single-integrator and double-integrator systems under the optimal distributed control. On the other hand, for the first-order unstable agents, the energy cost increases and consensus speed decreases monotonically with the value of the agent's real unstable pole. [ABSTRACT FROM AUTHOR]

This paper considers the problem of efficiently and securely controlling cyber-physical systems that are operating in uncertain, and adversarial environments. To mitigate sensor, actuator attacks, and performance loss due to such attacks, we formulate a secure control algorithm that consists of a proactive and a reactive defense mechanism. The proactive mechanism, which is based on the principles of moving target defense, utilizes a stochastic switching structure to dynamically and continuously alter the parameters of the system, while hindering the attacker's ability to conduct successful reconnaissance to the system. The unpredictability of the current actuator and sensor is optimized using an information entropy measure, which is induced by probabilistic switching. The reactive mechanism on the other side, detects potentially attacked components, namely sensors and actuators, by leveraging online data to compute an integral Bellman error. A rigorous mathematical framework is presented to guarantee the stability of the equilibrium point of the closed-loop system, and provide a quantified bound on the performance loss when utilizing both reactive and proactive mechanisms. Simulation results show the efficacy of the proposed approaches on a benchmark aircraft model. [ABSTRACT FROM AUTHOR]

This paper concerns a spectral estimation problem in which we want to find a spectral density function that is consistent with estimated second-order statistics. It is an inverse problem admitting multiple solutions, and selection of a solution can be based on prior functions. We show that the problem is well-posed when formulated in a parametric fashion, and that the solution parameter depends continuously on the prior function. In this way, we are able to obtain a smooth parametrization of admissible spectral densities. Based on this result, the problem is reparametrized via a bijective change of variables out of a numerical consideration, and then a continuation method is used to compute the unique solution parameter. Numerical aspects, such as convergence of the proposed algorithm and certain computational procedures are addressed. A simple example is provided to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a distributed Newton method for decenteralized optimization of large sums of convex functions. Our proposed method is based on creating a set of separable finite sum minimization problems by utilizing a decomposition technique known as Global Consensus that distributes the computation across nodes of a graph and enforces a consensus constraint among the separated variables. The key idea is to exploit the sparsity of the dual Hessian and recast the computation of the Newton step as one of the efficiently solving symmetric diagonally dominant linear equations. We show that our method outperforms the state-of-the-art algorithms, including ADMM. We validate our algorithm both theoretically and empirically. On the theory side, we demonstrate that our algorithm exhibits superlinear convergence within a neighborhood of optimality. Empirically, we show the superiority of this new method on a variety of large-scale optimization problems. The proposed approach is scalable to large problems and has a low communication overhead. [ABSTRACT FROM AUTHOR]

This paper deals with the dead-beat stabilizability of autonomous discrete-time switched linear systems. Based on a constructive necessary and sufficient condition for dead-beat stabilizability, we propose two algorithms. The first one is concerned with the problem of testing dead-beat stabilizability and computing the shorter stabilizing mode sequence, whenever it exists. The other one implements a method to construct a switched system whose shorter dead-beat stabilizing sequence has a prescribed length. Then, we present numerical assessments and possible applications. [ABSTRACT FROM AUTHOR]

When sum-of-squares (SOS) programs are recast as semidefinite programs (SDPs) using the standard monomial basis, the constraint matrices in the SDP possess a structural property that we call partial orthogonality. In this paper, we leverage partial orthogonality to develop a fast first-order method, based on the alternating direction method of multipliers (ADMM), for the solution of the homogeneous self-dual embedding of SDPs describing SOS programs. Precisely, we show how a “diagonal plus low rank” structure implied by partial orthogonality can be exploited to project efficiently the iterates of a recent ADMM algorithm for generic conic programs onto the set defined by the affine constraints of the SDP. The resulting algorithm, implemented as a new package in the solver CDCS, is tested on a range of large-scale SOS programs arising from constrained polynomial optimization problems and from Lyapunov stability analysis of polynomial dynamical systems. These numerical experiments demonstrate the effectiveness of our approach compared to common state-of-the-art solvers. [ABSTRACT FROM AUTHOR]

The paper studies digital redesign of linear time-invariant analog controllers under intermittent sampling. The sampling pattern is only assumed to be uniformly bounded, but otherwise irregular and unknown a priori. The contribution of the paper is twofold. First, it proposes a constructive algorithm to redesign any analog stabilizing controller so that the closed-loop stability is preserved. Second, it is shown that when applied to (sub) optimal \boldsymbolH^2 and \boldsymbolH^\infty controllers, the algorithm produces (sub) optimal sampled-data solutions under any a priori unknown sampling pattern. The proposed solutions are analytic, computationally simple, implementable, and transparent. Transparency pays off in showing the optimality, under a fixed sampling density, of uniform sampling for both performance measures studied. [ABSTRACT FROM AUTHOR]

This note presents further results based on the recent paper [J. Liang, H. Chen, and J. Lam, “An improved criterion for controllability of Boolean control networks,” IEEE Trans. Autom. Control, vol. 62, no. 11, pp. 6012–6018, Nov. 2017]. After some optimizations, the conventional method can be more efficient than the method used in the above paper. We also propose an improved method via combining the well known Tarjan's algorithm and depth-first search technique for the controllability analysis of Boolean control networks (BCNs). As a result, the computational complexity will not exceed $O(N^2)$ with $N=2^n$ , where $n$ is the number of state-variables in a BCN. [ABSTRACT FROM AUTHOR]

Existing results on cooperative control of multiagent systems with unknown control directions require that the underlying topology is either fixed with a strongly connected graph or switching between different strongly connected graphs. Furthermore, in most cases the graph is assumed to be balanced. This paper proposes a new class of nonlinear proportional-integral (PI) based algorithms to relax these requirements and allow for unbalanced and switching topologies having a jointly strongly connected basis. This is made possible for single-integrator (SI) and double-integrator (DI) agents with nonidentical unknown control directions by a suitable selection of the distributed nonlinear PI functions. Moreover, as a special case, the proposed algorithms are applied to strongly connected and fixed graphs. Finally, simulation examples are given to show the validity of our theoretical results. [ABSTRACT FROM AUTHOR]

The leader-following consensus problem for linear discrete-time multiagent systems has been studied in the literature using $H_{\infty }$ Riccati inequality design and $H_{2}$ Riccati equation design methods, respectively. These two methods lead to a solvability condition in terms of an inequality that relies on a scaling gain and a fixed weighting vector called nominal weighting vector. In this paper, we further study this problem by proposing a more general class of distributed state feedback control laws, which not only depends on a scaling gain, but also a set of weighting vectors. We first establish a spectral property of a weighted graph matrix, which will be instrumental in solving the problem. Then, we present a solvability condition based on a modified algebraic Riccati equation, which is somehow more general than $H_{\infty }$ and $H_{2}$ Riccati methods, in that the solvability condition can be made satisfied by tuning the weighting vector. We show that our solvability condition is also necessary for single-input follower systems and is always satisfied for leader systems without exponentially growing modes. Moreover, in case the solvability condition is not satisfied under the nominal weighting vector, we show that our solvability condition can always be made satisfied by choosing a weighting vector other than the nominal one for multiagent systems over acyclic digraphs. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of identifiability of dynamical networks in the case where the vector of noises on the nodes does not have full rank. In the full-rank noise case, network identifiability is defined as the capability of uniquely identifying the transfer function matrices describing the network from informative data. This includes the noise model, which can be uniquely defined when the noise vector has full rank. When the noise vector has a singular spectrum, it admits an infinite number of different noise models and the definition of network identifiability must be adapted to demand that the correct noise spectrum be identified from informative data rather than a specific noise model. With this new definition, we show that a network with rank reduced noise is identifiable under the same conditions that apply to a network with full-rank noise. [ABSTRACT FROM AUTHOR]

In this paper, we consider using multiple noisy binary sensors to track a target that moves as a Markov Chain in a finite discrete environment, with symmetric probability of false alarm and missed detection. We study two policies. First, we show that the greedy policy, whereby $m$ sensors are placed at the $m$ most-likely target locations, is one-step optimal in that it maximizes the expected maximum a posteriori (MAP) estimate. Second, we show that a policy in which the $m$ sensors are placed in the second through $(m+1)$ st most likely target locations achieves equal or slightly worse expected MAP performance, but leads to significantly decreased variance on the MAP estimate. The result is proven for $m = 1$ , and Monte Carlo simulations give evidence for $m > 1$. Both policies are closed loop, index-based active sensing strategies that are computationally trivial to implement. Our approach focuses on one-step optimality because of the apparent intractability of computing an optimal policy via dynamic programming in belief space. However, Monte Carlo simulations suggest that both policies perform well over arbitrary horizons. [ABSTRACT FROM AUTHOR]

Models of bipedal walking are hybrid, with continuous-time dynamics representing the swing phases and discrete-time dynamics representing the impact events. The feedback controllers for these systems can be two-level, including both continuous- and discrete-time (event-based) actions. This paper presents a systematic framework to design decentralized event-based controllers for robust stabilization of hybrid periodic orbits against possible disturbances in discrete-time phases. The properties of the Poincaré return map are investigated to study the orbital input-to-state stability for the closed-loop system with respect to disturbance inputs. An optimization problem involving bilinear matrix inequalities is then presented to design $\mathcal {H}_{2}$ - and $\mathcal {H}_{\infty }$ -optimal decentralized event-based controllers. The power of the proposed framework is finally demonstrated through designing a set of decentralized two-level controllers for underactuated walking of a three-dimensional autonomous bipedal robot with nine degrees of freedom and a decentralization scheme motivated by amputee locomotion with a transpelvic prosthetic leg. [ABSTRACT FROM AUTHOR]

Frequency-domain analysis of dynamic systems is important across many areas of engineering. However, while there are many analysis methods for linear systems, the problem is much less widely studied for nonlinear systems. Frequency-domain analysis of nonlinear systems using frequency response functions (FRFs) is particularly important to reveal resonances, super/subh-armonics, and energy transfer across frequencies. In this paper, the novel contribution is a time-domain, model-based approach to describing the uncertainty of nonlinear systems in the frequency domain. The method takes a nonlinear input–output time-domain model that has normally distributed parameters and propagates that uncertainty into the frequency domain using analytic expressions based on FRFs. We demonstrate the approach on both synthetic examples of nonlinear systems and a real-world nonlinear system identified from experimental data. We benchmark the proposed approach against a brute-force technique based on Monte Carlo sampling and show that there is good agreement between the methods. [ABSTRACT FROM AUTHOR]

This paper is concerned with the sliding mode control (SMC) problem for a class of uncertain discrete-time systems subject to unmatched external disturbances and communication constraints. In order to reduce the bandwidth usage between the controller and the actuators, the stochastic communication protocol (SCP) is utilized to determine which actuator should be given the access to the network at a certain instant. A key issue of the addressed problem is to design both the sliding surface and the sliding mode controller under the SCP scheduling. An updating rule on actuator input is first introduced and then a token-dependent SMC law is designed. Sufficient conditions are established for the resultant SMC systems such that not only the reachability with a sliding domain around the specified sliding surface is ensured, but also the stochastic stability with a prescribed $H_\infty$ performance level is guaranteed. Based on these conditions, a set of coupled matrix inequalities is given to acquire the token-dependent parameter matrices in the proposed SMC law. Finally, a numerical example is presented to illustrate the effectiveness of the proposed $H_\infty$ SMC scheme under the SCP scheduling. [ABSTRACT FROM AUTHOR]

The circle formation problem for a group of mobile agents with limited interaction range is addressed in this paper. Distributed switching control laws are developed for multiagent systems to form prescribed formations from any initial configurations on a circle. It is shown that the desired circle formation can be achieved if a parameter depending on the agents’ interaction range is larger than the prescribed angular distance from each agent to its immediate counterclockwise agent. When the agents’ interaction range is not sufficiently large, the formation error of each agent converges to a limit, and an upper bound and a lower bound on the limit value are provided. It is also shown that under the proposed control laws, the mobile agents’ spatial order on the circle is always preserved and thus collision between mobile agents is avoided. [ABSTRACT FROM AUTHOR]

The distributed convex optimization problem is studied in this paper for any fixed and connected network with general constraints. To solve such an optimization problem, a new type of continuous-time distributed subgradient optimization algorithm is proposed based on the Karuch–Kuhn–Tucker condition. By using tools from nonsmooth analysis and set-valued function theory, it is proved that the distributed convex optimization problem is solved on a network of agents equipped with the designed algorithm. For the case that the objective function is convex but not strictly convex, it is proved that the states of the agents associated with optimal variables could converge to an optimal solution of the optimization problem. For the case that the objective function is strictly convex, it is further shown that the states of agents associated with optimal variables could converge to the unique optimal solution. Finally, some simulations are performed to illustrate the theoretical analysis. [ABSTRACT FROM AUTHOR]

This paper is concerned with the $H_2$ control of linear systems with multiple quantization channels. The quantization parameters of each channel are not required to be identical. The resultant mismatches are represented by polytopic uncertainties. A composite controller composed of linear and nonlinear parts is designed to meet the required $H_2$ performance and offset the quantization error. Resorting to a vertex separation technique and Finsler lemma instead of matrix inverse operations, new synthesis conditions for the desired linear part are derived in terms of linear matrix inequalities, which are further extended to treat systems with norm-bounded uncertainties. A comparison of conservativeness between the proposed methods and the existing ones is demonstrated by two numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new approach to state estimation of multiple state-space models. Unlike the traditional methods (including the interacting multiple-model algorithm) that approximate a Gaussian mixture distribution with a single Gaussian distribution, the proposed method approximates the joint probability density functions of the state and model identity through Bayesian inference. It is shown that the proposed method reduces the approximation error considerably, and improves estimation accuracy without increasing computational cost. Analysis of its specific features as well as a potential extension is also presented. Numerical examples with a practically oriented simulation are employed to illustrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This paper considers a class of stochastic source-seeking problems to drive a mobile robot to the minimizer of a source signal. Our approach is first analyzed in an obstacle-free scenario, where measurements of the signal at the robot location and information of a contact sensor are required. We extend our results to environments with obstacles under mild assumptions on the step size. Our approach builds on the simultaneous perturbation stochastic approximation idea to obtain information of the signal field. We prove the practical convergence of the algorithms to a ball whose size depends on the step size that contains the location of the source. The novelty relies in that we consider nondifferentiable convex functions, a fixed step size, and the environment may contain obstacles. Our proof methods employ nonsmooth Lyapunov function theory, tools from convex analysis, and stochastic difference inclusions. Finally, we illustrate the applicability of the proposed algorithms in a two-dimensional scenarios. [ABSTRACT FROM AUTHOR]

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]

This paper is concerned with a general class of distributed constrained optimization problems over a multiagent network, where the global objective function is represented by the sum of all local objective functions. Each agent in the network only knows its own local objective function, and is restricted to a global nonempty closed convex set. We discuss the scenario where the communication of the whole multiagent network is expressed as a sequence of time-varying general unbalanced directed graphs. The directed graphs are required to be uniformly jointly strongly connected and the weight matrices are only row-stochastic. To collaboratively deal with the optimization problems, existing distributed methods mostly require the communication graph to be fixed or balanced, which is impractical and hardly inevitable. In contrast, we propose a new distributed projection subgradient algorithm which is applicable to the time-varying general unbalanced directed graphs and does not need each agent to know its in-neighbors’ out-degree. When the objective functions are convex and Lipschitz continuous, it is proved that the proposed algorithm exactly converges to the optimal solution. Simulation results on a numerical experiment are shown to substantiate feasibility of the proposed algorithm and correctness of the theoretical findings. [ABSTRACT FROM AUTHOR]

This paper presents a discrete-time distributed and noncooperative routing algorithm, which is proved, via Lyapunov arguments, to asymptotically converge to a specific equilibrium condition among the traffic flows over the network paths, known as Wardrop equilibrium. This convergence result improves the discrete-time algorithms in the literature, which achieve approximate convergence to the Wardrop equilibrium. Numerical simulations show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper presents a bounded confidence gossip algorithm for describing the process of opinion formation over a communication network. Each agent in the network keeps a time-varying opinion vector (or state), which represents its opinion about a set of matters. A common confidence threshold is set for all of the agents. The states of agents in the network will be updated time by time according to an iterative procedure: At each time, 1) one agent is chosen randomly, then it chooses one of its neighbors on the communication graph to contact with; 2) they exchange their states; and 3) if they have different states and the distance between their states is strictly smaller than the confidence threshold, they update their states as the average of the two. This algorithm converges almost surely to some equilibrium point such that any two adjacent agents either have the same state or have distinct states whose distance is no less than the confidence threshold. This is called the constant confidence threshold algorithm. An increasing confidence threshold algorithm, which repeats the constant confidence threshold algorithm several times with increasing confidence threshold, is also proposed. The algorithm is also convergent almost surely to some equilibrium point. Applicability of the method to clustering problems is shown through numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we study the interacting multiple model (IMM) estimator for networked control systems with packet loss but without packet acknowledgment (ACK). The ACK is a signal sent by the actuator to inform the estimator of whether control packets are lost or not. A system with ACK is usually called a transmission control protocol (TCP) like system; otherwise, it is called a user datagram protocol (UDP) like system. We show that the stability of the IMM estimator for UDP-like systems is determined by the observation packet arrival rate (p.a.r.) and is independent of the control p.a.r. and control inputs. The IMM estimator is stable if the observation p.a.r. is greater than a critical value. We show that this critical value is the same as the critical value for the stability of the optimal estimator for its corresponding TCP-like system. If control inputs eventually tend to zero, the error covariance of the IMM estimator converges to that of the optimal estimator for TCP-like systems. We characterize the impact of the control/observation p.a.r. and the control input on estimation performance. Finally, we prove that the average estimation performance of the IMM estimator approximates that of the optimal estimator within a finite bound, and is superior to that of the linear minimum mean square error estimator. [ABSTRACT FROM AUTHOR]

A reduction of a source distribution is a collection of smaller sized distributions that are collectively equivalent to the source distribution with respect to the property of decomposability. That is, an arbitrary language is decomposable with respect to the source distribution if and only if it is decomposable with respect to each smaller sized distribution (in the reduction). The notion of reduction of distributions has previously been proposed to improve the complexity of decomposability verification. In this paper, we address the problem of generating (optimal) reductions of distributions automatically. A (partial) solution to this problem is provided, which consists of an incremental algorithm for the production of candidate reductions and a reduction validation procedure. In the incremental production stage, backtracking is applied whenever a candidate reduction that cannot be validated is produced. A strengthened substitution-based proof technique is used for reduction validation, while a fixed template of candidate counter examples is used for reduction refutation; put together, they constitute our (partial) solution to the reduction verification problem. In addition, we show that a recursive approach for the generation of (small) reductions is easily supported. [ABSTRACT FROM AUTHOR]

This paper proposes distributed algorithms to solve robust convex optimization (RCO) when the constraints are affected by nonlinear uncertainty. We adopt a scenario approach by randomly sampling the uncertainty set. To facilitate the computational task, instead of using a single centralized processor to obtain a “global solution” of the scenario problem (SP), we resort to multiple interconnected processors that are distributed among different nodes of a network to simultaneously solve the SP. Then, we propose a primal-dual subgradient algorithm and a random projection algorithm to distributedly solve the SP over undirected and directed graphs, respectively. Both algorithms are given in an explicit recursive form with simple iterations, which are especially suited for processors with limited computational capability. We show that, if the underlying graph is strongly connected, each node asymptotically computes a common optimal solution to the SP with a convergence rate $O(1/(\sum _{t=1}^k\zeta ^t))$ , where $\lbrace \zeta ^t\rbrace$ is a sequence of appropriately decreasing stepsizes. That is, the RCO is effectively solved in a distributed way. The relations with the existing literature on robust convex programs are thoroughly discussed and an example of robust system identification is included to validate the effectiveness of our distributed algorithms. [ABSTRACT FROM AUTHOR]

Sensors are activated/deactivated according to a sensor activation policy (SAP), which is a decision function whose domain is the language of the system. An SAP is minimal for diagnosability if it is at the point where the system is diagnosable, but any additional deactivation prevents correct system diagnosis. Given that the system is diagnosable when all sensors are always activated, we find in this paper that minimal SAP for diagnosability does not always exist. We therefore develop algorithms to compute a minimal SAP under which the system is pseudodiagnosable. Adhering to such a policy extends the window of opportunity for proper system diagnosis indefinitely, but with the compromise that later policy amendments are allowed. [ABSTRACT FROM AUTHOR]