Search

In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides an upper bound of $O(nmD\log n)$ for the expected convergence time to consensus, where $n$, $m$ and $D$, denote, respectively, the number of nodes, the number of edges, and the diameter of the network. Moreover, the paper shows that the above upper bound is tight up to a factor of $\log n$ for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives an upper bound for the expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier ones given for different quantized consensus protocols over time-varying graphs. [ABSTRACT FROM PUBLISHER]

We continue to investigate the impacts of communication delays on networked control of discrete event systems (DES). Our previous results show that nondeterministic communication delays result in nondeterminism in the languages generated by the controlled system, which makes the networked control problems more complex. In this paper we investigate the language nondeterminism. We define delay observability and delay controllability. If the language to be synthesized is delay observable and delay controllable, we can synthesize a networked supervisor to control the DES such that the language generated by the controlled system is deterministic, that is, we can synthesize a “deterministic” state-estimate-based networked supervisor. We derive algorithms to check delay controllability and delay observability. If the language to be synthesized is not delay observable and/or delay controllable, we can find its infimal delay controllable and delay observable superlanguage and maximal delay controllable and delay observable sublanguages. We develop algorithms to find these superlanguages and sublanguages. All the algorithms proposed in the paper are of polynomial computational complexity. [ABSTRACT FROM PUBLISHER]

This paper addresses the problem of determining the \cal H\infty and \cal H2 norms of 2-D mixed continuous-discrete-time systems. The first contribution is to propose a novel approach based on the use of complex Lyapunov functions with even rational parametric dependence, which searches for upper bounds on the sought norms via linear matrix inequalities (LMIs). The second contribution is to show that the upper bounds provided are nonconservative by using Lyapunov functions in the chosen class with sufficiently large degree. The third contribution is to provide conditions for establishing the tightness of the upper bounds. The fourth contribution is to show how the numerical complexity of the proposed approach can be significantly reduced by proposing a new necessary and sufficient LMI condition for establishing positive semidefiniteness of even Hermitian matrix polynomials. This result is also exploited to derive an improved necessary and sufficient LMI condition for establishing exponential stability of 2-D mixed continuous-discrete-time systems. Some numerical examples illustrate the proposed approach. It is worth remarking that nonconservative LMI methods for determining the \cal H\infty and \cal H2 norms of 2-D mixed continuous-discrete-time systems have not been proposed yet in the literature. [ABSTRACT FROM PUBLISHER]

In this paper, we extend the stability theory on Kalman filtering with intermittent measurements from the scenario of one single sensor to the one of multiple sensors. Consider that a group of sensors take measurement of the states of a process and then send the data to a remote estimator. The estimator receives the measurements intermittently, which may be caused by the fact that the channels have packet dropouts or that the sensors schedule the data transmission stochastically. Based on the received measurements, the estimator computes the estimates of the process states by multi-sensor Kalman filtering. Because of the intermittent measurements, the estimator may be unstable. This stability issue is mainly investigated in this paper. A notion of transmission capacity, which is related to the communication rates of sensors, is proposed. It is shown that the expected estimation error covariance diverges for all feasible communication rates collections of the sensors when the transmission capacity is below a certain value; meanwhile, when the transmission capacity is above another certain value, there exists a feasible communication rates collection such that the expected estimation error covariance is bounded. [ABSTRACT FROM PUBLISHER]

In this paper, we introduce and study the notion of norm-controllability for nonlinear systems. This property captures the responsiveness of a system with respect to applied inputs, which is quantified via the norm of an output. As a main contribution, we obtain several Lyapunov-like sufficient conditions for norm-controllability, some of which are based on higher-order derivatives of a Lyapunov-like function. Various aspects of the proposed concept and the sufficient conditions are illustrated by several examples, including a chemical reactor application. Furthermore, for the special case of linear systems, we establish connections between norm-controllability and standard controllability. [ABSTRACT FROM AUTHOR]

