Distributed Knowledge-based Search

There are two principle ways to use several computers to do knowledge-based search (that also can be applied together):

• dividing one transition into several tasks that then are assigned to different computers (or processors of a multiprocessor computer)
     -> this we call parallel search
• defining transitions as undividable units and letting the computers do (different) transitions or transition chains in parallel
     -> this we call distributed search

We are interested in distributed knowledge-based search. In order to understand the problems that have to be solved when trying to come up with a concept for distributed search, let us look at an example for knowledge-based search we are all familiar with: puzzles.

A puzzle consists of many pieces that have one, two or even three sides in common. In order to make the problems in distributed search more obvious, let us also throw in many additional pieces that are not needed to solve the puzzle. The goal of solving a puzzle is to produce a certain picture by putting fitting pieces together.

Solving a puzzle is indead a good example for a knowledge-based search problem:

• The common sides of the pieces (and the additional pieces) result in many possibilities to continue from a situation, many of which will not lead to the goal.
• The picture parts on the pieces provide knowledge that can be used to lead the search.

Now let us assume that a group of people get the task to solve a puzzle. Then they face the following problems:

• 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).

Each concept for distributed knowledge-based search has to come up with solutions to these problems. We have developed two basic concepts for distributed search that have some features in common but that are aimed at teams of problem solvers that differ in their abilities:

• the TEAMWORK method is aimed at homogeneous teams, i.e. teams in which all agents have the same abilities and differ only in their strategies
• the TECHS approach is aimed at heterogeneous teams, i.e. teams in which agents can have different abilities and therefore different search techniques and even different ways to express the same information.

Both concepts have in common that they solve the control problem in the same way: in our puzzle example each of the agents gets its own copy of the puzzle. In fact, both concepts are improvements of the so-called competition approach towards added cooperation of the agents.

A distributed system employing the competition approach just gives the problem to solve to all agents and lets them work on their own until one agent has found a solution.

We also have developed an approach for distributed data mining, called CoLe that combines some concepts from improving on the competition approach with ideas from dividing the problem into subproblems.

to our TEAMWORK method.

Last Change: 5/12/2013