Distributed Constraint Optimization

A distributed constraint optimization problem (DCOP) is a problem where multiple agents coordinate with each other to take on values such that the sum of the resulting constraint costs, that are dependent on the values of the agents, is minimal. DCOPs are a popular way of formulating and solving multi-agent coordination problems such as the distributed scheduling of meetings, distributed coordination of unmanned air vehicles and the distributed allocation of targets in sensor networks. Privacy concerns in the scheduling of meetings and the limitation of communication and computation resources of each sensor in a sensor network makes centralized constraint optimization difficult. Therefore, the nature of these applications call for a distributed approach.

Our current research focus is two fold:

  • We seek to speed and scale up DCOP algorithms so that they can be amenable for real-world deployment. We have proposed methods that (1) exploit domain properties of the problems; (2) are parallelizable and, thus, sped up using graphical processing units (GPUs); (3) prune the search space through consistency propagation techniques; etc.
  • We plan to enrich DCOPs so that they can be used to model dynamic and uncertain problems through integration with concepts from decentralized Markov decision processes (Dec-MDPs). The proposed models and algorithms will serve as a bridge between DCOPs and Dec-MDPs, balancing the tradeoffs between expressivity and scalability. See MDP project page for more info.
Group Members and Current Collaborators
Sponsors
Recent Publications