Partially observed Markov decision processes (POMDPs) are an important class of control problems that are ubiquitous in a wide range of fields. Unfortunately, these problems are generally intractable, so, in general, we must be satisfied with suboptimal policies. But how do we evaluate the quality of these policies? This question has been addressed in recent years in the Markov decision process (MDP) literature through the use of information-relaxation-based duality, where the nonanticipativity constraints are relaxed, but a penalty is imposed for violations of these constraints. In this paper, we extend the information relaxation approach to POMDPs. It is of course well known that the belief-state formulation of a POMDP is an MDP, and therefore, the previously developed results for MDPs also apply to POMDPs. Under the belief-state formulation, we use recently developed change-of-measure arguments to solve the so-called inner problems, and we use standard filtering arguments to identify the appropriate Radon–Nikodym derivatives. We also show, however, that dual bounds can also be constructed without resorting to the belief-state formulation. In this case, change-of-measure arguments are required for the evaluation of the so-called dual feasible penalties rather than for the solution of the inner problems. We compare dual bounds for both formulations and argue that, in general, the belief-state formulation provides tighter bounds. The second main contribution of this paper is to show that several value function approximations for POMDPs are in fact supersolutions. This is of interest because it can be particularly advantageous to construct penalties from supersolutions, since absolute continuity (of the change of measure) is no longer required, and therefore, significant variance reduction can be achieved when estimating the duality gap directly. Dual bounds constructed from supersolution-based penalties are also guaranteed to provide tighter bounds than the bounds provided by the supersolutions themselves. We use applications from robotic navigation and telecommunication to demonstrate our results. [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 a bound-based simulation budget allocation (BSBA) procedure for solving ranking and selection (R&S) problems in simulation optimization. For many practical applications, strict bounds on system performances can be obtained through empirical and theoretical approaches. These bounds provide additional information which may help solve R&S problems. In this paper, a new method of objective function estimation is proposed using both bound information and simulation outputs. This new estimation method is demonstrated to be particularly effective. To solve R&S problems, several asymptotic optimal allocation rules are also derived. Using these allocation rules, a BSBA procedure is proposed to achieve high efficiency in identifying the best design. Numerical experiments are provided to examine the performance of the proposed BSBA procedure. The computational results show that BSBA outperforms three compared allocation procedures, especially when bounds are tight or the simulation budget is small. [ABSTRACT FROM AUTHOR]

In this paper, we comment on the algorithm proposed in the paper mentioned in the title to define and construct a graph, called Modified State Class Graph (MSCG), which summarizes all possible evolutions of a Time Petri net. We first show that under the assumptions mentioned in such a paper, the proposed graph could be infinite. Then, we underline the requirement of revising the notation and adding some information on certain edges of the graph. Finally, we remark that the current version of the algorithm does not consider all possible evolutions of the net system. In the final part of the manuscript, we propose a revised algorithm for the definition and construction of the MSCG that overcomes all such limitations. [ABSTRACT FROM AUTHOR]

This paper considers the fully distributed tracking consensus problem for general nonlinear multiagent systems with a leader whose control input is nonzero and bounded. First, a new class of distributed state observer for the leader is proposed without the knowledge of the upper bound of the leader's input. Then, the situations that followers are affected by disturbances with unknown upper bound or disturbances generated by exosystems are investigated. Specifically, two distributed control protocols based on the distributed state observer, neural networks, and adaptive laws are proposed. Finally, simulation examples are provided to illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

This paper studies the distributed event-triggered tracking control problem of general linear multiagent systems with a dynamic leader, whose control input might be nonzero and unknown. The existence of the leader's unknown input renders the network heterogeneous and largely increases the difficulty of designing distributed event-based protocols. To solve this problem, we establish a novel asynchronous edge-based event-triggered mechanism, under which communication is not required from the leader to its out-neighbors (informed followers) or by the edge, unless the embedded triggering functions are triggered. Using this mechanism, we design a static asynchronous edge-based event-triggered protocol and an adaptive one, both of which guarantee the achievement of the leader–follower consensus and the exclusion of the Zeno behavior. Note that the adaptive event-based protocol is fully distributed, requiring no global information of the network topology, such as the network's scale, the smallest nonzero eigenvalue of the Laplacian matrix, and the upper bound of the leader's control input. [ABSTRACT FROM AUTHOR]

This paper addresses the event-triggered tracking for a class of uncertain nonlinear systems. Essentially different from the related works, the nonlinear systems allow serious (parametric) uncertainties, while no further a priori information, excepting some coarse information, is required on the reference signal to be tracked. This makes event-triggered control more challenging, partially because the sampling error cannot be precisely bounded any more. As main contributions of this paper, new adaptive event-triggered tracking schemes are proposed for the systems in two event-triggering architectures with different roles of the event-triggering mechanism on the information transmitting and control computing/updating. Much importantly, a dynamic gain is incorporated in either scheme not only to counteract the serious uncertainties, but also to overcome the bad influence of the sampling error. Based on the dynamic gain, two adaptive event-triggered controllers are designed with distinct event-triggering mechanisms, respectively. Particularly, to ensure application flexibility, one of the triggering mechanisms is rendered relatively independent of the controller signal. The designed event-triggered controllers are shown to achieve the practical tracking for the systems, that is, the prespecified arbitrary tracking accuracy can be guaranteed (a comparable objective to that via continuous-time control), while avoiding infinitely fast sampling/execution. [ABSTRACT FROM AUTHOR]

This paper investigates the impact of quantized inter-agent communications on the asymptotic and transient behavior of gradient-based Nash-seeking algorithms in non-cooperative games. Using the information-theoretic notion of entropy power, we establish a universal lower bound on the asymptotic rate of exponential mean-square convergence to the Nash equilibrium (NE). This bound depends on the inter-agent data rate and the local behavior of the agents' utility functions, and is independent of the quantizer structure. Next, we study transient performance and derive an upper bound on the average time required to settle inside a specified ball around the NE, under uniform quantization. Furthermore, we establish an upper bound on the probability that agents' actions lie outside this ball, and show that this bound decays double-exponentially with time. Finally, we propose an adaptive quantization scheme that allows the gradient algorithm to converge to the NE despite quantized inter-agent communications. [ABSTRACT FROM AUTHOR]

A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behavior. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this paper, we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behavior over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori. [ABSTRACT FROM AUTHOR]

This paper investigates standard $H_\infty$ control of switched systems via dwell-time switchings without posing any internal stability requirements on subsystems of the switched systems. First, a sufficient condition is formed by specifying lower and upper bounds of the dwell time, constraining upper bound of derivative of a Lyapunov function of the active subsystem, and forcing the Lyapunov function values of the overall switched system to decrease at switching times to achieve standard $H_\infty$ control of unforced switched linear systems. Then, in the same framework of the dwell time, sufficient conditions are given for that of the corresponding forced switched linear systems by further designing state feedback controllers. Finally, numerical examples are provided to demonstrate the effectiveness of the proposed results. [ABSTRACT FROM AUTHOR]

This paper introduces a new approach for the synthesis of Markov chains with density safety constraints. Specific safety constraints considered are: (i) Density upper bound constraints; (ii) Bound on the rate of change of density. The proposed approach is based on a new mathematical result that formulates these constraints as linear, and hence convex, inequality constraints. The main contribution of the paper is that the new convex constraints are proved to be equivalent, necessary and sufficient, to the original constraints. This result enables the formulation of the Markov chain synthesis problem as a Linear Matrix Inequality (LMI) optimization problem with additional constraints on the steady state probability distribution, ergodicity, and feasible state transitions. The LMI formulation presents a necessary and sufficient design condition for reversible Markov chains, that is, it is not conservative. When the reversibility is not required, the LMI condition is only sufficient due to the ergodicity constraint. Since LMI problems can be solved to global optimality in polynomial time by using Interior Point Method algorithms, the proposed LMI-based design approach is numerically tractable. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of estimating the position of a scene point from its image projections onto generalized cameras, i.e., cameras that can be modeled by a spherical projection followed by a perspective one. The sought estimate is defined through a geometric criterion, specifically the minimization of the angles between the projections on the sphere of the available image points and the corresponding projections of the estimate. A solution based on convex optimization with linear matrix inequalities (LMIs) is proposed for addressing this problem, which provides a candidate of the sought estimate. Moreover, a condition is provided for establishing exactness of the found candidate, i.e., establishing whether the found candidate is a minimizer of the considered geometric criterion. [ABSTRACT FROM AUTHOR]

Quantum Hamiltonian identification (QHI) is important for characterizing the dynamics of quantum systems, calibrating quantum devices, and achieving precise quantum control. In this paper, an effective two-step optimization (TSO) QHI algorithm is developed within the framework of quantum process tomography. In the identification method, different probe states are input into quantum systems and the output states are estimated using the quantum state tomography protocol via linear regression estimation. The time-independent system Hamiltonian is reconstructed based on the experimental data for the output states. The Hamiltonian identification method has computational complexity $O(d^6)$ , where $d$ is the dimension of the system Hamiltonian. An error upper bound $O(\frac{d^3}{\sqrt{N}})$ is also established, where $N$ is the resource number for the tomography of each output state, and several numerical examples demonstrate the effectiveness of the proposed TSO Hamiltonian identification method. [ABSTRACT FROM AUTHOR]

This paper studies online shortest path routing over multihop networks. Link costs or delays are time varying and modeled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative difference of expected delay) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decisions. For each scenario, we derive a tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. Three algorithms, with a tradeoff between computational complexity and performance, are proposed. The regret upper bounds of these algorithms improve over those of the existing algorithms. We also assess numerically the performance of the proposed algorithms and compare it to that of existing algorithms. [ABSTRACT FROM PUBLISHER]

