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)

Filip Beskyd, Satisfiability in Artificial Intelligence Problem Solving, since 2021. Vojtěch Rybář, Agent-based Modeling in Domains with Complex Movement of Multiple Entities, since 2020. Jiří Švancara, Multi-agent Path Finding, co-supervision, defended 2020. Eliška Hejlová, Computer Aided Teaching of Spatial Geometry, cancelled 2015. Tomáš Balyo, Modeling and Solving Problems Using SAT Techniques, co-supervision, defended 2012.

Graduate (master theses)

Yana Zabrodskaya, Multi-agent Path Finding with Continuous Time via Integer Linear Programming, since 2021 Petr Švec, Constraint Programming for Service Scheduling in a Garage, since 2021 Zuzana Fílová, Lazy Compilation in Classical Planning, defended 2022 Martin Čapek, DPLL(MAPF): Integration of a SAT Solver and Multi-Agent Path Finding, defended 2022 Kristián Kuĺka, Generalization of the Pac-man Game from the Perspective of Turn-based Game Algorithms, since 2020 Petr Nešpůrek, Learning of Locally Controlled Agents in the Pac-Man Game, defended 2022 Ondřej Marek, Drone Aerial Display, defended 2022 Klára Dvořáková, Automated Planning for Warehouse Logistics, defended 2021 Filip Beskyd, Parameter Setting in SAT Solver Using Machine Learning Techniques, defended 2020 Ondřej Pleticha, Centralized Planning of Autonomous Traffic, defended 2020 Jindřich Kuzma, Simulation of Autonomous Road Traffic, since 2019 Ondřej Černý, Algorithms of Defense Against Flying Drones from the Perspective of Game Theory, since 2019 Ondřej Majerech, Multi-agent Path Finding in Dynamic Environments, defended 2017 Jiří Švancara, Multi-agent Path Finding in Unidirectional Environments, defended 2016. Marika Ivanová, Adversarial Cooperative Path-Finding, defended 2014.     Second place in the national competition of the Union of Czech Mathematicians and Physicists 2014 Josef Talaš, Content-based Image Search, Master thesis, defended 2014. Petr Michalík, Sub-optimal algorithms for solving sliding puzzles, defended 2011. Tomáš Balyo, Design of an efficient SAT solver, defended 2010.

Undergraduate (bachelor theses)

Vladislav Beneš, Robot Planning for Reconfigurable Warehouse, since 2021. Tomáš Holas, Multi-agent Path Finding with Production and Consumation of Agents, since 2021. Jakub Votrubec, Interactive Environment for Testing of Formation Maintenance in MAPF, since 2021. Martin Rameš, Compilation of Multi-Agent Collective Construction in the Minecraft Game, since 2020. Jan Czakoj, Using Machine Learning-based SAT Solver for Multi Agent Path Finding, since 2020. Petr Michalíček, Disjoint Pathfinding in Non-Planar Environments, defended 2021. Ladislav Miklík, Continuous Motion Planning for Autonomous Vehicles at an Intersection, since 2020. Lukáš Kameník, Multi-agent Path Finding for Dynamic Goals in a Generalization of the Pac-man Game, defended 2021. Silvestr Láník, Robot Localization During Execution of Multi-Agent Path Finding Plans with OZOBOTs, since 2020. Marek Nevole, Local and Systematic Algorithms for Solving Generalized Variants of Sudoku, defended 2021. Patrik Schweika, Discrete Simulation of Automobile Traffic with Continuous Time, defended 2021. Tomáš Valenta, Local Coordination and Planning for Robotic Soccer, defended 2021. Vít Šprachta, Hierarchical Coordination of a Multi-robot Construction Team in the Minecraft Game, defended 2021. Kristýna Janovská, Hierarchical Control of Swarms during Evacuation, since 2020. Petr Šindlář, Pathfinding and Target Assignment in a Generalization of the Pacman Game, since 2020. Adam Beckert, Automated Music Generation, defended 2021. Evgenii Abdalov, Visual Analysis of Plans for Multi-Agent Path Finding with Continuous Time (MAPF-R), defended 2020. Jan Lidák, Formation Maintenance in Multi-Agent Path Finding, since 2020. Yana Zabrodskaya, Resolving Collisions among Geometric Robots in Continuous Space, defended 2020. Nestor Popov, Compilation of Path Finding Algorithms for a Group of Small Mobile Robots, defended 2020. Ján Chudý, Simulation of Cenralized Algorithms for Multi-Agent Path Finding on Real Robots, defended 2020. Dominik Šmejkal, Controlling Mobile Agents by Finite Automata in Adversarial Scenenarios, defended 2020. Berker Katipoglu, Adapting the Conflict-based Search Algorithm for Alternative Objectives, defended 2020. Martin Zukal, Multi-agent Path Finding for Connected Robots, defended 2020. Radka Bodnárová, Simulation of Traffic Control for Autonomous Vehicles, 2019, cancelled 2019. Vojtěch Cahlík, Application of Artificial Neural Networks in Solving the (N^2-1)-Puzzle, defended 2020. Dominik Knežour, Sentiment Analysis in Czech Texts, since 2018. Róbert Selvek, Evacuation Planning Based on Local Cooperative Pathfinding Techniques, defended 2019.     Honorable mention at the national competition of the Union of Czech Mathematicians and Physicists 2019 Tomáš Vlk, Benchmarks for Multi-Agent Path Finding, defended 2019. Zuzana Filová, Processing and Editing the Outputs of Automated Music Transcription, defended 2019. Zdeněk Šimůnek, Adversarial Multi-agent Path Finding - Hierarchical Heuristics, since 2018. Filip Beskyd, Prediction of Dota 2 Game Result, defended 2018. Jakub Střelský, Automated Generation of Realistic Terrain Using Machine Learning Techniques, defended 2016.     First place at the national competition of the Union of Czech Mathematicians and Physicists 2016 Tran Tuan Hiep, Text Recognition in Natural Scenes, defended 2015. Milan Ježek, Modeling of Cooperative Path Finding, defended 2015. Miloš Chromý, Improvement of the BIBOX Algorithm, defended 2013. Jakub Vlček, Recognition and Filtration of Unwanted Video-Sequences, defended 2013. Václav Obrázek, Coordinated pathfinding with formations, defended 2013. Filip Stočes, Visualization of plans for logistics tasks, defended 2011. Ivana Lukšová, Bitmap picture classification, defended 2010. Jakub Kýpeť, Computer poker, defended 2010. Martin Petr, Handwriting recognition using neural network, defended 2010. Vojtěch Bardiovský, Generating of self-replicating cellular automata, defended 2010. Petr Koupý, Visualization of problems of motion on a graph, defended 2010. Martin Ščavnický, Automated prediction of results of tennis tournaments, defended 2010. Josef Pihera, Data archiving using longest common subsequence, defended 2010. Radovan Duga, Erasing Disturbing Objects from Digital Pictures, defended 2009. Martin Galajda, Algorithms for Solving the Sokoban Game, defended 2009. Ondřej Malý, Software for Modeling Car Driving Properties, defended 2008. Tomáš Balyo, Efficient Boolean Satisfiability Solver, defended 2008. Štefan Čudai, Multiagent Traffic Control System, defended 2007. Martin Langhammer, Train Traffic Simulation with Optimization, defended 2007. Attila Ulman, Emergence of Intelligent Behavior of Social Insects, defended 2007. Kristýna Bémová, Computer-aided Teaching of Spherical Geometry, defended 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.

