Archive: December 12th, 2008

Newell and Simon: Human Problem Solving

[Readings] (12.12.08, 5:09 pm)

Newell and Simon are enormously influential in AI and cognitive science. Their approach to human problem solving has however been a favorite target for criticism among advocates for embodiment, situated action, and activity based approaches to cognition. I have been finding myself taking up the mantle of this group, so I am approaching Newell and Simon from a critical perspective. It is not my aim to reject symbolic approaches to problems and problem solving, but rather to change how symbols are conceived of and used.

This is the text that introduces the General Problem Solver, or GPS. GPS eventually was transformed into Soar, which remains a usable problem solver.


Early on, the authors introduce the aim of the book as to develop a theory of cognition. Cognition is framed as a combination of three elements, which are performance, learning, and development. The emphasis in this book is performance, which is how cognition is used. The study of the book is introduced very early: “The present study is concerned with the performance of intelligent adults in our own culture. The tasks discussed are short (half-hour), moderately difficult problems of a symbolic nature. The three main tasks we use–chess, symbolic logic, and algebra-like puzzles (called cryptarithmetic puzzles)–typify this class of problems. The study is concerned with the integrated activities that constitute problem solving. It is not centrally concerned with perception, motor skill, or what are called personality variables.” (p. 3-4) This isolation of the problem is very specific and cuts out a huge class of cognition and activity. We should take Newell and Simon’s conclusions from this study as being applied specifically to this domain of problems, but it often gets conflated with something much greater. Performance and problem solving of chess, logic, and cryptarithmetic puzzles are not at all representative of cognition on the whole.

Performance on problems is compared to learning. Learning is described as a secondary activity, which is primarily dependent on performance. This type of reasoning is directly at odds with work by Vygotsky and Tomassello and other developmental psychologists. The study also omits “hot cognition,” which is cognition that is emotional, reactive, or dependent on personality. These forms of cognition are arguably much more embodied than the “cold” problem solving described by the problem domain. The authors argue that hot cognition should follow and derive from problem solving. This is emblematic of a trend in this form of thought, that other more tricky areas of cognition can just be added on to the architecture.

The study can also be viewed as a theory of psychology. Unlike other forms of theories, this one is content oriented (as opposed to process-oriented). Here the authors explain that a content oriented theory can serve as a model for the content: “The present theory is oriented strongly to content. This is dramatized in the peculiarity that the theory performs the task that it explains. That is, a good information processing theory of a good human chess player can play good chess; a good theory of how humans create novels will create novels; a good theory of how children read will likewise read and understand.” (p. 10-11) What is described here seems to be a generative model, as opposed to an analytic model. However, this authors’ claim is fraught with three counterexamples. Chess programs approach a game of chess very differently than chess players do. Algorithms for story generation (to say nothing of whole novel generation) are leagues behind actual human writers. And text understanding systems are also fraught with difficulty (notably the Bar-Hillel problem for word contextualization).

There is another more fundamental critique with the claim that a content oriented theory will perform the task in question. The issue is that a theory does not actually practice or perform the task that humans do, it merely models it. AI does not think, but it models thinking. It does not solve problems, but solves models of those problems. This distinction is subtle but important. If a problem is easily and non-problematically transformable into a symbolic model, then the solved model should solve the actual problem, but this is only as good as the transformation of reality into the model. Someone may program a computer to solve a model of a problem, such as a disease outbreak, but if the model in the program omits crucial details that arise in the complexity of real life, then the solution is intrinsically flawed.

It is relevant to note the authors’ use of the word “dramatized” in the citation. Dramatization can take on an interesting meaning here when compared to the elements of performance, resemblance, and enactment. A wholly legitimate way to examine AI and problem solving is that the computer dramatically enacts the problem. That is, it represents the problem and the solution dramatically, in the sense of performing to the user meaningfully.

Task Environments

Problem solving takes place in a task environment. The task environment contains the symbolic content necessary to solve the problem. The authors propose using the model of the rational economic man (who maximizes utility). The task (and hence utility) are defined by the task environment: “The term task environment, as we shall use it, refers to an environment coupled with a goal, problem, or task–the one for which the motivation of the subject is presumed.” (p. 55) Performance is inextricably tied to rationality, and the situation is transformed to the task environment. Task environments are internally represented. The internal representation is a symbolic construction which illustrates the problem space: all moves, states, and outcomes.