Most of time-varying systems in fusion estimation are generally modeled without bounded noises. In this paper, we study the distributed fusion estimation problem for networked time-varying systems with bounded noises, where the resource constraints (i.e., bandwidth or energy) and quantization effect are described by a unified model. A new local estimator with time-varying gain is designed by solving a class of convex optimization problems such that the square error of the estimator is bounded. When each local estimate is transmitted to the fusion center over communication networks, the selection probability criterion is derived such that the mean square error of the each compensating state estimate is bounded. Then, a convex optimization problem on the design of an optimal weighting fusion criterion is established in terms of linear matrix inequalities, which can be solved by standard software packages. Target tracking system with time-varying sampling period is given to show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

We investigate the supervisor synthesis problem for centralized partially-observed discrete event systems subject to safety specifications. It is well known that this problem does not have a unique supremal solution in general. Instead, there may be several incomparable locally maximal solutions. One then needs a mechanism to select one locally maximal solution. Our approach in this paper is to consider a lower bound specification on the controlled behavior, in addition to the upper bound for the safety specification. This leads to a generalized supervisory control problem called the range control problem. While the upper bound captures the (prefix-closed) legal behavior, the lower bound captures the (prefix-closed) minimum required behavior. We provide a synthesis algorithm that solves this problem by effectively constructing a maximally-permissive safe supervisor that contains the required lower bound behavior. This is the first algorithm with such properties, as previous works solve either the maximally-permissive safety problem (with no lower bound), or the lower bound containment problem (without maximal permissiveness). [ABSTRACT FROM AUTHOR]

