Full Text (Final Version)          

    [postscript]             [pdf]

   Acknowledgments                                                               xi
1. Introduction                                                                          1
  1.1 Organization of the Thesis                                            2
  1.2 Notation and Preliminaries                                           3
2. Resource-Bounded Agents                                                5
  2.1 Change in View                                                                 6
  2.2 Minimal Rationality                                                       10
  2.3 Do the Right Thing                                                         13
  2.4 Doxastic Performance                                                    13
  2.5 Doing the Right Revision?                                             16
3. The AGM Paradigm                                                           19
  3.1 Postulates                                                                           20
  3.2 Constructions                                                                    22
  3.3 Shortcomings                                                                    26
  3.4 Alternatives and Refinements                                      27
     3.4.1 Belief Bases                                                                 27
     3.4.2 Non-Prioritized Belief Revision                            35
4. Resource-bounded Belief Change                                    39
  4.1 Belief States                                                                       39
  4.2 Basic Operations                                                               45
  4.3 Embedding AGM Theory                                               48
  4.4 Harman's Principles                                                          51
  4.5 Refining the Model                                                            52
5. Local Change                                                                           59
  5.1 Defining Compartments and Local Inference             61
     5.1.1 Defining Compartments                                             61
     5.1.2 Defining Local Inference                                            64
  5.2 The Generalized Belief Revision Operators                 67
     5.2.1 Contraction                                                                    68
     5.2.2 Consolidation                                                                 70
     5.2.3 External and Internal Revision                                  71
     5.2.4 Semi-Revision                                                               74
     5.2.5 Levi and Harper Identities                                           75
     5.2.6 Local Operators                                                             75
  5.3 Related Work                                                                        76
     5.3.1 Compartments and Frames of Mind                         76
     5.3.2 Paraconsistent Logic                                                     77
     5.3.3 Relevance Logic                                                             78
  5.4 Embedding Local Change                                                  79
  5.5 Conclusions                                                                            81
6. Structured Bases                                                                        83
  6.1 RABIT                                                                                    84
  6.2 Structuring the Belief Base                                                86
  6.3 Where Does the Structure Come from?                          90
     6.3.1 The Syntactic Approach                                               91
     6.3.2 The Database Approach                                               92
     6.3.3 The Logical Approach                                                   92
     6.3.4 The Hybrid Approach                                                    93
  6.4 Computational Aspects                                                        94
  6.5 Related Work                                                                          95
  6.6 Conclusion                                                                               98
7. Local Diagnosis                                                                           99
  7.1 Reiter Diagnosis                                                                    100
     7.1.1 Basic Definitions                                                            100
     7.1.2 Computing Diagnoses                                                    101
  7.2 Diagnosis via Kernel Semi-Revision                               102
  7.3 Using System Structure                                                       105
  7.4 Local Kernel Diagnosis                                                       106
  7.5 Computing Kernel Operations                                          109
     7.5.1 Reiter's Algorithm                                                         109
     7.5.2 An Algorithm for Kernel Semi-Revision                111
     7.5.3 Applying the Algorithm to Local Operations         112
  7.6 Related Work                                                                         112
     7.6.1 Approximate Diagnosis                                                 112
     7.6.2 Assumption-Based Truth Maintenance Systems    114
  7.7 Conclusion                                                                               114
8. Discussion and Future Work                                                   115
A. Full Acceptance Via Argumentation                                 119
  A.1 Argumentation                                                                    120
  A.2 Using Argumentation for Accepting Beliefs                121
  A.3 Example                                                                                122
  A.4 Discussion                                                                             125
B. Proofs related to Chapter 4                                                   127
C. Proofs related to Chapter 5                                                   131
    Bibliography                                                                              149
    Samenvatting                                                                            157
 
 

                                    Introduction

The problem of belief revision has been extensively studied during the last
twenty years.  Given an agent with a set of (ascribed) beliefs, how should he
change his beliefs when confronted with new information? This is the most
general formulation of the problem of belief revision. An agent may be a human
being, a computer program or any kind of system to which one can ascribe
beliefs and from which one would expect rational reactions.

This is a multidisciplinary problem, with applications to several areas. We
can give some examples of belief revision as it appears in:

