Practical belief change

In this study, we seek to provide a framework for the design of practical systems for belief change. We do this through the following steps:;Competence. The work of Alchourron, Gardenfors and Makinson provides a comprehensive and widely accepted competence theory for the process of belief change. We identify the following major drawbacks in this theory: (1) It provides an inadequate account of the process of retracting a belief. Thus, the addition of a belief is duly recorded in the belief state of an agent, but the retraction of a belief is never recorded. (2) The theory provides no prescription on how beliefs must change when the belief input is not fully credible. Any approach to handling uncertain or less credible belief inputs should involve a generalization of techniques applied when the belief inputs are fully credible, instead of requiring a totally distinct set of techniques. (3) It is generally agreed that the principle of informational economy should guide any strategy for belief change. This requires that beliefs should be discarded as little as possible while effecting belief change. The competence theory of Alchourron, Gardenfors and Makinson seeks to satisfy this requirement, but with limited success. (4) The theory does not specify belief change beyond a single step. We develop a theory that accounts for each of the problems mentioned above, and argue that it provides an adequate set of benchmark tests, as well as a suitable starting point for implemented belief change systems.;Performance. We present the design of two belief change systems which use a variant of default logic as the belief representation language. The design of the first system preceded the development of our competence theory and provided the motivation for this theory, by identifying several of the lacunae in the existing definition of competence. The second system was developed using our competence theory as the starting point. These two designs serve to demonstrate that practically implementable systems that satisfy the requirements identified in our competence theory are indeed possible. The use of a default logic variant has several other practical benefits as well, such as the ability to incorporate lazy evaluation strategies in computing belief change.;Implementation. Belief change is a computationally hard problem, including our formulation of the problem in the two systems mentioned above. Nevertheless, practical constraints often require tractable solutions, or procedures that exhibit resource-bounded rationality. We present a toolkit of two approaches to address such concerns. First, we define a mapping from the problem of default inference to partial constraint satisfaction problems. The mapping enables us to apply techniques from the area of partial constraint satisfaction to improve the efficiency of procedures for computing default extensions, and hence for computing belief change. Next, we present a set of strategies for computing meaningful partial results in resource-bounded situations, by defining anytime procedures for default inference. (Abstract shortened by UMI.)...