Problem Solving Methods

✍ Scribed by Dieter Fensel

• Publisher: Springer
• Year: 2000
• Tongue: English
• Leaves: 161
• Category: Library

✦ Synopsis

Researchers in Artificial Intelligence have traditionally been classified into two categories: the “neaties” and the “scruffies”. According to the scruffies, the neaties concentrate on building elegant formal frameworks, whose properties are beautifully expressed by means of definitions, lemmas, and theorems, but which are of little or no use when tackling real-world problems. The scruffies are described (by the neaties) as those researchers who build superficially impressive systems that may perform extremely well on one particular case study, but whose properties and underlying theories are hidden in their implementation, if they exist at all. As a life-long, non-card-carrying scruffy, I was naturally a bit suspicious when I first started collaborating with Dieter Fensel, whose work bears all the formal hallmarks of a true neaty. Even more alarming, his primary research goal was to provide sound, formal foundations to the area of knowledge-based systems, a traditional stronghold of the scruffies - one of whom had famously declared it “an art”, thus attempting to place it outside the range of the neaties (and to a large extent succeeding in doing so).

✦ Table of Contents

Lecture Notes in Artificial Intelligence
Problem-Solving Methods
Preface
Acknowledgments
Table of Contents
Section I: What Are Problem-Solving Methods
1 Making Assumptions for Efficiency Reasons
1.1 A Definition of a Task
1.2 A Non-efficient Problem Solver
1.3 An Efficient Problem Solver
1.4 Summary of the Case Study
1.5 The Twofold Role of Assumptions
1.6 How Deal Other Approaches with Assumptions and Efficiency
2 An Empirical Survey of Assumptions
2.1 Assumptions Necessary to Define the Task
2.1.1 Identifying Abnormalities
2.1.2 Identifying Causes
2.1.3 Defining Hypotheses
2.1.4 Defining Diagnoses
2.1.5 Summary
2.2 Assumptions Necessary to Define an Efficient Problem Solver
2.2.1 Reducing the Worst-Case Complexity
2.2.2 Reducing the Average-Case Behavior
2.2.3 Search Guidance
2.2.4 Summary
2.3 Assumptions in System-Environment Interaction
2.4 Summary
Section II: How to Describe Problem-Solving Methods
3 A Four Component Architecture for Knowledge-Based Systems
3.1 The Entire Framework
3.1.1 The Main Elements of a Specification
3.1.2 The Main Proof Obligations
3.2 Task
3.3 Problem-Solving Method
3.3.1 The Black Box Description: Competence and Requirements
3.3.2 The Operational Specification
3.4 Domain Model
3.5 Adapters
3.5.1 Connecting Task and Problem-Solving Method
3.5.2 Connecting with the Domain Model
3.6 Related Work
4 Logics for Knowledge-Based Systems: MLPM and MCL
4.1 Specification Languages for Knowledge-Based Systems
4.1.1 (ML)**2
4.1.2 KARL
4.1.3 Design Rationales for a Logic of Dynamics
4.2 Logics for the Dynamics of Knowledge-Based Systems
4.2.1 Modal Logic of Predicate Modification (MLPM)
4.2.2 Modal Change Logic (MCL)
4.2.3 Modeling MLPM with MCL
4.3 Formalizing Other Approaches
4.3.1 Formalizing KADS Languages
4.3.2 Using MCL to Formalize Abstract State Machines
4.3.3 Approaches Using Different Paradigms
5 A Verification Framework for Knowledge-Based Systems
5.1 The Architecture in KIV
5.2 Formalizing a Task
5.3 Formalizing a Problem-Solving Method
5.4 Proving Total Correctness of the Problem-Solving Method
5.5 Adapter: Connecting Task and Problem-Solving Method
5.6 A Specific Pattern in Specifying Architectures of Knowledge-Based Systems
5.7 Future Work
Section III: How to Develop and Reuse Probelem-Solving Methods
6 Methods for Context Explications and Adaptation
6.1 Inverse Verification of Problem-Solving Methods
6.1.1 First Example: A Local Serach Method
6.1.2 Second Example: Finding an Abductive Explanation
6.1.3 Heuristic Assumptions
6.1.4 Related Work
6.2 Stepwise Adaptation of Problem-Solving Methods
6.2.1 Local Search
6.2.2 Hill-Climbing
6.2.3 Set-Minimizer
6.2.4 Abductive Diagnosis
6.2.5 Generalization and Limitation of Refinement with Adapters
7 Organizing a Library of Problem-Solving Methods
7.1 The Three Dimensions in Method Organization
7.2 Deriving Task-Specific Problem-Solving Methods
7.2.1 Problem Type Design
7.2.2 Local Search
7.2.3 Local Search as Design Problem Solving
7.2.4 Problem Type Parametric Design
7.2.5 Local Search as Parametric Design Problem Solving
7.3 Variating the Problem-Solving Paradigm
7.3.1 Derive Successor Candidates
7.3.2 Select the Design Model that Is to Be Expanded Next
7.3.3 Update the Set of Future Candidates
7.4 Conclusions
Conclusions and Future Work
Open Issues
Reasoning Agents in the Cyperspace