=Paper=
{{Paper
|id=Vol-3739/abstract-8
|storemode=property
|title=Towards CATS: A Modular ABox Abduction Solver Based on Black-Box Architecture (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-3739/abstract-8.pdf
|volume=Vol-3739
|authors=Janka Boborová,Jakub Kloc,Martin Homola,Júlia Pukancová
|dblpUrl=https://dblp.org/rec/conf/dlog/BoborovaKHP24
}}
==Towards CATS: A Modular ABox Abduction Solver Based on Black-Box Architecture (Extended Abstract)==
https://ceur-ws.org/Vol-3739/abstract-8.pdf
Towards CATS: A Modular ABox Abduction Solver Based
on Black-Box Architecture (Extended Abstract)
Janka Boborová, Jakub Kloc, Martin Homola and Júlia Pukancová
Comenius University in Bratislava, Mlynská dolina, 842 41 Bratislava, Slovakia
Abstract
CATS, standing for Comenius Abduction Team Solver, is an ABox abduction solver for description logics that
allows the users to choose among multiple abduction algorithms. The solver integrates the JFact reasoner as a
black-box, thanks to which it handles expressivity up to 𝒮ℛ𝒪ℐ𝒬 (OWL 2). It handles inputs and outputs via
OWL API and it offers a command line, GUI, and API interface.
Keywords
Abduction, description logics, ontologies, solver
1. Introduction
Abduction [1] is a type of hypothetical inference aiming to explain an observation using the background
knowledge of the problem domain. We specifically deal with ABox abduction [2]: Given a finite set of
ABox assertions Abd (hypotheses), a knowledge base 𝒦 and an ABox assertion 𝒪 (observation), an
ABox abduction problem is a pair 𝒫 = (𝒦, 𝒪) and a solution of 𝒫 (explanation) is a finite set of ABox
assertions ℰ ⊆ Abd such that 𝒦 ∪ ℰ |= 𝒪. We also require explanations to have standard properties
[2] such as minimality. In our work, 𝒪 can include any concept or role assertion (possibly multiple
ones), which may involve even complex concepts and negated roles. To prevent an infinite hypothesis
space, Abd consists of only atomic (concept and role) assertions and their complements involving any
named individuals from 𝒪 or 𝒦.
In the following example, we define an ABox abduction problem 𝒫𝑇 = (𝒦𝑇 , 𝒪𝑇 ) to determine the
potential causes of John’s toothache.
𝒦𝑇 = {DentalTrauma ⊑ Toothache, Cavity ⊑ SensitiveTeeth,
SensitiveTeeth ⊓ DrankColdDrink ⊑ Toothache},
𝒪𝑇 = {Toothache(john)}.
All desired explanations of 𝒫𝑇 are: ℰ1 = {DentalTrauma(john)}; ℰ2 = {DrankColdDrink(john),
Cavity(john)}; and ℰ3 = {DrankColdDrink(john), SensitiveTeeth(john)}.
There are some abduction solvers available [3, 4, 5, 6], however, they often offer only a single
abduction algorithm and most of them are limited w.r.t. the expressivity of description logics (DLs) they
are able to work with.
We introduce CATS, an ABox abduction solver for DLs with multiple alternate algorithms. The solver
builds on our previous experience with ABox abduction, particularly the black-box architecture based
on model extraction [7]. This allows us to plug-in an external DL reasoner from which a relevant part
of a model can be extracted. The resulting solver can thus handle any expressivity the DL reasoner can.
The following abduction algorithms are currently implemented: (i) MHS: Reiter’s classic algorithm
[8] that gradually searches the hypothesis space by building a tree structure called the HS-tree. It is
DL 2024: 37th International Workshop on Description Logics, June 18–21, 2024, Bergen, Norway
$ boborova@fmph.uniba.sk (J. Boborová); kloc4@uniba.sk (J. Kloc); homola@fmph.uniba.sk (M. Homola);
pukancova@fmph.uniba.sk (J. Pukancová)
https://dai.fmph.uniba.sk/~homola/ (M. Homola); https://dai.fmph.uniba.sk/~pukancova/ (J. Pukancová)
0009-0002-7487-9962 (J. Boborová); 0000-0001-6384-9771 (M. Homola); 0009-0001-3505-0716 (J. Pukancová)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
known to be incomplete [9], though our version does not use the third pruning condition to regain
completeness. (ii) HST: Wotava’s variant of MHS [10]. It generates the HS-tree in a way that prevents
duplicate paths from existing. This eliminates the need for Reiter’s second pruning condition and thus
avoids performing numerous subset checks while building the tree. (iii) MXP: A highly efficient but
incomplete method by Shchekotykhin et al. [11], relying on the divide and conquer principle. Currently,
it is the only incomplete method in CATS. (iv) MHS-MXP: A hybrid combination of MHS and MXP [7].
MXP can find multiple explanations in each node of the HS-tree and possibly prune the tree to reduce
its size and terminate the algorithm faster. (v) HST-MXP: An analogous hybrid combination of HST and
MXP.
CATS1 is a freely available software written in Java, using the OWL API [12] to work with DL objects.
2. Black-Box Integration with a DL Reasoner
To solve ABox abduction in a complete way, MHS and the algorithms derived from it require to run
repeated knowledge base consistency checks. Additionally, after each successful consistency check, the
algorithms need to obtain the ABox assertions that are satisfied in a model of the knowledge base to
navigate the search for explanations in the hypothesis space [8]. This latter functionality is referred
to as model extraction. In a truly black-box setting, we wish to delegate these tasks to an external DL
reasoner.
While consistency checking is a standard task for any DL reasoner, model extraction is not. Not
all DL reasoners need to construct a model (or its sufficient representation) to check knowledge base
consistency. But for instance, tableau-based DL reasoners [13, 14, 15] build a finite representation of a
model (dubbed completion graph). This representation is sufficient [16] to extract the facts required
in the basic ABox abduction setting, namely the set of all atomic concept and role assertions that are
satisfied in the model.
CATS currently uses a modified version of the JFact reasoner2 [7]. To our best knowledge, this is
the only DL reasoner to date that supports the OWLKnowledgeExplorerReasoner interface3 of the
OWL API that enables to read the completion graph. Possibly, other tableau-based DL reasoners could
implement this OWL API interface in the future. This would grant CATS the potential to experiment
with different reasoners in a modular way, to compare their capabilities, and to give the user the option
to choose between them.
3. CATS Solver
CATS supports any OWL 2 [17] ontology as the background knowledge of an abduction problem.
It currently implements the abduction algorithms listed above. The option to choose from different
algorithms can be utilised in multiple ways. Firstly, CATS may be used to empirically compare their
performance. Secondly, the user can choose an algorithm that is most suitable for their needs, as each
algorithm has an advantage over the others in specific situations. For example, when the user wants
to obtain any set of explanations quickly, it is best to use MXP. When all explanations are required,
different algorithms are necessary. MHS-MXP can be very efficient if we limit the hypothesis space to
atomic assertions only. If negations are included, it is better to use MHS or HST.
The solver also provides various options for configuring the abduction problem, such as the maximal
length of the explanations found, the maximal duration of solving, or limiting what symbols or axioms
the explanations can include.
By default, CATS is a command-line application that uses structured text files as its inputs. Let us
show an example of CATS’s input using the problem 𝒫𝑇 from the introduction:
1
https://github.com/Comenius-Abduction-Team/CATS-Abduction-Solver
2
https://github.com/boborova3/jfact
3
https://owlcs.github.io/owlapi/apidocs_4/org/semanticweb/owlapi/reasoner/knowledgeexploration/
OWLKnowledgeExplorerReasoner.html
-f: files/toothache_ontology.owl
-o: Prefix: pref: Class: pref:Toothache
Individual: pref:john Types: pref:Toothache
-alg: MHS-MXP
𝒦𝑇 was processed into toothache_ontology.owl. For readability, 𝒪𝑇 is split into three lines, but
in a proper input file, it would have to be in one. To compute explanations, MHS-MXP will be used.
This example can be run using command java -jar cats.jar . Subsequently, we obtain an output:
1; 1; 0,05; {{DentalTrauma(john)}}
2; 2; 0,05; {{Cavity(john),DrankColdDrink(john)},
{SensitiveTeeth(john),DrankColdDrink(john)}}
0,08
The last output line contains the total running time. Other lines are in the form: ;;; {}. As we can see, with MHS-MXP, we found all explanations ℰ1 –ℰ3 in 0.08 seconds. Because
this is a small example, we cannot demonstrate the differences between the algorithms in time efficiency.
We would get the same result using MHS, HST and HST-MXP. The only difference is in MXP, which
could not find ℰ3 .
CATS can be also used via a graphical interface in the DL Abduction App4 [18], which can be seen in
Figure 1. Another way of utilising the solver is by integrating it directly into Java code through the DL
Abduction API5 [18]. This library allows developers to work with the solver through abstract interfaces,
without the need to know how it functions internally.
Figure 1: Using CATS via the DL Abduction App.
4
https://github.com/Comenius-Abduction-Team/Abduction-App
5
https://github.com/Comenius-Abduction-Team/DL-Abduction-API
4. Outlook
Our main future goal is to extend CATS with more well-known abduction algorithms, such as HS-DAG
[9] (and its improved version, RC-Tree [19]) and combine them with MXP. We will also add the option
to use other efficient incomplete algorithms, such as QuickXplain [20], that is already implemented in
the solver, but currently only used as a part of MXP.
In the future, we would like to conduct a comparative evaluation of the algorithms, taking advantage of
the fact that they all share the same code-base and modular architecture. However, further considerations
are needed in regard to what test cases and methodology to use. Some works [21, 6, 7] already performed
evaluations, but to our knowledge, there is no standard proven procedure yet.
Acknowledgments
We were sponsored by the Slovak Republic under the grant no. APVV-19-0220 (ORBIS) and by the EU
under the H2020 grant no. 952215 (TAILOR). J. Boborová was supported by a DL student grant. J. Kloc
was supported by an extraordinary scholarship awarded by Comenius University in Bratislava, Faculty
of Mathematics, Physics and Informatics, and by a DL student grant.
References
[1] C. S. Peirce, Illustrations of the logic of science VI: Deduction, induction, and hypothesis, Popular
Science Monthly 13 (1878) 470–482.
[2] C. Elsenbroich, O. Kutz, U. Sattler, A case for abductive reasoning over ontologies, in: Proceedings
of the OWLED*06 Workshop on OWL: Experiences and Directions, Athens, GA, US, volume 216
of CEUR-WS, 2006.
[3] J. Du, K. Wang, Y. Shen, A tractable approach to ABox abduction over description logic ontologies,
in: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27-31, 2014,
Québec City, Québec, Canada., 2014, pp. 1034–1040.
[4] W. Del-Pinto, R. A. Schmidt, Abox abduction via forgetting in ALC, in: The Thirty-Third AAAI
Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, AAAI Press, 2019, pp.
2768–2775.
[5] J. Pukancová, M. Homola, The AAA ABox abduction solver, Künstliche Intell. 34 (2020) 517–522.
[6] P. Koopmann, W. Del-Pinto, S. Tourret, R. A. Schmidt, Signature-based abduction for expressive
description logics, in: Proceedings of the 17th International Conference on Principles of Knowledge
Representation and Reasoning, KR 2020, Rhodes, Greece, 2020, pp. 592–602.
[7] M. Homola, J. Pukancová, J. Boborová, I. Balintová, Merge, explain, iterate: A combination of
MHS and MXP in an ABox abduction solver, in: Logics in Artificial Intelligence – 18th European
Conference, JELIA 2023, Dresden, Germany, September 20–22, 2023, Proceedings, volume 14281 of
LNCS, Springer, 2023, pp. 338–352.
[8] R. Reiter, A theory of diagnosis from first principles, Artif. Intell. 32 (1987) 57–95.
[9] R. Greiner, B. A. Smith, R. W. Wilkerson, A correction to the algorithm in Reiter’s theory of
diagnosis, Artif. Intell. 41 (1989) 79–88.
[10] F. Wotawa, A variant of Reiter’s hitting-set algorithm, Inf. Process. Lett. 79 (2001) 45–51.
[11] K. M. Shchekotykhin, D. Jannach, T. Schmitz, MergeXplain: Fast computation of multiple conflicts
for diagnosis, in: Proceedings of the 24th International Joint Conference on Artificial Intelligence,
IJCAI 2015, Buenos Aires, Argentina, AAAI Press, 2015.
[12] M. Horridge, S. Bechhofer, The OWL API: A java API for OWL ontologies, Semantic Web 2 (2011)
11–21.
[13] I. Palmisano, JFact DL reasoner, http://jfact.sourceforge.net/, .
[14] B. Glimm, I. Horrocks, B. Motik, G. Stoilos, Z. Wang, Hermit: An OWL 2 reasoner, Journal of
Automated Reasoning 53 (2014) 245–269.
[15] E. Sirin, B. Parsia, B. Cuenca Grau, A. Kalyanpur, Y. Katz, Pellet: A practical OWL-DL reasoner,
Journal of Web Semantics 5 (2007) 51–53.
[16] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (Eds.), The Description
Logic Handbook: Theory, Implementation, and Applications, Cambridge University Press, 2003.
[17] B. Cuenca Grau, I. Horrocks, B. Motik, B. Parsia, P. Patel-Schneider, U. Sattler, OWL 2: The next
step for OWL, J. Web Semant. 6 (2008) 309–322.
[18] J. Kloc, M. Homola, J. Pukancová, DL abduction API v2 and GUI interface (Extended abstract), in:
Proceedings of the 36th International Workshop on Description Logics (DL 2023), Rhodes, Greece,
September 2–4, 2023, volume 3515 of CEUR-WS, 2023.
[19] I. Pill, T. Quaritsch, RC-Tree: A variant avoiding all the redundancy in Reiter’s minimal hitting set
algorithm, in: 2015 IEEE International Symposium on Software Reliability Engineering Workshops,
ISSRE Workshops, Gaithersburg, MD, USA, November 2-5, 2015, IEEE Computer Society, 2015, pp.
78–84.
[20] U. Junker, QuickXplain: Preferred explanations and relaxations for over-constrained problems, in:
Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference
on Innovative Applications of Artificial Intelligence, San Jose, California, US, AAAI Press, 2004,
pp. 167–172.
[21] J. Du, G. Qi, Y. Shen, J. Z. Pan, Towards practical ABox abduction in large description logic
ontologies, Int. J. Semantic Web Inf. Syst. 8 (2012) 1–33.