|
|
Efficient Representations and Conversions of Planning Problems
Toropila, Daniel
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...
|
|
|
Framework for development of optimization algorithms
Hurt, Tomáš ; Trunda, Otakar (advisor) ; Hric, Jan (referee)
The aim of the thesis is to design and implement an efficient tool for research and testing of algorithms of the combinatorial optimization. The domain of the planning research will be explained and the steps of design and implementation of such program will be covered. The framework will support two primary for- malisms for the description of optimization problems (PDDL, SAS+ ). The inputs processing will be provided, suitable data structures and efficient implementati- ons of search algorithms will also be included. The emphasis will be on a proper object design and easy extensibility for the future development. To achieve this goal, proven principles of software engineering will be used. 1
|
|
|
Efficient Representations and Conversions of Planning Problems
Toropila, Daniel ; Barták, Roman (advisor) ; McCluskey, Thomas Leo (referee) ; Pěchouček, Michal (referee)
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...
|
|
|
Efficient Representations and Conversions of Planning Problems
Toropila, Daniel
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...
|
guest ::
