In this section we will switch back to looking at very general techniques that are important throughout AI. In particular, we will look at how you can use search techniques to try and find a solution to a problem. The general idea is that if you know the available actions that you could take to solve your problem, but don't know which ones will get you to a solution, you can search through all the possibilities to find one that will give you a solution.
This basic notion of search applies to all sorts of problems. We mentioned above that backward chaining rule based systems must have a search strategy so that they can systematically go through the available choices when trying to prove goals. Prolog has a built-in search strategy, based on depth first search (with backtracking). In Prolog (and rule based systems) we are effectively searching for a sequence of steps which will constitute a proof of some goal. In other applications we may be searching for a sequence of physical actions that will achieve some particular state of the world, given an initial state - for example, we might be searching for the sequence of allowable moves that will solve some puzzle. There are generally lots of examples of this kind of search in AI text books.
In these lectures we will start off by introducing some terminology for talking about search problems, then discuss the basic search techniques and algorithms by considering how we might search for a good route on a map, then show how search techniques can be applied to various problem solving tasks.