Problem Solving

Solving a problem is transforming a given situation into a desired situation or goal (Hayes 1989). Problem solving may occur inside a mind, inside a computer, in some combination of both, or in interaction with an external environment. An example of the first would be generating an English sentence; of the last, driving to the airport. If a detailed strategy is already known for reaching the goal, no problem solving is required. A strategy may be generated in advance of any action (planning) or while seeking the goal.

Studying how humans solve problems belongs to cognitive psychology. How computers solve problems belongs to artificial intelligence. ROBOTICS studies how computers solve problems requiring interaction with the environment. As similar processes are often used, there is frequent exchange of ideas among these three subdisciplines.

To solve a problem, a representation must be generated, or a preexisting representation accessed. A representation includes (1) a description of the given situation, (2) operators or actions for changing the situation, and (3) tests to determine whether the goal has been achieved. Applying operators creates new situations, and potential applications of all permissible operators define a branching tree of achievable situations, the problem space. Problem solving amounts to searching through the problem space for a situation that satisfies the tests for a solution (VanLehn 1989).

In computer programs and (as cumulating evidence indicates) in people, operators usually take the form of condition-action rules (productions). When the system notices that the conditions of a production are satisfied, it takes the corresponding action of accessing information in memory, modifying information, or acting on the environment (Newell and Simon 1972).

In most problems of interest, the problem space is very large (in CHESS, it contains perhaps 10²⁰ states; in real life, many more). Even the fastest computers cannot search such spaces exhaustively, and humans require several seconds to examine each new state. Hence, search must be highly selective, using heuristic rules to select a few promising states for consideration. Chess grandmasters seldom search more than 100 states before making a move; the most powerful chessplaying computer programs search tens of billions, still a minuscule fraction of the total. In such tasks, expert computer programs trade off computer speed for some human selectivity (De Groot 1965).

The heuristics that guide search derive from properties of the task (e.g., in chess, "Ignore moves that lose pieces without compensation"). If a domain has strong mathematical structure (e.g., is describable as a linear programming problem), strategies may exist that always find an optimal solution in acceptable computation time. In less well structured domains (including most real-life situations) the heuristics follow plausible paths that often find satisfactory (not necessarily optimal) solutions with modest computation but without guarantees of success. In puzzles, the problem space may be small, but misleadingly constructed so that plausible heuristics avoid the solution path. For example, essential intermediate moves may increase the distance from the goal, whereas heuristics usually favor moves that decrease the distance.

An important heuristic is means-ends analysis (Newell and Simon 1972). Differences between the current situation and the goal situation are detected, and an operator selected that usually removes one of these differences. After application of the operator eliminates or decreases the difference, the process is repeated. If the selected operator is not applicable to the current situation, a subgoal is established of applying the operator. Means-ends analysis is powerful and general, but is not useful in all problems: for example, it cannot solve the Rubik's Cube puzzle in any obvious way.

Problems are called well structured if the situations, operators, and goal tests are all sharply defined; ill structured, to the extent that they are vaguely defined. Blending petroleum in a refinery, using linear programming, is a well-structured problem. Playing chess is less well structured, as it requires fallible heuristics to seek and evaluate moves.

Designing buildings and writing novels are highly ill-structured tasks. The tests of success are complex and ill defined, and are often elaborated during the solution process (Akin 1986). The alternative operations for synthesizing a design are innumerable, and may be discovered only by inspecting a partially completed product. As optimization is impossible and several satisfactory solutions may be encountered, the order in which alternatives are synthesized strongly affects the final product. Starting with the floor plan produces a different house than starting with the facade.

The study of problem solving has led to considerable understanding of the nature of EXPERTISE (human and automated). The expert depends on two main processes: HEURISTIC SEARCH of problem spaces, and recognition of cues in the situation that access relevant knowledge and suggest heuristics for the next step. In domains that have been studied, experts store tens of thousands or hundreds of thousands of "chunks" of information in memory, accessible when relevant cues are recognized (Chi, Glaser, and Farr 1988). Medical diagnosis (by physicians or computers) proceeds largely by recognition of symptoms, reinforced by inference processes. Most of what is usually called "intuition," and even "inspiration," can be accounted for by recognition processes.

Testing theories of problem solving, usually expressed as computer programs that simulate the processes, requires observing both outcomes and the steps along the way. At present, the most fine-grained techniques for observation of the processes are verbal (thinking aloud) or video protocols, and eye movement records (Ericsson and Simon 1993). Studies of brain damage and MAGNETIC RESONANCE IMAGING (MRI) of the brain are beginning to provide some sequential information, but most current understanding of problem solving is at the level of symbolic processes, not neural events.

