Introduction

Last week, I talked about heuristic search. We saw that a problem can be represented as a start state, a goal state, and a set of moves or operators. Now, heuristic searchers know something about operators; they have to, in order to change from one state to another. But their knowledge is very limited. Essentially, all they know is the operators that exist, and how, given an old state, each operator generates a new state, together perhaps with an evaluation function. But real problems demand more than this.

Other things being equal, if there are two operators that bring you nearer to your goal, and one brings you much closer than the other, it's worth trying that one first. An evaluation function will enable you to make that choice.

But it may be that you aren't quite in a condition to do so. I write this about an hour before I go to London for a talk. There's a choice of operators I can apply to change my current state (here in Oxford) to my desired state (in London). These include walk and take the train. The more powerful is take the train; but my state now is not quite right for that, because I'm in the Computing Service, and I can only take the train from the station. The answer is for me to walk to the station first. But a heuristic searcher would only find that answer after a lot of trial and error. What we want is a program that can plan intelligently --- something that says to itself ``Taking the train is a good choice; I'll accept that; now, I must set myself the subgoal of getting him from the Computing Service to the station''. And that's what the General Problem Solver GPS does.

GPS was one of the first programs to show this kind of goal-directed behaviour. I think it worth studying for this, and other reasons:

• It exemplifies what AI people mean when they talk about formalising a problem.

• You may remember from the histories in the 1966 Scientific American article and Chapter 1 of Semantic Information Processing that there were two approaches to AI. One was modelling human behaviour; the other was solving problems intelligently, without regard to how humans behave. GPS started off as a model of behaviour: Newell, Simon, and Shaw (amongst others in that group) were mainly concerned with cognitive modelling. And have been since: hence their later production-system models, which we do next week. In its later years though (1965 onwards ?), GPS was no longer regarded as a cognitive model. So GPS is a useful discussion point for AI as cognitive modelling vs AI as engineering.

• Wholly wonderful though GPS is, it's also the end of an era. It's the final program in the let's-find-a-generally-intelligent-algorithm approach, where everything could be regarded as a problem to be solved by the same method. Its limitations became obvious, and attention shifted from generally intelligent algorithms (dependent on embodying intelligence in the algorithm) to task-specific intelligence (intelligent use of task-specific knowledge). Expert systems are the best known example of the latter.