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...
Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:338119 |
Date | January 2014 |
Creators | Toropila, Daniel |
Contributors | Barták, Roman, McCluskey, Thomas Leo, Pěchouček, Michal |
Source Sets | Czech ETDs |
Language | English |
Detected Language | English |
Type | info:eu-repo/semantics/doctoralThesis |
Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0019 seconds