Supervising



I offer supervising of all types of theses at undergraduate, graduate and doctoral level. Please see the following lists of theses I have supervised and reviewed. I supervise a wide range of topics in artificial intelligence and occasionally interdisciplinary topics combining AI with some other area. If you are a student interested in working on a thesis under my supervision please feel free to contact me. Motivated Ph.D. students with solid background in computer science and mathematics are especially welcome.



Supervised theses

Doctoral (dissertations)
  • Jiří Švancara, Multi-agent Path Finding, co-supervision, since 2016.
  • Eliška Hejlová, Computer Aided Teaching of Spatial Geometry, 2015.
  • Tomáš Balyo, Modeling and Solving Problems Using SAT Techniques, co-supervision, 2012.
Graduate (master theses)
  • Ondřej Majerech, Multi-agent Path Finding in Dynamic Environments, 2017
  • Jiří Švancara, Multi-agent Path Finding in Unidirectional Environments, 2016.
  • Marika Ivanová, Adversarial Cooperative Path-Finding, 2014.
        Second place in the national competition of the Union of Czech Mathematicians and Physicists
  • Josef Talaš, Content-based Image Search, Master thesis, 2014.
  • Petr Michalík, Sub-optimal algorithms for solving sliding puzzles, 2011.
  • Tomáš Balyo, Design of an efficient SAT solver, 2010.
Undergraduate (bachelor theses)
  • Róbert Selvek, Evacuation Planning Based on Local Cooperative Pathfinding Techniques, since 2018.
  • Tomáš Vlk, Benchmarks for Multi-Agent Path Finding, since 2018.
  • Zuzana Filová, Processing and Editing the Outputs of Automated Music Transcription, since 2018.
  • Zdeněk Šimůnek, Adversarial Multi-agent Path Finding - Hierarchical Heuristics, since 2018.
  • Filip Beskyd, Prediction of Dota 2 Game Result, 2018.
  • Jakub Střelský, Automated Generation of Realistic Terrain Using Machine Learning Techniques, 2016.
        First place in the national competition of the Union of Czech Mathematicians and Physicists
  • Tran Tuan Hiep, Text Recognition in Natural Scenes, 2015.
  • Milan Ježek, Modeling of Cooperative Path Finding, 2015.
  • Miloš Chromý, Improvement of the BIBOX Algorithm, 2013.
  • Jakub Vlček, Recognition and Filtration of Unwanted Video-Sequences, 2013.
  • Václav Obrázek, Coordinated pathfinding with formations, 2013.
  • Filip Stočes, Visualization of plans for logistics tasks, 2011.
  • Ivana Lukšová, Bitmap picture classification, 2010.
  • Jakub Kýpeť, Computer poker, 2010.
  • Martin Petr, Handwriting recognition using neural network, 2010.
  • Vojtěch Bardiovský, Generating of self-replicating cellular automata, 2010.
  • Petr Koupý, Visualization of problems of motion on a graph, 2010.
  • Martin Ščavnický, Automated prediction of results of tennis tournaments, 2010.
  • Josef Pihera, Data archiving using longest common subsequence, 2010.
  • Radovan Duga, Erasing Disturbing Objects from Digital Pictures, 2009.
  • Martin Galajda, Algorithms for Solving the Sokoban Game, 2009.
  • Ondřej Malý, Software for Modeling Car Driving Properties, 2008.
  • Tomáš Balyo, Efficient Boolean Satisfiability Solver, 2008.
  • Štefan Čudai, Multiagent Traffic Control System, 2007.
  • Martin Langhammer, Train Traffic Simulation with Optimization, 2007.
  • Attila Ulman, Emergence of Intelligent Behavior of Social Insects, 2007.
  • Kristýna Bémová, Computer-aided Teaching of Spherical Geometry, 2007.



Reviewed theses

  • Jan Tožička, Multi-Agent Planning by Plan Set Intersection, Doctoral Dissertation (Ph.D.), 2017.
  • Michal Čáp, Centralized and Decentralized Algorithms for Multi-Robot Trajectory Coordination, Doctoral Dissertation (Ph.D.), 2017.
  • Holubyev Dmytro, Balancing rules of prototype board game Souboj živlů, Bachelor thesis, 2016.
  • Imrich Kuklis, Selected Problems Related to Vehicle Routing, Bachelor thesis, 2015.
  • Martin Blicha, Model Construction in Polynomial Representation, Bachelor thesis, 2015.
  • Jan Tomášek, Computational Intelligence for Malware Classification, Master thesis, 2015.
  • Radek Miček, Automated Model Construction, Master thesis, 2015.
  • Dominik Janata, Timetable Designing Environment, Bachelor thesis, 2014.
  • Michal Ondrejáš, Path planning in realistic 3D environments, Bachelor thesis, 2014.
  • Michal Klein, Coordinated Movement of Virtual Agents in Unreal Tournament 2004, Bachelor thesis 2014.
  • Martin Pecka, Detection of 2D features in MARSIS ionogram pictures, Master thesis, 2013.
  • Marcel Kikta, Visualization of Geometric Algorithms, Bachelor thesis, 2012.
  • Luboš Turek, Application of the ACO Algorithm to Solving Simple Substitution Cipher, Bachelor thesis, 2012.
  • Jakub Lehotský, Incomplete Search Algorithms, Master thesis, 2011.
  • Martin Molnár, Filtering Algorithms for Tabular Constraints, Master thesis, 2010.
  • Jindřich Ivánek, Heuristically controlled search for the optimum in NP-hard problems, Bachelor thesis, 2010.
  • Robert Brunetto, Interpreter and debugging environment for Prolog, Bachelor thesis, 2010.
  • Tomáš Caithaml, Domain specific languages, Master thesis, 2009.
  • Pavel Zykán, Dynamic Temporal Network, Master thesis, 2009.
  • Michal Tuláček, Constraint solvers, Bachelor thesis, 2009.
  • Tomáš Plch, Action selection for an animat, Master thesis, 2009.
  • Jaroslav Mlejnek, Global Constraints, Bachelor thesis, 2008.
  • Tomáš Huml, Portfolio Optimization, Bachelor thesis, 2008.
  • Petr Baudiš, Current Concepts in Version Control Systems, Bachelor thesis, 2008.
  • Ondřej Krč-Jediný, Matrix Calculator, Bachelor thesis, 2008.
  • Petr Baudiš, Current Concepts in Version Control Systems, Bachelor thesis, 2008.
  • Miroslava Plachá, Comparison of Constraint Programming Systems, Bachelor thesis, 2007.
  • Tomáš Haničinec, Constraint Modeling, Bachelor thesis, 2007.
  • Ľubomír Karlík, System for Administration of Tests, Bachelor thesis, 2007.
  • Luděk Cigler, Analysis and Implementation of School Timetabling Algorithms, Bachelor thesis, 2006.



