|
|
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
|
|
|
The Effectiveness of Centralized Planning for Intersections
Cizl, Eliáš ; Švancara, Jiří (advisor) ; Ivanová, Marika (referee)
Vehicle navigation on roads is a complex problem that will probably be solved by using artificial intelligence in key roles. Today, there are cars capable of autonomous driving, but they are dependent on an old infrastructure that primarily includes intersections designed for human drivers. This thesis opens a new chapter in the area of autonomous intersection management (AIM). Most research to date has only looked at how best to implement a solution for a single intersection. We have created a simulation that runs in real time, where up to several dozen intersections appear side by side. In this work, we conduct experiments where we test different layouts of the autonomous algorithms along with traffic lights. Autonomous intersections clearly win with their efficiency, and in larger cities it's most advantageous to deploy them at the busiest intersections. 1
|
|
|
Artificial intelligence algorithms for chess
Ivanová, Marika ; Petříček, Martin (advisor) ; Iša, Jiří (referee)
The primary objective of this thesis is to study and summarize the current algorithms used in computer chess and their subsequent implementation. The thesis includes a program that in addition to regular single-player game of chess against the computer leaves the user the option of used algorithms and setting their parameters. The theoretical part focuses on chess programming procedures and their illustrative explanation. Several experiments were performed with artificial intelligence algorithms and their results are presented here.
|
|
|
Detection of inconsistencies during multi-agent plans' execution
Mintál, Samuel ; Barták, Roman (advisor) ; Ivanová, Marika (referee)
In reality agents do not always execute their plans perfectly. Due to various reasons that are not foreseeable by the plans, agents tend to deviate from the assigned plans over time. These inaccuracies in execution can result from ordinary delays to fatal collisions. The contribution of this work is a research of the area dealing with the detection of potential collisions and creating an environment where errors can be injected into agent plans. This environment also makes it possible to determine the severity of events that are implied by the injected errors. The last contribution of this work is a proposal and a subsequent implementation of selected collision detection techniques, which we will compare at the end of the thesis.
|
|
|
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.
|
|
|
Kooperativní hledání cest s protivníkem
Ivanová, Marika ; Surynek, Pavel (advisor) ; Mrázová, Iveta (referee)
Presented master thesis defines and investigates Adversarial Cooperative Path-finding problem (ACPF), a generalization of standard Cooperative Path-finding. In addition to the Cooperative path- finding where non-colliding paths for multiple agents connecting their initial positions and destinations are searched, consideration of agents controlled by the adversary is included in ACPF. This work is focused on both theoretical properties and practical solving techniques of the considered problem. ACPF is introduced formally using terms from graph theory. We study computational complexity of the problem where we show that the problem is PSPACE-hard and belongs to EXPTIME complexity class. We introduce and discuss possible methods suitable for practical solving of the problem. Considered solving approaches include greedy algorithms, minimax methods, Monte Carlo Tree Search and adaptation of algorithm for the cooperative version of the problem. Surprisingly frequent success rate of greedy methods and rather weaker results of Monte Carlo Tree Search are indicated by the conducted experimental evaluation. Powered by TCPDF (www.tcpdf.org)
|
|
|
Artificial intelligence algorithms for chess
Ivanová, Marika ; Petříček, Martin (advisor) ; Iša, Jiří (referee)
The primary objective of this thesis is to study and summarize the current algorithms used in computer chess and their subsequent implementation. The thesis includes a program that in addition to regular single-player game of chess against the computer leaves the user the option of used algorithms and setting their parameters. The theoretical part focuses on chess programming procedures and their illustrative explanation. Several experiments were performed with artificial intelligence algorithms and their results are presented here.
|
guest ::
RSS feed.