Abstract

W. Yeoh, R. Zivan and S. Koenig. Discrepancy-Based Approach for Solving Distributed Constraint Optimization Problems. In International Workshop on Distributed Constraint Reasoning (DCR), pages 132-144, 2009.

Abstract: The distributed constraint optimization (DCOP) model is a popular model for formulating and solving agent-coordination problems. The cost-minimal solution that most DCOP algorithms look for might not be desirable in dynamically changing environments where agents are committed to an existing solution. In such situations, it might be more desirable to find either (a) a cost-minimal solution where at most k agents need to break their commitments, where k is a user-defined constant; or (b) any solution within a user-defined error bound that minimizes the number of agents that need to break their commitments. Limited discrepancy search searches for solutions in the order of increasing number of discrepancies, i.e. number of agents that need to break their commitments, and is thus ideally suited for finding the two types of solutions mentioned above. We describe how one can transform a DCOP algorithm that employs depth-first branch-and-bound to employ limited discrepancy search and, as an example, transform BnB-ADOPT to Limited Discrepancy Search ADOPT.

Download the paper in pdf.

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.