Topics

Sepsal jsem řadu návrhů témat na různé typy prací od projektu, přes bakalářskou a diplomovou práci, po témata k doktorskému studiu. Většinu témat lze rozpracovat v různých úrovních náročnosti. Na požádání k tématům poskytnu více informací, případně téma podrobněji vysvětlím.


Tie-breaking in CBS. Algoritmus CBS (Conflict-Based Search) je prohledávací algoritmus založený na relaxaci požadavků na řešení daného problému a jejich oddáleném splňování, tj. splňování až v okamžiku, kdy se kandidát na řešení nalezený za relaxovaných podmínek ukáže řešením nebýt (kvůli porušení určitých podmínek, které řešení splňovat musí). Výhodou algoritmu je, že máme-li štěstí, podaří se řešení nelézt, tj. splnit všechny požadované podmínky, i v relaxaci, tedy i když se všemi podmínkami algoritmus explicitně nezabývá. V určité fázi algoritmus vybírá uzel k dalšímu větvení, zde lze typicky vybírat z mnoha možností, aniž by výběr porušil garanci nalezení optima. Vhodný výběr uzlu ale může ovlivnit celkový počet kroků algoritmu. Navrhněte techniky pro výběr uzlu k větvení s ohledem na minimalizaci celkového počtu kroků algoritmu. Nabízí se prozkoumat různé expertně navržené heuristiky nebo automaticky se učící heuristiky (například pomocí strojového učení).

Flow Free Addiction. Hra Flow Free se velmi podobá na této stránce často zmiňovanému tématu MAPF (hledání cest pro mnoho agentů). Odlišnosti jsou v pojetí interakce mezi agenty, ve Flow Free je možno každým vrcholem projít nejvýše (možná právě) jedenkrát, zatímco v MAPF libovolněkrát. Řešící techniky aplikovatelné na MAPF (a je jich mnoho) jsou po drobných úpravách snadno aplikovatelné i na Flow Free. V rámci tématu lze řešit například automatický návrh a verifikaci úrovní (levelů), řešící algoritmy pro jednoho a více hráčů, nebo zobecnění hry (původní varianta se odehrává na mřížce, je možno uvážit mřížky s překážkami, jiné rovinné grafy a nerovinné grafy).

MIDI Beautify. Cílem práce je navrhnout systém pro vylepšování notového zápisu (například ve formátu MIDI) získaného automatickým převodem z digitálního vlnového zvukového záznamu (například ve formátu .wav nebo .mp3). Výsledek automatického převodu zvukového záznamu často bývá pro člověka těžko čitelný notový zápis. Práce se tedy bude zaměřovat na vylepšení notového zápisu vzhledem k jeho čitelnosti s využitím poznatků hudební teorie. Jako možné výpočetní nástroje se nabízejí techniky z teorie jazyků a zpracování řetězců (automaty a gramatiky) nebo strojové učení.

Taxonomie a benchmarky pro MAPF/CPF. Cílem je zavést vhodnou taxonomii pro problém MAPF/CPF a na jejím základě vytvořit sadu generátorů pro instance problému. Instance MAPF/CPF by mělo jít generovat podle různých parametrů. Klasickou taxonomickou třídou v MAPF/CPF jsou instance na mřížkových grafech s překážkami s náhodnou počáteční a cílovou konfigurací agentů. Parametry v této třídě jsou velikost mřížky, hustota překážek a počet agentů.

Evacuation 2 - via local CPF. Úloha evakuace spočívá v plánování přesunu osob z ohrožené oblasti do bezpečí. Při grafové interpretaci úlohy jde o nalezení nekonfliktních cest v neorientovaném grafu vedoucí evakuované osoby z ohrožených vrcholů do vrcholů bezpečných. Úlohu lze modelovat a řešit optimálně jako hledání maximálního toku v časově expandovaném grafu, ovšem tento přístup vyžaduje centrální plánování, které není při evakuaci často realizovatelné. V rámci navrhovaného tématu je cílem prozkoumat možnosti úpravy lokálních algoritmů kooperativního hledání cest (CPF), jako je například LRA* tak, aby produkovaly řešení zohledňující cíle evakuace (co nejvíce zachráněných osob, v co nejkratším čase atd.).

Komprese BDD/MTBDD a učení. Prozkoumejte možnosti reprezentace znalostí pomocí binárních rozhodovacích diagramů (binary decision diagram - BDD) či zobecněné varianty MTBDD pro rozhodování mezi více než dvěma alternativami (multi terminal BDD). Pomocí komprese se pokuste zvýšit generalizační schopnost a kapacitu rozhodovacích diagramů. Aplikujte komprimované BDD v praktické úloze rozpoznávání vzorů.

SAT Encoding of Global Constraints. Ve výrokových (booleovských) formulích lze modelovat proměnné s konečnou doménou a různé podmínky nad těmito proměnnými, např. lze modelovat proměnné a,b,c ∈ {1,2,3} a podmínku all-different, která říká, že a,b,c mají nabývat vzájemně různých hodnot. Podmínky zahrnující mnoho proměnných typicky označujeme jako globální - all-different je příkladem takové podmínky. Navrhněte nějaké nové kódování globální podmínky, jako je all-different, at-most-K, či jíné podmínky kardinality, lze zkoumat i grafové podmínky, tj. např. zda vybraná množina vrcholů grafu (vybereme pomocí ohodnocení určitých proměnných) splňuje zadanou vlastnost, např. je souvislá, tvoří podstrom, má malý poloměr atd.

