Toward Efficient Default Reasoning

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Nonmonotonic Reasoning

Early work on default reasoning aimed to formalize the notion of quickly jumping to conclusions. Unfortunately, the resulting formalisms have proven more computationally complex than classical logics. This has dramatically limited the applicability of formal methods to real problems involving defaults. The complexity of consistency checking is one of the two problems that must be addressed to reduce the complexity of default reasoning. We propose to approximate consistency checking using a novel synthesis of limited contexts and fast incomplete checks, and argue that this combination overcomes the limitations of its component parts. Our approach trades correctness for speed, but we argue that the nature of default reasoning makes this trade relatively inexpensive and intuitively plausible. We present a prototype implementation of a default reasoner based on these ideas, and a preliminary empirical evaluation.