Search is the basic problem solving method
employed by computer
programs. On can imagine the problem solving process as a kind of puzzle
consisting of many pieces that have one, two or even three sides in common many
of
which are even not needed for the actual solution. The common sides result in
many search paths that do not lead to a solution but force the evaluation
of many paths until the puzzle can be solved. Depending on the problem to solve
there exists much additional knowledge (more or less vague), in case of a puzzle
this knowledge would be the image on the puzzle pieces. This knowledge allows
the detection of unsuccessful search paths in a more or less early stage of
the evaluation.
The evaluation of many different possible paths (there are problems for
which there exists infinitely many possible paths) requires much computing power
which often cannot be provided by one computer alone. Therefore cooperation
concepts for computers are needed. There are many different possibilities how
several human beings can cooperate in solving a puzzle. The additional features
of our puzzle (additional pieces, common sides) result in many possible
cooperation concepts for computer program, too. These concepts have different
success when employed for different problems.
We are interested in a certain kind of search process, namely
knowledge
based search using sets of facts. In our puzzle example this means
working on subsets of the whole set of pieces. This kind of search can
successfully be employed for solving problems like
automated theorem proving or optimization problems like
scheduling production processes or the travelling
salesman problem. Our distribution concept is called the teamwork method.
The main result of our work using teamwork is that cooperation of computers
in problem solving can lead to so-called
synergetic effects, which are exactly the effects that human teams
want to achieve. Synergy means that the team of
computers can achieve more
than only summing up their computing power. We were able to solve problems
that none of our programs using a single computer could solve, even if they
were allowed to spend more time.
