Semestrální práce

Volba vlastního zadání SP

Zadání SP si můžete zvolit z již nabídnutých témat nebo si zvolit zadání zcela vlastní.

Volba vlastního zadání:

Zadání tématicky souvisí s obsahem předmětu BI-ZUM.
Vlastní zadání je nutné si nechat schválit cvičícím.

Doporučená zadání

Mickeyho klubík

Mickey, Minnie, Daisy, Donald, Goofy a Pluto si pořídili klubovničku (klubík). Cena klubíku byla 20 duhových kuliček, přičemž každý člen mohl přispět 1 až 8 kuličkami (kolik kdo si domyslíme). Členové se scházejí vždy v neděli odpoledne a přitom jeden z členů má podle výše svého podílu právo rozhodnout o zábavě, která se bude ten den provozovat. Naším úkolem je vytvořit rozvrh, kdo kdy bude určovat zábavu a přitom musíme respektovat řadu omezení.

Například chceme, aby na členy klubíku připadaly dny v roce rovnoměrně podle ročních období, tj. aby měl každý možnost vymýšlet zábavu na léto, na zimu atd.
Každý člen může vyjádřit preferenci dnů, kdy chce mít zábavu podle sebe, případně zda chce několik týdnů souvislých, a dny kdy se mu nechce nic vymýšlet.
Donald hodně zapomíná a často se opakuje, takže bychom nechtěli, aby měl možnost volit zábavu mockrát za sebou. Minnie je obětavá a pořád by chtěla něco vymýšlet, ale musíme se postarat, aby nevyhořela.

Bludišťáci

Máme bludiště (například mřížková mapa) a v něm jsou rozmístěni bludišťáci. K tomu máme skupinku robotů, kteří mají za úkol bludišťáky posbírat. Každý robot uveze jen jednoho bludišťáka. Pro zjednodušení můžeme ignorovat srážky mezi roboty. Někde na mapě je vyznačeno sběrné místo pro bludišťáky.

Je možno řešit různé varianty, například polohy bludišťáků jsou předem známé, nebo nikoli. Roboti sdílejí informace, nebo o objevených bludišťácích, nebo nikoli.
Chtěli bychom v co nejkratším čase posbírat co nejvíc bludišťáků. Ve sběru lze soutěžit s dalším týmem robotů.

Ztracený robot

Otázka lokalizace a mapování v robotice byla zmíněna jen velmi stručně, ale tato úloha ji objasní. Máme předem známé prostředí reprezentované mapou. Mapa může být dvourozměrná nebo pro zajímavost i trojrozměrná. Dvourozměrnou mapu si můžeme představovat jako mřížku z nějaké hry (viz. movingai.com). Máme robota, který mapu zná a má optické senzory, které jsou přesné, ale s omezeným dosahem. Robot tedy přesně vidí své okolí do určité vzdálenosti. Robota umístíme na nádně vybrané místo do prostředí, které zobrazuje zmíněná mapa.

Úkol pro robota a pro vás je se v prostředí podle mapy zorientovat, tedy určit místo na mapě, kde se robot nachází. Pochopitelně v prostředí nejsou žádné značky, robot se tedy musí orientovat podle "krajiny", kterou vidí, ovšem ta může bý velmi jednotvárná.
Představujme si robota v systému chodeb. Jako kritérium můžeme brát dobu, jak dlouho robotovi orientace trvá - čím kratší, tím lépe.

Neomylný šachista (či spíš dámista na malé šachovnici)

Budeme vytváře perfektní strategie pro malé hry. Perfektní strategie je taková, že hrajeme-li podle ní, tak ať soupeř dělá cokoli, vždy prohraje. Pro některé tahové hry existuje, například pro Dámu, když máme možnost táhnout první.