Area Protection Problem (APP) - Algorithmic Arms Race. APP je varianta problému AMAPF, kde jeden tým agentů brání určitou oblast před vniknutím agentů z nepřátelského týmu. Podobně jako v tématu AMAPF je cílem navrhovat řídící algoritmy pro bránící resp. pro útočící tým. Téma je vhodné řešit ve dvojici, kdy jeden řešitel navrhuje algoritmy pro útočné strategie, zatímco druhý řešitel se zabývá obrannými strategiemi. Závody v "algoritmickém zbrojení" mohou katalyzovat získávání nových poznatků o problému.

Polynomiální algoritmy pro multi-agentní hledání cest (Multi-agent Path Finding - MAPF). Problém MAPF lze řešit algoritmy pracujícími v polynomiálním čase (jako jsou BIBOX, Push-and-Swap, Push-and-Rotate), řešení ale v takovém případě není optimální navíc zpravidla od optima velmi vzdálené, ať už uvažujeme jakoukoli z běžných metrik. Otevřenou otázkou zůstává, jak navrhnout polynomiální algoritmy, které generují řešení blíže optimu. Lze se zabývat různými speciálními případy grafů, jako jsou mřížky, grafy s nízkou souvislostí, rovinné grafy, či speciálními případy konfigurací agentů.

Multi-agentní hledání cest s protivníkem (Adversarial Multi-agent Path Finding - AMAPF). MAPF neboli také kooperativní hledání cest (Cooperative Path Finding - CPF) může být do jisté míry i nekooperativní, tj. máme více týmů agentů, kde agenti v rámci týmu kooperují, ale týmy mezi sebou soutěží v dosažení svých cílových pozic. Cílem v tomto tématu je navrhnout ad-hoc heuristické algoritmy pro týmy agentů. Složitější varianta tématu si může klást za cíl hledání heuristických algoritmů pro týmy agentů automaticky (například pomocí hlubokého učení - Deep Learning, či genetického programování).

Multi-agentní hledání cest (Multi-agent Path Finding - MAPF) jako SMT. V rámci tohoto tématu je úkolem prozkoumat možnosti použití SAT Modulo Theory (SMT) pro řešení problému MAPF. Základní použití SMT v problému MAPF lze chápat jako algoritmus CBS (Conflict Based Search), kde nekonfliktní cesty hledá SAT řešič místo interní procedury algoritmu CBS, přičemž SAT řešič má na rozdíl interní procedury možnost se učit. Zvlášť zajímavé se jeví možnost prozkoumat různou míru těsnosti spolupráce mezi SAT řešičem a algoritmem CBS (například SAT řešič si může uchovávat naučené klauzule napříč různými iteracemi algoritmu CBS, SAT řešič může žádat o vyhodnocení konfliktů v částečně zkonstruovaných cestách atd.).

Kompilační přístup k multi-agentnímu hledání cest (Multi-Agent Path Finding - MAPF). Cílem je vylepšit existující nebo navrhnout nové řešící metody problému MAPF založené na překladu do jiného formalismu jako je SAT (výroková splnitelnost), IP (celočíselné programování), či CSP (programování s omezujícími podmínkami). Několik prací popisující metody překládající problém MAPF na problém SAT lze najít v sekci publikace.

Striker Eureka     

Virtual Jaeger Kit. Cílem bude naprogramovat fyzikálně realistický simulátor (obřího humanoidního) robota, kde robot bude sestaven z určitých pohyblivých částí, které budou charakterizovány veličinami popisujícími jejich hmotnost, točivý moment, sílu pohonu atd.. Nadstavbou simulátoru by pak mohl být algoritmus řídící základní pohyb robota (krok, úder s udržením rovnováhy, atd.).



Evacuation. Varianta kooperativního hledání cest (cooperative path-finding nebo multi-agent path-finding), kdy úkolem není dopravit agenty do cílových pozic, nýbrž maximální počet agentů (evakuovaných osob) co nejrychleji odsunout z ohrožené oblasti. Lze řešit různé varianty problému: on-line varianta pro předem neznámé počáteční rozmístění agentů v nezmámém prostoru, nebo off-line varianta, kdy evakuovaný prostor je předem známý a stejně tak rozmístění evakuovaných agentů je známé (velmi aktuální téma pro divadla, kina, školy, autobusy, letadla, ...). U on-line varianty potřebujeme rychlý algoritmus, přičemž rychlosti je možno obětovat kvalitu řešení, zatímco u off-line varianty na době běhu algoritmu nezáleží a kritériem je pouze kvalita řešení.

Robot Consumation. Uvážíme-li možnost konzumace robota v úloze, jako je kooperativní hledání cest (cooperative path-finding nebo multi-agent path-finding), vznikne zajímavá situace. Nechť konzumace robota znamená jeho zmizení, jakmile dorazí do cíle; tím se úloha podstatně mění. Prostudovat charakteristiky a řešící algoritmy pro tuto variantu hledání cest by jistě bylo přínosné. Lze uvážit i možnost produkce robota (opak konzumace) - pak se přirozeně nabízí hledat pohyb, který maximalizuje počet robotů dopravených z místa jejich produkce do místa jejich konzumace (praktická motivace: robot = automobil, hledáme kooperativní jízdu maximalizující průjeznost křižovatkou, dopravním uzlem, atd.).

Remotely Controlled Robots. Plánování pohybu robotů na dálkové ovládání, kdy robot je kabelem spojen s řídícím terminálem, představuje zajímavý kombinatorický problém, pokud se chceme vyhnout zamotání kabelů. Navrhněte algoritmy pro hledání cest pro více robotů, případně algoritmy kooperativního plánování složitějších činností více robotů s ohledem na kabelové spojení robotů s řídícím centrem, jejichž křížení a zamotání je nežádoucí (pozn.: kabelové spojení je používáno u podmořských robotů).

