M. -A. Belabbas

Xudong Chen, M. -A. Belabbas, Tamer Basar

We consider the problem of estimating the states of weakly coupled linear systems from sampled measurements. We assume that the total capacity available to the sensors to transmit their samples to a network manager in charge of the estimation is bounded above, and that each sample requires the same amount of communication. Our goal is then to find an optimal allocation of the capacity to the sensors so that the average estimation error is minimized. We show that when the total available channel capacity is large, this resource allocation problem can be recast as a strictly convex optimization problem, and hence there exists a unique optimal allocation of the capacity. We further investigate how this optimal allocation varies as the available capacity increases. In particular, we show that if the coupling among the subsystems is weak, then the sampling rate allocated to each sensor is nondecreasing in the total sampling rate, and is strictly increasing if and only if the total sampling rate exceeds a certain threshold.

M. -A. Belabbas

In this paper, we develop new methods for the analysis of decentralized control systems and we apply them to formation control problems. The basic set-up consists of a system with multiple agents corresponding to the nodes of a graph whose edges encode the information that is available to the agents. We address the question of whether the information flow defined by the graph is sufficient for the agents to accomplish a given task. Formation control is concerned with problems in which agents are required to stabilize at a given distance from other agents. In this context, the graph of a formation encodes both the information flow and the distance constraints, by fixing the lengths of the edges. A formation is said to be rigid if it cannot be continuously deformed with the distance constraints satisfied; a formation is minimally rigid if no distance constraint can be omitted without the formation losing its rigidity. Hence, the graph underlying minimally rigid formation provides just enough constraints to yield a rigid formation. An open question we will settle is whether the information flow afforded by a minimally rigid graph is sufficient to insure global stability. We show that the answer is negative in the case of directed information flow. In this first part, we establish basic properties of formation control in the plane. Formations and the associated control problems are defined modulo rigid transformations. This fact has strong implications on the geometry of the space of formations and on the feedback laws, since they need to respect this invariance. We study both aspects here. We show that the space of frameworks of n agents is CP(n-2) x (0,\infty). We then illustrate how the non-trivial topology of this space relates to the parametrization of the formation by inter-agent distances.

M. -A. Belabbas

In formation control, an ensemble of autonomous agents is required to stabilize at a given configuration in the plane, doing so while agents are allowed to observe only a subset of the ensemble. As such, formation control provides a rich class of problems for decentralized control methods and techniques. Additionally, it can be used to model a wide variety of scenarios where decentralization is a main characteristic. We introduce here some mathematical background necessary to address questions of stability in decentralized control in general and formation control in particular. This background includes an extension of the notion of global stability to systems evolving on manifolds and a notion of robustness of feedback control for nonlinear systems. We then formally introduce the class of formation control problems, and summarize known results.

M. -A. Belabbas

Given an ensemble of autonomous agents and a task to achieve cooperatively, how much do the agents need to know about the state of the ensemble and about the task in order to achieve it? We introduce new methods to understand these aspects of decentralized control. Precisely, we introduce a framework to capture what agents with partial information can achieve by cooperating and illustrate its use by deriving results about global stabilization of directed formations. This framework underscores the need to differentiate the knowledge an agent has about the task to accomplish from the knowledge an agent has about the current state of the system. The control of directed formations has proven to be more difficult than initially thought, as is exemplified by the lack of global result for formations with n \geq 4 agents. We established in part I that the space of planar formations has a non-trivial global topology. We propose here an extension of the notion of global stability which, because it acknowledges this non-trivial topology, can be applied to the study of formation control. We then develop a framework that reduces the question of whether feedback with partial information can stabilize the system to whether two sets of functions intersect. We apply this framework to the study of a directed formation with n = 4 agents and show that the agents do not have enough information to implement locally stabilizing feedback laws. Additionally, we show that feedback laws that respect the information flow cannot stabilize a target configuration without stabilizing other, unwanted configurations.

M. -A. Belabbas

We introduce and analyze a model for decentral- ized control. The model is broad enough to include problems such as formation control, decentralization of the power grid and flocking. The objective of this paper is twofold. First, we show how the issue of decentralization goes beyond having agents know only part of the state of the system. In fact, we argue that a complete theory of decentralization should take into account the fact that agents can be made aware of only part of the global objective of the ensemble. A second contribution of this paper is the introduction of a rigorous definition of information flow for a decentralized system: we show how to attach to a general nonlinear decentralized system a unique information flow graph that is an invariant of the system. In order to address some finer issues in decentralized system, such as the existence of so-called "information loops", we further refine the information flow graph to a simplicial complex-more precisely, a Whitney complex. We illustrate the main results on a variety of examples.

M. -A. Belabbas

Formation control is concerned with the design of control laws that stabilize agents at given distances from each other, with the constraint that an agent's dynamics can depend only on a subset of other agents. When the information flow graph of the system, which encodes this dependency, is acyclic, simple control laws are known to globally stabilize the system, save for a set of measure zero of initial conditions. The situation has proven to be more complex when the graph contains cycles; in fact, with the exception of the cyclic formation with three agents, which is stabilized with laws similar to the ones of the acyclic case, very little is known about formations with cycles. Moreover, all of the control laws used in the acyclic case fail at stabilizing more complex cyclic formations. In this paper, we explain why this is the case and show that a large class of planar formations with cycles cannot be globally stabilized, even up to sets of measure zero of initial conditions. The approach rests on relating the information flow to singularities in the dynamics of formations. These singularities are in turn shown to make the existence of stable configurations that do not satisfy the prescribed edge lengths generic.

