Research Group Formal Methods and Deduction Prof. Dr. J. Avenhaus

 The Teamwork Method for Distributed Search

In order to understand our teamwork method, one has to look at the problems that can occur when one tries to solve a problem using distributed search. As example to illustrate the problems we will use solving puzzles, again:
• A very basic problem is that several people cannot try simultaneously to put a piece in the same spot (Control problem).
• Even if the people work on different spots they may argue over single pieces they all believe that they will fit into their spot. It is also not very good for the whole solution process, if each one who thinks he has found a fitting piece tells all the others about it (Communication problem).
• The additional pieces that are not needed to solve the puzzle can have the effect that one or several of the problem solvers do in fact not work on solving the right puzzle (Focus problem).
Our teamwork method either avoids or solves these problems as follows:

There are three types of members in a team:
• Experts: are responsible for the actual search.
• Referees: try to judge the progress of the experts.
• Supervisor: coordinates the search and controls the communication.
Each expert has its own copy of the puzzle and can manipulate it in each way it wishes. In order to achieve a cooperation of the experts, there are so-called team meetings in regular intervals. Prior to such a team meeting the success of each expert is evaluated by its referee. In addition, each referee selects reasonable partial solutions of its expert. These solutions are sent to the supervisor together with the general evaluation of the expert. The supervisor determines the most successful expert, adds to its partial solutions the selected partial solutions of the other experts and sends this actual problem solving state to all experts.
Since there are typically not as many copies of the puzzle as one likes (as it is the case with computers that can be used to run experts on), the supervisor has the possibility to exchange experts that were not able to come up with usable partial solutions. This results in a kind of competition. A cycle between two team meetings is depicted here.

It is very important for a successful use of the teamwork method that the experts use different methods and strategies for generating (partial) solutions. In computer programs this is achieved by using different control heuristics that represent different, even contradictory, knowledge. With only one computer one would have to decide which of these heuristics to use. Furthermore, the selected heuristic may be totally inadequate.
For complex and hard search problems there is typically no heuristic that is capable of solving the whole problem. Some parts of the solution are always found very quickly while other parts can only be identified by an expensive and systematic enumeration of all possibilities. The teamwork method allows experts that find different parts of the solution quickly to combine these parts thus achieving synergetic effects.