Drone Air Superiority. Návrh kooperace letky létajících dronů, která má za úkol zabránit v průniku nepřátelských dronů do chráněného vzdušného prostoru. Téma představuje konkrétní aplikaci a variantu kooperativního hledání cest s protivníkem (Adversarial Cooperative Path Finding - ACPF). Je třeba uvážit manévrovací schopnosti létajících dronů a úroveň jejich umělé inteligence. Téma lze řešit nejprve simulačně či se zaměřit na určité podproblémy (kooperativní pronásledování unikajícího dronu).

Drone Alert! Stále dostupnější létající drony se stále větší nosností a řídícími schopnostmi budou pravděpodobně v blízké budoucnosti znamenat vážné bezpečnostní riziko. Útočník může například využít létajícího dronu k dopravě výbušniny do prostoru, který je pozemní cestou nedostupný, přičemž sám útočník zůstane skrytý. Proti podobným aplikacím létajících dronů zatím neexistuje účinná obrana. V rámci tohoto tématu je úkolem navrhnout systém protivzdušné obrany proti létajícím dronům resp. jeho vybranou komponentu se zaměřením na řídící mechanismy takového systému (software a umělou inteligenci). Zabývat se lze rovněž návrhem stíhacího dronu (jeho řídícího softwaru), jehož úkolem by bylo vyhledávání a ničení nepřátelských dronů.

Adversarial Cooperative Path-Finding (ACPF). V úloze kooperativního hledání cest s protivníkem je třeba dopravit agenty (roboty) do daných cílových pozic navzdory snaze protivníkových agentů (robotů), kteří tento záměr maří. Soupeřící skupiny agentů mohou si mohou vzájemně blokovat cílové pozice nebo si zabraňovat v pohybu. Úlohu lze zkoumat z teoretického hlediska a stejně tak z hlediska řešících algoritmů, které ovládají danou skupinu agentů.

Railroad Planning. Plánování jízdy vlaků do jejich cílových stanic v komplexní železniční síti s mnoha výhybkami může být motivací k zajímavým teoretickým problémům. Mimo jiné se v železniční síti projevuje směrová vlastnost výhybek, tj. výhybka funguje jen při průjezdu jedním směrem, což vede na určitou formu kooperativního hledání cest (cooperative path-finding - CPF, viz. další témata), ovšem nad orientovaným grafem. Orientace grafu, nad nímž se pohyb odehrává, představuje netriviální komplikaci a zároveň příležitost pro výzkum, neboť mnohé existující postupy pro řešení kooperativního hledání cest spoléhají na možnost reverzních pohybů (tj. pohybů v obou směrech).

     N700

Dangerous Roads. Nepromyšlené budování pozemních komunikací vytváří pro řidiče motorových vozidel nebezpečná místa. V tuzemnských podmínkách je problém umocněn poruchami chování některých řidičů (typicky agresivní) a někdy až cíleným vytvářením nebezpečných silničních úseků. Navrhněte systém na automatickou detekci nebezpečných silničních úseků či dopravních uzlů, přičemž jako parametry můžeme uvažovat podíl řidičů s poruchou chování (agresivní, sváteční). Jedná se o téma z oblasti simulace s příměsí psychologie chování.

Automated Music Transcription. Cílem by zde bylo vytvořit software s dobrým hudebním sluchem, který dokáže podle poslechu skladby vytvořit její notový zápis. V rámci tématu lze řešit řadu podúloh, jako je například dekompozice akordu podle poslechu atd. Jedná se převážně o výzkumné téma, neboť úloha transkripce není v době navržení tohoto tématu uspokojivě vyřešena.

     Music

Sentiment Analysis. Problémem je automaticky klasifikovat názory v krátkých textových vyjádřeních. Klasickou aplikací je analýza diskusních příspěvků k článkům na internetu s tématy, které navozují výraznou společenskou polarizaci (např. volba prezidenta, imigrace, evropská unie, ekologismus, atd...). V základní variantě by se jednalo o dichotomickou klasifikaci vyjádření ve smyslu souhlasu či neshlasu s danou otázkou (např. zda přispivatel podporuje jistého kandidáta). Výsledný softwarový nástroj by mohl najít využití v přípravě volební kampaně či v předpovědi volebního výsledku. Téma lze rozvíjet pro specificky české společenské prostředí, čímž se může odlišit od již dosažených výsledků v anglicky mluvícím prostředí.

Continuous CPF. Kooperativní hledání cest pro mnoho robotů (cooperative paht-finding - CPF) je klasická úloha řešená v umělé inteligenci. Mnoho výsledků existuje pro diskrétní variantu, kde se roboti pohybují v diskrétních krocích po grafu, který modeluje původní prostředí. Zajímavým přístupem by mohlo být řešit úlohu ve spojitém prostoru, kde by se roboti pohybovali spojitě po hladkých křivkách. Tento přístup by byl obzvlášť výhodný pro reálné roboty (kolové, pásové, létající) se specifickými manévrovacími schopnostmi.

CSD     

Computer Science Department Ranking. Chceme-li posoudit vědeckou kvalitu informatického pracoviště, děláme to zpravidla tak, že si prohlédneme publikace a citovanost všech jeho členů. Tyto informace lze poměrně rutinním způsobem najít v databázích, jako jsou DBLP či Google Scholar. Zmíněná rutinnost hledání údajů vede k myšlence celý proces automatizovat. Představme si software, který po zadání webové stránky zkoumaného pracoviště se seznamem jeho členů odpoví přehledným zhodnocením jeho vědecké výkonnosti. Existence podobného softwaru by umožňovala provádět zajímavá (kontroverzní) srovnání.



Automated Encoding. Řadu kombinatorických úloh lze modelovat a řešit jako úlohu výrokové splnitelnosti (SAT). Zajímavou otázkou je, zda lze tvorbu kódování automatizovat. V jistých případech lze hledání kódování formulovat jako úlohu patříci do třídy Σ1P a řešit pomocí řešiče pro QBF (quantified Boolean formula). Otevřenou otázkou je rovněž hledání obecných kódovacích obratů v automaticky vygenerovaném kódování.

