Knowledge-Based Systems Group

Lecture - Introduction to Knowledge Representation SS 2011

An announcement of the course can also be found in the course information system CAMPUS.

Contents

Topics covered in the course

The course introduces techniques for knowledge representation and reasoning. The topics covered are:

Proseminar Artificial Intelligence SS 2011

An announcement of the course can also be found in the course information system CAMPUS.

Content

In this proseminar we discuss selected topics from the textbook

• Stuart Russel, Peter Norvig: Artificial Intelligence - A Modern Approach, 3rd Edition, Prentice Hall, 2010. (or any later edition)

Requirements

The requirements for successfully completing the ProSeminar are to:

Seminar Knowledge Representation and Computational Tractability SS 2011

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.
Over the past decades, a few approaches have been proposed. One direction is to consider restric- tions to the representation language, such as those represented by description logics [Nardi & Brachman 2003; Brachman & Levesque 2004], which are currently implemented in a number of web and ontology applications. The second is to weaken the entailment relation is some way, such as those represented by [Schaerf & Cadoli 1995; Dalal 1996; Liu, Lakemeyer & Levesque 2004]. An emerging direction is to combine the two constraints, such as those represented by [Levesque 1998]. Here the language is not too restrictive, and the entailment is not too weak. Lastly, the worst-case non-polynomial com- plexity of Boolean reasoning has been challenged [Mitchell, Selman & Levesque 1992], as represented by research in satisfiability solvers [Gomes, Kautz, Sabharwal & Selman 2008] and its use in planning [Kautz & Selman 1992].
An important application of KR techniques, besides allowing us to reason about the facts about a domain, has been in reasoning about the dynamics and actions. A popular formalism is the situation calculus, and its variants developed by Reiter and his colleagues [McCarthy & Hayes 1969; Reiter 2001; Reiter 1991]. Thus, a second focus of this seminar is the explore the applications of KR methods to reason about uncertainty, reinforcement learning and dynamic programming, and robotics. For instance, approaches such as [Fagin & Halpern 1994], and its applications to the situation calculus [Bacchus, Halpern & Levesque 1995] attempt to address the fundamental issue that the world is inherently noisy; sensors are inaccurate and effectors are often faulty.