Jorge Cortés
Professor
Cymer Corporation Endowed Chair
Distributed strategies
for making a digraph weight-balanced
B. Gharesifard, J. Cortés
Allerton Conference on
Communications, Control, and Computing, Monticello, Illinois, USA, 2009, pp. 771-777
Abstract
A digraph is weight-balanced if, at each node, the sum of the
weights of the incoming edges (in-degree) equals the sum of the
weights of the outgoing edges (out-degree). Weight-balanced
digraphs play an important role in a variety of cooperative control
problems, including formation control, distributed averaging and
optimization. We call a digraph weight-balanceable if it admits an
edge weight assignment that makes it weight-balanced. It is known
that semiconnectedness is a necessary and sufficient condition for a
digraph to be weight-balanceable. However, to our knowledge, the
available approaches to compute the appropriate set of weights are
centralized. In this paper, we first propose a systematic
centralized algorithm for constructing a weight-balanced digraph and
compute its time complexity. Then we propose a distributed algorithm
running synchronously on a directed communication network that
allows individual agents to balance their in- and out-degrees. The
resulting interaction digraph is weight-balanced. Finally, we
modify this procedure to design an algorithm which is distributed
over the mirror digraph and has a time complexity much smaller than
the centralized algorithm.
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