Automatic Synthesis and Use of Generic Types in Planning

Derek Long and Maria Fox

Domain-independent planning concentrates on the general algorithmic issues raised in exploring a search space generated in finding sequences of state-transition functions between an initial state and a goal state. It is acknowledged that domain-dependent planning, in which features of specific domains are exploited in this search, offers opportunities for more efficient planning, but at the price of greater effort in the domain-encoding. The work presented in this paper is concerned with giving a domain-independent planner access to certain kinds of domain-specific heuristics without the need for additional domain encoding effort. This is achieved by automatically identifying generic types from strips planning domain descriptions. Generic types are higher order types allowing the categorisation of domains (and components of domains) into domain classes, including the commonly occurring transportation domain class. We show how the generic type structure of domains can begin to be exploited to increase planner efficiency. An interesting property of the work described here is that domain components which would not easily be recognised, by the human, as transportation problems can turn out to have an underlying transportation character which can be exploited by the application of standard transportation domain heuristics. The analyses described here are completely planner-independent and contribute to an increasing collection of pre-planning analysis tools which help to increase performance of planners by decomposing and understanding the structures of planning problems before planners are applied.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.