Framework pro vývoj optimalizačních algoritmů

• Název práce v češtině: Framework pro vývoj optimalizačních algoritmů
• Název v anglickém jazyce: Framework for development of optimization algorithms
• Klíčová slova: kombinatorická optimalizace, doménově nezávislé plánování, prohledávací algoritmy, plánovací systém
• Klíčová slova anglicky: combinatorial optimization, domain-independent planning, search algorithms, planning system
• Akademický rok vypsání: 2015/2016
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: RNDr. Ing. Otakar Trunda, Ph.D.
• Řešitel: Mgr. Tomáš Hurt - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 09.04.2016
• Datum zadání: 14.04.2016
• Datum potvrzení stud. oddělením: 03.05.2016
• Datum a čas obhajoby: 06.02.2020 09:00
• Datum odevzdání elektronické podoby: 06.01.2020
• Datum odevzdání tištěné podoby: 06.01.2020
• Datum proběhlé obhajoby: 06.02.2020
• Oponenti: RNDr. Jan Hric

Zásady pro vypracování

Řešitel nastuduje prohledávací algoritmy používané v oblasti kombinatorické optimalizace a tyto algoritmy implementuje včetně souvisejicích datových struktur. Dále prostuduje modelovací jazyky používané pro popis optimalizačních problémů (zejména PDDL a SAS+), navrhne vhodnou reprezentaci dat a implementuje metody pro práci se vstupy v těchto formátech. Navržené algoritmy a datové struktury poté otestuje na sérii optimalizačních problémů z oblasti plánování.

Výsledný program by měl tvořit základ pro framework pro vývoj a testování plánovacích algoritmů. Důraz bude kladem zejména na přehledný objektový návrh, efektivní implementaci algoritmů a datových struktur a snadnou rozšiřitelnost. K programu bude vytvořená také podrobná dokumentace, wiki stránky a on-line repozitář. Program bude určený pro platformu .NET.

Program bude mimo jiné poskytovat metody pro načítání vstupů v různých formátech, podporu pro automatické provádění rozsáhlejších experimentů, efektivní implementaci základních algoritmů a datových struktur a metody pro automatické vyhodnocení a vizualizaci výsledků.

Seznam odborné literatury

Stefan Edelkamp, Stefan Schrödl: Heuristic Search - Theory and Applications, Morgan Kaufmann, 2011

Ian Sommerville: Software Engineering (8th Edition), Addison-Wesley, 2006

Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach (3rd Edition), Prentice Hall, 2010

Malik Ghallab, Dana Nau, Paolo Traverso: Automated Planning: Theory & Practice, Elsevier, 2004

Franz Rothlauf: Design of Modern Heuristics - Principles and Application, Springer Science & Business Media, 2011

Malte Helmert: Understanding Planning Tasks - Domain Complexity and Heuristic Decomposition, Springer, 2008

Předběžná náplň práce

Práce se zabývá návrhem prostředí pro vývoj a testování prohledávacích a plánovacích algoritmů. Téma je vhodné buď pro studenty softwarového inženýrství, kteří zvládnou pokročilejší algoritmy z oblasti umělé inteligence nebo pro studenty teoretické informatiky, kteří se nebojí návrhu systémové architektury a většího množství implementační práce.

Předběžná náplň práce v anglickém jazyce

The thesis aims to devise a framework for developing and testing search algorithms and planning algorithms. The topic is suitable either for software engineering students who can handle advanced algorithms of artificial intelligence, or for theoretical computer scientists that are not afraid of system architecture and implementation work.