|
|
Modelling and Solving Problems Using SAT Techniques
Balyo, Tomáš ; Barták, Roman (vedoucí práce) ; Železný, Filip (oponent) ; Biere, Armin (oponent)
Řešení problémů plánování prostřednictvím překladů do splnitelnosti (SAT) je jedním z nejúspěšnějších přístupů k automatickému plánování. V této práci popíšeme několik způsobů jak přeložit problém plánování reprezentovaný v SAS+ formalismu do SAT. Přezkoumáme a přizpůsobíme stávající kódování a také zavedeme nové vlastní způsoby kódování. Porovnáme jednotlivá kódování pomocí výpočtu horních odhadů na velikosti formulí, které produkují, a pomocí spuštění rozsáhlých experimentů na referenčních problémech z Mezinárodní plánovací soutěže 2011. V experimentální části také porovnáme své kódování s nejmodernejšími kódováními z plánovače Madagascar. Experimenty ukazují, že naše techniky dokažou překonat tato kódování. V předložené práci také řešíme speciální případ optimalizace plánů -- odstranění redundantních akcí. Odstranění všech redundantních akcí je NP- úplný problém. Prostudujeme existující polynomialní heuristické přístupy a navrhneme vlastní heuristický přístup, který dokaže eliminovat vyšší počet a dražší redundantní akce než stávající techniky. Také navrhneme způsob kódování problému redundance plánů do SAT, který nám za použití MaxSAT řešičů umožní optimálně vyřešit problém eliminace redundantních akcí. Naše experimenty provedené s plány od nejmodernejších satisficing plánovačů pro referenční problémy...
|
|
|
Resolution-based methods for linear temporal reasoning
Suda, Martin ; Barták, Roman (vedoucí práce) ; Hoffmann, Jörg (oponent) ; Biere, Armin (oponent)
Cílem této práce je prozkoumat potenciál metod založených na rezoluci pro uvažování s lineárním časem. To na abstraktní rovině znamená navrhnout nové algoritmy pro automatické uvažovaní o vlastnostech systémů, které se vyvíjí v čase. Konkrétně v této práci ukážeme, 1) jak adaptovat superpoziční metodu pro dokazování vět ve výrokové lineární temporální logice (LTL), 2) jak využít příbuznost mezi superpozicí a kalkulem CDCL z moderních SAT-solverů pro navržení nového LTL dokazovače, 3) jak tento specializovat pro problém dosažitelnosti a objevit tak blízkou souvislost s algoritmem Property Directed Reachability (PDR), v nedávné době vyvinutém pro model checking hardwarových obvodů, 4) jak dále vylepšit PDR novou technikou pro urychlení fáze propagace klauzulí, 5) jak PDR adaptovat pro problém automatického plánování tím, že se SAT-solver v algoritmu nahradí procedurou specifickou pro plánovací vstupy. Navržené myšlenky byly implementovány a práce obsahuje výsledky experimentů, které na reprezentativních množinách benchmarků prokazují jejich praktický potenciál. Náš systém LS4 se ukázal býti jedním z nejsilnějších veřejně dostupných LTL dokazovačů. Zmíněné vylepšení algoritmu PDR podstatně zvyšuje výkon naší implementace při verifikaci hardware v multi-property módu. Dá se předpokládat, že ostatní implementace...
|
|
|
Modelling and Solving Problems Using SAT Techniques
Balyo, Tomáš ; Barták, Roman (vedoucí práce) ; Železný, Filip (oponent) ; Biere, Armin (oponent)
Řešení problémů plánování prostřednictvím překladů do splnitelnosti (SAT) je jedním z nejúspěšnějších přístupů k automatickému plánování. V této práci popíšeme několik způsobů jak přeložit problém plánování reprezentovaný v SAS+ formalismu do SAT. Přezkoumáme a přizpůsobíme stávající kódování a také zavedeme nové vlastní způsoby kódování. Porovnáme jednotlivá kódování pomocí výpočtu horních odhadů na velikosti formulí, které produkují, a pomocí spuštění rozsáhlých experimentů na referenčních problémech z Mezinárodní plánovací soutěže 2011. V experimentální části také porovnáme své kódování s nejmodernejšími kódováními z plánovače Madagascar. Experimenty ukazují, že naše techniky dokažou překonat tato kódování. V předložené práci také řešíme speciální případ optimalizace plánů -- odstranění redundantních akcí. Odstranění všech redundantních akcí je NP- úplný problém. Prostudujeme existující polynomialní heuristické přístupy a navrhneme vlastní heuristický přístup, který dokaže eliminovat vyšší počet a dražší redundantní akce než stávající techniky. Také navrhneme způsob kódování problému redundance plánů do SAT, který nám za použití MaxSAT řešičů umožní optimálně vyřešit problém eliminace redundantních akcí. Naše experimenty provedené s plány od nejmodernejších satisficing plánovačů pro referenční problémy...
|
host ::
RSS.