|
|
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...
|
|
|
Visualization and verification of plans
Glinský, Radoslav ; Barták, Roman (vedoucí práce) ; Dvořák, Filip (oponent)
Názov: Vizualizácia a verifikácia plánov Autor: Radoslav Glinský Katedra: Katedra teoretickej informatiky a matematickej logiky Vedúci bakalárskej práce: Doc. RNDr. Roman Barták, Ph.D. Abstrakt: Analýza plánov je dôležitou sú as ou kompletných plánovacích systémov. Aby smeč ť umožnili užívate omľ orientovať sa aj vo vä ších plánoch, vytvorili sme program, ktorý pomáha s analýzou ač vizualizáciou plánov. Program sa volá VisPlan - Interactive Visualization and Verification of Plans. VisPlan je neoddelite nouľ sú as ouč ť bakalárskej práce, ke že prakticky implementuje jej vizualiza né aď č verifika né riešenia. VisPlan nachádza a zobrazuječ kauzálne väzby medzi akciami, identifikuje možné chyby v pláne (a tak overuje jeho korektnos ), zvýraz uje nájdenéť ň chyby v pláne a umož ujeň užívate om interaktívne modifikova plán, a teda opravi chyby v pláne alebo ho jednoducho vylepši .ľ ť ť ť K úľ ovč é slová: Plánovanie, Umelá inteligencia, PDDL, Verifikácia
|
|
|
Compiling Planning Problems
Toropila, Daniel ; Barták, Roman (vedoucí práce) ; Chrpa, Lukáš (oponent)
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.
|
|
|
Classical planning techniques
Sasák, Róbert ; Barták, Roman (vedoucí práce) ; Toropila, Daniel (oponent)
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.
|
|
|
Constraint satisfaction for HW/SW verification
Cigler, Luděk ; Barták, Roman (vedoucí práce) ; Vomlelová, Marta (oponent)
Programování s omezujícími podmínkami (CSP) je silným nástrojem pro modelování a řešení mnoha problémů v umělé inteligenci a operačním výzkumu. Verifikace HW a SW může využít CSP pro automatické vytváření testů. Hlavním požadavkem na CSP algorithmus (vzhledem ke generování testů) je rovnoměrné rozložení nalezených řešení. Studujeme několik stávajících algoritmů pro náhodné generování řešení klasických CSP problémů, a prezentujeme naše rozšíření těchto algoritmů na problémy s ohodnocenými podmínkami. Naše algoritmy testujeme na různých benchmarkových problémech.
|
|
|
Optimalizace projektových portfolií s časem a zdroji
Huml, Tomáš ; Barták, Roman (vedoucí práce) ; Vlach, Milan (oponent)
Název práce: Optimalizace projektových portfolií s časem a zdroji Autor: Bc. Tomáš Huml Katedra: Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: Doc. RNDr. Roman Barták, Ph.D Abstrakt: Tradiční optimalizace projektových portfolií uvažuje statické projekty nevyvíjející se v čase. Cílem je vybrat optimální podmnožinu projektů vzhledem k daným omezením (rozpočet atd.). Tato diplomová práce se zabývá projekty, které se v čase vyvíjejí. Takové projekty se typicky skládají z posloupnosti aktivit potřebujících pro svoji realizaci čas a zdroje (peníze, lidi atd.). Cílem optimalizace portfolia projektů je potom vybrat podmnožinu projektů vzhledem k daným časovým a zdrojovým omezením a zároveň optimalizovat danou objektivní funkci, jako je například zisk. Takový problém má velmi blízko k tzv. oversubscribed rozvrhovacím problémům, kde se vybírá a rozvrhuje nejvíce zisková množina objednávek. Právě rozvrhovací techniky proto budou sloužit jako hlavní zdroj inspirace v diplomové práci. V rámci této práce je navrženo několik modelovacích algoritmů pro výběr optimálního portfolia a zároveň je řada z nich implementovaná v přiloženém programu. Klíčová slova: optimalizace portfolia, celočíselné lineární programování (ILP), optimalizace workflow, vztahy mezi projekty
|
|
|
Monte Carlo Techniques in Planning
Trunda, Otakar ; Barták, Roman (vedoucí práce) ; Toropila, Daniel (oponent)
Algoritmus Monte Carlo Tree Search (MCTS) v nedávné době prokázal, že dokáže úspěšně řešit těžké problémy v oblasti optimalizace i v oblasti hraní her. Pomocí tohoto algoritmu byly vyřešeny i některé problémy, které dlouho vzdorovaly konvenčním technikám. V této práci zkoumáme možnosti aplikace MCTS v oblasti plánování a rozvrhování. Problém zkoumáme z teoretického pohledu a snažíme se identifikovat případné potíže při použití MCTS v této oblasti. Navrhujeme řešení těchto problémů pomocí úpravy algoritmu a pomocí předzpracování plánovací domény. Představujeme techniky které jsme pro tyto účely vyvinuli a integrujeme je do funkčního celku. Výsledný algoritmus specializujeme na konkrétní typ plánovacích problémů - plánování přepravy. Vzniklý plánovač experimentálně porovnáváme se současnými plánovacími systémy.
|
|
|
Modelling Planning Problems
Vodrážka, Jindřich ; Barták, Roman (vedoucí práce) ; Chrpa, Lukáš (oponent)
Téma předložené diplomové práce spadá do oblasti znalostního inženýrství v automatickém plánování. V poslední době je pro reprezentaci plánovacích problémů často využíván koncept stavových proměnných. V rámci této práce je tento koncept využit v novém formalismu pro modelování plánovacích domén. Na základě tohoto formalismu je postaven prototyp nástroje určeného pro modelování plánovacích domén a problémů. Možnosti tohoto nástroje jsou pak demonstrovány na ukázkovém příkladu klasické plánovací domény. Nástroj poskytuje možnost exportu do standartního jazyka pro modelování plánovacích domén. Tím umožňuje propojení s existujícími plánovacími systémy.
|
|
|
Combinatorial algorithms for online problems: Semi-online scheduling on related machines
Ebenlendr, Tomáš ; Sgall, Jiří (vedoucí práce) ; Barták, Roman (oponent) ; Epstein, Leah (oponent) ; Woeginger, Gerhard (oponent)
Mgr. Tomáš Ebenlendr Kombinatorické algoritmy se zaměřením na online problémy: Semi-online rozvrhování na strojích s různými rychlostmi Abstrakt disertační práce Hlavním výsledkem této práce je konstrukce optimálních algoritmů pro celou třídu rozvrhovacích problémů. Tato třída zahrnuje většinu zkoumaných semi-online vari- ant preemptivního rozvrhování na strojích s různými rychlostmi s cílem minimali- zovat délku rozvrhu. Takto zkonstruované algoritmy jsou deterministické, nicméně dosahují optimální kompetitivní poměr i mezi pravděpodobnostními algoritmy. Navíc jsou optimální i pro libovolnou pevnou kombinaci rychlostí strojů, proto lze naši konstrukci uplatnit i na veškeré dříve studované speciální případy. Ukážeme nový dolní odhad 2.112 pro obecné online rozvrhování. Deterministický horní odhad e ≈ 2.718 pak plyne z dřívější existence e-kompetitivního pravděpodob- nostního algoritmu. Zmíněnou konstrukci lze aplikovat ve všech semi-online variantách, které jsou založeny na znalosti o vstupní sekvenci. Ty lze chápat jako omezení množiny plat- ných vstupů. Tuto konstrukci pak použijeme ke studiu dříve zkoumaných omezení, čímž získáme nové odhady kompetitivního poměru. Jmenovitě zkoumáme známou sumu...
|
|
|
Dynamické temporální sítě
Zykán, Pavel ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent)
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í.
|
host ::
RSS.