Research Group Logo CS Dept.
Formal Methods and Deduction
Prof. Dr. J. Avenhaus

Problem solving by a team

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.
Impressum RG Formal Methods and Deduction Department of Informatics Technical University of Kaiserslautern Valid HTML 4.01!

Last Update: Wednesday, 26-Oct-05 12:57:50 GMT
denzinge@informatik.uni-kl.de