1Planning with Analogical and Hybrid Representations*

This report illustrates how new methods and techniques from the area of knowledge representation and reasoning can be adopted and exploited in planning to produce new, more efficient domain-description languages. Planning domain description formalisms should be expressive and customisable, and yet be able to produce domain encodings that allow the planner to concentrate all of the computational effort on the search for a solution, rather than on calculating the trivia of the problem. This paper argues that most of the modern, ‘sentential ’ domain-modelling languages do not meet the latter requirement, and, when applied to realistically complex domains, produce encodings that are subject to the inefficiencies of the ramification problem. The solution proposed here consists of adopting non-sentential domain representations in planning. In particular, recent experimental evidence (Garagnani and Ding 2003) indicates that the adoption of analogical descriptions can lead to significant planning speed-ups. However, although more efficient, when compared to sentential languages these representations tend to be less expressive and less universally applicable. The main aim of this paper is to provide a theoretical basis for hybrid planning, in which analogical and sentential domain representations can be seamlessly integrated and used interchangeably, thereby overcoming the limitations and exploiting the advantages of both paradigms. The first part of the document clarifies the nature of analogical representations and illustrates how they can avoid the frame and the ramification problems, which afflict all sentential languages. The central section presents an expressive analogical representation (based on the structure of “setGraph”) and a formal framework for hybrid planning built on it, while the last section discusses related work, limitations and future directions. 1 Sentential vs. Analogica