velikost textu

Efficient Representations and Conversions of Planning Problems

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Efficient Representations and Conversions of Planning Problems
Název v češtině:
Efektivní reprezentace a konverze plánovacích problémů
Typ:
Disertační práce
Autor:
Mgr. Daniel Toropila
Školitel:
prof. RNDr. Roman Barták, Ph.D.
Oponenti:
prof. Thomas Leo McCluskey
Doc. Dr. Michal Pěchouček, MSc.
Id práce:
59877
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra teoretické informatiky a matematické logiky (32-KTIML)
Program studia:
Informatika (P1801)
Obor studia:
Teoretická informatika (4I1)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
5. 12. 2014
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
umělá inteligence, doménově nezávislé plánování, modelování problémů, stavové proměnné, splňování podmínek
Klíčová slova v angličtině:
artificial intelligence, domain-independent planning, problem modeling, state variables, constraint satisfaction
Abstrakt:
Název práce Efektivní reprezentace a konverze plánovacích problémů Autor Daniel Toropila Katedra Katedra teoretické informatiky a matematické logiky Vedoucí disertační práce prof. RNDr. Roman Barták, Ph.D. Abstrakt Efektivita všech typů plánovacích systému je silně závislá na formulaci vstupu, strukturu kterého musí plánovače využít, chtějí-li dosáhnout zvýšení své výpočet- ní efektivity. Z tohoto důvodu se reprezentace založená na stavových proměnných (SAS+) stala oblíbenou formou kódování vstupu mnoha moderních plánovačů. Jelikož ale většina plánovacích problémů je vyvíjena pomocí klasické reprezen- tace, vzniklo v nedávné minulosti několik technik jejího převodu do reprezen- tace SAS+. Tyto techniky ale bohužel ignorují informace specifiké pro jedno- tlivé instance plánovacích problémů. Proto představujeme nový algoritmus pro konstrukci SAS+, který naplno využívá informace o cíli i o iniciálním stavu, a pomocí obsáhlých vypočetních experimentů ukazujeme, že pro mnohé plánovací problémy nový algoritmus pomáhá zvýšit efektivitu jejich řešení. V poslední části práce poté prezentujeme přehled několika modelů splňování podmínek pro plánování, založených na kodóvání SAS+, a také na konečných stavových auto- matech. Uvádíme též experimentální srovnání jejich výkonnosti, které ukazuje, že v kategorii plánovačů založených na splňování podmínek představují tyto modely velice konkurenceschopnou alternativu. Klíčová slova umělá inteligence, doménově nezávislé plánování, modelování problémů, stavové proměnné, splňování podmínek
Abstract v angličtině:
Title Ecient Representations and Conversions of Planning Problems Author Daniel Toropila Department Department of Theoretical Computer Science and Mathematical Logic Supervisor prof. RNDr. Roman Barták, Ph.D. Abstract The eciency of all types of planning systems is strongly dependent on the in- put formulation, the structure of which must be exploited in order to provide an improved eciency. Hence, the state-variable representation (SAS+) has be- come the input of choice for many modern planners. As majority of planning problems is encoded using a classical representation, several techniques for trans- lation into SAS+ have been developed in the past. These techniques, however, ignore the instance-specific information of planning problems. Therefore, we in- troduce a novel algorithm for constructing SAS+ that fully utilizes the information from the goal and the initial state. By performing an exhaustive experimental evaluation we demonstrate that for many planning problems the novel approach generates a more ecient encoding, providing thus an improved solving time. Finally, we present an overview and performance evaluation of several constraint models based on SAS+ and finite-state automata, showing that they represent a competitive alternative in the category of constraint-based planners. Keywords artificial intelligence, domain-independent planning, problem modeling, state vari- ables, constraint satisfaction
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Daniel Toropila 4.94 MB
Stáhnout Abstrakt v českém jazyce Mgr. Daniel Toropila 64 kB
Stáhnout Abstrakt anglicky Mgr. Daniel Toropila 88 kB
Stáhnout Posudek vedoucího prof. RNDr. Roman Barták, Ph.D. 97 kB
Stáhnout Posudek oponenta prof. Thomas Leo McCluskey 1.72 MB
Stáhnout Posudek oponenta Doc. Dr. Michal Pěchouček, MSc. 180 kB
Stáhnout Záznam o průběhu obhajoby 79 kB