|
|
Algorithms for Multi-Agent Pickup-and-Delivery Problems
Šmíd, Petr ; Barták, Roman (vedoucí práce) ; Ivanová, Marika (oponent)
V rámci této práce zkoumáme algoritmy pro problémy multi-agentního vyzvednutí a doručení. Čtenáři představujeme základní definice společně s jednoduchými rozšířeními. Dále jsou důkladně popsány a analyzovány state-of-the-art algoritmy, které jsou otesto- vány v různých prostředích a na základě různých podmínek. V práci také popisujeme škálovatelnost algoritmů a demonstrujeme jí v několika scénářích. Práce zahrnuje krátké shrnutí vysvětlitelných plánů, motivaci za nimi a jejich implementaci. Podpůrný software byl vytvořen za účelem testování, vizualizace a vytváření vysvětlitelných plánů. 1
|
|
|
Konstrukce strategií pro multi-agentní hledání cest
Mestek, Jakub ; Barták, Roman (vedoucí práce) ; Švancara, Jiří (oponent)
Práce se zabývá problematikou hledání cest pro více agentů (multi-agent path fin- ding), kde je úkolem pro každého agenta najít cestu z aktuální lokace do destinace tak, aby nedošlo ke kolizím s jinými agenty. Práce je zaměřena na řešení tohoto problému v nedeterministickém prostředí a navrhuje nový přístup k řešení problému, a sice hledat řešení v podobě strategií, které agentovi říkají, jak se v dané situaci zachovat. 1
|
|
|
Autonomní křižovatka
Kotal, Jiří ; Barták, Roman (vedoucí práce) ; Švancara, Jiří (oponent)
Práce se zabývá problematikou průjezdů vozů plně automatizovanou křižovatkou a to z pohledu multi-agentního hledání cest (MAPF, multi-agent path finding). Cílem je pro- zkoumat různé abstrakce křižovatky a různé přístupy pro hledání nekolizního průjezdu křižovatkou. Zkoumané techniky jsou implementovány a empiricky porovnány v simulo- vaném prostředí. 1
|
|
|
Reduction-based Solvers for Multi-agent Pathfinding: Comparing Different Models
Ramesh, Samyuktha ; Švancara, Jiří (vedoucí práce) ; Barták, Roman (oponent)
- Samyuktha Ramesh Thesis Title: Reduction-based Solvers for Multi-agent Pathfinding: Comparing Different Models Multi-agent path finding (MAPF) is the problem of navigating a set of agents from their starting position to their respective goal position without any collisions. In this thesis, we provide an overview of the current approaches to solving MAPF. We implement six different encodings found in the literature using the Python programming language and the Glucose3 SAT solver. We run experiments on maps of different types and sizes to compare the performances of the encodings.
|
|
|
Heuristic Learning for Domain-independent Planning
Trunda, Otakar ; Barták, Roman (vedoucí práce) ; Onaindia, Eva (oponent) ; Komenda, Antonín (oponent)
Automatizované plánování se zabývá hledáním posloupnosti akcí, které vedou k dosažení cílového stavu ze zadaného počátečního stavu, např. řešení Rubikovy kostky, doručování balíků atd. Moderní plánovací techniky jsou založené na informovaném dopředném prohledávání řízeném heuristikou, kde heuristika poskytuje odhad vzdálenosti daného stavu od cílového stavu. V této práci představujeme techniky pro automatické vytvoření efektivní heuristiky pro jakoukoli zadanou plánovací doménu. Navržené řešení je založené na trénování hluboké neuronové sítě s využitím dříve vyřešených plánovacích problémů ze stejné domény. Navrhli jsme nový způsob extrakce příznaků pro stavy plánovacích problémů, která není závislá na využití existujících heuristik. Natrénovanou síť je možné využít jako heuristiku při řešení jakéhokoli problému z dané domény bez ohledu na velikost problému. Experimenty ukazují, že navržená technika je kompetitivní s populární doménově nezávislou heuristikou. Představujeme také teoretický rámec pro formální analýzu vlastností naučených heuristik. Formulujeme a dokazujeme věty, které stanovují meze na výkonnost naučených heuristik v nejhorším případě.
|
|
|
Osobní rozvrhování
Doležal, Lukáš ; Barták, Roman (vedoucí práce) ; Duša, Vladimír (oponent)
Přes pokroky na poli umělé inteligence stále postrádáme široce dostupný nástroj pro automatizaci organizace osobního času. Jednou z překážek je velká individuálnost problému a z toho důvodu složité splnění všech očekávání uživatele. V této práci jsme se zaměřili na vytvoření nástroje, který by uživateli dokázal nabídnout pomoc při organizaci svého času. Navrhli jsme model popisující osobní aktivity uživatele s preferencemi a formulovali hledání rozvrhu osobních aktivit jako optimalizační problém. Nad modelem jsme implementovali algoritmus rozvrhující tyto aktivity. Při jeho návrhu jsme se zaměřili na umožnění rozvrhování aktivit s přesností na sekundy. S využitím uvedeného modelu a algoritmu jsme vytvořili prototyp kalendářové webové aplikace, který jsme navrhli s cílem přehledného zobrazení času uživatele a snadného vkládání aktivit pro automatickérozvržení. Jádrem webové aplikace je RESTful API umožňující implementaci aplikací pro různé platformy a zařízení. Powered by TCPDF (www.tcpdf.org)
|
|
|
Optimalizace portfolia
Huml, Tomáš ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent)
Cílem této práce je navržení algoritmu pro vybrání optimálního portfolia ze vstupních projektů, které jsou ohodnoceny z hlediska nákladů, zisku a jejich potenciálního rizika. Mezi těmito vstupními projekty mohou být nadefinovány různé vazby. Součástí práce je také přehled alternativních přístupů k tomuto tématu uvedených v jiných pracích. K práci je přiložen program implementující navrhovaný algoritmus. Výstupem výpočtu tohoto programu je portfolio, které dosahuje nejvyššího možného zisku a zároveň splňuje všechna vstupní omezení a dodržuje zadané vztahy mezi projekty. Program umožňuje porovnávat výsledná portfolia pomocí grafu a zároveň poskytuje i bližší informace o každém portfoliu zvlášť.
|
|
|
Workflow Modelling
Rovenský, Vladimír ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent)
Cílem diplomové práce bylo navrhnout a implementovat grafický editor umožňující modelování pracovních postupů (workflows) s důrazem na efektivitu práce, jednoduchost a použitelnost pro běžného uživatele. Výsledná aplikace je integrována do systému FlowOpt, ve kterém lze vytvořené pracovní postupy použít k řízení výrobních procesů v malých a středně velkých továrnách. Vlastní editor by měl sloužit mj. jako demonstrace použití modelu Nested TNA v reálném protředí. Součástí práce je funkční implementace vlastního editoru, navržení a implementace procedury pro automatickou verifikaci pracovních postupů a podpora standardního formátu XPDL (BPMN) pro ukládání pracovních postupů (import i export).
|
|
|
Solving Boolean satisfiability problems
Balyo, Tomáš ; Surynek, Pavel (vedoucí práce) ; Barták, Roman (oponent)
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.
|
|
|
Constraint modelling
Haničinec, Tomáš ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent)
Constraint programming is one of the possible ways how to solve complicated combinatorial (and other) problems. We model a problem using variables representing real world objects and constraints representing various relations between the objects. However, there are often many possible ways how to model a problem. And what's more, the choice of a modeling strategy can a®ect the resulting efficiency dramatically. Unfortunately, there is no general recipe how to model problems e±ciently. Nevertheless there are still several modeling techniques, heuristics or advices that could improve the e±ciency of models. Some of these techniques are problem dependent, some can be applied only to a certain classes of problems but they still often help. This thesis is trying to give more or less complete list of the most important modeling techniques along with an explanation of why, how and for which classes of problems they work best and also with empirical results underlying the presented facts.
|
host ::
RSS.