Doctoral colloquium - Janka Boborová (25.3.2024)

Monday 25.3.2024 at 13:10, Lecture room I/9

20. 03. 2024 15.46 hod.
By: Damas Gruska

Janka Boborová:
CATS: Experimental solver employing multiple algorithms to tackle abduction

Abstract:
Abduction is one of the inference types that is less explored, therefore, it is interesting to research in the area of ontologies and description logics. The task of abduction is to explain (in the form of facts) an observation (also a fact) using the background knowledge of a problem domain. It has been applied, for example, in medical diagnosis, criminology and model-based diagnosis.
There are few abduction solvers, and even fewer employ more than one abduction algorithm. We have an experimental implementation of an abduction solver, recently dubbed CATS, that included two abduction algorithms: Minimal Hitting Set algorithm (MHS) and MHS-MXP, which is a hybrid combination of MHS and the MergeXplain method (MXP) that is used to speed up the search for explanations. MHS-MXP is a new method that has been developed by our faculty and is still being optimized. On the other hand, the MHS algorithm is well-known but considered outdated. Therefore, we wanted to find newer versions that could be combined with MXP.
Our goal is to expand CATS with more abduction algorithms and their hybrid combination with MXP. Then, propose a proper evaluation and compare them. We also plan to look into optimizing our hybrid approaches.
We researched several algorithms, found newer variants of MHS, and successfully managed to implement one of them (HST) and its hybrid combination (HST-MXP) into our solver. Currently, we are working on optimizing CATS mainly in terms of memory use and major code refactorization. Then, we are ready to implement the second MHS variant called RC-Tree.