Xudong Chen, M. -A. Belabbas

We consider the actuator placement problem for linear systems. Specifically, we aim to identify an actuator which requires the least amount of control energy to drive the system from an arbitrary initial condition to the origin in the worst case. Said otherwise, we investigate the minimax problem of minimizing the control energy over the worst possible initial conditions. Recall that the least amount of control energy needed to drive a linear controllable system from any initial condition on the unit sphere to the origin is upper-bounded by the inverse of the smallest eigenvalue of the associated controllability Gramian, and moreover, the upper-bound is sharp. The minimax problem can be thus viewed as the optimization problem of minimizing the upper-bound via the placement of an actuator. In spite of its simple and natural formulation, this problem is difficult to solve. In fact, properties such as the stability of the system matrix, which are not related to controllability, now play important roles. We focus in this paper on the special case where the system matrix is positive definite. Under this assumption, we are able to provide a complete solution to the optimal actuator placement problem and highlight the difficulty in solving the general problem.

Xudong Chen, Ji Liu, M. -A. Belabbas et al.

We consider in this paper a networked system of opinion dynamics in continuous time, where the agents are able to evaluate their self-appraisals in a distributed way. In the model we formulate, the underlying network topology is described by a rooted digraph. For each ordered pair of agents $(i,j)$, we assign a function of self-appraisal to agent $i$, which measures the level of importance of agent $i$ to agent $j$. Thus, by communicating only with her neighbors, each agent is able to calculate the difference between her level of importance to others and others' level of importance to her. The dynamical system of self-appraisals is then designed to drive these differences to zero. We show that for almost all initial conditions, the trajectory generated by this dynamical system asymptotically converges to an equilibrium point which is exponentially stable.

M. -A. Belabbas

An observer is an estimator of the state of a dynamical system from noisy sensor measurements. The need for observers is ubiquitous, with applications in fields ranging from engineering to biology to economics. The most widely used observer is the Kalman filter, which is known to be the optimal estimator of the state when the noise is additive and Gaussian. Because its performance is limited by the sensors to which it is paired, it is natural to seek an optimal sensor for the Kalman filter. The problem is however not convex and, as a consequence, many ad hoc methods have been used over the years to design sensors. We show in this paper how to characterize and obtain the optimal sensor for the Kalman filter. Precisely, we exhibit a positive definite operator which optimal sensors have to commute with. We furthermore provide a gradient flow to find optimal sensors, and prove the convergence of this gradient flow to the unique minimum in a broad range of applications. This optimal sensor yields the lowest possible estimation error for measurements with a fixed signal to noise ratio. The results presented here also apply to the dual problem of optimal actuator design.

Xudong Chen, M. -A. Belabbas, Tamer Basar

In this paper, we investigate the controllability of a class of formation control systems. Given a directed graph, we assign an agent to each of its vertices and let the edges of the graph describe the information flow in the system. We relate the strongly connected components of this graph to the reachable set of the formation control system. Moreover, we show that the formation control model is approximately path-controllable over a path-connected, open dense subset as long as the graph is weakly connected and satisfies some mild assumption on the numbers of vertices of the strongly connected components.

Xudong Chen, M. -A. Belabbas, Tamer Basar

A consensus system is a linear multi-agent system in which agents communicate to reach a so-called consensus state, defined as the average of the initial states of the agents. Consider a more generalized situation in which each agent is given a positive weight and the consensus state is defined as the weighted average of the initial conditions. We characterize in this paper the weighted averages that can be evaluated in a decentralized way by agents communicating over a directed graph. Specifically, we introduce a linear function, called the objective map, that defines the desired final state as a function of the initial states of the agents. We then provide a complete answer to the question of whether there is a decentralized consensus dynamics over a given digraph which converges to the final state specified by an objective map. In particular, we characterize not only the set of objective maps that are feasible for a given digraph, but also the consensus dynamics that implements the objective map. In addition, we present a decentralized algorithm to design the consensus dynamics.

Xudong Chen, M. -A. Belabbas, Tamer Basar

Formation control deals with the design of decentralized control laws that stabilize agents at prescribed distances from each other. We call any configuration that satisfies the inter-agent distance conditions a target configuration. It is well known that when the distance conditions are defined via a rigid graph, there is a finite number of target configurations modulo rotations and translations. We can thus recast the objective of formation control as stabilizing one or many of the target configurations. A major issue is that such control laws will also have equilibria corresponding to configurations which do not meet the desired inter-agent distance conditions; we refer to these as undesired equilibria. The undesired equilibria become problematic if they are also stable. Designing decentralized control laws whose stable equilibria are all target configurations in the case of a general rigid graph is still an open problem. We propose here a partial solution to this problem by exhibiting a class of rigid graphs and control laws for which all stable equilibria are target configurations.