Off-line Reasoning for On-line Efficiency

1 Introduction

Many activities in the framework of knowledge repre­ sentation and reasoning are concerned with the following task: An intelligent agent has a given representation of a system (or a relevant aspect of the world), and a problem that relates to this representation. Its task is to solve this problem relatively efficiently. Typical examples include

*This work was supported in part by a grant from the US-Israel Binational Science Foundation. The first author is incumbent of the Helen and Milton A. Kimmelman Career Development Chair.

Off-line Reasoning for On-line Efficiency*

Yoram Moses

Department of Applied Math and CS The Weizmann Institute of Science Rehovot, 76100 Israel Moshe Tennenholtz Robotics Lab Department of Computer Science Stanford University Stanford, CA 94305

planning and computing whether a query is entailed by a given knowledge base. The reasoning in both of these cases can be thought of as on-line reasoning: When an input is given, our algorithm should reason about the system and about the problem instance, and should find a solution to the problem. In order to handle such prob­ lems, researchers often use general schemes of knowl­ edge representation such as First Order Logic [MH81], logic programs [Kow74], semantic networks [Qui67], etc. Moreover, the reasoning .is then carried out using gen­ eral schemes of reasoning such as resolution for theorem proving, Prolog for logic programs, etc.

Consider the following question: Can our agent im­ prove its on-line performance in a case where the model it uses (e.g., its knowledge-base or representation of the world) is fixed, and we know ahead oftime that the agent is to be asked to solve many problems with respect to this model? Intuitively, it is clear that the answer should be positive; given a fixed model there should invariably be special-purpose algorithms for solving problems with respect to this particular model, instead of using gen­ eral schemes of reasoning. This answer, however, is not very useful to the agent, without our providing the agent with a way in which it can obtain such special-purpose algorithms. Our aim in this paper is to consider the problem of how an initial phase of off-line preprocessing can serve to reduce the complexity of the agent's on­ line behavior. We are especially interested in systems where agents might be presented with (perhaps expo­ nentially) many potential problems during the on-line activity. In such a case the agent should be allowed to perform rather extensive preprocessing without increas­ ing the amortized cost per solution significantly. Specif­ ically, we shall investigate two central contexts. The first involves an intelligent system that needs to compute whether particular formulas (queries) are entailed by its knowledge base. We present the notion of an efficient basis for a query language, and show that off-line pre­ processing can be very effective for query languages that have an efficient basis. The second context involves dy­ namic multi-agent activity, and is closely related to the artificial social systems approach introduced in [MT90] .

Reactive approaches to problems in AI, related espe­ cially to planning, have been suggested in a number of works (see [Agr91],[AC87]) . Some other works suggested to compile reactive behaviors in advance (see [Sch87]). However, the task of improving on-line behavior does not need to concentrate only on "real" reactive behav­ ior. On-line behavior might refer more generally to the behavior of an agent where it faces various problems af­ ter the initialization of the system. The main task is to identify areas where off-line processing can be helpful and to suggest a particular type of solution for each such area. This is exactly the objective of this work.

This paper is organized as follows. Section 2 contains a high-level discussion about how off-line reasoning can be used in two general scenarios. In Section 3 we discuss a property of query languages that makes preprocessing of knowledge bases for these languages extremely effective. Section 4 presents a fairly expressive query language with the property described in Section 3, and considers addi­ tional examples in which off-line preprocessing is useful in the context of knowledge bases. Section 5 relates the artificial social systems approach to the on-line vs. off­ line reasoning paradigm.

2 Off-line versus on-line reasoning