Internal representations are tied to linguistic structure (which is inherently semiotic). For transcribing problem solving into an information processing system, objects are mapped to symbols. This is unproblematic in the examples given (chess moves, symbolic logic problems), but is much more troublesome in other situations. Even in the example of a chessboard, there are many ways to look at the positions of pieces and encode them symbolically. For example, a pattern would probably be treated as a symbol by a grandmaster. It is obvious to represent piece coordinates as symbols, but it is not the only approach. In domains where the units are less obvious, the symbolic transformation is even more fraught with complexity.

Newell and Simon give their definition for a problem: “A person is confronted with a problem when he wants something and does not know immediately what series of actions he can perform to get it.” (p. 72) This definition alone is rather interesting. Here, a problem is tied to desire as well as possession and attainment. These are very embodied qualities. Given this definition, it is far from obvious what it would mean for a computer to be confronted with a problem. The answer the authors give is that problems can be represented using symbols, as constructed from set or 1st order logic.

Problem Solving

The problem solving process given resembles the architecture of Soar. (p. 88)

  1. An initial process, here called the input translation, produces inside the problem solver an internal representation of the external environment, at the same time selecting a problem space. The problem solving then proceeds in the framework of the internal representation thus produced–a representation that may render solutions obvious, obscure, or perhaps unattainable.
  2. Once a problem is represented internally, the system responds by selecting a particular problem solving method. A method is a process that bears some rational relation to attaining a problem solution, as formulated and seen in terms of the internal representation.
  3. The selected method is applied: which is to say, it comes to control the behavior, both internal and external, of the problem solver. At any moment, as the outcome either of processes incorporated in the method itself or of more general processes that monitor its application, the execution of the method may be halted.
  4. When a method is terminated, three options are open to the problem solver: (a) another method may be attempted, (b) a different internal representation may be selected and the problem reformulated, or (c) the attempt to solve the problem may be abandoned.
  5. During its operation, a method may produce new problems–i.e., subgoals–and the problem solver may elect to attempt one of these. The problem solver may also have the option of setting aside a new subgoal, continuing instead with another branch of the original method.

Logic: GPS and Human Behavior

Work here shows students solving problems and their actions written in the formal logic of GPS. Experimental subjects are either Yale or CMU students. The question of what the students are doing seems to trace back to their formal logic training. The problem domain is still a highly symbolic one to begin with. The problem solving approach is thus not really a representation of how humans solve problems, but how problems tend to be solved within the formal structure of this problem domain.

The Theory of Human Problem Solving

This section is where GPS (and Information Processing Systems in general) are translated into human problem solving. Obviously, my scruples are with the assumptions. The propositions which pose the questions for human problem solving (the assumptions) are these: (p. 788)

  1. Humans, when engaged in problem solving in the kinds of tasks we have considered, are representable as information processing systems.
  2. This representation can be carried to great detail with fidelity in any specific instance of person or task.
  3. Substantial subject differences exist among programs, which are not simply parametric variations but involve differences of structure and content.
  4. The task environment (plus the intelligence of the problem solver) determines to a large extent the behavior of the problem solver, independently of the detailed internal structure of his information processing system.

The propositions to be answered by the chapter are as follows: (p. 788-789)

  1. A few, and only a few, gross characteristics of the human IPS are invariant over task and problem solver.
  2. These characteristics are sufficient to determine that a task environment is represented (in the IPS) as a problem space, and that problem solving takes place in a problem space.
  3. The structure of the task environment determines the possible structures of the problem space.
  4. The structure of the problem space determines the possible programs that can be used for problem solving.

External memory is discussed, but affordances and cognitive extension into situation or environment are not discussed. This has a very mentalistic approach, where symbolic structure of environment is not addressed. The only symbols are in the problem space itself.

Reading Info:
Author/EditorNewell, Allen and Simon, Herbert
TitleHuman Problem Solving
ContextThis is the canonical work that introduces GPS and they symbolic approach to problem solving
Tagsspecials, ai
LookupGoogle Scholar, Google Books, Amazon


[General] (12.12.08, 12:36 pm)

I’m updating to WordPress 2.7. Hopefully this will not break anything. In case it does, it will likely take a little while for it to get fixed. Just a heads-up.