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.
Follow this link to
If you have questions, problems or suggestions send email to
denzinge@informatik.uni-kl.de