# Computing by committee: sharing searches.

Teamwork underlies a wide range of human activities, from the
founding of a company to assemble and market a new product to the
gathering of a group to solve a problem. Teams provide a means of
sharing not only the work but also the information gleaned by individual
members as they pursue specific tasks.

Experience suggests that for solving certain kinds of problems, cooperation can substantially improve performance, permitting the completion of these tasks faster than could be accomplished by an individual or a group in which members work in isolation. The same principle may apply to solving problems by computer, especially in situations where there are no efficient, step-by-step procedures, or algorithms, available, and where finding the answer requires searching through a large number of possibilities.

Using computer simulations of cooperative problem solving, a team of computer scientists at the Xerox Palo Alto (Calif.) Research Center has now provided some of the first quantitative estimates of the degree to which information sharing can speed up searches for answers to certain types of problems. Scott H. Clearwater, Bernardo A. Huberman and Tad Hogg describe their findings in the Nov. 22 SCIENCE.

As a simple test problem, the reserchers chose a type of cryptarithmetic puzzle that requires finding the digits that correspond to certain letters of the alphabet so that the number represented by the given words add up correctly. For example, for what digits would the sum DONALD+GERALD = ROBERT be true? This particular problem has one solution, which is given by A = 4, R = 7, and so on.

Cooperation in solving this puzzle takes the form of reading and writing hints on a central "blackboard" accessible to all the "individuals" (in this case, computer programs) working on the puzzle. Hints consist of lists of letter-digit assignments that add up correctly for at least one column in the given sum. Starting at different points, each individual constantly checks the blackboard for hints, randomly generating and testing new combinations whenever all hints are exhausted or none is available.

Compared with noncooperative strategies, such searches bring a striking overall improvement in performance, the reserchers found. The actual speedup varies greatly from run to run because the time needed to solve the puzzle depends strongly on the quality of the first few hints posted on the blackboard. Nonetheless, shared information reduces the number of possibilities that need to be considered by focusing the problem solvers on more plausible courses of action.

In computer science, this work suggests that instead of seeking a single, ideal algorithm for solving a certain problem, a better strategy would involve developing a set of relatively simple computer programs that work on the program concurrently while communicationg their partial results. "You might be better off sometimes having a bunch of dump processes cooperating," Huberman says.

"These results also have implications for problem solving in general," he adds. "In a sense, this is a simple simulation of a model of something like a society."

Experience suggests that for solving certain kinds of problems, cooperation can substantially improve performance, permitting the completion of these tasks faster than could be accomplished by an individual or a group in which members work in isolation. The same principle may apply to solving problems by computer, especially in situations where there are no efficient, step-by-step procedures, or algorithms, available, and where finding the answer requires searching through a large number of possibilities.

Using computer simulations of cooperative problem solving, a team of computer scientists at the Xerox Palo Alto (Calif.) Research Center has now provided some of the first quantitative estimates of the degree to which information sharing can speed up searches for answers to certain types of problems. Scott H. Clearwater, Bernardo A. Huberman and Tad Hogg describe their findings in the Nov. 22 SCIENCE.

As a simple test problem, the reserchers chose a type of cryptarithmetic puzzle that requires finding the digits that correspond to certain letters of the alphabet so that the number represented by the given words add up correctly. For example, for what digits would the sum DONALD+GERALD = ROBERT be true? This particular problem has one solution, which is given by A = 4, R = 7, and so on.

Cooperation in solving this puzzle takes the form of reading and writing hints on a central "blackboard" accessible to all the "individuals" (in this case, computer programs) working on the puzzle. Hints consist of lists of letter-digit assignments that add up correctly for at least one column in the given sum. Starting at different points, each individual constantly checks the blackboard for hints, randomly generating and testing new combinations whenever all hints are exhausted or none is available.

Compared with noncooperative strategies, such searches bring a striking overall improvement in performance, the reserchers found. The actual speedup varies greatly from run to run because the time needed to solve the puzzle depends strongly on the quality of the first few hints posted on the blackboard. Nonetheless, shared information reduces the number of possibilities that need to be considered by focusing the problem solvers on more plausible courses of action.

In computer science, this work suggests that instead of seeking a single, ideal algorithm for solving a certain problem, a better strategy would involve developing a set of relatively simple computer programs that work on the program concurrently while communicationg their partial results. "You might be better off sometimes having a bunch of dump processes cooperating," Huberman says.

"These results also have implications for problem solving in general," he adds. "In a sense, this is a simple simulation of a model of something like a society."

Printer friendly Cite/link Email Feedback | |

Author: | Peterson, Ivars |
---|---|

Publication: | Science News |

Date: | Nov 30, 1991 |

Words: | 494 |

Previous Article: | Many doctors would shun AIDS patients. |

Next Article: | Fickle fields: EMFs and epidemiology. |

Topics: |