|
|
Solving Boolean satisfiability problems
Balyo, Tomáš ; Barták, Roman (referee) ; Surynek, Pavel (advisor)
In this thesis we study the possibilities of decomposing Boolean formulae into connected components. For this reason, we introduce a new concept - component trees. We describe some of their properties and suggest some applications. We designed a class of decision heuristics for SAT solvers based on component trees and experimentally examined their performance on benchmark problems. For this purpose we implemented our own solver, which uses the state-of-theart SAT solving algorithms and techniques.
|
|
|
AI Planning with Time and Resource Constraints
Dvořák, Filip ; Chrpa, Lukáš (referee) ; Barták, Roman (advisor)
Automated planning plays an important role in many fields of human interest, where complex and changing tasks involve demanding efficiency and error-avoidance requirements. Research in planning is also motivated by capturing the computational aspects of Artificial Intelligence, where planning, being a reasoning side of acting, is one of the key elements. Introduction of time and resources into planning is an important step towards modelling problems from the real world, however planning is generally hard and introduction of time and resources makes it even harder. In this thesis we explore theoretical aspects of planning, temporal reasoning and resource reasoning. Based on these studies we develop our own suboptimal domain-independent planning system that focuses on planning, where time plays a major role and resources are constrained. We test the developed planning system on the planning problems with time and resources from the International Planning Competition 2008 and compare our results with the competition participants.
|
|
|
Temporal networks
Vlk, Rudolf ; Čepek, Ondřej (referee) ; Barták, Roman (advisor)
Integration of planning and scheduling requires new approaches to the scheduling problem. The scheduler must be able to provide useful information for the planner in order to avoid generation of unfeasible plans. In constraint-based scheduling it is possible to de ne custom ltering rules that improve the solving procedure. If the ltering rules exploit the information shared by the planner and the scheduler (e.g. precedence or temporal constraints), the outcome of these rules can be used to provide useful hints for the planner. This work presents a ltering technique that exploits temporal relations between a set of activities allocated to one or more disjunctive resources. The work also presents a set of propagation rules for constraint-based scheduling based on various ltering techniqes.
|
|
|
Dynamic Temporal Networks
Zykán, Pavel ; Surynek, Pavel (referee) ; Barták, Roman (advisor)
This work focuses on algorithms related to dynamic temporal networks. In the rst part, we describe existing algorithms mainly for maintaining path consistency after either restriction or relaxation of constraints. In the second part, we describe a problem of nding a minimal perturbation within a solution in sequence of dynamic temporal networks. We solve this problem on Simple Temporal Networks. We analyze the problem and then we propose an approach for solving it. We also include experimental e ectivity measurements on sets of parametrically generated problems.
|
|
|
Constraint solvers
Tuláček, Michal ; Surynek, Pavel (referee) ; Barták, Roman (advisor)
Constraint solver is a specialized software used to solve constraint satisfaction problems. The thesis surveys constraint solvers and some of them compares using the criteria of user accessibility and variety of problems which can be modeled.
|
|
|
Classical planning techniques
Sasák, Róbert ; Toropila, Daniel (referee) ; Barták, Roman (advisor)
Classical planning deals with nding a sequence of actions transferring the initial state of world into a desired goal state. This work surveys two classical planning techniques, forward and backward search. We implement both techniques in a form of software prototype using ve di erent search algorithms, in particular DFS, BFS, IDDFS, A*, WA*. By introducing additional heuristic we get family of 26 planners. We compare e ectivity of the planners on several domains from International Planning Competition. None of the planners is signi cantly better on all domains, however, in general, the planners based on forward search perform better.
|
|
|
Learning for Classical Planning
Chrpa, Lukáš ; Barták, Roman (advisor) ; Železný, Filip (referee) ; Berka, Petr (referee)
This thesis is mainly about classical planning for artificial 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 do mains 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...
|
|
|
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...
|
|
|
Interactive Gantt Charts
Skalický, Tomáš ; Vojtáš, Peter (referee) ; Barták, Roman (advisor)
This work deals with problems of interactive rescheduling in Gantt charts. The goal of the work is to design and implement an algorithm which resolves the inconsistencies in a schedule. First existing approaches are studied. Algorithm for solving our inconsistencies in a schedule is the most important contribution of this work. It is introduced there and there is also it's proof of correctness and finiteness. Demonstration of applicability of the algorithm follows. For this reason, program GanttViewer which is a part of this work is used. Finally, this program is described in detail.
|
|
|
Solving over-constrained problems
Kasl, Tomáš ; Barták, Roman (advisor) ; Zlomek, Josef (referee)
Constraint hierarchies belong to techniques for solving over-constrained problems, that is, constraint satisfaction problems where it is not possible to satisfy all the constraints. The idea of constraint hierarchy is to label each constraint by a preference level describing how much the constraint should be satisfied. Currently, there exist two classes of constraint hierarchy solvers: local propagation solvers that can handle more or less equality constraints only and refining solvers that are a bit cumbersome and non-incremental. The theoretical framework of constraint hierarchy solvers combines advantages of both above mentioned classes but no algorithm exploiting the power of this framework has been proposed so far. The thesis describes a new algorithm for solving constraint hierarchies based on this framework.
|
guest ::