Vaším ukolem bude vybrat si nějaké tahové hry a u nich najít perfektní strategii. To není snadné pro hry v plné původní velikosti, takže se omezíme například na Dámu či Šachy na maličké šachovnici.
Předpokládáme, že hledání perfektní strategie bude probíhat automaticky, tj. bude hledána některým z probíraných algoritmů.
Vítáme další tahové hry, např. varianty Go na malém prostoru, různé netypické Šachy (zvláštní figurky) atd.

Dron 'Opatrník' v krápníkové jeskyni

Máme jednoho létajícho drona, který je velmi opatrný a nechce si rozbít vrtulky. Jeho úkol ovšem je proletět krápníkovou jeskyní s velkými a ostrými krápníky. Vymyslete a implementujte algoritmus pro plánování pohybu takového drona. Musíme předpokládat, že dron se pohybuje ve velmi členitém trojrozměrném prostředí, kde nikde nesmí narazit, či lépe se ani přiblížit k překážce. Senzorickou stránku úlohy zanedbáváme, dron prostředí dokonale zná a vždy přesně zná svoji polohu.

Jedná se o hledání bezpečné cesty pro drona, což není úplně libovolná cesta.
Můžeme uvažovat dvě kritéria, a sice pohybovat se po bezpečné cestě, ale zároveň dorazit do cíle co nejrychleji.

Karbaník s kamennou tváří

Ačkoli jsme hry s neúplnou informací a s neurčitostí neměli, základní intuice, jak se s tímto problémem vypořádat nám postačí. Budeme navrhovat UI pro hraní karetních her se sázkami, například Poker nebo jiné. Výhoda umělé inteligence je, že na sobě nenechá znát znepokojení, když jdou sázky nahoru a držené karty jsou slabé.

Navrhněte různé postupy pro hraní vybrané karetní hry se sázkami, postačí intuitivní postupy. Pokud se vám podaří integrovat nějakou techniku z přednášky, tak tím lépe.
Otestujte techniky při hře mezi sebou a zhodnoťte, co je pro úspěšné hraní rozhodující.

Pracovitý bobr

Předpokládáme, že posluchači kurzu o umělé inteligenci vědí, co je to Turingův stroj. V rámci úlohy budeme chtít vytvořit Turingův stroj, který je co nejmenší, ale bude pěkně pracovitý. Tedy poběží co nejdéle, ale nikoli věčně, nakonec zastaví. Tato úloha je obecně známá jako Busy Beaver.

Pomocí probíraných technik vytvořte takový Turingův stroj.
Je potřeba si dát určitá vstupní omezení na počet stavů a symbolů, přičemž doporučujeme pracovat s velmi malými číly, např.: 2, 3, 4.

Plánování pětiletky

Analogie předchozí úlohy ovšem ve světě klasického plánování. Pokuste se vytvořit klasický plánovací problém, který bude co nejmenší, co do délky zadání, tj. ve smyslu počtu konstant, počtu akcí, atd., ale bude generovat co nejdelší plány. Pochopitelně taková plánovací úloha je asi tak užitečná jako plánování pětiletky v plánované ekonomice, nicméně ukazuje složitost plánovací úlohy a limity plánovačů.

Popsané plánovací úlohy se můžete pokusit generovat a testovat automaticky.

Automatický ajťák

Mnoho zaměstnání kvůli rozmachu umělé inteligence zanikne a lidé se tak konečně budou moci věnovat tomu, co je baví (například hraní počítačových her). Pokuste se přispět k tomu, aby i ajťácká zaměstnání konečně zanikla a nahradila je UI a ajťáci se tak mohli naplno věnovat svým koníčkům. Pro zjednodušení budeme vymýšlet UI, která nahradí programátora pro jednoduché procesory, které mají řekněme tři registry AX, BX, a CX. Paměť bude označena polem Pam, přičemž Pam[i] znamená i-tá buňka paměti. Máme několik instrukcí: Load(buňka paměti Pam[i],registr), Save(registr,buňka paměti Pam[i]) s přirozeným významem uložení obsahu paměťové buňky do registru, resp. vložení obsahu registru do paměťové buňky. Dále máme nějaké operace s registy např.: Swap(registr1,registr2), která prohodí obsah registrů, vektorová Shift, která vezme všechy registry a provede rotaci resp. posun tj. obsah AX půjde do CX, obsah BX do AX, obsah CX do BX.

