Dissertation theses
Counterexample Guided Abstraction Refinement for Multi-robot Planning
Supervisor
Level
Topic of dissertation thesis
Topic description
Counterexample guided abstraction refinement (CEGAR) is a successful technique in model checking [1,2]. Within the proposed topic, the task is to investigate the possibilities of using the CEGAR technique in multi-robot planning [3,4]. Planning with many robots offers a lot of scope for designing abstractions of the problem that bring appropriate simplifications and allow the solver to solve the problem more easily, for example, some robots in the problem can be ignored, but at the cost of inaccuracies in the resulting solution. The design, search, and checking of counterexamples for a multi-robot system, with the help of which it would be possible to eliminate inaccuracies in the solution, represents another interesting challenge. Some progress has been made in multi-robot path planning, where the abstraction refinement has been made against collisions between robots. However, abstractions for path planning represent only a special case, while within this topic we would like to move the design of abstractions further towards more general multi-robot systems, where the range of robot actions is wider. An interesting direction is the extension of the CEGAR technique with abstractions that produce inaccuracy in the solution, against which the multi-robotic system is robust, and therefore there is no need to refine them.
Literature
- [1] Edmund M. Clarke, Anubhav Gupta, Ofer Strichman: SAT-based counterexample-guided abstraction refinement. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 23(7): 1113-1123 (2004)
- [2] Anubhav Gupta, Edmund M. Clarke: Reconsidering CEGAR: Learning Good Abstractions without Refinement. ICCD 2005: 591-598
- [3] Teng Guo, Si Wei Feng, Jingjin Yu: Polynomial Time Near-Time-Optimal Multi-Robot Path Planning in Three Dimensions with Applications to Large-Scale UAV Coordination. IROS 2022: 10074-10080
- [4] Lydia E. Kavraki, Steven M. LaValle: Motion Planning. Springer Handbook of Robotics, 2nd Ed. 2016: 139-162
Lazy Compilation for Classical Planning
Supervisor
Level
Topic of dissertation thesis
Topic description
In automated planning, the task is to find a sequence of actions that, after performing, meet a certain goal [1, 2]. This topic specifically focuses on compilation of the planning task into another formalism, such as constraint satisfaction (CSP) [3] or propositional satisfiability (SAT) [4]. Especially promising seems to be the lazy compilation, when the task is encoded into the target formalism incompletely. The encoding is subsequently refined in cooperation with the solver by generating counterexamples. The lazy compilation technique has been successfully used in the specific domain of multi-agent path finding [5]. However, the generalization of lazy compilation for classical planning is still an open question.
Literature
- [1] Malik Ghallab, Dana S. Nau, Paolo Traverso: Automated Planning and Acting. Cambridge University Press 2016, ISBN 978-1-107-03727-4
- [2] Malik Ghallab, Dana S. Nau, Paolo Traverso: Automated planning - theory and practice. Elsevier 2004, ISBN 978-1-55860-856-6, pp. I-XXVIII, 1-635
- [3] Rina Dechter: Constraint processing. Elsevier Morgan Kaufmann 2003, ISBN 978-1-55860-890-0
- [4] Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications 185, IOS Press 2009, ISBN 978-1-58603-929-5
- [5] Pavel Surynek: Unifying Search-based and Compilation-based Approaches to Multi-agent Path Finding through Satisfiability Modulo Theories. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 1916-1922, Macau, China, International Joint Conferences on Artificial Intelligence, 2019, ISBN (Online): 978-0-9992411-4-1
Multi-agent Path Finding in Continuous Spaces
Supervisor
Level
Topic of dissertation thesis
Topic description
Specialist supervisor: doc. Dipl.-Ing. Dr. techn. Stefan Ratschan
Multi-agent path finding (MAPF) is the problem of computing collision-free paths from given starting positions to goal positions for a set of agents [1,2]. The MAPF problem is motivated by a number of real-world applications, for example agents can model robots for transporting goods in warehouses. Traditional solutions to this problem are based on models where both time and space are discrete. However, continuous models would be more realistic. The current state-of-the-art in this topic allows agents to move continuously along linear trajectories [3,4]. The goal of this work is to contribute to more general techniques, for example to allow agents to move along non-linear trajectories, or to model certain kinematic properties of agents, such as acceleration, or other properties that manifest themselves in a continuous model of the problem.
Literature
- [1] David Silver: Cooperative Pathfinding. AIIDE 2005: 117-122
- [2] Ko-Hsin Cindy Wang, Adi Botea: MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees. J. Artif. Intell. Res. 42: 55-90 (2011)
- [3] Thayne T. Walker, Nathan R. Sturtevant, Ariel Felner: Extended Increasing Cost Tree Search for Non-Unit Cost Domains. IJCAI 2018: 534-540
- [4] Anton Andreychuk, Konstantin S. Yakovlev, Pavel Surynek, Dor Atzmon, Roni Stern: Multi-agent pathfinding with continuous time. Artif. Intell. 305: 103662 (2022)
Bachelor theses
Prediction of Dota 2 Game Result
Author
Filip Beskyd
Year
2018
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Karel Klouda, Ph.D.
Department
Summary
Theoretical part of this thesis will focus on briefly clarifying decision tree and artificial neural network theory and explain basic factors that have significant impact on game result. In practical part, focus is set on experimenting with used machine learning technique's parameters, extending input data by information regarding hero compositions, compare and evaluate performance of these extensions. All of this resulting in implementation of experimental program which will produce predictive ANN model. This model can be used later to predict the outcome of the game based on knowing initial team's hero compositions.
Benchmarks for Multi-Agent Path Finding
Author
Tomáš Vlk
Year
2019
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
MSc. Juan Pablo Maldonado Lopez, Ph.D.
Department
Summary
Multi-agent pathfinding is an important problem with vast and varied use cases. However, its algorithms are mostly benchmarked solely on grid graphs. Aim of this thesis is to fix this by providing other types of graphs, as well as, means to generate them. It also provides some testing on those generated graphs, as well as, the results and analysis of them.
Processing and Editing the Outputs of Automated Music Transcription
Author
Zuzana Fílová
Year
2019
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Daniel Dombek, Ph.D.
Department
Summary
The subject of this bachelor thesis is focused on the automatic music transcription (AMT). The basic information related to this problematic, the state of the art in the solution of AMT and the problems tackled in this research domain are summarized in the theoretical part of this work. The approaches to the evaluation of results obtained by different AMT systems are also given. It has been found that unsatisfactory results are reached by AMT till now. Resulting music representation (MIDI file or sheet music) contains many errors that make it impossible to use this technology in practice.
Therefore, in the practical part of the thesis, an analysis of the most common errors generated by the automatic transcription of a wave audio recording into a format MIDI were analyzed. Based on this analysis, a method for automatic removal of these errors and modification of acquired MIDI file is proposed. The goal of these modifications was to improve the success of the automatic music transcription system. The success of the proposed method was evaluated by F-measure and edit distance of the musical strings.
The experiments presented in the final part of the thesis showed that the proposed method of adjustment increases the similarity of the resulting sheet music with the original and contributes significantly to the better readability of the resulting sheet music.
Visual Analysis of Plans for Multi-Agent Path Finding with Continuous Time (MAPF-R)
Author
Evgenii Abdalov
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Josef Pavlíček, Ph.D.
Department
Summary
This thesis is dedicated to creation of visualization tool in order to convey
visual analysis of Multi Agent Path Finding with Continuous Time(MAPF-R)
problem. It describes MAPF-R problem, then it continues with description of
development of visualization tool and economic evaluation of its usage poten-
tial in logistics domain.
Evacuation Planning Based on Local Cooperative Pathfinding Techniques
Author
Róbert Selvek
Year
2019
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
MSc. Juan Pablo Maldonado Lopez, Ph.D.
Department
Summary
This thesis addresses the problem of evacuation from buildings and open areas from the perspective of cooperative path-finding algorithms. We define a problem called Multi-Agent Evacuation based on undirected graphs with agents (such as people, robots, or game characters) located in their vertices. Each vertex can either be marked as safe or as endangered. The task consists of moving the agents from endangered to safe vertices as quickly as possible.
There are centralized algorithms for solving this problem that are optimal with respect to various objectives. Such algorithms are hardly applicable to real-world scenarios because real agents are unable to follow the centrally generated plan and must react to changes in the environment. Therefore, we designed and implemented an evacuation planning algorithm based on local cooperative path finding techniques. Simulations on various realistic situations show that solutions generated by this algorithm are of a quality similar to the solutions from centralized algorithms.
Application of Artificial Neural Networks in Solving the (N^2-1)-Puzzle
Author
Vojtěch Cahlík
Year
2020
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Daniel Vašata, Ph.D.
Department
Summary
The thesis focuses on the usage of artificial neural networks in near-optimal solving of the (N^2-1)-puzzle. In the first part of the thesis, possible applications of artificial neural networks in solving the puzzle are analyzed, and it is found that the most effective way is to use them as a heuristic for state-space search algorithms. Later in the thesis, several heuristics based on deep artificial neural networks are trained, and they are evaluated on a set of benchmarks. When used together with the A* algorithm, the solutions obtained with the new heuristics are optimal most of the time, while the number of expanded nodes is significantly lower than that in comparable admissible and non-admissible heuristics.
Multi-agent Path Finding for Connected Robots
Author
Martin Zukal
Year
2020
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Pavel Hrabák, Ph.D.
Department
Summary
This work is focused on comparing two different algorithms dealing with the problem of multi-agent path finding for connected robots.One of the algorithms, which converts the above mentioned problem to the problem of the Boolean problem of satisfiability, is explained in detail.
Resolving Collisions among Geometric Robots in Continuous Space
Author
Yana Zabrodskaya
Year
2020
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Ivan Šimeček, Ph.D.
Department
Summary
This thesis describes the problem of avoiding collisions among robots in pathfinding. First, the algorithm for finding a shortest collision free path for two robots of any geometric shape is proposed. Then the algorithm is theoretically and experimentally evaluated and an analysis of the economic impact of using autonomous robots in warehouses and retail stores is performed.
Simulation of Centralized Algorithms for Multi-Agent Path Finding on Real Robots
Author
Ján Chudý
Year
2020
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
Mgr. Vojtěch Rybář
Department
Summary
The simulation of multi-agent pathfinding solutions is essential for research but also in educational demonstrations. Most of the time, the simulation is only displayed on a screen without the use of robotic agents. If robots are used, they get a sequence of commands they need to execute, or they receive the commands gradually, to follow their planned paths correctly. This work proposes a novel approach to simulation of centralized multi-agent pathfinding algorithms on physical agents called ESO-Nav. In this approach, the agents are not part of the planning process, nor do they have any information about their paths. The agents have a simple predetermined behavior in an environment and navigate in it based on the environment outputs. A working prototype of a simulator that utilizes this novel approach was implemented for a group of Ozobot Evo robots.
Adapting the Conflict-based Search Algorithm for Alternative Objectives
Author
Berker Katipoglu
Year
2020
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Michal Valenta, Ph.D.
Department
Summary
The Multi-Agent Path Finding (MAPF) is an important type of planning problem in artificial intelligence. There are many applications of MAPF and each application has its own priorities, which gives MAPF many different variations. With the increasing interest of researchers on this topic, new algorithms developed for solving different variations of MAPF in the recent years. Conflict Based Search (CBS) is one of those algorithms, which is currently the state-of-art for solving MAPF instances with sum-of-cost objective function. In this paper, we will discuss how to adapt CBS for makespan objective function, emprical comparison of the difficulty of solving MAPF instances with CBS under sum-of-costs and makespan objective functions, and ways to improve the behaviour of CBS with makespan objective function. Experimental results show that solving makespan is easier than solving sum-of-costs, and it is possible to adjust the algorithm for the objective function to obtain better performance.
Compilation of Path Finding Algorithms for a Group of Small Mobile Robots
Author
Nestor Popov
Year
2020
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
RNDr. Luděk Kleprlík, Ph.D.
Department
Summary
Compilation possibilities of multi-agent pathfinding algorithms on group of small robots -- Ozobot Evo are researched in this thesis. Starting and goal positions on predifined map which is representation of grid graph are assigned to each robot. Theese robots should move to their goal positions following the condition that no collision between robots could occur. In this work framework for robots Ozobot Evo is implemented, which allows theese robots to follow pathes that were the output from multi-agent path finding algorithms. Functionallity of this framework is verified in relevant experiments.
Controlling Mobile Agents by Finite Automatons in Adversarial Scenarios
Author
Dominik Šmejkal
Year
2020
Type
Bachelor thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
RNDr. Kateřina Trlifajová, Ph.D.
Department
Summary
In this thesis we analyse the possibility of utilizing finite automatons for local management of agents competing in achieving target positions against another team of agents. There are several algorithms to solve this problem, which are either centralized or assume a way of communication between agents.
The method of local management of agents by a finite automaton presented by us is distributed and agents plan their moves independently of the others. To reduce the number of collisions among agents, we use a finite automaton that plans another move for agents, provided that it avoids obstacles. We learned the parameters of a finite state machine with an evolutionary algorithm and created a more successful solution. Tests showed high scheduling speed even for higher numbers of managed agents, but solution was not very successful against teams controlled by slower separate algorithms, such as IADPP. Conversely, in scenarios with an opponent controlled by the A * algorithm, teams locally controlled by a finite state machine were highly efficient.
Formation Maintenance in Multi-Agent Pathfinding
Author
Jan Lidák
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Dr. techn. Ing. Jan Legerský
Department
Summary
This thesis addresses the problem of formation maintenance in multi-agent pathfinding on grid graphs. At the beginning, it introduces concepts and algorithms for basic pathfinding, multi-agent pathfinding and formations. Together with term definitions, this helps the reader navigate through the rest of the thesis.
Algorithm solving said problem was developed and implemented. This was done in Python, together with a visualization of resulting paths. It supports movement in formation, together with the ability to rate formation deviation based on real distance. This prevents formations to be split by an obstacle.
Performance was measured with a set of formations and scenarios. Data from said testing is presented with the help of tables and graphs, together with a short discussion regarding the results.
Automated Music Generation
Author
Adam Beckert
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Magda Friedjungová, Ph.D.
Department
Summary
This bachelor thesis describes the algorithmic generation of music, it gives an overview of existing solutions in the process of automatic composition and their results. This summary predominantly describes the advantages and disadvantages of different approaches to the issue.
The next section describes structures from music theory, state transition systems, and probabilistic introduction. These structures are the basis for the synthesis of the transition between two songs.
The practical part defines constraints on the MIDI songs used as input to the system. The system is separated into two parts: the analyzer and the generator. The analysis uses concepts from music theory to create an internal representation, which is then used to create Markov chains. This model and other attributes from the analysis are then given to the generator.
The system is subjectively evaluated.
Hierarchical Control of Swarms during Evacuation
Author
Kristýna Janovská
Year
2022
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Pavel Hrabák, Ph.D.
Department
Summary
In this work I propose a hierarchical system of multi-agent coordination for simulating evacuations. I distinguish between two types of agents. Leaders communicate between themselves and escort their swarms to a safe location, while followers follow their leader. For this multi-agent path finding algorithms are used.
I propose multiple models varying both in leaders' behavior towards their respective swarms and followers' behavior considering their attempts at individual evacuation.
In the work I perform experiments, whose results will show how parameters of agents' behavior influence the success of an evacuation. Results of these experiments will point out advantages of communication between leaders, problems, that might occur during an evacuation and their connection to agents' inadequate behavior.
Local Coordination and Planning for Robotic Soccer
Author
Tomáš Valenta
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Karel Klouda, Ph.D.
Department
Summary
The goal of this thesis is examine relevant techniques of design local agent coordination with the possibility of application in robotic football. Decision trees are used for inner mechanism of agents and for their construction we are using the ID3 algorithm. Furthermore, software prototype is created and relevant data are gathered from simulations of simple situations. Finally, the created agents are tested in various simulations. Their results are compared with other approaches.
Hierarchical Coordination of a Multi-robot Construction Team in the Minecraft Game
Author
Vít Šprachta
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Ivan Šimeček, Ph.D.
Department
Summary
Minecraft is a sandbox computer game, in which the player finds himself in a cubic world and has a free hand over he will do. In particular, what, where and how he pleases to build anything.
Multi-agent collective robotic construction is a problem where a group of robots are tasked to build a three-dimensional structure from blocks. Robots can carry, pick up and lay down individual blocks. Because the blocks are usually placed on a grid, Minecraft offers an interesting simulation environment.
Based on the theoretical background of collective robotic construction, this thesis designs its own hierarchical multi-agent system. The design takes into account the occasional need to construct scaffolding to reach otherwise inaccessible places, while also trying to ensure good scalability to larger structures consisting up to hundreds of thousands blocks.
The system is then implemented in form of an extension (mod) to the game Minecraft and follow-up experiments proves the system is able to build any structure while keeping very good scalability.
Local and Systematic Algorithms for Solving Generalized Variants of Sudoku
Author
Marek Nevole
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Ivan Šimeček, Ph.D.
Department
Summary
The aim of this thesis was to apply algorithms of systematic and local search on a generalized variant of the game Sudoku modeled as a constraint satisfaction problem. The question was which approach would achieve better results. In the first part we present the formulation of problems as constraint satisfaction problems, as well as algorithms used to solve these problems. In the second part, we apply general and theoretical background to the game of Sudoku. The last part contains experiments of individual algorithms and mutual comparison together with a discussion of the results. Experiments have shown that systematic algorithms can better solve game boards whose state space is smaller or can be reduced. Local algorithms gain an advantage in the opposite case, but generally require a larger time limit.
Continuous Motion Planning for Autonomous Vehicles at an Intersection
Author
Ladislav Miklík
Year
2022
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Pavel Hrabák, Ph.D.
Department
Summary
This work serves as an introduction into the topic of continuous multi-agent path planning and presents its own solution to this problem. The implemented method is based on the representation of feasible paths of a vehicle, discretization of a coordination space and searching this space for an optimal path utilizing A* algorithm. A throughput of 2.93 cars per second was reached using an optimal approach and 2.47 cars per second using a real-time computation (7.6ms to compute).
Discrete Simulation of Automobile Traffic with Continuous Time
Author
Patrik Schweika
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. RNDr. Tomáš Valla, Ph.D.
Department
Summary
In this thesis we deal with design and implementation of vehicle traffic simulator with discrete space and continuous time. The main intended use of the simulator is for comparison of route planning algorithms. We implement two distinct algorithms for route planning in the simulator. First one is Dijkstra's algorithm, which plan routes according to the shortest paths. Second is centralized algorithm based on maximum concurrent flow. Finally, we perform experiments in the simulator on prepared testing scenarios, where we compare the algorithms. Experiment results shown that the network throughput is significantly higher for flow-based algorithm. Documentation and user manual of the simulator can be found in the appendix.
Multi-agent Path Finding for Dynamic Goals in a Generalization of the Pac-man Game
Author
Lukáš Kameník
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
RNDr. Luděk Kleprlík, Ph.D.
Department
Summary
This bachelor thesis solves a multi-agent pathfinding problem with dynamic targets in a generalization of the Pac-Man game. This work aims to propose a method for planning the movement of multiple Pac-Men who chase frightened ghosts. Collisions should be avoided for Pac-Man. The work focuses on ways to effectively solve the problem of moving targets.
To solve the problem of multi-agent pathfinding with moving targets, algorithms from David Silver were used, namely Cooperative A*, Hierarchical Cooperative A* and Windowed Hierarchical Cooperative A*, and the Generalized Adaptive A* algorithm was used to effectively solve similar single-agent pathfinding problems. Using these algorithms, four new algorithms were created in this work, namely Cooperative Generalized Adaptive A* (CGAA*), Hierarchical Cooperative Generalized Adaptive A* (HCGAA*), Hierarchical+ Cooperative A * (H+CA*), and Hierarchical+ Cooperative Generalized Adaptive A* (H+CGAA*). The Cooperative Generalized Adaptive A* algorithm regularly achieves the best results. The benefit of this work is an algorithm that can be effectively used for more complex problems of multi-agent pathfinding.
Disjoint Pathfinding in Non-Planar Environments
Author
Petr Michalíček
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
RNDr. Luděk Kleprlík, Ph.D.
Department
Summary
Cooperative disjoint pathfinding is a variant of the multi agent pathfinfing problem. For a given space and a set of pairs of start and goal positions in space the objective is to find vertex-disjoint paths, which connecting the start and goal position from each given pair. In cooperative pathfinding, agents try to cooperate with each other. Every agent knows the positions of others. They all have a common objective, which is successfully complete paths for all agents. In this work new algorithms for disjoint pathfinding are presented.
Popular algorithms CA*, HCA* and WHCA* were modified to solving cooperative disjoint pathfinding problem with a voxel grid. They were also implemented in version, which works with octree. Using octree brings significant speed improvement in some spaces. The created algorithm Obstacle A* can find paths more successfull than other methods in regions with botllenecks. New methods MDCA* and MDWHCA* can be used for creating paths,
which has bigger spaces among themselves.
Pathfinding and Target Assignment in a Generalization of the Pacman Game
Author
Petr Šindlář
Year
2022
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Mgr. Ladislava Smítková Janků, Ph.D.
Department
Summary
This bachelor thesis deals with the topic of multi-agent path finding and two extending problems -- target assignment and goal ordering. Research part of this work gives insight into these problems and ways of solving them. Studied concepts are applied to generalized version of Pacman game in which there can be more Pacmans and ghosts. This thesis contains the design and implementation of an algorithm that solves instances of this generalization using modifications of existing algorithms BFS, DFS, A* and CBS.
Compilation of Multi-Agent Collective Construction in the Minecraft Game
Author
Martin Rameš
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Dr. techn. Ing. Jan Legerský
Department
Summary
This bachelor thesis studies current exact approaches to multi-agent collective construction problem, with emphasis on three-dimensional structures, built by agents repositioning passive blocks on a grid under the condition of gravity. A generalization of current fastest exact model is proposed, using mixed integer linear programming, to accommodate varying durations of agent actions. An application of the proposed model is used in conjunction with a solver to exactly optimize construction plan of user entered structures. The result is visualized in Minecraft, using program built upon project Malmo API. A series of experiments is performed on several small instances to measure relative construction makespan reduction, relative to the instances with one-timestep actions. Results show significant makespan reduction at action durations used for visualization in Minecraft.
Robot Localization During Execution of Multi-Agent Path Finding Plans with OZOBOTs
Author
Silvestr Láník
Year
2021
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. RNDr. Alena Šolcová, Ph.D.
Department
Summary
In my work, I focus on creating a localization system of Ozobots while they performing a multi-agent pathfinding simulation. The main reason for this work is the occasional errors during the execution of the simulation, caused by poor detection of the projected path by the Ozobot. I use a webcam and known insights from computer vision to track and locate Ozobots. The developed localization system can detect the simulation area in the image and further detect and track Ozobots moving in the area and return their positions in the simulation. According to the measurements made, the localization system has a success rate of 97 % and in the future it is planned to use it in a more complex surveillance mechanism, which will lead to a more accurate execution of the simulation.
Interactive Environment for Visualization and Testing of Formation Maintenance in Multi-Agent Path Finding
Author
Jakub Votrubec
Year
2023
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Jan Matoušek
Department
Summary
In the theoretical background, we introduce the reader to the problem of maintaining formations in a~multi-agent environment and explain the algorithm used in the practical part. In the practical part, we then design and implement an interactive application for visualizing and testing formation maintenance in a~multi-agent environment.
We solved the chosen problem by building an interactive application in the Godot game engine and creating a structure for implementations of the algorithms in C++. For testing, we use the formation maintenance algorithm discussed in the theoretical background.
The main result is an application that provides a user-friendly way of using the algorithm to solve user-specified problems, as well as allowing us to modify the problems and try to find their optimal solution.
The complete source code and the already compiled application ready to run can be found on the attached media.
Multi-agent Path Finding with Production and Consumation of Agents
Author
Tomáš Holas
Year
2022
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
RNDr. Luděk Kleprlík, Ph.D.
Department
Summary
The scope of this bachelor thesis is to create a multi-agent control solver that accounts for production and consumption of agents. The solver builds a plan for continuous time and this plan is then demonstrated using ozobots.
Multi-agent pathfinding is problematic due to possible robot collisions. The collisions need to be resolved for the smooth passage of robots through the warehouse, which will make the entire warehouse logistics more efficient.
Path Planning for Robots in Reconfigurable Warehouse
Author
Vladislav Beneš
Year
2023
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
RNDr. Luděk Kleprlík, Ph.D.
Department
Summary
This work is focused on Multi-agent path finding (MAPF) algorithms for robots in warehouses in which places, where the items will be stored, is decided by warehouse anarchy. Warehouse anarchy doesn't have specified places in the warehouse for storing items, but those places are selected in the progress and thez can be specified for storing items or purely for robot movement. The main focus will be on algorithm SMTCBS and ideas for effective warehouse anarchy.
Navigation of a Swarm of UAVs in an Environment with Obstacles
Author
Erich Beneš
Year
2023
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Miroslav Čepek, Ph.D.
Department
Summary
The focus of this thesis is mainly on the creation of a system for the transformation of existing
flight plans found using multi-agent pathfinding algorithms to flight sequences for drones. The
definition of multi-agent pathfinding and algorithms CBS and SMT-CBSR are introduced in the
first chapter. The second chapter explains how Crazyflie 2.1 drone control environment works,
with emphasis on Loco Positioning system. Then package crazyflie_controller is presented. It
offers a simple way of communicating with drones Crazyflie 2.1, along with a way of transforming
flight plans into flight sequences, evaluation and visualization of the results. The package is then
tested in an environment containing obstacles.
Plan Execution in Automated Warehouse
Author
Filip Leško
Year
2023
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Mgr. Ladislava Smítková Janků, Ph.D.
Department
Summary
In this paper, a scaled down model of an automated warehouse is proposed and the execution of the plans is subsequently tested. The plans are executed by a group of robots called Ozobot Evo. In solving, this work builds on the knowledge of plan execution for multi-agent pathfinding and algorithms solving the warehouse problem, which the work modifies and extends. The model supports both manual job addition and job generation to better simulate real warehouses. Tests were conducted on both the modified algorithm that solves the warehouse instances and the warehouse model with robots. During the testing of the algorithm, it was determined how the different attributes of the warehouse affect the efficiency of the algorithm's solution. Experiments with robots compare the success of execution and then discusses what influences the failure of plan execution.
Drone Display Based on Crazyflies
Author
Matouš Kulhan
Year
2022
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Dr. techn. Ing. Jan Legerský
Department
Summary
This bachelor thesis deals with producing drone display effect using a swarm of mini quadcopters Crazyflie 2.1. Drone display is a visual effect, where a swarm of flying drones capable of emitting light create an image in 3D space. The goal of this thesis is to create a process that transforms drone display task to commands send to each drone.
This is done by splitting the problem into two phases, planning and acting. Planning phase transforms drone display task into a time plan for each drone in the swarm using multi-agent pathfinding (MAPF), specifically CCBS algorithm. Acting phase aims to fulfill this plan as precisely as possible using Python library cflib, which controls Crazyflie drones remotely.
Two programs, each solving one of the phases, are created as a result of this thesis. This solution was tested on real drones in the Robotic Agents Laboratory of Faculty of Information Technology, CTU using LED-ring expansion deck and Loco positioning system.
Visual Object Detection and Tracking by the Crazyflie Quadcopter
Author
Artem Redchych
Year
2023
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Miroslav Skrbek, Ph.D.
Department
Summary
In this thesis's literature review section, contemporary and older methods for visual object detection, tracking, and distance estimation were investigated. The main components of the Crazyflie ecosystem were also described. In the implementation part, selected methods were implemented. For object detection, the MobileNetV2-SSD model with FPNlite was used, the Kalman Filter was employed for object tracking, and the monocular distance estimation technique was utilized for distance estimation. Object detection achieved an average accuracy of 87 % and a tracking accuracy of 74 %. This work's main result is exploring the potential use of object detection and tracking methods using the Crazyflie 2.1 drone and its Loco Positioning and AI-deck modules. In the appendices of the work, one can find key components and the final implementation of the flying streamer.
Multi-Goal Multi-Agent Path Finding Using Boolean Satisfiability
Author
Štěpán Tupý
Year
2023
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Mgr. Jan Starý, Ph.D.
Department
Summary
This thesis deals with the search for the optimal solution to the multi-goal multi-agent pathfinding problem (MG-MAPF), which is a generalization of multi-agent pathfinding (MAPF). The task in the MG-MAPF problem is to find a non-conflicting path for each agent starting in its initial position and covering its assigned set of goal vertices. Therefore, the problem of selecting the order in which agents visit their goals so that the set of found paths is overall optimal is introduced. Current algorithms search for optimal MG-MAPF solutions using state space search or reduction of the problem to propositional satisfiability. In this thesis, I implemented an existing algorithm SMT-Hamiltonian-CBS (SMT-HCBS), which combines both approaches. However, the reduction of MG-MAPF produces a long Boolean formula and the difficult search for its valid evaluation decreases the efficiency of this algorithm. I have therefore introduced two new variants of encoding MG-MAPF into the Boolean formula that use fewer clauses and thus decrease the formula's length. The reduced encoding successfully increased the efficiency of SMT-HCBS, which was demonstrated when tested on grid-shaped graphs of different sizes. SMT-HCBS performed better than its original variant on all tested graphs when using the reduced encoding.
Object Arrangement for 3D Printing as a Constraint Satisfaction Problem
Author
Lukáš Pokorný
Year
2024
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Jan Schmidt, Ph.D.
Department
Summary
This thesis is going to deal with the layout of 3D objects, which are reduced to 2D objects from the top view, on the print surface of a 3D printer, using the Constraints Satisfaction Problem (CSP). This means presenting a possible solution for processing the STL file into a 2D object, which will further be used for OR-Tools and Gecode solvers, for which the formulation and subsequent implementation will be presented. The results from both solvers are then compared, and then the use of the solvers themselves is also compared.
Multi-agent Path Finding as a Constraint Satisfaction Problem
Author
Miroslav Fáč
Year
2024
Type
Bachelor thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Jan Schmidt, Ph.D.
Department
Summary
In this work we explore the application of Constraint Satisfaction Problem (CSP) formalisms to Multi-Agent Path Finding (MAPF), a computational challenge traditionally addressed through boolean satisfiability problem (SAT). MAPF is important in robotics and logistics, where the coordination of multiple agents is essential for navigating from start to destination points without conflicts. Although SAT-based solutions are common, CSP formalisms present a promising alternative.
We provide a theoretical foundation by discussing graph theory, the general principles of MAPF, and the CSP formalisms. This includes a detailed examination of algorithms typically employed in CSP, various heuristic techniques, and other relevant methodologies. We then introduce how to approach MAPF using Constraint Programming (CP), focusing on MiniZinc, a language designed to standardize CP practices. In our work, we utilize two leading CP solvers, Gecode and OR-Tools.
In the experimental section, we do analysis between Gecode and OR-Tools, conducted across various test scenarios. The results indicate that while Gecode generally performs better in pure CSP contexts, OR-Tools excels in Constraint Optimization Problems (COP), providing valuable insights into the strengths and limitations of each solver.
Master theses
Centralized Planning of Autonomous Traffic
Author
Ondřej Pleticha
Year
2020
Type
Master thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Karel Klouda, Ph.D.
Department
Summary
This thesis deals with the problem of managing autonomous traffic in cities. We consider future transport system where all vehicles are shared and can transport people or objects on their own without a driver. Customers only create transport requests. The aim of the work is to design and test algorithms for the system that could be used to solve the problem of finding suitable routes for vehicles. Key objectives are the overall energy performance of the system and customer satisfaction. To verify the results of the algorithms, a simulation is implemented which, in a simplified model, mimics traffic and city requirements. First, an environment is defined that describes how that transportation system might work. Three different existing algorithms are considered for traffic management, which differ in the distribution of requirements and the planning of vehicle routes. All three algorithms are modified and improved to allow for different priority requests. The testing is focused on the ability of algorithms to meet requirements at different vehicle to task ratios. Furthermore, it is also examined how long customers waited under certain conditions or what the computing power requirements are for individual algorithms.
Parameter Setting in SAT Solver Using Machine Learning Techniques
Author
Filip Beskyd
Year
2020
Type
Master thesis
Supervisor
doc. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Tomáš Kalvoda, Ph.D.
Department
Summary
SAT solvers are essential tools for many domains in computer science and engineering. SAT solvers took a place of a universal tool which their users use when in need for solution of their problems, which would otherwise require ad-hoc solution, which would probably be nowhere near the effectiveness of modern SAT solvers.
Over the course of at least two decades of SAT related research, many heuristics were produced, most effective ones are embedded in SAT solvers of present day, which further increase their effectiveness compared to their predecessors. Heuristics can usually be tuned by single or multiple numerical parameters prior to executing the search process over the concrete SAT instance.
In this thesis I present machine learning approach which predicts the parameter values for heuristic from underlying SAT instance structure in view of reducing computational time.
Automated Planning for Warehouse Logistics
Author
Klára Dvořáková
Year
2021
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Jan Janoušek, Ph.D.
Department
Summary
This thesis describes automated warehouse logistics. The paper focuses on the coordination of the robot in a warehouse so there are no collisions and the robots fulfil their tasks effectively. A typical task is to move an item from its storage location to its delivery location. The main goal of the thesis is to analyze and develop a modification of existing algorithms with a focus on tasks with different priorities. The theoretical part of this paper deals with a multi-agent pathfinding problem and a description of existing algorithms that solve this problem. The practical part of the paper follows up with the analysis and implementation of Windowed CBS improvements so the algorithm would process tasks with different priorities effectively. Finally, experiments are run on several maps with a various number of agents, and the results are evaluated and analyzed. The outcome of the thesis is a software prototype of Windowed Priority CBS that accepts tasks with different priorities and takes said priorities into account when searching for the solution.
Generalization of the Pac-man Game from the Perspective of Turn-based Game Algorithms
Author
Kristián Kuľka
Year
2022
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Mgr. Petr Klán, CSc.
Department
Summary
The Pac-Man game represents an interesting problem in the field of artificial intelligence since it belongs to the category of the multi-agent systems which require good dose of cooridnation and long-term planning. This game is also complicated by the fact that immediate actions do not significantly change the state of the game many times, which makes it harder to decide an optimal move.
In this thesis, I will define the general version of the Pac-Man from the perspective of turn-based games with multiple agents (pacmans and ghosts). I will introduce the main problems and summarize some approaches from the literature. Next, I will introduce implemented methods, which were based on the negamax algorithm, AlphaZero and original implementation of the game from the year 1980. I will also mention their possible improvements, which can adress the occurred problems. I have also implemented the visualization module and general framework which is capable of evaluating strategies, optimizing their parameters and training, which will be discussed in its own chapter. I will finish the thesis by analysing results, which were obtained by evaluating strategies on various maps.
DPLL(MAPF): Integration of a SAT Solver and Multi-Agent Path Finding
Author
Martin Čapek
Year
2022
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Mgr. Jan Starý, Ph.D.
Department
Summary
Multi-agent path finding (MAPF) is often compiled to Boolean satisfiability (SAT) and solved by existing SAT solvers.
We present in this paper a novel compilation scheme called DPLL(MAPF), which brings closer integration of SAT solver and MAPF theory. We show that DPLL(MAPF) is the next logical step in improving lazy encoding MAPF solvers. Such solver that we focus on is SMT-CBS.
We propose a new strategy of adding constrains more eagerly - Eager chokepoints.
We implemented DPLL(MAPF) and evaluated it. The results show that DPLL(MAPF) can outperform SMT-CBS and our strategy Eager chokepoints is not a favorable improvement.
Learning of Locally Controlled Agents in the Pac-Man Game
Author
Petr Nešpůrek
Year
2022
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
doc. Ing. Ivan Šimeček, Ph.D.
Department
Summary
This thesis is about creating an agent, that can learn to play the Pac-man game. Two types of approach are used. The first approach is a combination of genetic programming and reinforcement learning. The second approach uses artificial neural networks that use training data obtained from simulations of other agents of manual gameplay.
This thesis includes creation of a Pac-man game model with simplified rules. It also includes implementation of an application, which enables gameplay and serves as an interface between the agents and the game model, and contains auxiliary functions for agent learning.
Lazy Compilation in Classical Planning
Author
Zuzana Fílová
Year
2022
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Daniel Vašata, Ph.D.
Department
Summary
The subject of this diploma thesis is focused on a lazy compilation in classical planning. The theoretical part summarizes the basics of classical planning. Key concepts of the classical representation of planning problems are defined and basic planning algorithms are presented, in particular, the search in the planning state space and techniques using the planning graph. The compilation of the planning problem into the propositional satisfiability problem (SAT) is discussed at the end of this section.
Based on the obtained knowledge, a new method for lazy compilation of planning problems into SAT has been proposed. Different from the classical compilation, in this method the propositional formula is gradually created and modified. As part of the practical part of the work, a planner was implemented using two compilation variants - the proposed method for lazy compilation and classical compilation.
The planner was tested on planning problems from the International Planning Competition (IPC). The experiments focused on evaluating the success of the planner based on lazy compilation and comparing the results with the planner using the classical compilation method. A total of 79 problems of varying difficulty from four domains were used, of which the lazy planner was able to solve 63 faster than the classical planner. The performed experiments pointed out the advantages and possible disadvantages of lazy compilation. The results of the experiments indicate that the use of lazy compilation has the potential to improve the performance of the planner.
Drone Aerial Display
Author
Ondřej Marek
Year
2022
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Miroslav Skrbek, Ph.D.
Department
Summary
This thesis deals with the creation of an algorithm for so called drone display where individual pixels are created by luminous drones. The drones can change their color as well as position in space. The goal of this thesis is a planning of the drones movement taking into account user defined criteria and required visual effect.
A well known algorithm called CBS (Conflict Based Search) that solves a problem of multi-agent path finding was adjusted for this cause. The conflict search part of the algorithm utilizes the fact that the display is split into cubes. Thus the algorithm can check if various drones occupy the same cube area at the same time. An adapted A* algorithm is used for the path finding part of the CBS. Generalized 2^k neighborhood in space describes a connectivity of neighboring pixels. The drones move between pixels utilizing either straight paths or trajectories defined by spacial interpolating curves. The algorithm also takes into account drones maximum speed, their acceleration and their momentum.
A new algorithm called CSPT_CBS (Continuous Spacetime Conflict Based Search) and a simulating program are conceived as the results of this thesis. In the simulating program one can choose placement and colors of individual pixels and then see a visualisation of the drones movement.
Multi-Agent Path Finding with Continuous Time Based on Integer Linear Programming
Author
Yana Zabrodskaya
Year
2022
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Daniel Vašata, Ph.D.
Department
Summary
The thesis describes the problem of finding the shortest path for several robots so that these robots do not collide. In order to find a solution to this problem and basing on integer linear programming with a lazy compilation elements, an algorithm has been developed. The experimental evaluation of the algorithm is followed.
Constraint Programming in Scheduling for Garage
Author
Petr Švec
Year
2023
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Daniel Vašata, Ph.D.
Department
Summary
This thesis deals with the implementation of a system for scheduling workshop work in a car repair shop. The thesis analyses the customer requirements, based on which it defines a model. Model is using constraint programming. Based on the proposed model, we implemented the solver using the choco library. We validated the solver on synthetic and practice motivated data. Various properties of the generated solution for the test instances were measured.
The focus was on universal use with maximum parameterization for the needs of individual clients and integrations.
Simulation and Visualization of Motion Plans for a Desktop Robotic Arm with the ROS and Unity Platforms
Author
Ján Chudý
Year
2023
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Mgr. Ladislava Smítková Janků, Ph.D.
Department
Summary
The Robot Operating System (ROS) is the most widely used framework for developing robotic applications. Also, several simulation tools exist that are used with ROS. Robot simulation is an essential part of robotics, making the development of hardware and robotic applications quicker, cheaper, and safer. Such simulation can also be used for academic demonstrations and research before fully developing the physical robot. Recently, powerful 3D development platforms like Unity have started to appeal to researchers in robotics. This work develops a ROS backend for a faculty-developed robotic manipulator Real Robot One (RR1), which allows the simulation of its digital twin prototype in Unity and Gazebo, a commonly used simulator in the ROS ecosystem. As one of the primary motivations behind the RR1 robotic arm is the research of multi-robot motion planning, the two simulation tools are compared with an emphasis on multi-robot simulation and user experience.
Hierarchical Planning for Real-Time Strategic Games
Author
Lukáš Kameník
Year
2023
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
Ing. Daniel Vašata, Ph.D.
Department
Summary
This thesis addresses hierarchical planning for real-time strategy games. The aim of the thesis is to test the suitability of applying HTN planning to a computer-controlled RTS game player by applying HTN planning to the game Dune 2000.
In this thesis, two slightly different approaches, named Resourced Based AI (RBAI) and Income Based AI (IBAI), have been proposed and implemented, modifying the original AI only to the extent needed. The former approach models the game for planning more accurately. The second mentioned tests a simpler approach. From experimental measurements, both approaches were found to work well and beat the default AI in most cases, but in the end, HTN planning proved unnecessarily robust and laborious for the chosen approach of creating AI.
Multi-agent Path Finding in Continuous Environment
Author
Kristýna Janovská
Year
2024
Type
Master thesis
Supervisor
prof. RNDr. Pavel Surynek, Ph.D.
Reviewers
RNDr. Jiří Vyskočil, Ph.D.
Department
Summary
This work sets to develop a model of collision-free multi-agent path finding in continuous environment, where agents move on sets of smooth curves. Agents communicate between themselves using the Continuous Environment Conflict-Based Search (CE-CBS) algorithm proposed in this work.
Various parameters of this model and different types of environment and agent setting are studied to determine how agents behave based on the difficulty of the environment setting and how the solution quality changes. The results of these experiments show the ability of agents to move on non-colliding smooth paths while also optimising the path costs.