A Tractable Computational Framework for Dynamic Coverage and Clustering

用于动态覆盖和聚类的易于处理的计算框架

• 批准号: 1100257
• 负责人: Srinivasa Salapaka
• 金额: $ 38.1万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1100257&HistoricalAwards=false
• 关键词: Tractable; Computational; Framework; Dynamic; Coverage

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.

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