|
|
Planning Solar Array Operations on the ISS
Jelínek, Jan ; Barták, Roman (advisor) ; Vilím, Petr (referee)
This work focuses on the problem of planning solar array operations on the International Space Station. The goal is to find a viable orientation for ten joints which attach panels to the station. These orientations and modes must satisfy various constraints and the final schedule should also take into account certain preferences. This is a task suitable for automated planning and scheduling, but new technologies are gaining very slowly in the field of the human spaceflights. In this work we will analyze the current solution of this problem and then we will propose a new algorithm that will exploit techniques of automated planning and scheduling. In the contrast with the original greedy algorithm, the suggested algorithm initially finds any solution and then tries to improve it by optimazing partial objective functions. Due to the size of the search space, the search attempts are limited by the time limit. Powered by TCPDF (www.tcpdf.org)
|
|
|
Constraint satisfaction for inductive logic programming
Chovanec, Andrej ; Barták, Roman (advisor) ; Železný, Filip (referee)
Inductive logic programming is a discipline investigating invention of clausal theories from observed examples such that for given evidence and background knowledge we are finding a hypothesis covering all positive examples and excluding all negative ones. In this thesis we extend an existing work on template consistency to general consistency. We present a three-phase algorithm DeMeR decomposing the original problem into smaller subtasks, merging all subsolutions together yielding a complete solution and finally refining the result in order to get a compact final hypothesis. Furthermore, we focus on a method how each individual subtask is solved and we introduce a generate-and-test method based on the probabilistic history-driven approach for this purpose. We analyze each stage of the proposed algorithms and demonstrate its impact on a runtime and a hypothesis structure. In particular, we show that the first phase of the algorithm concentrates on solving the problem quickly at the cost of longer solutions whereas the other phases refine these solutions into an admissible form. Finally, we prove that our technique outperforms other algorithms by comparing its results for identifying common structures in random graphs to existing systems.
|
|
|
Controlled Landing of an Autonomous Drone
Hraško, Andrej ; Barták, Roman (advisor) ; Obdržálek, David (referee)
The goal of this work is to develop and implement a desing for the most appropriate method allowing autonomous landing of the quadrocopter on a heliport with a visible pattern. This work includes an analysis dedicated to finding the best pattern for the designated landing area and the most reliable way to identify this pattern in an image taken from the camera of quadrocopter. The work explains the different ways of controlling devices as dynamic systems and implements algorithms for navigation of the quadrocopter to the target. The achieved results are verified by documented experiments. Powered by TCPDF (www.tcpdf.org)
|
|
|
Workforce Optimisation
Pacinda, Štefan ; Barták, Roman (advisor) ; Klusáček, Dalibor (referee)
Title: Workforce Optimisation Author: Štefan Pacinda Department / Institute: Department of Theoretical Computer Science and Mathematical Logic (KTIML) Supervisor of the master thesis: doc. RNDr. Roman Barták Ph.D., KTIML Abstract: Workforce management deals with the problem of maintaining productive workforce for example in call centers, hospitals, transportation companies etc. It includes the problem of deciding which skills are necessarily at each given time and how many personnel with given skills is required. These decisions are followed by solving the problem of allocating particular employees to shifts while satisfying the skill demands but also other constraints derived for example from law regulations, trade unions agreements, and individual preferences. This thesis deals with workforce optimization, that is with the optimal assignment of personnel to shifts in order to cover the demand for resources that vary over time. In this paper the solved problem is described in all detail and modeled as mixed integer program. Implementation details are presented and exhaustive analysis and experiments on a real life problem instance are performed to assure that the aims of the work have been met. Keywords: Rostering, Workforce Management, Shift Scheduling
|
|
|
Constraint Programming in Planning
Surynek, Pavel ; Barták, Roman (advisor) ; Vojtáš, Peter (referee) ; Štěpánková, Olga (referee)
This thesis deals with planning problems and Boolean satisfiability problems that represent major challenges for artificial intelligence. Planning problems are stated as finding a sequence of actions that reaches certain goal. One of the most successful techniques for solving planning problems is a concept of plan- ning graphs and the related GraphPlan algorithm. In the thesis we identified a weak point of the original GraphPlan algorithm which is the search for actions that support certain goal. We proposed to model this problem as a constraint satisfaction problem and we solve it by maintaining arc-consistency. Several propagation variants for maintaining arc-consis- tency in the model are proposed. The model and its solving process were integrated into the general GraphPlan-based planning algorithm. The performed experimental evaluation showed improvements in order of magnitude in several measured characteristics (overall solving time, number of backtracks) compared to the standard version of the GraphPlan algorithm. Next we proposed a stronger consistency technique for pruning the search space during solving the problem of finding supports. It is called projection consistency and it is based on disentangling the structure of the problem formulation. If the problem of finding sup- porting actions is...
|
|
|
Filtering Algorithms for Tabular Constraints
Molnár, Martin ; Barták, Roman (advisor) ; Surynek, Pavel (referee)
The thesis studies an implementation of arc-consistency filtering algorithms for constraints defined in extension. We propose a new concept of binarization for decomposing high-arity ad-hoc constraints into networks of binary constraints. A theory proving correctness of the binarization is developed. We study the existing algorithms from the perspective of our binarization concept and propose possible binarization schemes for ad-hoc constraints defined in some of the common forms. In the thesis we also propose the filtering algorithms for the elementary constraints. A compound propagator then uses the elementary constraint filtering algorithms to propagate over the high-arity constraint. Finally, we experimentally evaluate the proposed approaches on constraints generated when solving the planning problems.
|
|
|
Interactive scheduling and visualisation
Skalický, Tomáš ; Barták, Roman (advisor) ; Surynek, Pavel (referee)
The goal of this thesis was to design and implement a graphical tool for visualization and editing of schedules which would provide a function for automatic repairing of violated constraints in the schedule. The resulting application called a Gantt Viewer is integrated to the FlowOpt project that represents a complex solution for modeling workflows, creation of schedules from them and analysis of these schedules. The application has been developed with the focus on intuitiveness of the user interface and performance during the management of large schedules. It enables the user to visualize extended manufacturing schedules thanks to the cooperation with other modules of the FlowOpt project. Moreover, the Gantt Viewer incorporates a repair tool exploiting a new Repair-DTP algorithm which is both introduced and demonstrated in this work.
|
|
|
Constrained activity sequencing
Nguyen, Son Tung ; Barták, Roman (advisor) ; Čepek, Ondřej (referee)
Many scheduling problems can be seen as activity sequencing problems, where the activity sequence in demand satisfies certain constraints. A typical example is scheduling in the airline industry where the task is to assign to each aircraft a segment of flight and nonflight activities while guaranteeing certain required properties. This diploma thesis deals with such type of constrained activity sequencing. The aim is to propose a formal model of the problem, including specification of all constraints and objectives, capable of finding (near)optimal sequences of activities. The proposed model is based on Constraint programming techniques.
|
|
|
Algorithms for automated logistics
Tuláček, Michal ; Barták, Roman (advisor) ; Dvořák, Filip (referee)
This thesis deals with a real world problem of an optimal planning of transferring goods between stores of a certain retail company. The aim is to propose a system which, based on customer orders and current stock items availability, should be capable of devising an optimal plan. In this thesis, following a thorough analysis of the problem, there is a formalised problem of automated logistics. After a brief overview of existing approaches in the area of logistics problem solving, there are subsequently designed solution methods based on programming with limited conditions and mixed integer programming. Both methods are compared to each other experimentally, by taking into account the quality of the found solution and the methods' efficiency.
|
|
|
Interactive Gantt Charts
Skalický, Tomáš ; Barták, Roman (advisor) ; Vojtáš, Peter (referee)
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.
|
guest ::
