Scott H. Clearwater, Bernardo A. Huberman and Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@INCOLLECTION {
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.
postcript (633K)