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.
When implementing a search on a computer (or several ones) the problems to solve are
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).
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
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.
Last Change: 5/12/2013