prof. RNDr. Pavel Surynek, Ph.D.

V automatickém plánování je úkolem najít posloupnost akcí, které vedou ke splnění určitého cíle [1,2]. Plánování probíhá na abstraktní úrovni, kdy je plánovací prostředí, ve kterém se úloha odehrává, popsáno pomocí množin logických atomů. Akce postupně mění za splnění daných předpokladů prostředí pomocí množinových operací. Plánování pro robotické agenty představuje speciální případ plánování, kdy na rozdíl od obecného plánování, které v principu umožňuje akce měnící prostředí libovolně, je třeba uvažovat o topologii prostředí a vykonávání akcí jedním či více robotickými agenty. U robotických agentů přitom předpokládáme lokalizaci v rámci prostředí, tedy omezený dosah jejich efektorů, případnou nutnost přesunu na místo vykonání akce a obsazení prostoru jinými agenty [3,4]. Otevřenou otázkou je návrh centrálních algoritmů pro efektivní a robustní plánování uvažující jak jedno-robotický případ, tak více spolupracujících robotických agentů.

• [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] Ron Alterovitz, Sven Koenig, Maxim Likhachev: Robot Planning in the Real World: Research Challenges and Opportunities. AI Magazine 37(2): 76-84 (2016
• [4] Yawen Deng, Yiwen Hua, Nils Napp, Kirstin Petersen: A Compiler for Scalable Construction by the TERMES Robot Collective. Robotics Auton. Syst. 121 (2019)

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.

• [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

Plánování pohybu v robotice představuje jeden z klíčových kroků k realizaci abstraktního plánu zadaného jako posloupnost akcí prostřednictvím fyzického působení robota v prostředí [1,2]. Pohybový plán pro každý spojitý časový okamžik určuje prostorové nastavení jednotlivých částí a efektorů robota tzv. konfiguraci. Techniky plánování pohybu zpravidla pracují se spojitým mnoha-dimenzionálním prostorem všech možných konfigurací robota, kde nalezení plánu pro pohyb odpovídá nalezení spojité trajektorie v konfiguračním prostoru [1,3]. Výzvu představuje zejména případ, kdy je plánován pohyb více robotů s potenciálem k prostorové kolizi, jelikož s rostoucím počtem robotů prudce narůstá dimenze spojeného konfiguračního prostoru a tím obtížnost nalezení nekolidujících trajektorií [4]. Zajímavou otázkou je rovněž vykonávání pohybu skutečnými roboty a reakce na případné selhání vykonávání u jednoho či více robotů.

• [1] M. LaValle, S.: Planning Algorithms. Cambridge University Press, 2006
• [2] Malik Ghallab, Dana S. Nau, Paolo Traverso: Automated Planning and Acting. Cambridge University Press 2016, ISBN 978-1-107-03727-4
• [3] Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, 2005
• [4] Duong Le, Erion Plaku: Cooperative, Dynamics-based, and Abstraction-Guided Multi-robot Motion Planning. J. Artif. Intell. Res. 63: 361-390 (2018)

Výzkum v rámci tohoto tématu bude zaměřen na hledání řešení vybraných problémů v umělé inteligenci pomocí redukce na problém splnitelnosti [1]. Mezi problémy, které přestavují vhodné kandidáty pro tento způsob řešení, patří doménově závislé plánování (například hledání cest, plánování pro roboty) [2], rozvrhování, návrh obvodů, nebo kombinatorické úlohy. Pojem splnitelnost zde chápeme v širším smyslu, tj. nikoli pouze jako základní výrokovou splnitelnost (problém SAT), ale zahrnujeme i obecnější splňování podmínek (constraint satisfaction) [3], či kombinace splnitelnosti v různých logických teoriích (SAT-modulo theory – SMT) [4].

• [1] Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications 185, IOS Press 2009.
• [2] Pavel Surynek: Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems. Ann. Math. Artif. Intell. 81(3-4): pp. 329-375, 2017.
• [3] Francesca Rossi, Peter van Beek, Toby Walsh: Handbook of Constraint Programming. Foundations of Artificial Intelligence 2, Elsevier 2006.
• [4] Daniel Kroening, Ofer Strichman: Decision Procedures - An Algorithmic Point of View, Second Edition. Texts in Theoretical Computer Science. An EATCS Series, Springer 2016.

Cílem výzkumu je návrh nových konceptů a souvisejících řešících algoritmů pro multi-agentní hledání cest (Multi-Agent Path Finding) [1]. V základní variantě problému MAPF hledáme cesty pro agenty pohybující se po neorientovaném grafu tak, aby každý agent dorazil do svého cíle ze zadané počáteční pozice, a přitom se nesrazil s žádným jiným agentem. Současné řešící techniky pro MAPF zahrnují škálu metod od sub-optimálních polynomiálních algoritmů [2] přes optimální algoritmy založené na prohledávání stavového prostoru [3] po transformace do jiných formalismů jako je SAT [4]. Otevřené otázky nabízejí zejména zobecněné varianty problému MAPF, kde uvažujeme navíc například komplexnější vzájemné vyhýbání, udržování formací, souvislostí či jiných globálních vlastností (vlastnost, jež zahrnuje všechny agenty), zobecněné cenové funkce či více nezávislých (soupeřících) týmů agentů.

• [1] David Silver, “Cooperative pathfinding,” Proceedings of AIIDE, pp. 117–122, 2005.
• [2] Boris de Wilde, Adriaan ter Mors, Cees Witteveen: Push and Rotate: a Complete Multi-agent Pathfinding Algorithm. J. Artif. Intell. Res. 51: pp. 443-492, 2014.
• [3] Guni Sharon, Roni Stern, Meir Goldenberg, Ariel Felner: The increasing cost tree search for optimal multi-agent pathfinding. Artif. Intell. 195, pp. 470-495, 2013.
• [4] Pavel Surynek, Ariel Felner, Roni Stern, Eli Boyarski: Efficient SAT Approach to Multi-Agent Path Finding Under the Sum of Costs Objective. Proceedings of ECAI, pp. 810-818, 2016.

doc. RNDr. Pavel Surynek, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra softwarového inženýrství

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

RNDr. Kateřina Trlifajová, Ph.D.

Katedra aplikované matematiky

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é.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Karel Klouda, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

Ing. Daniel Vašata, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra aplikované matematiky

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í.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Dr. techn. Ing. Jan Legerský

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Mgr. Ladislava Smítková Janků, Ph.D.

Katedra aplikované matematiky

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.

prof. RNDr. Pavel Surynek, Ph.D.

Dr. techn. Ing. Jan Legerský

Katedra teoretické informatiky

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í.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Magda Friedjungová, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

MSc. Juan Pablo Maldonado Lopez, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

Mgr. Vojtěch Rybář

Katedra teoretické informatiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

doc. RNDr. Alena Šolcová, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Pavel Hrabák, Ph.D.

Katedra aplikované matematiky

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).

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

RNDr. Luděk Kleprlík, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Dr. techn. Ing. Jan Legerský

Katedra aplikované matematiky

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

RNDr. Luděk Kleprlík, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

Ing. Michal Valenta, Ph.D.

Katedra softwarového inženýrství

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

Ing. Pavel Hrabák, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Pavel Hrabák, Ph.D.

Katedra aplikované matematiky

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ů.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

Ing. Daniel Dombek, Ph.D.

Katedra aplikované matematiky

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ů.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

MSc. Juan Pablo Maldonado Lopez, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Josef Pavlíček, Ph.D.

Katedra softwarového inženýrství

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

Ing. Karel Klouda, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

RNDr. Luděk Kleprlík, Ph.D.

Katedra aplikované matematiky

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.

prof. RNDr. Pavel Surynek, Ph.D.

doc. RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Mgr. Ladislava Smítková Janků, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

RNDr. Luděk Kleprlík, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

RNDr. Luděk Kleprlík, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Daniel Vašata, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

doc. Ing. Mgr. Petr Klán, CSc.

Katedra softwarového inženýrství

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.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

doc. Ing. Jan Janoušek, Ph.D.

Katedra teoretické informatiky

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í.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Mgr. Jan Starý, Ph.D.

Katedra aplikované matematiky

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á.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

Ing. Karel Klouda, Ph.D.

Katedra aplikované matematiky

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ů.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Daniel Vašata, Ph.D.

Katedra aplikované matematiky

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í.

prof. RNDr. Pavel Surynek, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

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ů.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Miroslav Skrbek, Ph.D.

Katedra teoretické informatiky

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ů.

Práce na DSpace

prof. RNDr. Pavel Surynek, Ph.D.

Ing. Daniel Vašata, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

Ing. Tomáš Kalvoda, Ph.D.

Katedra aplikované matematiky

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.

Práce na DSpace