Planning from rich ontologies through translation betweeen representations
Fiona McNeill, Alan Bundy, Chris Walton · Edinburgh Research Explorer (University of Edinburgh) · 2005
The richness and expressivity of standard ontology representations and the limitations on expressivity required by modern planners have resulted in a situation where it is hard for an agent both to have a rich ontology and be capable of efficient planning. We discuss how translation between different kinds of representation can allow an agent to have different versions of the same ontology, so that it can simultaneously meet different demands of expressivity. We introduce our ontology refinement system (ORS), in which these ideas are implemented. Using rich ontologies for planning There is currently a disparity between the richness of ontological representation used in multi-agent systems, and ontologies used in Semantic Web like environments, and the richness of ontological representation used in planning. This disparity comes about due to the different requirements of each domain. In a multi-agent system and environments such as the Semantic Web, rich, expressive ontologies are desirable. Such ontologies facilitate the encoding of detailed domain information: information about infinite domains, meta-information about ontological objects, complex class hierarchies which allow for slot information in classes, use of the open world assumption, and so on. Some common ontological representations for multi-agent systems, such as Knowledge Interchange Format (KIF) [3], are full first-order, and are thus extremely expressive. Other common ontological representations: for example, description logic based ontologies, such as RDF and OWL, are less expressive than full first-order logic, owing to the tractability problems associated with inference in full first-order logic, but, nevertheless, retain a high level of expressivity. In popular planning representations, much of this expressivity is removed. Languages such as PDDL [2], resemble first-order languages; however, this is an illusion. Most planners that take domain information from PDDL files are propositional and thus, though Copyright c 2005, American Association for Artificial Intelligence (www.aaai.org). All rights reserved. PDDL provides a first-order window on to the propositional space, anything that is expressed in PDDL must be translatable into propositional logic. This places restrictions on what can be expressed; there are some ontological objects that are expressible in a firstorder representation but not in a less expressive representation: for example, quantification over infinite domains. Additionally, the closed world assumption is normally used in planning. One might argue that this disparity comes about partly due to the separation of the planning community and the ontology community: state-of-the-art planners are usually designed and assessed on how well they perform purely with respect to planning considerations; there is much less emphasis on how to balance good plan formation performance with consideration of other issues, such as dealing with richer ontologies. However, there is a more fundamental issue underlying this disparity. Automated planning is very difficult, largely because the search problems involved in finding even short plans are vast. The only feasible way to solve these problems is to reduce the search space. Thus the most important aspect of planning representations is that they are not difficult to search through; this inevitably leads to loss of expressivity. There are two approaches to this problem. One approach is to attempt to balance the demands of an expressive ontological representation with those of a tractable planning representation. The resulting representation will be less expressive than a standard ontological representation and less efficient for producing plans than a standard planning representation; however, the advantage of combining both facets in a single representation may be thought to outweigh these problems. However, we believe that the best solution to the problem is provided by an alternative approach: allowing ontological knowledge to be represented in different ways, depending on the current required functionality, and translating between the different representations as necessary. Inevitably, information is lost through translation from a more expressive to a less expressive representation. However, if the most expressive representation is retained after it is translated to a less expressive representation, then the agent still has access to its complete ontology as well as to the less expressive representation that can be used, for example, for planning. We believe that the demands of a planning representation are incompatible with the demands of a standard ontological representation. The ability to form plans quickly and efficiently is vital to agents that are attempting to plan within multi-agent systems, but equally, the ability to represent complex information within their ontology is important. We believe that an attempt to combine the two needs in a single representation requires too great a loss to both domains, and therefore our approach is to develop translation processes between different kinds of ontological representations. It should be noted that by ontology, we mean both the representation language of the domain and the knowledge base expressed in that language. Thus, in our terms, a PDDL ontology would consist of a domain file and one or more problem files; a KIF ontology would define the vocabulary but also contain the facts expressed in that vocabulary. Therefore, an ontology can be altered either by changing the representational language or by changing the facts expressed in that language (as occurs during plan execution). In this paper, we describe the translation process that we have implemented, and explain its role in ORS. We describe the context that ORS is designed to work in: that of a multi-agent, service-based architecture, and mention how this context affects the kind of translation that is necessary in ORS. We discuss how our evaluation of ORS demonstrates that this translation process is successful, and show how, as a result, ORS can be used to dynamically refine ontologies in a planning environment. Translating from KIF to PDDL Currently, we have implemented one such translation process: translating from KIF ontologies to a PDDL representation. In translating from KIF, we have already tackled some of the most severe problems inherent in such an approach: KIF is full first-order, and thus the loss of expressivity in our existing translation process is at least as severe as the loss of expressivity in translating any ontological representation to PDDL, although our system does not currently deal with full KIF but only with a subset of it; thus not all these issues have been confronted. Certainly, there would be different implementation issues when translating from a language such as OWL to PDDL, but the theoretical problems surrounding loss of expressivity would be less. Full details of this translation process can be found in [7]; in this section we briefly discuss some of the chief issues involved in this process, which is illustrated in Figure 1. We have implemented this translation process as part of our ontology refinement system (ORS), which is discussed in the following section. The translation process is important because the system deals with Planning Agent