Managing Change in Answer Set Programs: A Logical Approach

摘要

Answer set programming (ASP) is an appealing, declarative approach for representing problems in knowledge representation and reasoning. While answer sets have a conceptually simple syntactic characterization, ASP has been shown to be applicable to a wide range of practical problems, and efficient implementations are now available. However, as is the case with any body of knowledge, a logic program is not a static object in general, but rather it will evolve and be subject to change. Such change may come about as a result of adding to (or removing from) the program, importing the contents of one program into another, merging programs, or in some other fashion modifying the knowledge in the program. In classical logic, the problem of handling such change has been thoroughly investigated. The seminal AGM approach provides a general and widely accepted framework for this purpose. While this approach focusses on revision and contraction, related work, such as merging, has stayed close to the AGM paradigm. Until recently, the study of change in ASP has been addressed at the level of the program, focussing on the revision (and update) of logic programs. In revision, for example, a typical approach is to begin with a sequence of answer set programs, and determine answer sets based on a priority ordering among the programs or among rules in the programs. An advantage of such approaches is that they are readily implementable. On the other hand, the underlying non-monotonicity of logic programs makes it difficult to study formal properties of an approach. Recently a more logical view of ASP has emerged. Central to this view is the (monotonic) concept of SE-models, which underlies the answer-set semantics of logic programs. In characterizing an AS program by its set of SE models, one can deal with a program at an abstract, syntax-independent level. I suggest that this is an appropriate level for dealing with change in logic programs, complementing earlier syntax-dependent approaches. To this end, I review such work dealing with change in logic programs, begining with the much simpler, but nonetheless relevant, case of Horn theories. From this, I touch on work concerning AS revision, with respect to both specific approaches and logical characterisations. This leads naturally to approaches for merging logic programs. While logic program contraction has not been addressed, I discuss what can be regarded as an extreme case of contraction, that of forgetting. I finish with some thoughts on open problems and issues, and future directions. The overall conclusion is that classical belief change is readily applicable to ASP, via its model theoretic basis.