|
|
Ořezávání grafu pro multiagentní plánování cest
Husár, Matej ; Švancara, Jiří (vedoucí práce) ; Ivanová, Marika (oponent)
V tejto práci sa zameriame na zrýchlenie celkového výpočtu optimálneho multiagentového plánovania ciest, ktoré je NP-ťažkým problémom, preto jeho riešenie budeme hľadať pomocou SAT riešiča. Na dosiahnutie tohto výsledku využijeme orezávanie grafu, ktoré spočíva v odstránení takých vrcholov z pôvodného grafu, ktoré agenti nemusia využiť, a preto predstavujú takéto vrcholy zbytočnú záťaž pre SAT riešič. Na riešenie tejto úlohy navrhneme tri algoritmy, pričom ich následne experimentálne porovnáme so základným bežným algoritmom. Na jednotlivých navrhovaných algoritmoch nás bude zaujímať ich celková rýchlosť výpočtu, ale taktiež aj optimalita nimi nájdeného výsledku. Ukážeme si, že jeden z navrhovaných algoritmov zachováva optimalitu a tiež prináša aj značné zrýchlenie vo výpočte na veľkých grafoch.
|
|
|
Plánování cest pro multi-robotické sklady
Tauchmanová, Klára ; Barták, Roman (vedoucí práce) ; Švancara, Jiří (oponent)
Práce se zabývá problémem hledání bezkolizních cest v automatizovaném skladu pro skupinu agentů, tzv. Multi-agent pickup and delivery (MAPD) problémem. Agentům ve skladu jsou kontinuálně zadávány nové úkoly, které vyžadují vyzvednout zboží na určeném místě a převézt ho na jiné místo v prostředí skladu. V práci je popsán hierarchický algo- ritmus na řešení MAPD problémů, který provádí plánování na dvou úrovních - globální a lokální. Algoritmus pracuje s prostředím skladu, které je ručně rozděleno na oblasti. Na globální úrovni dochází k zadávání úkolů volným agentům a následně k plánování posloupnosti oblastí, které agent při vykonávání úkolu navštíví. Úkol je zadán vždy nej- bližšímu volnému agentovi. Na lokální úrovni dochází k samotnému hledání bezkolizních cest v rámci jednotlivých oblastí, ke kterému se používají upravené Multi-agent path finding (MAPF) algoritmy. Navržený algoritmus byl otestován v simulovaném prostředí. Experimentálně jsme ukázali, že hierarchický algoritmus používající Conflict-based search (CBS) na lokální úrovni má menší runtime a nachází řešení s menším makespanem než algoritmus využívající redukci na SAT. Dále ukazujeme, že hierarchický přístup k řešení MAPD výrazně snižuje runtime algoritmu, zatímco nalezená řešení nejsou o mnoho horší než u nehierarchického přístupu. 1
|
|
|
Řešení multiagentního plánování cest pomocí inkrementálního SAT
Agh, Juraj ; Švancara, Jiří (vedoucí práce) ; Barták, Roman (oponent)
Inkrementálny SAT (z anglického slova satisfiability) je spôsob riešenia splniteľnosť booleovskej formule opakovane a to na základe učenie z predchodzích riešení. Zadanie MAPF (z anglického slova Multi agent path finding) je navrhnúť cesty pre množinu agentov v zdieľanom prostredí bez konfliktov medzi agentmi. Pri riešenie MAPF pomocou SAT solveru pokiaľ optimálne riešenie je požadované tak iterujeme volanie SAT solveru, pokaždý s upravenou formulou k dĺžku riešení. Toto nás vedie k použití Inkrementálneho SAT solveru. V tejto práci sa snažíme vyriešiť problémy ktoré nastanú pri použitý inkrementálneho SAT solveru na problém MAPF a to v niekoľkých krokoch. Najprv predstavíme prístupy k riešení MAPF pomocou prevodu na splniteľnosť booleovskej formule. Tieto pístupy modelujeme v jazyke C++, ktorý nám poskytuje jednoducho upraviteľný modely na vytváranie formule. V ďalšom kroku lepší model upravíme na riešenie MAPF pomocou inkrementálneho SAT solveru. Vtedy pri každej iterácií model nevytvorí novú formulu iba rozšírí už použitú formulu z predchádzajúceho iterácie. V poslednej časti práce porovnáme prístupy na riešenie prevodu z MAPF na Inkrementálny SAT solver.
|
|
|
Škálovatelná navigace vozidel na dynamických grafech
Polický, Adam ; Kratochvíl, Miroslav (vedoucí práce) ; Švancara, Jiří (oponent)
Algoritmy pro hledání nejkratších cest ve velkých grafech tvoří nezbytnou část mnoha moderních navigačních systémů. Tento problém je ale při navigaci vozidel komplikovaný dynamičností silniční sítě, především uzavírkami a změnami v provozu, což omezuje ap- likaci mnoha bězných optimalizací. Cílem této práce je navrhnout algoritmus pro hledání cest ve velkých grafech, který je škálovatelný a efektivní díky tomu, že minimalizuje počet navštívených, v paměti uložených objektů. Docílilo se toho iterativním zjednodušováním grafu do vrstevnaté aproximativní struktury a vyvinutím modifikované verze Dijkstrova algoritmu, která na ní umožnuje efektivní navigaci. Výsledky ukazují, že navrhovaný algoritmus prozkoumá 4× méně grafových objektů než A* a 14× méně než Dijkstra. Dosahuje tak lepšího výkonu na úkor o něco delších nalezených cest. Kromě toho je tato vrstevnatá struktura schopna přizpůsobit se změnám v původním grafu, což umožňuje algoritmu pracovat i na měnící se síti bez náročných přepočtů. 1
|
|
|
Virtuální sklad
Hájek, Břetislav ; Barták, Roman (vedoucí práce) ; Švancara, Jiří (oponent)
Práce se zabývá vizualizací skladu a s ním spojenými produkty, objednávkami a statis- tikami kolem jejich rozmístění. Dále umožňuje analýzu pohybu robotů, kteří objednávky zprostředkovávají. K reprezentaci skladu slouží datová struktura popsaná pomocí onto- logie definované v jazyce OWL. Formální popis skladu pomocí ontologií zatím neexistuje a práce má tak mimo jiné za cíl takový formální popis vytvořit. Sklad popsaný touto ontologií je pak možné snadno exportovat a využít v jiných programech, které s onto- logiemi pracují. Program také poskytuje možnost tuto strukturu dynamicky rozšiřovat a vizualizovat nově vzniklé kategorie objektů. Kromě použití již zabudovaných statistic- kých nástrojů program umožňuje snadné rozšíření o vlastní moduly, jejichž výstupy jsou pak automaticky vizualizovány. 1
|
|
|
Multi-agent Path Finding
Švancara, Jiří ; Barták, Roman (vedoucí práce) ; Koenig, Sven (oponent) ; Vokřínek, Jiří (oponent)
Zadáním multi-agentního hledání cest (MAPF z anglického multi-agent path finding) je nalézt nekonfliktní cesty pro neměnnou skupinu agentů, kteří se pohybují ve sdíleném prostředí. Každý z agentů je definován svojí výchozí a cílovou polohou. Tato běžná definice MAPF je velice jednoduchá a často nezohledňuje všechny parametry reálného světa, které je potřeba vyřešit, aby byl problém prakticky aplikovatelný. V této práci se snažíme tento nedostatek odstranit tím, že definici rozšíříme o několik parametrů. Toho dosáhneme v několika krocích. Nejprve představíme přístup k řešení MAPF pomocí převodu na splnitelnost Booleovských formulí. Tento přístup modelujeme v programovacím jazyce Picat, který nám poskytuje snadno upravitelný model, do kterého lze přidávat nové podmínky a omezení. Toho využijeme v dalším kroku, kdy upravíme původní zadání MAPF. Zaprvé povolíme, aby do sdíleného prostředí vstupovali noví agenti během exekuce již nalezeného plánu. Zadruhé relaxujeme požadavek na homogenitu sdíleného prostředí, které je běžně reprezentováno neohodnoceným grafem. V poslední části práce provedeme experimentální studii na skutečných robotech, abychom ověřili, že přidané atributy skutečně modelují situaci lépe než klasická definice.
|
|
|
3D sociální síť
Hruška, Lukáš ; Švancara, Jiří (vedoucí práce) ; Brom, Cyril (oponent)
Sociálních sítí existuje již velké množství a využíváme je každý den. Málo se jich ale pokusilo odpojit se od stereotypního vzhledu ve formě nekonečně dlouhé nástěnky obsahující příspěvky lidí o které se daný uživatel zajímá a možnosti soukromé komunikace pomocí chatu a případně i hovoru. Tato práce se však odehrává ve 3D prostoru, kde každý uživatel ovládá svou postavu pohybující se v místnosti mezi dalšími uživateli. Samotné 3D prostředí spolu s modulárním návrhem celé aplikaci dodává možnost rozšířitelnosti o různé aplikace, kdy se může jednat o libovolný objekt položený v místnosti, 2D aplikaci v prostředí menu, nebo aplikaci ovládající celou místnost. 1
|
|
|
Hledání koordinovaných cest pro skupinu robotů
Mestek, Jakub ; Barták, Roman (vedoucí práce) ; Švancara, Jiří (oponent)
Práce se zabývá hledáním nekolizních cest pro skupiny robotů z počátečních do cí- lových pozic (Multi-agent Path Finding - MAPF). Cílové pozice jsou zadány ve formě pouze množiny pozic pro každou skupinu robotů, není dáno konkrétní přiřazení robotů na cílové pozice. Jedná se tedy o skupinovou (team, colored) variantu MAPF. V rámci práce byla vytvořena aplikace umožňující zadat počáteční a cílovou konfiguraci robotů a nalézt co nejkratší nekolizní plány. Nalezené plány mohou být vizuálně odsimulovány a je možné z nich vygenerovat programy proveditelné na robotech Ozobot Evo. 1
|
|
|
Umělá inteligence pro deskovou hru dáma
Bělíček, David ; Švancara, Jiří (vedoucí práce) ; Hric, Jan (oponent)
Dáma je desková hra, která se v různých formách hraje po celém světě. Cílem této práce je teoreticky popsat a implementovat algoritmus umělé inteligence, která bude schopna hrát dámu. Vysvětlíme si co je to algoritmus Minimax, jak ho zefektivnit pomocí Alfa-Beta prořezávání a jeho verzi s omezenou hloubkou, která využívá heuristických ohodnocení. Uvedeme si dvě konkrétní heuristická ohodnocení, jak tyto ohodnocení nahradit neuronovou sítí a jak tyto sítě vyvíjet pomocí evolučních algoritmů. Nakonec uděláme několik experimentů, ve kterých otestujeme vytvořené heuristiky a sítě. Práce je zakončená turnajem, jenž rozhodne který z vyvinutých algoritmů je nejlepší.
|
|
|
Od abstraktních k proveditelným plánům
Wiesner, Robert ; Barták, Roman (vedoucí práce) ; Švancara, Jiří (oponent)
Tato práce se zabývá postprocesingem na plánech řešících problém hledání cesty pro více agentů. Účelem postprocesingu je převod plánů na takové, které mohou být snáze prováděny reálnými agenty. Jedná se o snižování plýtvání časem a zavádění robustnosti. Je v ní navrženo pět základních metod, později rozšířených na 10, jejichž prostřednictvím jsou MAPF plány převáděny na významně nižší úroveň abstrakce. Výsledky byly ověřeny na šedesáti plánech na šesti mapách generovaných programem MAPF Scenario. Některé výsledky byly ověřeny na robotech Ozobot Evo. Ukázalo se, že vhodným postprocesingem lze za relativně malou výpočetní cenu výrazně vylepšit kvalitu původních plánů z pohledu rychlosti i bezpečnosti. Zároveň se ukázalo, že jednotlivé navrhované algoritmy jsou užitečné pro různé účely a typy plánů.
|
host ::
RSS.