Diploma theses

Domain control knowledge can be used to constrain the valid plans of a planning task in a certain domain. This reduces the search space and allows planning systems to solve tasks that would otherwise be too challenging. One way of defining domain control knowledge is to describe an abstract plan using a procedural (Golog-style) language. Baier proposed such a language for classical planning and showed how it can be exploited by compiling the constraint into the PDDL description of the task.

The aim of this diploma thesis is to carry this method over to temporal planning. The procedural description language should be extended with suitable temporal concepts with a clearly defined semantics. The temporal control programs should then be compiled into the temporal PDDL description of the planning task. This compilation should not only be defined theoretically but also be implemented for an experimental evaluation.

Reputation mechanisms such as those employed by Amazon and eBay offer an effective way to prevent market failure in online economies. However, most of these mechanisms assume that the privately monitored transaction outcomes are honestly reported. This clearly is a simplification since buyers may have incentives to misreport. While it has been shown that the truthful elicitation of these outcomes is feasible in settings with pure adverse selection, i.e. with a purely stochastic seller, we study whether honest feedback can be elicited in settings with moral hazard, i.e. with a strategic seller. For a pure moral hazard setting motivated by the one at eBay, we find that there is no feedback mechanism that makes honest reporting a best response to truthful play by all other players. For a combined setting with both adverse selection and moral hazard, however, we retrieve a positive result and construct a payment scheme that can be used as a "feedback plug-in" for reputation mechanisms.

Although international planning conferences, e.g. within the International Planning Competition (IPC), cover numerical as well as classical planning tasks, the number of numerical planners has remained low over recent years. This is different from the situation for classical planners, whose number has grown significantly. As a consequence, the quality of classical planners is considerably better than for numerical planners. The topic of this thesis is to modify numerical planning tasks in such a way that they can be solved with classical planners. For this purpose, the numerical parts of the problem must be extracted, converted, and reintegrated into the problem specification. In this context, the given problems are analyzed in order to recognize numerical variables and constants. We present methods for reducing the domains of numerical varables (optimally and approximatively) and to convert numerical problem into problems conforming to the STRIPS fragment of PDDL.

The present work is concerned with finding strong plans for non-deterministic planning problems by 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 PDB heuristics, which have already been successfully employed in classical planning and should now be generalized to non-deterministic planning. We show under which conditions patterns are additive and the corresponding PDB heuristics can be safely added in order to obtain an informative heuristic value while maintaining admissibility of the sum. The search algorithm and the heuristic are completely implemented. The performance of the heuristic is evaluated on three planning domains and the results are discussed. It turns out that PDB heuristics can yield very good results in non-deterministic planning as well, in particular if additivity is exploited.

In this thesis, Hoffmann's h+ heuristic for domain-independent planning systems is studied from a domain-dependent perspective. A theoretical study analyzes the complexity of computing the h+ heuristic in standard planning domains like Logistics or Blocksworld, and an empirical study implements the heuristic for a number of benchmark domains and empirically evaluates it in comparison to state-of-the-art domain-independent heuristics.

In this Diploma thesis, a procedure for generating Büchi-automata from LTL formulae is implemented and proved correct using the interactive theorem prover Isabelle/HOL. Subsequently, executable code is generated from this Isabelle spcification using the Isabelle/HOL code generator. Thus based on the original idea of the construction by Gerth, Peled, Vardi and Wolper, the correctness of the construction was proven.

Nowadays, domain-independent planning is a scientific area dealt with by many people using very different methods. Even though important advances were achieved in the last couple of years it seems as if classical methods such as heuristic search or planning as satisfiability are about to reach their limitations.

One possibility to push that limit anyways might be the inclusion of domain-dependent knowledge. This thesis covers two topics relevant to that idea: On the one hand, methods to automatically detect already known subproblems in domains are discussed. On the other hand, two optimal planners for specific domains are described and taken as an example of how to analyze domains in general.

The performance of the implemented domain-specific planners clearly shows that the use of domain-dependent knowledge leads to better performing planners.

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.

The purpose of this work is to develop a General Game Playing System based on the Java reference player Jocular that uses automatically generated evaluation functions to guide the exploration of the game tree. The inference of the evaluation function given the game description should be based on the fuzzy logic approach used in the Fluxplayer system. Experimenting with other distance heuristics would be interesting as well.

The resulting system should be evaluated against other General Game Playing Systems and possibly against human players on a number of benchmark games available online.

