Nonmonotonic reasoning: towards efficient calculi and implementation

Research in nonmonotonic reasoning has begun at the end of the seventies. One of the major motivations came from reasoning about actions and events. John McCarthy and Patrick Hayes had proposed their situation calculus as a means of representing changing environments in logic. The basic idea is to use an extra situation argument for each fact which describes the situation in which the fact holds. Situations, basically, are the results of performing sequences of actions. It soon turned out that the problem was not so much to represent what changes but to represent what does not change when an event occurs. This is the so-called frame problem. The idea was to handle the frame problem by using a default rule of the form If a property P holds in situation S then P typically also holds in the situation obtained by performing action A in S. Given such a rule it is only necessary to explicitly describe the changes induced by a particular action. All non-changes, for instance that the real colour of the kitchen wall does not change when the light is turned on, are handled implicitly. Although it turned out that a straightforward formulation of this rule in some of the most popular nonmonotonic formalisms may lead to unintended results, the frame problem was certainly the challenge motivating many people to join the field. In the meantime a large number of different nonmonotonic logics have been proposed and we have many results that clarify the close relationship as well as the different aspects of such logics. There is quite an agreement in the field that now, after almost twenty years, the conceptual phase has ended and there is enough knowledge available to start implementing nonmonotonic reasoning systems and applying them to non-trivial problems. (orig.)SIGLEAvailable from TIB Hannover: RO 6844(1998,20) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman