3.1.4 Complexity of Plan Rewriting

The complexity of plan rewriting in PbR originates from two sources: matching the rule antecedent against the plan, and computing the embeddings of the replacement plan. In order to analyze the complexity of matching plan-rewriting rules, we introduce the following database-theoretic definitions of complexity [2]:

**Data Complexity:** complexity of evaluating a *fixed
query* for variable database inputs.

**Expression Complexity:** complexity of evaluating, on a
*fixed database instance*, the queries specifiable in a given
query language.

Data complexity measures the complexity with respect to the size of the database. Expression complexity measures the complexity with respect to the size of the queries (taken from a given language). In our case, the database is the steps and links of the plan and the queries are the antecedents of the plan-rewriting rules.

Formally, the language of the rule antecedents described in
Section 3.1.1 is conjunctive queries with interpreted
predicates. The worst-case combined data and expression complexity of
conjunctive queries is exponential [2]. That is, if
the size of the query (rule antecedent) and the size of the database
(plan) grow simultaneously, there is little hope of matching
efficiently.
Fortunately, relationally-complete languages have a *data*
complexity contained in Logarithmic Space, which is, in turn,
contained in Polynomial Time [2]. Thus our conjunctive
query language has at most this complexity. This is a very encouraging
result that shows that the cost of evaluating a fixed query grows very
slowly as the database size increases.
For PbR this means that matching the antecedent of the rules is not
strongly affected by the size of the plans. Moreover, in our
experience useful rule antecedents are not very large and contain many
constant labels (at least, the node and edge predicate names) that
help to reduce the size of the intermediate results and improve the
efficiency of matching.
This result also indicates that we could extend the language of the
antecedent to be relationally complete without affecting significantly
the performance of the system.^{11} Another possible extension is to use datalog with stratified negation,
which also has polynomial time data complexity. Graph-theoretic
properties of our plans could be easily described in datalog. For
example, the `possibly-adjacent` interpreted predicate of
Figure 7 could be described declaratively as a datalog
program instead of a piece of code.
In summary, rule match for moderately sized rules, even for quite
expressive languages and large plans, remains tractable and can be
made efficient using production match [32] and query
optimization techniques [74].

The second source of complexity is computing the embeddings of the replacement plan given in the consequent of a plan-rewriting rule. By the definition of full-specification rules, the embedding is completely specified in the rule itself. Thus, it suffices simply to remove the undesired subplan and directly add the replacement subplan. This is linear in the size of the consequent.

For partial-specification rules, computing all the embeddings of the
replacement subplan can be exponential in the size of the plan in the
worst case. However, this occurs only in pathological cases. For
example, consider the plan in Figure 15(a) in which we are
going to compute the embeddings of step `x` into the remainder of
the plan in order to satisfy the open precondition *g0*. Step `x` has no preconditions and has two effects `b` and `g0`. Each step in the plan has proposition `b` as an
effect. Therefore, the new step `x` conflicts with every step in
the plan (`1` to `n`) and has to be ordered with respect to
these steps. Unfortunately, there are an exponential number of
orderings. In effect, the orderings imposed by adding the step `x`
correspond to *all* the partitions of the set of steps (`1` to
`n`) into two sets: one ordered before `x` and one
after. Figure 15(b) shows one of the possible
orderings. If the subplan we were embedding contained several steps
that contained similar conflicts the problem would be compounded.
Even deciding if a single embedding exists is NP-hard. For example, if
we add two additional effects `a` and `g1` to
operator `x`, there is no valid embedding. In the worst case
(solving first the flaws induced by the conflicts on proposition `b`) we have to explore an exponential number of positions for step
`x` in the plan, all of which end up in failure.
Nevertheless, given the quasi-decomposability of useful planning
domains we expect the number of conflicts to be relatively small. Also
most of the useful rewriting rules specify replacement subplans that
are small compared with the plan they are embedding into.
Our experience indicates that plan rewriting with
partial-specification rules can be performed efficiently as shown by
the results of Section 4.