Student Awards

SVOČ 2021 first place for a bachelor thesis by Ján Chudý under my supervision Competing work: Simulation of Centralized Algorithms for Multi-Agent Path Finding on Real Robots Award given by: The Union of Czech Mathematicians and Physicists. Category: I1+I2 Computer Science + Artificial Intelligence   Dean's Award 2019 for a bachelor thesis by Zuzna Fílová under my supervision Competing work: Processing and Editing the Outputs of Automated Music Transcription Award given by: Faculty of Information Technology, Czech Technical University.   Dean's Award 2019 for a bachelor thesis by Róbert Selvek under my supervision Competing work: Evacuation Planning Based on Local Cooperative Pathfinding Techniques Award given by: Faculty of Information Technology, Czech Technical University.   SVOČ 2019 honorable mention for a bachelor thesis by Róbert Selvek under my supervision Competing work: Evacuation Planning Based on Local Cooperative Pathfinding Techniques Award given by: The Union of Czech Mathematicians and Physicists. Category: I1+I2 Computer Science + Artificial Intelligence.   SVOČ 2016 first place for a bachelor thesis by Jakub Střelský under my supervision Competing work: Automated Generation of Realistic Terrain Using Machine Learning Techniques Award given by: The Union of Czech Mathematicians and Physicists. Category: I1+I2 Computer Science + Artificial Intelligence.   Dean's Award 2014 for a master thesis by Marika Ivanová under my supervision Competing work: Adversarial Cooperative Path-Finding Award given by: Faculty of Mathematics and Physics, Charles University.   SVOČ 2014 second place for a master thesis by Marika Ivanová under my supervision Competing work: Adversarial Cooperative Path-Finding Award given by: The Union of Czech Mathematicians and Physicists. Category: I1+I2 Computer Science + Artificial Intelligence.

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.

Computer Vision for RR1 | Počítačové vidění pro RR1. Zajímavou nadstavbu pro robotickou paži RR1 představuje počítačové vidění realizované pomocí jednoduché webové kamery. Do existující 3 vrstvé architektury robota (fyzický robot (RR1) <-> nízkoúrovňové řízení (Arduino) <-> vysokoúrovňové řízení (PC)) je relativně snadné počítačové vidění integrovat, a sice zapojením kamery do 3. vrstvy řídícího softwaru běžícího na PC. Předpokládáme, že bychom pomocí kamery identifikovali určitý objekt v sadě objektů a ten by následně robot uchopil. Současně s identifikací objektu by proběhlo odpovídající plánování a vykonávání pohybu, případně složitější interakce mezi identifikací objektu a plánováním a vykonáváním pohybu.

Sequential 3D-Printing | Sekvenční 3D-tisk. Běžný postup při 3D tisku je vykreslování všech objektů na tiskovém plátu po jednotlivých vrstvách najednou. Vezmeme-li v úvahu určitou pravděpodobnost selhání tisku, je tento postup při tisku více objektů najednou nevýhodný. Při selhání jsou totiž všechny tištěné objekty ještě nedokončené a tyto částečně vytištěné objekty jsou nepoužitelné. V případě tisku více objektů se zdá být výhodnější tisknout po vrstvách každý objekt zvlášť, což se označuje jako tzv. sekvenční tisk. Při sekvenčním tistku ale narážíme na problémy, protože je-li již vytištěný objekt dost vysoký může dojít ke kolizi s tiskovou hlavou případně s osou X. Proto je rozmístění objektů na tiskovém plátu vzhledem k sekvenčnímu tisku potřeba pečlivě rozvrhnout. Problém je ještě zajímavější vezmeme-li v úvahu 3D tiskárnu v meničem tiskových hlav (nástrojů), potom lze sekvenční tisk, resp. jeho zobecnění ve smyslu tisku ve více úrovních, lze použít ke snížení počtu výměn tiskových hlav a celkově tak tisk urychlit.

3D Object Embedding and Classification| Vkládání 3D objektů a jejich klasifikace. Jedná se o převod 3D objetků na vektor reálných čísel. Tedy klasická záležitost ze strojového učení, která je asi nejlépe známá pro slova jako technika word-2-vec, tedy zde se budeme snažit o jakýsi 3D-object-2-vec. Můžeme předpokládat vstupní zadání 3D objektu ve formě bodového mračna, volumetrickou reprezentací (např. oktantový strom) nebo ploškovou reprezentací (jako soubor .stl). Pravděpodobně půjde vektorovou reprezentaci 3D objektu získat nějakým auto-enkóderem, což se ale zdá být snadnou částí úlohy. Podstatné zřejmě bude, jak získat vhodný vstup pro auto-enkóder pomocí vhodného předzpracování vstupní reprezentace 3D objektu. Vložené vektorové reprezentace 3D objektů půjde následně použít pro klasifikaci a rozpoznávání.

3D-Print All at Once | 3D-tiskni všchno najednou (Object Arrangement on Print Sheet). Chceme 3D-tisk více bezoblužný, tj. vytisknout co nejvíce objektů najednou, tedy preferujeme jeden dlouhý tisk před několika kratšími, což znamená pouze jedno zahřívání tiskového plátu, případně jednu kalibraci první vrstvy. Tisk co nejvíce objektů najednou znamená jejich úsporné rozmístění na tiskovém plátu, přičemž v prvním přiblížení můžeme uvažovat pouze o 2D průmětech tištěných 3D objektů do roviny plátu, ty ale mohou být prakticky libovolné 2D útvary (konvexní, nekonvexní, atd.). Vezměme tuto úlohu jako optimalizační kombinatorický problém. Nabízejí se techniky CSP (constraint satisfaction) nebo COP (constraint optimization). Navíc se zdá, že roli bude hrát spojitý prostor tiskového plátu, tedy úloha pravděpodobně nebude čistě diskrétní. Při optimalizaci můžeme preferovat umístění objektů směrem ke středu tiskového plátu, což je výhodnější vzhledem k možnostem vyhřívání.

Advanced Trajectory Planning for 3D Printers | Pokročilé plánování trajektorií pro 3D tisk. Problém naplánování trajektorie pro tiskovou hlavu 3D tiskárny představuje zajímavý optimalizační problém podobný variantám problému obchodního cestujícího (Travelling Salesman Problem - TSP). V případě 3D tiskárny do hry vstupují další zajímavé vlastnosti, jako je spojitost prostoru, kde trajektorii plánujeme, různé technické parametry tiskárny, jako je zrychlení/zpomalení, nebo vlastnosti tištěného objektu resp. jeho částí, jako je důraz na kvalitu tisku okraje menší důraz na kvalitu vnitřku atd.. Na obrázku je tiskárna Prusa XL s více tiskovými hlavami, která činí problém ještě zajímavějším, protože je potřeba brát v úvahu výměny tiskových hlav pro tisk různých částé objektu různými materiály (typicky různými barvami). Z hlediska řešení problému je nutno vzít v úvahu i uživatele, který nebude čekat na vyřešení problému několik hodin, ale bude chtít zahájit tisk co nejdříve. Přístupy založené na prohledávání kombinatorického prostoru je tedy nutné používat jen v rozumné míře.

