A Tractable Computational Framework for Dynamic Coverage and Clustering

该奖项的研究目标是开发一种计算框架，解决大规模网络上定义的动态聚类和分类问题。该框架将专门处理组合计算的复杂性和可扩展性、覆盖范围和协调成本函数的可变性、组成元素动态的特定区域约束、它们的通信网络结构以及它们的相互作用或相互依赖性。在我们的框架中占主导地位的方法是确定性的，但具有很强的随机概念基础，其中概率密度函数被赋予决策变量的空间，从而使决策变量的最可能值是组合问题的近似解。这个概率密度函数是用最大熵原理推导出来的。在这项研究中，我们汇集了控制和动态系统理论，优化理论和信息论的工具，制定了一个灵活的框架，可以用于许多应用领域。特别是，我们将通过与智能建筑系统和救灾行动相关的聚类和分类问题来演示该框架。如果成功，本研究将直接影响组合优化算法的分析和设计，以及对医疗、基础设施和网络行业（如生物信息学、化学信息学、传感器网络、组合药物发现和数据挖掘）具有重要意义的应用领域。特别是，我们的研究结果将(1)实现智能建筑系统中传感器网络的同时覆盖和路由，(2)促进救灾场景中搜索和救援行动的优化，以及(3)为组合药物设计生成可扩展的算法。研究生和本科生将受益于课堂教学和参与研究。基于图形用户界面（GUI）的软件模块将与网络集成，以生成与专家、学生和广大社区的交互通信能力。

The research objective of this award is to develop a computational framework addressing dynamic clustering and classification problems defined over large-scale networks. This framework will specifically address combinatorial computational complexity and scalability, variability in coverage and coordination cost functions, area-specific constraints on dynamics of constituent elements, their communication network structures, and their interactions or interdependencies. The dominant methods in our framework are deterministic, but have a strong stochastic conceptual basis where a probability density function is ascribed on the space of decision variables in such a way that the most probable value for the decision variable is an approximate solution to the combinatorial problem. This probability density function is derived using the maximum entropy principle. In this research, we bring together tools from control and dynamic system theory, optimization theory, and information theory to formulate a flexible framework that can be used for many application domains. In particular, we will demonstrate the framework through clustering and classification problems related to Intelligent Building Systems and Disaster Relief Operations. If successful, the proposed research will directly impact analysis and design of combinatorial optimization algorithms and application areas of great significance to medical, infrastructure, and cyber industries such as bioinformatics, chemoinformatics, sensor networks, combinatorial drug discovery, and data mining. In particular our results will (1) enable simultaneous coverage and routing in sensor networks found in intelligent building systems, (2) facilitate optimization of search and rescue operations in disaster relief scenarios, and (3) generate scalable algorithms for combinatorial drug design. Graduate and undergraduate engineering students will benefit through classroom instruction and involvement in the research. A graphical user interface (GUI) based software module will be integrated with the web to generate interactive communication, capabilities with experts, students and the community at large.