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

人们正在为现代工程系统设想和开发一系列新的传感技术，这些技术为操作员提供了监测或估计系统状态的独特能力。一旦传感器就位，就可以通过分析从部署的传感器收集的数据以及系统的数学模型来获得状态估计。然而，随着系统规模和复杂性的增加，用于高质量状态估计的传感器的部署仍然是从微处理器到配电网络和社会规模的物联网等广泛应用的瓶颈。该项目支持创建新的传感器布局(部署)算法，并提供严格的性能保证。这项研究将对传感器布局算法的基本局限性和可实现的性能有一个新的理解，并制定出在存在传感器故障和外部攻击时性能良好的高效布局算法。除了创造新的方法和理论外，这项研究还将对产业研发和教育产生更广泛的影响。具体地说，这项研究将通过将研究成果转化为工业合作伙伴，直接支持多处理器系统和节能建筑的设计。这些成果还将用于增加本科生的研究参与度，并将被纳入课程，使学生了解毕业后将遇到的复杂系统的尖端技术。该项目将专注于预算有限的设计时间传感器布局问题。受这一领域基本开放问题的启发，本研究将建立新的传感器放置算法，以便在满足传感器预算约束的同时促进状态估计的最优性、稳健性和弹性。为此，传感器布局问题被描述为一个受干扰的动态系统的最优资源设计问题，其中昂贵的或受限的离散传感资源被部署来优化估计性能指标。研究议程围绕五个综合性和互补性的任务展开：(1)随机扰动系统中的传感器布局；(2)确定性(但未知)扰动中的传感器布局；(3)容错和攻击的传感器布局；(4)传感器布局的图论知识和算法；(5)异质动态和传感器中的传感器布局。

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.