|
|
Practical Exercises for Artificial Intelligence
Mařík, Matouš ; Švancara, Jiří (advisor) ; Zelinka, Mikuláš (referee)
The thesis describes practical tasks for the lecture of Artificial Intelligence, that is to introduce students to basic structures and algorithms of this field of informatics: rational agent, uninformed and informed search, adversarial search and algorithms solving constraint satisfaction problems. It consists of the motivation for their creation, their implementation and documentation.
|
|
|
Traffic - Road Network Simulation Game
Kripner, Matěj ; Ježek, Pavel (advisor) ; Švancara, Jiří (referee)
The goal of this thesis was to implement the mobile game Traffic, in which the player controls a car and navigates through a road network. The general concept of the game is based on our vision of a game simulating the experience of driving that would be different from similar existing games. This vision proved to be overly complex. Therefore, we selected only a subset of its features while ensuring that the resulting game can serve as a basis for future extension towards the original vision. We targeted the Android operating system and used the Unity game engine and C# for implementation. In the resulting game, the player acts as a taxi driver, i.e. they pick up customers and drop them off at designated locations. The player receives game money and rating based on the quality of each ride. The game world contains roads, intersections, sidewalks, buildings and pedestrians. The game world can be edited by a game designer with no programming skills. The designer can shape the roads and sidewalks using Bézier curves and connect roads into intersections. The shape of intersections is generated automatically. 1
|
|
|
Crustal Structure of the Bohemian Massif Based on Seismic Refraction Data
Hrubcová, Pavla ; Vavryčuk, Václav (advisor) ; Plomerová, Jaroslava (referee) ; Švancara, Jan (referee)
The deep structure of the Bohemian Massif, the largest stable outcrop of the Variscan rocks in central Europe, was studied using the data of the international seismic refraction and wide- angle reflection experiments CELEBRATION 2000, ALP 2002 and SUDETES 2003. The data were interpreted by seismic tomographic inversion and by 2-D trial-and-error forward modelling of the P and S waves. Above, additional constraints on the crustal structure were imposed by reflectivity or gravity modelling, and by receiver function interpretation. Knowledge of the crustal velocity structure in the Bohemian Massif was complemented by its azimuthal variation. Though consolidated, the Bohemian Massif can be subdivided into several tectonic units separated by faults, shear zones, or thrusts reflecting varying influence of the crust forming processes. The resultant velocity models determined different types of the crust-mantle transition reflecting variable crustal thickness and delimiting contacts of these tectonic units at depth.
|
|
|
Finding Minimum Satisfying Assignments of Boolean Formulas
Švancara, Jiří ; Balyo, Tomáš (advisor) ; Trunda, Otakar (referee)
In this thesis we examine algorithms and techniques used for solving Boolean satisfiability (SAT). Then we inspect the possibility to use them in solving the weighted short SAT problem, which is a generalization of the satisfiability problem. Given that each variable has a weight, this generalization is the problem of finding a satisfying truth assignment while using the smallest sum of weights. To solve this problem, we introduce three truth assignments of variables - True, False and Unassign. We show that not all algorithms and techniques used in modern SAT solvers can be used in our program. Those that can be converted, will be implemented using our three truth assignments. This will yield several versions of our new solver, which will be compared. Powered by TCPDF (www.tcpdf.org)
|
|
|
Multi-agent Path Finding
Švancara, Jiří ; Barták, Roman (advisor)
Multi-Agent Path Finding (MAPF) is the task to find efficient collision-free paths for a fixed set of agents. Each agent moves from its initial location to its desired destination in a shared environment represented by a graph. The classical definition of MAPF is very simple and usually does not reflect the real world accurately. In this thesis, we try to add several attributes to the MAPF definition so that we overcome this shortcoming. This is done in several steps. First, we present an approach on how to model and solve MAPF via reduction to Boolean satisfiability using Picat programming language. This provides us with a useful model that can be easily modified to accommodate additional constraints. Secondly, we modify MAPF to portray a more realistic world. Specifically, we allow new agents to enter the shared environment during the execution of the found plan, and we relax the requirement on the homogeneousness of the shared environment. Lastly, we experimentally verify the applicability of the novel models on real robots in comparison with the classical MAPF setting.
|
|
|
Multi-agent picker routing problem
Krejčí, Jiří ; Barták, Roman (advisor) ; Švancara, Jiří (referee)
An important part of warehouse operations is order picking, which is the process of collecting products from stocking locations. In our case, a scattered storage warehousing strategy is assumed. Items are stored at multiple locations scattered through the ware- house. Usually, multiple order pickers are responsible for a quick collection of items. That can result in order pickers blocking each other, reducing the picking throughput. Most of the existing picker routing algorithms are not concerned with picker blocking, even though its effect on picking efficiency can be substantial. It is the objective of this thesis to address the picker routing problem in a multi-agent environment. First, the literature is surveyed and then a multi-agent picker routing algorithm is presented. The algorithm is based on the idea of prioritized planning. Results of the empirical evaluation indicate that the multi-agent approach leads to better quality solutions. 1
|
|
|
Graph pruning for multi-agent pathfinding
Husár, Matej ; Švancara, Jiří (advisor) ; Ivanová, Marika (referee)
In this thesis, we focus on improving the overall length of the calculation for the optimal multi-agent pathfinding which is an NP-hard problem, therefore we will look for a solution using a SAT solver. In order to achieve this result, we will be using graph pruning. This consists of removing such vertices from the original graph that the agents do not have to use and therefore such vertices represent an unnecessary burden for the SAT solver. To solve this problem we propose three algorithms that will be compared experimentally with the basic common algorithm. When comparing the proposed algorithms we will be interested in their overall speed of the calculation and also in the optimality of the result found by them. We will show that one of the proposed algorithms maintains optimality and also brings significant acceleration in the calculation on large graphs.
|
|
|
Path planning for multi-robot warehouses
Tauchmanová, Klára ; Barták, Roman (advisor) ; Švancara, Jiří (referee)
Thesis covers the problem of finding non-colliding paths in automated warehouses for a group of agents - so called Multi-agent pickup and delivery (MAPD) problem. Agents in the warehouses are constantly engaged with new tasks which require picking up the object on certain coordinates and transporting it to another place in the warehouse. The- sis describes a hierarchical algorithm for MAPD problems that plans paths in two levels - global and local. The algorithm works with a warehouse environment manually divided into sectors. Planning on the global level consists of assigning tasks to free agents and selecting a sequence of sectors to go through. The task is always assigned to the closest free agent. On the local level, the actual path through the sector is planned using modi- fied Multi-agent path finding (MAPF) algorithms. The proposed algorithm was tested in a simulated environment. We showed that the hierarchical algorithm with Conflict-based search (CBS) on the local level has a smaller runtime and finds a solution with a lower makespan than the algorithm using reduction to SAT. Further, we showed that the hierar- chical approach for MAPD significantly lowers the runtime of the algorithm, meanwhile, the outputted solutions are not much worse than for non-hierarchical approaches. 1
|
|
|
Solving multi-agent pathfinding via incremental SAT
Agh, Juraj ; Švancara, Jiří (advisor) ; Barták, Roman (referee)
Incremental SAT (satisfiability) is a way of determining the satisfiability of a formula repeatedly based on the previous determination. Multi-Agent path finding is a task of finding paths for a fixed set of agents in a shared environment without any collisions. When we require an optimal solution of MAPF using a SAT solver, we iterate through repeated formulae, each adjusted to the length of the solution. This leads us to use Incremental SAT solver. In this work, we try to solve the problems that arise during application of Incremental SAT solver to the MAPF. This is done in several steps. Firstly, we introduce some approaches to solve MAPF with a basic SAT solver. We model these approaches in C++ language, which provides us with some simply modifiable models for creating formulae. In the next step, we modify the better model to a model using an Incremental SAT solver. Thus at every iteration the model instead of creating a new formula, only extends the old formula. Lastly, we compare these approaches solving MAPF with an Incremental SAT solver.
|
|
|
Scalable dynamic graph-based vehicular routing
Polický, Adam ; Kratochvíl, Miroslav (advisor) ; Švancara, Jiří (referee)
Algorithms for finding shortest paths in large graphs form an essential part of many modern navigation and routing systems. In vehicular navigation, the problem is compli- cated by dynamic nature of the network caused by road closures and changes in traffic, preventing application of many common speed-up techniques. The aim of this thesis is to design an algorithm for finding paths in large graphs that gains efficiency and scalability by minimizing the number of visited graph objects in storage. This was achieved by itera- tively simplifying the graph into a multi-layered approximative structure, and developing a modification of Dijkstra's algorithm that allow efficient navigation in the structure. The results show that the proposed method examines 4× less graph objects than A* and 14× less than Dijkstra, achieving better performance at the cost of slightly longer discovered paths. Additionally, the layered structure is able to accommodate changes in the base graph, allowing the algorithm to work on a changing network without costly recomputations. 1
|
guest ::
RSS feed.