|
|
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
|
|
|
Virtual Warehouse
Hájek, Břetislav ; Barták, Roman (advisor) ; Švancara, Jiří (referee)
This thesis focuses on the creation of software for the visualization of a warehouse. That includes warehouse structure, items, orders, and stats around them. The software also provides a possibility to animate a movement of picker agents. The data structure is represented using ontology written in OWL language. There is no standard ontology for warehouse representation right now, so one of the goals of this thesis is to propose such representation. The benefits of using such ontology are the ability to share the data in a standard format across different software. The software also allows dynamic extension of this ontology The program has a modular structure that allows creating plugins for calculating custom metrics which will be then automatically visualized. 1
|
|
|
Multi-agent Path Finding
Švancara, Jiří ; Barták, Roman (advisor) ; Koenig, Sven (referee) ; Vokřínek, Jiří (referee)
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.
|
|
|
3D social network
Hruška, Lukáš ; Švancara, Jiří (advisor) ; Brom, Cyril (referee)
There are plenty of social networks which we use every day, though just a few of them do not follow the mainstream design in the form of infinitely long news feed with posts from people the user is interested in and the possibility of private communication using a chat or a private call. However, this project is in 3D space where every user controls his own character in a room full of other users. The 3D space with the modular design of the app adds a feature of extensibility in form of apps, where an app can be an object placed in the room, 2D app in menu interface, or an app controlling logic of the room. 1
|
|
|
Co-ordinated Path Finding for a Robot Swarm
Mestek, Jakub ; Barták, Roman (advisor) ; Švancara, Jiří (referee)
The thesis deals with finding of collision free paths for groups of robots from their initial locations to their target locations (Multi-agent Path Finding - MAPF). The target locations are inputted only as a set of locations for each group, a particular assignment of agents to locations is not given. Therefore, it is a group (team, colored) variant of the MAPF problem. As a part of this thesis, an application was developed that enables users to enter an initial and target configuration of robots and to find the shortest possible collision free plans. These plans can be visually simulated and it is possible to generate from them programs executable on Ozobot Evo robots. 1
|
|
|
Artificial Inteligence for Draughts
Bělíček, David ; Švancara, Jiří (advisor) ; Hric, Jan (referee)
Draughts is a board game that is played all around the world in various forms. The aim of this thesis is to describe and implement an artificial intelligence algorithm that will be able to play draughts. We will explain the working of Minimax algorithm, how to enhance it using Alpha-Beta pruning, and its limited-depth version, which uses heuristic evaluations. We will present two hand-crafted heuristic evaluations, how such heuristic evaluation can be replaced with a neural network, and how to develop these networks using evolutionary algorithms. Finally, we will perform experiments in which we will test the created heuristics and networks. At the end of the thesis, we present a tournament that decides which of the developed algorithms is the best.
|
|
|
From abstract to executable plans
Wiesner, Robert ; Barták, Roman (advisor) ; Švancara, Jiří (referee)
This thesis delves into postprocesing on plans for Multi Agent Path Finding. The intent behind postprocesing is to chang the plans so they can be performed by real robots. Changes include reduction in wasted time and introduction of robustness. This thesis proposes five algorithms (later extended to ten), through which MAPF plans are being transfered to a significantly lower level of abstraction. Results were tested on sixty plans created by MAPF solver MAPF Scenatio over five maps. Some resulting plans were tested in real life on robots Ozobot Evo. Results indicate that significantly lower makespan and greater robustness can be achieved through postprocessing. This study also indicates that various algorithms are more effective for certain types of plans.
|
guest ::
RSS feed.