

![0_image_0.png](0_image_0.png)

the number of characters in the specification file. This graph was constructed by running TIM ON All of the STRIPS Mystery domain problems in the PDDL release. The increasing sizes of the problem specifications reflect increases in any and all of the various categories of objects in the domain and corresponding facts to describe their initial states.

Figure 5 shows the effect on TIM's performance as the number of operator schemas increases. This graph was constructed using an artificial domain in which each new operator causes two new state transitions described by two new literals. Thus, both number of operators and number of properties is increasing whilst the number of objects stays constant.

The domain is described in detail in Appendix E. The graph indicates the linear growth of cost of analysis.

The final dimension for evaluating TIM is the effect of exploitation of its output by a planner. Gerevini and Schubert (1998) and Kautz and Selman (1998) provide convincing evidence supporting the powerful role of state invariants in enhancing the performance of SAT-based planning. In Figure 6 we demonstrate the power of inferred types by showing the advantage that sTAN with TIM obtains over sTAN without TIM on untyped Rocket domain problems. Figure 6 shows the effect on performance of increasing the number of packages to be transported. The time taken by sTAN with TIM grows linearly, whilst sTAN without TIM follows a c u b i c c u r v e . If there are p packages in a problem instance then STAN with TIM
constructs 4(p 1) operatorinstances while stan without tim constructs (p 3) 2 (p 5) 2 p instances. This demonstrates that type information is the most significant factor in the advantage depicted in the graph. Figure 7 demonstrates that a similar improvement is obtained in the Logistics domain. In this graph a series of sub-problems were considered in