Title of Dissertation:
Supervenience in Dynamic-World Planning

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

Abstract

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


Availability


TABLE OF CONTENTS

Section Page (in pdf version)

Chapter 1 Introduction 1


PART I PLANNING, REACTION, AND ABSTRACTION 5

Chapter 2 Planning and Reaction 7
2.1 Static-World Planning 7
2.2 Generating Planned Activity 10
2.3 Problems of Integrated Behavior 14

Chapter 3 Abstraction in Planning 19
3.1 The Abstraction Kaleidoscope 19
3.2 Reduced Partition Abstraction 24
3.3 Partitioned Control Abstraction 27
3.4 Reduced Partitions and Partitioned Control 30


PART II SUPERVENIENT LEVELS 33

Chapter 4 Supervenience 35

Chapter 5 Supervenience Formalized 41
5.1 The Role and Nature of the Formalism 41
5.2 Argument Systems 44
5.3 Layered Argument Systems and Supervenient Planning Hierarchies 46

Chapter 6 Supervenience and ABSTRIPS 49


PART III IMPLEMENTATION 57

Chapter 7 The Supervenience Architecture 59
7.1 Introduction 59
7.2 The Gulf Between Theory and Practice 59
7.3 General Architecture 61
7.4 Comparison to the Subsumption Architecture 65

Chapter 8 The Abstraction-Partitioned Evaluator (APE) 69
8.1 Introduction 69
8.2 Specific Levels 69
8.2.1 Philosophical and Psychological Evidence 70
8.2.2 Summary of Levels in APE 73
8.2.2 Types of Knowledge at Each Level 75
8.3 Specialization of the Supervenience Architecture 77
8.4 Knowledge Representation 79
8.5 Operators 83
8.6 Translators 87
8.7 Strategies for Monitoring 90
8.8 Parallelism: Theoretical and Simulated 94

Chapter 9 HomeBot 97
9.1 Domain Description 97
9.2 Application of APE 101
9.3 Examples 103
9.3.1 Basic Examples 103
9.3.1.1 Basic Operators and Translators 103
9.3.1.2 HomeBot Feels Pain 106
9.3.1.3 HomeBot Navigates 114
9.3.1.4 HomeBot and the Ice Cube 119
9.3.2 Doorbells, Fire, and Overflowing Sinks 126
9.3.2.1 Doorbells 126
9.3.2.2 Fire 129
9.3.2.3 Overflowing Sinks 132
9.4 Performance 136


PART IV CONCLUSIONS 142

Chapter 10 Summary and Future Directions 144


Bibliography 152