About | Study | Members | Projects | Publications | Events | Search | Internals | Contact & Imprint

Logic-based Knowledge Representation - Events

A workshop featuring regular talks, a PhD student colloquium, and a strategy session is being held at the RWTH Aachen.

A workshop bringing together the participating researchers for presentation of new results and mutual exchange of ideas is being held at the TU Dresden.

* Mr. Conrad Drescher (TU Dresden)
Agent Logic Programs*

Agent logic programs are a new framework for declaratively specifying heuristics in planning problems. These programs are definite logic programs augmented with two special predicates that are evaluated wrt. an underlying action domain axiomatization that is subject only to some very general conditions. For example, the background action theory can be given in the Event, the Fluent, or the Situation Calculus. We present the declarative first order semantics of agent logic programs and their operational semantics that is based on SLD-resolution and Constraint Logic Programming.

*Mr. Jens Claßen (RWTH Aachen)
A Logic for Non-Terminating Golog Programs*

Typical Golog programs for robot control are non-terminating. Analyzing such programs so far requires meta-theoretic arguments involving complex fix-point constructions. We propose a logic based on the situation calculus variant ES, which includes elements from branching time, dynamic and process logics and where the meaning of programs is modelled as possibly infinite sequences of actions. We show how properties of non-terminating programs can be expressed in the logic and, for a subset of it, how existing ideas from symbolic model checking in temporal logic can be applied to automatically verify program properties.

*Mr. Jens Claßen (RWTH Aachen)
Integrating Golog and Planning: An Empirical Evaluation*

The Golog family of action languages has proven to be a useful means for the high-level control of autonomous agents, such as mobile robots. In particular, the IndiGolog variant, where programs are executed in an online manner, is applicable in realistic scenarios where agents possess only incomplete knowledge about the state of the world, have to use sensors to gather necessary information at runtime and need to react to spontaneous, exogenous events that happen unpredictably due to a dynamic environment. Often, the specification of such an agent's program also involves that certain subgoals have to be solved by means of planning. IndiGolog supports this in principle by providing a variety of lookahead mechanisms, but when it comes to pure, sequential planning, these usually cannot compete with modern state-of-the-art planning systems, most of which being based on the Planning Domain Definition Language PDDL. Previous theoretical results provide insights on the semantical compatibility between Golog and PDDL and how they compare in terms of expressiveness. We do an empirical evaluation that shows that equipping IndiGolog with a PDDL planner (FF in our case) pays off in terms of the runtime performance of the overall system. For that matter, we study a number of example application domains and compare the needed computation times for varying problem sizes and difficulties.

*Ms Gabi Röger (Uni Freiburg)
How Good is Almost Perfect?*

Heuristic search using algorithms such as A* and IDA* is the prevalent method for obtaining optimal sequential solutions for classical planning tasks. Theoretical analyses of these classical search algorithms, such as the well-known results of Pohl, Gaschnig and Pearl, suggest that such heuristic search algorithms can obtain better than exponential scaling behaviour, provided that the heuristics are accurate enough. We show that for a number of common planning benchmark domains, including ones that admit optimal solution in polynomial time, general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the optimistic assumption of almost perfect heuristic estimators, whose heuristic error is bounded by a small additive constant. The results shed some light on the comparatively bad performance of optimal heuristic search approaches in simple domains such as Gripper. They suggest that in many domains, further improvements in run-time require changes to other parts of the planning algorithm than the heuristic estimator.

*Mr Stephan Schiffel (TU Dresden)
Symmetry Detection in General Game Playing*

We develop a method for detecting symmetries in arbitrary games and exploiting these symmetries when using tree search to play the game. Games in the General Game Playing domain are given as a set of logic based rules defining legal moves, their effects and goals of the players. The rules are similar to Situation Calculus domain axiomatizations. The main idea of the presented method is to transform the rules of a game into a vertex-labeled graph such that automorphisms of the graph correspond with symmetries of the game.

*Mr Hongkai Liu (TU Dresden)
The Projection Problem For The Description Logic EL*

The complexity of the projection problem for the description logics between ALC and ALCQIO is known to be intractable. In this talk, we will discuss whether tractability can be restored by restricting the expressivity of the languages underlying the action formalism. We will show that even for the very lightweight description logic EL, for which the standard inference problems can be done in polynomial time, the projection problem with empty TBox is already coNP-hard even if negations only occur in the post-conditions. The coNP upper bound is given with the help of the so-called small model property for EL with atomic negations. If we allow acyclic TBoxes, then the projection problem for EL is PSpace-complete, which is as hard as the one for ALC.

