BSF: 2014012: Robust Solutions for Distributed Constraint Optimization Problems

分布式约束优化问题(DCOP)在会议调度、传感器网络、电源管理等分布式组合优化问题的建模中具有广泛的应用前景。然而，这些问题中的许多不仅在性质上是分布的，而且是动态的。例如，灾难救援场景可以包括动态事件，如建筑物倒塌、检测到新的幸存者和火灾蔓延。以前应对DCOP中的动态变化的尝试都集中在当事件发生时主动寻找新的解决方案。在这个项目中，PI将采取主动的方法，在搜索解决方案时考虑未来可能发生的事件。这项研究将导致(1)新设计的稳健DCOP(R_DCOP)模型，其中将包括表示动态事件可能性的概率方案；(2)将解决问题的随机元素的R_DCOP算法。这项研究项目的广泛影响有两个方面：(1)通过这项研究，PI将为可应用于动态环境的一般稳健的DCOP模型奠定基础，并推动DCOP算法在现实世界中的部署；(2)该项目将支持NMSU--一家为少数族裔和西班牙裔服务的机构--代表不足的学生更广泛地参与其中。

Distributed constraint optimization problems (DCOPs) have been shown to be useful in modeling various distributed combinatorial optimization problems, including meeting scheduling, sensor network, and power management problems. However, many of these problems are not only distributed in nature but dynamic as well. For example, a disaster rescue scenario can include dynamic events like the collapse of buildings, detection of new survivors, and spread of fires. Previous attempts to cope with dynamism in DCOPs have focused on reactively finding a new solution when an event occurs.In this project, the PI will take a proactive approach by taking possible future events into consideration when searching for solutions. This research will result in (1) a newly designed Robust DCOP (R_DCOP) model that will include a probabilistic scheme representing the likelihood of dynamic events; and (2) R_DCOP algorithms that will address the stochastic elements of the problem. The broader impacts of this research project are two fold: (1) Through this research, the PI will build the foundations for a general robust DCOP model that can be applied in dynamic environments and spur deployment of DCOP algorithms in the real world; and (2) This project will support broadening participation of underrepresented students at NMSU, a minority- and Hispanic-serving institution.