Vidal's library
Title: Distributed Partial Constraint Satisfaction Problem
Author: Katsutoshi Hirayama and Makoto Yokoo
Book Tittle: Proceedings of the Third International Conference on Principles and Practice of Constraint Programming
Pages: 222--236
Year: 1997
Abstract: Many problems in multi-agent systems can be described as Distributed Constraint Satisfaction Problems (Distributed CSPs), where the goal is to nd a set of assignments to variables that satis es 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 satis es 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.

Cited by 36  -  Google Scholar

@InProceedings{hirayama97a,
  author =	 {Katsutoshi Hirayama and Makoto Yokoo},
  title =	 {Distributed Partial Constraint Satisfaction Problem},
  googleid =	 {PDdwGDTP5YIJ:scholar.google.com/},
  booktitle =	 {Proceedings of the Third International Conference on
                  Principles and Practice of Constraint Programming},
  pages =	 {222--236},
  year =	 1997,
  abstract =	 {Many problems in multi-agent systems can be
                  described as Distributed Constraint Satisfaction
                  Problems (Distributed CSPs), where the goal is to nd
                  a set of assignments to variables that satis es 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 satis es 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.},
  keywords =     {multiagent dcsp},
  url =		 {http://jmvidal.cse.sc.edu/library/hirayama97a.pdf},
  cluster = 	 {9432172817252628284}
}
Last modified: Wed Mar 9 10:14:18 EST 2011