Artificial Intelligence Techniques in PROLOG

Preface Acknowledgments Software Availability 1 On Prolog 1.1 A checklist 1.2 Additional prolog material 1.2.1 Standard lists and 'and' lists 1.2.2 'All-solutions' predicates 1.2.3 Indexing 1.2.4 last-call optimization 1.2.5 Difference lists and 'holes' 1.2.6 Static and dynamic predicates 1.2.7 Bitwise operations 1.2.8 Database references 1.3 Utility predicates 2 Search 2.1 Review of basic graph-theoretic terminology 2.2 Representing graphs in Prolog 2.2.1 Representing graphs 2.2.2 Representing trees 2.2.3 Representing and-or trees 2.3 Review of graph search techniques 2.4 Depth-first search 2.5 Breadth-first search 2.6 Iterative deepening 2.7 Best-first search 2.7.1 The general best-first algorithm 2.7.2 The A* algorithm 2.8 Game-tree search 2.8.1 Minimax search 2.8.2 (-( search 2.9 Further reading 2.10 Exercises 3 Backward-Chaining Methods 3.1 The basic meta-interpreter 3.2 A full standard meta-interpreter 3.4 Toward an expert-system shell 3.4.1 An explanatory meta-interpreter 3.4.2 An interpreter with a query mechanism 3.5 Partial evaluation 3.6 A breadth-first meta-interpreter 3.7 A best-first meta-interpreter 3.8 Further reading 3.9 Exercises 4 Other Rule-Based Methods 4.1 Forward chaining 4.1.1 Representing positive forward-chaining rules 4.1.2 Forward chaining with positive rules, unoptimized 4.1.3 Optimizing the implementation 4.1.4 Representing general forward-chaining rules 4.1.5 Forward chaining with negative conditions 4.1.6 Termination conditions for forward chaining 4.1.7 Variables in forward-chaining rules 4.2 Production systems 4.2.1 The general structure of a production system 4.2.2. Implementing a generic production system 4.2.3 Determining the conflict set 4.2.4 Resolving the conflict set 4.2.5 Firing a production rule 4.3 Further reading 4.4 Exercises 5 Truth Maintenance Systems 5.1 Reason maintenance 5.1.1 Justifications and premises 5.1.2 Operations on RMSs 5.1.3 An inefficient Prolog implementation 5.1.4 Optimizing the implementation 5.2 Consistency maintenance 5.3 Assumption-based truth maintenance 5.3.1 The structure of an ATMS 5.3.2 Operations on an ATMS 5.3.3. An implementation of an ATMS 5.4 Further reading 5.5 Exercises 6 Constraint Satisfaction 6.1 Precise definition of CSP 6.2 Overview of constraint satisfaction techniques 6.3 Consistency enforcing 6.4 Consistency enforcing in temporal reasoning 6.5 Further reading 6.6 Exercises 7 Reasoning with Uncertainty 7.1 Representing uncertainty in the database 7.2 A general meta-interpreter with uncertainty 7.3 Informal heuristics 7.4 Certainty factors in MYCIN 7.5 A review of probability theory 7.6 Bayesian networks 7.7 Further reading 7.8 Exercises 8 Planning and Temporal Reasoning 8.1 Basic notions 8.1.1 Plan and action libraries 8.1.2 The blocks world 8.1.3 Planning problems 8.2 Linear planning 8.2.1 STRIPS 8.2.2 Goal protection and goal regression 8.3 Nonlinear planning 8.4 Time map management 8.4.1 The basic time map manager 8.4.2 Abductive queries 8.4.3 Causal time maps 8.5 Further reading 8.6 Exercises 9 Machine Learning 9.1 Inductive inference 9.1.1 Concept hierarchies 9.1.2 Prolog representation of concept hierarchies 9.1.3 Inductive inference algorithms 9.2 Induction of decision trees (ID3) 9.3 Explanation-based learning 9.3.1 Generalizing correct reasoning 9.3.2 Learning from failed reasoning 9.4 Further reading 9.5 Exercises 10 Natural Language 10.1 Syntax 10.1.1 Context-free grammars 10.1.2 Definite Clause Grammars (DCGs) 10.1.3 Parse trees 10.1.4 Syntactic extensions 10.2 Semantics 10.2.1 Semantic representation 10.2.2 Compositionality principle 10.2.3 Quantification 10.2.4 Tensed verbs 10.3 Further reading