Quantum MAPF | Kvantový MAPF. Současná vyjádření úlohy multi-agentního hledání cest (multi-agent path finding - MAPF) jako výrokové splnitelnosti (SAT) zejména v líných modelech typu CEGAR dosahují relativně značné úspornosti. V této souvislosti se ukazuje jako zajímavé uvažovat o vyjádření MAPF ve formalismech vhodných pro kvantové počítání. Například formalismus QUBO (quadratic unconstrained binary optimization), kterým lze vyjadřovat úlohy pro model kvantového počítače využívajícího kvantové žíhání (quantum annealing), se zdá pro MAPF vhodný. Jak ale název QUBO napovídá, nebude vyjadřování omezení (constraints) známých z výrokových modelů pro MAPF přímočarý, což představuje hlavní výzvu v tomto tématu.

Kido Butai byla obávaná japonská mobilní úderná skupina složená z letadlových lodí a palubního letectva. Inspirujme se nikoli ničivou silou tohoto uskupení, ale letectvím a mobilitou. V naší Laboratoři robotických agentů (RoboAgeLab) máme leteckou skupinu dronů, ovšem vázanou na pevně instalovanou voliéru s lokalizačním systémem. Cílem v tomto tématu je naší letecké skupině dronů přidat mobilitu, tedy abychom mohli létat i mimo laboratoř. Nebudeme ovšem stavět letadlovou loď pro drony, ale spíše se zaměříme na konstrukci mobilního (přenosného) lokalizačního systému. Využít můžeme například 3D-tisk ke zhotovení různých fixačních a transportních pomůcek.

Lazier Lazy Compilation | Línější líná kompilace. Současná líná kompilace, ať už pro multi-agentní hledání cest (MAPF), nebo klasické plánování, nekóduje do cílového formalismu určitý vybraný typ omezení - v případě MAPF se jedná o kolize, v případě klasického plánování se jedná o vzájemná vyloučení (mutexy). Co kdybychom línou kompilaci udělali ještě línější, tj. kódovali bychom ještě méně omezení, v krajním případě žádná omezení a řešič pro cílový formalismus by tak začínal pouze s rozhodovacími proměnnými? V tomto krajním případě by tak líná kompilace postupně automaticky vytvářela kódování problému v cílovém formalismu. Pojďme tyto otázky prozkoumat podrobněji.

1000-times Faster SMT-CBS | 1000-krát rychlejší SMT-CBS. Toto téma je čistě technicky-programátorské. Cílem je reimplementovat algoritmus SMT-CBS, tedy algoritmus pro multi-agentí hledání cest (MAPF) založený na liné kompilaci do výrokové splnitelnosti, tak, aby byl 1000-krát rychlejší, než je současná autoská implementace v C++ (100 násobné urychlení, nebo 10 násobné by také bylo dobré). Současná autorská implementace například používá obecné datové struktury z STL, což by bylo možné nahradit speciálními datovými strukturami.

Multi-drone Mapping | Multi-dronové mapování. Otázka mapování pomocí létajícího drona je klasickou úlohou, ve které se spojuje plánování, lokalizace, případně rozpoznávání. Zde bychom se chtěli speciálně zaměřit na využité více dronů najednou, což může výrazně pomoci rychlosti zmapování určité oblasti, ovšem na druhou stranu se tím značně zkomplikuje koordinace mezi drony a plánování, které se stává multi-agentním. Zdá se, že plánování v tomto problému musí mít silnou zpětnou vazbu od rozpoznávávání, tedy musí reagovat na nově zjištěné skutečnosti (na objevení nezmapované části oblasti může plánovací modul reagovat naplánováním vyslání drona do této nezmapované části).

Any-angle MAPF | Všesměrové multi-agentní hledání cest. Uvažujme klasickou úlohu multi-agentního hledání cest (MAPF) nikoli však v diskrétním grafu, ale v nějakém euklidovském prostoru. Je tu navíc rozdíl oproti někde níže uvedené variantě spojitého MAPF, zde ani nemáme graf, který by do euklidovského prostoru (2D rovina, 3D prostor) byl vložen a agenti se pohybovali mezi pozicemi odpovídajícími vrcholům grafu. Zde se agenti mohou pohybovat úplně volně ve všech směrech. Pro úspěšné vyřešení úlohy zřejmě bude potřeba přijmout určitá omezení, ale chtěli bychom se obejít bez vkládání grafu. Zajímavou otázkou je i detekce neexistence řešení pro tuto variantu MAPF (ostatně toto je otázka i pro níže uvedenou spojitou variantu).

Multi-head 3D Printer | Multi-hlavová 3D tiskárna. Představme si super skvělou FDM 3D tiskárnu (strunovou/filamentovou), která má několik tiskových hlav na robotických ramenech. Například si představujme více než 2 hlavy a méně než 10 hlav. Hlavní otázkou je naplánovat efektivní pohyb hlav při tisku, přičemž musíme dbát na to, aby mezi hlavami nedošlo ke kolizím a jiným nepříjemnostem, jako je třeba zamotání filamentů. Můžeme uvažovat i o tom, že tisknutý model není na klasické podložce, ale na podložce, která se může libovolně pohybovat, tj. podložkou pohybuje další robotické rameno, případně ani podložka nemusí být přítomna a model je přímo upevněn na rameno. Zajímavou inženýrskou otázkou je samotný design tiskárny. Z hlediska plánování a plánování pohybu představuje výzvu návrh sliceru, tj. softwaru, který model k tisku pomocí tiskových hlav vykreslí ve 3D prostoru. Vzhledem k uvedeným zobecněním nemusí jít o klasické rozdělení modelu na 2D vodorovné vrstvy a jejich pokrytí 1D křivkami. V našem případě mohou být 2D vrstvy reprezentovány i různě zakřivenými plochami.

(Tactical) Planning for Turn-based Tactics (Laser Squad, U.F.O.) | (Taktické) plánování pro tahovou taktiku (Laser Squad, U.F.O.). Co kdybychom aplikovali techniky z teorie her pro tahové hry a z klasického plánování nikoli na klasické deskové hry ale na tahové taktické hry typu Laser Squad nebo U.F.O.: Enemy Unknown? Oproti deskovým hrám se taktické tahové hry vyznačují větším herním prostorem, což samo o sobě představuje výzvu pro vývoj nových technik. Taktické hry navíc často pracují s neúplnou informací, tj. o nepřátelské jednotce, která není pozorována žádnou naší jednotkou, nemáme informace a tuto neurčitost mohou obě strany využívat ve svůj prospěch. Pro zjednodušení můžeme uvažovat, že každá ze soupeřících stran má jednotky stejného typu, avšak ve větším počtu. Podobně jako ve hře U.F.O. lze pracovat i s nedeterminismem, tj. vykonání naplánované akce se nemusí podařit (střelba mine cíl).

