Principles of AI Planning - Overview

Lecturers: Prof. Dr. Bernhard Nebel and Dr. Robert Mattmüller

Time and place

Lecture: Tuesday, 16:15-17:45, and Thursday, 16:15-17:00, in lecture hall 101-00-036. Slides and recordings made in the previous winter semester, with the same content as the in-person lecture, will be uploaded to ILIAS.
Exercises and Q&A: Thursday, 17:00-17:45, in lecture hall 101-00-036. We will try to do this in a hybrid way with possible remote participation via Zoom.

Language

The lecture will be given in English, and the lecture slides will be in English as well. Exercises may be answered in German or English.

Topics

The lecture provides a detailed introduction to the theoretical and algorithmic foundations of modern AI planning systems. In detail, we will cover the following topics:

Formalization of planning
Planning as search; progression and regression
Satisficing heuristic-search planning using relaxation heuristics
Optimal heuristic-search planning using abstraction heuristics
Optimal heuristic-search planning using landmark heuristics
State-space pruning techniques for planning
Planning in nondeterministic domains
Theoretical complexity of planning

Prerequisites

The course is primarily aimed at Masters students majoring in Computer Science, but advanced Bachelors students in their final year and CS minors with the necessary background are also welcome.

The essential concepts from complexity theory (NP completeness, polynomial reductions) should be known. We also expect basic knowledge of the basic search algorithms covered in the lecture on Foundations of Artificial Intelligence, such as depth-first search, breadth-first search, heuristic search with the A* algorithm, or greedy best-first search. Basic knowledge of (propositional) logic is expected.

Exercises and Exam

Bachelors and Masters students in Computer Science can take this course as part of their specialization in the area of cognitive technical systems. There will be a final exam that needs to be passed which will be oral or written, at our discretion, depending on the number of students registered for the exam. The exam will take place in the semester break after the course.

During the semester there will be weekly exercises (theoretical assignments and occasional implementation projects). To successfully complete the Studienleistung it is necessary to reach 50% of all points.

Exercises and projects may be worked on in groups of three. Larger groups or copied solutions will not be accepted and result in nonadmission to the exam.

In this course 6 ECTS credits can be earned.

ILIAS

Lecture slides, homework assignments, a bibliography, and lecture recordings will be made available via ILIAS.

More details will be provided soon via email through HISInOne and via ILIAS.

We will attempt to make all students registered for the course via HISInOne members of the ILIAS course room automatically. If you are registered via HISInOne, but do not have access to the ILIAS course room by the end of the first week of teaching, please let us know.

FAQ

Q: How exactly will this course be taught?

A: We plan to teach it in a hybrid way, with in-person lectures and exercises/Q&A sessions. The in-person meetings are scheduled for Tuesdays, 16:15-17:45 (lectures), and Thursdays, also 16:15-17:45 (lectures + exercises/Q&A), always in lecture hall 101-00-036. The in-person meetings will not be recorded, so there should be plenty of opportunity for interaction and questions. There will still be lecture recordings (and slides) available on ILIAS, namely those from last year. We intend to cover the exact same material in the in-person lectures also covered in the ILIAS recordings, so even though the experience between in-person meetings and recorded lectures may differ, the material is equivalent. For the exercise/Q&A sessions on Thursdays from 17:00-17:45, we intend to go fully hybrid by allowing in-person presence in lecture hall 101-00-036 as well as remote participation via Zoom. Fresh Zoom meeting IDs and passwords will be used each week, and communicated via the ILIAS forum that is part of the ILIAS course room. Note that those meetings will not be recorded, so again, there is no reason to be shy and not speak up during the exercises.

Q: What will be the style of the in-person lectures?

A: A fairly standard presentation-style lecture. We will try to make it as interaction-friendly as possible, though. If you have questions at any point during the lectures, do not hesitate to interrupt us and ask. We have enough time, and in case we need to go over some parts of the material a bit faster to compensate for discussion time, this is fine. Recordings and slides are available for a detailed review, after all. Note that we are not using the flipped classroom setting in the sense that we would expect you to study the material beforehand.

Q: What will be the style of the exercise/Q&A sessions?

A: We will start with a quick (ca. 5-10 minute) online live-quiz for warm-up. This means that those participating in presence should bring a computer or other mobile device with internet access if they want to take the quiz, too. This will be followed by a Q&A part where everyone (present or via Zoom) can ask questions about the lecture material. After that, we discuss the exercise sheets and model solutions.

Q: How should I prepare for the Q&A sessions and discussion of homework assignments?

A: Please bring your questions that came up while studying the material of the week! Don't be shy to ask. For those participating remotely: Questions can be asked via chat or verbally. We as instructors will do our best to answer your questions.

Q: What material can be found on ILIAS?

A: Lecture slides, lecture recordings (from the winter semester 2020/2021), homework assignments, pointers to the literature, pointers to external resources.

Q: In what intervals will new material be added to ILIAS?

A: Lecture slides and recordings have already been uploaded to ILIAS. Access to the material for a given week will always be enabled on Monday mornings of that week. You should be able to configure ILIAS to notify you whenever new material is available. Feel free to use those slides/recordings or other resources of you choice to study the material.

Q: What about the homework assignments?

A: There will be weekly exercise sheets and possibly a more practical hands-on exercise every now and then. Furthermore, we provide quizzes about the material every week (usually a superset of the live quizzes mentioned above). Exercise sheets will be uploaded to ILIAS once a week. Solutions are due one week later, and have to be submitted via ILIAS as well. Within another week, you will receive individual feedback on your solutions, and possibly model solutions, again via ILIAS. The exercise sheets must be worked on in groups of three students. How you coordinate with your group members is up to you. If you need help finding group partners, let us know. Please hand in only one copy of your solution per group.

Q: How will asynchronous communication between students and instructors work?

A: First, we hope that much of the interaction and discussion of the course material can be accomplished in person on Tuesdays and Thursdays. However, we also understand that not everyone will always be able to attend those meetings. Therefore, the instructors will use the HISInOne "email to all participants" feature and the ILIAS forum for this course to broadcast important information. Contact via individual email is possible, too. Furthermore, we encourage you to use the forum to ask questions and answer those of your peers. The instructors will also be active in this forum. Topics suitable for the forum include questions about the lecture, questions about the assignments, and organizational or technical questions.

Q: Do I need to somehow sign up to attend the in-person meetings?

A: No. Lecture hall 101-00-036 is large enough for all registered participants, as long as masks are worn.

Q: Anything else I should know when participating in person?

A: Yes. First, for each teaching event attended in person, students have to "check in" before the event. Second, students must fulfill 3G ("geimpft" = vaccinated or "genesen" = immunity by infection or "getestet" = negative antigen or PCR test from the last 24 hours). If a student does not "check in", it's an "Ordnungswidrigkeit".