*Ms Maja Milicic (TU Dresden)
Planning in Action Formalisms based on DLs: First Results*

We continue the recently started work on integrating action formalisms with description logics (DLs), by investigating planning in the context of DLs. We prove that the plan existence problem is decidable for actions described in fragments of ALCQIO. More precisely, we show that its computational complexity coincides with the one of projection for DLs between ALC and ALCQIO.

*Mr Stephan Schiffel (TU Dresden)
Fluxplayer: A Successful General Game Player*

General Game Playing (GGP) is the art of designing programs that are capable of playing previously unknown games of a wide variety by being told nothing but the rules of the game. This is in contrast to traditional computer game players like Deep Blue, which are designed for a particular game and can't adapt automatically to modifications of the rules, let alone play completely different games. General Game Playing is intended to foster the development of integrated cognitive information processing technology. In this talk we present an approach to General Game Playing using a novel way of automatically constructing a position evaluation function from a formal game description. Our system is being tested with a wide range of different games. Most notably, it is the winner of the AAAI GGP Competition 2006.

*Mr Patrick Eyerich (Uni Freiburg)
Subsumption of Planning Operators*

Actions and operators are playing an important role in many subfields of artificial intelligence such as e.g. automated planning. The possibility to search automatically for subsumption relations between operators would provide great advantages: Among other things, operator domains which were developed independently could be compared with each other much more precisely. Furthermore, the design of new operator domains could be facilitated by creating new operators as specialisations or generalisations of already existing operators. In this talk we will introduce the concept of operator subsumption, investigate the complexity of the problem to decide whether there is a subsumption relation between two operators and illustrate why there cannot be a natural modelling of the subsumption problem in OWL.

*Ms Maja Milicic (TU Dresden)
Updating Description Logic ABoxes*

Description logic (DL) ABoxes are a tool for describing the state of affairs in an application domain. In this talk, we consider the problem of updating ABoxes when the state changes. We assume that changes are described at an atomic level, i.e., in terms of possibly negated ABox assertions that involve only atomic concepts and roles. We analyze such basic ABox updates in several standard DLs by investigating whether the updated ABox can be expressed in these DLs and, if so, whether it is computable and what is its size. It turns out that DLs have to include nominals and the "@" constructor of hybrid logic (or, equivalently, admit Boolean ABoxes) for updated ABoxes to be expressible. We devise algorithms to compute updated ABoxes in several expressive DLs and show that an exponential blowup in the size of the whole input (original ABox + update information) cannot be avoided unless every PTIME problem is LOGTIME-parallelizable. We also exhibit ways to avoid an exponential blowup in the size of the original ABox, which is usually large compared to the update information.

*Mr Patrick Eyerich (Albert-Ludwigs-Universit�t Freiburg)
Basic Action Theories with the same expressive power as ADL*

Action formalisms like GOLOG or FLUX have been developed primarily to get an expressive language. In another line of research efficiency of planning methods was the topmost goal, resulting in strongly restricted expressivity of the languages (above all STRIPS). The planning language PDDL developed in 1998 is an extension of STRIPS with many expressive features. So it turns out to be quite interesting to compare its expressivity with that of action formalisms. Basic Action Theories are used to characterize dynamical domains in the situation calculus and they are the basis of GOLOG. We will define so called Restricted Basic Action Theories which are as expressive as the ADL-fragment of PDDL. To prove this equivalence in terms of expressivity we use the compilation framework.

*Mr Stephan Schiffel (TU Dresden)
Reconciling Situation and Fluent Calculus*

The Situation Calculus and the Fluent Calculus are successful action formalisms that share many concepts. But until now there is no formal relation between the two calculi that would allow to formally analyze the relationship between the two approaches as well as between the programming languages based on them, Golog and FLUX. Furthermore, such a formal relation would allow to combine Golog and FLUX and to analyze which of the underlying computation principles is better suited for different classes of programs. We develop a formal translation between domain axiomatizations of the Situation Calculus and the Fluent Calculus and present a Fluent Calculus semantics for Golog programs. For domains with deterministic actions our approach allows an automatic translation of Golog domain descriptions and execution of Golog programs with FLUX.

*Mr Jens Claßen (RWTH Aachen)
A Semantics for ADL as Progression in the Situation Calculus*

Lin and Reiter were the first to propose a purely declarative semantics of STRIPS by relating the update of a STRIPS database to a form of progression in the situation calculus. We show that a corresponding result can be obtained also for ADL. We do so using a variant of the situation calculus recently proposed by Lakemeyer and Levesque. Compared to Lin and Reiter this leads to a simpler technical treatment, including a new notion of progression.