(Strategic) Planning for RTS (Dune II, AoE, StarCraft) | (Strategické) plánování pro RTS (Dune II, AoE, StarCraft). Plánování pro real-time strategické (RTS) hry typu Dune II, Age of Empires nebo StarCraft stále představuje pro techniky plánování výzvu. RTS hra obsahuje rozhodování od strategické úrovně (například rozhodnutí o umístění základny, obranných prvků, zajištění zásobování surovinami) po plánování na mikro-úrovni (například plánování pohybu jednotek), pričemž každá úroveň rozhodování se vyznačuje principiálními odlišnostmi. Zatímco strategická úroveň spíše odpovídá herní teorii s uvažováním oponenta, plánování na mikro-urovni lze dokonce nahlížet jako klasické plánování bez oponenta. Vytvořit jakýsi hybridní hierarchický prístup, který by všechny úrovně integroval do funkčního celku by jistě bylo zajímavé.

Ozobot Screen-Hockey | Ozobotický hokej na obrazovce. Navigace a ovládání mobilních robotů Ozobotů při pohybu po povrchu obrazovky je již odzkoušená a docela dobře funguje. Na tomto principu by bylo možné vystavět robotický hokej. Fotbal Ozoboti nezvládnou - nedohoní míček, naproti tomu miniaturní puk, který příliš neklouže, se dá dohonit a zdá se, že by s ním měl robot zvládnout základní manipulaci - dotlačit puk do brány. Téma nabízí různé otázky: jak plánovat akce robotů a ohledem na tým protivníka, jak teoretický plán přenášet do realného světa, jak provádět lokalizaci robotů, jak reagovat na chybné vykonávání plánu, atd. Přirozeně tedy lze toto téma rozdělit na více dílčích projektů.

Automated Gearbox Design | Automatické vytváření převodů s ozubenými koly. Při konstrukci robota se vývojář dříve či později setká s potřebou vytvořit silné a přesné aktuátory, tj. pohony, které dávají do pohybu různé klouby. V návrhu aktuátorů se používají různé převody založené na ozubených kolech, jako je například planetový převod a tak podobně. Návrh převodů, tak abychom dosáhli dostatečné přesnosti a síly/točivého momentu, není jednoduchý. Pomozte vývojáři pomocí algoritmů, které budou převody navrhovat automaticky. Možná se podaří objevit nové uspořádání ozubených koleček a objevit tak automaticky nějaký inovativní aktuátor. Možná se podaří objevit podobně zajímavý pohon, jako je harmoický převod.

Crazy MAPF | Šílené hledání cest. Vyzkoušejte si spojitou variantu multi-agentního hledání cest (MAPF^R) v reálu, tedy přesněji na miniaturních dronech Crazylie. Budete se muset vypořádat s různými robotickými problémy, jako je lokalizace dronů a jejich ovládání v reálném čase podle vytvořeného plánu. Vytváření plánu rovněž představuje výzvu, neboť drony se budou pohybovat spojitě v trojrozměrném prostoru a zdá se tedy vhodné o spojitosti uvažovat již na úrovni vytváření plánu.

Curved MAPF | Zakřivený MAPF. Spojité varianty problému multi-agentního hledání cest (MAPF^R) zatím spoléhají na to, že agenti odvracejí srážku čekáním, tj. dávají přednost. Co kdybychom agentům umožnili větší volnost pohybu, tj. odvraceli bychom srážku spíše úhybným manévrem po nějaké hladké křivce, která agentovi umožní nezastavovat. Taková varianta MAPF by možná znamenala, že možné trajektorie agentů nebudou dány výčtem přímých spojic mezi význačnými pozicemi (vrcholy), ale množinou různých zakřivených spojnic. Bude třeba se zamyslet nad tím, jak v takovém případě bude definováno optimální řešení a jakým způsobem množinu možných spojnic omezit (množina všech hladkých křivek se přece jen zdá být příliš velká). Problém má široké aplikace v plánování pohybu pro mnoho robotů, neboť tam je vyžadován spíše plynulý pohyb bez zastavování kvůli omezení opotřebení robotů.

MAPF Spy | Špion na MAPF. Na rozdíl od většiny témat na multi-agentní hledání cest (MAPF), které jsou na této stránce uvedené, nemáme v rámci tohoto tématu v úmyslu vytvářet řešič, ale místo toho se budeme zabývat analýzu řešení/plánů, které nějaký řešič již vyprodukoval. Předpokládáme, že provádíme špionáž, tj. pozorujeme průběh vykonávání plánu MAPF a na základě pozorování se budeme snažit určit, jaké jsou cíle pozorovaných agentů. Můžeme například předpokládat, že pozorovaný plán je optimální vzhledem k nějaké účelové funkci, navíc lze předpokládat, že k danému okamžiku máme vždy plnou pozovatelnost plánu, který proběhl. Otevřenou otázkou je, jestli znalost použitého řešiče pomůže při analýze řešení.

SAT/SMT-based Collective Construction | Kolektivní konstrukce pomocí SATu a SMT. Problém kolektivní konstrukce mezi tématy již je, a sice jako téma "Stavitelé pyramid", zde ale chceme jeden konkrétní přístup k řešení. Současné optimální řešiče problému kolektivní konstrukce spoléhají na převod úlohy na smíšené celočíselné lineární programování (mixed integer linear programming - MILP). V rámci tohoto tématu bychom chtěli navrhnout alternativní přístup založený na převodu na logickou splnitelnost, výrokovou (SAT) nebo obecněji na SATem modulované teorie (SMT). Jak si povedou algoritmy založené na SAT/SMT vůči těm založeným na MILP?

Swarm Alert! Toto téma je aktualizací dřívějšího tématu Drone Alert!. Místo jednoho útočícího dronu předpokládáme útok celého roje dronů, který je koordinován tak, aby došlo k přetížení resp. vyčerpání protivzdušné obrany při minimalizaci vlastních ztrát. Lze se zabývat jak koordinací pohybu útočícího roje, tak koordinací protivzdušné obrany, která může být založena na vystřelování (neřízených) projektilů. Útočící roj může využívat skutečnosti, že protivzdušná obrana dokáže v určitém okamžiku sledovat jen omezený počet cílů, rovněž můžeme předpokládat, že projektil po zásahu cíle zanikne, tj. útočící drony se mohou za cenu vlastní oběti vzájemně krýt. U protivzdušné obrany je důležité určit její prostorové rozmístění tak, aby byla proti útoku efektivní.

Systém zachytávání pohybu svépomocí | Poor Man’s Motion Capture System. Než si budeme moci dovolit profesionální systém zachytávání pohybu (motion capture system, MoCap), musíme si vystačit svépomocí. Například můžeme použít několik webových kamer, nebo nějakých pokročilejších senzorů jako např. Intel RealSense, které však stále vycházejí podstatně levněji než profesionální MoCap. O software se postaráme sami a právě jeho vytvoření je podstatou tohoto tématu. Zvládnutí sledování mnoha pohybujících se značek bude tvořit základ lokalizace pro multi-robotický systém.

