|
|
Praktické příklady z umělé inteligence
Mařík, Matouš ; Švancara, Jiří (vedoucí práce) ; Zelinka, Mikuláš (oponent)
Práce popisuje praktické úlohy k přednášce z Umělé inteligence, jež mají za úkol seznámit studenty se základnějšími strukturami a algoritmy této oblasti informatiky: s racionálním agentem, s neinformovaným a informovaným prohledáváním, s herními algoritmy a s algoritmy pro splňování omezujících podmínek. Součástí je motivace pro tvorbu těchto úloh, jejich implementace a dokumentace.
|
|
|
Traffic - hra se simulací silniční sítě
Kripner, Matěj ; Ježek, Pavel (vedoucí práce) ; Švancara, Jiří (oponent)
Cílem této práce byla implementace mobilní hry Traffic, ve které hráč ovládá auto a projíždí herním světem po silniční síti. Její základní princip vychází z naší vize hry simulující řízení, která by obohatila nabídku již existujících her. Tato vize se ukázala jako příliš komplexní, a proto jsme z jejích funkcionalit vybrali pouze podmnožinu, přičemž jsme dbali na zachování rozšiřitelnosti směrem k původní vizi. Jako cílovou platformu jsme zvolili systém Android a jako implementační nástroj engine Unity spolu s jazykem C#. Ve výsledné hře je hráč v roli taxikáře, tj. převáží lidi na jimi určené destinace. Podle kvality jednotlivých jízd získává peníze a hodnocení. Při tom projíždí světem obsahujícím silnice, křižovatky, chodníky, budovy a chodce. Herní svět je připraven na modifikaci herním návrhářem, který ne nutně umí progra- movat. Návrhář silnicím a chodníkům přiřazuje libovolný tvar daný Bézierovou křivkou a silnice pak spojuje do křižovatek. Tvar křižovatek se automaticky určí z tvaru navazu- jících silnic. 1
|
|
|
Crustal Structure of the Bohemian Massif Based on Seismic Refraction Data
Hrubcová, Pavla ; Vavryčuk, Václav (vedoucí práce) ; Plomerová, Jaroslava (oponent) ; Švancara, Jan (oponent)
Český masív je jedním z největších souvisle vystupujících fragmentů původně rozsáhlého variského orogenu ve střední Evropě. Na základě současné koncepce deskové tektoniky je možné interpretovat Český masív jako heterogenní celek složený ze čtyř samostatných regionálních jednotek s rozdílným vývojem i tektonickým omezením vůči svému okolí. Ke studiu hlubinné stavby tohoto komplexu byla použita data z mezinárodních seismických reflexních a refrakčních experimentů CELEBRATION 2000, ALP 2002 a SUDETES 2003. Tato data byla interpetována pomocí seismické tomografie a modelována s využitím paprskových metod pro vlny typu P a S. K omezení mnohoznačnosti řešení bylo použito reflektivity, modelování tíhových účinků i interpretace s využitím dalších metod, zejména receiver function. Rozložení seismických rychlostí v kůře Českého masívu bylo studováno podél profilů i doplněno o azimutální, mimoprofilovou závislost. Výsledné rychlostní modely ukazují rozdílné mocnosti kůry i různé typy přechodu na hranici kůra-plášť, což umožňuje vymezit kontakt jednotlivých jednotek ve větších hloubkách. Rozložení rychlostí pak odráží geotektonický vývoj dílčích jednotek Českého masívu.
|
|
|
Hledání minimálních splňujících ohodnocení Booleovských formulí
Švancara, Jiří ; Balyo, Tomáš (vedoucí práce) ; Trunda, Otakar (oponent)
V této práci zkoumáme algoritmy a techniky pro řešení Booleovské splnitelnosti. Dále se zabýváme možnostmi jejich použití při řešení weighted short SAT, což je zobecnění problému splnitelnosti. Toto zobecnění požaduje nalézt splňující ohodnocení za použití minimálního součtu vah proměnných. K řešení tohoto problému zavádíme tři pravdivostní ohodnocení proměnných - True, False a Unassign. Ukážeme, že ne všechny algoritmy a techniky používané v moderních SAT solverech můžeme aplikovat v našem programu. Ty, které můžeme, převedeme tak, aby používali námi nadefinované pravdivostní ohodnocení. Různou kombinací takto převedených technik dostaneme několik verzí solveru, které mezi sebou na závěr porovnáme. Powered by TCPDF (www.tcpdf.org)
|
|
|
Multi-agent Path Finding
Švancara, Jiří ; Barták, Roman (vedoucí práce)
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.
|
|
|
Multi-agent picker routing problem
Krejčí, Jiří ; Barták, Roman (vedoucí práce) ; Švancara, Jiří (oponent)
Důležitou součástí skladových procesů je kompletace objednávek, což je proces sesbí- rávání produktů z místa skladování. V této práci uvažujeme uložení produktů pomocí strategie rozptýleného skladování, což znamená, že stejné produkty se ve skladu nachází na více místech. Obvyklá je situace, kdy více sběračů sesbírává produkty zároveň, při čemž může docházet k jejich vzájemnému blokování. To má za následek snížení efektivity tohoto procesu. Tato skutečnost ovšem není zohledněna většinou stávajících alrgoritmů pro návrh tras sběračů i přes to, že blokování má značný vliv na efektivitu komple- tace objednávek. Předmětem této bakalářské práce je řešit problematiku tras sběračů v multiagentním prostředí. Práce obsahuje shrnutí aktuálního stavu, ze kterého vychází prezentovaný multiagentní algoritmus pro sběrače. Algoritmus je založen na myšlence pri- oritního plánování. Výsledky empirického vyhodnocení indikují, že multiagentní přístup vede k efektivnějším cestám pro sběrače. 1
|
|
|
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
|
host ::
RSS.