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