Timed automata are a generalisation of finite automata having, apart from states and alphabet symbols, real-valued variables called clocks as well as integer variables. In contrast to usual automata, the transitions depend on conditions on these variables. Timed automata are a wide-spread formalism for modelling systems. For model checking timed automata, there is the tool Uppaal.

In the context of the AVACS project, the AI group explores heuristic search in the state spaces of timed automata. Therefore we are always interested in hard examples. Note that timed automata with a description of a few dozen lines can easily have state spaces of size 1000000 to 100000000.

The goal of the bachelor thesis is to generate such examples, either ad-hoc or even better, automatically, so that we can analyse systematically the relationship between certain parameters (number of clocks, out-degree of the states, etc.) and the hardness of the search problem and heuristic performance.

Verification of invariants in model checking is a problem that is closely related to classical AI planning. It is thus often possible to successfully apply ideas from one of these areas to the other. In this thesis, an automata-theoretic heuristic from the model checking area is applied to classical AI planning tasks and compared to other well-known planning heuristics such as the FF heuristic.

The integration of action formalisms like Golog and planning techniques, which usually use PDDL as description language, would provide great advantages. First endeavours have been made by identifying a subset of the situation calculus, which is the basis of Golog, with the same expressive power as the ADL fragment of PDDL.

In this thesis this framework shall be enlarged to include the arithmetic functions of PDDL. For this, requirements on the situation calculus must be identified that lead to the same expressivity. This property shall be proven by means of compilation techniques which also directly provide a method to translate problems of one formalism into the other. This translation shall be implemented. Furthermore, for some of the requirements shall be proven that they are necessary, or it shall be shown to what extent they can be eased.

This diploma thesis deals with the translation of PLC automata into timed automata. Such a translation is of interest, because currently there is no model checker which accepts PLC automata directly as input. The existing translation is part of Moby/RT, a CASE tool for PLC automata. Moby/RT verifies PLC automata by first translating them into Uppaal's input language and using Uppaal for verification afterwards. However, Moby/RT uses only a small fraction of Uppaal's input language; this leads to an unnecessary blow up of the resulting automata.

This thesis describes a translation which makes use of contemporary features of the input language. The resulting timed automata are more natural as the ones produced by Moby/RT. This is because one transition of the PLC automata is represented by one transition in the translation.

In many NP-complete decision problems, one can observe so called phase transitions between regions of underconstrained positive and overconstrained negative instances. These transitions can usually be characterized by a problem dependent order parameter. Instances far away from the phase boundary can often be easily shown to be positive or negative instances, respectively. Many of the really hard instances are located near the phase boundary.

In this thesis, phase transitions in planning benchmark problems are investigated and described empirically, as knowledge about phase transitions potentially permits the automatic generation of particularly hard benchmark instances.

The goal of this diploma thesis is to develop an algorithm for exploration on rough terrain containing obstacles as pallets or ramps. In contrast to environments as gras or gravel, which already pose a challenge for a robot's mobility, very steep structures cannot be handled by just one behavior. Moreover it is necessary, that the robot knows about different obstacles and possesses specific skills to negotiate them.

To detect obstacles the robot uses a tilted 2d laser range scanner und builds classified elevation maps online. Based on those maps and a set of skill descriptions behavior maps are built automatically encoding skill routines directly into the map. This enables to plan using classical A* search handling specific obstacles implicitly. Experiments demonstrate a fully autonomous run in a test parcours, while the robot is traversing a pallet and a ramp.

Partial satisfaction planning or over-subscription planning is an extension of the classical planning problem where the agent has the option of only partially satisfying a given goal. To estimate plan quality, the utility provided by the satisfied subgoals is compared to the cost of the plan.

In this thesis, algorithms for partial satisfaction planning are implemented, focusing on the problem of selecting an appropriate set of subgoals. For planning the actual sequence of actions for a given set of subgoals, a classical planner is used as a black box. Several new approaches to partial satisfaction planning are evaluated against each other and against techniques from the literature.

We apply Monte Carlo simulation and alpha-beta search to the game of Skat. The developed Skat-playing program integrates well-known techniques such as move ordering with two new search enhancements. Quasi-symmetry reduction generalizes symmetry reductions, popularized by Ginsberg's Partition Search algorithm, to search states which are "almost equivalent". Adversarial heuristics generalize ideas from single-agent search algorithms like A* to two-player games, leading to guaranteed lower and upper bounds for the score of a game position. Combining these techniques with state-of-the-art tree search algorithms, our program determines the game-theoretical value of a typical Skat hand (with perfect information) in 10 milliseconds.