Collaborative Research: Algorithmic and Graph-Theoretic Approaches to Optimal Sensor Placement in Complex Dynamical Systems

Washington State University, Pullman WA

Investigators

Abstract

A wide array of new sensing technologies are being envisioned and developed for modern engineered systems, which provide operators with unique abilities to monitor or estimate the systems' state. Once sensors are in place, state estimates can be obtained by analyzing data gathered from the deployed sensors together with mathematical models of the system. However, as systems increase in scale and complexity, the deployment of sensors for high quality state estimation remains a bottleneck in a broad spectrum of applications ranging from microprocessors to power distribution networks and societal-scale Internet-of-Things. This project supports the creation of new sensor placement (deployment) algorithms with rigorous performance guarantees. The research will produce a new understanding of the fundamental limitations and achievable performance of sensor placement algorithms, and formulate efficient placement algorithms that perform well in the presence of sensor faults and external attacks. In addition to the creation of new methods and theories, the research will have broader impact on industrial research-and-development as well as education. Specifically, the research will directly support design of multi-processor systems and energy-efficient buildings via the transition of research results to industrial partners. The outcomes will also be used to increase undergraduate participation in research, and will be incorporated into courses to expose students to cutting edge techniques for the complex systems that they will encounter after graduation. The project will be focused on the budget-constrained design-time sensor placement problem. Motivated by fundamental open problems in this space, this research will establish new algorithms for placing sensors in order to facilitate state estimation with optimality, robustness and resilience guarantees, while meeting sensor budget constraints. To do this, the sensor placement problem is framed as an optimal resource design problem for a dynamical system subject to disturbances, wherein expensive or constrained discrete sensing resources are deployed to optimize an estimation performance metric. The research agenda is organized around five comprehensive and complementary tasks: (1) sensor placement in systems with stochastic disturbances, (2) sensor placement in systems with deterministic (but unknown) disturbances, (3) fault- and attack-tolerant sensor placement, (4) graph-theoretic rubrics and algorithms for sensor placement and (5) sensor placement for heterogeneous dynamics and sensors.