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

协作研究：复杂动态系统中优化传感器放置的算法和图论方法

• 批准号: 1635014
• 负责人: Shreyas Sundaram
• 金额: $ 24.46万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1635014&HistoricalAwards=false
• 关键词: Collaborative; Research; Algorithmic; Graph; Theoretic

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.

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

项目成果

Near-Optimal Data Source Selection for Bayesian Learning

• 发表时间: 2020-11
• 期刊: ArXiv
• 作者: Lintao Ye;A. Mitra;S. Sundaram

Sensor Selection and Removal for State Estimation of Linear Systems with Unknown Inputs

用于未知输入的线性系统状态估计的传感器选择和移除

• DOI: 10.1109/cdc.2018.8618918
• 发表时间: 2018
• 期刊: 2018 IEEE Conference on Decision and Control (CDC
• 作者: Woodford, Nathaniel;Sundaram, Shreyas
• 通讯作者: Sundaram, Shreyas

Distributed Maximization of Submodular and Approximately Submodular Functions

• DOI: 10.1109/cdc42340.2020.9304492
• 发表时间: 2020-09
• 期刊: 2020 59th IEEE Conference on Decision and Control (CDC)
• 作者: Lintao Ye;S. Sundaram

Sensor Selection for Hypothesis Testing: Complexity and Greedy Algorithms

• DOI: 10.1109/cdc40024.2019.9029235
• 发表时间: 2019-12
• 期刊: 2019 IEEE 58th Conference on Decision and Control (CDC)
• 作者: Lintao Ye;S. Sundaram

On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering

• DOI: 10.1109/tac.2020.3007383
• 发表时间: 2020-03
• 期刊: IEEE Transactions on Automatic Control
• 影响因子: 6.8
• 作者: Lintao Ye;Nathaniel T. Woodford;Sandip Roy;S. Sundaram