• Daily life: I believed it was always raining in Amsterdam. One morning I woke up in Amsterdam and the sun was shining. I believed that on that day the weather was fine, contradicting my previous belief. I had to give up my belief that it always rained there.
• Databases: In the database containing data about the customers of a bookstore, there is an entry for John Smith, with his date of birth being 20/2/67. I get then a new order, where John Smith's date of birth is 20/2/76. I cannot add another date of birth and John's date of birth cannot have changed with time. I have to decide what to do. Keep the old data? Substitute it by the new? Or is it another John Smith after all, who should be added to the database?
• Robotics: A mobile robot has a map of the environment where it is supposed to move. On the map, there is nothing in front of it, so it should be able to move straight. But then its sensors indicate the presence of a big object in front of the robot. Should it doubt its sensors and continue trying to move straight? Or should it believe itssensors and doubt the map?
• Diagnosis: I believe that if I put an article at the right position on a properly working copying machine, I get copies of the article. Suppose I put

an article at the right position, but all I get are blank pages. Should I give up my belief that I chose the right position? Or should I give up the belief that the copying machine is working properly?

Belief revision has been extensively studied in philosophy for extremely
idealized agents. The agents considered are infinite beings, without any
limitation  of memory, time, or deductive ability. However, adapting these
solutions to less idealized agents is far from trivial. In order to solve the
problems cited above in a way which can be used by real agents, one has to
consider that any realizable agent is a finite being and that calculations
take time (Cherniak, 1986). We need a theory which takes these characteristics
--- finiteness, memory and time limitations --- into account.
 

Departing from the standard logical model for belief revision, the main goal
of the present work is to find a theory that can be applied to more realistic
agents. We stress here that our purpose is not to find a computational
implementation of existing theories, but to elaborate a theory for less
idealized agents.

In a recent paper, Chopra and Parikh (1999) presented some
desiderata for a belief revision formalism which we also see as our goals:
distinction between explicit and implicit beliefs,
no trivialization in the presence of inconsistencies,
computational tractability, and minimal change.

The main achievements of our work are:
 

1. Formalization of a richer notion of belief state, based on the informal works of Harman and Cherniak (Chapter 4).
2. Generalization of standard results found in the literature, allowing for the use of more general logics (Chapter 5). This part is joint work with Sven Ove Hansson.
3. Design of a psychologically motivated, computationally efficient method for focussing on the relevant part of a belief state (Chapter 6).
4. Application of the developed framework to the problem of model-based diagnosis and use of the computational tools from model-based diagnosis for implementing belief revision operators (Chapter 7).

In the next  chapter, we present an overview of some theories about
resource-bounded agents. Although being very informal, these theories
contain ideas which we will formalize in the following chapters.

In Chapter 3, we will present an overview of the main line of
research in belief revision. We start by introducing the AGM paradigm and then
present some variations on it that have been proposed in the literature.

In Chapter 4, we introduce our formal framework.
We describe the belief state of a resource-bounded agent and operations
that can be applied to it. We also show how our framework relates to
the AGM paradigm and to Harman's informal proposal. Our framework classifies
beliefs according to their status: whether they are explicitly believed
or not, whether they are active or not and whether they are fully accepted
or only provisional. All the operations affect the set of active beliefs.
This set contains the beliefs which are available at a certain time and it
changes according to the goals of the agent.

In Chapters 5 and 6, we turn to the problem of
deciding which beliefs should become active for a belief change operation.
Chapter 5 presents a logical solution, making use of the
notion of local inference. We offer axiomatizations and representation
results for generalizations of several belief change operations found
in the literature.

In Chapter 6 we use extra-logical information in order
to select which part of the belief state should become active. We
present a computationally efficient method of retrieving the relevant part
of an agent's beliefs and show how this method can be combined with
the logical results obtained in Chapter 5.

In Chapter 7, we present an application of the formal
framework developed in the preceding chapters. We show how to use
extra-logical information present in the system descriptions used for
model-based diagnosis in order to focus on a small relevant portion
of the system. We also show how an algorithm used for finding minimal
diagnoses can be adapted for implementing belief revision operators.

Finally, in Chapter 8 we present some conclusions and
point toward future work.
 
 

Back to Renata's Home Page