Description Logics (DLs) and Logic Programs are formalisms for describing knowledge about the world. In industrial settings, DLs are often used to describe factories and inventories, and logic programs could be useful for planning production - if they can be integrated with DLs. We here introduce a variation of the DL Program formalism for integrating description logics with Answer Set Programming (ASP). We a new implementation based on OWLAPI and a use case in Explainable AI for production planning. Our integration is based on the HEX formalism and the Hexlite solver. Different from previous work, we extend the integration interface to permit an arbitrary number of parallel modifications of the OWL ontology to be considered for the computation of a single answer set. This is useful to model changes of the planning domain over time, where each time step is a separate modification of the ontology. We present a case study towards the EU recommendations on 'Human-centered, trustworthy AI systems', concretely we present a production planning framework that can be challenged by users with alternative scenarios. With our case study we argue that Explainability in the context of planning is not about the rationale behind decisions (those are defined by formal semantics and by the program) but we argue that Explainability should mainly focus on the possibility of human operators to challenge the system and request alternative solutions under alternative assumptions. We provide the following examples to show that Logic Programming requires only very small modifications to provide insights by means of the following whatif questions: (i) which machines could be deactivated without preventing to reach the production goal and (ii) which product could be skipped to reach a reduced production goal in a shorter time limit.
Description Logics (DLs) are useful tools for describing knowledge about objects in the world, and they are in practical usage in industrial settings, where they are the basis for describing factory inventories and production processes. These descriptions are static and usually considered timeless.
In production planning, processes in a factory change products
and materials. For planning it is useful to consider changes in the
assertional knowledge of an ontology. One method for planning is
the usage of Answer Set Programming (ASP) [
r1 : MRobot b1 : OpenBox r2 : MRobot b2 : OpenBox r2 : PRobot b3 : ClosedBox is represented as a sequence of steps and in each step different truth values can hold in the world.
In practice, representing planning in DLs or representing
ontological knowledge in ASP is usually impractical.2 Therefore, it is natural
to integrate DLs and ASP in a way that both formalisms are used in
parallel within one integrated reasoning method. HEX is an ASP
formalism for integrating ASP with external computations of all kinds,
and one existing method for integrating ASP with DLs, DL-programs
[
As a running example, consider an ontology about robots that can manipulate and paint boxes: the TBox is shown in Figure 1, the ABox of a concrete factory is shown in Figure 2. The goal of our production planning is to find a sequence of actions that paint all boxes where only robots in the class PRobot can paint and only closed boxes afford3 painting. Finally, robots in the class MRobot can open and close boxes. Consider now the following information we would like to gain by quering this planning domain: (I) is there a plan that finishes the production within n1 steps, using as few actions as possible, and what is that plan; (II) if we would have n2 > n1 steps available, which robots could we omit from the domain and still finish the job in time; (III) if we have only n3 < n1 steps available, which product 2 It is sometimes possible due to complexity results. 3 Affordances are a popular concept in robotics regarding prototypical actions: if an object affords a certain action, it provides the possibility to be affected by that action. An affordance is a property of an object, not an agent, and some agents might not be capable of performing the action due to geometric constraints or missing actuators. could we omit from production to finish the other products in time.
DL-programs [
In the following, we use the idea of DL-programs but we develop and present the problem directly within the HEX-formalism. This removes one layer of abstraction and simplifies presentation.
ASP is often praised for its Elaboration Tolerance [
Human Agency, concretely to ‘self-assess and challenge the system‘; and Technical Robustness, concretely to provide ‘Fallback Plans‘.
We next address above challenges and make the following contributions.
We introduce a new way of interfacing with DLs from HEX where it is easily possible to describe multiple ontology modifications in the extension of one predicate, which facilitates the encoding of domains where multiple alternative worlds must be considered and we do not know beforehand how many of such alternative worlds exist. Planning is such a domain.
We implement this integration using the OWLAPI interface and the
HEXLITE solver [
We present a use case of production planning where action preconditions are defined by the ontology, action effects are realized as ontology modifications in the HEX program, and the initial state of the world is taken from the ontology, including in particular all individual names which are not known to the HEX program prior to solving.
We formulate our thoughts about how Explainability can be realized in Logic programs and argue that the classical notion of Explainability does not apply to Logic Programming, and that instead the possibility to challenge the system with alternative scenarios is an appropriate way to make a Logic Program more human-centric.
We discuss a possible usage of the production planning encoding for obtaining explanations about feasible and necessary changes in the production process to reach given production goals. Such reasoning can be useful for optimizing the factory and for hardening it against equipment malfunctions. framework for integrating OWLAPI in HEX and comment on the implementation, in Section 4 we use the framework for demonstrating how to explain contingencies in production planning, we discuss Explainability in Section 5 and we conclude in Section 6 with a brief discussion. 2 2.1
We give syntax and semantics of the HEX formalism [
Let C, X , and G be mutually disjoint sets whose elements are called constant names, variable names, and external predicate names, respectively. Usually, elements from X and C are denoted with first letter in upper case and lower case, respectively; while elements from G are prefixed with ‘ & ’. Elements from C [ X are called terms. An (ordinary) atom is a tuple p(Y1; : : : ; Yn) where p 2 C is a predicate name and Y1; : : : ; Yn are terms and n 0 is the arity of the atom. An atom is ground if all its terms are constants. An external atom is of the form &g[Y1; : : : ; Yn](X1; : : : ; Xm), where Y1; : : : ; Yn and X1; : : : ; Xm are two lists of terms, called input and output lists, respectively, and &g 2 G is an external predicate name. We assume that input and output lists have fixed lengths in(&g) = n and out (&g) = m. With each term Yi in the input list, 1 i n, we associate a type ti 2 fconsg [ N. We call the term constant input iff ti = cons, otherwise we call it predicate input of arity ti.
A rule r is of the form 1 _ _ k 1; : : : ; n; not n+1; : : : ; not m with m; k 0 where all i are atoms and all j are either atoms or external atoms. We let H(r) = f 1; : : : ; kg and B(r) = B+(r) [ B (r), where B+(r) = f 1; : : : ; ng and B (r) = f n+1; : : : ; mg. A HEX-program is a finite set P of rules.
Given a rule r, the grounding grnd (r) of r is obtained by systematically replacing all variables with constants from C. Given a HEXprogram P , the Herbrand base HB P of P is the set of all possible ground versions of atoms and external atoms occurring in P obtained by replacing variables with constants from C. The grounding grnd (P ) of P is given by grnd (P ) = Sr2P grnd (r). Importantly, the set of constants C that is used for grounding a program is only partially given by the program itself: external computations may introduce new constants, for example external computations can import individual names from an ontology.
Extensional Semantics [
An interpretation I HB P is a model of an atom a, denoted
I j= a if a is an ordinary atom and a 2 I. I is a model of a ground
external atom a = &g [y1; : : : ; yn](x1; : : : ; xm) if (x1; : : : ; xm) 2
F&g(I; y1; : : : ; yn). Given a ground rule r, I j= H(r) if I j= a for
some a 2 H(r); I j= B(r) if I j= a for all a 2 B+(r) and I 6j= a
for all a 2 B (r); and I j= r if I j= H(r) whenever I j= B(r).
Given a HEX-program P , I j= P if I j= r for all r 2 grnd (P ); the
FLP-reduct [
An important shortcut notation that we use in this work is the guess in the head of a rule: f 1; ; kg 1; : : : ; n; not n+1; : : : ; not m with m; k 0 is rewritten into a set of rules such that, given the rule body is satisfied, candidate answer sets are generated which contain all subsets of f 1; : : : ; kg. 2.2
Description Logics (DLs) [
For the purposes of this paper it is sufficient to introduce concept inclusion axioms, concept intersection, the empty concept, and concept assertions. Concept inclusion axioms of form C v D denote that 8x : C(x) ! D(x), i.e., every instance in concept C is also in concept D. Concept intersection C u D is a concept expression that contains the intersection of two concepts, i.e., all instances that are both in C and in D. The empty concept, ?, denotes an impossible class that is always empty. A concept membership axiom of form i : C denotes that the individual/constant i is in concept C. Example 1. In our running example TBox in Figure 1, the meaning of each axiom is written next to the axiom, except for the affordances which can be read as ‘A ordsClosing is an A ordance’, etc. The ABox in Figure 2 introduces individual constants into the theory and assigns concept memberships to them.
Answer Set Programs and DLs have been combined in Description
Logic Programs (DL-Programs) [
DL[C1 op1 p1; : : : ; Cm opm pm; Q](~t) which evaluates the DL-Query Q on an ontology modified by operations of form C op p and evaluates to true for all tuples ~t in the result of query Q. The modifications can add (op = ]) or subtract (op = [-) the extension of predicate p from the assertions of concept C. Note that one DL-atom always takes the whole extension of all predicates p1; : : : ; pm to modify the ontology. 6 Formally, this is the set fyi(v1; : : : ; vti ) 2 Ig.
Our novel integration interface has two major components: a representation for ontology modifications in ASP atoms (Section 3.1) and external atoms that query the ontology based on these modifications (Section 3.2). 3.1
Ontology modifications are represented as atoms in ASP as follows. Definition 1. A modification atom is of the form ( ; ) 2 N and with some predicate name, one of the following terms: addc(C; I) delc(C; I) addop(OP ; I1; I2) delop(OP ; I1; I2) adddp(DP ; I; D) deldp(DP ; I; D) where C, OP , and DP are OWL Class, Object Property, and Data Property IRIs, respectively, I, I1, and I2 are OWL Individual IRIs, and D is either an integer or a string parseable as OWL Data value.
Intuitively the modifications in (2) add ABox assertions and those in (3) remove ABox assertions. (1) (2) (3) 3.2
External atoms for querying the ontology are of the following form, where ! is a specifier for the ontology and / are as above. &dlConsistent [!; ; ]()
for consistency of the ontology (4) &dlC [!; ; ; C ](I )
for querying class instances &dlDP [!; ; ; DP ](I1 ; I2 )
for querying data properties &dlOP [!; ; ; OP ](I1 ; D ) for querying object properties (5) (6) (7)
Intuitively, these external atoms query the ontology ! after it has been modified using all modifications in the extension of in the current answer set candidate I, selected by . Formally, the above external atoms perform reasoning on the ontology modified by f j ( ; ) 2 Ig: Example 2. In our running example, the external atom &dlC[onto,delta,T,"ex:AffordsOpening"](B) with T=0 and an empty extension of delta is false for B=b1 and true for B=b2, because the ontology contains assertions b1 : ClosedBox and b2 : OpenBox from which the reasoner infers that b1 affords opening (via Axiom ClosedBox v A ordsOpening ) but b2 does not.
The HEX-program defines in each time step T that the modification of the ontology corresponds with the planning state which is represented in predicate s(Box,State,T). Therefore, if at T=2 some action has caused a change in the state such that s(b1,open,2) and s(b2,open,2) are true, then the above external atom, with T=2, is false for both B=b1 and B=b2.
The format of the ontology specifier ! is a string pointing to a JSON file that holds the location of the OWL ontology file and provides namespaces for usage in ASP.
Example 3. In our running example, the file meta.json has the # c o n s t o n t o =” meta . j s o n ” . following content.
{ } } "load-uri": "sample.owl", "namespaces": { "owl": "http://www.w3.org/2002/07/owl#", "ex": "http://www.kr.tuwien.ac.at/hexlite/example#"
The external atoms (4)–(7) have been implemented in the OWLAPI
Plugin7;8 for the HEXLITE [
To facilitate value invention from the ontology, i.e., to allow for importing all individual names from the ontology instead of specifying them in the HEX program, the OWLAPI plugin contains ‘readonly’ external atoms of the form &dlCro[!; C ](I ) &dlDPro[!; DP ](I1 ; I2 ) &dlOPro[!; OP ](I1 ; D) which correspond to (5)–(7) but operate on the unmodified ontology.
Here we concretely develop the use case described in the Introduction as a HEX-program. the same time; in the ontology;12 the initial state of the planning domain is obtained from the ontolall fluents are inertial, i.e., the fluent state it is maintained unless otherwise specified, moreover a box cannot be open and closed at the fluents are represented in delta predicates so that the OWLAPI integration can represent the fluent values not only in ASP but also we require consistency of the ontology for all time steps, using the &dlConsistent external atom; we guess which action is applied, where actions are licensed by certain affordances on boxes and can be performed by certain robot types; we constrain actions so that each robot can only perform one action at each step, and each box can be affected by only one action at each step; finally we define the effect of actions on the fluents. 12 Note, that we remove the OWL assertions that correspond with non-true fluent values, and we add assertions for true fluent values. This ensures that the initial state (which is represented in the ontology in form of OpenBox and ClosedBox assertions does not interfere with reasoning in time steps T > 0. We could get rid of all ‘del’ operations by using a separate ontology for specifying the initial state. This is possible using the plugin but it would complicate the example. (c) %% manadke a c t i o n s as e a r l y as p o s s i b l e
as few as p o s s i b l e : do (A, T ) . [ T+1@1, A] (i) % aim t o f i n i s h i n t i m e s t e p 3 # c o n s t f i n a l t i m e s t e p = 3 .
% aim t o f i n i s h i n t i m e s t e p 5 (ii) # c o n s t f i n a l t i m e s t e p = 5 .
% r e q u i r e b o x e s t o be p a i n t e d i n t h e f i n a l s t e p : box (B ) , not s t a t e ( B , p a i n t e d , f i n a l t i m e s t e p ) . % d e a c t i v a t e as many r o b o t s as p o s s i b l e f e x p l a n a t i o n ( d e a c t i v a t e (R ) ) g : r o b o t (R ) . : not e x p l a n a t i o n ( d e a c t i v a t e (R ) ) , r o b o t (R ) . [ 1@2, R] % d e a c t i v a t e d r o b o t s c a n n o t do a c t i o n s : e x p l a n a t i o n ( d e a c t i v a t e (R ) ) ,
a c t S t e p ( S ) , do ( a c t i o n ( , R , ) , T ) . % r e q u i r e b o x e s t o be p a i n t e d i n t h e f i n a l s t e p : box (B ) , not s t a t e ( B , p a i n t e d , f i n a l t i m e s t e p ) . % aim t o f i n i s h i n t i m e s t e p 2 (iii) # c o n s t f i n a l t i m e s t e p = 2 .
% g u e s s which b o x e s t o s k i p f o r p a i n t i n g f e x p l a n a t i o n ( s k i p (B ) ) g : box (B ) . % s k i p as few as p o s s i b l e : e x p l a n a t i o n ( s k i p (B ) ) , box (B ) . [ 1@2, B] % r e q u i r e non s k i p p e d b o x e s t o be p a i n t e d : box (B ) , not e x p l a n a t i o n ( s k i p (B ) ) ,
not s t a t e ( B , p a i n t e d , f i n a l t i m e s t e p ) . Given a value for finaltimestep this encoding does not contain a planning goal, that means it will produce all possible plans and all resulting states without a restriction on the final state. For example, resulting plans include the plan without actions, and the plan that repeatedly opens and closes a single box. 4.2
When we compute answer sets using the above program fragments integrated with the above ontology, we obtain the following results. (C)+(I) Painting all boxes until time step 3: Table 1 shows two optimal answer sets for this query. We observe that the integration successfully permitted only those actions that are licensed by affordances in the ontology. Multiple plans of the same quality exist, they differ in the order of closed and painted boxes. Table 2 provides the ontology modifications that are used in each time step of the planning to obtain the first plan in Table 1. (C)+(II) Explaining how to reduce the number of robots by achieving the goal only at time step 5: Table 3 shows one of the optimal answer sets: an explanation together with a witnessing plan. We observe that the robot r2, which can both paint and manipulate boxes, was chosen to do the whole work, and r1, which can only manipulate boxes, was deactivated. As in the previous example, multiple plans of same quality exist. However, all plans deactivate r1 because without r2 the goal can not be reached. (C)+(III) Explaining how to finish the work until time step 2 by skipping a product: Table 4 displays one of the optimal explanations together with its witnessing plan. Note that b2 is not touched by the robots, although r1 is idle in Step 1 and could close it. This can be explained by constraint (C) which requires robots to perform only the minimally required actions for reaching the goal. In this section, we argue that Explainability as it is usually understood is not applicable to Answer Set Programming and propose an alternative.
The classical notion of Explanation in AI aims to provide to the user of a system at least some parts of the rationale, assumptions, data, and reasoning process that leads to a decision. In the case of Logic Programming, decisions are made on (i) the basis of a mathematical framework, i.e., based on the mathematical definition of Logic Programming, (ii) based on the program given by the programmer, and (iii) based on the query we pose to the program, again in the shape of program rules that have clearly defined syntax and semantics. Therefore, explanations of the classical form would amount to teaching formal semantics and presenting the program that is reasoned upon by the solver software, which is neither feasible for an end-user nor does it serve the intention of Explainability. Classical explanations apply mostly to Machine Learning systems where the system makes a decision based on input data and a model learned from training data, and where usually a big amount of input data (such as audio or video data) is fed to an algorithm that makes a decision that is based on a small part of that input data.
Classical Logic Programming makes no decisions in the presence of uncertainty, it produces multiple solutions that are equally viable. In case of optimization criteria, it is also clearly determined which solution(s) are preferred.
Teaching end-users the formal semantics of ASP so that they can understand the reasoning process and programs requires to make 0 1 2 3 4 5 0 1 2 end-users experts in order to use explanations. This approach would be too fine-grained to have any practical value. Therefore, a more macroscopic approach for Explainability is necessary.
We therefore argue that the best way to gain Explainability in Logic Programming is an interaction possibility where users can (i) challenge the system with alternative scenarios, (ii) explore differences between alternative solutions to a single scenario, and (iii) change optimization criteria to explore their effect on solutions. The short query snippets we presented in the previous section (Figure 4) provide such a way of challenging the system using concise program additions or modifications.
The ASP literature contains several studies about such types of
Explainability under the names Diagnosis [
We have described a new interface for integrating Description Logics, in particular every DL reasoner that is compatible with OWLAPI, with logic programming under Answer Set Semantics, concretely using the HEX formalism. The benefit of such an integration is, that the ontology is used in its original form, and that the ASP planning domain permits all freedoms that ASP provides for planning, as demonstrated by our example use cases with explanatory queries. An alternative solution for integrating ontologies with logic programs would be to convert the ontology into a logic program, but this creates the need for a conversion process and for maintenance of not only the ontology but also the conversion process.
Using logic programming for planning is only one possibility among many others. The benefit of using Answer Set Programming is the power and freedom that comes with a guess-and-check paradigm where guesses and constraints and optimizations can be combined freely. In particular, Answer Set Programming permits expressive representations such as indirect effects/ramifications and domain-global constraints and optimization criteria that are difficult or impossible to model in STRIPS and PDDL.
DL-Programs [
Action Languages, e.g., PDDL [
As future work on the API side of the integration, we see an extension of the interface to permit arbitrary DL queries using the OWLAPI DL Query Parser, and additional ontology modifications that permit adding and removing axioms. As future work on the implementation side, it will be necessary to generate on-demand constraints that speed up the reasoning. Due to time constraints it was not possible to implement this technique so far, therefore we here do not report timing results.
We would like to acknowledge fruitful discussions about Description Logics and Production Planning with Magdalena Ortiz, Ivan Gocev, Raoul Blankertz, Sonja Zillner, and Stephan Grimm. We would also like to thank the referees and chairs for their feedback. This work has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement 825619 (AI4EU).