Smart Grid. Inteligentní propojovací sítě (smart grid) umožňují propojení míst výroby a spotřeby elektrické energie podle aktuálních potřeb v reálném čase. Problematiku lze zkoumat z hlediska teorie grafů a kombinatorické optimalizace - otázkou může být například, jak rozmístit zdroje výroby elektřiny s co nejmenšími náklady na budování sítí, jak navrhnout topologii sítě s co nejmenšími náklady atd...

Extraktor nápisů. Cílem je navrhnout a implementovat software, který ze vstupní digitální fotografie extrahuje nápisy ve formě znakových řetězců. Možná aplikace je pak v internetovém vyhledávači, který na textový dotaz odpoví pomocí obrázků, které obsahují odpovídající nápis.

Optimalizace CPF. Rychlé algoritmy pro řešení úlohy kooperativního hledání cest (cooperative path-finding - CPF) generují ve většině případů nekvalitní plán. V rámci tohoto tématu bychom se zabývali technikami pro zlepšování sub-optimálních plánů pro CPF. Jak snadno identifikovat nekvalitní podplán a jak za něj najít kvalitnější náhradu? Jedna z možností je úlohu zlepšování podplánu modelovat jako výrokovou splnitelnost (SAT) a hledat tak optimální náhrady.

CPF jako SAT. Cílem by bylo navrhnout nová kódování či vylepšení existujících kódování úlohy kooperativního hledání cest (cooperative path-finding - CPF) jako výrokové splnitelnosti (SAT). Články pojednávající o existujících kódováních lze nalézt v sekci s publikacemi.

iBIBOX. Reimplementace algoritmu BIBOX s vylepšeními pro případy, kdy je graf řídce obsazen agenty. Jedná se téma spadající pod cooperative path-finding (CPF). BIBOX je úplný suboptimální algoritmus řešící úlohu CPF na 2-souvislých grafech v polynomiálním čase. Ovšem předpokládá velkou zaplněnost grafu agenty a v případech, kdy tomu tak není, podává horší výkon (generovaný plán je příliš dlouhý).

Super zoom. Předpokládejme, že máme video záznam vzdáleného statického objektu. Chtěli bychom daný objekt z video záznamu co nejlépe zrekonstruovat, tj. pořídit fotografii v co nejlepší kvalitě. Snímáním objektu po delší časový úsek umožňuje shromáždit více světelné informace, což lze teoreticky dále využít k získání obrazu ve vyšším rozlišení než je rozlišení snímače kamery. Motivace pro tento problém je možnost identifikace diváků na sportovních akcích z televizních záznamů.

Wave     

Identifikátor umění. Jednalo by se o aplikaci pro chytrý telefon, která by pomocí kamery zabudované v telefonu identifikovala umělecká díla při procházce galerií. Je-li povoleno fotografovat, mohla by aplikace rovněž automaticky přiřazovat popis pořízeným fotografiím (tedy: autor, název, rok vzniku, technika).



Vyhledávání multimediálního obsahu. Navrhněte techniky pro vyhledávání multimediálního obsahu v prostředí internetu. Multimediálním obsahem mohou být fotografie, obrazy, hudba či video. Vyhledávat lze na základě podobností či na základě abstraktních charakteristik. Například vyhledávání uměleckého díla by mohlo proběhnout na základě stručného popisu či náčrtku v editoru - návrh vhodné abstraktní charakterizace je součástí tohoto tématu.

Podmínky kardinality jako SAT. Cílem je navrhnout efektivní reprezentace podmínek kardinality nad bitovými vektory jako výrokové formule. Příkladem podmínky kardinality je požadavek, že daný počet proměnných z jisté množiny proměnných musí nabývat určité hodnoty. Téma lze spojit s modelováním úlohy, jejíž model podmínky kardinality vyžaduje, ve výrokové splnitelnosti.

Aktivní kamufláž (částečně hardwarové téma). Cílem je navrhnout a implementovat techniku "aktivní kamufláže" za pomoci jistého druhu projekce. V podstatě jde o emulaci techniky, která je známá ze sci-fi produkce (kamufláž využívá fiktivní rasa agresivních mimozemšťanů nazývaných Yautja, též známých jako Predátoři). Na základě 3D modelu povrchu kamuflovaného objektu a pozice pozorovatele chceme v reálném čase na povrch kamuflovaného objektu promítat obraz pozadí tak, aby objekt vzhledem k pozorovateli s pozadím splýval. Pro zjednodušení lze předpokládat, že kamuflovaný objekt je statický, pohybuje se pouze pozorovatel. K pokusu lze použít bežný projektor a snímač polohy. V pokročilejší variantě se pohybuje i kamuflovaný objekt. V nejpokročilejší variantě pak navíc kamuflovaný objekt mění tvar - zde patrně již dostupný HW k realizaci nestačí.

     Predator


Cooperative path-finding     

Kooperativní plánování. Zde máme na mysli zejména kooperativní plánování cest pro agenty (cooperative path-finding - CPF). Zkoumat lze zobecnění úlohy - například zobecnění cíle, kdy pouze někteří agenti budou mít předepsanou cílovou pozici. Další zobecnění se mohou týkat pohybu agentů - může být požadován pohyb ve formaci. Lze se též vydat cestou překonávání dosavadních možností - pro kolik agentů dokážete vytvářet optimální plány? V roce 2010 to bylo asi 60 agentů v grafu obsahujícím zhruba 800 vrcholů. Speciální témata k CPF budou postupně přidávána výše.



SAT v širším smyslu. Prozkoumejte možnosti aplikace některé ze SAT technik v širším smyslu - například pseudo-Boolean podmínky, MaxSAT, či QBF - pro řešení konkrétní úlohy z rozvrhování, plánování, či optimalizace. Pro vyřešení úlohy pak použijte existující pseudo-Boolean řešič, MaxSAT řešič, či QBF řešič.

