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）（4）用于传感器和（5）传感器的图形理论和算法的功能。

项目成果

Near-Optimal Data Source Selection for Bayesian Learning

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

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 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

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