Jörg Denzinger's

Knowledge-based Search

Search is a fundamental problem solving technique employed by human beings and also by computers. Whenever there are several possibilities to continue from a certain point and there is no way to determine in advance what possibility will lead to the intended goal then a search is performed.

A robot searching Calgary

When implementing a search on a computer (or several ones) the problems to solve are

  • defining the possible situations (states)
  • determining in each possible (or occuring) situation all possibilities to continue (the transitions)
  • selecting one possibility (preferably one that has a high probability to take us to our goal)

While usually there are already several or even many solutions to the first two problems, the third problem is the most difficult one, if the problem we want to solve using search is a hard one. Because for such problems in most states there are very many possible transitions and wrong selections often result in search runs that do not reach the goal (or a good goal) in acceptable time.

So, while there is in theory always the possibility to try out systematically all possible chains of transitions, for hard problems this is not a practical option. Therefore designers of search systems have to put much effort in developing good selection strategies that use various kinds of knowledge to guide the system (like the geographical knowledge our Robbie is employing in the next picture).

A robot deducing that Calgary is near the Rocky Mountains

Unfortunately, usually there is much knowledge available of which many pieces are either not applicable (this is not such a serious problem) or applicable but misleading (this causes serious problems). Knowledge can be derived from

  • the problem or its instance to solve,
  • the description of states and transitions, and
  • experiences of developers and users.

In our research projects we tackle the problem of controlling a search using two general ideas:

Both general ideas can be combined and lead then to even better effects, because the ideas have different strengths and weaknesses and the weaknesses can be overcome by the combination.

to our projects about distributed search.

Last Change: 5/12/2013