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.
Participation
Places for seminars and laboratories are centrally allocated. Please apply directly through the link provided to you by the CAMPUS systems/Masters coordinator. Specify very clearly why you are interested in joining the seminar. You can also mention courses you have taken in the past which you believe will help you participate in the seminar successfully. Failing to provide such reasons may mean that we will not consider your application. Additional Information
- Please read and understand our general information and suggestions on seminars!
Requirements
- basic study period completed (Vordiplom) or currently doing your Master studies. Bachelor students may also apply provided they have already completed OR they are currently attending courses offered by the department.
- An understanding of logic in AI and computer science
- It is extremely helpful if the participants have taken both the Artificial Intelligence and the Knowledge Representation course
Topics
The seminar offers 10 topics, the details of which can be found in the PDF attached. Staff contacts can be found here.
List of topics:
- Description Logics
- Approximate Reasoning
- Open-World Reasoning
- Tractable reasoning with Incomplete KBs
- Tractable planning
- SAT
- Progression
- Tractable Progression
- Interval Algebra
- Symbolic Dynamic Programming