Multi-robotická lokalizace a mapování | Multi-Robot Localization and Mapping. Lokalizace a mapování predstavují základní problémy robotice, kdy jde o urcení polohy robota resp. o vytvorení mapy prostredí, ve kterém se robot pohybuje. V multi-robotickém systému úloha predstavuje zvláštní výzvu, vice robotu muže úkol zvládnout efektivneji, protože mohou být v prostoru rozptýleni a sdílet informace z ruzných míst. Zároven je ale koordinace vice robotu a spojování informací o ruzných místech prostredí složitejší. Varianty problému lze uvažovat od plne distribuované po centralizovanou.

Špionážní roj | Spy Swarm. Předpokládejme, že chceme automaticky plánovat pohyb a akce roje špionážních dronů. Každý dron je vybaven kamerou a autonomně vykonává předem spočítaný plán, což znamená provádění pohybu a pořizování fotografií/videa. Cílem je nasnímat určité území, přičemž na tento úkol mohou být kladeny různé dodatečné požadavky, jako například nasnímání některých míst opakovaně atd. Na výsledný plán budeme rovněž klást různé požadavky, například současný výskyt více dronů ve vzájemné blízkosti bude nežádoucí. Přirozeně také budeme chtít, aby byl špionážní úkol splněn co nejdříve atd.. Analogická úloha vzniká pri využití roje pro mapování pohybu divokých zvířat.

Výpočetní geopolitika | Computational Geopolitics. Je pro ekonomický a politický rozvoj lepší mít polohu jako USA nebo jako Čína? Je v některých částech světa pravděpodobná teritoriální expanze na základě současných ekonomických a geografických podmínek? Chtěli bychom na tyto otázky odpovídat automaticky a lépe než kvalifikovaný lidský expert. Pomoci nám v tom může zpracování většího objemu dat o současné situaci než je lidský expert schopen vůbec pojmout a simulace velkého množství scénářů budoucího vývoje. Klíčovou otázkou je návrh vhodného abstraktního modelu, který dostatečně detailně zachycuje ekonomicko-politické vztahy v kontextu geografických podmínek.

(Discrete Planning and Complex Acting) or (Continuous Planning and Simple Acting)? Je lepší plánovat v diskrétním prostoru a se spojitostí reálného světa se vypořádat až při vykonávání plánu na skutečném robotovi, nebo plánovat ve spojitém prostoru a pak docela jednoduše plán s robotem vykonávat? Otázka je, co způsobí větší komplikace, zda složitější plánování ve spojitém prostoru, nebo složitější vykonávání původně diskrétního plánu. Navíc lze jak na úrovni plánování, tak na úrovni vykonávání mezi spojitostí a diskrétností různě balancovat. Jako výchozí doména může sloužit multi-agetní hledání cest (MAPF), pro nejž spojité i diskrétní plánovače existují.

Drone Display | Dronová vzdušná obrazovka. Název tématu je samovysvětlující, jedná se o vytváření displeje/obrazovky, kde jednotlivé pixely jsou tvořeny barevně svítícimi létajícími drony. Na rozdíl od běžné ploché obrazovky tedy máme pixely prostorově rozložené ve třech rozměrech, a navíc, což je to hlavní, se pixely mohou pohybovat. Možnost současného pohybu a změny barvy pixelů jistě umožní zajímavé vizuální efekty. Hlavní otázkou je automatizace plánování pohybu pixelových dronů v součinnosti s jejich barevným světelným projevem.

Automated Dogfight | UI pro manévrový vzdušný souboj. Umělá inteligence v roli stíhacího pilota je aktuální téma. Cílem je navrhnout automatické řízení stíhacího letounu a vedení manévrového vzdušného souboje. Základní varianta problému počítá s jedním protivníkem, lze ale uvažovat i ovládání několika strojů proti více strojům protivníka. Téma souvisí s plánováním pohybu se speciálním zřetelem na letové vlastnosti moderního stíhacího letounu. V rámci tématu je třeba se zabývat i simulací stíhacího letounu alespoň s určitým zjednodušením.

Stavitelé pyramid | Pyramid Builders. Pokusíme se odpovědět na notorickou otázku "Jak se stavěly pyramidy?". Ovšem z multi-robického hlediska. Máme mnoho robotů stejného typu a kamenolom, kde jsou produkovány kamenné kvádry, pro zjednodušení budou kvádry stejného typu. Roboty mají uřčité omezené schopnosti, mohou se pohybovat, vézt jeden kvádr, položit kvádr. Stavba do výšky je realizována tím, že robot může i s naloženým kvádrem vystoupat na jiný kvádr, ale vystoupání je možné jen o jeden kvádr (dva kvádry na sobě už robot nepřekoná). Pokuste se navrhnout algoritmy, kterými bychom mohli činnost robotů efektivně plánovat, tak aby ve výsledku postavily pyramidu či jinou zajímavou stavbu. Lze se zabývat i leteckou variantou, kdy stavební kvádry převáží skupina dronů. Inspirace k tomuto tématu pochází z projektu TERMES.

Spojité multi-agetní hledání cest s bezejmennými agenty | Continuous Multi-Agent Path Finding with Anonymous Agents (Anonymous MAPF^R). Multi-agentní hledání cest lze řešit pro spojitý případ (MAPF^R). Jednotlivé agenty v základní variantě úlohy rozlišujeme (mají jména). Co když mezi jednotlivými agenty, kteří mají stejný vlastnosti (tvar, rychlost, ...) přestaneme rozlišovat, stanou se bezejmennými? Pokuste se navrhnout řešící algoritmy pro tuto variantu úlohy. Dojde oproti původnímu MAPF^R k nějakému zjednodušení? V diskrétním případě lze použít analogii v toky v sítích. Existuje podobná analogie i ve spojitém případě?

Skladová robotická anarchie | Warehouse Robotic Anarchy. Uvažujme sklad, kde roboty převážení zboží (pro názornou představu viz. například sklad Amazon). Současný přístup je takový, že sklad má pevnou dispozici (půdorys) s místy pro zboží a volným prostorem pro manipulaci. Chceme-li být striktní, můžeme určit také, kde které zboží má být uskladněno. Zdá se výhodné umisťovat často převážené zboží blízko cílovému místu, případně rozhodnutí, kam zboží uložit, nechat na robotech resp. jejich řídícím algoritmu, aby to pro roboty bylo výhodné. Můžeme jít ještě dál, co když dáme robotům volnost v přetváření dispozice skladu? Pokuste se navrhnout algoritmy, které takové uvažování realizují.

Multi-Agent Hamiltonian Path Finding | Multi-agerní hledání hamiltonovských cest (MAHPF). V poslední době se objevuje mnoho více či méně bizarních variant problému MAPF (multi-agetní hledání cest, multi-agent path finding). Přidáme jednu užitečnou a teoreticky zajímavou. Stejně jako v MAPF máme roboty/agenty pohybující se po grafu a sice tak, že se nesmí srazit. Na rozdíl od standarního MAPF bude ale nyní úkol ne robotem/agentem dojít do cílového vrcholu, ale navštívít v libovolném pořadí alespoň jednou (nebo právě jednou) každý ze zadané množiny vrcholů. Každý robot/agent tedy provádí jakousi hamiltonovskou procházku po svých vrcholech. Problém lze nahlížet teoreticky (složitost), z hlediska polynomiálních algoritmů, nebo heuristického prohledávání, budeme-li se snažit najít v nějakém smyslu optimální řešení.

