|
|
Global Constraints in Scheduling
Vilím, Petr ; Barták, Roman (vedoucí práce) ; Rudová, Hana (oponent) ; Wolf, Armin (oponent)
In this place, I would like to say my best thanks to everyone who supported me in my work and helped me along my whole Ph.D. study. First of all I owe a major debt to my supervisor Doc. RNDr. Roman Barták, Ph.D. for his patient leading, collaboration, support and help; especially for guidingmy research to this topic, providing important information from CP field, helping me publish my papers and reviewing them (most of them several times). Next I want to thank to Doc. RNDr. Ondřej Čepek, Ph.D. I wrote with him and Roman Barták a paper to CP 2004 which was very successful. They both contributed to this success. I also wish to express my gratitude to the whole CP community. To anonymous reviewers for providing me valuable feedback, for pointing out flaws in my papers and helping me to fix them. To my mentors on CP conferences who gave me a lot of helpful advices concerning my research and this a Ph.D. Thesis. I'm also very thankful to all the people with whom I could discuss during several conferences - they often asked very good questions; and good questions are often one half of whole research. My special thanks belongs to Philippe Baptiste, Mats Carlsson, Narendra Jussien, Philippe Laborie, Francois Laburthe, Narendra Jussien, Claude Le Pape, Jean-Charles Régin, Jerome Rôgerie, Francesca Rossi and...
|
|
|
Compiling Planning Problems
Toropila, Daniel ; Chrpa, Lukáš (oponent) ; Barták, Roman (vedoucí práce)
Napriek tomu, že techniky splňovania podmienok (SP) sú častým spôsobom riešenia rozvrhovacích problémov, v plánovaní sa stále vyskytujú iba zriedka. Na riešenie plánovacích problémov bolo síce vyskúšaných niekol'ko rôznych spôsobov ich aplikácie, avšak žiaden nebol natol'ko úspešný ako napríklad plánovače založené na SAT, a teda žiadna z techník SP sa nestala dominantnou v obore plánovania. V tejto práci prezentujeme a zastávame názor, že existujúce modely klasických plánovacích problémov nevyužívajú potenciál techník SP naplno, na dôkaz čoho predkladáme návrh reformulácie týchto modelov, ktorý významou mierou prispieva k zvýšeniu výpočtovej efektivity pri riešení problémov plánovania.
|
|
|
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...
|
host ::
RSS.