Collaborative Research: Toward graphon-based structural system theory

Washington University, Saint Louis MO

Investigators

Abstract

This project will develop theory and methods to address network-level uncertainty in the control of large-scale networked systems. In such systems, the communication topology is described by a directed graph, whose nodes represent the agents in the system and the edges represent the communication links between them. To meet the modelling demands of realistic multi-agent settings, it is known that one needs to account for process and observation noise. The goal of this project is to explore what lies beyond these requirements and account for uncertainty at the level of the communication topology. To this end, the project will integrate the fields of random graph theory, and particularly graphon theory, with structural system theory to develop the needed theoretical tools to model and understand network-level uncertainty in control systems. Graphons are relatively new models in the landscape of random graph theory. They generalize many existing random graph models, such as the Erdös-Rényi model, by allowing for heterogeneous edge densities. A major research goal of this project is to characterize completely how a given structural system property behaves under network uncertainty. The main research problem of the project is the following: Given a desired system property (e.g., controllability and stability), what is the probability that a graph sampled from a graphon can sustain the property? The problem is by nature combinatorial and probabilistic. To tackle these challenges, this project will rely on tools from analysis and geometry to develop a new set of ideas geared toward the computation the aforementioned probabilities in the asymptotic regime, where the size of the random graph goes to infinity. The intellectual merits of this project lie in the use of methods from graphon theory, probability, and combinatorics to understand control system properties. More specifically, the project will (1) formulate new problems at the intersection of structural system theory and graphon theory, (2) develop a new toolbox for analyzing structural properties for network systems drawn from graphons, and (3) establish new theoretical results and algorithms that may have impacts on both areas and beyond. A major novelty of the proposed approach is that the project leverages tenets from graphon theory to circumvent the complexity of combinatorial problems, leading to the use of analytical tools and geometric approaches to provide complete solutions. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.