This paper addresses the design problem of robust controllers, which are composed of state observers and state-feedback controllers, for linear time-invariant parameter-dependent (LTIPD) systems. The design problems for continuous-time and discrete-time LTIPD systems are both addressed. The state-space matrices of the LTIPD systems are supposed to be multiaffine with respect to time-invariant parameters, and the supposed uncertainty blocks, which have an ability to define various design requirements, are characterized by scaling matrices, e.g.,  $D$ - and $(D, G)$ -scaling. We propose a tractable condition for the simultaneous design of robust controllers and scaling matrices via dilated linear matrix inequality  technique. A numerical example demonstrates the effectiveness of our method. [ABSTRACT FROM AUTHOR]

This paper proposes an efficient marking estimation method for a subclass of time labeled Petri nets (TLPNs), in which each transition is associated with an infinite upper bound delay. The unobservable subnet of the considered subclass of TLPNs is backward-conflict-free, and all the output transitions of each conflict place are observable. The highlight of this method is that the markings set consistent with a given observation can be determined by a linear algebraic system based on the so-called slow-bound marking and fast-bound marking pairs. An algorithm to compute an online estimator is provided, and an example is given. By this method, the exhaustive construction of the full state space including the state class graph is avoided. This approach provides guidelines of sensor deployment in the design stage so that the online marking estimation problem can be efficiently solved. [ABSTRACT FROM AUTHOR]

Randomized optimization is an established tool for control design with modulated robustness. While for uncertain convex programs there exist efficient randomized approaches, this is not the case for non-convex problems. Methods based on statistical learning theory are applicable to non-convex problems, but they usually are conservative in achieving the desired probabilistic guarantees. In this paper, we derive a novel scenario approach for a wide class of random non-convex programs, with a sample complexity similar to that of uncertain convex programs and with probabilistic guarantees that hold not only for the optimal solution of the scenario program, but for all feasible solutions inside a set of a-priori chosen complexity. We also address measure-theoretic issues for uncertain convex and non-convex programs. Among the family of non-convex control-design problems that can be addressed via randomization, we apply our scenario approach to stochastic model predictive control for chance constrained nonlinear control-affine systems. [ABSTRACT FROM PUBLISHER]

Information relaxation and duality in Markov decision processes have been studied recently by several researchers with the goal to derive dual bounds on the value function. In this paper we extend this dual formulation to controlled Markov diffusions: in a similar way we relax the constraint that the decision should be made based on the current information and impose a penalty to punish the access to the information in advance. We establish the weak duality, strong duality and complementary slackness results in a parallel way as those in Markov decision processes. We further explore the structure of the optimal penalties and expose the connection between the optimal penalties for Markov decision processes and controlled Markov diffusions. We demonstrate the use of this dual representation in a classic dynamic portfolio choice problem through a new class of penalties, which require little extra computation and produce small duality gap on the optimal value. [ABSTRACT FROM PUBLISHER]

Stability is of fundamental importance to the design and application of control systems, in which stable equilibrium points and the neighboring points can have various interesting physical implications. In the paper, we derive a lower bound and an upper bound on the number of neighboring stable equilibrium points in the spatially-periodic nonlinear dynamical systems. It is shown that, in such an $n$-dimensional system, there are at least $2n$ neighboring stable equilibrium points. Meanwhile, an upper bound on the number of neighboring stable equilibrium points is derived. Some applications of these analytical results are illustrated. [ABSTRACT FROM AUTHOR]