Consider the well known problem of determining whether queries are entailed by a knowledge base, as dis­ cussed for example in [Lev89] . We assume that we have a knowledge base ]{ B expressed in some logical language, and a query language QL in which queries concerning f{ B are formulated. Given a query a, we are interested in whether J( B f= a. This problem is intractable in the generic case. Moreover, even for tractable queries, the verification process might be very inefficient. There are two main approaches that are discussed in the AI literature for overcoming this difficulty:

1. Replacing problem-solving by model checking [HV91]: discuss knowledge bases that represent specific models, so that a query needs only to be checked against a model, rather than computing whether it is logically entailed by a knowledge base.
2. Decreasing the expressive power of the knowledge base and of the query language in order to have more tractable queries.

The first approach is in fact the way in which rela­ tional databases are treated in theoretical computer sci­ ence. The second is concerned with finding good trade­ offs between expressiveness and complexity (as is done in the knowledge base case by [Lev89], or in the case of multi-agent activity by [TM89]).

Another potential way for decreasing complexity is the following. Assume that any specific query can be veri­ fied in time t where t might be large but feasible (e.g., super-linear but polynomial in the size of the knowledge base ]{B). The question is whether we can find a subset QL' C QL of a feasible size, verify off-line for each mem­ ber a of Q L' whether ]{ B F= a (all of this might take a lot of time), and use this off-line processing in order to make the on-line behavior more efficient. In the next sections we illustrate how this approach can be useful. We point to a general set of queries that can be han­ dled in this way, and discuss specific examples. Notice that this approach can be treated as a type of multiple query optimization. However, the context of our query optimization (entailment by knowledge bases instead of retrieval from relational databases), and the actual way in which it is performed (off-line preprocessing instead of clever retrieval of a set of queries after their arrival) will be different from classical multiple query optimization (see [Sel88]).

Another area in which off-line design can improve on­ line reasoning is multi-agent activity. A major issue in multi-agent activity is concerned with the coordination of agents' activities (see [BG88] for a collection of papers on this topic and on other topics in multi-agent activ­ ity). There are several ways for coordinating activity, such as deals and negotiations (e.g., [RG85], [DS83]). Here we will concentrate on a specific methodology for coordinating activity called artificial social systems. We will now briefly review the artificial social systems ap­ proach to multi-agent activity (see [MT90] and [MT91]) and discuss its connection to the off-line vs. on-line idea.

Consider the following scenario: You are the manager of a large warehouse that treats tens of customers at a time. You have just received a shipment of fifty mobile robots for the purpose of automating your warehouse. Clearly, at any given time different robots will serve the needs of different clients (some of them may concurrently perform additional maintenance operations) . Before you can put the robots to work, you are faced with a major design problem involving how to make effective use of the robots. The artificial social systems approach to this problem, introduced in [MT90, MT91, Ten91], is to al­ low robots to work individually but force them to obey certain social laws, conventions, etc. The basic thesis of this approach is that the right social laws can signifi­ cantly simplify both a robot's task of planning to achieve its goals, and the amount of work it needs to perform while actually pursuing the goal. The choice of these laws, however, is a delicate matter . Notice that devis­ ing appropriate social laws can be considered as off-line processing, while devising a plan for achieving a specific goal in a given situation (while obeying the social order) corresponds to solving a problem on-line. We discuss this issue in greater detail in Section 5.

3 Languages with an efficient basis

In this section we concentrate on off-line reasoning in the knowledge base case. We assume that each query formulated in the query language Q L can be verified in time t (generally, t might be a function of the size of the knowledge base and of the size of the current query). For ease of exposition we will assume that the knowl­ edge base K B and every query a E Q L are formulas in the language C of propositional logic. Let us de­ note the set of primitive propositions in this logic by X= {x1,x2, ... ,xn,· ··}· We use£; to denote the set of formulas of C whose primitive propositions are a sub­ set of {x1 , x2 , ... , x;}. As usual, we define the size of a formula to be the number of symbols appearing in the formula. We will associate with every query lan­ guage QL an infinite sequence QL1 ~ QL2 ~ · · ·, where Q L; = Q L n £;. We say that a query language Q L' is of polynomial size if there exists a fixed polynomial p( i), such that IQL:I < p(i), where IQL:I denotes the number of elements in QL';·

We can spend time t(lal) to compute any given query a . However, if we expect to encounter exponen­ tially many queries of a certain size, it will be very costly to compute each one of them from scratch. In such a case it would be desirable to identify a small set of queries which, once computed, make computing other queries considerably simpler. If we consider polynomially many queries a reasonably small number, this leads to the fol­ lowing definitions:

Definition 3.1: A set B ~ QL of queries will be called a basis for QL if every query in QL is equivalent to a conjunction of elements of B . A basis is called an efficient basis if its size (as a sublanguage of QL) is polynomial.

Given these definitions, we can now show:

Theorem 3.1: Let Q L be a query language, and let Q L' be an efficient basis for Q L. Moreover, let K B be a knowledge base and let n ~ 1 be an integer for which K B ~ Cn holds. Finally, let t be an upper bound on the time it takes to compute whether K B F a' for an arbitrary a' E Q L~. Then there exists an off-line computatian of complexity O(t · poly(n)), after which on­ line testing whether K B F a can be performed in time O(size(a) · logn) for every a E QLn.

The proof of this result, as well as all other results reported on in this paper, will appear in the long version of the paper. We remark that the size of the knowledge base K B in Theorem 3.1 plays a role only in affecting the parameter t. Once the preprocessing is done, the knowledge base can be ignored, and the complexity of computing entailment of a query is linear in the size of the query and in log n.

Notice that, assuming the size of a query is negligible relative to the size of K B , this result shows that in the abovementioned case we are able to get on-line reasoning which is much more efficient than what can be achieved without appropriate off-line computations.

4 Efficient On-Line Reasoning

In the previous section we showed that off-line prepro­ cessing can be very effective for query languages that have an efficient basis. One wonders, however, whether this family contains any natural and/or useful query lan­ guages that can be used in practice. We now present such a query language. Recall that a CNF formula is a con­ junction of clauses each of which contains a disjunction of literals. (A literal is a primitive proposition or the negation of one.) A k-CNF formula is a CNF formula where each clause contains no more than k literals. It is not hard to show:

Proposition 4.1: For every k > 0, the k-CNF query language has an efficient basis.

Recall that every formula of propositional logic is equiv­ alent to a CNF formula. In particular, every formula is equivalent to a k-CNF formula for a sufficiently large k . Moreover, formulas that serve as queries to a knowledge base are likely to be expressible as k-CNF formulas for a rather small k. The language k-CNF is thus a fairly expressive query language in general, for which off-line preprocessing is a useful procedure.

We remark that Proposition 4.1 can be extended some­ what beyond the purely propositional case. In partic­ ular, it applies to universal formulas of the predicate calculus that have the form V x1, ... , Xn <p(x1, ... , Xn), where <p may contain function symbols and relations, but is syntactically of the form of a k-CNF formula. (Here we allow as literals not only primitive propositions, but any term of the predicate calculus.) The result and the proof are the same as in the propositional case. The key point remains having a polynomial basis.

We now consider a concrete class of knowledge bases for which the preprocessing stage for a basis for k­ CNF described above can be performed using feasible resources, and can yield considerable amortized savings in the on-line computations. Consider the case in which the knowledge base K B consists of a formula in disjunc­ tive normal form (DNF). In this case we can show:

Proposition 4.2: Testing whether a k-CNF formula <p is entailed by a DN F knowledge base K B is linear in I~PI·IKBI.

Notice that considering very large knowledge bases and the need for close to real-time response during the on-line activity, the above proposition points to the fact that the on-line reasoning in this case might still be rather inefficient. However, Theorem 3.1 guarantees that with appropriate off-line processing (before any query arrives) testing whether a k-CNF formula <pis entailed by a DNF knowledge-base is linear in I'PI · log(n). This is signifi­ cantly better than what can be achieved without off-line processing.

The results presented so far illustrate the fact that off-line reasoning can greatly improve the on-line per­ formance of useful AI applications involving knowledge bases. However, a designer that decides to use such off­ line reasoning must be careful. A possible drawback of such reasoning might appear when we consider knowl­ edge bases that need to be updated frequently. In such cases the contribution of off-line processing depends on the amount of updates and on the cost of updating the preprocessing performed earlier. Suppose that we have two separate knowledge bases /{ B1 and /{ B2 that use the same language, that the query language for both of them is k-CNF, and that appropriate off-line reasoning was performed for each knowledge base separately. If we want to combine these knowledge bases, there is no general way for combining the respective off-line data on which much effort was spent. The designer will have to investigate whether it is worthwhile to compute all the off-line queries again, or whether in the specific case it is relatively easy to combine the off-line results. We now show a particular form of systems where the above problem can be handled efficiently.

One motivation for discussing knowledge bases that consist of propositions and not of specific models is the need to represent uncertainty (this issue is thoroughly discussed in [Lev89]). Therefore, it is often reasonable to consider knowledge bases in contexts where updates increase the degree of uncertainty in the knowledge base. For example, a knowledge base might contain a hypothe­ sis about the relationships between x1 , ... , Xn, and there might be another knowledge base that represents another alternative for these relationships. Combining these al­ ternatives corresponds to taking a disjunction between propositional formulas. In such cases the appropriate off-line computations can be easily combined. If two sci­ entists worked on different knowledge bases (hypotheses) using off-line computations, and would like to combine their hypotheses (to see what is entailed if it might be the case that only one of the hypotheses is true), then they can combine their off-line computations easily in order to answer the on-line queries efficiently. Formally, this can be formulated as follows:

Proposition 4.3: Let /{ B1 and I< B2 be knowledge bases, let Q L be a query language, and let Q L' C Q L be an efficient basis for QL. Finally, let n satisfy (K B1 V I< B2) C Ln. Then computing the relevant off-line data for QL with respect to (I< B1 V /{ B2 ) given the data with respect to I< B1 and the data with respect to J{ B2 can be done in time linear in IQL~I·

5 Social Laws as Off-line Design

The notion of artificial social systems has been suggested as a paradigm for the design of shared multi-agent envi­ ronments. Essentially, when a number of loosely-coupled agents are to function in a shared environment, care must be taken to ensure that the agents do not interfere with one another. Conflicts should be resolved, or better yet to be avoided whenever possible. As suggested in [MT90] and [MT91], an effective way for agents to usefully co­ exist in a shared environment is by having them obey certain general rules, and allowing them to act indepen­ dently in the context of these rules. We think of these rules as conventions or a social law.

The design of a social law can be thought of as an in­ stance of off-line preprocessing whose role is to improve the agents' ability to better attain their goals on-line. For example, we now consider the case in which agents are modelled by finite state automata, each able to per­ form a certain set of actions.

A system of dependent automata (DA) is a tuple (N,{M;};EN,T) where N = {l, ... ,n} is a set of n agents where each agent i is represented by a non­ deterministic finite-state machine M;, and T is a state transition function for the system. Each M; may be in one of a finite number of different (physical) local states from a set S; (we assume that the S; 's are disjoint). A tuple of states ( s1, ... , Sn), where s; E S; for all i , is called a configuration of the system. We denote the set of system configurations by C. We assume that at any point in time the system is in a particular configuration. At every step, agent i performs an action taken from a set A of possible actions (notice that the agent can still choose which action it will perform in a given state, since this is not necessarily determined by its state). The set of possible actions an agent can take is in general a func­ tion of the local state the agent is in. A tuple of actions ( a1 , ... , an) consisting of the actions the different agents perform at a given point (where agent i is assumed to ex­ ecute a;) constitutes the agents' joint action there. The next state of every agent is a function of the system's current configuration and the joint action performed by the agents. Formally this is captured by the transition function T: C x An --+C. At any given point, a goal for an agent is identified with one of its states. We assume that an agent can perform computations to plan how to attain its goal, and to determine what actions to take at any given point .

In such a model, the success of one agent's actions may depend in a crucial way on the actions the other agents take. Many of the issues that arise in complex multi-agent systems can already be represented in DA systems.

An agent's plan that guarantees the attainment of a particular goal in a DA system amounts to a strategy by which, regardless of what the other agents do, our agent will attain its goal. Computing such plans can be rather complex. Moreover, a plan that needs to be able to respond to any possible behavior by the other agents may be very inefficient in the number of steps it takes. Indeed, such a plan may often fail to exist! A DA system is said to be social if it is computationally feasible for an agent to devise, on-line, efficient plans that guarantee to attain any of its possible goals. From the point of view of artificial social systems, a number of computational questions are natural at this stage. These computational problems relate to finding a set of restrictions (called the social law) on the actions performed by different agents at different states of the original DA. These restrictions will be determined off-line before the initiation of ac­ tivity and will induce a system where agents are able to (efficiently) achieve their goals during the on-line ac­ tivity. For example, given a DA system S we may be interested in restricting the agents' actions by a social law I: to yield a system S'E so that either:

1. in s'E every agent has a plan to achieve each of its goals;
2. in s'E every agent has an efficient plan to achieve each of its goals;
3. the problem of computing plans in S'E is tractable; or
4. the system s'E is social.

Various assumptions about the structure of the DA system, for example regarding the number of local states agents have, or the number of actions an agent can per­ form in every state, may affect the abovementioned com­ putational problems. These and similar problems will apply to more complex types of systems as well. We now turn to study a particular problem in the context of DA systems. Let us call a plan simple if it consists of a short sequence of actions, where by short we mean that its length is at most polynomial (in the size of the DA system) . 1 We say that a social law I: for aDA system S is enabling if in the system s'E resulting from the appli­ cation of the social law I: in S, every agent has a simple plan for attaining each of its goals from each of its local states. We can now show:

1 Our results hold also when we assume that a simple plan is a tree of polynomial size where the nodes correspond to tests on the current state and the edges correspond to appropriate actions.

Proposition 5.1: Let n ?: 2 be a constant. Given a DA system S with n agents, the problem of finding an enabling social law for such a system, if one exists, is NP-complete.

Notice that although the number of agents is constant in Proposition 5.1, the size of the system (or, rather its representation) may vary. It depends on the number of local states the agents can be in, the number of ac­ tions they can perform, and on the number of possible transitions in the system. These parameters may vary considerably even in the case of just two agents.

Proposition 5.1 answers a question of the second type in the above list. While NP-completeness results are usu­ ally interpreted as evidence that a problem is hard, we interpret this result in a slightly different manner here. Since social laws will be found off-line before the initia­ tion of activity, we can spend much time in determining a social law. The proof of the proposition shows that the design process of an enabling social law can be sup­ ported by an efficient verification of whether we found an enabling social law or where we failed. Thus, in generic cases, it should be feasible to (off-line) construct an en­ abling social law incrementally.

A further restriction can provide us with answers to questions of the third and fourth type in the above list. Given a DA system, we say that a pair (s, t) of local states for an agent are neighbors if there exist two con­ figurations c,, Ct of the system and a joint action a such that (i) inc, the agent is in states and in Ct it is in t, and (ii) performing a in c. yields the state Ct. Given a DA system S, a social law I: for this system is called deter­ minizing if for every pair of neighbor states of the agent , in the resulting system s'E the agent has a simple plan for getting from s to t. Specifically, it has a sequence consisting of a constant number of actions which, when started ins is guaranteed to reach t. Notice that a deter­ minizing social law is necessarily an enabling social law, but not vice-versa. A determinizing social law solves the third computational problem stated above, and since en­ abling social laws solve the second, we obtain that a de­ terminizing social law yields a social system (and hence solves the fourth computational problem). We have:

Proposition 5.2: Let n ?: 2 be a constant. Given a DA system S with n agents, the problem of finding a determinizing social law for such a system, if one exists, is NP-complete.

As before, the fact the problem is NP-complete can be interpreted here as relatively good news. Given a can­ didate for a determinizing social law we will be able to efficiently verify whether it is appropriate or where it fails . Thus, in generic cases, it should be feasible to (off­ line) construct a determinizing social law incrementally. We remark that if the local states of the agents have a sufficiently simple form, then the problem of finding a de­ terminizing social law for a system of a constant number of agents can be solved in polynomial time (see [Ten91]).

A particular case study of the design of a social law is presented in [ST92]. There, Shoham and Tennenholtz investigate traffic laws for mobile robots that operate on an n by n grid. They present nontrivial laws that allow the robots to carry out respective tasks without collision at a rate that is within a constant of the rate it would take each of them if it had the whole space to itself. This is an example of how appropriate off-line design of social laws guarantees very effective on-line behavior.

6 Conclusions

This paper suggests the use of off-line processing before the initiation of a system in order to improve the on­ line behavior of artificial systems. We investigated this approach in the framework of entailment of queries by knowledge bases, and in the context of multi-agent ac­ tivity. We presented the notion of an efficient basis for a query language, and showed that off-line preprocessing can be very effective for query languages that have an ef­ ficient basis. We also showed that the language of k-CNF formulas, a useful and rather expressive language, has an efficient basis. The second context in which off-line pro­ cessing is very helpful is multi-agent activity. Finding an efficient and computationally tractable social law is the appropriate form of off-line processing in this case. The social law is a set of restrictions on agents' activities that enables agents to tend to work individually but in a mutually compatible manner. This social law needs to be designed carefully and the design process might be a relatively long trial and error procedure, but when we arrive at the appropriate social law then the on-line activity becomes effective and efficient . We formulated the approach in the framework of dependent automata. In that framework, testing whether a given social law is appropriate or where it fails can be efficiently computed. This can greatly speed up the process of generating an appropriate social law.