Archive: Fall Semester 2016
Lecture: Planning and Optimization
Course Number | 45400-01 |
Lecturers |
Malte Helmert
Gabriele Röger |
Assistants |
Martin Wehrle
Thomas Keller |
Tutors | Salome Eriksson |
Time and Location |
Mon 14:15 - 16:00; Seminarraum 00.003, Spiegelgasse 1
Thu 14:15 - 16:00; Seminarraum 00.003, Spiegelgasse 1 |
Start | 22-09-2016 |
Exercises | Thu 16:00 - 17:30; Seminarraum 00.003, Spiegelgasse 1 |
Prerequisites |
Good knowledge in the foundations and core areas of computer science are assumed (in particular algorithms and data structures, complexity theory, mathematical logic, programming).
Good knowledge of the contents of the course "Foundations of Artificial Intelligence" (13548) is assumed, in particular the chapters on state-space search. Students who have not previously passed the prerequisite course are strongly advised to learn the necessary material in self-study prior to the beginning of this course. If you are interested in participating in this course but do not yet have strong knowledge on state-space search, we strongly encourage you to contact the lecturers prior to the semester to discuss a possible self-study plan. |
Objectives | The participants get to know the theoretical and algorithmic foundations of action planning as well as their practical implementation. They understand the fundamental concepts underlying modern planning algorithms as well as the theoretical relationships that connect them. They are equipped to understand research papers and conduct projects in this area. |
Literature | There is no textbook for the course. The course slides will be made available to the participants, and additional research papers complementing the course materials will be uploaded to the course webpage during the semester. |
Assessment |
Lehrveranst.-begleitend
Please note : Oral examination, January 30 - February 01, 2017 Marked homework exercises will be handed out weekly in order to verify the learning progress. To qualify for the oral examination, students must obtain at least 50% of the total marks from the exercises. Exercise marks do not contribute to the final grade for the course, which is exclusively based on the oral examination. |
Credit Points | 8 |
Grades | 1-6 0,5 |
Modules |
Modul Kerninformatik (MSF - Informatik (Studienbeginn vor 01.08.2016))
Modul Kerninformatik (Master Informatik 10) Wahlbereich Master Informatik: Empfehlungen (Master Informatik 10) Modul Praxis aktueller Informatikmethoden (MSF - Informatik (Studienbeginn vor 01.08.2016)) Modul Applications of Distributed Systems (Master Computer Science 16) Modul Concepts of Machine Intelligence (Master Computer Science 16) Modul Concepts of Machine Intelligence (MSF - Computer Science) |
Registration | Services (Requires login) |
Lecture slides
No. | Topic | Date | Slides |
A1 | Organizational Matters | 22.09.2016 | |
A2 | What is Planning? | 22.09.2016 | |
A3 | Transition Systems and Propositional Logic | 03.10.2016 | |
A4 | Planning Tasks | 03.10.2016 | |
A5 | Equivalent Operators and Effect Normal Form | 06.10.2016 | |
A6 | Positive Normal Form and STRIPS | 06.10.2016 | |
A7 | Invariants and Mutexes | 10.10.2016 | |
A8 | Finite Domain Representation | 10.10.2016 | |
B1 | Planning as Search | 13.10.2016 | |
B2 | Regression: Introduction & STRIPS Case | 13.10.2016 | |
B3 | General Regression, Part I | 17.10.2016 | |
B4 | General Regression, Part II | 17.10.2016 | |
B5 | Computational Complexity of Planning: Background | 20.10.2016 | |
B6 | Computational Complexity of Planning: Results | 20.10.2016 | |
C1 | Delete Relaxation: Introduction | 24.10.2016 | |
C2 | Delete Relaxation: Finding Relaxed Plans | 24.10.2016 | |
C3 | Delete Relaxation: AND/OR Graphs | 27.10.2016 | |
C4 | Delete Relaxation: Relaxed Task Graphs | 27.10.2016 | |
C5 | Delete Relaxation: h max and h add | 31.10.2016 | |
C6 | Delete Relaxation: Best Achievers and h FF | 31.10.2016 | |
C7 | Abstractions: Introduction | 03.11.2016 | |
C8 | Abstractions: Formal Definition and Heuristics | 03.11.2016 | |
C9 | Abstractions: Additive Abstractions | 07.11.2016 | |
C10 | Pattern Databases: Introduction | 07.11.2016 | |
C11 | Pattern Databases: Multiple Patterns | 10.11.2016 | |
C12 | Pattern Databases: Pattern Selection | 10.11.2016 | |
C13 | Merge-and-Shrink Abstractions: Synchronized Product | 14.11.2016 | |
C14 | Merge-and-Shrink Abstractions: Generic Algorithm | 14.11.2016 | |
C15 | M&S: Maintaining the Mapping and Some Theory | 17.11.2016 | |
C16 | M&S: Strategies and Label Reduction | 17.11.2016 | |
C17 |
Critical Path Heuristics:
h^m |
21.11.2016 | |
C18 | Critical Path Heuristics: Properties and Pi^m Compilation | 21.11.2016 | |
C19 | Landmarks: Introduction & Minimum Hitting Set Heuristics | 24.11.2016 | |
C20 | Landmarks: Cut Landmarks & LM-cut Heuristic | 24.11.2016 | |
C21 | Landmarks: And/Or Landmarks | 28.11.2016 | |
C22 | Landmarks: LM-count Heuristic | 28.11.2016 | |
C23 | Linear & Integer Programming | 01.12.2016 | |
C24 | Flow Heuristic | 01.12.2016 | |
D1 | Cost Partitioning: Definition, Properties, and Abstractions | 05.12.2016 | |
D2 | Cost Partitioning: Landmarks and Generalization | 05.12.2016 | |
D3 | Post-hoc Optimization | 08.12.2016 | |
D4 | Operator Counting | 08.12.2016 | |
D5 | Potential Heuristics | 08.12.2016 | |
D6 | Comparison of Heuristic Families I | 12.12.2016 | |
D7 | Comparison of Heuristic Families II | 12.12.2016 | |
E1 | Symbolic Search: BDDs | 15.12.2016 | |
E2 | BDD Operations and Breadth-First Search | 15.12.2016 | |
E3 | Symbolic Search: Uniform-cost and A search | 19.12.2016 | |
X1 | Hands-On and Repetition | 26.09.2016 | |
X2 | Hands-On and Repetition | 29.09.2016 |
Exercise sheets
No. | Due date | Files |
1. | 05.10.2016 | |
2. | 12.10.2016 |
sheet 2
|
3. | 19.10.2016 |
sheet 3
|
4. | 26.10.2016 |
sheet 4
|
5. | 02.11.2016 |
sheet 5
|
6. | 09.11.2016 |
sheet 6
|
7. | 16.11.2016 |
sheet 7
|
8. | 23.11.2016 |
sheet 8
|
9. | 30.11.2016 |
sheet 9
|
10. | 07.12.2016 |
sheet 10
|
11. | 14.12.2016 | sheet 11 |
12. | 21.12.2016 | sheet 12 |
13. | 04.01.2017 | sheet 13 |