|
|
Global Constraints in Scheduling
Vilím, Petr ; Barták, Roman (advisor) ; Rudová, Hana (referee) ; Wolf, Armin (referee)
In this place, I would like to say my best thanks to everyone who supported me in my work and helped me along my whole Ph.D. study. First of all I owe a major debt to my supervisor Doc. RNDr. Roman Barták, Ph.D. for his patient leading, collaboration, support and help; especially for guidingmy research to this topic, providing important information from CP field, helping me publish my papers and reviewing them (most of them several times). Next I want to thank to Doc. RNDr. Ondřej Čepek, Ph.D. I wrote with him and Roman Barták a paper to CP 2004 which was very successful. They both contributed to this success. I also wish to express my gratitude to the whole CP community. To anonymous reviewers for providing me valuable feedback, for pointing out flaws in my papers and helping me to fix them. To my mentors on CP conferences who gave me a lot of helpful advices concerning my research and this a Ph.D. Thesis. I'm also very thankful to all the people with whom I could discuss during several conferences - they often asked very good questions; and good questions are often one half of whole research. My special thanks belongs to Philippe Baptiste, Mats Carlsson, Narendra Jussien, Philippe Laborie, Francois Laburthe, Narendra Jussien, Claude Le Pape, Jean-Charles Régin, Jerome Rôgerie, Francesca Rossi and...
|
|
|
Visualization and verification of plans
Glinský, Radoslav ; Barták, Roman (advisor) ; Dvořák, Filip (referee)
Title: Visualization and Verification of Plans Author: Radoslav Glinský Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor of the bachelor thesis: Doc. RNDr. Roman Barták, Ph.D. Abstract: Plan analysis is an important part of complete planning systems. In order to make even larger plans transparent and human readable, we have developed a program which helps users with the analysis and visualization of plans. This program is called VisPlan - Interactive Visualization and Verification of Plans. VisPlan is an inevitable part of this thesis as it practically implements its plan verification and visualization solutions. VisPlan finds and displays causal relations between actions, it identifies possible flaws in plans (and thus verifies plans' correctness), it highlights the flaws found in the plan and finally, it allows users to interactively modify the plan and hence manually repair the flaws or just fine-tune the plan. Keywords: Planning, Artificial Intelligence, PDDL, Verification
|
|
|
Compiling Planning Problems
Toropila, Daniel ; Barták, Roman (advisor) ; Chrpa, Lukáš (referee)
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.
|
|
|
Classical planning techniques
Sasák, Róbert ; Barták, Roman (advisor) ; Toropila, Daniel (referee)
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.
|
|
|
Constraint satisfaction for HW/SW verification
Cigler, Luděk ; Barták, Roman (advisor) ; Vomlelová, Marta (referee)
Constraint satisfaction techniques (CSP) are a powerful framework for modeling and solving various problems in artificial intelligence and operations research. Verification of HW and SW can profit from employing constraint satisfaction for test generation. The essential property of a CSP algorithm (wrt. test generation) is the uniform generation of solution samples. We present several algorithms for sampling solutions of a CSP and extend them so that they can be used for sampling solutions of CSP with preferences. We test the performance of our algorithms on various benchmark problems.
|
|
|
Project portfolio optimisation with time and resources
Huml, Tomáš ; Barták, Roman (advisor) ; Vlach, Milan (referee)
Title: Project portfolio optimization with time and resources Author: Bc. Tomáš Huml Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Roman Barták, Ph.D Abstract: Traditional project portfolio optimization deals with static projects that are not evolving in time. The focus of this diploma thesis is on projects that are spread in time, typically such projects consists of a sequence (or other partially ordered structure) of actions that require some resources (money, people, etc.) for realization. Then the project portfolio optimization deals with selecting a subset of projects according to given time and space (resource) restrictions and optimizing certain criteria such as overall profit. This problem is very close to oversubscribed scheduling where the most profitable subset of orders is being scheduled. Hence scheduling techniques will be the main inspiration for solving this new type of problems. Lots of modelling algorithms for optimal portfolio selection are proposed in this diploma thesis and several of them are implemented in a program which is part of this thesis as well. Keywords: portfolio optimization, integer linear programming (ILP), workflow optimization, project interdependencies
|
|
|
Monte Carlo Techniques in Planning
Trunda, Otakar ; Barták, Roman (advisor) ; Toropila, Daniel (referee)
The Monte Carlo Tree Search (MCTS) algorithm has recently proved to be able to solve difficult problems in the field of optimization as well as game-playing. It has been able to address several problems that no conventional techniques have been able to solve efficiently. In this thesis we investigate possible ways to use MCTS in the field of planning and scheduling. We analyze the problem theoretically trying to identify possible difficulties when using MCTS in this field. We propose the solutions to these problems based on a modification of the algorithm and preprocessing the planning domain. We present the techniques we have developed for these tasks and we combine them into an applicable algorithm. We specialize the method for a specific kind of planning problems - the transportation problems. We compare our planner with other planning system.
|
|
|
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.
|
|
|
Combinatorial algorithms for online problems: Semi-online scheduling on related machines
Ebenlendr, Tomáš ; Sgall, Jiří (advisor) ; Barták, Roman (referee) ; Epstein, Leah (referee) ; Woeginger, Gerhard (referee)
Mgr. Tomáš Ebenlendr Combinatorial algorithms for online problems: Semi-online scheduling on related machines Abstract of doctoral thesis We construct a framework that gives optimal algorithms for a whole class of scheduling problems. This class covers the most studied semi-online variants of preemptive online scheduling on uniformly related machines with the objective to minimize makespan. The algorithms from our framework are deterministic, yet they are optimal even among all randomized algorithms. In addition, they are optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. We provide new lower bound of 2.112 for the original online problem. The (deterministic) upper bound is e ≈ 2.718 as there was known e-competitive randomized algorithm before. Our framework applies to all semi-online variants which are based on some knowledge about the input sequence. I.e., they are restrictions of the set of valid inputs. We use our framework to study restrictions that were studied before, and we derive some new bounds. Namely we study known sum of processing times, known maximal processing time, sorted (decreasing) jobs, tightly grouped processing times, approximately known optimal makespan and few combinations. Based on the analysis...
|
|
|
Dynamic Temporal Networks
Zykán, Pavel ; Barták, Roman (advisor) ; Surynek, Pavel (referee)
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.
|
guest ::
