|
|
Aproximace obtížných rozvrhovacích úloh
Lisý, Viliam ; Čepek, Ondřej (vedoucí práce) ; Vlach, Milan (oponent)
Tato práce zkoumá rozvrhování problémů typu "shop". Po zavedení notace a základních definic používaných v rozvrhování přinášíme přehled známých výsledků o výpočetní složitosti různých rozvrhovacích problémů typu "open shop", "flow shop" a "job shop". Později se soustředíme na "open shop" a hlavně na podtřídu této třídy problémů, která povoluje jenom dvě operace nenulové délky na úlohu. Ve standardní notaci je označovaná Om|mj = 2|Cmax. Mimo několik méně významných lemmat a pozorování přinášíme čtyři významné výsledky o této podtřídě. Prvním je pozorování, že každý rozvrh v této podtřídě lze transformovat na rozvrh stejné délky s jediným intervalem nečinnosti na každém stroji. Druhý je důkaz známé domněnky o takzvaných hustých rozvrzích pro tuto podtřídu. Třetí je modifikace známého hladového algoritmu, aby produkoval rozvrhy ne více jak 1.5 krát delší než optimální délka, a poslední významný výsledek je modifikace známého polynomiálního schématu, která garantuje lepší vlastnosti na zmíněné podtřídě.
|
|
|
Using reinforcement learning to learn how to play text-based games
Zelinka, Mikuláš ; Kadlec, Rudolf (vedoucí práce) ; Lisý, Viliam (oponent)
Schopnost naučit se optimálnímu chování v prostředích, kde jsou stavy i akce vyjádřeny v přirozeném jazyce, by se dala aplikovat na řadu skutečných problémů, jako je optimalizace dialogových systémů. Pro tento učící problém jsou vhodnou doménou textové hry s větším počtem možných konců se zpětnou vazbou v podobně číselných ohodnocení. S její pomocí můžeme v tomto kontextu využít technik zpětnovazebního učení pro současné učení vhodné reprezentace textových dat a rozhodovacích pravidel. Představujeme model obecného agenta schopného hrát textové hry a zkoumáme jeho schopnost generalizace a přenosu získaných znalostí na nová prostředí. Rovněž demonstrujeme, že se agent dokáže naučit hrát více textových her najednou. Dále prezentujeme otevřenou knihovnu pyfiction, která sjednocuje přístup k různým textovým hrám a doufáme, že společně s agentem, který je její součástí, by v budoucnu mohla sloužit jako referenční rámec pro podobné úlohy.
|
|
|
Distributed Monte-Carlo Tree Search for Games with Team of Cooperative Agents
Filip, Ondřej ; Lisý, Viliam (vedoucí práce) ; Majerech, Vladan (oponent)
Cílem této práce je návrh, implementace a experimentální evaluace distribuovaných algoritmů pro plánování akcí týmu kooperujících autonomních agentů založených na Monte-Carlo tree search algoritmu. Jednotlivé algoritmy vyžadují rozdílné množství komunikace. V práci jsou shrnuty relevantní poznatky o Monte-Carlo tree search algoritmu, jeho paralelizaci a distribuovatelnosti a~algoritmech pro distribuovanou koordinaci autonomních agentů. Navržené algoritmy jsou testovány v prostředí zjednodušené hry Ms Pac-Man. Testována je síla jednotlivých algoritmů v závislosti na času výpočtu, množství komunikace a robustnosti vůči selhání komunikace. Jednotlivé algoritmy jsou dle těchto charakteristik porovnány. Powered by TCPDF (www.tcpdf.org)
|
|
|
Aproximace obtížných rozvrhovacích úloh
Lisý, Viliam ; Vlach, Milan (oponent) ; Čepek, Ondřej (vedoucí práce)
Tato práce zkoumá rozvrhování problémů typu "shop". Po zavedení notace a základních definic používaných v rozvrhování přinášíme přehled známých výsledků o výpočetní složitosti různých rozvrhovacích problémů typu "open shop", "flow shop" a "job shop". Později se soustředíme na "open shop" a hlavně na podtřídu této třídy problémů, která povoluje jenom dvě operace nenulové délky na úlohu. Ve standardní notaci je označovaná Om|mj = 2|Cmax. Mimo několik méně významných lemmat a pozorování přinášíme čtyři významné výsledky o této podtřídě. Prvním je pozorování, že každý rozvrh v této podtřídě lze transformovat na rozvrh stejné délky s jediným intervalem nečinnosti na každém stroji. Druhý je důkaz známé domněnky o takzvaných hustých rozvrzích pro tuto podtřídu. Třetí je modifikace známého hladového algoritmu, aby produkoval rozvrhy ne více jak 1.5 krát delší než optimální délka, a poslední významný výsledek je modifikace známého polynomiálního schématu, která garantuje lepší vlastnosti na zmíněné podtřídě.
|
host ::
RSS.