Search

We study the computational complexity of a general consensus problem for switched systems. A set of n × n stochastic matrices {P 1 , …, P k } is a consensus set if for every switching map τ : ℕ → {1, …, k} and for every initial state x(0), the sequence of states defined by x(t + 1) = P τ(t) x(t) converges to a state whose entries are all identical. We show in this paper that, unless P = NP, the problem of determining if a set of matrices is a consensus set cannot be decided in polynomial-time. As a consequence, unless P = NP, it is not possible to give efficiently checkable necessary and sufficient conditions for consensus. This provides a possible explanation for the absence of such conditions in the current literature on consensus. On the positive side, we provide a simple algorithm which checks whether {P 1 , …, P k } is a consensus set in a number of operations which scales as a doubly exponential in n.

We study a simple continuous-time multi-agent system related to Krause's model of opinion dynamics: each agent holds a real value, and this value is continuously attracted by every other value differing from it by less than 1, with an intensity proportional to the difference.

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms [2]–[6], Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting [7], this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging [5], except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.

Researchers have been unable to predict the large-scale features of aggregate social networks. We analyze the anonymous communications patterns of 2.5 million customers of a Belgian mobile phone operator. With these communications, we construct the social network of the customers, that we call microscopic network. Grouping customers together by billing address city, we obtain a social network of cities, which we call the macroscopic network, is built from 571 towns and cities in Belgium. Using the mobile phone network, we are able to show that the macroscopic network has both a degree distribution and edge weight distribution with lognormal characteristics. We find that inter-city communications can be characterized by a gravity model: the intensity of communication between two cities is proportional to the product of the two populations divided by the square of the distance between them. Furthermore, we observe that intra-urban communications scale superlinearly with city population.

We consider a simple dynamical model of agents distributed on the real line. The agents have a limited vision range and they synchronously update their positions by moving to the average position of the agents that are within their vision range. This dynamical model was initially introduced in the social science literature as a model of opinion dynamics and is known there as the “Krause model”. It gives rise to surprising and partly unexplained dynamics that we describe and discuss in this paper. One of the central observations is the 2R-conjecture: when sufficiently many agents are distributed on the real line and have their position evolve according to the above dynamics, the agents eventually merge into clusters that have inter-cluster distances roughly equal to 2R (R is the vision range of the agents). This observation is supported by extensive numerical evidence and is robust under various modifications of the model. It is easy to see that clusters need to be separated by at least R. On the other hand, the unproved bound 2R that is observed in practice can probably only be obtained by taking into account the specifics of the model's dynamics. In this paper, we study these dynamics and consider a number of issues related to the 2R conjecture that explicitly uses the model's dynamics. In particular, we provide bounds for the vision range that lead all agents to merge into only one cluster, we analyze the relations between agents on finite and infinite intervals, and we introduce a notion of equilibrium stability for which clusters of equal weights need to be separated by at least 2R to be stable. These results, however, do not prove the conjecture. To understand the system behavior for a large agent density, we also consider a version of the model that involves a continuum of agents. We study properties of this continuous model and of its equilibria, and investigate the connections between the discrete and continuous versions.

Motivated by [1], [2] and [3], we consider here formations of autonomous agents in a 2-dimensional space. Each agent tries to maintain its distances toward a pre-specified group of other agents constant, and the problem is to determine if one can guarantee that the structure of the formation will persist, i.e., if the distance between any pair of agents will remain constant. A natural way to represent such a formation is to use a directed graph. We provide a theoretical framework for this problem, and give a formal definition of persistent graphs (a graph is persistent if almost all corresponding agents formations persist). Note that although persistence is related to rigidity (concerning which much is known [4]), these are two distinct notions. We then derive various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define the notion of minimal persistence (persistence with least number of edges), and eventually, we apply these notion to the interesting special case of cycle-free graphs.

We discuss an old distributed algorithm for reaching consensus that has received a fair amount of recent attention. In this algorithm, a number of agents exchange their values asynchronously and form weighted averages with (possibly outdated) values possessed by their neighbors. We overview existing convergence results, and establish some new ones, for the case of unbounded intercommunication intervals.

The authors disprove conjectures on simultaneous stabilizability conditions by showing that, unlike the case of two plants, the existence of a simultaneous stabilizing controller for more than two plants is not guaranteed by the existence of a controller such that the closed loops have no real unstable poles. An example of a plant which has the even interlacing property but which is not stabilizable by a bistable controller is presented. >

We analyse the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalised spectral radii of two integer matrices are not approximable in polynomial time, and that, two related quantities-the lower spectral radius and the largest Lyapunov exponent-are not algorithmically approximable. As a corollary of these results we show that: 1) the problem of deciding if all possible products of two given matrices are stable is NP-hard, 2) the problem of deciding if at, least one product of two given matrices is stable is undecidable.

The authors study the following problem: 'under what condition(s) is it possible to find a single controller which stabilizes k single-input-single-output (SISO) linear time-invariant plants p/sub i/(s) (i=l,. . .,k)?'. They show that the problem admits a solution if and only if an avoidance condition in the complex plane is satisfied, and this result is used to derive a sufficient condition for k plants to be simultaneously stabilizable. >

The use of an identified model for the design of a feedback controller for an actual plant introduces strictures on the quality of the model which are different from those pertaining in open loop identification. For example, a model P/spl circ/ is admissible for the design of a controller for the actual plant P only if the pair (P/spl circ/, P) is simultaneously stabilizable. This paper addresses the question of the quality of a model to be used for control design, by analysing the interplay between the plant P, the designed closed loop system T and the set of admissible models {P/spl circ/}. For given P and T we characterize the set of admissible models {P/spl circ/}, where admissible means that a controller designed from P/spl circ/ and T yields a stable closed loop. Necessary conditions on (P, T) are derived for this set to be nonempty.

We show that the simultaneous stabilization question: When are three linear systems stabilizable by the same controller? cannot be solved by a semialgebraic set description nor be answered by computational machines.

In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable (NP-hard). As a special case, we consider a class of "hybrid" systems in which the state space is partitioned into two halfspaces. and the dynamics in each halfspace correspond to a different linear system.