In this note, we investigate the stabilization of discrete-time linear systems with an unknown time-varying delay. Existing literature on the stabilization of time-delay systems require some knowledge, such as an upper bound, of the delay. In this paper, by proposing a switched low-gain feedback control law, we are able to achieve asymptotic stabilization of the system without any knowledge of the delay. In addition, the proposed switched low-gain feedback law also significantly improves the closed-loop system performance in terms of overshoot and convergence speed in comparison with the traditional fixed gain design. Simulation study illustrates the effectiveness of our theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, we combine a global differentiator based on higher-order sliding modes (HOSM) and dynamic gains with classical model reference adaptive control (MRAC) schemes to solve the relevant and yet open problem of trajectory tracking via output feedback of uncertain plants with arbitrary relative degree in a simple-closed form for the control design. The gains of the differentiator are adapted through state-norm observers for the unmeasured state, whereas the control parametrization explores the input–output filters commonly used in the MRAC design. Global asymptotic stability and robust exact tracking are rigorously demonstrated. Simulations highlight the claimed properties as well as the remarkable simplicity of the proposed adaptive control system using robust exact differentiators when compared to more involved alternatives found in standard approaches. The theoretical results are also illustrated with an application to bilateral teleoperation. [ABSTRACT FROM AUTHOR]

We consider the Hegselmann-Krause model for opinion dynamics and study the evolution of the system under various settings. We first analyze the termination time of the synchronous Hegselmann-Krause dynamics in arbitrary finite dimensions and show that the termination time in general only depends on the number of agents involved in the dynamics. To the best of our knowledge, that is the sharpest bound for the termination time of such dynamics that removes dependency of the termination time from the dimension of the ambient space, and connects the convergence speed of the dynamics to the eigenvalues of the adjacency matrix of the connectivity graph in the Hegselmann-Krause dynamics. This answers an open question in the paper by Bhattacharyya et al. on how to obtain a tighter upper bound for the termination time. Furthermore, we study the asynchronous Hegselmann-Krause model from a novel game-theoretic approach and show that the evolution of an asynchronous Hegselmann-Krause model is equivalent to a sequence of best response updates in a well-designed potential game. We then provide a polynomial upper bound for the expected time and expected number of switching topologies until the dynamic reaches an arbitrarily small neighborhood of its equilibrium points, provided that the agents update uniformly at random. This is a step toward analysis of heterogeneous Hegselmann-Krause dynamics. Finally, we consider the heterogeneous Hegselmann-Krause dynamics and provide a necessary condition for the finite termination time of such dynamics. In particular, we sketch some future directions toward more detailed analysis of the heterogeneous Hegselmann-Krause model. [ABSTRACT FROM AUTHOR]

In this paper, we consider a similarity control problem for the plant and the specification modeled as nondeterministic automata. This problem requires us to synthesize a nondeterministic supervisor such that the supervised plant is simulated by the specification. We show that a state-controllable subautomaton of the synchronous composition of the observer automaton of the plant and the specification can be used as a solution to the similarity control problem. It is desirable that a supervisor be as permissive as possible. Thus, to synthesize a similarity enforcing supervisor, we construct the largest state-controllable subautomaton of the synchronous composition of the observer automaton of the plant and the specification. [ABSTRACT FROM AUTHOR]

In recent years, information relaxation and duality in dynamic programs have been studied extensively, and the resulted primal-dual approach has become a powerful procedure in solving dynamic programs by providing lower-upper bounds on the optimal value function. Theoretically, with the so-called value-based optimal dual penalty, the optimal value function could be recovered exactly via strong duality. However, in practice, obtaining tight dual bounds usually requires good approximations of the optimal dual penalty, which could be time consuming if analytical computation is not possible and nested simulation has to be used to estimate the conditional expectations inside the dual penalty. In this paper, we will develop a framework of a regression approach to approximating the optimal dual penalty in a nonnested manner, by exploring the structure of the function space consisting of all feasible dual penalties. The resulted approximations maintain to be feasible dual penalties, and thus yielding valid dual bounds on the optimal value function. We show that the proposed framework is computationally efficient, and the resulted dual penalties lead to numerically tractable dual problems. Finally, we apply the framework to a high-dimensional dynamic trading problem to demonstrate its effectiveness in solving the dual problems of complex dynamic programs. [ABSTRACT FROM AUTHOR]

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]

