###
Distributed Partial Constraint Satisfaction Problem

Katsutoshi Hirayama, Makoto Yokoo

Third International
Conference on Principles and Practice of Constraint Programming (CP-97),
1997.

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 Distributed Breakout (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.