|
|
Monte Carlo Techniques in Planning
Trunda, Otakar ; Barták, Roman (vedoucí práce)
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.
|
|
|
Artificial Intelligence for Children of the Galaxy Computer Game
Šmejkal, Pavel ; Gemrot, Jakub (vedoucí práce) ; Trunda, Otakar (oponent)
Ačkoli je umělá inteligence (UI) dnes schopna úspěšně řešit mnoho klasických her, na poli počítačových strategických her UI oponenti stále velmi pozadu. V této práci řešíme problém soubojů ve strategických počítačových hrách tím, že adaptujeme existující přístupy: Portfolio greedy search (PGS) a Monte-Carlo tree search (MCTS). Dále také představujeme vylepšenou verzi MCTS, nazvanou MCTS considering hit points (MCTS_HP). Kvalita těchto metod je uvažována v kontextu nedávno vydané 4X strategické hry Children of the Galaxy. Pro tuto hru implementujeme simulátor soubojů a vyhodnocovací framework, ve kterém srovnáváme různé přístupy k UI. Ukazujeme, že pro malou až střední velikost souboje jsou MCTS metody lepší než PGS. Ve všech scénářích je MCTS_HP lepší nebo stejně dobré jako klasické MCTS díky lépe vedenému prohledávání. V malých bitvách dokonce MCTS_HP se 100 milisekundovým časovým limitem poráží klasické MCTS s dvousekundovým časovým limitem. Kombinací rychlého hladového prohledávání PGS pro velké bitvy a přesnějšího MCTS_HP pro menší bitvy je možné dosáhnou univerzálnějšího UI hráče.
|
|
|
Implementace heuristik pro rozvozní problém s časovými okny
Trunda, Otakar ; Pelikán, Jan (vedoucí práce) ; Holý, Vladimír (oponent)
Rozvozní problém s časovými okny patří mezi těžké optimalizační problémy. Přestože má tento typ problémů mnoho praktických aplikací, otázka jeho efektivního řešení stále není uspokojivě objasněná. Tato práce se zabývá studiem Rozvozních problémů s časovými okny a návrhem nových algoritmů pro jejich řešení. Jsou zde představené dvě heuristiky a několik navazujících algoritmů, které tyto heuristiky dále rozšiřují. Efektivita navržených postupů je experimentálně ověřena na sadě testovacích dat. Součástí práce je také vytvoření desktopové aplikace, která implementuje navržené algoritmy a poskytuje další funkcionalitu pro usnadnění řešení rozvozních problémů v praxi. Patří mezi ně například generátor pseudo-náhodných zadání problému, vizualizace řešení a podobně.
|
|
|
Logická hra založená na celulárním automatu
Škopková, Věra ; Trunda, Otakar (vedoucí práce) ; Chromý, Miloš (oponent)
Tato práce se zabývá využitím celulárního automatu pro vytvoření logické hry. Popisuje klady a zápory jednotlivých typů celulárních automatů a jejich potenciál pro použití v logické hře. Dále se věnuje podrobnému návrhu pravidel hry a tvorbě uživatelského rozhraní. Vytvořená hra podporuje jednorozměrné celulární automaty o dvou až deseti stavech a umí pracovat jak s klasickými, tak s totalistickými přechodovými funkcemi. Cílem hry je odhalit hodnoty buněk, které vygeneroval celulární automat, na základě pravidel přechodové funkce, která jsou hráči známa. Hra je velmi variabilní, nabízí uživateli herní i vizuální parametry, které lze měnit. Navíc hra poskytuje dva nástroje pro vytváření nových celulárních automatů. Prvním z nich je vizuální editor, ve kterém lze pohodlně vytvářet nové či upravovat stávající celulární automaty. Druhým je generátor, který je schopný nalézt pravidla a ohodnocení výchozí generace buněk, z nichž lze vygenerovat konkrétní obrazce.
|
|
|
Planning for Transportation Problems
Škopek, Ondrej ; Barták, Roman (vedoucí práce) ; Trunda, Otakar (oponent)
Obrovské množství zdrojů je každodenně zbytečně promarněno kvůli neefektivnímu plánování přepravy. Pomocí technik automatizovaného plánování navrhujeme několik plánovacích systémů pro efektivní řešení zjednodušených variant logistických problémů. V těchto problémech jsou balíky doručovány do různých cílů pomocí nákladních vozidel pohybujících se na orientovaném, nezáporně ohodnoceném grafu, který představuje silniční síť. Experimenty provedené na původních problémech z plánovacích soutěží ukazují, že naše přístupy dokáží zlepšit kvalitu řešení ve srovnání s plánovači nezávislými na plánovací doméně. V neposlední řadě jsme vyvinuli nástroj TransportEditor, vizualizátor a editor těchto problémů, který umožňuje efektivní analýzu problémů, konstrukci plánovačů a introspekci plánů. 1
|
|
|
Využití celulárních automatů pro kompresi dat
Polák, Marek ; Trunda, Otakar (vedoucí práce) ; Mráz, František (oponent)
V této práci se zabýváme možnostmi využití celulárních automatů pro bezeztrátovou kompresi dat. Popisujeme klasifikaci celulárních automatů a jejich dosavadní využití. Zkoumáme vlastnosti jednotlivých typů elementárních celulárních automatů (tzv. Wolframova pravidla), popisujeme jejich třídy ekvivalence, možnosti jak dopředné, tak i zpětné simulace, zkoumáme pravidla se zajímavým chováním. Stavy získané těmito pravidly hodnotíme z hlediska jejich uspořádanosti (např. poměr živých buněk či aproximace entropie). Implementujeme některé standardní kompresní algoritmy a porovnáváme je z hlediska využitelnosti pro nejlépe ohodnocené stavy. Aplikací získaných poznatků navrhujeme nový kompresní algoritmus, testujeme jej na textových a obrazových datech a výsledky srovnáváme s tradičními kompresními algoritmy. Powered by TCPDF (www.tcpdf.org)
|
|
|
Adaptation of behavior of non-dying agents
Satmári, István ; Trunda, Otakar (vedoucí práce) ; Holan, Tomáš (oponent)
Predmetom bakalárskej práce je návrh a implementácia aplikácie umožňujúcej simuláciu jednoduchých neumierajúcich agentov na dvojrozmernej ploche, ktoré sú riadené svojím vlastným kódom. Rozhodovanie agentov je adaptívne. Aplikácia je zameraná na flexibilitu a umožňuje užívateľovi namodelovať veľké množstvo situácii a popísať veľa scenárov. Súčasťou práce je aj prevedenie s danou aplikáciou niekoľkých testov a popis ich výsledkov.
|
|
|
Rozvrhování úkolů v dobrovolnické organizaci
Žofák, Norbert ; Trunda, Otakar (vedoucí práce) ; Barták, Roman (oponent)
Předmětem této práce je analýza a implementace nástroje, který bude podporovat rozvrhování práce pro jednotlivé pracovníky na každý den v rámci každoroční týdenní dobrovolnické brigády. Rozvrhování probíhá poloautomaticky na základě nejrůznějších kritérií. Uživatelé nástroje vidí vždy aktuální stav výpočtu a mohou jej v průběhu ovlivňovat. Součástí práce je analýza výběru algoritmů použitých k rozvrhování a jejich následné srovnání na reálných datech. Nástroj bude zároveň evidovat všechny potřebné údaje o pracovnících, dostupných pracích, oblastech a autech. Důraz je dále kladen na jednoduchost a intuitivnost ovládání a zadávání dat.
|
|
|
Hledání minimálních splňujících ohodnocení Booleovských formulí
Švancara, Jiří ; Balyo, Tomáš (vedoucí práce) ; Trunda, Otakar (oponent)
V této práci zkoumáme algoritmy a techniky pro řešení Booleovské splnitelnosti. Dále se zabýváme možnostmi jejich použití při řešení weighted short SAT, což je zobecnění problému splnitelnosti. Toto zobecnění požaduje nalézt splňující ohodnocení za použití minimálního součtu vah proměnných. K řešení tohoto problému zavádíme tři pravdivostní ohodnocení proměnných - True, False a Unassign. Ukážeme, že ne všechny algoritmy a techniky používané v moderních SAT solverech můžeme aplikovat v našem programu. Ty, které můžeme, převedeme tak, aby používali námi nadefinované pravdivostní ohodnocení. Různou kombinací takto převedených technik dostaneme několik verzí solveru, které mezi sebou na závěr porovnáme. Powered by TCPDF (www.tcpdf.org)
|
|
|
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.
|
host ::
RSS.