This paper considers the discrete-time version of Altafini's model for opinion dynamics in which the interaction among a group of agents is described by a time-varying signed digraph. Prompted by an idea from [3], exponential convergence of the system is studied using a graphical approach. Necessary and sufficient conditions for exponential convergence with respect to each possible type of limit states are provided. Specifically, under the assumption of repeatedly jointly strong connectivity, it is shown that 1) a certain type of two-clustering will be reached exponentially fast for almost all initial conditions if, and only if, the sequence of signed digraphs is repeatedly jointly structurally balanced corresponding to that type of two-clustering; 2) the system will converge to zero exponentially fast for all initial conditions if, and only if, the sequence of signed digraphs is repeatedly jointly structurally unbalanced. An upper bound on the convergence rate is provided. The results are also extended to the continuous-time Altafini model. [ABSTRACT FROM PUBLISHER]

This paper addresses the controllability of a class of antagonistic multiagent networks with both positive and negative edges. All the agents of the multiagent network run a consensus algorithm using a signed Laplacian. Based on the generalized equitable partition, we propose a graph-theoretic characterization of an upper bound on the controllable subspace. Then, we provide a necessary condition for the controllability of the system and give an algorithm to compute the partition. Furthermore, we prove that for a structurally balanced network, the controllability is equivalent to that of the corresponding all-positive network, if the leaders are chosen from the same vertex set. Several examples are given to illustrate these results. [ABSTRACT FROM AUTHOR]

Secure state estimation is the problem of estimating the state of a dynamical system from a set of noisy and adversarially corrupted measurements. Intrinsically a combinatorial problem, secure state estimation has been traditionally addressed either by brute force search, suffering from scalability issues, or via convex relaxations, using algorithms that can terminate in polynomial time but are not necessarily sound. In this paper, we present a novel algorithm that uses a satisfiability modulo theory approach to harness the complexity of secure state estimation. We leverage results from formal methods over real numbers to provide guarantees on the soundness and completeness of our algorithm. Moreover, we discuss its scalability properties, by providing upper bounds on the runtime performance. Numerical simulations support our arguments by showing an order of magnitude decrease in execution time with respect to alternative techniques. Finally, the effectiveness of the proposed algorithm is demonstrated by applying it to the problem of controlling an unmanned ground vehicle. [ABSTRACT FROM AUTHOR]

This technical note develops observer design techniques in a unified framework for both time invariant and parameter varying Lipschitz nonlinear systems that are differentiable w.r.t. state variables. First, a new sufficient condition for asymptotic convergence is developed for Arcak's two-DOF nonlinear observer for time-invariant nonlinear systems. In addition to ensuring asymptotic convergence, extension of this observer design technique to optimization of a L2 performance criterion is presented, which improves disturbance rejection performance of the observer. Next, augmentation of this technique to parameter varying nonlinear (PVNL) systems is developed. Different from methods suggested in the LPV literature, a simple but non-conservative finite dimensional relaxation method for quadratic parameter dependent LMIs is presented. These results constitute perhaps the first systematic observer design methodology in literature for PVNL systems. Finally, the performance of the developed observers is evaluated for estimation of slip angle using the commercial vehicle dynamics software CARSIM. Unlike previous results which use a LTI or a time invariant nonlinear model for observer design, this technical note presents a PVNL observer guaranteed to work with continuously varying velocity of the vehicle. [ABSTRACT FROM PUBLISHER]

We consider the quantized consensus problem on undirected time-varying connected graphs with $n$ nodes, and devise a protocol with fast convergence time to the set of consensus points. Specifically, we show that when the edges of each network in a sequence of connected time-varying networks are activated based on Poisson processes with Metropolis rates, the expected convergence time to the set of consensus points is at most O(n^{2}\log^{2}n), where each node performs a constant number of updates per unit time. [ABSTRACT FROM AUTHOR]

In this paper, we present a method for reducing a regular, discrete-time Markov chain (DTMC) to another DTMC with a given, typically much smaller number of states. The cost of reduction is defined as the Kullback–Leibler divergence rate between a projection of the original process through a partition function and a DTMC on the correspondingly partitioned state space. Finding the reduced model with minimal cost is computationally expensive, as it requires an exhaustive search among all state space partitions, and an exact evaluation of the reduction cost for each candidate partition. Our approach deals with the latter problem by minimizing an upper bound on the reduction cost instead of minimizing the exact cost. The proposed upper bound is easy to compute and it is tight if the original chain is lumpable with respect to the partition. Then, we express the problem in the form of information bottleneck optimization, and propose using the agglomerative information bottleneck algorithm for searching a suboptimal partition greedily, rather than exhaustively. The theory is illustrated with examples and one application scenario in the context of modeling bio-molecular interactions. [ABSTRACT FROM AUTHOR]

