DAI-List Digest Tuesday, 24 December 1991 Issue Number 65 Topics: Cooperative Problem Solving (re "Science," vol.254) Re: Theory of cooperation Please send submissions to DAI-List@mcc.com. Send other requests, such as changes in your e-mail address, to DAI-List-Request@mcc.com. ------------------------------------------------------------------------ From: Scott Clearwater To: DAI-List@mcc.com Subject: Cooperative Problem Solving Date: Mon, 23 Dec 1991 16:21:11 PST I wish to address some of Mr. Petrie's remarks [DAI-List Digest #64] because they are erroneous. 1) We did not run "several" agents to obtain our results, we ran at least 100, as clearly stated in the paper. 2) We did *not* conclude that "it is better to have simple cooperating processes than a single task-specific program". What we mean is that there is often enormous effort involved in constructing task-specific programs and for some of those tasks it may be easier to use a collection of simpler interacting programs. These simple programs also need not rely on perfect information from the other programs in order for high performance to be acheived. Of course, if task-specific programs are available then they should be used, preferably in a cooperative mode to acheive even greater speed. Our purpose was not to show how to solve cryptarithmetic problems via cooperation (we know task-specific algorithms exist for this problem), but to show on a specific, familiar example how cooperation of simple programs can be used to improve performance over non-cooperative simple programs. Scott Clearwater ------------------------------------------------------------------------ From: cl@lgc.com (Cameron Laird) Subject: Re: Theory of cooperation Date: 21 Dec 91 20:45:55 GMT Organization: Landmark Graphics Corporation In DAI-List Digest #64 konolige@stump.ai.sri.com (Kurt Konolige) writes: >I found the argument of this article somewhat hard to understand. >What does cooperation have to do with finding speedier solutions to >cryptarithmetic problems? The "hints" that agents post are simple >heuristics that could be incorporated into a (noncooperative) search >strategy. Any stochastic search process using such heuristics should... > Yes and no. I've seen more than my share of graduate students whose "parallelism" research consists in implementing on two microcomputers an algorithm that could best be studied on a single sheet of paper. On the other hand, it's a substantial contribution to *prove* statements like "The key difference between cooperating and noncooperating agents is that hints effectively reduce the size of the search space by focusing the agents on much more plausible courses of action. Moreover, an agent searching one part of the space may find a hint useful to another agent in a different part of the space." or "Hence, with specialization the faster performers benefit while the slower performers suffer." Some people do not believe in cooperation, in the sense that they expect communication costs to swamp any gains due to "specialization". I rate it useful for Clearwater et al. to have worked out some of the true details behind this question. >observe the same lognormal distribution. Well, OK, I believe it should; do you have a good proof of that? I think it would be worth publishing? > >Still, the article was intriguing and I appreciate not having to read >too many equations. Unfortunately there is an error in the first one. I count at least two, but note how typical they are of what happens when editors try to slim something down to keep it "popular" (*Scientific American* commits this incessantly). I suspect the authors themselves have a bit more respect for the syntax of formal parameters. My apologies to the *Science* reviewers, if they were not the ones responsible in this case. Cameron Laird +1 713-579-4613 cl@lgc.com (cl%lgc.com@uunet.uu.net) +1 713-996-8546