Many of the early practitioners of AI hoped that the difficult tasks they had set, such as building automated chess players, theorem provers, and language translators, could be tackled by employing a few general-purpose techniques. One of the earliest AI programs was even given the optimistic title of the General Problem Solver (Ernst and Newell, 1969). The most important of these general techniques is search.
In recent years attention has shifted towards constructing detailed representations of knowledge, of the kind described in the last chapter, coupled with mechanisms more closely based on those of human problem-solvers. Nevertheless, search remains an important topic in AI, both as a technique for implementing the lower levels of cognition, like visual scene recognition and language understanding, and as a means of modelling those occasions when we consciously search for an entity or a possibility.
Suppose a mobile robot needs to find the best route through some furniture in a room to the door. It can do so by looking at the consequences of the possible moves it can make. Without actually moving the robot, its program checks out the various possibilities in a systematic way. In effect, the program asks itself questions like ``What if I move to my left?''. If the answer is ``I collide with the table,'' then that possible move can be ruled out, but if the answer is ``I get closer to the door,'' then the next move after that can be considered, and so on. Any program that asks this kind of ``What if ...?'' question over and over until it finds a solution to its problem is doing search.
The idea of search in a computer program is not really all that different from searching in everyday life. Imagine you have lost a key. You systematically try the possibilities, asking ``What if ...?'' questions, until the thing is found. Sometimes, in this example, the questions are answered by a making an action (``What if it's under the cushion?'' is answered by lifting up the cushion) and sometimes just by thinking (``What if I left it on the bus?'' might be answered by recalling that you used the key after getting off the bus). If you are calm, you do not look in places that you have already searched. You look in the most probable places first but also try to organize your search so as to minimize the amount of walking around you do. And you ask yourself questions that can rule out a whole range of possibilies at once -- for example, the question of where you last saw the key.
Searching does not always mean looking for a physical object, of course. You might search for a word you do not know how to spell in a dictionary, you might search for the best route to get across a city, or you might search for the best way to express an idea on paper. But even though some of these searches are very abstract, they all involve trying out possibilities, and in this way are closely related to the technique of search used by computer programs.
Often we do not know how our minds search for something. We have little idea how we come up with the solution to an obscure crossword clue, or a good move in a chess game, or the words to get across an idea. Mostly we cannot program computers to do these things well. On the other hand, we do know how to program computers to search for solutions to a wide range of tasks. The rest of this chapter is about how such programs work.