Sestavte program z uvedených instrukcí, který prohodí v paměti dva řetězce, jejichž pozice jsou předem známé. Tedy například na začátku je obsah paměti: "Pavel zjistil, že Petr neumí UI, a proto ho vyhodil od zkoušky.", po provedení programu chceme v paměti mít: "Petr zjistil, že Pavel neumí UI, a proto ho vyhodil od zkoušky."
Program nechceme sestavovat ručně, chceme jej sestavit automaticky. Použijte tedy některou z probíraných technik k této automatizaci.
Jednoduchý procesor můžete různě zobecňovat, přidávat instrukce, registry atd. Zjistete, kde jsou limity podobné automatizace programování a zda je možné současnými technikami ajťáky skutečně nahradit.

MAPF (čti "mep ef")

Multi-agentní hledání cest (Multi-agent path finding - MAPF) je klasická plánovací úloha v umělé inteligenci. Je dán neorientovaný graf. Ve vrcholech grafu jsou agenti tak, že ve vrcholu je vždy nejvýše jeden a úkolem je najít nekolidující cesty, pomocí kterých se agenti dostanou ze svých počítečních vrcholů do zadaných cílových. Každý agent má svůj unikátní cílový vrchol.

V úloze se tradičně hovoří o agentech, ale nejsou to agenti ve smyslu v jakém jsme je probírali. Zde nemají žádnou vnitřní inteligenci, vše je řešeno centrálně z vnějšího pohledu. Dříve se výstižněji úloha jmenovala Cooperative Pathfinding (CPF).
Implementujte techniku, která zvládne plánování cest pro netriviální počet agentů (např. > 5) v netriviálním grafu (např. mřížka 10x10 s nějakou překážkou).
Úlohu lze modelovat i pomocí klasického plánování.

BetaGo (nebo radši GammaGo).

Pokuste se z probíraných technik postavit konkurenta pro AlphaGo (mimochodem úlohu MAPF a AlphaGo spojuje tatáž osoba a sice David Silver, který vymylel pro úlohu ten správný název CPF). Jde se o hledání herní strategie pro hru Go. Základním přístup může vycházek z klasických herních algoritmů - minimax, alpha-beta. Jelikož je strom hry velký, je potřeba vymyslet, jak odhadovat ohodnocení v uzlech stromu, odkud již prohledávání nemůže pokračovat.

Můžete sílu svého návrhu porovnat s vlastní herní silou nebo s i AlphaGo.
Podaří-li se vám vytvořit více variant herního algoritmu, lze je vyzkoušet proti sobě.

Sudoku na 100%

Uvažujme známou doplňovačku SUDOKU, kdy máme doplnit číslice 1 až 9 do mřížky velikosti 9x9 tak, aby byly splněny různé podmínky na různost číslic. Pravidla nebudeme detailně popisovat, předpokládáme, že jsou známá. Vaším úkolem je vyřešit doplňovačku pomocí technik umělé inteligence, ale tak aby to bylo provedeno co nejrychleji a garantovaně, tj. řešící algoritmus vždy skončí a dá správné řešení.

Nabízí se použít přístup z CSP, tedy modelovat Sudoku jako CSP a pak nad CSP provádět prohledávání
Nebo lze využít převodu na výrokovou splnitelnost. Zajímavou otázkou je implementovat více technik a porovnat jejich výkon.

Sudokář - klikař

Opět SUDOKU, ale tentokrát si vsadíme na štěstíčko tedy kliku. Systematické algoritmy z předchozí úlohy nejsou vždy snadné na naprogramování, zato lokální prohledávání/optimalizaci zvládne každý. Platíme za to neúplností lokálních algoritmů, ale jejich jednoduchost to vyvažuje.

