1997•Unpublished venueRequires access
Distributed Partial Constraint Satisfaction Problem
Katsutoshi Hirayama, Makoto Yokoo
Open publisher page 61 citations
Abstract
. Many problems in multi-agent systems can be described as Distributed Constraint Satisfaction Problems (Distributed CSPs), where the goal is to find a set of assignments to variables that satisfies all constraints among agents. However, when real-life application problems are formalized as Distributed CSPs, they are often over-constrained and have no solution that satisfies all constraints. This paper provides the Distributed Partial Constraint Satisfaction Problem (DPCSP) as a new framework for dealing with over-constrained situations. We also present new algorithms for solving Distributed Maximal Constraint Satisfaction Problems (DMCSPs), which is an important subset of DPCSPs. The algorithms are called the Synchronous Branch and Bound (SBB) and the Iterative DistributedBreakout (IDB). Both algorithms were tested on hard classes of over-constrained random binary Distributed CSPs. The results can be summarized as SBB is preferable when we are mainly concerned with the optimality of a solution, while IDB is preferable when we want to get a nearly optimal solution quickly. 1