Knowledge Representation

Seminar Dynamics of Knowledge and Belief SS 2014

Submitted by Christoph Schwering on 6. January 2014 - 0:08

In this seminar we will study several modeling and reasoning techniques for knowledge and belief in dynamic systems. Knowledge is an important aspect of intelligent programs: while most of today's systems assume a closed world, i.e., everything they don't know to be true is assumed to be false, an intelligent system needs to consider possible that there are truths not known to the system. In a dynamic environment, i.e., an environment where one or multiple agents (inter)act, the system will usually have to acquire new knowledge through sensing. Potentially it may even revise its beliefs when it realizes some beliefs were wrong. In this seminar we will study various aspects of action, knowledge, and belief.

We plan to implement a peer review process for this seminar. That is, every student will read some other students' term paper and provide feedback in form of a written review. This shall not only deepen your understanding of the other topics, but it also introduces you to the academic review process.

Diploma Thesis: Towards Decidable Verification of Non-Terminating Golog Programs [completed]

Submitted by Martin Liebenberg on 13. April 2013 - 20:45

Claßen and Lakemeyer recently introduced algorithms for the verification of temporal properties of non-terminating Golog programs, based on the first-order modal Situation Calculus variant ES, and regression-based reasoning. However, while Golog’s high expressiveness is a desirable feature, it also means that their verification procedures cannot be guaranteed to terminate in general. In this thesis, we address this problem by showing that, for a relevant subset, the verification of non-terminating Golog programs is indeed decidable, which is achieved by means of three restrictions. First, we use the ES variant of a decidable two-variable fragment of the Situation Calculus that was introduced by Gu and Soutchanski. Second, we have to restrict the Golog program to contain ground action only. Finally, we consider special classes of successor state axioms, namely the context-free ones and those that only admit local effects.

Hybris-A1: Verification of Non-Terminating Action Programs

Submitted by Jens Claßen on 1. February 2013 - 19:00

The action language GOLOG has been used, among other things, for the specification of the behaviour of mobile robots. Since the task of such autonomous systems is typically open-ended, their GOLOG programs are usually non-terminating. To ensure that the program will let the robot exhibit the intended behaviour, it is often desirable to be able to formally specify and then verify the desired properties, which are often of a temporal nature. This task has been studied within our preliminary work from two perspectives: On the one hand, the problem was tackled for very expressive specification and action program formalisms, but without the goal of achieving decidability, i.e. the developed verification methods were not guaranteed to terminate. On the other hand, the verification problem was studied for action formalisms based on decidable description logics and very limited means of specifying admissible sequences of actions, which allowed us to show decidability and complexity results for the verification problem. The purpose of this project is to combine the advantages of both approaches by, on one hand, developing verification methods for GOLOG programs that are effective and practically feasible and, on the other hand, going beyond the formalisms with very limited expressiveness to enhance their usefulness. Among other things, both qualitative and quantitative temporal program properties will be addressed.

Seminar Robust Reliable Robotics SS 2012

Submitted by tim on 9. January 2012 - 13:10

In this seminar we will study several aspects of robust and reliable robotics. Robots are machines created to fulfill particular tasks instead of or in cooperation with humans. In virtually all scenarios a failure is annoying or even catastrophic. Planetary rovers cannot be repaired easily or at all, broken factory robots can become vastly expensive not only due to the cost to repair the robot itself, but the problems they cause for the overall supply chain; and domestic service robots operate in close proximity to humans in their habitats and must take special precautions as not to harm a human or damage the interior. These considerations make it necessary to develop techniques and systems that enable a robot system to detect failures or unexpected behavior and at least stop, better even work around the problem.

The topics include recent papers on execution monitoring, robot system debugging, and fault detection.

Seminar Knowledge Representation and Computational Tractability SS 2011

Submitted by vaishakbelle on 4. January 2011 - 18:11

Knowledge Representation (KR) is a vibrant and exciting field in artificial intelligence. The endeavor rests on two fundamental ideas. First, to reason about the problem domain one must formalize it, perhaps in some logical formalism such as propositional logic or first-order logic. Second, for the representation to be useful one must be able to obtain reasonable and intuitive inferences in a timely fashion.
Unfortunately, propositional reasoning is intractable (Boolean reasoning is NP-COMPLETE) and first-order logic is undecidable. Thus, an important goal in the KR enterprise is to find a tradeoff be- tween the expressiveness of the representational language and the computational behavior of associated reasoning tasks. A main objective of this seminar is to discuss approaches bordering this tradeoff.

Bachelor's Thesis: Implementation and Evaluation of an ES-based Golog system [completed]

Submitted by Jens Claßen on 19. May 2010 - 20:00

This thesis describes the implementation and evaluation of an extension to the agent control language IndiGolog that uses the ES logic as description language, which allows a higher expressiveness including nested belief operators, quantifying-in and arbitrary first order logic sentences as the objective knowledge base. To exploit the full expression power of ES, a first-order logic theorem prover is used to evaluate requests against the agents knowledge base. For those changes the modular build-up of IndiGolog is harnessed, such that only a redevelopment of the evaluator was needed, whereas the remaining system was unchanged. After an introduction into the ES-logic and the IndiGolog platform the construction of the new evaluation module is described. Afterwards the new system is evaluated against original IndiGolog and Flux, another agent framework, and the advantages in terms of expression power are lined out.