We analyze a class of distributed quantized consensus algorithms for arbitrary static networks. In the initial setting, each node in the network has an integer value. Nodes exchange their current estimate of the mean value in the network, and then update their estimation by communicating with their neighbors in a limited capacity channel in an asynchronous clock setting. Eventually, all nodes reach consensus with quantized precision. We analyze the expected convergence time for the general quantized consensus algorithm proposed by Kashyap et al. (“Quantized consensus,” Automatica, 2007). We use the theory of electric networks, random walks, and couplings of Markov chains to derive an O(N^3 \log N) upper bound for the expected convergence time on an arbitrary graph of size $N$, improving on the state of art bound of O(N^{5} ) for quantized consensus algorithms. Our result is not dependent on graph topology. Example of complete graphs is given to show how to extend the analysis to graphs of given topology. This is consistent with the analysis in “Convergence speed of binary interval consensus,” (M. Draief and M. Vojnovic, SIAM J. Control and Optimization, 2012. [ABSTRACT FROM AUTHOR]

We study a notion of estimation entropy for continuous-time nonlinear systems, formulated in terms of the number of system trajectories that approximate all other trajectories up to an exponentially decaying error. We also consider an alternative definition of estimation entropy, which uses approximating functions that are not necessarily trajectories of the system, and show that the two entropy notions are equivalent. We establish an upper bound on the estimation entropy in terms of the sum of the desired convergence rate and an upper bound on the matrix measure of the Jacobian, multiplied by the system dimension. A lower bound on the estimation entropy is developed as well. We then turn our attention to state estimation and model detection with quantized and sampled state measurements. We describe an iterative procedure that uses such measurements to generate state estimates that converge to the true state at the desired exponential rate. The average bit rate utilized by this procedure matches the derived upper bound on the estimation entropy, and no other algorithm of this type can perform the same estimation task with bit rates lower than the estimation entropy. Finally, we discuss an application of the estimation procedure in determining, from the quantized state measurements, which of two competing models of a dynamical system is the true model. We show that under a mild assumption of “exponential separation” of the candidate models, detection always happens in finite time. [ABSTRACT FROM AUTHOR]

The slow state variables feedback stabilization problem for semi-Markov jump discrete-time systems with slow sampling singular perturbations is discussed in this work. A new fairly comprehensive system model, semi-Markov jump system with singular perturbations, which is more general than Markov jump model, is employed to describe the phenomena of random abrupt changes in structure and parameters of the systems. Based on a slow state variables feedback control scheme, a novel technique to design the desired controller is presented and the allowed maximum of singular perturbation parameter can be calculated. With the help of the discrete-time semi-Markov kernel approach, some sojourn-time-dependent and less-conservative sufficient conditions are established via a novel matrix decoupling technique to ensure the solvability of the problem to be addressed. Finally, an illustrative example is given to show the superiority and usefulness of the proposed method. [ABSTRACT FROM AUTHOR]

In a cyber-physical system, security problems are of vital importance as the failure of such system can have catastrophic effects. Detection methods can be employed to sense the existence of an attack. In a previous study of an attack on the controller while avoiding detection in scalar systems under a certain control assumption, the notion of $\epsilon$-stealthiness was introduced and the strength of $\epsilon$- stealthy attacks was fully characterized. We generalize to the vector system and prove the cases in which we show that the limitations of $\epsilon$-stealthy attack do not extend, in the sense that $\epsilon$- stealthy can inflict damage of arbitrary magnitude to a vector system. [ABSTRACT FROM PUBLISHER]

This technical note focuses on a class of switched nonlinear systems with unstable modes and switching uncertainties. Both prescribed switching instants and switching sequence of the nominal switching signal would change. Two novel indexes named time changing ratios and mode changing ratios are proposed, based on which several conditions that fully utilize the trade-off among stable and unstable modes are established to achieve the robust stability of the switched system. An example of multi-agent systems illustrates the efficiency of the new results. [ABSTRACT FROM PUBLISHER]

Sample complexity bounds are a common performance metric in the reinforcement learning literature. In the discounted cost, infinite horizon setting, all of the known bounds can be arbitrarily large, as the discount factor approaches unity. These results seem to imply that a very large number of samples is required to achieve an epsilon-optimal policy. The objective of the present work is to introduce a new class of algorithms that have sample complexity uniformly bounded over all discount factors. One may argue that this is impossible, due to a recent min–max lower bound. The explanation is that these prior bounds concern value function approximation and not policy approximation. We show that the asymptotic covariance of the tabular Q-learning algorithm with an optimized step-size sequence is a quadratic function of a factor that goes to infinity, as discount factor approaches 1; an essentially known result. The new relative Q-learning algorithm proposed here is shown to have asymptotic covariance that is uniformly bounded over all discount factors. [ABSTRACT FROM AUTHOR]

This technical note studies fixed-time consensus tracking with disturbance rejection for first-order multiagent systems. The communication topology among the leader and followers contains a directed spanning tree. The control input to the leader is time-varying and unknown to the followers, except that its upper bound is known a priori. A novel fixed-time protocol is devised based on discontinuous and nonlinear control. A fixed-time stability analysis for consensus tracking with disturbance rejection is completed as a one-step control process using nonsmooth analysis. An upper bound estimate for the settling time, independent of the initial conditions, is aesthetically pleasing, in comparison to previous results derived based on two-step control design technique using sliding modes. Finally, a numeric example confirms the theoretical results. [ABSTRACT FROM AUTHOR]

This article aims to solve the problem of decentralized event-based finite-time control for a class of high-order interconnected nonlinear systems with an asymmetric output constraint. In order to achieve finite-time stability and reduce the update frequency of the controller, a novel controller and its event-trigger mechanism is proposed by adding a power integral technique and utilizing sign function. To fulfill the requirement of asymmetric output constraints, an asymmetric barrier Lyapunov function (BLF) is constructed, which is different from tan-type and log-type BLFs. Based on the contradictory idea and finite-time stability theory, it is proved that there is no Zeno phenomenon under this event-trigger mechanism and all state variables of the closed-loop system attenuate to the origin in the finite-time while the output signals never violate the constraint. Furthermore, the result in this article is expanded to fixed-time control. Finally, a simulation example is given to demonstrate the effectiveness of the presented strategy. [ABSTRACT FROM AUTHOR]

In Niu and Ho (2014), an interesting issue was investigated on how an existing controller can still achieve the same control performance under the quantization case by designing the online adjusting strategy for the quantizer’s parameter. However, the above-mentioned work ignored the limitation of the coding length in the practical transmitting procedure such that the desirable performance may not be achieved due to the inevitable coding errors. Hence, this article will further consider the above-mentioned issue under the limited coding length. Different coding rules are designed for the quantized states and the adaptive quantizer’s parameters. The minimum bound of coding errors is explicitly given, which are dependent on the coding length and the coding range. Moreover, the relation between the coding length and the control performance is established, that is, the coding length has a direct effect on the convergent upper bound of the system state and the sliding domain around the specified sliding surface. Finally, an operational amplifier circuit system is provided to verify the proposed method. [ABSTRACT FROM AUTHOR]

Indivisible resource allocation motivates us to study the matrix completion concerning the class of (0,1)-matrices with prescribed row/column sums and preassigned zeros. We illustrate and generalize the (0,1)-matrix completion in the following two scenarios: a demand-response application involving nonnegative integer matrices with different bounds across rows and an edge caching matching problem allowing row and column sums to vary within separately designated bounds. The applications require analytic characterizations of the supply adequacy and cause large-scale matrix completion instances. Remarkably, we derive a structure tensor and use its nonnegativity to establish a necessary and sufficient condition under which the considered matrix class is nonempty. The tensor condition can characterize the adequacy of a supply for a prescribed demand and facilitate identifying the minimum supplement to the supply so that the augmented supply becomes adequate when the adequacy gap is nonzero. Notably, we design a tensor-based combinatorial algorithm to construct a required matrix, representing a feasible resource allocation. Numerical simulations justify the efficiency of our approach. [ABSTRACT FROM AUTHOR]

This technical note investigates distributed containment control for a single-integrator continuous-time multi-agent system with a limited communication data rate. Network topology is a directed communication graph. The containment control with quantized communication for each follower is designed using only its neighbour's quantized information so that all followers move into the convex hull spanned by the leaders. Necessary and sufficient criteria which guarantee achievement of containment consensus are given if the communication data rates are unfixed or fixed. Under a given bound on communication data rate, an algorithm is established to achieve the containment consensus. Finally, all the theoretical results are illustrated by numerical simulations. [ABSTRACT FROM AUTHOR]

Tackling large approximate dynamic programming or reinforcement learning problems requires methods that can exploit regularities of the problem in hand. Most current methods are geared towards exploiting the regularities of either the value function or the policy. We introduce a general classification-based approximate policy iteration (CAPI) framework that can exploit regularities of both. We establish theoretical guarantees for the sample complexity of CAPI-style algorithms, which allow the policy evaluation step to be performed by a wide variety of algorithms, and can handle nonparametric representations of policies. Our bounds on the estimation error of the performance loss are tighter than existing results. [ABSTRACT FROM AUTHOR]