BSF: 2014012: Robust Solutions for Distributed Constraint Optimization Problems

分布式约束优化问题（dcop）在建模各种分布式组合优化问题（包括会议调度、传感器网络和电源管理问题）方面非常有用。然而，这些问题中的许多不仅在自然界中是分布的，而且是动态的。例如，灾难救援场景可以包括建筑物倒塌、发现新的幸存者和火灾蔓延等动态事件。以前在dcop中处理动态的尝试侧重于在事件发生时反应性地寻找新的解决方案。在这个项目中，PI将采取积极主动的方式，在寻找解决方案时考虑到未来可能发生的事件。本研究将产生：(1)新设计的鲁棒DCOP （R_DCOP）模型，该模型将包含表示动态事件可能性的概率方案；(2) R_DCOP算法，将解决问题的随机元素。该研究项目的广泛影响有两个方面：(1)通过这项研究，PI将为可应用于动态环境的通用鲁棒DCOP模型奠定基础，并推动DCOP算法在现实世界中的部署；(2)该项目将支持新密歇根州立大学（一所为少数族裔和西班牙裔服务的机构）扩大代表性不足的学生的参与。

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.