Formulujte SUDOKU ja úlohu lokálního prohledávání, čili ve smyslu algoritmu stoupání do kopce.
Vzykoušejte různé varianty, jak lokálně měnit kandidáta na řešení a porovnejte je.
Pole velikosti 9x9 je pro dnešní počítače hračka (samozřejmě, jak kdy), proto vyzkoušejte zobecněné SUDOKU na větší hrací ploše.

Mistři volantu

Automobil, tedy ten autonomní je klasický případ robota. Vyzkoušíme si plánování pohybu při parkování - příčné je pro amatéry, my budeme parkovat podélně do řady do mezery, která je tak akorát. Trochu novější auta funkci automatického parkování mají, takže si vyzkoušejte, jesli umíte aspoň to, co už programátoři u automobilek zvládli. Pro zjednodušení vynecháme senzorickou stránku, řídící algoritmus všechno přesně vidí.

Auta můžeme dále uvažovat jako obdélníky. Auto může jet dopředu a dozadu. Řízení je pomocí předních kol, při natočení kol se automobil otáčí tedy jede po kružnici se středem v průsečíku osy zadní nápravy a os předních kol, čož mimo jiné znamená, že každé z předních kol můsí být natočene mírně jinak (vniřní víc).
Využijte poznatků o dopředné a zpětné kinematice, prostředí můžete vhodně diskretizovat.

Chalupářský automobilismus

Opět autonomní automobilismus, tentokrát chalupářký tj. s připojenou a pěkně naloženou kárkou/vozíkem. Budeme couvat a pakrovat, zde už je varianta příčného zaparkování (pozadu) zajímavá. Podélné pakrování nás zajímá rovňěž. Opět platí, že některé vozy funkci automatického parkování s vozíkem mají, takže si můžete vyzkoušet, zda se by o vás automobilka vůbec stála.

Platí stejná zjednodučení jako v přechozí úloze, tj. senzorickou stránku zanedbáváme, algoritmus všechno vidí.
Úkolem je tedy opět naplánovat pohyb, kterým úspěšně uklidíme auto i s kárkou da nějakého malého prostoru.

Mistři dvou volantů

Některé modernější automobily mají možnost zatáčení koly i na zadní nápravě. Rozmyslete k čemu to může být dobré a využijte toho. Například pro manévrování v úzkých uličkách se schopnost řídít zadní nápravu může hodit. Navrhněte plánování pohybu pro takto řízený automobil.

Důležité je, že při natočení zadních kol vůz jede po kružnici, které není na ose zadní nápravy, ale více vpředu.
Můžete vyzkoušet plánování pohybu pro podélné parkování, či průjezd úzkou pravoúhlou zatáčkou.

Zlatá 80. léta: Pacman

Podívejme se na klasickou arkádovou hru Pacman z hlediska herní teorie. Jak naplánovat pohyb Pacmana případně pohyb duchů za předpokladu, že protivník je velmi inteligentní, tedy v případě Pacmana se snažíme o snězení co nejvíce kuliček, aniž by Pacmana chytil nějaký duch, z hlediska duchů se snažíme o co nejrychlejší chycení Pacmana.

Navrhněte a implementujte algoritmus na hledání herní strategie pro Pacmana a duchy
Můžete uvažovat rozšíření, kdy Blinky (červený duch) je velitel a řídí ostatní duchy, jakmile ho Pacman sní, duchové dočasně (do oživení Blinkyho) přestanou hrát inteligentně

2020s: Multi-Pacman

Budeme plánovat pro více Pacmanů najednou. V původní hře z roku 1980 je jen jeden Pacman, my po několika desetiletích si dovolíme Pacmanů víc, neboli multi-Pacmana (ostatně nyní na rozdíl od roku 1980 máme multi-jádrové procesory), to s sebou nese nové pravidlo, a sice, že na jedno políčko hrací plochy se vejde jen jeden Pacman. Budeme-li tedy automaticky plánovat pohyb Pacmanů, je třeba se nejen snažit o snězení všech kuliček, ale také dbát na to, aby se Pacmani nesrazili.

