architecture. Tim has been implemented in C++ and executables and examples of output are available at our web site (see Appendix A) and in Online Appendix 1.

TIM takes a domain description in which no type information need be supplied and infers a rich type structure from the functional relationships between objects in the domain.  If type information is supplied TIM can exploit it as the foundation of the type structure and will often infer an enriched type structure on this basis. State invariants can be extracted from the way in which the inferred types are partitioned. The consequence is that the domain designer is relieved of a considerable overhead in the description of the domain. Whilst it is easy to hand-code both types and state invariants for simple domains containing few objects and relations, it becomes progressively more difficult to ensure cross-consistency of handcoded invariants as domains become increasingly complex. Similarly, the exploitable type structure of a domain may be much richer than can easily be provided by hand. We have observed that TIM often infers unexpected type partitions that increase the discrimination of the type structure and provide corresponding benefits to stan's performance. We therefore see TIM as a domain engineering tool, helping to shift the burden of domain design from the human to the automatic system.

The usefulness of both types and state invariants is well-documented. Types have been provided by hand since it was first observed that they reduce the number of operator instantiations that have to be considered in the traversal of a planner's search space. The elimination of meaningless instantiations is particularly helpful in a system such as Graphplan, in which the structure to be traversed is explicitly constructed prior to search. We believe that the benefits to be obtained from type inference in planning are similar to those obtained in programing language design: type inference is more powerful than type checking and can assist in the identification of semantic errors in the specification of the relational structure of the domain. Indeed, we have found TIM to be a useful domain debugging tool, allowing us to identify flaws in some published benchmark domains. We also used TIM to reveal the underlying structure of the Mystery domain, a disguised transportation problem domain, used in the planning competition. The Mystery domain is described in Appendix C.2.

The use of domain knowledge can significantly improve the performance of planners, as shown by a number of researchers. Gerevini and Schubert (1996a, 1996b) have considered the automatic inference of some state constraints and demonstrated that a significant empirical advantage can be obtained from their use. Kautz and Selman (1998) have handcoded invariants and provided them as part of the domain description used by Blackbox. They demonstrate the performance advantages obtained and acknowledge theimportance of inferring such invariants automatically. McCluskey and Porteous (1997) have also demonstrated the important role that hand-coded state invariants can play in domain compilation for efficient planning. Earlier work by Kelleher and Cohn (1992) and Morris and Feldman
(1989) explores the automatic generation of some restricted invariant forms. We discuss these, and other, related approaches in section 5.

In this paper we will describe the type inference process employed by TIM and explain how four different forms of state invariant can be extracted from the inferred type structure.

We will argue that TIM is correct since it never infers sentences that are not state invariants.

We will then provide experimental results demonstrating the performance advantages that can be obtained by the use of types.