TIM

TIM: An automatic planning domain analysis tool

TIM is a domain-independent automatic domain analysis tool. Originally TIM was developed to automatically extract type information from a planning domain. This analysis typically constructs a more informative type structure than the human domain engineer supplies and this can, in turn, aid the domain engineer in correcting and extending a domain.

The original analyses carried out by TIM are based on identification of simple finite-state machines which characterise the state-transitions possible for objects of different types within a planning domain. This characterisation of object behaviours allows TIM to infer invariant properties of the objects. There are two important roles for these invariants: they allow a domain engineer to confirm that the domain encodes appropriate behaviours and they can be exploited by a planner to improve performance. We have demonstrated the potential for some of the invariants constructed by TIM in our planning system, STAN, although this by no means exhausts their possibilities.

More recent work on TIM has been focussed on a more powerful role: the identification of generic type structures within domains. These are collections of types which exhibit certain characteristic behaviours. Examples include mobile objects which are characterised by the ability to move around between locations and portable objects which are carried between locations. TIM is able to automatically identify (in a syntax-independent manner) these generic types. This allows us to extract key sub-problems within a planning problem which might be best tackled by specialised solvers, such as path-planning for mobiles.

Current investigations are looking at identification of resource types and construction types (including blocks in the classic blocks-world domain). We have already demonstrated a simple mechanism for abstracting certain kinds of path-planning for separate solution by a specialist solver. We expect to extend this idea to integrate more powerful sub-problem solvers.

One of our recent enterprises has been the construction of an API for TIM to give access to the information it can extract from a domain. This is now available in a first release. This is still at a preliminary stage: it currently offers C and C++ API functions accessing type information and some logical domain structure information. The API is supported through a shared library that can be built for use on Linux. We are working on supporting a Java API and to make the library available in a Sun OS version and, possibly, a MS-Windows version (depending on demand).