Název:
Efektivní reprezentace a konverze plánovacích problémů
Překlad názvu:
Efficient Representations and Conversions of Planning Problems
Autoři:
Toropila, Daniel Typ dokumentu: Rigorózní práce
Rok:
2015
Jazyk:
eng
Abstrakt: [eng][cze] Title E cient 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 e ciency 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 e ciency. 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 e cient 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...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...
Klíčová slova:
doménově nezávislé plánování; modelování problémů; splňování podmínek; stavové proměnné; umělá inteligence; artificial intelligence; constraint satisfaction; domain-independent planning; problem modeling; state variables