Témata studentských prací

Pokud máte zájem dělat u mě ročníkový projekt případně bakalářskou/diplomovou práci, ozvěte se e-mailem. Téma záleží na domluvě - buď přijďte s konkrétním návrhem, nebo můžeme téma vymyslet společně podle oblastí, které vás zajímají. V každém případě bych byl rád, aby téma bylo z mého pohledu zajímavé. Nejlépe pokud bude souviset s oblastmi, kterými se zabývám (viz např. hlavní stránka nebo programy).

Ve spolupráci s externí firmou mohu nabídnout témata týkající se umělé inteligence a strojového učení. Pro více informací mě kontaktujte emailem.

Pár nápadů pro inspiraci:

Netradiční metody pro kompresi dat
Inverzní problémy celulárních automatů a jejich aplikace
Vytvoření jednoduché hry
Celulární automat jako hra (Téma už je zabrané)
Skládání hudby jako hra
Šifrování pomocí celulárních automatů (Téma už je zabrané)
Řešení nějakého NP-těžkého problému

Zájemcům o prohledávání a optimalizaci můžu nabídnout témata z oblastí, kterými se zabýváme v naší výzkumné skupině. (Od řešitelů se očekává vlastní zájem o problematiku plánování a rozvrhování nebo prohledávání obecně.) Následuje seznam několika oblastí, kterými se chceme zabývat. Konkrétní téma a rozsah práce bychom stanovili po domluvě.

Implementace a experimentální porovnání prohledávacích algoritmů pro plánování

Jedná se zejména o různé varianty algoritmů A*, BFS a branch-and-bound. Řešitel by měl nastudovat tyto algoritmy, implementovat je a porovnat jejich efektivitu na různých plánovacích doménách. Hlavním smyslem projektu je, abychom měli k dispozici efektivní implementace těchto algoritmů a mohli je jednoduše používat v další práci. Další výzkum se může ubírat těmito směry:

Transformace prostoru pro efektivnější prohledávání

Při hledání minima jisté objektivní funkce je efektivita prohledávání silně závislá na tvaru funkce (např. počet lokálních minim a podobně). Transformací prostoru můžeme prohledávání urychlit - například pomocí vhodné permutace definičního oboru můžeme libovolně "ošklivou" funkci převést na funkci bez ostrých lokálních minim.
Obecně chceme nalézt topologii na definičním oboru, která by zajišťovala, že oblasti s podobnou hodnotou učelové funkce budou blízko sebe.
Rádi bychom takové transformace nalezli "ručně" pro některé třídy problémů (plánovací domény) a poté tento přístup zobecnili a zautomatizovali.

Návrh efektivních heuristik pro konkrétní problémy

Myslí se tím heuristiky pro algoritmus A*. Existuje mnoho doménově nezávislých heuristik, většina z nich však nefunguje dobře na "těžkých" problémech (např. Sokoban). Rádi bychom navrhli efektivní doménově specifickou heuristiku pro některý z těchto problémů, tuto následně analyzovali (zjistili proč je efektivní, jaké vlastnosti problému využívá...), a pokusili se ji zobecnit na šiřší třídu problémů. V ideálním případě by takto mohla vzniknout nová doménově nezávislá heuristika.

Komprese databází vzorů

Databáze vzorů jsou v současnosti velmi populární pro vytváření přípustných heuristik. Čím větší je databáze, tím přesnější je výsledná heuristika. Bohužel během prohledávání není k dispozici příliš mnoho volné paměti, proto se používají i komprimované databáze. Rádi bychom prozkoumali nové metody komprese databází vzorů, s důrazem na rychlý přístup k datům (dekomprese). Je možné použít i ztrátovou kompresi, což povede k méně informované heuristice, ale úspora prostoru se může přesto vyplatit. Kompresi je možné zlepšit pomocí dalších technik, například hledání symetrií. Také je možné pro tyto účely modifikovat některé paměťově úsporné datové struktury.

Automatické vytváření databází vzorů

Hlavním problémem je najít správné vzory - tj. ty, které povedou k efektivní heuristice. Tento problém lze řešit například pomocí optimalizačních meta-heuristik, pro návrh fitness funkce je možné využít predikci chování algoritmu - pro zjištění, zda je vzor kvalitní, se pokusíme odhadnout jak by dopadlo prohledávání, kdybychom tento vzor vybrali (viz následující bod).

Predikce časových a paměťových nároků při prohledávání

Problém spočívá v tom, jak jednoduše a rychle zjistit, jak se bude daný prohledávací algoritmus chovat na daném problému. Například kolik uzlů bude přibližně expandovat A* nebo IDA* s danou heuristikou než najde řešení, kolik uzlů expanduje v i-té hladině, jak velký strom prohledá, jaký bude průměrný větvící faktor a podobně. S tím se pojí také otázky typu: Která ze dvou heuristik je lepší, který ze dvou prohledávacích algoritmů je lepší.

Některá další témata jsou už vypsaná v SISu