BSF: 2014012: Robust Solutions for Distributed Constraint Optimization Problems

New Mexico State University, Las Cruces NM

Investigators

Abstract

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.