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.