Dizertační práce
Líná kompilace pro klasické plánování
Školitel
Stupeň
Téma dizertační práce
Popis tématu
V automatickém plánování je úkolem najít posloupnost akcí, které po jejich vykonání vedou ke splnění určitého cíle [1, 2]. Speciálně se toto téma zaměřuje na kompilaci plánovací úlohy do jiného formalismu, jako je například splňování omezení (CSP) [3] nebo výroková splnitelnost (SAT) [4]. Potenciál představuje zejména líná kompilace, kdy je úloha zakódována do cílového formalismu neúplně a ke zpřesnění jejího zakódování dochází až ve spolupráci s řešičem pomocí generování protipříkladů. Technika líné kompilace byla úspěšně použita ve speciální doméně multi-agentního hledání cest [5]. Zobecnění líné kompilace pro klasické plánování je ovšem stále otevřenou otázkou.
Literatura
- [1] Malik Ghallab, Dana S. Nau, Paolo Traverso: Automated Planning and Acting. Cambridge University Press 2016, ISBN 978-1-107-03727-4
- [2] Malik Ghallab, Dana S. Nau, Paolo Traverso: Automated planning - theory and practice. Elsevier 2004, ISBN 978-1-55860-856-6, pp. I-XXVIII, 1-635
- [3] Rina Dechter: Constraint processing. Elsevier Morgan Kaufmann 2003, ISBN 978-1-55860-890-0
- [4] Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications 185, IOS Press 2009, ISBN 978-1-58603-929-5
- [5] Pavel Surynek: Unifying Search-based and Compilation-based Approaches to Multi-agent Path Finding through Satisfiability Modulo Theories. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 1916-1922, Macau, China, International Joint Conferences on Artificial Intelligence, 2019, ISBN (Online): 978-0-9992411-4-1
Multi-agentní hledání cest ve spojitých prostorech
Školitel
Stupeň
Téma dizertační práce
Popis tématu
Školitel-specialista: doc. Dipl.-Ing. Dr. techn. Stefan Ratschan
Multi-agentní hledání cest (MAPF) je problém výpočtu bezkolizních cest z daných výchozích pozic do cílových pozic pro sadu agentů [1,2]. Problém MAPF je motivován řadou reálných aplikací, agenty mohou například modelovat roboty pro přepravu zboží ve skladech. Tradiční řešení tohoto problému jsou založené na modelech, kde čas i prostor jsou diskrétní. Spojité modely by však byly realističtější. Současný stav poznání v této oblasti umožňuje agentům pohybovat se spojitě po lineárních trajektoriích [3,4]. Cílem této práce je přispět k obecnějším technikám, například umožnit agentům pohyb po nelineárních trajektoriích, nebo modelovat určité kinematické vlastnosti agentů, jako je zrychlení, či další vlastnosti, které se projevují ve spojitém modelu problému.
Literatura
- [1] David Silver: Cooperative Pathfinding. AIIDE 2005: 117-122
- [2] Ko-Hsin Cindy Wang, Adi Botea: MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees. J. Artif. Intell. Res. 42: 55-90 (2011)
- [3] Thayne T. Walker, Nathan R. Sturtevant, Ariel Felner: Extended Increasing Cost Tree Search for Non-Unit Cost Domains. IJCAI 2018: 534-540
- [4] Anton Andreychuk, Konstantin S. Yakovlev, Pavel Surynek, Dor Atzmon, Roni Stern: Multi-agent pathfinding with continuous time. Artif. Intell. 305: 103662 (2022)
Protipříklady řízené zpřesňování abstrakcí pro multi-robotické plánování
Školitel
Stupeň
Téma dizertační práce
Popis tématu
Protipříklady řízené zpřesňování abstrakcí (counterexample guided abstraction refinement – CEGAR) je úspěšná technika v ověřování modelů [1,2]. V rámci navrhovaného tématu je úkolem prozkoumat možnosti použití techniky CEGAR v plánování pro mnoho robotů [3,4]. Plánování s mnoha roboty nabízí velký prostor pro návrh abstrakcí problému, které přinášejí vhodná zjednodušení a umožňují řešícímu systému problém snadněji vyřešit, například lze některé roboty v problému ignorovat, ovšem za cenu nepřesností ve výsledném řešení. Návrh, vyhledání a ověření protipříkladů pro multi-robotický systém, pomocí nichž by bylo možné nepřesnosti v řešení eliminovat, představuje další zajímavou výzvu. Určitého pokroku bylo dosaženo v plánování cest pro mnoho robotů, kde zpřesnění abstrakce probíhalo vůči srážkám mezi roboty. Abstrakce pro plánování cest ale představují pouze speciální případ, přičemž v rámci tohoto tématu bychom chtěli návrh abstrakcí posunout dál směrem k obecnějším multi-robotickým systémům, kde je škála činností robotů širší. Zajímavým směrem je i obohacení techniky CEGAR abstrakcemi, které produkují nepřesnost v řešení, vůči kterým je multi-robotický systém robustní, a není tedy třeba provádět jejich zpřesnění.
Literatura
- [1] Edmund M. Clarke, Anubhav Gupta, Ofer Strichman: SAT-based counterexample-guided abstraction refinement. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 23(7): 1113-1123 (2004)
- [2] Anubhav Gupta, Edmund M. Clarke: Reconsidering CEGAR: Learning Good Abstractions without Refinement. ICCD 2005: 591-598
- [3] Teng Guo, Si Wei Feng, Jingjin Yu: Polynomial Time Near-Time-Optimal Multi-Robot Path Planning in Three Dimensions with Applications to Large-Scale UAV Coordination. IROS 2022: 10074-10080
- [4] Lydia E. Kavraki, Steven M. LaValle: Motion Planning. Springer Handbook of Robotics, 2nd Ed. 2016: 139-162
Bakalářské práce
Předpovídání výsledků hry Dota 2
Autor
Filip Beskyd
Rok
2018
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Karel Klouda, Ph.D.
Katedra
Anotace
Teoretická část této práce se zabývá stručným vysvětlením teorií rozhodovacího stromu a umělých neuronových sítí a vysvětlením základních faktorů které mají významný dopad na výsledek hry. Praktická část se zaměřuje na experimentování s parametry použitých technik strojového učení, rozšiřování vstupních dat o informace týkajících se složení hrdinů, porovnávání a vyhodnocení výkonu těchto rozšíření. Toto vše končí implementací experimentálního programu, který vytváří prediktivní ANN model. Tento model může být později použit pro predikci výsledku hry podle počáteční kompozice hrdinů v týmu.
Testovací instance pro multi-agentní hledání cest
Autor
Tomáš Vlk
Rok
2019
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
MSc. Juan Pablo Maldonado Lopez, Ph.D.
Katedra
Anotace
Multi-agentní hledání cest je důležitý problém se širokým a rozmanitým využitím. Avšak jeho algoritmy jsou většinou testované pouze na mřížkových grafech. Cílem této práce je toto vyřešit poskytnutím jiných typů grafů a také způsobu jak je generovat. Práce také obsahuje testování na vygenerovaných grafech a také výsledky a jejich analýzu.
Zpracování a úpravy výstupů automatické transkripce hudby
Autor
Zuzana Fílová
Rok
2019
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Daniel Dombek, Ph.D.
Katedra
Anotace
Předmětem této bakalářské práce je problematika automatické transkripce hudby (AMT). V teoretické části práce byly shrnuty základní informace o zmíněné problematice, byl zde představen aktuální stav řešení AMT a nastíněny problémy, se kterými se tato výzkumná oblast potýká. Dále byly popsány různé možnosti zhodnocení výsledků systémů AMT. Bylo zjištěno, že automatická transkripce hudby v současnosti nedosahuje uspokojivých výsledků. Výsledná reprezentace hudby (MIDI soubor nebo notový zápis) obsahuje mnoho chyb, které znemožňují praktické využití této technologie.
V praktické části práce proto byla provedena analýza nejčastějších chyb vznikajících při automatické transkripci vlnového zvukového záznamu do formátu MIDI. Na základě této analýzy byla navržena metoda pro automatické odstranění těchto chyb a úpravu získaného MIDI souboru. Cílem těchto úprav bylo vylepšení úspěšnosti systému automatické transkripce hudby. Úspěšnost navržené metody byla hodnocena pomocí F-míry a editační vzdálenosti hudebních řetězců.
Experimenty v závěrečné části práce ukázaly, že navržená metoda úprav zvětšuje podobnost výsledných notových záznamů s originálem a zásadním způsobem přispívá k lepší čitelnosti výsledných notových záznamů.
Vizuální analýza plánů pro multi-agentní hledání cest se spojitým časem (MAPF-R)
Autor
Evgenii Abdalov
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Josef Pavlíček, Ph.D.
Katedra
Anotace
Tato práce je věnována vytvořeni vizualizačniho nástroje za účelem zprostředkováni
vizuálni analýzy problému Multi-agentniho hledani cest v nepřetržitem čase
(MAPF-R). Popisuje problém MAPF-R, poté pokračuje popisem vývoje vi-
zualizačniho nástroje a ekonomickým hodnocenim jeho potenciálu využiti v logistické oblasti.
Plánování evakuace založené na lokálních technikách kooperativního hledání cest
Autor
Róbert Selvek
Rok
2019
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
MSc. Juan Pablo Maldonado Lopez, Ph.D.
Katedra
Anotace
V tejto práci sa venujeme otázke evakuácie z budov alebo priestranstiev z perspektívy algoritmov na kooperatívne hľadanie ciest. Definujeme problém na zvaný multi-agentná evakuácia, ktorý sa skladá z neorientovaného grafu, v ktorého vrcholoch sa nachádzajú agenti (napríklad ľudia, roboty alebo postavy v počítačovej hre). Vrcholy v grafe sú označené ako ohrozené alebo bezpečné a úlohou je naplánovať presun agentov z ohrozených do bezpečných vrcholov v čo najkratšom čase.
Existujú centralizované algoritmy založené na modelovaní tokov v sieťach, ktoré dokážu tento problém riešiť optimálne vzhľadom na rôzne ukazovatele. V reálnom svete sa však tieto algoritmy dajú aplikovať len problematicky, pretože skutoční agenti nie sú schopní nasledovať centrálne generovaný plán a musia reagovať na meniace sa situácie, ako napríklad nekooperujúcich agentov. Preto sme navrhli a implementovali algoritmus na plánovanie evakuácie založený na technikách lokálneho kooperatívneho hľadania ciest. Simulácie na viacerých realistických situáciách ukazujú, že riešenia generované týmto algoritmom majú kvalitu podobnú riešeniam z centralizovaných algoritmov.
Využití umělých neuronových sítí při řešení hlavolamu (N^2-1)
Autor
Vojtěch Cahlík
Rok
2020
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Daniel Vašata, Ph.D.
Katedra
Anotace
Práce se zaměřuje na využití umělých neuronových sítí při hledání řešení hlavolamu (N^2-1), která jsou blízká řešením optimálním. V první části práce je provedena analýza možností využití umělých neuronových sítí při řešení hlavolamu, a je zjištěno, že nejefektivnější je použít umělou neuronovou síť jako heuristiku pro algoritmy prohledávání stavového prostoru. Později se práce zaměřuje na natrénování několika heuristik založených na hlubokých umělých neuronových sítích, jejichž výkonnost je následně experimentálně změřena. Při využití heuristik spolu s algorithem A* jsou nalezená řešení nejčastěji optimální, a počet expandovaných stavů je výrazně nižší než při použití srovnatelných přípustných i nepřípustných heuristik.
Multi-agentní hledání cest pro připojené roboty
Autor
Martin Zukal
Rok
2020
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Pavel Hrabák, Ph.D.
Katedra
Anotace
Tato práce je zaměřená na porovnávání dvou různých algoritmů, které se zabývají řešením problému multi-agentního hledání cest pro připojené roboty. Do větší hloubky je zde rozpracován návrh algoritmu, který výše zmíněný problém převádí na problém boolovského problému splnitelnosti.
Řešení kolizí mezi geometrickými roboty ve spojitém prostoru
Autor
Yana Zabrodskaya
Rok
2020
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Katedra
Anotace
Tato práce se zabývá problémem vyhýbání se srážkám mezi roboty při hledání cesty. Zde je navržen algoritmus pro nalezení nejkratší cesty bez srážek pro dva roboty libovolného geometrického tvaru. Algoritmus je teoreticky a experimentálně vyhodnocen a je provedena analýza ekonomického dopadu využití autonomních robotů ve skladech a maloobchodech.
Simulace centralizovaných algoritmů pro multi-agentní hledání cest na skutečných robotech
Autor
Ján Chudý
Rok
2020
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
Mgr. Vojtěch Rybář
Katedra
Anotace
Simulace řešení multi-agentího hledání cest je nezbytná pro výzkum, ale také pro demonstrace v akademickém prostředí. Většinou se simulace pouze zobrazuje na obrazovce bez použití robotických agentů. Používají-li se roboty, obdrží posloupnost příkazů, které potřebují provést, nebo příkazy obdrží postupně, aby správně sledovaly své naplánované cesty. Tato práce navrhuje nový přístup k simulaci centralizovaných multi-agentných algoritmů pro hledání cest na fyzických agentech s názvem ESO-Nav. V tomhle přístupu agenti nejsou součástí plánovacího procesu, ani nemají o svých cestách žádné informace. Agenti mají jednoduché předdefinované chování v prostředí, v kterém navigují na základě jeho podnetů. Pro skupinu robotů Ozobot Evo byl implementován funkční prototyp simulátoru, který využívá tento nový přístup.
Adaptace algoritmu prohledávání s konflikty pro alternativní účelové funkce
Autor
Berker Katipoglu
Rok
2020
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Michal Valenta, Ph.D.
Katedra
Anotace
Hledání cesty pro více agentů (MAPF) je důležitým typem problému plánování v umělé inteligenci. Existuje mnoho aplikací MAPF a každá aplikace má své vlastní priority, což dává MAPF mnoho různých variací. S rostoucím zájmem vědců o toto téma byly vyvinuty nové algoritmy pro řešení různých variací MAPF v posledních letech. Konfliktní vyhledávání (CBS) je jedním z těchto algoritmů, který je v současné době nejmodernějším řešením řešení instancí MAPF pomocí objektivní funkce součtu nákladů. V tomto článku budeme diskutovat o tom, jak přizpůsobit CBS pro objektivní funkci značky makespan, emprické srovnání obtížnosti řešení instancí MAPF s CBS v rámci součtu nákladů a objektivních funkcí značky a způsoby, jak zlepšit chování CBS pomocí objektivní funkce značkypanpan. Experimentální výsledky ukazují, že řešení usnadňuje řešení než řešení součtu nákladů, a je možné upravit algoritmus pro objektivní funkci tak, aby se dosáhlo lepšího výkonu.
Kompilace algoritmů hledání cest pro skupinu malých mobilních robotů
Autor
Nestor Popov
Rok
2020
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
RNDr. Luděk Kleprlík, Ph.D.
Katedra
Anotace
V této práci autor zkoumá možnosti kompilace algoritmů multi-agentního hledání cest na skupině malých robotů - Ozobot Evo. Každý robot má zadané počáteční a cílové pozice na předem zadané fyzické mapě, která je reprezentací mřížkového grafu. Tito roboti se následně musí přemístit do svých cílových pozicí, přitom nesmí dojít ke kolizi mezi nimi. V práci je implementován framework pro roboty Ozobot Evo, který umožnuje vyplnit předem spočítané cesty pro agenty z algoritmů multi-agentního hledaní cest. Funkčnost tohoto frameworku je oveřená v různých experimentech.
Řízení mobilních agentů pomocí konečných automatů ve scénářích s protivníkem
Autor
Dominik Šmejkal
Rok
2020
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
RNDr. Kateřina Trlifajová, Ph.D.
Katedra
Anotace
V této práci se zabýváme možným využitím konečných automatů pro lokální řízení agentů soutěžících v dosažení cílových pozic proti jinému týmu agentů. Existuje několik algoritmů řešících tento problém, které jsou buďto centralizované, nebo předpokládají způsob komunikace mezi agenty.
Námi předkládaná metoda lokálního řízení agentů konečným automatem je distribuovaná a agenti své tahy plánují nezávisle na ostatních. Pro snížení množství kolizí mezi agenty používáme konečný automat, který agentům lokálně plánuje vždy další tah s předpokladem že se bude vyhybat překážkám. Parametry konečného automatu jsme naučili evolučním algoritmem a vytvořili úspěšnější řešení. Metoda v testech ukázala vysokou rychlost plánování i pro vyšší počty řízených agentů, ale proti týmům řízeným pomalejšími oddělenými algoritmy, jako například IADPP, nebyla velmi úspěšná. Naopak ve scénářích s protivníkem řízeným algoritmem A* byly týmy lokálně řízené konečným automatem vysoce účinné.
Udržování formací v multi-agentním hledání cest
Autor
Jan Lidák
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Dr. techn. Ing. Jan Legerský
Katedra
Anotace
Tato práce se zabývá řešením problému udržení formace při hledání cest pro množinu agentů v rovinném prostředí mřížkových grafů. Na začátku je představena základní problematika hledání cest, hledání cest pro více agentů a formací, spolu s vhodnými definicemi jež čtenáři umožní se lépe orientovat ve zbývajícím textu.
V praktické části byl navržen a implementován funkční algoritmus řešící tento problém spolu s vhodnou vizualizací v jazyce Python. Algoritmus podporuje pohyb ve formaci spolu s možností hodnotit odchylku formace na základě reálné vzdálenosti. Zabrání se tak tomu, aby se při překonání překážky formace rozdělila na dvě.
Výkon algoritmu byl prověřen za pomocí řady testovaných scénářů a formací. Data z tohoto testování jsou představena ve formě tabulek a grafů spolu s krátkou diskuzí nad výsledky daného testování.
Automatické generování hudby
Autor
Adam Beckert
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Magda Friedjungová, Ph.D.
Katedra
Anotace
Tato bakalářská práce se zabývá algoritmickým generováním hudby. Práce shrnuje aktuální řešení automatické kompozice a jejich výsledky. Jsou zde převážně zmíněné rozdíly mezi jednotlivými přístupy a jejich nevýhodami.~V další části jsou popsány prvky z hudební teorie, teorie jazyků a základy pravděpodobnosti. Ty jsou dále využity k vytvoření systému ke generování přechodu mezi dvěma skladbamy.
Praktická část definuje omezení na skladby použité pro generování. Skladby jsou definované ve formátu MIDI. Dále je práce rozdělena do dvou částí: analýzy skladeb a procesu generování. U analýzy je použito znalosti z teorie hudby pro reprezentaci a analýzy skladeb. Následně s použitím Markovových řetězců je vytvořen model, který slouží ke generování nové skladby.
Testování je následně provedeno se čtyřmi písní a vzniklé skladby jsou posouzeny dobrovolníkem za pomoci předem definovaných charakteristik.
Hierarchické řízení rojů při evakuaci
Autor
Kristýna Janovská
Rok
2022
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Pavel Hrabák, Ph.D.
Katedra
Anotace
V této práci se zabývám návrhem hierarchického systému koordinace agentů určeného pro simulaci evakuace. V práci rozeznávám dva typy agentů. Řídící agenti navzájem komunikují pomocí algoritmu konfliktového prohledávání a odvádějí své roje do bezpečné oblasti, zatímco agenti následníci následují svého řídícího agenta.
Představím několik modelů, které se liší jak chováním řídících agentů vůči svým rojům, tak chováním agentů následníků, co se týče pokusu o samostatnou evakuaci.
V práci provádím experimenty, jejichž výsledky ukáží, jak úspěšnost evakuace ovlivňují parametry chování agentů. Výsledky těchto experimentů poukáží na výhody komunikace mezi řídícími agenty, problémy, které mohou při evakuaci nastat a jejich závislost na nevhodném chování agentů.
Lokální koordinace a plánování pro robotický fotbal
Autor
Tomáš Valenta
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Karel Klouda, Ph.D.
Katedra
Anotace
Předmětem této práce je prozkoumání relevantních technik návrhu lokálního řízení agentů s možností aplikace v robotickém fotbale. Jako vnitřní mechanismus agentů jsou použity rozhodovací stromy a k jejich konstrukci je využit algoritmus ID3. Dále je vytvořen softwarový prototyp a z něho jsou sesbíraná relevantní data ze simulací jednoduchých situací. Nakonec jsou vytvoření agenti testováni v různých simulacích. Výsledky jsou poté srovnány s jinými přístupy.
Hierarchická koordinace multi-robotického konstrukčního týmu ve hře Minecraft
Autor
Vít Šprachta
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Katedra
Anotace
Minecraft je počítačová sandboxová hra, ve které se hráč ocitne ve světě z kostek a má volnou ruku nad tím co bude dělat. Zejména, co, kde a jak bude stavět.
Multi-agentní kolektivní robotická konstrukce je problém, kde se skupina robotů za úkol postavit trojrozměrnou strukturu z bloků. Roboti mohou jednotlivé bloky nosit, sbírat a pokládat. Vzhledem k tomu, že bloky bývají umístěné na mřížce, nabízí se hra Minecraft jako zajímavé simulační prostředí.
Tato práce nejprve projde teoretická východiska robotické kolektivní konstrukce, ze kterých vyjde při návrhu vlastního hierarchického multi-agentního systému. Při návrhu se bere v potaz občasná potřeba přistavit lešení k jinak nedostupným místům a zároveň se dbá na dobrou škálovatelnost na větší struktury o velikosti stovek tisíců bloků.
Výsledný systém se následně implementuje jako rozšíření (mod) do hry Minecraft a na experimentech se ukáže jeho schopnost stavit libovolné struktury spolu s velmi dobrou škálovatelností.
Lokální a systematické algoritmy pro řešení zobecněné varianty Sudoku
Autor
Marek Nevole
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Katedra
Anotace
Cílem této práce bylo aplikovat současné algoritmy systematického a lokálního prohledávání na zobecněné variantě hry Sudoku modelované jako problém splňování omezení. Otázkou bylo, který přístup bude dosahovat lepších výsle-dků. V první části představujeme formulaci problémů jako problémy splňování omezení, a také algoritmy řešící tyto problémy. V druhé části aplikujeme obecná a teoretická východiska na hru Sudoku. Poslední část obsahuje experimenty jednotlivých algoritmů a vzájemné srovnání společně s diskuzí výsledků. Experimenty ukázaly, že systematické algoritmy dokážou lepé řešit herní plochy, jejichž stavový prostor je menší nebo ho lze redukovat. Lokální algoritmy získávají výhodu v opačném případě, ale obecně vyžadují větší časový limit.
Spojité plánování pohybu pro autonomní vozy na křižovatkách
Autor
Ladislav Miklík
Rok
2022
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Pavel Hrabák, Ph.D.
Katedra
Anotace
Tato práce seznamuje čtenáře s problematikou spojitého plánování více entit na křižovatce a představuje vlastní metodu pro řešení této problematiky. Implementovaná metoda je založená na reprezentování proveditelných stavů autonomního vozidla pomocí stavové mřížky, diskretizaci vzniklého koordinačního prostoru a následné jeho prohledání pomocí A* algoritmu pro optimální cestu. Podařilo se dosáhnout propustnosti 2,93 aut za sekundu u optimálnějšího přístupu a 2,47 aut za sekundu při počítání v reálném čase (7,6ms pro výpočet).
Diskrétní simulace automobilové dopravy se spojitým časem
Autor
Patrik Schweika
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. RNDr. Tomáš Valla, Ph.D.
Katedra
Anotace
V práci se zabýváme návrhem a realizací simulátoru automobilové dopravy s diskrétním prostorem a spojitým časem, jehož hlavní využití předpokládáme pro porovnání algoritmů na plánování tras. V simulátoru implementujeme dva odlišné algoritmy pro plánovaní tras. Prvním je Dijkstrův algoritmus, který plánuje trasy podle nejkratších cest. A druhým je centralizovaný algoritmus založený na maximálním souběžném toku. Nakonec pomocí simulátoru provádíme experimenty na připravených testovacích scénářích, kde tyto algoritmy porovnáváme. Výsledky experimentů ukázali, že průchodnost silniční sítě je významné lepší pro tokový algoritmus. V příloze práce lze nalézt dokumentaci a uživatelskou příručku k simulátoru.
Multi-agentní hledání cest pro dynamické cíle v zobecnění hry Pac-man
Autor
Lukáš Kameník
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
RNDr. Luděk Kleprlík, Ph.D.
Katedra
Anotace
Tato bakalářská práce řeší problém multi-agentního hledání cest s pohyblivými cíli v zobecnění hry Pac-man. Cílem práce je navrhnout metodu pro plánování pohybu více Pac-manů, kteří pronásledují vystrašené duchy. U Pac-manů je třeba se vyhýbat srážkám. Práce se zaměřuje na způsoby, jak problém pohyblivých cílů efektivně řešit.
Pro vyřešení problému multi-agentního hledání cest s pohyblivými cíli byly použity algoritmy od Davida Silvera, jmenovitě Cooperative A*, Hierarchical Cooperative A* a Windowed Hierarchical Cooperative A*, a algoritmus Generalized Adaptive A* pro efektivní řešení podobných problémů hledání cest jedním agentem. S využitím těchto algoritmů byly v~této práci vytvořeny čtyři nové algoritmy, jmenovitě Cooperative Generalized Adaptive A* (CGAA*), Hierarchical Cooperative Generalized Adaptive A* (HCGAA*), Hierarchical+ Cooperative A* (H+CA*) a Hierarchical+ Cooperative Generalized Adaptive A* (H+CGAA*). Algoritmus Cooperative Generalized Adaptive A* dosahuje pravidelně nejlepších výsledků. Přínosem této práce je algoritmus, který může být efektivně použit i pro složitější problémy multi-agentního hledání cest.
Hledání disjunktních cest v nerovinném prostředí
Autor
Petr Michalíček
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
RNDr. Luděk Kleprlík, Ph.D.
Katedra
Anotace
Kooperativní hledání disjunktních cest je varianta problému multiagentního hledání cest, při kterém je zadán prostor a množina obsahující několik párů se startovní a cílovou pozicí z prostoru. Úkolem je nalézt vrcholově-disjunktní cesty ze startovní do cílové pozice pro každý z těchto párů. Při kooperativním hledání se agenti snaží spolupracovat, tedy každý má informace o pozicích ostatních a jejich společný cíl je, aby každý agent dosáhl cíle. V této práci je přestaveno několik nových algoritmů, vhodných pro řešení tohoto problému.
Populární a používané algoritmy CA*, HCA* a WHCA* byly upraveny tak, aby fungovaly pro hledání disjunktních cest na voxelové mřížce. Všechny 3 byly také zprovozněny na datové struktuře oktantový strom, a to přineslo v některých prostorech výrazné zrychlení. Dále byl vytvořen algoritmus Obstacle CA*, který dokáže sestavovat úspěšněji cesty v oblastech, kde se vyskytují úzké průchody. Nové metody MDCA* a MDWHCA* hledají cesty tak, aby mezi nimi byly co největší mezery a tím předcházelo kolizím.
Hledání cest a přiřazování cílů ve zobecnění hry Pacman
Autor
Petr Šindlář
Rok
2022
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Mgr. Ladislava Smítková Janků, Ph.D.
Katedra
Anotace
Tato bakalářská práce se zabývá tématikou multi-agentního hledání cest a dvěma rozšiřujícími úlohami -- přiřazováním a seřazováním cílů. Rešeršní část práce přibližuje tyto problémy a možnosti jejich řešení. Nastudované koncepty jsou aplikovány na zobecnění hry Pacman, ve kterém je libovolný počet Pacmanů a duchů. V práci je navržen a implementován algoritmus, který řeší instance tohoto zobecnění. K tomu jsou využity modifikace existujících algoritmů BFS, DFS, A* a CBS.
Kompilace multi-agentní kolektivní konstrukce ve hře Minecraft
Autor
Martin Rameš
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Dr. techn. Ing. Jan Legerský
Katedra
Anotace
Tato bakalářská práce zkoumá současné přístupy k přesným řešením problému multi-agentní kolektivní konstrukce, s důrazem na tří-rozměrné struktury, postavené agenty přenášejícími v mřížce bloky, za předpokladu přítomnosti gravitace. Zobecnění v současné době nejrychlejšího přesného modelu je navrženo, s použitím smíšeného celočíselného lineárního programování, k přizpůsobení se různému trvání kroků agentů. Uplatnění navrženého modelu je použito v kombinaci s řešičem k přesné optimalizaci stavebního plánování uživatelem navržených struktur. Výsledek je vizualizován v Minecraftu, za použití programu postaveného na Malmo API. Série experimetů je provedena na několika malých instancích, k naměření relativního snížení doby stavění vzhledem k jednokrokovým krokům agentů. Výsledky ukazují na výrazné snížení doby stavění při délkách kroků použitých pro vizualizaci v Minecraftu.
Lokalizace robotů při vykonávání plánů multi-agentního hledáního cest s OZOBOTy
Autor
Silvestr Láník
Rok
2021
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. RNDr. Alena Šolcová, Ph.D.
Katedra
Anotace
Ve své práci se zabývám vytvořenim lokalizačniho systému Ozobotů, během
prováděni simulace multi-agentniho hledáni cest. Hlavnim důvodem vzniku
této práce jsou občasné chyby při prováděni simulace, způsobené špatnou de-
tekci promitané trasy ze strany Ozobota. Ke sledováni a lokalizaci Ozobotů
použivám webovou kameru a známé poznatky z oblasti počitačového viděni.
Vytvořený lokalizačni systém dokáže v obraze detekovat oblast simulace a dále detekovat a sledovat Ozoboty, kteři se v ni pohybuji a navracet jejich po-
zice v této simulaci. Dle provedených měřeni má lokalizačni systém úspěšnost
97 % a v budoucnu se počitá s jeho využitim v komplexnějšim dohledovém
mechanismu, což povede k zpřesněni prováděni simulace.
Interaktivní prostředí pro vizualizaci a testování udržování formací v multi-agentním hledání cest
Autor
Jakub Votrubec
Rok
2023
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Jan Matoušek
Katedra
Anotace
V teoretické části práce se zabýváme seznámením čtenáře s problematikou udržování formací v multi-agentním prostředí a vysvětlením algoritmu použitého v praktické části. V praktické části poté navrhujeme a implementujeme interaktivní aplikaci pro vizualizaci a testování udržování formací v multi-agentním prostředí.
Zvolený problém jsme vyřešili vybudováním interaktivní aplikace v herním enginu Godot a postavením struktury pro konkrétní implementace algoritmů v jazyce C++. K testování používáme algoritmus pro udržování formací, kterému se věnujeme v literární rešerši.
Hlavním výsledkem je aplikace, která umožňuje uživatelsky přívětivý způsob využití algoritmu pro řešení uživatelem zadaných problémů, dále umožňuje problémy upravovat a zkoušet najít jejich optimální řešení.
Kompletní zdrojový kód a již zkompilovanou aplikaci připravenou na spuštění lze nalézt v přiloženém médiu.
Multi-agentní hledání cest s produkcí a konzumací agentů
Autor
Tomáš Holas
Rok
2022
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
RNDr. Luděk Kleprlík, Ph.D.
Katedra
Anotace
Obsahem této bakalářské práce je vytvoření řešiče pro ovládání více agentů, který počítá s~produkcí a~konzumací agentů. Řešič sestaví plán pro spojitý čas a tento plán je následně demonstrován pomocí robotů typu ozobot.
Multi-agentní hledání cest je problematické kvůli možným kolizím robotů. Kolize je potřeba vyřešit pro bezproblémový průchod robotů skladištěm, což způsobí zefektivnění celé logistiky skladu.
Plánování cest pro roboty v rekonfigurovatelném skladu
Autor
Vladislav Beneš
Rok
2023
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
RNDr. Luděk Kleprlík, Ph.D.
Katedra
Anotace
Tato práce se zabývá mutli-agentním vyhledáváním cest (MAPF) pro roboty ve skladu, ve kterém je umisťování položek, které roboti přemisťují, určováno skladovou anarchií. Ta spočíva v tom, že ve skladu nejsou dané pevná místa na ukládání položek, nýbrž tyto pozice jsou vybírány za běhu a mohou tak být určeny pro uskladnění položky nebo čistě jen pro pohyb robotů. Do větší hloubky tu je rozveden algoritmus SMTCBS, který použit pro řešení problému MAPF, a úvaha pro efektivní skladovou anarchii.
Navigace letky dronů v prostředí s překážkami
Autor
Erich Beneš
Rok
2023
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Miroslav Čepek, Ph.D.
Katedra
Anotace
Tato práce se zaměřuje na tvorbu systému pro převod existujících letových plánů na letovou
sekvenci dronů za pomoci algoritmů multiagentního hledání cest. V úvodu práce je definováno
multiagentní hledání cest a dva algoritmy pro řešení této problematiky, CBS a SMT-CBSR.
V práci je také představeno prostředí pro ovládání dronů Crazyflie 2.1, speciálně pak systém Loco
Positioning. Výstupem práce je pak balíček crazyflie_controller, který umožňuje jednoduchou
komunikaci s drony Crazyflie 2.1, převod plánů na letové sekvence, vyhodnocení jejich kvality
a vizualizaci letů. Tento balíček je následně otestován v prostředí s překážkami.
Vykonávání plánů pro automatický sklad
Autor
Filip Leško
Rok
2023
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Mgr. Ladislava Smítková Janků, Ph.D.
Katedra
Anotace
V této práci byl navržen zmenšený model automatizovaného skladu, na kterém je následně testováno provádění plánů. Plány provádí skupina robotů nazvaná Ozobot Evo. Při řešení tato práce vychází ze znalostí vykonáváním plánů pro multi-agetní hledání cest a algoritmů řešících problém skladu, které práce upravuje a rozšiřuje. Model podporuje jak ruční přidávání úloh, tak jejich generování pro lepší simulaci reálných skladů. Testy byly provedeny jak na upraveném algoritmu, který řeší instance skladu, tak na modelu skladu s robotmi. Během testování algoritmu bylo zjištěno, jak jednotlivé atributy skladu ovlivňují efektivitu řešení algoritmu. Experimenty s roboty porovnávají úspěšnost vykonávaní a následně je diskutováno, co ovlivňuje neúspěšnost provedení plánu.
Realizace dronového displeje pomocí dronů Crazyflie
Autor
Matouš Kulhan
Rok
2022
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Dr. techn. Ing. Jan Legerský
Katedra
Anotace
Tato bakalářská práce se zabývá realizací tzv. dronového (vzdušného) displeje pomocí roje mini-kvadrokoptér Crazyflie 2.1 a navazuje na diplomovou práci Ing. Ondřeje Marka, která se stejným tématem zabývala na teoretické úrovni. Dronový displej je vizuální efekt, kdy roj létajících světélkujících dronů vytváří 3D obraz. Cílem této práce je navrhnout způsob převedení zadání problému dronového displeje na příkazy zasílané jednotlivým dronům v roji tak, aby toto zadání plnily.
K řešení tohoto cíle je využito rozdělení problému na dvě fáze, a to plánování a konání. Ve fázi plánování je zadání dronového displeje převedeno na časový plán pro každý dron v roji. K tomu je využit koncept multi-agentního hledání cest (MAPF), konkrétně algoritmus CCBS. Fáze konání časový plán co nejpřesněji plní pomocí Python knihovny cflib, která slouží pro vzdálené ovládání dronů Crazyflie.
Výsledkem této práce jsou dva programy, každý z nich řeší jednu z výše zmíněných fází. Toto řešení bylo otestováno na reálných dronech v Laboratoři robotických agentů Fakulty informačních technologií ČVUT s využitím rozšíření LED-ring a polohovacího systému Loco.
Vizuální detekce a sledování objektu pomocí dronu Crazyflie
Autor
Artem Redchych
Rok
2023
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Miroslav Skrbek, Ph.D.
Katedra
Anotace
V literární rešerši této práce byly prozkoumány současné i starší metody pro vizuální detekci objektů, sledování a odhad vzdálenosti. Byly také popsány hlavní složky ekosystému Crazyflie. V části implementace byly zavedeny vybrané metody. Pro detekci objektů byl použit model MobileNetV2-SSD s FPNlite, pro sledování objektů byl použit Kalmanův filtr a pro odhad vzdálenosti pomocí jediné kamery. Detekce objektů dosáhla průměrné přesnosti 87 % a přesnosti sledování 74 %. Hlavním výsledkem této práce je průzkum možného využití metod detekce a sledování objektů pomocí dronu Crazyflie 2.1 a jeho modulů Loco Positioning a AI-deck. V přílohách práce lze nalézt klíčové komponenty a finální implementaci létajícího streameru.
Multi-agentní hledání cest s více cíli pomocí výrokové splnitelnosti
Autor
Štěpán Tupý
Rok
2023
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Mgr. Jan Starý, Ph.D.
Katedra
Anotace
Tato práce se zabývá hledáním optimálního řešení problému multi-agentního hledání cest s více cíli (MG-MAPF), který je zobecněním multi-agentního hledání cest (MAPF). Úkolem v problému MG-MAPF je nalezení nekonfliktní cesty pro každého agenta z jeho počátečního vrcholu, která pokrývá jemu přiřazenou množinu cílových vrcholů. Přibývá tedy problém volby pořadí, ve kterém agenti své cíle navštíví tak, aby nalezená množina cest byla celkově optimální. Současné algoritmy hledají optimální řešení MG-MAPF pomocí prohledávání stavového prostoru nebo redukcí problému na výrokovou splnitelnost. V této práci jsem implementoval existující algoritmus SMT-Hamiltonian-CBS (SMT-HCBS), který oba přístupy kombinuje. Při redukci MG-MAPF ale vzniká dlouhá booleovská formule a náročné hledání jejího platného ohodnocení snižuje efektivitu tohoto algoritmu. Uvedl jsem tedy dvě nové varianty kódování MG-MAPF do booleovské formule, které využívají méně klauzulí a tím snižují její délku. Redukovaná varianta kódování úspěšně zvýšila efektivitu SMT-HCBS, což se prokázalo při testování na grafech ve tvaru mřížek různé velikosti. SMT-HCBS používající redukované kódování byl na všech testovaných grafech výkonnější než jeho původní varianta.
Rozmisťování objektů pro 3D tisk jako problém s omezeními
Autor
Lukáš Pokorný
Rok
2024
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Jan Schmidt, Ph.D.
Katedra
Anotace
Tato práce se bude zabývat rozmístěním 3D objektů, které se redukují na 2D objekty pohledem ze shora, na tiskovou plochu 3D tiskárny, pomocí Problému s omezeními(CSP). To znamená představit možné řešení zpracování STL souboru na 2D objekt, který se dál bude používat pro řešiče OR-Tools a Gecode, pro které se představí formulace a následná implementace. Výsledky z obou řešičů se poté srovnají a následně se srovnají i použití samotných řešičů.
Multi-agentní hledání cest jako problém splňování omezení
Autor
Miroslav Fáč
Rok
2024
Typ
Bakalářská práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Jan Schmidt, Ph.D.
Katedra
Anotace
V této práci zkoumáme aplikaci formalismů Problému splnění omezení (CSP) na úlohu multi-agentního vyhledávání cest (MAPF), což je problém tradičně řešený metodami založenými na problému splnitelnosti booleovské formule (SAT). MAPF má zásadní význam v robotice a logistice, kde je koordinace více agentů nezbytná pro navigaci od startovních bodů k cílovým bodům bez konfliktů. Ačkoli jsou běžná řešení založená na SAT, CSP formalismy představují slibnou alternativu.
V úvodní části práce prezentujeme teoretický základ teorie grafů, obecných principů MAPF a podrobnosti CSP formalismů. To zahrnuje podrobné zkoumání algoritmů typicky používaných v CSP, různých heuristických technik a dalších relevantních metodologií. Poté představujeme, jak přistupovat k MAPF pomocí Programování s omezeními (CP), s důrazem na MiniZinc, jazyk navržený pro standardizaci praktik CP. V naší práci využíváme dva přední řešiče CP, Gecode a OR-Tools.
V experimentální části provádíme analýzu mezi Gecode a OR-Tools na různých scénářích. Výsledky experimentů ukazují, že zatímco Gecode obecně lépe funguje v čistě CSP problémech, OR-Tools exceluje v problémech optimalizace omezení (COP), což poskytuje cenné vhledy do silných a slabých stránek každého řešiče.
Diplomové práce
Centralizované plánování autonomní dopravy
Autor
Ondřej Pleticha
Rok
2020
Typ
Diplomová práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Karel Klouda, Ph.D.
Katedra
Anotace
Tato diplomová práce se zabývá problémem řízení autonomní dopravy ve městech. Je uvažována budoucnost, kde jsou všechna vozidla sdílená a dokáží přepravovat osoby či předměty sama bez řidiče. Zákazníci pouze vytváří požadavky o přepravu. Cílem práce je pro daný systém navrhnout a otestovat algoritmy, které by mohly být použity při řešení problému nalezení vhodných tras pro vozidla. Klíčové ukazatele jsou celková energetická náročnost systému a spokojenost zákazníků. Pro ověření výsledků algoritmů je vytvořena simulace, která ve zjednodušené verzi napodobuje dopravu a požadavky ve městě. Nejprve je definováno prostředí, které popisuje, jak by uvedený dopravní systém mohl fungovat. Pro řízení dopravy jsou uvažovány tři různé existující algoritmy, které se liší v rozdělování požadavků a plánování tras vozidel. Všechny tři algoritmy jsou upraveny a vylepšeny o možnost zpracovávat požadavky s různou prioritou. Testování je zaměřeno na schopnost algoritmů uspokojovat požadavky při různém poměru vozidel a úkolů. Dále je také zkoumáno, jak dlouho zákazníci za určitých podmínek čekají nebo jaké jsou požadavky na výpočetní výkon u jednotlivých algoritmů.
Volba parametrů řešiče SATu pomocí technik strojového učení
Autor
Filip Beskyd
Rok
2020
Typ
Diplomová práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Tomáš Kalvoda, Ph.D.
Katedra
Anotace
SAT řešiče jsou nezbytné nástroje pro mnohé oblasti počítačové vědy a průmyslu. Obsadily funkci univerzálního nástroje, který uživatelé používají k řešení problémů, jež by v opačném případě museli řešit ad-hoc, což by pravděpodobně nebylo zdaleka tak efektivní jako moderní SAT řešiče.
V posledních dvou a více dekádách spojených s výzkumem SAT řešičů bylo vytvořeno mnoho heuristik. Ty nejefektivnější z nich jsou dnes neodmyslitelnou součástí moderních SAT řešičů, což dále zlepšuje jejich efektivitu v porovnání s jejich předchůdci. Heuristiky mohou být, před samotným provedením prohledávacího procesu konkrétní SAT instance, laděny jedním nebo více numerickými parametry.
V této diplomové práci představuji nástroj, který za pomoci technik strojového učení předpovídá hodnoty těchto parametrů pro heuristiku z podkladové struktury SAT instance s cílem redukce výpočetního času.
Automatické plánování pro skladovou logistiku
Autor
Klára Dvořáková
Rok
2021
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Jan Janoušek, Ph.D.
Katedra
Anotace
Tato práce se zabývá automatickou skladovou logistikou. Práce se zaměřuje na pohyb robotů ve skladu tak, aby nedocházelo ke kolizím a roboti efektivně plnili své úkoly. Typickým úkolem je přesun položky z místa uskladnění na místo výdejní. Hlavním cílem práce je zanalyzovat a vyvinout modifikaci existujících metod se zaměřením na úkoly s různými prioritami. Literární rešerše se zabývá problémem hledání cest pro více agentů a popisem existujících algoritmů řešících tento problém. Praktická část práce navazuje analýzou a implementací vylepšení Windowed CBS algoritmu tak, aby efektivně zpracovával úkoly s různými prioritami. Závěrečná část práce je věnována experimentům na různých mapách s různým počtem agentů a analýze jejich výsledků. Výsledkem práce je softwarový prototyp Windowed Priority CBS, který přijímá úkoly s různými prioritami a tyto priority bere v potaz při jejich řešení.
Zobecnění hry Pac-man z hlediska tahových herních algoritmů
Autor
Kristián Kuľka
Rok
2022
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Mgr. Petr Klán, CSc.
Katedra
Anotace
Hra Pac-Man predstavuje zaujímavý problém z pohľadu umelej inteligencie, keďže predstavuje multi-agentný systém, ktorý si vyžaduje koordináciu agentov a dlhodobé plánovanie. Hru navyše komplikuje fakt, že jednotlivé akcie sú častokrát nevýrazné a nemajú signifikantný efekt na stav hry, čo sťažuje rozhodovanie a výber optimálneho ťahu.
V tejto práci zobecním hru Pac-Man z pohľadu ťahových hier, pričom uvažujem väčší počet agentov (duchov aj pacmanov). Predstavím jej základné problémy a zhrniem širšie spektrum prístupov z literatúry. Následne predstavím poupravené implementované metódy, ktoré vychádzali z algoritmu negamax, AlphaZero a z pôvodnej implementácie z roku 1980. Opíšem taktiež ich možné vylepšenia, ktoré môžu adresovať objavené problémy. Na vyhodnotenie, optimalizáciu parametrov a trénovanie týchto stratégií som implementoval obecný modul spoločne s vizualizačnou funkcionalitou, ktorý taktiež detailne opíšem. Prácu zakončím rozborom výsledkov na rôznorodých mapách.
DPLL(MAPF): Integrace řešiče SATu a multi-agetního hledání cest
Autor
Martin Čapek
Rok
2022
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Mgr. Jan Starý, Ph.D.
Katedra
Anotace
Multiagentní hledání cest (MAPF) se často kopiluje do výrokové splnitelnosti (SAT) a je dále vyřešeno existujícím SAT řešičem.
V této práci jsme přišli s novým kompilačním schématem DPLL(MAPF), který používá těsnou inegraci teorie MAPF a SAT řešiče. Vysvětlili jsme, že DPLL(MAPF) je dalším logickým krokem pro zlepšení řešičů MAPF používající líné kódování. Takovým řešičem je SMT-CBS, na který jsme se v této práci zaměřili.
Dále jsme navrhli novou stategii líného kódování - Eager chokepoints.
Impementovali jsme DPLL(MAPF) a podrobili testům. Vyšlo nám, že DPLL(MAPF) dokáže překonat SMT-CBS. Nakonec jme vyhodnotili strategii Eager chokepoints, která se ukázala jako nevhodná.
Učení lokálně řízených agentů ve Pac-Man
Autor
Petr Nešpůrek
Rok
2022
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Katedra
Anotace
Tato práce řeší možnosti, jak vytvořit agenta, který se naučí hrát hru Pacman. K tomu jsou využity dva přístupy. Prvním je kombinace genetického programování a zpětnovazebního učení. Druhým je využití neuronové sítě s pomocí trénovacích dat získaných simulací jiných agentů nebo manuálním hraním hry.
Práce zahrnuje vytvoření modelu hry Pac-man se zjednodušenými pravidly. Dále obsahuje implementaci aplikace, která umožňuje hraní hry a slouží jako rozhraní mezi herním modelem a agenty, a obsahuje pomocné funkce umožňující učení agentů.
Líná kompilace v klasickém plánování
Autor
Zuzana Fílová
Rok
2022
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Daniel Vašata, Ph.D.
Katedra
Anotace
Předmětem této diplomové práce je problematika líné kompilace v klasickém plánování. V teoretické části práce jsou nejprve shrnuty základní informace o klasickém plánování, definovány důležité pojmy klasické reprezentace plánovacích problémů a představeny základní algoritmy pro jejich řešení, zejména prohledávání plánovacího stavového prostoru a techniky využívající plánovací graf. Poslední sekce se věnuje převodu plánování na problém výrokové splnitelnosti (SAT).
Na základě zjištění z teoretické části byla navržena metoda pro línou kompilaci plánovacích problémů do SAT, při které na rozdíl od klasické kompilace dochází k postupnému vytváření a úpravám formule výrokové logiky. V rámci praktické části práce byl implementován plánovač využívající dvě varianty kompilace -- navrženou metodu pro línou kompilaci a kompilaci klasickou.
Plánovač byl testován na úlohách ze soutěže IPC (International Planning Competition). Experimenty se zaměřovaly na vyhodnocení úspěšnosti plánovače s línou kompilací a porovnání výsledků s plánovačem využívajícím klasický způsob kompilace. Celkem bylo využito 79 problémů různé obtížnosti ze čtyř domén, 63 z nich dokázal plánovač s línou kompilací vyřešit rychleji než plánovač s klasickou kompilací. Provedené experimenty poukázaly na výhody a možné nevýhody líné kompilace. Výsledky experimentů naznačují, že využití líné kompilace má potenciál ke zlepšení výkonu plánovače.
Dronový vzdušný displej
Autor
Ondřej Marek
Rok
2022
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Miroslav Skrbek, Ph.D.
Katedra
Anotace
Tato práce se zabývá vytvořením algoritmických podkladů pro tzv. dronový displej, kde jednotlivé pixely jsou tvořeny světélkujícími drony. Tyto drony mohou měnit jak barvu, tak polohu v prostoru. Cílem této práce je plánování pohybu dronů s ohledem na uživatelsky zvolená kritéria a požadovaný vizuální efekt.
K řešení problému byl přizpůsoben známý algoritmus CBS (Conflict Based Search) problému multi-agentního hledání cest. Část algoritmu, která řeší nalezení konfliktů, využívá toho, že prostor displeje je rozdělen na stejně velké krychle. Díky tomu algoritmus může zkontrolovat, zda různé drony svým objemem nevstoupily do stejné části displeje ve stejný časový okamžik. K hledání cest se využívá velmi upravený algoritmus A*. Hustotu propojení pixelů předepisuje zobecněné 2^k sousedství do prostoru. Drony se pohybují mezi pixely buď přímo nebo po trajektori definované pomocí interpolačních křivek v prostoru. Algoritmus také bere v úvahu maximální rychlost a akceleraci dronů i jejich momentum.
Výsledkem této práce je nový algoritmus zvaný CSPT_CBS (Continuous Spacetime Conflict Based Search) a simulační program, ve kterém je možné navolit umístění a barvy pixelů a následně shlédnout vizualizaci pohybu dronů.
Multi-agentní hledání cest se spojitým časem založené na celočíselném lineárním programování
Autor
Yana Zabrodskaya
Rok
2022
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Daniel Vašata, Ph.D.
Katedra
Anotace
Tato práce se zabývá problémem hledání nejkratší cesty pro několik robotů tak, aby se tito roboti nesrazili. Za účelem řešení výše uvedeného problému byl vyvinut algoritmus, který je založen na celočíselném lineárním programování s prvky líné kompilace. Následně je algoritmus experimentálně vyhodnocen.
Programování s omezeními v rozvrhování pro autoservis
Autor
Petr Švec
Rok
2023
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Daniel Vašata, Ph.D.
Katedra
Anotace
Tato diplomová práce se zabývá implementací systému pro rozvrhování dílenských prací v autoservisu. Práce analyzuje požadavky zákazníka podle kterých, s využitím programování s omezeními, definuje model. Na základě navrženého modelu jsem implementoval řešič pomocí knihovny choco. Řešič jsem ověřil na syntetických datech a datech motivovaných praxí. Na testovaných instancích jsem provedl měření různých vlastností generovaných řešení pro testovací instance.
Důraz byl kladen na univerzální použití s maximální možnou parametrizací pro potřeby jednotlivých klientů a integrací.
Simulace a vizualizace plánů pohybu pro stolní robotickou paži pomocí platforem ROS a Unity
Autor
Ján Chudý
Rok
2023
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Mgr. Ladislava Smítková Janků, Ph.D.
Katedra
Anotace
Robot Operating System (ROS) je nejpoužívanější framework pro vývoj robotických aplikací. Jako nadstavby ROSu existuje také několik nástrojů pro robotické simulace. Simulace robotů je nezbytnou součástí robotiky, díky čemuž je vývoj hardwaru a robotických aplikací rychleší, levnější a bezpečnější. Simulace mohou být také použity pro akademické demonstrace a výzkum před samotným vyvinutím fyzického robota. V poslední době začaly výzkumníky v oblasti robotiky oslovovat výkonné 3D vývojové platformy, jako je Unity. Tato práce vyvíjí backend pro ROS pro fakultně vyvinutou robotickou paži Real Robot One (RR1). Navržený backend umožnuje simulaci prototypu jeho digitalního dvojčete RR1 v Unity a Gazebo, běžně používaném simulátoru v ekosystému ROS. Protože jednou z primárních motivací pro robotickou paži RR1 je výzkum plánování pohybu více robotů, jsou oba simulační nástroje porovnávány s důrazem na simulaci více robotů jak z hlediska grafického výkonu, tak vzhledem k uživatelskému komfortu.
Hierarchické plánování pro real-time strategické hry
Autor
Lukáš Kameník
Rok
2023
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
Ing. Daniel Vašata, Ph.D.
Katedra
Anotace
Tato diplomová práce řeší hierarchické plánování pro real-time strategické hry. Cílem práce je vyzkoušet vhodnost aplikace HTN plánování pro počítačem řízeného hráče RTS hry tím, že bude HTN plánování použito ve hře Dune 2000.
V práci byly navrženy a implementovány dva mírně odlišné přístupy, pojmenované jako Resourced Based AI (RBAI) a Income Based AI (IBAI), modifikující původní umělou inteligenci jen do té míry, která je potřeba. První jmenovaný přístup modeluje fungování hry pro plánování přesněji. Druhý zmíněný testuje jednoduší přístup. Z experimentálního měření bylo zjištěno, že jsou oba přístupy funkční a ve většině případů poráží výchozí umělou inteligenci, ale nakonec se ukázalo HTN plánování zbytečně robustní a pracné pro zvolený přístup k vytvoření AI.
Multi-agentní hledání cest ve spojitém prostředí
Autor
Kristýna Janovská
Rok
2024
Typ
Diplomová práce
Vedoucí
prof. RNDr. Pavel Surynek, Ph.D.
Oponenti
RNDr. Jiří Vyskočil, Ph.D.
Katedra
Anotace
Tato práce je zaměřena na vývoj modelu pro bezkolizní multi-agentní hledání cest ve spojitém prostoru, kde se agenti pohybují po množinách hladkých křivek. Agenti mezi sebou komunikují za použití algoritmu Continuous Environment Conflict-Based Search (CE-CBS), který je v této práci navržen.
Jsou zde studovány různé parametry modelu a typy prostředí a nastavení agentů, aby bylo zjištěno, jak se agenti chovají v závislosti na náročnosti prostoru a jak se mění kvalita řešení. Výsledky těchto experimentů ukazují schopnost agentů pohybovat se po bezkolizních hladkých cestách, kdy zároveň optimalizují délky těchto cest.