Optimising Robustness of Consensus to Noise on Directed Networks

Abstract

A major area of study in recent years has been the development of robotic groups that are capable of carrying out complicated and useful tasks and yet are comprised of relatively simple individuals following relatively simple rules. Despite the evidence from natural groups of animals, birds, fish and insects that such behaviour is possible, many challenges remain in the attempt to translate it into engineered systems. One important aspect of understanding and designing group behaviour is the analysis of the communication structure within a group and its effect on overall group performance.

In this dissertation, we focus on understanding the role played by a directed communication graph in the ability of a group to maintain consensus in noisy environments. To this end, we relate a H2 norm that can be computed from a directed graph to the robustness of the group to noise. Using this relationship, we are able to compute bounds on the group robustness and analyse the capabilities of several families of graphs.

The robustness of consensus to noise on undirected graphs is intimately related to the concept of effective resistance. We present a generalisation of this concept to directed networks and confirm that our new notion of effective resistance is a graphical property that depends on the connections between nodes in the graph. Furthermore, in certain circumstances effective resistance in directed graphs behaves in a similar fashion to effective resistance in undirected graphs, while in other situations it behaves in unexpected ways.

We use effective resistance as a tool to analyse tree graphs, and derive rules by which local changes can be made that will guarantee that the robustness of the entire system will improve. These rules lead to the possibility of decentralised algorithms that allow individuals interacting over a tree graph to rearrange their connections and improve robustness without requiring knowledge of the entire group.

Finally, we use our measure of robustness to analyse a family of interaction strategies within flocks of starlings. This analysis demonstrates that the observed interactions between the starlings optimise the tradeoff between robust performance of the group and individual sensing cost.