National Repository of Grey Literature 59 records found  1 - 10nextend  jump to record: Search took 0.01 seconds. 
Solving Algorithms for Multi-agent Path Planning with Dynamic Obstacles
Majerech, Ondřej ; Surynek, Pavel (advisor) ; Vlk, Marek (referee)
In this work we present the problem of multi-agent path-finding with dynamic obstacles, a generalisation of multi-agent path-finding (MAPF) in which the environment contains randomly-moving dynamic obstacles. This generalisation can be though of as an abstraction of incomplete knowledge of the environment or as a simplification of the multi-agent path-finding where we do not include all agents in the cooperative planner. We adapt three planning algorithms for MAPF to work in an environment with dy- namic obstacles: Local-Repair A* (LRA*), Windowed Hierarchical Cooper- ative A* (WHCA*) and Operator Decomposition with Independence Detec- tion (OD/ID). In addition, we propose two heuristics for these algorithms in dynamic environments: Path Rejoining and Obstacle Predictor. In our experiments, we find that LRA* and WHCA* are best suited for the dy- namic environment. The Path Rejoining heuristic is successful in improving run-times at a small cost in makespan. Obstacle Prediction is capable of lowering the number of times a plan has to be found, but the overhead of our implementation outweighs any performance benefits in most cases. 1
Constraint Programming in Planning
Surynek, Pavel ; Barták, Roman (advisor) ; Vojtáš, Peter (referee) ; Štěpánková, Olga (referee)
This thesis deals with planning problems and Boolean satisfiability problems that represent major challenges for artificial intelligence. Planning problems are stated as finding a sequence of actions that reaches certain goal. One of the most successful techniques for solving planning problems is a concept of plan- ning graphs and the related GraphPlan algorithm. In the thesis we identified a weak point of the original GraphPlan algorithm which is the search for actions that support certain goal. We proposed to model this problem as a constraint satisfaction problem and we solve it by maintaining arc-consistency. Several propagation variants for maintaining arc-consis- tency in the model are proposed. The model and its solving process were integrated into the general GraphPlan-based planning algorithm. The performed experimental evaluation showed improvements in order of magnitude in several measured characteristics (overall solving time, number of backtracks) compared to the standard version of the GraphPlan algorithm. Next we proposed a stronger consistency technique for pruning the search space during solving the problem of finding supports. It is called projection consistency and it is based on disentangling the structure of the problem formulation. If the problem of finding sup- porting actions is...
Balancing rules of prototype board game Souboj živlů
Holubyev, Dmytro ; Gemrot, Jakub (advisor) ; Surynek, Pavel (referee)
The main goal of this thesis is to analyze the mechanisms of the prototype board game Clash of the elements. Using knowledge from the field of game theory and simulations using the shortcomings of the rules, which are unbalanced between players. The simulator has to offer players and developers a comprehensive and flexible tool that thanks to sophisticated artificial gamers can efficiently test the changes without the risk of disturbing the gaming policies and strategies.
Multi-agent Path Planning in Unidirectional Environments
Švancara, Jiří ; Surynek, Pavel (advisor) ; Barták, Roman (referee)
In this paper we focus on the optimal multi-agent path planning, which is an NP-complete problem. To solve this task, we will use centralized A* search algorithm for which we propose a new heuristic. To construct our proposed heuristic, we examine the solution of multi-agent path planning via its reduction to multi-commodity flow, which is also an NP-complete problem. Our heuristic is based on relaxation of multi-commodity flow to single-commodity flow that can be solved in polynomial time. We show that this new heuristics is admissible and consistent. We also show types of problems for which our heuristic is more successful than other heuristics. Powered by TCPDF (www.tcpdf.org)
Vybrané problémy související s vehicle routing
Kuklis, Imrich ; Pergel, Martin (advisor) ; Surynek, Pavel (referee)
In our thesis we concentrate on a well-known problem which is popular among the scientists from the field of logistics, theoretical computer science and applied mathematics. This problem is called the Vehicle Routing Problem. We concentrate mainly on the Vehicle Routing Problem with Time Window. We implement some scheduling algorithms and compare their results. Powered by TCPDF (www.tcpdf.org)
Konstrukce modelů v polynomiální reprezentaci
Blicha, Martin ; Stanovský, David (advisor) ; Surynek, Pavel (referee)
Finite model finding is a problem defined as follows: given a theory in first-order logic, find a finite model of this theory. We present a new ap- proach to finite model finding based on a translation of axioms to a system of multivariate polynomial equation. Existence of a model of given size is then equivalent to an existence of a solution of the system. We prove the correctness of this approach, implement it and compare its performance with current state-of-the-art model finders. 1
Computational Intelligence for Malware Classification
Tomášek, Jan ; Pilát, Martin (advisor) ; Surynek, Pavel (referee)
As the number of computers and other smart devices grows in every aspect of human life, the amount of malicious software (malware) also grows. Such software tries to disrupt computer usage. Therefore one of the challenges for computer science is to divide the Malware into classes according to its behaviour. The thesis summarizes known ways to look at the problem at hand, some of them are extensions of known approaches, while others are completely new. They are all implemented, tested and compared. We also propose few ideas for future research. Powered by TCPDF (www.tcpdf.org)
Automated model building
Miček, Radek ; Stanovský, David (advisor) ; Surynek, Pavel (referee)
We implement a MACE-style method for finding finite models in unsorted classical first-order logic. Additionally to well-known modifications of the method we also describe and implement several new modifications such as: unflattening, generation of redundant clauses and encoding into Gecode constraints. Our implementation is benchmarked together with Mace4, Paradox and iProver. Finally, some suggestions for improvements and further research are given. Powered by TCPDF (www.tcpdf.org)
Automated Generation of Realistic Terrain Using Machine Learning Techniques
Střelský, Jakub ; Surynek, Pavel (advisor) ; Holan, Tomáš (referee)
Title: Automated Generation of Realistic Terrain Using Machine Learning Tech- niques Author: Jakub Střelský Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Pavel Surynek, Ph.D., Department of Theoretical Computer Science and Mathematical Logic Abstract: Artificial terrain is important component of computer games, simulati- ons and films. Manual terrain creation can be arduous process, hence automa- tization of this process would be convenient in many cases. Thanks to current advances in employing artifical neural networks on various generative tasks, the possibility of generating terrain using artificial neural networks should be investi- gated. We will focus on Generative Adversarial Networks as it is one of the most successful content generation method, and we will adjust this method to the task of artificial terrain generation. Resulting model is capable of generating realistic terrain based on raster sketch given by user and allows interactive modelling. Disadvantage of the model is it's requirement of a lot of training data. However, thanks to global elevation datasets providing us with more than enough training data, the model could be useful in certain applications. Keywords: procedural generation, terrain, neural networks, deep learning 1
Modeling of Cooperative Path Finding
Ježek, Milan ; Surynek, Pavel (advisor) ; Majerech, Vladan (referee)
In this thesis we describe new models for solving the cooperative pathfinding (cpf) with the requirement of minimal makespan and experimental comparison with current models is performed. These new models investigate the possibilities of encoding the cpf problem into binary integer programming (bip) or constraint satisfaction problem (csp). Mainly the new active-edges IP model tests with high number of agents yielded good results, where it fell only slightly behind the best SAT model. A new csp model reached the fastest times in tests with low number of obstacles and agent interactions while struggling heavily in the opposite cases. Powered by TCPDF (www.tcpdf.org)

National Repository of Grey Literature : 59 records found   1 - 10nextend  jump to record:
Interested in being notified about new results for this query?
Subscribe to the RSS feed.