Research has progressed from well-structured problems calling for little specific domain knowledge to ill-structured problems requiring extensive knowledge. As basic understanding of problem solving in one domain is achieved, research moves to domains of more complex structure. There has also been considerable movement "downward" from theories, mainly serial, of symbolic structures that model processes over intervals of a fraction of a second or longer, to theories, mainly parallel, that use connectionist networks to represent events at the level of neural circuits. Finally, there has been movement toward linking problem solving with other cognitive activities through unified models of cognition (Newell 1990).

Recent explorations extend to such ill-structured domains as scientific discovery (e.g., Langley et al. 1987) and architectural design (Akin 1986). In modeling scientific discovery and similarly complex phenomena, multiple problem spaces are required (spaces of alternative hypotheses, alternative empirical findings, etc.). We are learning how experimental findings induce changes in representation, and how such changes suggest new experiments. Allen Newell's (1990) Soar system operates in such multiple problem spaces. Kim, Lerch, and Simon (1995) have explored the generation of problem representations, and there is increasing attention to nonpropositional inference (e.g., using mental IMAGERY in search; Glasgow, Narayanan, and Chandrasekaran 1995). Several models now can represent information in both propositional (verbal or mathematical) and diagrammatic forms, and can use words and mental images conjointly to reason about problems.

Another important area of recent research activity explains intuition and insight in terms of the recognition processes of the large memory structures found in knowledge-rich domains (Kaplan and Simon 1990; Simon 1995). Yet another area, robotics, shows, by studying problem solving in real-world environments (Shen 1994), how the problem-solver's incomplete and inaccurate models of changing situations are revised and updated by sensory feedback from the environment.

Finally, interest in knowledge-rich domains has called attention to the essential ties between problem solving and LEARNING (Kieras and Bovair 1986). Both connectionist learning systems and serial symbolic systems have shown considerable success in accounting for concept learning (CATEGORIZATION), a key to the recognition capabilities of knowledge-rich systems. Self-modifying systems of condition-action rules (adaptive production systems) have been shown capable, under classroom conditions, of accounting for students' success in learning such subjects as algebra and physics from worked-out examples (Zhu et al. 1996) .

References

Akin, O. (1986). Psychology of Architectural Design. London: Pion.

Chi, M. T. H., R. Glaser, and M. Farr. (1988). The Nature of Expertise. Hillsdale, NJ: Erlbaum.

De Groot, A. (1965). Thought and Choice in Chess. The Hague: Mouton.

Ericsson, K. A., and H. A. Simon. (1993). Protocol Analysis. Rev. ed. Cambridge, MA: MIT Press.

Glasgow, J., N. H. Narayanan, and B. Chandrasekaran, Eds. (1995). Diagrammatic Reasoning: Computational and Cognitive Perspectives. Menlo Park, CA: AAAI/MIT Press, pp. 403-434.

Hayes, J. R. (1989). The Complete Problem Solver. 2nd ed. Hillsdale, NJ: Erlbaum.

Kaplan, C., and H. A. Simon. (1990). In search of insight. Cognitive Psychology 22:374-419.

Kieras, D. E., and S. Boviar. (1986). The acquisition of procedures from text. Journal of Memory and Language 25:507-524.

Kim, J., J. Lerch, and H. A. Simon. (1995). Internal representation and rule development in object-oriented design. ACM Transactions on Computer-Human Interaction 2(4):357-390.

Langley, P., H. A. Simon, G. L. Bradshaw, and J. M. Zytkow. (1987). Scientific Discovery: Computational Explorations of the Creative Processes. Cambridge, MA: MIT Press.

Newell, A. (1990). Unified Theories of Cognition. Cambridge, MA: Harvard University Press.

Newell, A., and H. A. Simon. (1972). Human Problem Solving. Englewood Cliffs, NJ: Prentice-Hall.

Shen, W. (1994). Autonomous Learning from the Environment. New York: W. H. Freeman.

Simon, H. A. (1995). Explaining the ineffable: AI on the topics of intuition, insight and inspiration. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence 1:939-948.

VanLehn, K. (1989). Problem solving and cognitive skill acquisition. In M. L. Posner, Ed., Foundations of Cognitive Science. Cambridge, MA: MIT Press.

Zhu, X., Y. Lee, H. A. Simon, and D. Zhu. (1996). Cue recognition and cue elaboration in learning from examples. Proceedings of the National Academy of Sciences 93:1346-1351.

Problem Solving

See also

References

Further Readings