|
|
Learning for Classical Planning
Chrpa, Lukáš ; Barták, Roman (advisor)
This thesis is mainly about classical planning for articial intelligence (AI). In planning, we deal with searching for a sequence of actions that changes the environment from a given initial state to a goal state. Planning problems in general are ones of the hardest problems not only in the area of AI, but in the whole computer science. Even though classical planning problems do not consider many aspects from the real world, their complexity reaches EXPSPACE-completeness. Nevertheless, there exist many planning systems (not only for classical planning) that were developed in the past, mainly thanks to the International Planning Competitions (IPC). Despite the current planning systems are very advanced, we have to boost these systems with additional knowledge provided by learning. In this thesis, we focused on developing learning techniques which produce additional knowledge from the training plans and transform it back into planning domains and problems. We do not have to modify the planners. The contribution of this thesis is included in three areas. First, we provided theoretical background for plan analysis by investigating action dependencies or independencies. Second, we provided a method for generating macro-operators and removing unnecessary primitive operators. Experimental evaluation of this method...
|
|
|
Compilation-based Approaches for Automated Planning
Pantůčková, Kristýna ; Barták, Roman (advisor) ; Chrpa, Lukáš (referee)
One of the possible approaches to automated planning is compilation to sat- isfiability or constraint satisfaction. Compilation enables to take advantage of the advancement of SAT or CSP solvers. In this thesis, we implement three of the encodings recently proposed for compilation of planning problems: the model TCPP, the R2 ∃-Step encoding and the Reinforced Encoding. All these approaches search for parallel plans; however, since they use different definitions of parallel step and different variables and constraints, we decided to compare their per- formance on standard benchmarks from international planning competitions. As the R2 ∃-Step encoding was not suitable for our implementation, we present a mod- ified version of this encoding with a reduced number of variables and constraints. We also demonstrate how different definitions of parallel step in the Reinforced Encoding affect the performance. Furthermore, we suggest redundant constraints extending these encodings. Although they did not prove to be beneficial in gen- eral, they could slightly improve the performance on some benchmarks, especially in the R2 ∃-Step encoding.
|
|
|
Navigation of Units in Video Games Using Flow Networks
Pacovský, Jan ; Gemrot, Jakub (advisor) ; Chrpa, Lukáš (referee)
This thesis investigates the navigation of units in real-time strategy computer games and is focused on the task of navigating a bigger group of units through a game world that contains narrows passages. The narrow passages causes signi- ficant delays that could be avoided by splitting the group and taking some part of it through an alternative way. In this thesis, a solution using flow networks is proposed. The map is transformed into a flow network which then allows the planner to find an alternative route to the fully occupied narrow passage. The proposed method was tested in a simulator specifically designed for this task and compared with the conventional methods of navigation in computer games. The final evaluation shows that the navigation of units using flow networks can successfully solve this problem. 1
|
|
|
Exploiting Structures in Automated Planning
Kuckir, Ivan ; Barták, Roman (advisor) ; Chrpa, Lukáš (referee)
This thesis focuses on improving the process of automated planing through symmetry breaking. The aim is to describe symmetries, which are often observed by human programmers, but haven't been properly theoretically formalized. After an analysis of available research, there are new definitions of symmetries proposed in context of classical planning, such as state equivalence, T1 automorphisms and more general automorphisms of constants. Several theorems are proved about new symmetries. As a result, an algorithm for detecting a special symmetry class is proposed, together with a method of exploiting such class during planning. Experimens are made to show the effect of symmetry breaking on the performance of the planner. Powered by TCPDF (www.tcpdf.org)
|
|
|
Generating Side Quests for RPG Games From Hand-Crafted Building Blocks
Hromada, Tomáš ; Černý, Martin (advisor) ; Chrpa, Lukáš (referee)
Role-playing games (RPG) often contain side quests - shorter quests not related to the main story, to give the player the feeling of freedom and to let him choose his own path. For this effect to be good, there must be a large number of side quests in the game. Replacing hand-made quests with generated ones is one of the possibilities to make this task easier, however contemporary attempts at generating quests result in the quests being simple and repetitive. This thesis aims to explore a different approach to the problem, a system generating side quests from a set of hand-crafted building blocks. An abstract design and an implementation are described, along with the methods used for evaluating the implementation. The system was evaluated on a group of players, which rated the generated quests similarly to the hand-picked ones.
|
|
|
Modelling Planning Problems
Vodrážka, Jindřich ; Barták, Roman (advisor) ; Chrpa, Lukáš (referee)
This thesis deals with the knowledge engineering for Automated Planning. The concept of state variables has been recently used with benefits for representation of planning problems. In this thesis the same concept is used in a novel formalism for planning domain and problem modeling. A proof-of-concept knowledge modeling tool is developed based on the new formalism. This tool is then used for modeling of example classical planning domain to show its capabilities. The export to standard domain modeling language is also implemented in the tool in order to provide connection to existing planning systems.
|
|
|
Modular system for managing web contents
Kulman, Igor ; Lokoč, Jakub (referee) ; Chrpa, Lukáš (advisor)
Modular web content management system (thereinafter ModularCMS) offers the users an easy and simple way to create an manage their own website, from a simple personal presentation to complex and extensive company web. ModularCMS puts the main afford on the simplicity of user and programming interface, separating itself from other existing CMSs. The simplicity of user inteface maens, taht if an end user orderes an web presentation based on this CMS, atfer its deployment, he will be able to manage the content and do all the other actions he may need very easy and quickly. The architecture of MudularCMS is modular, it could be extended with other functions a project may need by programming new moduls.
|
|
|
Matrix calculator
Krč-Jediný, Ondrej ; Surynek, Pavel (referee) ; Chrpa, Lukáš (advisor)
The aim of this project is creating an environment which would allow the user to work with chosen matrix algorithms, with the emphasis on understanding their principles. Using a simple programming language, the user will be able to perform computations and display their results. Moreover, the environment is able to show a characterisation, and a description of the course of computation of each algorithm, thus providing information about the means of its operation. The project implements several basic and several advanced algorithms for handling matrices.
|
|
|
Train Traffic Simulation with Optimization
Langhammer, Martin ; Chrpa, Lukáš (referee) ; Surynek, Pavel (advisor)
The aim of this thesis was to create a train traffic simulation system with optimization. The created system can serve to find an optimal schedule for trains in a fixed railway network. An input of the presented system consists of a railway network, passangers' requirements, tariff rate zones, and a schedule. The output of the simulation is a profit. The profit depending on the schedule defines the objective function whose maximum we are tying to find. Two different algorithms were used to find the maximum profit - hill climbing and differential evolution method. We show an experimental comparison of both algorithms in this thesis.
|
|
|
Compiling Planning Problems
Toropila, Daniel ; Chrpa, Lukáš (referee) ; Barták, Roman (advisor)
Constraint satisfaction techniques are used frequently for solving scheduling problems, but they are still seldom in AI planning. There exist several attempts to apply constraint satisfaction for solving AI planning problems, however, these techniques never became prevailing in planning and did not reach the success of, for example, SATbased planners. In this work we argue that the existing constraint models for classical AI planning are indeed not exploiting fully the power of constraint satisfaction and we propose their reformulation which significantly improves efficiency.
|
guest ::
