|
|
Algorithms for Multi-Agent Pickup-and-Delivery Problems
Šmíd, Petr ; Barták, Roman (advisor) ; Ivanová, Marika (referee)
In this thesis, we explore the world of Multiagent pickup and delivery algorithms. Basic definitions, as well as simple extensions, are introduced to the reader. State-of-the- art algorithms are thoroughly described, analyzed, and tested in various environments based on multiple conditions. We describe the scalability of the algorithms and demon- strate it in multiple scenarios. The thesis includes a short overview of explainable plans, their motivation, and their implementation. Support software was created for conducting experiments, visualization, and making explainable plans. 1
|
|
|
Constructing policies for multi-agent path finding
Mestek, Jakub ; Barták, Roman (advisor) ; Švancara, Jiří (referee)
The thesis deals with the Multi-Agent Path Finding problem. The task is to find for each agent a path from its current location to its destination in such a way that agents will not collide. A novel approach to solving this problem in non-deterministic environment is suggested. That is to look for a solution in form of policies that prescribe which action the agent should perform in given situation. 1
|
|
|
Autonomous traffic junction
Kotal, Jiří ; Barták, Roman (advisor) ; Švancara, Jiří (referee)
Práce se zabývá problematikou průjezdů vozů plně automatizovanou křižovatkou a to z pohledu multi-agentního hledání cest (MAPF, multi-agent path finding). Cílem je pro- zkoumat různé abstrakce křižovatky a různé přístupy pro hledání nekolizního průjezdu křižovatkou. Zkoumané techniky jsou implementovány a empiricky porovnány v simulo- vaném prostředí. 1
|
|
|
Reduction-based Solvers for Multi-agent Pathfinding: Comparing Different Models
Ramesh, Samyuktha ; Švancara, Jiří (advisor) ; Barták, Roman (referee)
- Samyuktha Ramesh Thesis Title: Reduction-based Solvers for Multi-agent Pathfinding: Comparing Different Models Multi-agent path finding (MAPF) is the problem of navigating a set of agents from their starting position to their respective goal position without any collisions. In this thesis, we provide an overview of the current approaches to solving MAPF. We implement six different encodings found in the literature using the Python programming language and the Glucose3 SAT solver. We run experiments on maps of different types and sizes to compare the performances of the encodings.
|
|
|
Heuristic Learning for Domain-independent Planning
Trunda, Otakar ; Barták, Roman (advisor) ; Onaindia, Eva (referee) ; Komenda, Antonín (referee)
Automated planning deals with the problem of finding a sequence of actions leading from a given state to a desired state, e.g., solving Rubik's Cube, delivering parcels, etc. The state-of-the-art automated planning techniques exploit informed forward search guided by a heuristic, where the heuristic estimates a distance from a state to a goal state. In this thesis, we present a technique to automatically construct an efficient heuristic for a given planning domain. The proposed approach is based on training a deep neural network using a set of previously solved planning problems from the same domain. We use a novel way of extracting features for states which doesn't depend on usage of existing heuristics. The trained network can be used as a heuristic on any problem from the domain of interest without any limitation on the problem size. Our experiments show that the technique is competitive with popular domain-independent heuristic. We also introduce a theoretical framework to formally analyze behavior of learned heuristics. We state and prove several theorems that establish bounds on the worst-case performance of learned heuristics.
|
|
|
Personal Timetabling
Doležal, Lukáš ; Barták, Roman (advisor) ; Duša, Vladimír (referee)
Despite all the advancements in Artificial Intelligence, we still do not have a broadly available application for automated scheduling of personal activities. The main difficulty in creating such an application is satisfying user's diverse expectations about time organization. In this study we focused on creating a tool that can help users with organizing their time. We designed a model for describing personal activities with user preferences. We formulated scheduling of personal activities as an optimization problem for which we designed and implemented a solving algorithm, aiming to schedule activities with precision of seconds. We created a prototype of web-calendar application powered by this model and an algorithm which we designed with the focus on ability to clearly display user's time and easily insert activities for automated scheduling. The web application is backed by RESTful API which enables implementing application on various platforms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Portfolio Optimisation
Huml, Tomáš ; Barták, Roman (advisor) ; Surynek, Pavel (referee)
The goal of this work is to propose an algorithm selecting an optimal portfolio from input projects, which are assessed by costs, profits and potential risk. Any interdependencies can be defined among these input projects. Summary of alternative approaches concerning this topic is part of this work too. Program implementing proposed algorithm is attached to this work. Output of program computation is a portfolio achieving the highest possible profit as well as satisfying all of input constraints and defined interdependencies among the projects. The program allows graph comparison of resulted portfolios and provides detail information about each portfolio.
|
|
|
Workflow Modelling
Rovenský, Vladimír ; Barták, Roman (advisor) ; Surynek, Pavel (referee)
The goal of this thesis was to design and implement a graphical editor for workflow modelling, focusing on productivity, simplicity and usability for the common user. The resulting application is integrated into the FlowOpt project, in which the workflows can be used to manage manufacturing processes in small and medium size factories. The workflow editor should serve among other things as a proof of concept of practical usability of the Nested TNA workflow model. The main parts of the thesis include a working implementation of the editor, a procedure for automatic verification of the workflows and support of the XPDL (BPMN) standard for saving workflows.
|
|
|
Solving Boolean satisfiability problems
Balyo, Tomáš ; Surynek, Pavel (advisor) ; Barták, Roman (referee)
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.
|
|
|
Constraint modelling
Haničinec, Tomáš ; Barták, Roman (advisor) ; Surynek, Pavel (referee)
Constraint programming is one of the possible ways how to solve complicated combinatorial (and other) problems. We model a problem using variables representing real world objects and constraints representing various relations between the objects. However, there are often many possible ways how to model a problem. And what's more, the choice of a modeling strategy can a®ect the resulting efficiency dramatically. Unfortunately, there is no general recipe how to model problems e±ciently. Nevertheless there are still several modeling techniques, heuristics or advices that could improve the e±ciency of models. Some of these techniques are problem dependent, some can be applied only to a certain classes of problems but they still often help. This thesis is trying to give more or less complete list of the most important modeling techniques along with an explanation of why, how and for which classes of problems they work best and also with empirical results underlying the presented facts.
|
guest ::
