Human and Machine Problem Solving

Problem solving is a central topic for both cognitive psychology and artificial intelligence (AI). Psychology seeks to analyze naturally occur­ ring problem solving into hypothetical processes, while AI seeks to synthesize problem-solving performance from well-defined processes. Psychology may suggest possible processes to AI and, in turn, AI may suggest plausible hypotheses to psychology. It should be useful for both sides to have some idea of the other's contribution-hence this book, which brings together overviews of psychological and AI re­ search in major areas of problem solving. At a more general level, this book is intended to be a contribution toward comparative cognitive science. Cognitive science is the study of intelligent systems, whether natural or artificial, and treats both organ­ isms and computers as types of information-processing systems. Clearly, humans and typical current computers have rather different functional or cognitive architectures. Thus, insights into the role of cognitive ar­ chitecture in performance may be gained by comparing typical human problem solving with efficient machine problem solving over a range of tasks. Readers may notice that there is little mention of connectionist ap­ proaches in this volume. This is because, at the time of writing, such approaches have had little or no impact on research at the problem­ solving level. Should a similar volume be produced in ten years or so, of course, a very different story may need to be told.

1 Human and Machine Problem Solving: Toward a Comparative Cognitive Science.- 1. Introduction.- 2. Problem Solving.- 2.1. Problems.- 2.2. Solving.- 3. Perspectives.- 3.1. Psychological Perspective.- 3.2. Machine Perspective.- 3.3. Interaction of Human and Machine Perspectives.- 4. Some Issues.- 5. References.- 2 Nonadversary Problem Solving by Machine.- 1. Introduction.- 1.1. Problem-Solving Systems.- 1.2. State Space Search and Problem Reduction.- 1.3. Blind Search and Heuristic Search.- 1.4. Graphs and Trees.- 2. State Space Representation.- 2.1. The Graph Traverser.- 2.2. Blind Search.- 2.3. Heuristic Search.- 3. Problem Reduction Representation: And/or Graphs.- 3.1. Blind Search.- 3.2. Heuristic Search.- 3.3. Means/Ends Analysis.- 4. Planning.- 4.1. Theorem-Proving Approaches.- 4.2. sTRips-like Systems.- 4.3. Hierarchical and Nonlinear Planners.- 5. Conclusions.- 6. References.- 3 Human Nonadversary Problem Solving.- 1. Introduction.- 1.1. Definitions.- 1.2. Types of Problems.- 1.3. Analysis of Problem Solving.- 2. Constraints on a Model of Human Nonadversary Problem Solving.- 2.1. Humans Systematically Distort the Problem To Be Consistent with Prior Knowledge.- 2.2. Humans Focus on Inappropriate Aspects of the Problem.- 2.3. Humans Change the Problem Representation during Problem Solving.- 2.4. Humans Apply Procedures Rigidly and Inappropriately.- 2.5. Humans Are Intuitive and Insightful and Creative.- 2.6. Humans Let Their Beliefs Guide Their Approach to Problem Solving.- 3. Conclusion.- 4. References.- 4 Adversary Problem Solving by Machine.- 1. Introduction.- 2. Search Techniques for Two-Person Games.- 3. Minimaxing with an Evaluation Function.- 4. The Alpha-Beta Algorithm.- 5. Refinements of the Basic Alpha-Beta Rule.- 6. Theoretical Analyses of Alpha-Beta and Its Variants.- 7. Other Problem-Independent Adversary Search Methods.- 8. Selective Search, Evaluation Functions, and Quiescence.- 9. A Short History of Game-Playing Programs.- 10. Example of Implementation Method for Chess.- 11. Knowledge-Based Selective Search.- 12. Exact Play in Chess Endgames.- 13. Other Nonprobabilistic Games.- 14. Games of Imperfect Information, Game Theory.- 15. Conclusion—Likely Future Trends.- 16. References.- 17. Further Reading.- 5 Adversary Problem Solving by Humans.- 1. Adversary Games.- 1.1. Games Research.- 1.2. Memory and Skill.- 1.3. The Need for Alternative Explanations.- 2. Dealing with the Adversary.- 2.1. Predicting Opponent Moves.- 2.2. The Opponent’s Intentions.- 3. Characteristics of the Search Process.- 3.1. Problem Behavior Graphs.- 3.2. Progress through the Tree.- 4. Plans and Knowledge.- 4.1. Using Plans.- 4.2. Using Knowledge.- 4.3. Knowledge and Skill.- 5. Evaluation Functions.- 5.1. Material and Positional Evaluations.- 5.2. Judgment and Skill.- 5.3. Comparison with Computers.- 6. Projecting Ahead.- 6.1. Following One Line of Moves.- 6.2. Anticipation through a Tree.- 6.3. Human Minimaxing.- 7. Humans versus Computers.- 7.1. Knowledge, Search, and Evaluation.- 7.2. Experimental Comparisons.- 7.3. Playing against Computers.- 8. Overview.- 8.1. Unresolved Issues.- 8.2. Conclusions.- 9. References.- 6 Machine Expertise.- 1. The Automation of Problem Solving—Continuing a Tradition.- 2. Problem-Solving Knowledge Representation.- 3. The Nature of Expert Knowledge.- 4. Knowledge Representation.- 5. Problems with the Traditional Approach.- 6. Architectures for Representing Machine Expertise.- 6.1. The Production System Approach.- 6.2. Multiple Experts and Mixed Reasoning Strategies.- 6.3. The Set-Covering Approach (or Frame Abduction).- 6.4. Multiple Paradigms.- 7. The Rule-Based Approach—mycin, prospector, and xcon.- 7.1. The mycin System.- 7.2. The xcon System (r1).- 7.3. The prospector System.- 8. The Blackboard Approach (hearsay).- 9. The Set-Covering Approach (Frame Abduction).- 9.1. The Inference Mechanism.- 9.2. System D—An Example.- 9.3. The internist System.- 10. Multiple Paradigm Approaches.- 10.1. The compass System.- 11. Expert System Shells.- 11.1. The Shell Concept.- 11.2. What Does a Shell Provide?.- 11.3. What Sorts of Shells Exist?.- 12. Recent Developments.- 12.1. Nonmonotonic Reasoning.- 12.2. Deep Knowledge.- 12.3. Commonsense Reasoning and Causality.- 12.4. Better Tools.- 13. Conclusions.- 14. References.- 7 Human Expertise.- 1. Introduction.- 2. The Theoretical Framework: Information-Processing Theory of Problem Solving.- 3. The Construction of a Problem Representation.- 4. The Role of Schemata in Problem Solving.- 5. Problem-Solving Strategies.- 5.1. Interaction of Different Problem-Solving Strategies.- 5.2. Switching Problem-Solving Strategy.- 6. The Development of Expertise.- 6.1. Acquisition of Episodic Knowledge Structures.- 6.2. Acquisition of Procedural Knowledge.- 7. Conclusion.- 8. References.- 8 Machine Inference.- 1. Input of Knowledge.- 1.1. Formal Languages.- 1.2. Recognition and Parsing.- 1.3. Translation.- 1.4. Summary of Input of Knowledge.- 2. Machine Inference Based on Logic.- 2.1. Introduction.- 2.2. Classical Propositional Logic.- 2.3. Automatic Inference in Classical Propositional Logic.- 2.4. Summary of Machine Inference Based on Logic.- 3. The Production-Rule-Based Approach to Inference.- 3.1. What Is a Production-Rule-Based System?.- 3.2. Origins of the Production-Rule-Based Approach.- 3.3. Rule Application.- 3.4. Accommodating Uncertainty.- 3.5. Summary of the Production-Rule-Based Approach to Inference.- 4. The Frame-Based Approach to Inference.- 4.1. Some Definitions.- 4.2. Matching.- 4.3. Finding the Best Match.- 4.4. Inference in the Frame-Based Approach.- 4.5. Summary of the Frame-Based Approach to Inference.- 5. The Current Status of Machine Inference.- 5.1. The Status of the Logic-Based Approach to Inference.- 5.2. The Status of the Production-Rule-Based Approach to Inference.- 5.3. The Status of the Frame-Based Approach to Inference.- 5.4. Integration of Techniques from All Three Approaches.- 6. References.- 9 Human Inference.- 1. Introduction.- 1.1. What Is an Inference?.- 1.2. Implicit and Explicit Inferences.- 1.3. Logic and Comprehension.- 2. The Mental Logic Approach.- 2.1. Henle’s Argument.- 2.2. Mental Logic and Propositional Reasoning.- 2.3. Other Arguments and Evidence for Mental Logic.- 3. The Mental Models Approach.- 3.1. Simulation by Mental Model.- 3.2. Truth-Functional Reasoning.- 3.3. Propositional Reasoning with Mental Models.- 3.4. Reasoning with Syllogisms.- 4. The Nature of Inference.- 4.1. The Argument from Observation.- 4.2. Analytical Comprehension Revisited.- 4.3. Conclusion.- 5. References.- 10 Machine Learning.- 1. Introduction.- 2. Learning Concepts from Examples: Problem Statement.- 2.1. Concepts as Sets.- 2.2. Description Languages for Objects and Concepts.- 2.3. The Problem of Learning from Examples.- 2.4. Criteria of Success.- 3. Learning Concepts by Induction: A Detailed Example.- 4. Learning Decision Trees and Coping with Noise.- 4.1. The TDIDT Family of Learning Programs.- 4.2. Tree Pruning in TDIDT Programs.- 4.3. How Pruning Affects Accuracy and Transparency of Decision Trees.- 5. Other Approaches to Learning and Bibliographical Remarks.- 6. References.- 11 Human Learning.- 1. Introduction.- 2. Schemata, Scripts, and Frames.- 3. Amnesia.- 4. Retrieval from Long-Term Memory.- 5. Concept Learning.- 6. Conclusions.- 7. References.- 12 Problem Solving by Human-Machine Interaction.- 1. Problem Solving for the Real World.- 1.1. What Is Problem Solving?.- 1.2. The Importance of Problem Solving.- 1.3. How Can Computers Help People Solve Problems?.- 2. Problem Solving Reconsidered from a Human Factors Perspective.- 2.1. The Importance of the Task.- 2.2. The Importance of the User.- 2.3. The Importance of the Interface.- 2.4. Recommendations for Human-Computer Problem Solving.- 3. Stages of the Problem-Solving Process.- 3.1. Problem Finding.- 3.2. Problem Formulation.- 3.3. Idea Generation.- 3.4. Idea Evaluation.- 3.5. Solution Match with Goal.- 3.6. Solution Match with Environment.- 3.7. Idea Integration.- 3.8. Acceptance or Modification.- 3.9. Planning for Implementation.- 3.10. Measuring the Outcome.- 3.11. Evaluating the Process.- 4. Human-Computer Problem Solving: Cases.- 4.1. Speech Synthesis as an Interface Problem.- 4.2. The Computer as an Active Communications Medium.- 5. A Retrospective Example.- 5.1. Designing a Strategy for Human Factors.- 5.2. The Actual Use of Computers in Solving This Problem.- 5.3. The Potential for Human-Computer Problem Solving.- 6. Summary and Conclusions.- 7. References.- 8. Further Reading.- 13 Human and Machine Problem Solving: A Comparative Overview.- 1. Introduction.- 2. Nonadversary Problems.- 3. Adversary Problems.- 4. Expertise.- 5. Inference.- 6. Learning.- 7. Solving Problems by Human-Computer Interaction.- 8. Concluding Comments.- 9. References.- Author Index.