Lokální řešící algoritmy. Survey propagation (propagace průzkumů), Warning propagation (propagace výstrah), Belief propagation (propagace přesvědčení). Úkolem je implementovat některou z uvedených řešících technik a prozkoumat její chování na standardní sbírce úloh z knihovny SATLib a/nebo soutěží SAT Competition a SAT Race.

Analýza sociální sítě. Navrhněte metody a algoritmy pro analýzu vztahů v sociální. Na sociální síť lze nahlížet jako na graf, na němž je možné zkoumat základní grafové vlastnosti (stupně vrcholů, velikost klik, průměr, ...). Pokuste se z grafových vlastností odvodit vztahové vlastnosti - např. kdo je oblíbený, kdo je neoblíbený. Pokročileji je možné se zabývat vývojem sociální sítě v čase.

Implementace sociální sítě. Implementujte jednuchou sociální síť formou webového rozhraní. Hlavní funkcí, kterou by sociální síť měla umožňovat, je uzavírání "přátelství" s dalšími uživateli. Lze se také zabývat otázkou, jaké další vztahové operace by síť měla umožňovat, aby se stala uživatelsky atraktivní.

Glass Facade Reflections. Jedná se o grafické téma. Cílem je vypracovat fotorealistický rendering se zaměřením na budovy s převážně skleněnou s fasádou (mrakodrapy). Jako osvětlení se předpokládá ozáření slunečními paprsky s případnými odrazy od fasád. Pokročilejší technikou by mohlo být zapracování efektů na čočce objektivu (lens flare).

Automatický výtvarník. Navrhněte systém, který bude automaticky komponovat (vizálně hezký) obraz. Seznamte se se základními pravidly výtvarné kompozice a zabudujte je do automatického systému. Pro vyřešení případných kombinatorických podúloh lze využít některého z existujících systémů pro řešení SAT či CSP. Použitelnost automatického výtvarného systému se předpokládá zejména v oblasti abstraktní malby (viz. Vasilij Kandinskij).

Automatický hudebník. Navrhněte systém, který bude automaticky skládat (poslouchatelnou) hudbu. Prozkoumejte melodická pravidla a možnosti kompozice melodie. Jako podkladový řešící systém pro kombinatorické zpracování úlohy je možno využít některý z existujících SAT či CSP řešících systémů.

ASP - Answer Set Programming. Zvolenou úlohu modelujte jako ASP instanci a použijte k jejímu řešení nějaký z existujících systémů pro ASP. Téma lze zpracovat též rešeršním způsobem, tedy porovnat možnosti modelování a řešení úloh pomocí ASP s alternativními přístupy, tj. např. s CSP (Problém splňování podmínek - Constraint Satisfaction Problem) či s ILP (Celočíselné programování - Integer Linear Programming).

Optimalizace parametrů (PbO - Programming by Optimization). Mějme jistý řešící systém (např. SAT řešič), který může se zadáním instance problému k řešení obdržet také určité parametry (např. periodu restartu). Naším cílem je najít hodnoty parametrů tak, aby s nimi řešič běžel co nejefektivněji na zvolené podmnožině instancí problému (např. na instancích kódujících plánovací problémy). Chceme tedy obecný řešit pomocí vhodné volby parametrů natrénovat na specifické instance. Téma má různé možnosti rozpracování: lze vzít existující řešič a optimalizovat jeho parametry, lze ale také cíleně navrhovat řešič s mnoha parametry včetně alternativního kódu pro následnou optimalizaci.

Mapa oblohy II. Jaký je pohled na hvězdy a planety z Europy* či z 51 Pegasi b+? Vytvořte program, který takové pohledy zprostředkuje. Program by měl umět zobrazovat známé hvězdy a planety Sluneční soustavy. Dále by měl uživateli umožnit specifikovat nejen místo pozorování, ale také čas, kdy němu dochází.
*Europa - jeden z mnoha měsíců planety Jupiter. Společně s měsíci Io, Ganymed a Callisto tvoří tzv. Galileovy měsíce, objevené Galileo Galileim v 17. století.
+51 Pegasi b - první objevená exoplaneta obíhající běžnou hvězdu. Objev byl uskutečněn v roce 1995.

On-line Article. Navrhněte systém pro vytváření on-line odborných článků v informatice. Odborné články v informatice často ukazují výsledky experimentů pomocí tabulek a grafů, přičemž vstupní data pro tyto tabulky a grafy bývají generována testovaným programem. V případě, že je vytvořena nová verze testovaného programu, článek automaticky zastará. Cílem systému pro on-line články je tento problém překonat automatickou aktualizací tabulek a grafů v článku vždy, když se objeví nová verze testovaného programu. Zároveň by bylo zajímavé umožnit prohlížení minulých verzí článku. Předpokládá se, že článek bude zobrazován jako webová stránka s příslušnými ovládacími prvky.

On-line řešič CSP/SAT/Plan. V rámci toho tématu bychom chtěli vytvořit on-line systém s webovým rozhraním pro řešení problémů SAT, CSP, nebo plánovacích. Cílem zde není vytváření samotného řešiče daného typu problému, nýbrž integrace již existujícího řešiče či více řešičů s webovým rozhraním a běhovým prostředím serveru. Webové rozhraní by sloužilo k interakci s uživatelem a bylo by nejspíše tvořeno webovou stránkou umožňující zadání instance problému a provedení souvisejích nastavení. Běhové prostředí by obstarávalo výběř a spuštění řešiče pro zadanou instanci a přidělení výpočetních zdrojů. Při výběru a spouštění řešiče lze využít poznatků z minulých běhů (např. lze detekovat v minulostí již řešenou instanci).

