
## 3.3  Effects Of Tim On The Properties Of The Planner

TIM is itself sound, so no planner that uses TIM is in danger of losing soundness as a result.

TIM is certainly not complete for all domain axioms because there are invariant properties of other kinds that cannot be extracted by the current version. For example, Kautz and Selman
(1998) identify optimality conditions and simplifying assumptions amongst the different kinds of axioms that might be inferred from a domain. An optimality condition in the Logistics domain might be: a package should not be returned to a location it has been removed from. A simplifying assumption in the same domain might be: once a truck is loaded it should immediately move (assuming all necessary loads can be done in parallel). These constraints require a deeper analysis of the domain than is currently performed by TIM, but we intend to characterise them and infer them in our future work.

We cannot guarantee that the type structure inferred by TIM is always fully discriminting, although we do guarantee that it is not over-discriminating. However, failure on TIM's part to infer all of the structure that is there to be inferred does not impact on the completeness of a planner using TIM because, in these cases, TIM will return an unstructured domain and the planner can therefore default to reasoning with the unstructured domain w hen necessary.

## 4. Experimental Results

An examination of TIM's performance can be carried out on several dimensions. We consider three specific dimensions here: the viability of the analysis on typical benchmark domains; the scalability of the analysis and the utility of performing the analysis prior to planning. Its general performance on standard benchmark problems provides an indication of the scale of the overhead involved in using TIM as a preprocessing tool. All experiments were performed under Linux on a 300MHz PC with 128 Mb of RAM. Figure 3 shows that, even on large problem instances, the overhead is entirely acceptable. All of the Mystery problems listed in this table are very large (involving initial states containing hundreds of facts) and could not be solved by stan, ipp (Koehler, Nebel, & Dimopoulos, 1997) or Blackbox (Kautz &
Selman, 1998) in the AIPS-98 competition. The nature of the Mystery domain is described in Appendix C. This emphasises the relative costs of the preprocessing and planning efforts.

The selection of problems used to construct table 3 is justified as follows. In the Blocks world we have used a representative example from each of three encodings supplied in the PDDL release. These are: the simple encoding (prob12), the ATT encoding (prob18) and the SNLP encoding (prob23). The Hanoi set contains a collection of reasonably sized problems.

A representative group of relatively large Mystery instances was chosen from the pddl release. The two Tyre world instances are the only two strips instances available in the release. The three Logistics problems are the three largest for the simple strips encoding included in the pddl release.

The second dimension is scalability of the analysis. An analytic examination of the agorithm can determine an upper bound on performance that is polynomial in all of the key domain and problem components, including number of operator schemas, number of literals in operators, numbers of objects and facts in the initial state and the number and arities of predicates in the language. Figure 4 shows that the performance of tim is roughly quadratic in the size of the problem specification. In the graph, size is crudely equated with