|
|
Solving Boolean satisfiability problems
Balyo, Tomáš ; Surynek, Pavel (vedoucí práce) ; Barták, Roman (oponent)
V této práci studujeme možnosti rozkladu booleovských formulí do komponent souvislosti. Z tohoto důodu zavádíme nový pojem - komponentový strom. Popisujeme některé vlastnosti komponentových stromů a možnosti jejich aplikace. Navrhli jsme třídu rozhodovacích heuristik pro SAT řešič na základě komponentových stromů a experimentálně zkoumali jejich výkon na testovacích SAT problémech. Pro tento účel jsme implementovali vlastní řešič, který využívá nejmodernější algoritmy a techniky pro řešení booleovské splnitelnosti.
|
|
|
Constraint modelling
Haničinec, Tomáš ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent)
Constraint programming is one of the possible ways how to solve complicated combinatorial (and other) problems. We model a problem using variables representing real world objects and constraints representing various relations between the objects. However, there are often many possible ways how to model a problem. And what's more, the choice of a modeling strategy can a®ect the resulting efficiency dramatically. Unfortunately, there is no general recipe how to model problems e±ciently. Nevertheless there are still several modeling techniques, heuristics or advices that could improve the e±ciency of models. Some of these techniques are problem dependent, some can be applied only to a certain classes of problems but they still often help. This thesis is trying to give more or less complete list of the most important modeling techniques along with an explanation of why, how and for which classes of problems they work best and also with empirical results underlying the presented facts.
|
|
|
Plánování operací solárních panelů na ISS
Jelínek, Jan ; Barták, Roman (vedoucí práce) ; Vilím, Petr (oponent)
Práce se zabývá problémem plánování operací solárních panelů na Mezinárodní vesmírné stanici. Úkolem je nalézt vhodné orientace a módy pro deset kloubů, kterými jsou panely přichyceny ke stanici. Tyto orientace a módy musí splňovat různé podmínky a zároveň by měl výsledný rozvrh zohledňovat určité preference. Jde o úlohu vhodnou pro automatické plánování a rozvrhování, ale v oblasti pilotovaných vesmírných letů se nové technologie prosazují velmi pomalu. V práci proto bude analyzováno aktuální řešení tohoto problému a bude představen nový algoritmus, který by měl více využívat možností automatického plánování a rozvrhování. V kontrastu s původním hladovým algoritmem, navržený algoritmus nejprve nalezne libovolný rozvrh a poté se ho snaží zlepšovat optimalizováním jednotlivých částečných optimalizačních funkcí. Vzhledem k velikosti prohledávaného prostoru jsou hledání omezena časovým limitem. Powered by TCPDF (www.tcpdf.org)
|
|
|
Constraint satisfaction for inductive logic programming
Chovanec, Andrej ; Barták, Roman (vedoucí práce) ; Železný, Filip (oponent)
Induktívne logické programovanie je oblasť zaoberajúca sa vývojom klauzálnych teórií z pozorovaní, kde pre danú množinu príkladov a dodatočnú informáciu hľadáme hypotézu, ktorá pokrýva všetky pozitívne príklady a nepokrýva žiadny negatívny príklad. V tejto práci nadväzujeme na prácu skúmajúcu konzistenciu šablón a rozširujeme ju k riešeniu všobecnej konzistencie. Navrhujeme algoritmus DeMeR skladajúci sa z troch fáz, ktorý rozdelí pôvodný problém na viacero menších častí, následne ich vyrieši a tieto riešenia spojí do kompletného riešenia a nakoniec transformuje výsledok do kompaktnej výslednej hypotézy. Ďalej sa zameriavame na techniku hľadania riešení dekomponovaných častí a navrhujeme generuj-a-testuj metódu založenú na pravdepodobnostnom prístupe s pamäťou výpočtu. V práci analyzujeme jednotlivé komponenty navrhnutých algoritmov a demonštrujeme ich vplyv na dobu výpočtu a štruktúru výslednej hypotézy. Ukazuje sa, že prvá fáza algoritmu sa koncentruje na rýchle vyriešenie problému za cenu dlhšej štruktúry hypotézy, kým zvyšné dve fázy skracujú výsledok do prijateľnej podoby. Nakoniec naše výsledky porovnávame s existujúcimi systémami na príkladoch hľadania spoločných štruktúr v náhodných grafoch a ukazujeme, že nami prezentované techniky prekonávajú uvedené systémy.
|
|
|
Controlled Landing of an Autonomous Drone
Hraško, Andrej ; Barták, Roman (vedoucí práce) ; Obdržálek, David (oponent)
Cieľom tejto práce je vytvoriť a implementovať návrh najvhodnejšej metódy umožňujúcej autonómne pristátie kvadrikoptéry na pristávacej ploche s viditeľným obrazcom. V rámci práce je vytvorený rozbor venujúci sa nájdeniu najlepšieho obrazca určeného pre pristávaciu plochu a najspoľahlivejšieho spôsobu ako tento obrazec identifikovať v obraze prijatom z kamery kvadrikoptéry. Práca vysvetľuje rôzne spôsoby riadenia zariadení ako dynamických systémov a implementuje algoritmus pre navigáciu kvadrikoptéry na cieľ. Dosiahnuté výsledky sú overené zdokumentovanými experimentami. Powered by TCPDF (www.tcpdf.org)
|
|
|
Workforce Optimisation
Pacinda, Štefan ; Barták, Roman (vedoucí práce) ; Klusáček, Dalibor (oponent)
Název práce: Optimalizace pracovních sil Autor: Štefan Pacinda Katedra / Ústav: Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: doc. RNDr. Roman Barták Ph.D., KTIML Abstrakt: Optimalizace pracovních sil se zabývá udržováním produktivity pracovní síly například v nemocnicích, či dopravních společnostech. Zahrnuje problém rozhodování o nutnosti použití jednotlivých dovedností v každém okamžiku, stejně jako rozhodování o množství vyžadovaného personálu. Po těchto rozhodnutí následuje řešení problému alokování určitých zaměstnanců ke směnám za současného plnění požadavků na dovednosti ale i jiných omezení odvozených z na příklad právních regulací, odborových dohod a vlastních preferencí. Tato práce se zabývá optimalizací pracovních sil, tedy optimálním nasazením personálu na směny za účelem pokrytí požadavků na zdroje, které se mění v čase. V této práci je řešený problém detailně rozebrán, popsán a namodelován jako problém celočíselného programování. Jsou zde prezentovány detaily o implementaci a vyčerpávající analýza a experimenty s instancí problém z praxe za účelem prokázání naplnění cílů, které si práce klade. Klíčová slova: Rostering, Optimalizace pracovních sil, Rozvrhování směn
|
|
|
Constraint Programming in Planning
Surynek, Pavel ; Barták, Roman (vedoucí práce) ; Vojtáš, Peter (oponent) ; Štěpánková, Olga (oponent)
This thesis deals with planning problems and Boolean satisfiability problems that represent major challenges for artificial intelligence. Planning problems are stated as finding a sequence of actions that reaches certain goal. One of the most successful techniques for solving planning problems is a concept of plan- ning graphs and the related GraphPlan algorithm. In the thesis we identified a weak point of the original GraphPlan algorithm which is the search for actions that support certain goal. We proposed to model this problem as a constraint satisfaction problem and we solve it by maintaining arc-consistency. Several propagation variants for maintaining arc-consis- tency in the model are proposed. The model and its solving process were integrated into the general GraphPlan-based planning algorithm. The performed experimental evaluation showed improvements in order of magnitude in several measured characteristics (overall solving time, number of backtracks) compared to the standard version of the GraphPlan algorithm. Next we proposed a stronger consistency technique for pruning the search space during solving the problem of finding supports. It is called projection consistency and it is based on disentangling the structure of the problem formulation. If the problem of finding sup- porting actions is...
|
|
|
Filtering Algorithms for Tabular Constraints
Molnár, Martin ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent)
Předložená práce se zabývá implementací filtračních algoritmů hranové konzistence pro extenzivně definované podmínky. Zavádíme zde nový koncept binarizace pro rozkládání více-árních ad hoc podmínek na síť binárních podmínek. Je zde také rozpracována teorie pro dokázání správnosti této binarizace. V práci studujeme existující algoritmy z pohledu našeho konceptu binarizace a navrhujeme binarizace pro ad hoc podmínky definované vybranými běžnými způsoby. V práci také navrhujeme filtrační algoritmy pro dílčí podmínky. Složený propagátor pak používá tyto dílčí filtrační algoritmy pro propagaci přes více-ární podmínky. Konečně, navrhované postupy experimentálně ověřujeme na podmínkách generovaných plánovacími.
|
|
|
Interactive scheduling and visualisation
Skalický, Tomáš ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent)
Cílem této diplomové práce bylo navrhnout a implementovat grafický nástroj pro zobrazování a editaci rozvrhů, který by obsahoval funkci pro automatické opravení porušených podmínek v rozvrhu. Výsledná aplikace Gantt Viewer je integrována do projektu FlowOpt, jenž představuje komplexní řešení od modelování pracovních procesů, přes vytváření rozvrhů, až po jejich analýzu. Aplikace byla vyvíjena s důrazem na přívětivé uživatelské rozhraní a na výkonnost při práci s velkými daty. Díky integraci do FlowOpt projektu umožňuje zobrazit u rozvrhů informace o pracovních procesech. Gantt Viewer též obsahuje nástroj pro automatické opravení rozvrhů využívající Repair-DTP algoritmus, který je v této práci podrobně představen a demonstrován.
|
|
|
Constrained activity sequencing
Nguyen, Son Tung ; Barták, Roman (vedoucí práce) ; Čepek, Ondřej (oponent)
Mnoho rozvrhovacích problémů lze považovat za problémy s hledáním posloupností aktivit splňujících určité podmínky a omezení. Typickým příkladem je rozvrhování letů v leteckém průmyslu, kde úlohou je přiřazení segmentů letů a servisních aktivit k jednotlivým letadlům. Tato diplomová práce se zaměřuje na hledání takovýchto omezených posloupností aktivit. Cílem práce je navrhnout formální model problému, včetně přesné specifikace podmínek a účelové funkce, schopný najít (sub)optimální posloupnosti aktivit. Navrhovaný model je založen na technikách Programování s omezujícími podmínkami.
|
host ::
RSS.