DPLL/CDCL(CSP). Kombinací řešícího systému pro booleovskou splnitelnost (SAT) - DPLL/CDCL, tedy klasického SAT řešiče řízeného konflikty s učením, a systému pro řešení omezujících podmínek (CSP) bychom mohli získat systém se zajímavými vyjadřovacími schopnostmi. Bylo by možné formulovat zobecněný CSP problém, kde nepožadujeme splnit všechny podmínky, ale nějakou jejich booleovskou kombinaci (např. chceme, aby platily podmínky c1 a c2 nebo podmínky c2 a c3). SAT řešič by se v takovém systému staral o splnění booleovské struktury podmínek a CSP řešič by kontroloval, zda podmínky vybrané SAT řešičem ke splnění lze skutečně splnit.

Ztlumovač reklamy (obrazový). Navrhněte systém, který bude sledovat obrazový signál nějakého média (tedy televize) a bude schopen identifikovat výskyt reklamního spotu a následně provést uživatelem definovanou akci (např. ztlumit zvuk).

Ztlumovač reklamy (zvukový). Úkolem je navrhnout systém, který bude sledovat zvukový signál nějakého média (např. rozhlasu nebo televize) a bude schopen identifikovat výskyt reklamního spotu a následně provést uživatelem definovanou akci (např. ztlumit zvuk).

Obrázkový google II. Cílem je navrhnout program, který bude vyhledávat bitmapové obrázky na základě podobností (prostor, kde bude vyhledávání probíhat, může být lokální disk či internet). Součástí problému je i návrh rozhraní, s jehož pomocí uživatel specifikuje hledaný obrázek.

Obtížné instance SATu. Předmětem zkoumání v rámci tématu jsou postupy na generování formulí, jež jsou obtížné pro moderní systémy pro řešení booleovské splnitelnosti (SAT řešiče). Základní otázkou například může být, jak vypadá formule (tedy instance SATu) s daným počtem výrokových proměnných, pro kterou daný řešící systém běží co nejdelší dobu než rozhodne. Přitom by ze znalosti konstrukce formule mělo být zjistitelné, zda je splnitelná či nikoli, případně jak vypadá splňující ohodnocení proměnných. V rámci tématu lze implementovat příslušný generátor, který bude parametrizován SAT řešičem. Výsledné těžko rozhodnutelné formule mohou rozšířit současné sady testovacích SAT instancí.

Aritmetika v SATu. Aritmetické operace (sčítání, násobení, atd.) a relace (rovnost, větší, atd.) lze zavést nad bitovými vektory. Pravdivost či splnitelnost výroků nad celými čísly obsahující celočíselné aritmetické operace a relace lze pak aproximovat pomocí pravdivosti a splnitelnosti odpovídajících výroků na bitovými vektory (např. můžeme zkoumat pravdivost výroku x + y = y + x nad celými čísly, tuto otázku aproximujeme zkoumáním pravdivosti výroku xb +b yb = yb +b xb nad bitovými vektory, kde xb a yb jsou řekněme 8-bitové neznaménkové vektory a +b je 8-bitové neznaménkové sčítání). Podstatnou výhodou je, že rozhodovací otázky týkající se bitových vektorů lze kódovat jako úlohu booleovské splnitelnosti (SAT), přičemž je pak možné využít řešící systémy pro SAT. Předmětem zkoumání v tomto tématu mohou být způsoby kódování výroků s bitovými vektory vhodné pro moderní řešící systémy pro SAT. Dále je možné vytvářet systém pro automatické kódování výroků s bitovými vektory.

Konkrétní řešící programy. Představme si nějakou relativně obtížnou úlohu (například plánovací problém, CSP instanci, SAT instanci, atp...). Běžný přístup k řešení takové úlohy je napsat program, který načte zadání úlohy a pak úlohu nějakým standardním způsobem řeší (například prohledáváním). Zkusme se zamyslet nad jiným přístupem: uvažujme program, který načte zadání úlohy, ale místo, aby úlohu přímo řešil, sestaví řešící program pro dané konkrétní zadání - konkrétní řešící program. Konkrétní řešící program může být založen na standardním řešícím postupu, jaký by se použil běžně. Dovoluje však jiný programátorský styl - řídící a datové struktury konkrétního programu mohou být velmi specifické a tudíž efektivnější (například větvení programu může být jednodušší, neboť o konkrétním zadání úlohy lze odvodit, že některé případy nikdy nenastanou; místo obecných datových struktur lze používat hashovací tabulky, atd...). Konkrétní řešící program lze dále transformovat směrem k vyšší efektivitě pomocí existujících kompilačních technik a částečného vyhodnocování (například lze vyhodnocovat výrazy pro konkrétní konstanty, lze optimalizovat větvení, lze použít agresivnější vkládání (inlining), atd.). Vzhledem k tomu, že výsledný konkrétní řešící program je na závěr nutno přeložit a pak teprve spustit, přínos uvedené techniky se dá očekávat spíše u obtížných úloh, kde je čas kompilace zanedbatelný vzhledem k času řešení.

Zobecnněná posuvná skládačka (generalized sliding box puzzle). Uvažme zobecnění hry Lloydova patnáctka (viz. následující téma - přečtěte nejdříve, pak pokračujte zde). Hra se bude odehrávat na obdelníkovém hracím poli velikosti n x m, kde n a m jsou přirozená čísla. Na hracím poli budou rovnoběžně s okraji hrací plochy položeny obdélníkové kameny tak, že se vzájemně nepřekrývají a vrcholy (rohy) kamenů budou na celočíselných souřadnicích vzhledem k počátku (levému dolnímu rohu) hracího pole. Délka a šířka hracích kamenů jsou přirozená čísla. Kámen je možno posunout o celočíselnou vzdálenost v horizontální nebo vertikální ose, pokud v tomto posunutí nepřekáží jiný kámen. Úkolem je přeuspořádat kameny z dané počáteční konfigurace do dané cílové konfigurace. Snažme se minimalizovat počet tahů. Řešící systém pro tuto úlohu již existuje (SBPSolver 1.6), překonejte jej ve zvoleném kritériu (čas na řešení, kvalita řešení).