Drone Heroes | Drony-hrdinové. Algoritmy hledání obranných strategií proti leteckému útoku vedeného autonomními drony nebudou mít v dněšní realitě o aplikace nouzi. Předpokládáme, že útočící drony mají za úkol vniknout do cílové zóny a tam provést útok. Skupina útočících dronů může být heterogenní s tím, že některé drony mají velitelskou funkci a ovládají ostatní podřízené drony. Na straně obránce máme rovněž k dispozici autonomní drony, předpokládejme, že méně početnou skupinu než má útočník, přičemž dron útočníka můžeme zničit sebedestruktivní stážkou. Každá strana má k dispozici úplnou informaci o svých dronech, ale nikoli o dronech protivníka. Je například možné zkoumat strategie vedoucí k odhalení a zničení velitelského dronu útočníka.

Multi-pacmanovské plánování cest | Multi-Pacman Path Planning (MPPP). Budeme plánovat cesty 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. Duchové jsou problém sám o sobě, pro zjednodušení předpokládejme, že nejsou moc chytří. Vhodné pro všechny stupně: bakalář až doktor.

Multi-pacmanovské plánování s protivníkem | Adversarial Multi-Pacman Planning (AMPP). Jiná varianta multi-pacmanovského plánování nastane, když uvážíme, že duchové jsou kolektivně chytří a také důkladně plánují, jak Pacmany pochytat. V takové situaci už musíme úlohu chápat z hlediska herní teorie (podobně jako Dámu, Šachy, atd..) a uvažovat, co všechno proti nám může protivník podniknout. Pro duchy můžeme právem předpokládat, že mohou sdílet stejné místo (neplatí pro ně stejné omezení, jako pro Pacmany). Pro vyrovnání sil bude zřejmě vhodné uvážit větší počet duchů než v původní hře. Dalším zajímavým rozšířením může být uvažování veliteského ducha (přirozeně by to mohl být červený Blinky), který je-li aktivní, probíhá u duchů důkladné plánování, je-li snězen, duchové do jeho oživení propadnou v chaos. Téma lze pojímat jak z pohledu Pacmanů, tak z pohledu duchů. Vhodné pro všechny stupně: bakalář až doktor.

Vizualizátor pohybu robotů - jedno i multi | Robot Motion Visualizer - Single / Multi. Vývoji algoritmů na plánování pohybu geometrických robotů jak v jedno-robotickém, tak v multi-robotickém případě by pomohl vhodný vizualizátor. Tedy software, který v reálném čase pohyb robotů ve vybraných projekcích promítá, například ve 3D. Nutno však vzít v úvahu vizualizace robotů nejen v jejich pracovním prostoru (tedy typicky ve 3D), ale i zobrazení konfiguračních prostorů, které mohou mít mnohem více rozměrů. Téma lze pojmout softwarově nebo i kombinovaně, tj. řešit pomocí vizualizátoru výzkumnou otázku týkající se pohybu robotů. Zajímavou otázkou je, jak efektivně detekovat kolize robotů. Viz. témata jedno a multi-robotické plánování pohybu.

Jedno-robotické plánování pohybu (chobotnicový robot) | Single Robot Motion Planning (Octopus Robot). Plánování pohybu pro jednoho robota se zdá být jednoduché, ale co když je sám robot komplikovaný, tj. má složitý tvar a jeho tvar se navíc může měnit. Můžeme si představovat například chobotnicovitého robota s vysokým stupněm volnosti. Plánování pohybu takového robota, přičemž tento robot má navíc během pohybu plnit určitý úkol (například odšroubovat víčko sklenice, což mimochodem chobotnice zvládají), představuje výzvu. Cílem je navrhnout koncepty pro plánování pohybu podobných složitých robotů. Viz. též téma Multi-robotické plánování pohybu. Vhodné pro všechny stupně: bakalář až doktor.

Inteligentní hlídka | Intelligent Patrolling. Otázkou je praktický a teoretický návrh inteligentního hlídkování. Předpokládejme, že máme k dispozici různé statické a mobilní hlídkovací senzory a roboty a naším úkolem je navrhnout jejich rozmístění a naplánovat jejich pohyb tak, aby byla minimalizována možnost nepozorovaného průniku nepřítele do střežené oblasti. Je třeba počítat s tím, že střežená oblast je velká a zdroje na její zabezpečení jsou omezené. Zajímavým rozšířením by mohlo být uvažování o odražení nepřítele, je-li detekován, tj. zejména jak efektivně alokovat obranné prostředky v místě detekce nepřítele. Stejně tak lze uvažovat z pohledu utočníka, tedy jak alokovat prostředky k překonání obrany. Téma lze zkoumat z hlediska návrhu efektivních algoritmů, ale i čistě teoreticky.

Spojité multi-agetní hledání cest | Continuous Multi-Agent Path Finding (MAPF^R). Zobecněná varianta multi-agentního hledání cest (MAPF), kdy opět máme graf a agenty ve vrcholech grafu s úkolem přesunout se do cílových vrcholů s tím, že se cestou nesmí srazit s jíným agentem. Rozdíl oproti standarnímu MAPF je, že vrcholy grafu jsou vnořeny do euklidovského prostoru (2D nebo 3D) a agenti jsou různých geometrických tvarů (kruhy, koule [kruhoboti], krychle, ...) a mají určité kinematické vlastnosti (rychlost, zrychlení, rychlost otáčení). Agenti se pohybují po přímých spojnicích mezi vrcholy a za srážku se považuje jejich libovolný dotyk či překryv. Chtěli bychom nové optimální algoritmy pro MAPF^R.

Paralelní řešič SATu/CSP/IP | Parallel SAT/CSP/IP Solver. Cílem je vytvoření řešiče pro SAT/CSP/IP, který maximálně využije paralelní architekturu moderních CPU, tj. bude se snažit problém řešit maximálně paralelně. Využít lze například včasného rozkladu problému na nezávislé části. Lze uvažovat i o implementaci některých částí řešiče na GPU (například propagace podmínek).

Posílání zpráv a multi-jádrový procesor | Message Passing Algorithms and Multi-Core CPU. Cílem efektivní implementace algoritmů posílání zpráv, jako jsou Warning Propagation či Survey Propagation na paralelní architektuře moderních CPU. Vzhledem k lokální povaze algoritmů a jejich relativní jednoduchosti lze uvažovat i o implementaci na GPU.

Multi-robotické plánování pohybu | Multi-Robot Motion Planning (MRMP). Otázkou je, jak plánovat pohyb více robotů současně a koordinovaně, například dvě a více spolupracujících robotických paží. Naivně by šlo problém řešit jako hledání cesty v kartézském produktu konfiguračních prostorů jednotlivých robotů. Takový přístup je ale neefektivní kvůli velikosti takového spojeného konfiguračního prostoru. Chtěli bychom úlohu řešit spíše jako hledání více cest v původním konfiguračním prostoru (vhodné pro i disertaci).

