@Article{yokoo98a,
  author =	 {Makoto Yokoo and Edmund H. Durfee and Toru Ishida
                  and Kazuhiro Kuwabara},
  title =	 {The Distributed Constraint Satisfaction Problem:
                  Formalization and Algorithms},
  googleid =	 {W55Ld-21gRcJ:scholar.google.com/},
  journal =	 {{IEEE} Transactions on Knowledge and Data
                  Engineering},
  year =	 1998,
  volume =	 10,
  number =	 5,
  pages =	 {673--685},
  abstract =	 {In this paper, we develop a formalism called a
                  distributed constraint satisfaction problem
                  (distributed CSP) and algorithms for solving
                  distributed CSPs. A distributed CSP is a constraint
                  satisfaction problem in which variables and
                  constraints are distributed among multiple
                  agents. Various application problems in Distributed
                  Artificial Intelligence can be formalized as
                  distributed CSPs. We present our newly developed
                  technique called asynchronous backtracking that
                  allows agents to act asynchronously and concurrently
                  without any global control, while guaranteeing the
                  completeness of the algorithm. Furthermore, we
                  describe how the asynchronous backtracking algorithm
                  can be modified into a more efficient algorithm
                  called an asynchronous weak-commitment search, which
                  can revise a bad decision without exhaustive search
                  by changing the priority order of agents
                  dynamically. The experimental results on various
                  example problems show that the asynchronous
                  weak-commitment search algorithm is, by far more,
                  efficient than the asynchronous backtracking
                  algorithm and can solve fairly large-scale
                  problems. },
  keywords = 	 {multiagent dcsp survey},
  url =		 {http://jmvidal.cse.sc.edu/library/yokoo98a.pdf},
  cluster = 	 {3323530956550053993}
}