Lloydova patnátcka. Návrh algoritmů pro řešení hry Lloydova patnáctka (shoda jmen u dalšího tématu je čistě náhodná). Jedná se o hru s patnácti očíslovanými kameny na čtvercovém poli 4 x 4 míst, kde jedno místo je volné. Vždy je možné přesunout kámen na sousední volné místo. Cílem je dosáhnout zadané cílové konfigurace kamenů (například po řádcích seřazené od 1 do 15). Navrhněme řešící algoritmus tak, aby se snažil minimalizovat počet kroků nutných k řešení. Zkoumejme obecnejší varianty - větší hrací pole a více volných míst.

Mrakodrap až do nebe. Navrhněte software pro určení maximální výšky mrakodrapu, který lze postavit s použitím současných stavebních a (hlavně) výtahových technologií. Vhodným přístupem k řešení by mohla být například simulace provozu mrakodrapu (pohyb lidí v rámci budovy), přičemž nedostatečná průchodnost budovy by indikovala dosažení limitní výšky. Toto téma má nejrůznější modifikace - lze se zabývat návrhem výtahové soustavy, dá se experimentovat s tvarem budovy (směrem k vrcholu se budova zužuje), lze uvažovat o různém způsobu využívání jednotlivých částí mrakodrapu atd... Pro inspiraci: Frank Lloyd Wright v roce 1956 navrhl mrakodrap vysoký 1600m (Mile High Illinois).

Vševysvětlující teorie. Celulární automat je formální systém, který v jedné ze svých variant vypadá jako čtvercová síť nekonečné velikosti, kde každá buňka této sítě se nachází buď ve stavu rozsvíceno nebo ve stavu zhasnuto (formálněji tedy buď ve stavu 1 nebo ve stavu 0). Každé buňce sítě je přiřazena přachodová funkce (všem buňkám stejná), která prvku kartézského součinu možných stavů buněk z jistého nevelkého okolí dané buňky přiřazuje stav. Celý automat funguje tak, že se v každém kroku změní synchronně stavy všech buněk podle přechodové funkce (tj. všechny buňky se mění najednou). Někteří lidé si myslí, že by se dal sestrojit celulární automat, který simuluje veškeré fyzikální zákony, či, že by pomocí celulárního automatu bylo možné simulovat celý vesmír (pak by ovšem bylo možné říct, že vesmír je celulární automat). Tak daleko my nepůjdeme. Spokojíme se návrhem celulárního automatu, který simuluje počítač nebo alespoň některé počítačové součástky (paměť, řídící jednotka, hodně zde záleží na interpretaci pojmů). Téma je vhodné pro "experimentátory".

Perspektiva versus Predátor. Chtěli bychom vytvářet neviditelné předměty metodou perspektivního klamu. Je dán předmět poměrně jednoduchého tvaru - například kvádr nebo krychle. Tento předmět je umístěn v nějakém prostředí - v interiéru či v exteriéru. Dále je zadáno pozorovací místo. Vhodným potapetováním fotografickou tapetou lze daný předmět zamaskovat tak, že při pozorování z daného pozorovacího místa bude splývat s pozadím (tj. nepozorný pozorovatel si jej nevšimne). Navrhněte program pro vytváření zneviditelňovacích tapet.

Fotolab KGB. Představme si, že chceme vyfotografovat architektonicky cennou budovu, avšak v záběru se nachází nežádoucí osoba či předmět. V takovém případě by se uplatnil program, který umí z pořízené fotografie nežádoucí osobu nebo předmět odstranit a nahradit jej odpovídajícím pozadím tak, že na výsledné fotografii nejsou patrné žádné úpravy (alespoň ne na první pohled resp. pro neodborníka).

SAT. Je dána Booleovská formule (proměnné mohou mít hodnotu pravda nebo nepravda) v konjunktivním normálním tvaru (konjunkce disjunkcí literálů, kde literál je proměnná či negace proměnné). Pro formule v tomto tvaru se používá ustálený formát souborů s příponou .cnf. Na následujícím odkazu je příklad: logistický problém. Napište řešič, který vezme soubor ve formátu .cnf jako vstup a nalezne splňující ohodnocení v něm obsažené formule nebo prokáže, že formule nemá žádné splňující ohodnocení. Téma je vhodné pro pisatele efektivních programů.

F1 Grand Prix - Optimální zastávky. Představme si, že chceme naplánovat optimální okamžik pro zastávky na výměnu pneumatik a doplnění paliva během závodu F1 GP pro vozy naší stáje. V takové situaci je velmi důležité, aby se náš vůz při návratu na trať nepřipletl za méně výkonné jezdce a vozy, což by nás mohlo stát cenné desetiny sekund. Je známa výkonnost ostatních monopostů účastnících se závodu, rovněž jsou známy určité základní technické charakteristiky monopostů jako je spotřeba paliva, zpomalení způsobené větším množstvím paliva v nádrži atd... Simulujte průběh závodu a na základě této simulace navrhněte optimální zastávkovou strategii pro váš tým.

F1 Grand Prix - Optimální stopa. Jsou dány charakteristiky monopostu F1 do jisté úrovně detailů (rozměry, hmotnost, akcelerace, přilnavost pneumatik, aerodynamický přítlak, výkon brzdového systému, atd...). Dále je zadán okruh s charakteristikami do jisté úrovně detailů (minimálně je znám tvar okruhu a šířka vozovky, detailněji může být znám i výškový profil, kvalita povrchu, atd...). Pro monopost a okruh je cílem nalézt optimální průjezd okruhem, přičemž monopost se musí při tomto průjezdu udržet na trati. Optimalizujeme vzhledem k času na jeden kolo. Intuitivně tedy hledáme stopu, ve které může jet monopost v průměru co nejrychleji.

Cesta pro robota. Hledání cesty pro robota mezi geometricky zadanými překážkami (trojúhelníky, polygony, kruhy, ...) v rovině. Je zadáno počáteční a cílové místo pro robota, rozměry robota (lze i tvar). Cílem je najít cestu z počátečního místa do cílového místa tak, aby přitom robot nenarazil do žádné překážky. Lze dělat i variantu bezpečné cesty, tj. cesty, kdy se robot překážkám vyhýbá v co největší vzdálenosti.