In this dissertation, several aspects of design for networked

systems are addressed. The main focus is on combining approaches

from system theory and graph theory to characterize graph

topologies that result in efficient decision making and control.

In this framework, modelling and design of sparse graphs that are

robust to failures and provide high connectivity are considered.

A decentralized approach to path generation in a collaborative

system is modelled using potential functions. Taking inspiration

from natural swarms, various behaviors of the system such as

target following, moving in cohesion and obstacle avoidance are

addressed by appropriate encoding of the corresponding costs in

the potential function and using gradient descent for minimizing

the energy function. Different emergent behaviors emerge as a

result of varying the weights attributed with different components

of the potential function. Consensus problems are addressed as a

unifying theme in many collaborative control problems and their

robustness and convergence properties are studied. Implications of

the continuous convergence property of consensus problems on their

reachability and robustness are studied. The effects of link and

agent faults on consensus problems are also investigated. In

particular the concept of invariant nodes has been introduced to

model the effect of nodes with different behaviors from regular

nodes. A fundamental association is established between the

structural properties of a graph and the performance of consensus

algorithms running on them. This leads to development of a

rigorous evaluation of the topology effects and determination of

efficient graph topologies.

It is well known that graphs with large diameter are not efficient

as far as the speed of convergence of distributed algorithms is

concerned. A challenging problem is to determine a minimum number

of long range links (shortcuts), which guarantees a level of

enhanced performance. This problem is investigated here in a

stochastic framework. Specifically, the small world model of Watts

and Strogatz is studied and it is shown that adding a few long

range edges to certain graph topologies can significantly increase

both the rate of convergence for consensus algorithms and the

number of spanning trees in the graph. The simulations are

supported by analytical stochastic methods inspired from

perturbations of Markov chains. This approach is further extended

to a probabilistic framework for understanding and quantifying the

small world effect on consensus convergence rates: Time varying

topologies, in which each agent nominally communicates according

to a predefined topology, and switching with non-neighboring

agents occur with small probability is studied. A probabilistic

framework is provided along with fundamental bounds on the

convergence speed of consensus problems with probabilistic

switching. The results are also extended to the design of robust

topologies for distributed algorithms.

The design of a semi-distributed two-level hierarchical network is

also studied, leading to improvement in the performance of

distributed algorithms. The scheme is based on the concept of

social degree and local leader selection and the use of

consensus-type algorithms for locally determining topology

information. Future suggestions include adjusting our algorithm

towards a fully distributed implementation.

Another important aspect of performance in collaborative systems

is for the agents to send and receive information in a manner that

minimizes process costs, such as estimation error and the cost of

control. An instance of this problem is addressed by considering a

collaborative sensor scheduling problem. It is shown that in

finding the optimal joint estimates, the general tree-search

solution can be efficiently solved by devising a method that

utilizes the limited processing capabilities of agents to

significantly decrease the number of search hypotheses.