UCSD

Mechanical and Aerospace Engineering

• Home
• Publications
• Group
• Projects
• Teaching
• Software

---

Distributed strategies for generating weight-balanced and doubly stochastic digraphs
B. Gharesifard, J. Cortés
SIAM Journal on Control and Optimization, submitted October 2009

Abstract

Weight-balanced and doubly stochastic digraphs are two classes of digraphs that play an essential role in a variety of cooperative control problems, including formation control, distributed averaging, and optimization. We refer to a digraph as doubly stochasticable (weight-balanceable) if it admits a doubly stochastic (weight-balanced) adjacency matrix. This paper studies the characterization of both classes of digraphs, and introduces distributed algorithms to compute the appropriate set of weights in each case. It is known that semiconnectedness is a necessary and sufficient conditions for a digraph to be weight-balanceable. The first main contribution of the paper is a characterization of doubly-stochasticable digraphs. In doing so, we unveil the connection between weight-balanced and doubly stochastic digraphs. The second main contribution of the paper is the synthesis of a distributed algorithm running synchronously on a directed communication network that allows individual agents to balance their in- and out-degrees. We also develop a systematic centralized algorithm for constructing a weight-balanced digraph, compute its time complexity, and show that a variation of our distributed procedure over the mirror graph has a much smaller time complexity. The final main contribution of the paper is the design of two distributed algorithms for finding a doubly stochastic weight assignment. One algorithm works under the assumption that individual agents are allowed to add self-loops. When this assumption does not hold, we demonstrate the nonexistence of an algorithmic solution within a large class of distributed strategies. This result justifies our design of the second algorithm as a distributed exhaustive search based on a newly-introduced concept called the DS-character of the digraph. Numerous examples illustrate the results.

pdf   |   ps.gz

Mechanical and Aerospace Engineering, University of California, San Diego
9500 Gilman Dr, La Jolla, California, 92093-0411

Ph: 1-858-822-7930
Fax: 1-858-822-3107

cortes at ucsd.edu
Skype id: jorgilliyo