Líná kompilace v (klasickém) plánování | Lazy Compilation in (Classical Planning). Stejně jako lze pro MAPF (a MAPF^R) konstruovat kódování v SATu (nebo CSP nebo IP) líně, lze podobně postupovat i v (klasickém) plánování. Tedy popravdě je jasné, že úplně stějně to nepůjde, a právě otázka, co je potřeba v plánování dělat obecněji a jinak než v MAPF, je zajímavá a stojí za prozkoumání (vhodné i pro disertaci).

Kumulativní optimalizace v MAPF. V multi-agentním hledání cest (MAPF) se většinou používá jako účelová funkce tzv. součet cen (angl. sum-of-cost), která je poněku paradoxně definována jako počet akcí vykonaných než agent dorazí do cíle a dál se nehýbe. Bylo vyvinuto mnho algoritmů, které hledají optimální řešení MAPF vzhledem k součtu cen, jako jsou algoritmy CBS, ICTS, MDD-SAT a další. V rámci tohoto tématu bude cílem vybrané algoritmy upravit pro jiné kumulativní účelové funkce, jako je například makespan či spotřeba energie (čekání nekonzumuje energii, cenu ale ano). Lze se pokusit mimo jiné o modifikaci ICTS (Increasing Cost Tree Search) pro makespan, tedy o vytvoření algoritmu IMTS (Increasing Makespan Tree Search), a podobně.

Vizualizace MAPF^R. MAPF^R je spojitá varianta úlohy multi-agentního hledání cest (MAPF), tj. agenti se zde pohybují spojitě po přímých spojiních mezi zadanými poziceni v prostoru. Vývoji řešících algoritmů pro MAPF^R by velmi pomohlo, kdyby byl k dispozici vizualizační nástroj, který by umožňoval prohlížet a analyzovat vygenerovaná řešení. Se standardní variantou MAPF se podobná vizualizace již podařila v podobě programu GraphRec.

Heuristiky pro BDD (MDD). BDD či MDD jsou základní rozhodovací diagramy pro reprezentaci znalostí, formálně matematicky řečeno lze jimi více či méně efektivně reprezentovat podmnožiny kartézského součinu {0,1}^k či D^k, kde D je nějaká konečná množina. Velikost BDD/MDD je silně ovlivňována pořadím rozhodovacích proměnných. Prozkoumejte a vylepšete heuristiky pro určování vhodného pořadí proměnných v BDD/MDD, za úvahu stojí i aplikace strojového učení.

Navigace s OZOBOTy. Vyzkoušejte si navigaci, hledání cest, či multi-agentní hledání cest (MAPF) a další simulace na OZOBOTech, tedy na skutečných mobilních robotech. Roboti jsou připraveni plnit úkoly, není třeba se zabývat konstrukcí robota ani hardwarem, stačí programovat chování robotů pomocí jednoduchého jazyka OzoBlockly. Pro lepší představu o robotickém hardwaru doporučuji osobní návštěvu, skupina našich OZOBOTů se na vás těší. Jaké experimenty a simulace budete chtít s OZOBOTy provádět, záleží jen na vaší fantazii (rádi poskytneme inspirační nápady).

SAT Solver a strojové učení. Cílem je nahradit v řešiči SATu založeném na CDCL rozhodovací heuristiku využívající technik strojového učení. Standardně používané heuristiky, jako jsou VSIDS nebo Berkmin, používají intuitivní postupy na výpočet skóre výrokových promených, podle kterého je nakonec vybrána proměnná k ohodnocení. Tento přístup ale nebere v úvahu typ a vlastnosti řešeného problému. Chtěli bychom po vzoru řešiče MapleSAT navrhnout heuristiky založené na strojovém učení, které podle vhodné množiny příznaků vyberou co nejlepší proměnnou k ohodnocení.

K velmi disjunktních cest. Problémem je najít k disjunktních cest, které budou více separované než je tomu v základním problému hledání k disjunktních cest. Standardní problém k disjunktních cest lze řešit například převodem na úlohu hledání maximálního toku velikosti k v určité odvozené síti. Zde budeme navíc chtít, aby mezi libovolnými dvěma nalezenými cestami, byl jistý stupeň separace, tj. například určitá specifikovaná vzdálenost. Problém má aplikace v robotice a zdá se být zajímavý i teroreticky.

Robotické Kung-Fu. Uvažujme humanoidní (nebo i jiné, například psovité) roboty v kinematickém simulátoru (viz. jiné téma níže). Roboti budou zápasit. Téma se soustřeďuje na plánování hmatů a chvatů robota, tak aby přemohl soupeřícího robota. Na zápas lze nahlížet jako na hru dvou hráčů podobně jako například na šachy. Plán robota by tedy měl brát v úvahu možné budoucí akce soupeře. Roboti mohou být stejní, ale i různí (například silněší proti rychlejšému atp.).

Konfigurujeme Porsche. Při konfiguraci vysněného automobilu často narazíme na různé paradoxní příplatky za vybavení a různé nepříjemné podmínky. Například, když si přejeme silnější motor, je to pochopitelně za příplatek, ale navíc je nutné pořídit i automatickou převodovku, která je rovněž za příplatek atd. Představme si, že máme daný rozpočet a chtěli bychom enumerovat konkrétně vybavené automobily, které lze pořídit s daným rozpočtem. Lze použít technik SMT - SAT modulované teorie.

Voronoj zajistí bezpečí. Je známo, že pokud zkonstruujeme v konfiguračním prostoru robota Voronojův diagram a následně používáme pro pohyb robota cesty sestávající z hran diagramu, pohybuje se robot co nejdále od překážek, tedy po bezpečné trajektorii. V konfiguračních prostorech o vyšší dimenzi je exaktní konstrukce Voronojova diagramu obtížná. V tomto tématu se ale přesto budeme snažit digramy sestrojit i ve vyšších dimenzích, alespoň přibližně, například skeletonizačními či buněčnými technikami.

Robotická kinematika. Návrh a implementace simulátoru kinematiky různých robotů. Je možné uvažovat základní kinematické komponenty, jako je ruka, podvozek, atd. a z nich sestavovat složitější roboty. Kinematický simulátor by měl umět pracovat ze základní mechanikou a umožnit interakci více robotů. Simulátor lze podpořit kvalitním grafickým výstupem (2D nebo 3D).

DPLL_MAPF nebo CDCL_MAPF. Toto téma je pokročilejší variantou tématu MAPF jako SMT (čili multi-agentního hledání cest jako SAT modulované teorie - viz. někde níže). Jedná se o kombinaci dvou logických teorií - výrokové splnitelnosti (SAT) a konjunktivní teorie MAPF. Intuitivně řečeno výroková teorie pracuje na vysoké úrovni a vybírá cesty pro agenty bez ohledu na další podmínky (kolize atd.), zatímco teorie MAPF pracuje na nízké úrovni a ověřuje, zda cesty vybrané na vysoké úrovni splňují podmínky (jsou bezkolizní atd.). V rámci tohoto tématu půjde o implementaci DPLL či CDCL (toho spíše) s integrovanou propagací mezi oběma teoriemi, tedy výrokovou a konjunktivní MAPF. Od zmíněné úzké integrace očekáváme vyšší výkon než od jiných méně integrovaných přístupů.

