Slovenský názov: Optimalizácia MHS-MXP algoritmu
Vedúci: doc. RNDr. Martin Homola, PhD.
Konzultant: Mgr. Janka Boborová
Rýchly prehľad pojmov
Anotácia
Abduktívny algoritmus MHS-MXP využíva metódu rozdeľuj a panuj (MXP) pri prehľadávaní priestoru možných vysvetlení (HS-strom).
Behy MXP sú iterované, preto môže vhodná heuristika, orezávanie stromu a kešovanie informácií z predchádzajúcich behov potenciálne zlepšiť čas behu v nasledujúcich iteráciách.
Ciele
- ☑ Analyzovať prácu s pamäťou v MHS-MXP solveri
- ☑ Optimalizovať extrakciu modelov
- ☑ Preskúmať alternatívne algoritmy
- ☑ Implementovať HST a HST-MXP
- ☑ Implementovať HS-Dag/RC-Tree a MXP verziu
- ☐ Evalvovať výkon a vlastnosti jednotlivých algoritmov
- ☐? Evalvovať efektívnosť optimalizácii pamäte
Prvé 3 kapitoly
Kód solveru na GitHube
Postup riešenia
December 2023
Kód
- mergovanie rôznych verzii solvera, ktoré vznikli v rámci dvoch záverečných prác
- oprava drobných bugov z minulých verzii
- analýza "podozrivého" správania solvera: správnosť kešovania; správnosť práce s modelmi; heap dumpy z príkladov, ktoré počas evalvácie padli na nedostatku pamäte...
Články
- oboznamovanie sa s algoritmami MHS a MHS-MXP a "treťou orezávaciou podmienkou" - súčasťou MHS algoritmu, ktorá nie je v solveri implementovaná, lebo bola neskôr dokázaná jej nekorektnosť
- hľadanie alternatív, ktoré opravily chybu v tretej podmienke - algoritmus HS-Dag
Január 2024
Články
- skúmanie algoritmov HST(alternatívny prístup k riešeniu 3. orezávacej podmienky) a RC-Tree(vylepšenie HS-Dag)
- rozhodnutie implementovať HST ako alternatívu k MHS
Február 2024
Kód
- zavedenie unit testov na kontrolu správnosti zmien v solveri
- implementácia algoritmov HST a HST-MXP
- spustenie malej evalvácie na serveri na porovnanie časovej efektívnosti HST(-MXP) a MHS(-MXP)
Marec 2024
Evalvácie
- analýza výsledkov evalvácie - HST v drvivej väčšine prípadov nie je efektívnejšie než MHS-MXP
- kontroly, prečo je HST menej efektívne - vytvára veľmi veľa vrcholov
Písanie
Apríl 2024
Kód
- extrakcia modelov extrahuje iba axiómy, ktoré sú v abducibles
- ak sú zakázané negácie vo vysvetleniach, ignorujú sa axiom abducibles s negáciou (predtým boli tieto axiómy povolené aj pri zakázaných negáciách)
- refaktorizácia a dokumentácia kódu solvera a súvisiacích knižníc (aby sa na nich ľahšie pracovalo bakalárskym študentom v rámci semestrálnych a bakalárskych prác)
Máj 2024
Kód
- extrakcia modelov nevytvára nové objekty axiómov, iba recykluje tie, čo už sú v abducibles
Evalvácia
- testovanie vstupov, ktoré počas minuloročnej evalvácie padali na nedostatku pamäte - 8 zo zvolených 9 už na chybe nepadajú
Písanie
- prepisovanie článku na DL na finálnu verziu
Jún 2024
Kód
- implementácia MXP ako samostatne spustiteľného algoritmu
- oprava bugov v HST a extraktore modelov
Reprezentácia
- prezentovanie práce na konferencii DL Workshop 2024
Júl 2024
Kód
- náhrada nevhodných pamäťových štruktúr (napr. LinkedList -> ArrayList)
- optimizácia HST - neextrahujú sa modely, ak každý axióm z abducibles už má priradený index
August 2024
Kód
- oddelenie tried reprezentujúcich vrchol stromu a model
- prerobenie systému, ako sa narába s modelmi
- samostatné triedy pre vrchol MHS stromu a HST stromu - príprava na oddelenie algoritmov v novej architektúre
September 2024
Kód
- masívne refaktorovanie a prerobenie architektúry solvera
- trieda HybridSolver prerobená na všeobecný AlgorithmSolver využívajúci rozhrania TreeBuilder a NodeProcessor
Október 2024
Kód
- implementácia algoritmov Rc-Tree a RCT-MXP
- adaptácia MXP algoritmu do novej architektúry
November 2024
Kód
- oprava nedostatkov v Rc-Tree
- implementácia merania pokročilých štatistík
December 2024
Kód
- návrh systému na meranie používanej pamäte
Písanie
- prvé 3 kapitoly diplomovej práce
- príprava prezentácie na Projektový seminár
Literatúra
- S. Rudolph. Foundations of description logics.
- C. Elsenbroich, O. Kutz, and U. Sattler. A case for abductive reasoning over ontologies.
- R. Greiner, B. A. Smith, and R. W. Wilkerson. A correction to the algorithm in Reiter’s theory of diagnosis.
- M. Homola, J. Pukancová, I. Balintová, and J. Boborová. Hybrid MHS-MXP Abox abduction solver: First empirical results.
- F. Wotawa. A variant of Reiter’s hitting-set algorithm.