Consensus problems and the effects of graph topology in collaborative control

Abstract

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.