Rebustní a resilientní týmy. Bude chtít sestavovat tým pracovníků tak, aby kvalifikace a schopnosti členů týmu pokrývaly určitou danou množinu kompetencí (například sestavujeme tým programátorů a potřebujeme mít pokryto programování v C++, PHP, Pythonu a HTML). Každý pracovník disponuje jistou množinou kvalifikací a schopnostmi (například u programátorů nás zajímá, jak dobře ovládá ten který programovací jazyk). V této základní variantě je úloha známá a mnoho již je vyřešeno. Zkoumejme variantu, kdy nám půjde o robustnost týmu, tj. jak bude tým odolný proti odchodu jednoho či více pracovníků vzhledem k zachování požadované množiny kompetencí. Překročí-li fluktuace pracovníků určitou míru, stane se sestavování robustních týmů příliš nákladným. Zajímavou variantou je pak sestavení tzv. resilientního (těžko zdolatelného) týmu, kdy nás zajímá, jak snadno dokážeme kompetence chybějících pracovníků nahradit novými.

Nespoléhej na Google Translate, čeština má na víc. Je známo, že automatické překladače typu Google Translate mají potíže s již přeloženými větami a spojeními z literatury. Pro mnoho literatury máme v češtině skvělé překlady, příkladem buď spojení "Light, seeking light, doth light of light beguile..." z Shakespearovy hry Marná lásky snaha, kterou Martin Hilský překládá jako "Ve jménu světla světlo světlem vraždit...". Ovšem Google Translate nám nabídne následující nesmyslný překlad "Světlo, které hledá světlo, světlo světla bloudí...". V rámci tématu zkoumejte možnosti automatického (statistického) překladu do češtiny s využitím již přeložené literatury.

Formace ve spojitém MAPF. Zvláště ve spojité variantě problému MAPF (multi-agentního hledání cest) je důležité uvažovat o formacích agentů. Při přesunu se skupina agentů bude snažit pohybovat ve formaci, což jí v reálných aplikacích umožní například pohybovat se rychleji, bezpečněji, nebo být lépe připraven na nadcházející úkoly. V případě, že není možné formaci udržet například z důvodu přítomnosti překážky nebo jiných agentů, je třeba formaci rozpustit nebo změnit. V takovém případě je zajímavé zamýšlet se nad otázkou, jak toto provést, abychom formaci co nejmenším úsilím obnovili. Je možné se zabývat i 3D variantou, tj. například případem, kdy agenti jsou představováni létajícími drony.

Dekompilátor/deobfuskátor JavaScriptu. V rámci tohoto tématu bychom chtěli zvrátit efekt obfuskačních kompilátorů pro JavaScript, jako je například Closure. Cílem je tedy zrekonstruovat z kompilovaného kódu původní člověkem čitelný a strukturovaný kód. JavaScript zde uvažujeme z toho důvodu, že zdrojový i cílový jazyk je stejný. V případě klasických komplilátorů do nativního procesorového kódu je transformace ze zdrojového kódu příliš složitá a úkol dekompilace nesnadný. U skriptovacích jazyků, kdy cílový kód je ve stejném jazyce, je naopak šance, že z původního kódu zbydou fragmenty původních struktur, které lze k dekompilaci použít.

CDCL napsaný na půl A4. V některých kulturách lidé neradi obracejí list (ponechme stranou, o které konkrétně se jedná) a chtějí mít celé sdělení napsané na jedné stránce (řekněme A4). Pro nás tím sdělením bude kód významných algoritmů UI, jako je například backjumping, WalkSAT, CDCL, závislostmi řízený backtracking (dependency-directed backtracking), backpropagation, abychom jmenovali aspoň některé. Ovšem nikoli pseudo-kód, to by bylo příliš snadné (a zvládl by to i kdejaký učitel UI, který ve skutečnosti neumí programovat), ale skutečný kód v některém z běžných procedurálních programovacích jazyků, jako je C++, Java, C#, Python, atd. Téma lze řešit expertně heuristicky, nebo také vývojem automatických nástrojů na zkracování kódu.

Kruhoví roboti = kruhoboti (MAPFR). Budeme chtít navigovat skupinu kruhových robotů (tzv. kruhobotů), kteří se pohybují ve spojitém 2D prostoru s jistými překážkami. Běžným příkladem kruhobota je kruhový automatický vysavač. Naším cílem je navigovat kruhoboty tak, aby mezi nimi nedocházelo ke kolizím a každý kruhobot se dostal do svého cíle. Kruhobot se může pohybovat rovně (například můžeme uvažovat konstantní rychlost, nebo konstantní zrychlení) a může se na místě otáčet (můžeme uvažovat konstantní úhlovou rychlost, nebo konstantní úhlové zrychlení). Navrhněte algoritmy pro centrální kooperativní navigaci kruhobotů. Jedná se o spojitou variantu problému multi-agentního hledání cest (MAPF), čili hledání cest pro multi-kruhoboty.

Vybírej dobře (proměnnou) v SATu nebo CSP. Téma na výběr proměnné k ohodnocení v systematickém SAT řešiči typu CDCL (conflict-driven clause learning) nebo na backtrackingu/backjumpingu založeném řešiči CSP. Řešiče uvedeného typu, ať už se jedná o SAT nebo CSP, postupně rozšiřují částečné ohodnocení proměnných. Výběr následující proměnné k ohodnocení je často určen jednoduchou doménově nezávislou heuristikou. Tento přístup bychom chtěli překonat návrhem nových heuristik založených na automatickém učení (strojovém/hlubokém) při řešení mnoha úloh specifického typu. Cílem je vytvořit schéma pro automatický trénink heuristik a vytrénovat heuristiku, která překoná doménově nezávislé na vybrané třídě vstupních instancí SATu či CSP. Toto téma je obdobou tématu tie-breaking in CBS s rozdílem, že je zaměřeno na SAT a CSP.

Automobile Utopia = Autopia. Rok 2050: ve světě autonomních aut je veškerá doprava řízena centrálně. Systém ovládá velké množství osobních a nákladních vozidel a všem jim detailně plánuje trasy. Lidský faktor je zcela vyloučen, tj. žádné člověkem řízené auto se v dopravním systému nepohybuje. Chodce a podobné jevy pro zjednodušení zanedbejme. Centrální systém má o veškerém pohybu vozidel dokonalý přehled, takže dopravní zácpy, nečekané objížďky a podobné nepříjemnosti již patří do minulosti. Uživaleté přicházejí s požadavky odkud, kam a kdy chtějí jet (podobně pro náklady) a systém jim zařídí, že je autonomní vozidlo v požadovaném místě a čase vyzvedne a dopraví do cíle. Navrněte systém pro řízení dopravy podle této (možná utopické) vize. Optimalizujte například celkovou energetickou spotřebu dopravního systému. Nesmíme zapomínat ani na VIP, kdy dosažení co nejkratšího času pro VIP má přednost před ostatními atd.

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.

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).

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.

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.

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 Σ₁^P 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ů.

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čí.

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 x_b +_b y_b = y_b +_b x_b nad bitovými vektory, kde x_b a y_b 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.

Copyright © 2015 - 2023 Pavel Surynek