|
|
Acceleration of Particle Swarm Optimization Using GPUs
Krézek, Vladimír ; Schwarz, Josef (referee) ; Jaroš, Jiří (advisor)
This work deals with the PSO technique (Particle Swarm Optimization), which is capable to solve complex problems. This technique can be used for solving complex combinatorial problems (the traveling salesman problem, the tasks of knapsack), design of integrated circuits and antennas, in fields such as biomedicine, robotics, artificial intelligence or finance. Although the PSO algorithm is very efficient, the time required to seek out appropriate solutions for real problems often makes the task intractable. The goal of this work is to accelerate the execution time of this algorithm by the usage of Graphics processors (GPU), which offers higher computing potential while preserving the favorable price and size. The boolean satisfiability problem (SAT) was chosen to verify and benchmark the implementation. As the SAT problem belongs to the class of the NP-complete problems, any reduction of the solution time may broaden the class of tractable problems and bring us new interesting knowledge.
|
|
|
Application of SAT Solvers in Circuit Optimization Problem
Minařík, Vojtěch ; Mrázek, Vojtěch (referee) ; Vašíček, Zdeněk (advisor)
This thesis is focused on the task of application of SAT problem and it's modifications in area of evolution logic circuit development. This task is supposed to increase speed of evaluating candidate circuits by fitness function in cases where simulation usage fails. Usage of SAT and #SAT problems make evolution of complex circuits with high input number significantly faster. Implemented solution is based on #SAT problem. Two applications were implemented. They differ by the approach to checking outputs of circuit for wrong values. Time complexity of implemented algorithm depends on logical complexity of circuit, because it uses logical formulas and it's satisfiability to evaluate logic circuits.
|
|
|
Extensions to the class of matched formulae
Chromý, Miloš ; Kučera, Petr (advisor) ; Babka, Martin (referee)
We can associate an incidence graph with any CNF formula. It's a bipartite graph, in which he first part corresponds to variables and the second one to clauses. We can define matched formulas and biclique satisfiable formulas, based on this incidence graph. Both of these classes share an interesting property: Given a formula F which is matched or biclique satisfiable, F remains satisfiable even after we switch polarity of any occurrence of any literal. Class of formulas with this property is called var-satisfiable. In this thesis, we consider a parameterized algorithm introduced by Stefan Szeider for deciding satisfiability of formulas with small deficiency. Here deficiency of a formula is defined as a difference between the number of clauses and the number of variables in the formula. We explain why this algorithm cannot be simply generalized for the case of biclique satisfiable formulas. Since the problem of determining whether a formula is biclique satisfiable is NP-complete, we introduce a heuristic, which tries to find some biclique cover in time O(n2 e), where n denotes the number of variables and e denotes the length of the input formula. We performed experiments testing this heuristic on random formulas. The results of these experiments suggest, that there is a phase transition in the behaviour of the heuristic....
|
|
|
Modelling and Solving Problems Using SAT Techniques
Balyo, Tomáš ; Barták, Roman (advisor) ; Železný, Filip (referee) ; Biere, Armin (referee)
Solving planning problems via translation to satisfiability (SAT) is one of the most successful approaches to automated planning. In this thesis we describe several ways of encoding a planning problem represented in the SAS+ formalism into SAT. We review and adapt existing encoding schemes as well as introduce new original encodings. We compare the encodings by calculating upper bounds on the size of the formulas they produce as well as by running extensive experiments on benchmark problems from the 2011 International Planning Competition (IPC). In the experimental section we also compare our encodings with the state-of-the-art encodings of the planner Madagascar. The experiments show, that our techniques can outperform these state-of-the-art encodings. In the presented thesis we also deal with a special case of post-planning optimization -- elimination of redundant actions. The elimination of all redundant actions is NP-complete. We review the existing polynomial heuristic approaches and propose our own heuristic approach which can eliminate a higher number and more costly redundant actions than the existing techniques. We also propose a SAT encoding for the problem of plan redundancy which together with MaxSAT solvers allows us to solve the problem of action elimination optimally. Experiments done with...
|
|
|
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.
|
|
|
Solving Boolean satisfiability problems
Balyo, Tomáš
In this thesis we study the possibilities of decomposing Boolean formulae into connected components. or this reason, we introduce a new concept - component trees. We describe some of their properties and suggest some applications. We designed a class of decision heuristics for SAT solvers based on component trees and experimentally examined their performance on benchmark problems. For this purpose we implemented our own solver, which uses the state-of-the-art SAT solving algorithms and techniques.
|
|
|
Classes of Boolean Formulae with effectively soluable SAT.
Vlček, Václav
This work studies classes of Boolean formulae with polynomially solvable satsiability problem (SAT). It investigates the behavior of these classes with respect to basic operation with formulae (variable and literal complementation, deletition of a literal or a clause, partial assignment and joining formulae). Furthermore the work studies recognition problems for a formula and a given class of functions, satisability testing, and mutual relations of the studied classes with respect to inclusion.
|
|
|
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.
|
|
|
Application of SAT Solvers in Circuit Optimization Problem
Minařík, Vojtěch ; Mrázek, Vojtěch (referee) ; Vašíček, Zdeněk (advisor)
This thesis is focused on the task of application of SAT problem and it's modifications in area of evolution logic circuit development. This task is supposed to increase speed of evaluating candidate circuits by fitness function in cases where simulation usage fails. Usage of SAT and #SAT problems make evolution of complex circuits with high input number significantly faster. Implemented solution is based on #SAT problem. Two applications were implemented. They differ by the approach to checking outputs of circuit for wrong values. Time complexity of implemented algorithm depends on logical complexity of circuit, because it uses logical formulas and it's satisfiability to evaluate logic circuits.
|
|
|
Extensions to the class of matched formulae
Chromý, Miloš ; Kučera, Petr (advisor) ; Babka, Martin (referee)
We can associate an incidence graph with any CNF formula. It's a bipartite graph, in which he first part corresponds to variables and the second one to clauses. We can define matched formulas and biclique satisfiable formulas, based on this incidence graph. Both of these classes share an interesting property: Given a formula F which is matched or biclique satisfiable, F remains satisfiable even after we switch polarity of any occurrence of any literal. Class of formulas with this property is called var-satisfiable. In this thesis, we consider a parameterized algorithm introduced by Stefan Szeider for deciding satisfiability of formulas with small deficiency. Here deficiency of a formula is defined as a difference between the number of clauses and the number of variables in the formula. We explain why this algorithm cannot be simply generalized for the case of biclique satisfiable formulas. Since the problem of determining whether a formula is biclique satisfiable is NP-complete, we introduce a heuristic, which tries to find some biclique cover in time O(n2 e), where n denotes the number of variables and e denotes the length of the input formula. We performed experiments testing this heuristic on random formulas. The results of these experiments suggest, that there is a phase transition in the behaviour of the heuristic....
|
guest ::
