Off-line Reasoning for On-line Efficiency

Abstract

The complexity of reasoning is a fundamental issue in AI. In many cases, the fact that an intelligent system needs to perform reasoning on-line contributes to the difficulty of this reasoning. In this paper we investigate a couple of contexts in which an initial phase of off-line preprocessing and design can improve the on-line complexity considerably. The first context is one in which an intelligent system computes whether a query is entailed by the system's knowledge base. We present the notion of an efficient basis for a query language, and show that off-line preprocessing can be very effective for query languages that have an efficient basis. The usefulness of this notion is illustrated by showing that a fairly expressive language has an efficient basis. The second context is closely related to the artificial social systems approach introduced in [MT90]. We present the design of a social law for a multi-agent environment as primarily an instance of off-line processing, and study this problem in a particular model. We briefly review the artificial social systems approach to design of multi-agent systems, introduced in [MT90] . Computing or coming up with a social law is viewed as a primarily off-line activity that has major impact on th e effectiveness of the on-line activity of the agents. The tradeoff between the amount of effort invested in computing the social law and the cost of the on-line activity can thus be viewed as an off-line vs. on-line tradeoff.