|
|
Solving Boolean satisfiability problems
Balyo, Tomáš ; Barták, Roman (oponent) ; Surynek, Pavel (vedoucí práce)
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.
|
|
|
AI Planning with Time and Resource Constraints
Dvořák, Filip ; Chrpa, Lukáš (oponent) ; Barták, Roman (vedoucí práce)
Automatizované plánování hraje bezesporu klíčovou roli v mnoha oblastech lidského zájmu, kde složité a proměnlivé úlohy vyžadují efektivní řešení a omezení možných chyb. Další motivací pro výzkum plánování je zachycení výpočetních aspektů umělé inteligence, kde plánování je jedním z klíčových elementů coby uvažování nutné k jednání. Zavedení času a zdrojů do plánování je důležitým krokem pro modelování problémů z reálného světa, nicméně plánování je samo o sobě v obecném případě velmi těžké a zavedení času a zdrojů plánování dělá ještě těžším. V této práci prozkoumáme z teoretického hlediska aspekty plánování, uvažování o čase a uvažování o zdrojích. Na základě tohoto průzkumu navrhneme vlastní suboptimální a doménově nezávislý plánovací systém zaměřený na plánování, kde čas hraje hlavní roli, a zdroje jsou omezené. Navržený systém otestujeme na plánovacích problémech s časem a zdroji z mezinárodní plánovací soutěže roku 2008 a výsledky navrženého plánovacího systému porovnáme s výsledky plánovacích systémů, které se účastnili této soutěže.
|
|
|
Temporal networks
Vlk, Rudolf ; Čepek, Ondřej (oponent) ; Barták, Roman (vedoucí práce)
Integrace plánování rozvrhování vyžaduje hledání nových přístupů problému rozvrhování. Rozvrhovací systém musí být schopen poskytnout užitečné informace plánovači, aby se zabránilo vytvářní neuskutečnitelných plánů. Pro rozvrhování založené na splňování omezujících podmínek je možné de novat vlastní fi ltrační pravidla a tak zefektivnit řešící algoritmus. Pokud filtrační pravidla využívají informace sdělené plánovačem a rozvrhovacím systémem (např. precedenční a nebo temporální podmínky), výstup těchto pravidel je mozné poskytnout plánovači, který je může s výhodou využít. V této práci je navržena filtrační metoda, která využívá temporální vztahy mezi aktivitami alokovanými na jeden nebo více disjunktivních zdrojů. Práce také popisuje sadu propagačnch pravidel založených na kombinaci ruzných fi ltračních technik.
|
|
|
Dynamické temporální sítě
Zykán, Pavel ; Surynek, Pavel (oponent) ; Barták, Roman (vedoucí práce)
Tato práce se zabývá algoritmy pro práci s dynamickými temporálními sítěmi. Ve své první části se soustřed'uje zejména na udržování konzistence po cestě při restrikci i uvolnění některých podmínek v síti. Ve druhé části popisujeme problém hledání minimální změny existujícího přiřazení časových okamžiků uzlům v rámci dynamické posloupnosti sítí, provádíme jeho analýzu a navrhujeme přístup k jeho řešení. Tento problém zavádíme a řešíme na jednoduchých temporálních sítích - STN. Součástí práce je i experimentální měření rychlosti navrhovaného přístupu na množině parametrizované generovaných sítí.
|
|
|
Constraint solvers
Tuláček, Michal ; Surynek, Pavel (oponent) ; Barták, Roman (vedoucí práce)
Řešič omezujících podmínek je specializovaný software, určený k řešení problémů popsaných omezujícími podmínkami. Práce podává přehled řešičů a vybrané z nich testuje z pohledu uživatelské přístupnosti a rozsahu problémů, které lze modelovat.
|
|
|
Classical planning techniques
Sasák, Róbert ; Toropila, Daniel (oponent) ; Barták, Roman (vedoucí práce)
Klasické plánovanie sa zaoberá hľadaním postupností akcií, ktéré převádzajů počiatočný stav sveta na požadovaný konečný stav. Predložená práca pojednáva o dvoch metódach klasického plánovania: doprednom a spatnom plánovaní. Obe metódy sme implementovali formou softvérového prototypu využitím piatich prehladávaní: DFS, BFS, IDDFS, A*, WA*. Dalším rozšírením o viaceré heuristiky sme zíkali celkovo 26 plánovačov. Efektivitu plánovačov sme porovnali na niekol'kých doménach z medzinárodnej plánovaciej sut'aže. Žiaden z plánovačov nie je výrazne lepšie na všetkých doménach, ale vo všeobecnosti boli lepšie dopredné plánovače.
|
|
|
Learning for Classical Planning
Chrpa, Lukáš ; Barták, Roman (vedoucí práce) ; Železný, Filip (oponent) ; Berka, Petr (oponent)
This thesis is mainly about classical planning for artificial intelligence (AI). In planning, we deal with searching for a sequence of actions that changes the environment from a given initial state to a goal state. Planning problems in general are ones of the hardest problems not only in the area of AI, but in the whole computer science. Even though classical planning problems do not consider many aspects from the real world, their complexity reaches EXPSPACE-completeness. Nevertheless, there exist many planning systems (not only for classical planning) that were developed in the past, mainly thanks to the International Planning Competitions (IPC). Despite the current planning systems are very advanced, we have to boost these systems with additional knowledge provided by learning. In this thesis, we focused on developing learning techniques which produce additional knowledge from the training plans and transform it back into planning do mains and problems. We do not have to modify the planners. The contribution of this thesis is included in three areas. First, we provided theoretical background for plan analysis by investigating action dependencies or independencies. Second, we provided a method for generating macro-operators and removing unnecessary primitive operators. Experimental evaluation of this...
|
|
|
Learning for Classical Planning
Chrpa, Lukáš ; Barták, Roman (vedoucí práce)
This thesis is mainly about classical planning for articial intelligence (AI). In planning, we deal with searching for a sequence of actions that changes the environment from a given initial state to a goal state. Planning problems in general are ones of the hardest problems not only in the area of AI, but in the whole computer science. Even though classical planning problems do not consider many aspects from the real world, their complexity reaches EXPSPACE-completeness. Nevertheless, there exist many planning systems (not only for classical planning) that were developed in the past, mainly thanks to the International Planning Competitions (IPC). Despite the current planning systems are very advanced, we have to boost these systems with additional knowledge provided by learning. In this thesis, we focused on developing learning techniques which produce additional knowledge from the training plans and transform it back into planning domains and problems. We do not have to modify the planners. The contribution of this thesis is included in three areas. First, we provided theoretical background for plan analysis by investigating action dependencies or independencies. Second, we provided a method for generating macro-operators and removing unnecessary primitive operators. Experimental evaluation of this method...
|
|
|
Interactive Gantt Charts
Skalický, Tomáš ; Vojtáš, Peter (oponent) ; Barták, Roman (vedoucí práce)
Tato práce se zabývá problematikou interaktivního rozvrhování v Ganttových diagramech. Cílem práce je navrhnout a implementovat algoritmus, jež řeší nekonzistence v rozvrhu. Nejprve jsou rozebrány existující přístupy. Hlavním přínosem této práce je algoritmus, které řeší nekonzistence v rozvrhu. Je zde navržen a je zde také proveden důkaz jeho korektnosti a konečnosti. Následuje demonstrování jeho použitelnost. K tomuto účelu je použit program GanttViewer, jež je součástí práce. Na závěr je tento program podrobněji popsán.
|
|
|
Řešení příliš omezených problémů
Kasl, Tomáš ; Barták, Roman (vedoucí práce) ; Zlomek, Josef (oponent)
Hierarchie omezujících podmínek jsou jednou z metod řešení příliš omezených problémů, což jsou problémy splňování podmínek, ve kterých není možné splnit všechny podmínky. Hierarchie vzniknou rozšířením "plochých" omezujících podmínek o preference, které vyjadřují, jak důležité je splnění konkrétní podmínky.Většina existujících řešičů hierarchií se dá rozdělit mezi algoritmy lokální propagace, které jsou většinou limitovány na podmínky typu rovnost, a zjemňující algoritmy, které jsou neinkrementální a málo efektivní. Obecná teorie sítí podmínek spojuje oba přístupy, ale dosud neexistuje algoritmus , který by plně využil výhod této teorie. Tato práce navrhuje nový algoritmus,který by tuto teorii využil.
|
host ::
RSS.