Note: This list is currently being revised and does not claim to be complete.
Bachelor's thesis
Extension of a Planning System for the
Solution of Single Person Games
Author: Silvan Sievers (October 2009)
Download: (PDF)A General Game Playing System is one that can accept a formal definition of a game and play the game effectively without human intervention. Unlike specialized game players, general game players do not rely on algorithms designed in advance for specific games, and they are able to play different kinds of games.
Besides two-player and multi-player games, the games that have to played successfully at the AAAI General Game Playing Competition also include single-player games. Due to algorithmic reasons, it is preferable to develop different modules handling the different kinds of games. Since single-player games described in the Game Description Language (GDL), in which the competition games are encoded, are essentially classical planning problems, it is possible to solve them using according algorithms.
The goal of this thesis was to integrate state-of-the-art algorithms and heuristics used in classical planning into a General Game Playing system currently under development. The resulting system should be evaluated using some of the benchmark games available online.
Bachelor's thesis
An analysis of SGPlan
Author: Diana Hille (September 2009)
Download: (PDF)The purpose of this work is to give a detailed analysis of SGPlan. SGPlan achieved good results in the last international planning competitions (in particular at the 4th and 5th IPC). The source code of the planner wasn't accessible until now, but was made available for free use within the 6th IPC. Using this code, the achievement of the results and the algorithmic background of SGPlan shall be examined, because up until now the code was not sufficiently explained through the publicly available descriptions.
Bachelor's thesis
Fluent Merging for classical planning
problems
Author: Jendrik Seipp (September 2009)
Download: (PDF)Fluent merging is a reformulation technique for classical planning problems that can be applied automatically or semi-automatically. The reformulation strives to transform a planning task into a representation that allows a planning algorithm to find solutions more efficiently or to find solutions of better quality. This work introduces different approaches for fluent merging and evaluates them within state-of-the-art planning systems.
Bachelor's thesis
Influence of the Finite Domain Representation
on the performance of planning systems
Author: Jonas Sternisko (September 2009)
Download: (PDF)In contrast to the common propositional representation of planning tasks, where each state variable can only take the values true and false, the Finite Domain Representation allows arbitrary finite domains. This permits a much more natural formalization of the planning tasks. In addition, it explicitly states certain mutexes, which can be exploited by planning systems to solve the task more efficiently. The objective of this thesis is to examine the influence of the representation on the performance of several planning systems empirically.
Bachelor's thesis
Automatic Pattern Selection for Pattern Database Heuristics in Non-deterministic Planning
Author: Manuela Ortlieb (September 2009)
Download: (PDF)This work is concerned with a subproblem of the problem of finding strong plans for non-deterministic planning problems via the approach of planning as heuristic search, more precisely, AO* search guided by domain-independent pattern database (PDB) heuristics. Strong plans guarantee that a goal state is reached in a finite number of steps independently of the non-deterministic outcomes. The focus of this work is on the automatic selection of approproate patterns through heuristic search in the space of pattern collections, alalogous to the work by Haslum et al. in the context of deterministic planning. The aim of this work is the implementation and evaluation of a pattern selection algorithm.
Bachelor's thesis
Solving General Games by Heuristic Search
Author: Johannes Aldinger (April 2009)
Download: (PDF)A General Game Playing System is a system that can accept a formal definition of a game and play the game effectively without human intervention. Unlike specialized game players, general game players do not rely on algorithms designed in advance for specific games, and they are able to play different kinds of games.
In this work, a player based on the General Game Playing System Jocular was developed that uses an automatically generated evaluation function derived from the FF heuristic known from research in action planning. The evaluation function generalizes the FF heuristic in that it is designed for two-player games with numeric preferences over terminal states.
Bachelor's thesis
Compact encodings of monotonic Boolean
functions
Author: David Goergen (May 2008)
A Boolean function is monotonic if it can be represented by a combinatorial circuit of AND- and OR-gates. Monotonic Boolean functions play an important role in complexity theory and naturally occur in a number of applications.
The goal of this project is to compute a compact representation for monotonic Boolean functions given as circuits or propositional logic programs, i.e., to find a circuit with a small number of gates which computes the given function. The resulting algorithm shall then be applied to the problem of computing relaxation heuristics for AI planning tasks, and to the problem of line of sight computation in discrete 2D worlds.
