Cooperative Problem Solving

 AUTHOR = "Scott H. Clearwater and Bernardo A. Huberman and Tad Hogg",
 TITLE = "Cooperative Problem Solving",
 BOOKTITLE = "Computation: The Micro and the Macro View",
 EDITOR = "B. Huberman",
 PAGES = "33-70",
 PUBLISHER = "World Scientific",
 ADDRESS = "Singapore",
 YEAR = "1992"}


We present a quantitative assessment of the value of cooperation for solving constraint satisfaction problems through a series of experiments, as well as a general theory of cooperative problem solving. These experiments, using both hierarchical and non-hierarchical cooperation, clearly exhibit a universal improvement in performance that results from cooperation. We also show both theoretically and experimentally the super-linear speed-up that results from having a diverse collection of skills among the cooperating agents. Our results suggest an alternative methodology to existing techniques for solving constraint satisfaction problems in computer science and distributed artificial intelligence.
pdf (297K)

A shorter version of this paper appeared in
S. H. Clearwater, B. A. Huberman and T. Hogg, Cooperative Solution of Constraint Satisfaction Problems, Science 254, 1181-1183 (1991).