Essay and main reading

This week, I want you to write an essay on ``How does the General Problem Solver work? What are its limitations, both as a model of human problem-solving, and as an engineering tool for solving problems in general?''

For the reading, start by working through sections 5.1 to 5.6 of the OU book. You can omit, or skim, section 5.5 (and-or trees) if you want; it's not relevant to how GPS works, though it does show how you can represent its behaviour.

You may also find useful the overview of GPS in AI and Natural Man by Boden, pp 354-356.

Unfortunately, the OU book doesn't give any examples of how to present problems to GPS. For this, read Winston Chapter 5, pages 146-156. Note on page 153 how GPS can be regarded as search. Note on pages 153-154 how it might be adapted to plan more efficiently by deferring detail. GPS itself was never used like this, though a sucessor called ABSTRIPS was.

These are adequate to tell you how GPS works. To put it in context, to find out why anyone should want to write such a program, read GPS, A Program that Simulates Human Thought, by A Newell and H A Simon, in Computers and Thought edited by E A Feigenbaum and J Feldman (RSL: per 19668 d 335; Psychology: KH:F.). Warning: what I called states, the authors call ``objects''.

As you read, ask yourself whether the protocol-taking technique really tells us what the subjects were doing? What does your knowledge of psychology have to say on this point?

For a critique of GPS, both as a cognitive model and as a tool for problem-solving, see Boden, Computer Models of Mind, pp 152-154.

If you want to find out more about GPS, you could have a look at GPS - a case study in generality and problem solving, by G W Ernst and A Newell (RSL: 1878 d 142). You won't need it for the essay, or for Finals; I mention it just for interest. Note that parts of this are rather hard to read, because a lot of the general discussion is interspersed with terminology concerning GPS' internal workings. It does contain a lot of examples of how GPS was used, and the introduction discusses the motivation for writing GPS.

• The Introduction: for motivation.

• Chapter II, the section ``An Approach to Generality'': for its subsections on External Representation, Internal Representation, and Techniques. The first discusses how to present problems to a solver. The second is about what properties an internal representation should have. In the third, read the section on ``Heuristic Search'' for a summary of GPS and related methods. Note that the authors use ``Heuristic Search'' to mean search with operators, GPS-style; not evaluation-function search as the OU book does.

• Pages 91,92,249,250 for more comments on what a good representation should do for GPS. This may be useful to add to what we did in the Evans tutorial.

• The Summmary, pages 247-250.

• If you want examples of how problems can be formalised in terms of operators and states (something rare elsewhere in descriptions of GPS), then read the pages listed below. Because of the stuff about GPS internal workings, these may not be too easy to follow. At least try to see what operators are being used for each problem; how they reduce differences; how states are represented. Like the Computers and Thought paper, what we call states, the authors call ``objects''.
  • Page 65.
  • Pages 150-156: Hanoi.
  • Pages 181-184: Father and Son.
  • Pages 189-192: Monkey puzzle.
  • Pages 194-197: 3 coins.
  • Pages 200-206.
  • Pages 209-210: Bridges of Koenigsberg.
  • Pages 221-226: Water jugs.