Integrating Ontologies and Planning for Cognitive Systems Gregor Behnke1 , Pascal Bercher1 , Susanne Biundo1 , Birte Glimm1 , Denis Ponomaryov2 , and Marvin Schiller1 1 Institute of Artificial Intelligence, Ulm University, Germany 2 A.P. Ershov Institute of Informatics Systems, Novosibirsk, Russia Abstract. We present an approach for integrating ontological reasoning and plan- ning within cognitive systems. Patterns and mechanisms that suitably link plan- ning domains and interrelated knowledge in an ontology are devised. In partic- ular, this enables the use of (standard) ontology reasoning for extending a (hi- erarchical) planning domain. Furthermore, explanations of plans generated by a cognitive system benefit from additional explanations relying on background knowledge in the ontology and inference. An application of this approach in the domain of fitness training is presented. 1 Introduction Cognitive systems aim to perform complex tasks by imitating the cognitive capabil- ities of human problem-solvers. This is typically achieved by combining specialised components, each of which is suited to fulfil a specific function within that system, such as planning, reasoning, and interacting with the user or the environment. Each component requires extensive knowledge of the domain at hand. Traditionally, several representations of knowledge are used by the different components, each well suited for their respective components. As a result, domain knowledge is distributed across various parts of such a system, often in different formalisms. Thus, redundancy and maintaining consistency pose a challenge. In this paper, we present an approach for using an ontology as the central source of domain knowledge for a cognitive system. The main issue we address is how the planning domain (representing procedural knowledge) and other (ontological) domain knowledge can be suitably combined. The approach uses the ontology and ontological reasoning to automatically generate knowledge models for different components of a cognitive system, such as the planning component or an explanation facility. In par- ticular, the planning domain is automatically extended using ontological background knowledge. The same ontology is used by an explanation mechanism providing coher- ent textual explanations for the generated plans and associated background knowledge to the user. The planning component uses Hierarchical Task Network (HTN) planning [7, 9], which is well-suited for human-oriented planning. This paper is organised as follows. We commence with the relevant preliminar- ies in Section 2. A general outline of the approach and its foundations is presented in Section 3, illustrated by a case study using a real-world fitness training scenario. In Section 4, the explanation mechanism is described by using accompanying examples from the case study. Related work is discussed in Section 5 and Section 6 concludes the paper. 2 Preliminaries In the paper, we refer to the Description Logic ALC [24], which, as we assume, is fa- miliar to the reader. We briefly introduce the relevant concepts of HTN planning that help to understand the context of our work. HTN planning [7, 9] is a discipline of au- tomated planning where tasks are hierarchically organised; tasks are either “primitive” (they can be executed directly) or abstract (also called complex or compound in the literature), i.e., they must be decomposed into sets of subtasks which can in turn be ab- stract or primitive. Plans are represented by so-called task networks, which are partially ordered sets of tasks. Planning is done in a top-down manner, such that abstract tasks in a task network are refined stepwise into more concrete courses of action. This approach to planning is deemed similar to human problem solving, and thus considered appropri- ate for use in cognitive systems [4]. HTN planning problems consist of an initial task network, a planning domain – a set of operators (specifying the preconditions and ef- fects of primitive actions) together with a set of decomposition methods (which specify how each abstract task can be decomposed by replacing it with a network of subtasks) – and an initial state (specifying the state of the world before the tasks in the plan are carried out). A decomposition method m is denoted as A 7→≺ B1 , ..., Bn , stipulating that the abstract task A may be decomposed into the plan containing the subtasks B1 to Bn adhering to the partial order ≺. The subscript ≺ is omitted if no order is defined on the subtasks. Applying a method m to a plan containing A refines it into a plan where A is replaced by the subtasks of m with the given order ≺. All orderings imposed on A are inherited by its subtasks Bi . A plan is a solution for a planning problem if it consists of a fully executable network of tasks. 3 Integrating Ontologies and Planning When bringing ontologies and planning together, a key challenge is to find a represen- tation that suitably links general ontological knowledge with information in the plan- ning domain. The aim is to enable both a specialised reasoner and a planner to play to their strengths in a common application domain of interest, while the consistency of the shared domain model remains ensured. The first part of our approach is to embed planning knowledge (a hierarchical planning domain) into a general ontology of the application domain. To address differences in the formalisms of planning and DL, we present suitable modelling patterns and translation mechanisms. As a second step, an off-the-shelf DL reasoner is applied to infer new knowledge about the planning domain in terms of new decomposition methods. Thanks to the integrated model, the struc- ture of decompositions in the planning domain is accessible to DL reasoning, i.e., new methods are implied using knowledge of both domains. This modelling yields a stan- dard planning domain such that an off-the-shelf planner can be used. We have applied this approach to a fitness scenario and have developed a system which creates a training plan for a user pursuing some fitness objective. Such a plan defines a training schedule, comprising training and rest days, as well as the exercises and their duration which are necessary to achieve a certain goal, e.g., to train the lower body. A similar scenario is used by Pulido et al. [21], where exercises for physiotherapy of upper-limb injuries are arranged by a planner. 3.1 Embedding Planning Methods into Ontologies In this section we describe how the knowledge contained in a hierarchical planning do- main can be represented in an ontology such that its contents are described declaratively and thus become amenable to logical reasoning. First, a link between the planning domain and corresponding/additional information in the ontology is defined by a common vocabulary – there is a distinguished set of task concepts in the ontology which correspond to planning tasks. If T is a planning task, then a corresponding task concept is denoted as T. In addition to task concepts, the ontology allows for concepts to model further aspects of the application domain. Task concepts are provided with definitions/told subsumptions in the ontology which are de- termined by the set of predefined decomposition methods for the counterpart planning tasks. Based on these predefined methods, new ones are derived from the ontology, as further described in Section 3.2. A simple decomposition method A 7→ B is inter- preted as a subsumption B v A between task concepts A, B. This pattern, however, works only for such simple decomposition methods. In general, a method has the form A 7→ B1 , ..., Bn and can be viewed as an instruction that A is achieved by “executing” the tasks B1 , ..., Bn . When representing such decomposition methods in an ontology one needs to take into account that a decomposition method is a precise definition of the tasks created. It specifies the subtasks required to achieve an abstract task, but si- multaneously states that these tasks are also sufficient. Ontologies, on the other hand, are built on the open world assumption – representing a task decomposition by the tasks B1 , ..., Bn is insufficient. The ontology must also contain the explicit information that only these tasks belong to the decomposition. For this purpose we use the onlysome construct (see, e.g., Horridge et al. [13]), which is a short-hand notation for a pattern combining the existential and universal restrictions to represent collections of concepts. Definition 1 Let r be a role, I an index set, and {Ci }di∈I concepts. We F define the  onlysome restriction Cr.({Ci }i∈I ) by Cr.({Ci }i∈I ) := i∈I ∃r.Ci u ∀r. i∈I Ci . With the onlysome restriction we can give a decomposition method in a definition stating that a collection of tasks corresponds to a task concept to be decomposed. Thus, a method A 7→ B1 , ..., Bn can be expressed by using the axiom A ≡ Cincludes.(B1 , ..., Bn ). Let us now turn to our application domain of fitness training. Here, elementary train- ing exercises are represented as planning tasks whose preconditions and effects follow certain rules (e.g. muscles must be warmed up before being exercised, intense exer- cises must precede lighter ones, ...). The ontology further encompasses concepts for training exercises, equipment, workouts, training objectives, and a part of the NCICB corpus [17], describing muscles etc. Contained in the ontology are four planning-related types of concepts: exercises, workouts, workout templates, and trainings. Workouts are predefined (partially ordered) sets of exercises, modelled by a domain expert using onlysome-definitions. This implicitly defines decomposition methods for each work- out. Workouts are, e.g., defined by: Workout1 ≡ Cincludes.(FrontSquat, SumoDeadlift) This axiom postulates that Workout1 includes front squats and sumo deadlifts but noth- ing else. At a more abstract level, workout templates serve to specify groups of work- outs with similar properties. For example, there exist many similar variants of squats and deadlifts with similar training effects, which can be grouped together. For instance, consider WorkoutTemplate1: WorkoutTemplate1 ≡ Cincludes.(Squat, Deadlift) This workout template subsumes Workout1 wrt the ontology (since FrontSquat v Squat and SumoDeadlift v Deadlift). As detailed in the next subsection, these sub- sumptions are the basis for generating corresponding decomposition methods, e.g., in this case a method decomposing the task WorkoutTemplate1 into Workout1 which again is decomposed into its concrete subtasks. Finally, trainings define abstract training ob- jectives, such as improving strength or training the lower body. Here, the requirements that need to be met are formulated using onlysome restrictions. For instance, the fol- lowing axiom postulates that lower body training contains at least one and only exer- cises targeting muscles in the lower body: LowerBodyTraining ≡ Cincludes.∃engages target.(∃part of.LowerBody) The cornerstone of our approach is to establish a correspondence between subsumptions among task concepts in the ontology and corresponding decompositions in the planning domain. For two task concepts representing collections of tasks using onlysome, we require that one is subsumed by the other if and only if the tasks defined by the first serve to achieve all requirements specified by the second. In more detail, a collection C1 (representing a set of tasks) should be subsumed by a collection C2 if and only if for any task concept (requirement) from C2 , there is a task concept in C1 , which achieves it (i.e., C1 is subsumed by C2 ), and there are only those task concepts in C1 that meet some requirement from C2 . For this property to hold, we require that in onlysome restrictions Cr.({Ci }i∈I ) the role r is independent of concepts Ci , i.e., has no semantic relationship with them, as captured by the following definition. Definition 2 Let O be an ontology, r a role, and C1 , ..., Cn concepts. We call r inde- pendent of C1 , ..., Cn wrt O if, for any model I of O and any binary relation [s] on the domain of I, there is a model J of O with the same domain such that r is interpreted as [s] in J and the interpretation of Ci , 1 ≤ i ≤ n, in I and J coincides. Next, we show that the given intuition holds for the collections defined with the onlysome restriction. Theorem 1 Let O be an ontology, C1 , ..., Cm concepts satisfiable wrt O, D1 , ..., Dn concepts, and r a role independent of C1 , ..., Cm , D1 , ..., Dn wrt O. Then it holds O |= Cr.(C1 , ..., Cm ) v Cr.(D1 , ..., Dn ) if and only if (1) ∀i, 1 ≤ i ≤ m, ∃j, 1 ≤ j ≤ n, such that O |= Ci v Dj and (2) ∀j, 1 ≤ j ≤ n, ∃i, 1 ≤ i ≤ m, such that O |= Ci v Dj . Proof (Sketch). The if direction can be shown using monotonicity of existential/universal restrictions and Conditions (1) and (2). Using contraposition, we can show the only-if direction by constructing a countermodel for the subsumption. Since each Ci is satisfi- able, there are models of O with some instance ci of Ci . Using the negation of Condi- tion (1), there is further a model with an instance x of some Ci that is not an instance of any Dj . We now build a new model as the disjoint union of these models and take an arbitrary element d in the constructed model. Using independence of r, we obtain a model in which r contains hd, xi and the tuples hd, ci i. We obtain the desired contradic- tion since d is an instance of Cr.(C1 , ..., Cm ), but not an instance of ∀r.(D1 t ... t Dn ) (due to hd, xi) and, hence, of Cr.(D1 , ..., Dn ). We can proceed similarly for the case of Condition (2) not holding.  Until now, only the tasks contained in a decomposition method have been regarded, while their partial ordering was ignored. To incorporate it in the ontology, the notion of collections must be extended to partially ordered sets of concepts. Unfortunately, many DLs (also ALC) are not well suited to represent partial orders, since their expressivity is limited by the tree-model property [28], stating that non-tree structures cannot fully be axiomatized. Since our aim is to completely represent the planning domain in the ontology, we propose a syntactic encoding for this information that is opaque to DL reasoners and has no influence on the semantics. A task A following a task B is ex- pressed by replacing the concept A in onlysome expressions by At(⊥u∃after.B). The latter disjunct is trivially unsatisfiable and the given expression is semantically equiv- alent to just A. This makes order opaque to any reasoner. Preconditions and effects of primitive tasks are modelled using auxiliary roles, making them accessible for logical reasoning, too. 3.2 Extending Planning Domains by DL Inference Embedding the planning domain into the ontology enables us to infer new decomposi- tion methods using off-the-shelf DL reasoners. More precisely, subsumption relations between task concepts inferred from an ontology O result in decomposition methods being added to the planning domain. Suppose there are task concepts A and B such that O |= B v A and there is no other task concept C such that O |= {B v C, C v A}. Then, a decomposition method A 7→ B is created in analogy to the way such methods are encoded in the ontology. This simple scheme provides only for methods decom- posing into a single subtask. Further, we interpret onlysome-definitions provided by the ontology as told decompositions that provide collections of tasks. Besides these two simple cases, we are also interested in knowing whether an abstract task A can be achieved by combining some task concepts B1 , ..., Bn into a new decomposition method A 7→ B1 , ..., Bn . If so, some concept expression E describing this combination should be subsumed by A. In keeping with the principle of matching task collections described by Theorem 1, we consider combining concepts using onlysome restrictions. The concepts B1 , ..., Bn describe requirements, which another concept A might fulfil. If for some tasks A, B1 , ..., Bn it holds O |= Cr.(B1 , ..., Bn ) v A, then a decompo- sition method of A into the collection B1 , ..., Bn is created. Let us once again consider our use-case to discuss an example. Consider the definition of lower body training in- troduced in the previous subsection: LowerBodyTraining ≡ Cincludes.∃engages target.(∃part of.LowerBody) Since our ontology respects the requirement that the role includes is independent of concepts occurring in onlysome expressions, Theorem 1 applies and we know that any workout solely comprised of lower body exercises is subsumed by LowerBodyTraining. This results in decomposition methods for LowerBodyTraining into every possible workout for the lower body. Furthermore, consider the following definition of full body training: FullBodyTraining ≡ Cincludes.( ∃engages target.(∃part of.LowerBody), ∃engages target.(∃part of.UpperBody)) Using reasoning, one can now establish whether combinations of different workouts achieve such a training objective, such that a corresponding decomposition method is automatically introduced into the planning domain. For instance, we can infer that a workout solely training the lower body and a workout solely training the upper body in combination constitute this training. Hence a decomposition method for a full body training into these two workouts is added to the planning domain. The following theo- rem clarifies the relationship between the obtained decomposition methods and entailed concept inclusions. Theorem 2 Let A be an abstract task, which can be refined into some plan P by ap- plying decomposition methods created from the ontology O. Let the plan P contain the tasks B1 , ..., Bn , n ≥ 1. Then there is a concept P such that O |= P v A, B1 , ..., Bn occur in P , and P is either of the form: 1. a task concept from O, or 2. an expression Cr.(F1 , ..., Fm ) with each Fi a concept of the form 1 or 2. Proof. The claim is proved by induction on the number m of (decomposition) steps made to obtain P using O. In the induction base, for m = 0, A is the required con- cept. For m > 0, let P 0 = {C1 , ..., Ck } be a set of tasks obtained in m − 1 decom- position steps and let P 0 be a concept satisfying the claim for P 0 . Let P be obtained from P 0 by decomposing some task Ci , for i ∈ {1..., k}. Assume that a decompo- sition method for Ci was created from the concept inclusion D v Ci entailed by O. Then D is one of the task concepts B1 , ..., Bn , we have O |= PC0 i /D v P 0 , hence, O |= PC0 i /D v A and thus, PC0 i /D is the required concept (denoting P 0 with every occurrence of Ci substituted with D). If a decomposition method for Ci was created from a concept inclusion Cr.(D1 , ..., D` ) v Ci entailed by O (and possibly obtained from an axiom Ci ≡ Cr.(D1 , ..., D` )), then every Dj , j = 1, ..., `, is a task concept among B1 , ..., Bn and we have O |= PC0 i /Cr.(D1 , ... ,D` ) v A, so PC0 i /Cr.(D1 , ... ,D` ) is the required concept.  Taking into account all possible combinations of tasks in the ontology presents a problem, since there are exponentially many. We propose a pragmatic solution. First, the maximal number of task concepts to be combined in onlysome expressions can be restricted by some number k. Second, most real-world domains (including our appli- cation example) have restrictions on which tasks can be combined. In our case study using the fitness training scenario, we only considered combinations of two task con- cepts defined by an onlysome axiom. This already enabled a considerable number of methods to be inferred. Essentially, the ontology used in our system consists of two parts O1 and O2 , with O1 containing definitions as above and O2 representing the core knowledge about the subject domain: exercises (being task concepts), training equipment, body anatomy, etc. The ontology is built in such a way that it guarantees independence of the role includes from any concept occurring under Cincludes, which means that the principle of matching task collections outlined in Section 3.1 correctly applies. The general shape of our ontology is formally described in the following theorem, where the role includes is abbreviated as r. Theorem 3 Let r be a role and O = O1 ∪ O2 an ontology such that O1 is an acyclic terminology consisting of definitions A ≡ Cr.(C1 , ..., Cm ), where r does not occur in C1 , ..., Cm and A, r do not occur in O2 . Then the role r is independent of any concepts appearing under Cr in O1 . Proof (Sketch). Let A be the set of concept names occurring on the left-hand side of axioms in O1 . Let I be a model of O and [s] a binary relation on the domain of I. Let I 0 be an interpretation obtained from I by changing the interpretation of r to [s]. Since r and A-concepts do not occur in O2 , we have I 0 |= O2 . It remains to consider an expansion of the terminology O1 (cf. [2, Prop. 2.1]) to verify that there exists a model J of O1 ∪ O2 obtained from I 0 by changing the interpretation of A-concepts (and leaving the interpretation of other symbols unchanged). For any concepts C1 , ..., Cm appearing under Cr in O1 , their interpretations in J and I coincide, which shows the required statement.  The initial planning domain of our case-study scenario encompasses 310 differ- ent tasks and a few methods. Its formalisation in the ontology consists of 1 230 con- cepts and 2 903 axioms, of which 613 concepts and 664 axioms are imported from the NCICB corpus. Initially, 9 different training objectives and 24 workout templates are specified. For extending the ontology with inferred decompositions, we employ the OWL reasoner FaCT++ [27], which requires 3.6 seconds on an up-to-date laptop computer (Intel R CoreTM i5-4300U). After being extended, the planning domain con- tains 471 tasks and 967 methods, of which 203 are created based on subsumptions between workouts and workout templates, and further three methods have been created by onlysome-combinations of task concepts. In addition, 59 decomposition methods for training objectives into workout templates are created of which 24 are onlysome- combinations of task concepts. Lying Gluteus Maximus Sumo obtained by obtained by Strength ... Gluteus warmed up decomposing Workout1 decomposing Training Deadlift Stretch Fig. 1. Example of a plan explanation for the task lying gluteus stretch 4 Explanations Cognitive systems that interact with users need to be able to adequately communicate their solutions and actions. In the field of HCI and dialog modelling, it was shown that systems that provide additional explanations receive increased trust from their users [16, 20]. Bercher et al. [3] empirically investigated the role of plan explanations in an interactive companion system in a real-world scenario. In our integrated approach, both DL reasoning and planning work together, thereby using the procedural and declarative information contained in the integrated knowledge model, and generating new information artefacts of different flavours (in particular, in- ferred facts and refined plans). We now describe how explanations are generated from this information by combining techniques from plan explanation (specifically, an ap- proach for explaining hybrid plans [25]) and an approach for explaining ontological inferences [23]. Together they offer complimentary views on a given application do- main. Plan explanation focuses on dependencies between tasks in a plan, in particular how tasks are decomposed into subtasks, and how these tasks are linked by preconditions and effects. To provide an explanation why a particular task is part of a generated plan, the information relevant to justify its purpose is extracted from the causal dependencies and the decompositions applied to the plan. Technically, this information (which internally is represented in a logic formalism) is considered the “explanation”. It is guaranteed that plan explanations are always linear chains of arguments, each based on its prede- cessor. For instance, consider that in our application scenario, the user asks to justify a particular action, for example “Why do I have to do a lying gluteus stretch?” Fig. 1 shows the dependencies that establish the use of the lying gluteus stretch within a plan that achieves a strength training. This information is further converted into text to be communicated to the user by using simple templates. Causal dependencies between two tasks A and B, where A provides a precondition l for B, are verbalised as “A is necessary as it ensures that l, which is needed by B.” Similarly, decompositions are justified by patterns such as “Task A is necessary, since it is part of B.” In the running example, this yields: The lying gluteus stretch is necessary as it ensures that the gluteus maximus is warmed up, which is needed by the sumo deadlift. The sumo deadlift is necessary, since it is part of the Workout1. The Workout1 is necessary, since it is part of the strength training. ... The mechanism presented so far represents the part of “traditional” plan explanation. Here, method decompositions are treated as facts (e.g. “Workout1 is part of strength XvY Y ≡Z Y is an RvDef atomic “... hhX v Y ii. Thus, hhX v Zii according XvZ concept to the definition of hh Y ii.” Fig. 2. Sample inference rule (left) together with corresponding text template (right). Guillements indicate the application of a function translating DL formulas into text. training”); however, in our approach, they can be justified further, since they correspond to subsumptions inferred from background knowledge in the ontology. Therefore, the reasoning behind the subsumption can be used as an explanation to justify the decom- position. For example, the user may ask the question “Why is Workout1 a strength training?” For this purpose, we use the second explanation mechanism, which has been implemented as a prototype. Its aim is to generate stepwise textual explanations for ontological inferences. In the running example, it outputs: According to its definition, Workout1 includes front squat and sumo deadlift. Furthermore, since sumo deadlift is an isotonic exercise, it follows that Workout1 includes an isotonic exercise. Given that something that includes an isotonic exercise has strength as an intended health outcome, Workout1 has strength as an intended health outcome. Thus, Workout1 is a strength training according to the definition of strength training. To generate such explanations, first a consequence-based inference mechanism is used to construct a derivation tree for a given subsumption. This is done in two stages. First the relevant axioms in the ontology (the “justifications”) are identified using the im- plementation provided by Horridge [12], which is done efficiently using a standard tableau-based reasoner. Then, a (slower) proof search mechanism using consequence- based rules is applied for building a derivation tree. This tree is then linearised to yield a sequence of explanation steps. The ordering of the explanation steps corresponds to a post-order traversal in the tree structure of inference rule applications (where the in- ference step that yields the conclusion is taken to be the root). As an example of a consequence-based inference rule used for explanation generation and its correspond- ing text template, consider Fig. 2. This template generates the last statement in the sample text shown above. Note that even though the presented inference rule is quite simple, it represents a (logical) shortcut, since the conclusion X v Z could also be obtained in two steps by inferring Y v Z from the equivalence axiom and then us- ing the transitivity of v. For the generation of explanations, this (logically redundant) rule is given precedence over the “standard” inference rules, in the interest of smaller proofs and greater conciseness of the generated text. By contrast, some inference rules are specified to never generate output, since it would be considered uninformative for a user. Consider the rule deriving X v (Y tZ) from X v Y , which is always ignored during text generation. Such considerations provide ample scope for further work into adjusting the generated texts according to pragmatics and user preferences. To answer the general question how well people understand automatically gener- ated verbalisations of ontological axioms and inferences, studies have already been per- formed as part of related work. For example, in experiments, Nguyen [18] found that the understandability of verbalised inference steps depends on the employed inference rules, where some kinds of inference rules were found considerably more difficult than others. Furthermore, if the more difficult-to-understand inference rules were verbalised in a more elaborated manner, understanding was improved. Such work hints at a general challenge for empirical evaluations of the general “usefulness” of such verbalisations (to be addressed as future work); their accessibility partially depends on the complexity of the formalised domain and on the prerequisites of the user. 5 Related Work Past research on coupling ontological reasoning and planning mainly addressed the aim of increasing expressivity/efficiency. There is a large body of research on integrating ontology and action formalisms, see e.g., the overview in Calvanese et al. [6], which aims at bringing together the benefits of static and dynamic knowledge representation. Gil [10] provides a survey of approaches joining classical planning and ontologies and names a number of planners that use ontological reasoning to speed-up plan genera- tion. Hartanto and Hertzberg [11] use a domain-specific ontology to prune a given HTN model. However, additional content in the domain can not be inferred in their paradigm. A number of approaches use ontologies to enrich the structure of the planning domain. Typically, ontologies provide hierarchies of tasks and plans and are often used to repre- sent states under the open world assumption [22, 26]. For a survey, we refer to Sirin [26, Chapter 8]. Further approaches (e.g. [14, 8]) use OWL as a representation language for HTN planning domains but do not employ ontology reasoning to extend these domains. Sirin [26] describes HTN-DL, combining HTN and description logics to solve Web Service composition problems. HTN-DL planning domains are encoded in an ontology by representing tasks as concepts and decomposition methods as individuals. Both are augmented with axioms describing their preconditions and effects. Here Sirin’s view of methods differs from standard HTN, as they define a partially ordered list of actions, but not an abstract task they decompose. Further, preconditions and effects are assigned to methods, which are not necessarily related to the contents of the plan. Although Sirin’s and our approach are similar in the idea of using an ontology and DL reasoning to generate planning domains, there are conceptual differences. In HTN-DL all decompo- sition methods are provided in the domain by a modeller, while the presented approach infers new decomposition methods. Sirin applies reasoning to determine whether a de- composition method can be applied to an abstract task, using their preconditions and effects. His approach does not allow inference based on the tasks in a method nor their decompositions or other properties, which is the cornerstone of ours. Related work on the generation of explanations from ontologies encompasses a number of approaches to verbalise the formalised contents with the goal of imitating natural language. Systems targeting non-expert users include, e.g., the NaturalOWL system [1] and the ontoVerbal verbaliser [15]. By contrast, the generation of expla- nations for entailments is addressed only by some approaches, e.g., by Horridge [12], whose approach targets expert users. The generation of stepwise explanations of entail- ments for non-expert users is considered by Borgida et al. [5], Nguyen et al. [19, 18] and Schiller and Glimm [23], whose work provided a basis for the approach to explanations presented in this paper. 6 Conclusion We presented an approach to integrating hierarchical planning knowledge into ontolo- gies that encompass a general representation of the application domain. A central issue of this paper is to establish the semantic correspondence between the constructs of the planning domain (in particular, decomposition methods) and their representation in the ontology. Our results enable a cognitive system to use a coherent knowledge model for both planning and reasoning, which at the same time enables coherent and detailed ex- planations for the user, as demonstrated in the application scenario. Our investigation also highlights avenues for future work. One such topic is incorporating mixed-initiative planning into the approach, such that communication with and participation of the user would benefit from explanations by the system. Second, the explanations generated by the system raise the issue of selecting the right level of verbosity. Future work should address this from the viewpoint of pragmatics (e.g. that explanations for “obvious” inferences should generally be omitted) and user modelling (e.g. taking prior knowl- edge of the user into account). While our approach enables the hierarchical structure of a planning domain to be exploited by DL reasoning, the partial order of tasks is not amenable to DL reasoning. The question how this limitation could be addressed can be taken up by future work. Acknowledgements. This work was done within the Transregional Collaborative Re- search Centre SFB/TRR 62 “A Companion-Technology for Cognitive Technical Sys- tems” funded by the German Research Foundation (DFG). Bibliography [1] Androutsopoulos, I., Lampouras, G., Galanis, D.: Generating natural language de- scriptions from OWL ontologies: The NaturalOWL system. JAIR 48, 671–715 (2013) [2] Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press (2003) [3] Bercher, P., Biundo, S., Geier, T., Hoernle, T., Nothdurft, F., Richter, F., Schat- tenberg, B.: Plan, repair, execute, explain - How planning helps to assemble your home theater. In: Proc. of the Int. Conf. on Automated Planning and Scheduling. pp. 386–394. AAAI Press (2014) [4] Biundo, S., Bercher, P., Geier, T., Müller, F., Schattenberg, B.: Advanced user assistance based on AI planning. Cognitive Systems Research 12(3-4), 219–236 (2011), Special Issue on Complex Cognition [5] Borgida, A., Franconi, E., Horrocks, I.: Explaining ALC subsumption. In: Proc. of the European Conf. on Artificial Intelligence. pp. 209–213. IOS Press (2000) [6] Calvanese, D., De Giacomo, G., Montali, M., Patrizi, F.: Verification and synthesis in description logic based dynamic systems. In: Proc. of the 7th Int. Conf. on Web Reasoning and Rule Systems (RR 2013). LNCS, vol. 7994, pp. 50–64. Springer (2013) [7] Erol, K., Hendler, J.A., Nau, D.S.: Complexity results for HTN planning. Annals of Mathematics and Artificial Intelligence 18(1), 69–93 (1996) [8] Freitas, A., Schmidt, D., Panisson, A., Meneguzzi, F., Vieira, R., Bordini, R.H.: Semantic representations of agent plans and planning problem domains. In: Engi- neering Multi-Agent Systems, pp. 351–366. Springer (2014) [9] Geier, T., Bercher, P.: On the decidability of HTN planning with task insertion. In: Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011). pp. 1955–1961. AAAI Press (2011) [10] Gil, Y.: Description logics and planning. AI Magazine 26(2), 73–84 (2005) [11] Hartanto, R., Hertzberg, J.: Fusing DL reasoning with HTN planning. In: KI 2008: Advances in Artificial Intelligence. LNCS, vol. 5243, pp. 62–69. Springer (2008) [12] Horridge, M.: Justification Based Explanations in Ontologies. Ph.D. thesis, Uni- versity of Manchester, Manchester, UK (2011) [13] Horridge, M., Drummond, N., Goodwin, J., Rector, A., Stevens, R., Wang, H.: The Manchester OWL syntax. In: Proc. of the Workshop on OWL Experiences and Directions. Athens, GA, USA (2006) [14] Ko, R.K.L., Lee, E.W., Lee, S.G.: Business-OWL (BOWL) – A hierarchical task network ontology for dynamic business process decomposition and formulation. IEEE Transactions on Services Computing 5(2), 246–259 (2012) [15] Liang, S.F., Scott, D., Stevens, R., Rector, A.: OntoVerbal: a generic tool and practical application to SNOMED CT. Int. J. of Advanced Computer Science and Applications 4(6), 227–239 (2013) [16] Lim, B.Y., Dey, A.K., Avrahami, D.: Why and why not explanations improve the intelligibility of context-aware intelligent systems. In: Proc. of the SIGCHI Conf. on Human Factors in Comp. Systems. pp. 2119–2128 (2009) [17] NCICB, N.: (2015), http://ncicb.nci.nih.gov/xml/owl/EVS/ Thesaurus.owl (accessed February 9, 2015) [18] Nguyen, T.A.T.: Generating Natural Language Explanations For Entailments In Ontologies. Ph.D. thesis, The Open University, Milton Keynes, UK (2013) [19] Nguyen, T.A.T., Power, R., Piwek, P., Williams, S.: Predicting the understandabil- ity of OWL inferences. In: The Semantic Web: Semantics and Big Data, LNCS, vol. 7882, pp. 109–123. Springer (2013) [20] Nothdurft, F., Richter, F., Minker, W.: Probabilistic human-computer trust han- dling. In: Proc. of the Annual Meeting of the Special Interest Group on Discourse and Dialogue. pp. 51–59. Association for Computational Linguistics (2014) [21] Pulido, J.C., González, J.C., González-Ferrer, A., Garcı́a, J., Fernández, F., Ban- dera, A., Bustos, P., Suárez, C.: Goal-directed generation of exercise sets for upper-limb rehabilitation. In: Proc. of the Workshop on Knowledge Engineering for Planning and Scheduling (2014) [22] Sánchez-Ruiz, A.A., González-Calero, P.A., Dı́az-Agudo, B.: Abstraction in knowledge-rich models for case-based planning. In: Case-Based Reasoning Re- search and Development, LNCS, vol. 5650, pp. 313–327. Springer (2009) [23] Schiller, M., Glimm, B.: Towards explicative inference for OWL. In: Proc. of the Int. Description Logic Workshop. vol. 1014, pp. 930–941. CEUR (2013) [24] Schmidt-Schauss, M., Smolka, G.: Attributive concept descriptions with comple- ments. AIJ 48, 1–26 (1991) [25] Seegebarth, B., Müller, F., Schattenberg, B., Biundo, S.: Making hybrid plans more clear to human users – a formal approach for generating sound explanations. In: Proc. of the Int. Conf. on Automated Planning and Scheduling. pp. 225–233. AAAI Press (2012) [26] Sirin, E.: Combining Description Logic Reasoning with AI Planning for Com- position of Web Services. Ph.D. thesis, University of Maryland at College Park (2006) [27] Tsarkov, D., Horrocks, I.: Fact++ description logic reasoner: System description. In: Proc. of the Third Int. Joint Conf. on Automated Reasoning (IJCAR). pp. 292– 297. Springer (2006) [28] Vardi, M.Y.: Why is modal logic so robustly decidable? In: Descriptive Com- plexity and Finite Models. vol. 31, pp. 149–184. American Mathematical Society (1997)