Navrhněte a implementujte prohledávací algoritmus pro řízení Pacmanů
Můžete předpokládat, že duchové nejsou moc inteligentní, pohybují se náhodně, v blízkosti Pacmana hladově

8-bit Games Stike Back: Had

Navrhněte inteligentní řízení hada ve stejnojmenné hře Had. V nejjednodušší variantě jde o čtverečkového hada, který se pohybuje po dvourozměrné mřížce hadovitým stylem, tj. tělo postupně následuje hlavu, a snaží se sníst jedlé čtverečky, které jsou v mřížce různě rozmístěny, případně se mohou objevovat nové. Po pozření jedlého čtverečku se had prodlouží o jeden čtvereček. Musíme ale dávat pozor na to, aby se had nezamotal sám do sebe.

Hada chápejte jako inteligentního agenta ve virtuálním prostředí, jeho řízení tedy bude realizováno agentní funkcí
Posudte různé urovně agentních schopností, které se vám mohou hodit: reflexní agent, agent s modelem prostředí, agent s cílem atd.
Realizujte agentní funkci pomocí probíraných technik, nabízí se: heuristické prohledávání, klasické plánování, různé evoluční techniky

SAT Solver Killer

Výroková splnitelnost (SAT) je silný cílový formalismus pro modelování a řešení úloh. A to díky efektivním programům-řešičům pro SAT. V této úloze řešiče SATu potrápíme. Nalezněte krátkou výrokovou formuli v CNF takovou, aby pro řešič SATu byla co nejobtíženější (obtížnost měřte jako dobu běhu resp. jako počet kroků řešiče).

Je vhodné stanovit nějaké limity na velikost formule, např.: celkový počet literálů vyskytujících se v celé formuli bude maximálně 1000.
Doporučený řešič je Glucose, který sice není nejvýkonnější, ale dává stabilní výsledky. Případně se lze dívat také na stránky soutěže SAT Competition, kde jsou k dispozici další řešiče.
Vyzkoušejte si jak výsledky dopadají pro splnitelný a nesplnitelný případ. Typicky těžší ne nesplnitelná varianta. Zkuste se omezit jen na splnitelné formule, či jen na nesplnitelné, resp. obojí.

OCR (Optical Character Recognition) snadno a rychle

Mějme znaky nějaké abcedy jako obrázky, například velikosti 16x16 ve stupních šedi. Vaším úkolem je najít pozice několika pixelů tak, aby bylo možné podle hodnot těchto pixelů znaky abecedy od sebe rozeznat. Pro abecedu s 26 znaky s černo-bílými obrázky by teoreticky mělo stačit 5 pixelů, protože hodnoty v těchto pixelech mohou nabývat celkem 2<sup>5</sup>=32 různých kombinací což je více ne 26.

Pokuste se úlohu vyřešit pro latinskou abecedu, obrázky znaků můžete najít v následujícím archivu: Datová sada - latinka.
Najděte co nejmenší počet bodů, podle nichž jste schopni rozpoznávat znaky jedné z japosnký abeced, a sice hiraganu, obrázky znaků poskytujeme v následujícím archivu: Datová sada - hiragana (odkaz na zdroj).

Vlastní téma

Máte-li zajímavou úlohu z oblasti umělé inteligence, kterou byste chtěli vypracovat, je možné ji odevzdat jako semestrální práci. Téma nemusí být v předmětu odpřednášeno ani odcvičeno, nicméně by svou náročností mělo odpovídat doporučenému zadání. Náročnost posoudí cvičící a téma buď schválí, nebo doporučí nějaké změny. Neschválené téma není možné odevzdat.

Téma z laboratoře

Student si může vybrat některé z témat prezentovaných v HW laboratoři. Pro tyto možnosti si lze z laboratoře zapůjčit některý z dostupných HW. I tato zadání podléhají schválení cvičícího (především upřesnění tématu i rozsahu).