Lee Arthur Spector, Doctor of Philosophy, 1992
Advisory Committee:
Dr. James Hendler, Chairman/Advisor
Dr. Jordan Grafman
Dr. John Horty
Dr. Dana Nau
Dr. James Reggia
This dissertation investigates the utility of abstraction for agents living in complex, dynamic environments. The generation of intelligent behavior in such environments requires the integration of deliberative and reactive processes. Modularity and hierarchy have proven to be valuable organizational principles in this context, and the notion of "levels of abstraction" has played a particularly important role. This dissertation presents a form of abstraction called supervenience, of which other common forms of abstraction are special cases. Supervenience is based on epistemological "distance from the world," and is particularly useful for integrating deliberative processes with actions in a changing environment. Supervenience is discussed in relation to the literature of AI planning systems, the literature of cognitive psychology, and the philosophical literature in which the term originated. Supervenience is described in the context of nonmonotonic reasoning systems, and is compared to related formal constructs. A program based on the concept of supervenience is described, and its performance in a dynamic-world planning domain is demonstrated.
c) Copyright by Lee Arthur Spector, 1992
TABLE OF CONTENTS
Section Page
Chapter 1 Introduction 1
PART I PLANNING, REACTION, AND ABSTRACTION
Chapter 2 Planning and Reaction 6
2.1 Static-World Planning 7
2.2 Generating Planned Activity 3
2.3 Problems of Integrated Behavior 19
Chapter 3 Abstraction in Planning 26
3.1 The Abstraction Kaleidoscope 26
3.2 Reduced Partition Abstraction 35
3.3 Partitioned Control Abstraction 39
3.4 Reduced Partitions and Partitioned Control 45
PART II SUPERVENIENT LEVELS
Chapter 4 Supervenience 48
Chapter 5 Supervenience Formalized 59
5.1 The Role and Nature of the Formalism 59
5.2 Argument Systems 64
5.3 Layered Argument Systems and Supervenient Planning Hierarchies 68
Chapter 6 Supervenience and ABSTRIPS 72
PART III IMPLEMENTATION
Chapter 7 The Supervenience Architecture 84
7.1 Introduction 85
7.2 The Gulf Between Theory and Practice 86
7.3 General Architecture 88
7.4 Comparison to the Subsumption Architecture 93
Chapter 8 The Abstraction-Partitioned Evaluator (APE) 97
8.1 Introduction 97
8.2 Specific Levels 98
8.2.1 Philosophical and Psychological Evidence 99
8.2.2 Summary of Levels in APE 104
8.2.2 Types of Knowledge at Each Level 107
8.3 Specialization of the Supervenience Architecture 110
8.4 Knowledge Representation 113
8.5 Operators 120
8.6 Translators 127
8.7 Strategies for Monitoring 132
8.8 Parallelism: Theoretical and Simulated 138
Chapter 9 HomeBot 142
9.1 Domain Description 142
9.2 Application of APE 147
9.3 Examples 149
9.3.1 Basic Examples 150
9.3.1.1 Basic Operators and Translators 151
9.3.1.2 HomeBot Feels Pain 154
9.3.1.3 HomeBot Navigates 164
9.3.1.4 HomeBot and the Ice Cube 170
9.3.2 Doorbells, Fire, and Overflowing Sinks 178
9.3.2.1 Doorbells 178
9.3.2.2 Fire 182
9.3.2.3 Overflowing Sinks 186
9.4 Performance 190
PART IV CONCLUSIONS
Chapter 10 Summary and Future Directions 196
Bibliography 208