An Introduction to Non-Monotonic Reasoning

Abstract

An AI-agent who does not only adopt some beliefs but also abandons some while working on a given problem is said to reason non-monotonically. Non-monotonic reasoning, NMR in short, subsumes problem solving processes where the need for updating the current set of beliefs may arise at runtime. Belief revision may be required for various reasons, in particular if some current beliefs depend on working hypotheses or consistency assumptions, and if the conditions under which problem solving is done change at runtime. The need for NMR is widely acknowledged, and it has been clear for a long time that standard logical calculi are inadequate for NMR. Thus far, the problems of NMR have most commonly been attacked by some experimental ad-hoc approaches. While these approaches seemed to settle matters nicely in AI's artificial toy worlds, the current trend towards substantial real world applications urges for a deeper understanding of the theoretical foundations of NMR. In the present paper, we emphasize the need for NMR by showing that some well-known problems in AI can't be solved without it. We then discuss some key issues concerned with the theoretical formalization of NMR, as well as with its practical realization. To make things a bit more concrete, we present two prominent approaches to NMR in some detail, Reiter's default logic, and reason maintenance a la Doyle. Some further approaches are reviewed more briefly. An extensive bibliography on NMR is included. Finally, it is argued that the current state of the art in the field is poor when compared with its prospective applications, and we claim the need for long-term basic research in this area.