Project "Distributed Constraint Optimization"
Constraint satisfaction problems require one to satisfy a set of given constraints, while constraint optimization problems require one to minimize the total cost of the unsatisfied constraints. Methods for solving Distributed Constraint Optimization Problems (DCOPs) have emerged as key techniques for distributed reasoning in multiagent domains. For example, DCOPs are able to model the task of scheduling meetings in large organizations, where privacy needs make centralized constraint optimization difficult. DCOPs are also able to model the task of allocating sensor nodes to targets in sensor networks, where the limited communication and computation power of individual sensor nodes makes centralized constraint optimization difficult. Finally, DCOPs are able to model the task of coordinating teams of unmanned air vehicles, where the need for rapid local responses makes centralized constraint optimization difficult. Unfortunately, the application of DCOP algorithms faces significant hurdles in many multiagent domains due to their inefficiency. Solving DCOPs optimally is known to be NP-hard, yet one often needs to find optimal DCOP solutions quickly. We therefore study how to speed up DCOP algorithms in order to scale them up to larger problems than can be solved today. For example, we introduced a framework of preprocessing techniques that allowed us to reduce the runtime of a state-of-the-art DCOP algorithm (ADOPT) by one-order of magnitude.
Representative Publications
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.