BSF: 2014012: Robust Solutions for Distributed Constraint Optimization Problems

分布式约束优化问题（DCOPs）已被证明在建模各种分布式组合优化问题（包括会议调度、传感器网络和电源管理问题）中是有用的。然而，这些问题中的许多问题不仅在自然界中是分布的，而且是动态的。例如，灾难救援场景可以包括动态事件，如建筑物倒塌，新幸存者的检测和火灾蔓延。以往在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.