Archive: Spring Semester 2017
Lecture: Foundations of Artificial Intelligence
| Course Number | 13548-01 |
| Lecturers |
Malte Helmert
Gabriele Röger |
| Assistants |
Jendrik Seipp
Silvan Sievers |
| Tutors | Daniel Killenberger |
| Time and Location |
Mon 16:15 - 18:00; Seminarraum 05.002, Spiegelgasse 5
Wed 14:15 - 16:00; Seminarraum 05.002, Spiegelgasse 5 |
| Start | 20-02-2017 |
| Exercises |
Tue 16:15 - 18:00; Seminarraum 00.003, Spiegelgasse 1
Wed 16:15 - 18:00; Computer-Labor U1.001, Spiegelgasse 1 Group assignment (Requires login) |
| Prerequisites | No formal requirements, but solid basic knowledge of foundational concepts in computer science (algorithms, complexity theory) and mathematics (formal proofs and basic concepts like sets, functions and relations) are necessary for following the lecture. Good programming skills are necessary for some of the exercises. |
| Objectives | Students learn the theoretical and practical foundations of classical problems in artificial intelligence and their algorithmic solution. In particular, participants will obtain the necessary knowledge and skills to independently solve typical AI problems by selecting, implementing and evaluating standard algorithms from the AI literature. |
| Contents | The course offers an introduction into the basic concepts, problems, methods and algorithms of artificial intelligence. Topics include: introduction and historical development of AI, rational agents, problem solving and search, constraint satisfaction problems, formal logic, and automated planning. |
| Literature | Stuart Russell and Peter Norvig: Artificial Intelligence - A Modern Approach (3rd edition), Prentice Hall, 2009. |
| Assessment |
Lehrveranst.-begleitend
Please note : oral examination; 28/29/30 June 2017, Spiegelgasse 1, office 06.004. The course includes weekly homework assignments and weekly exercise sessions. To pass the course, students need to successfully work on the homework assignments and pass the final oral examination. At least 50% of the possible marks from homework assignment are needed to qualify for the final exam. The final grade for the course is based exclusively on the final exam. |
| Credit Points | 8 |
| Grades | 1-6 0,5 |
| Modules |
Vertiefungsmodul Computer Science (Bachelor Informatik 07)
Vertiefungsmodul Bioinformatik (Bachelor Informatik 07) Modul Wahlbereich Informatik (BSF - Informatik (Studienbeginn vor 01.08.2016)) Modul Praxis aktueller Informatikmethoden (MSF - Informatik (Studienbeginn vor 01.08.2016)) Vertiefungsmodul Computational Intelligence (Bachelor Informatik 10) Vertiefungsmodul Life Science-Informatik (Bachelor Informatik 10) Modul Methoden für Computational Biology (Bachelor Computational Sciences 11) Modul Methoden für Computational Chemistry (Bachelor Computational Sciences 11) Modul Methoden für Computational Mathematics (Bachelor Computational Sciences 11) Modul Methoden für Computational Physics (Bachelor Computational Sciences 11) Modul Machine Intelligence (Bachelor Computer Science 16) Modul Applications and Related Topics (BSF - Computer Science) |
| Registration | Services (Requires login) |
Slides
| No. | Topic | Date | Slides |
| 0. | Organizational Matters | 20.02.2017 |
(Screen)
(Printer) |
| 1. | Introduction: What is Artificial Intelligence? | 20.02.2017 |
(Screen)
(Printer) |
| 2. | Introduction: AI Past and Present | 22.02.2017 |
(Screen)
(Printer) |
| 3. | Introduction: Rational Agents | 22.02.2017 |
(Screen)
(Printer) |
| 4. | Introduction: Environments and Problem Solving Methods | 27.02.2017 |
(Screen)
(Printer) |
| 5. | Introduction: State-Space Search: State Spaces | 27.02.2017 |
(Screen)
(Printer) |
| 6. | State-Space Search: Representation of State Spaces | 01.03.2017 |
(Screen)
(Printer) |
| 7. | State-Space Search: Examples of State Spaces | 01.03.2017 |
(Screen)
(Printer) |
| 8. | State-Space Search: Data Structures for Search Algorithms | 13.03.2017 |
(Screen)
(Printer) |
| 9. | State-Space Search: Tree Search and Graph Search | 13.03.2017 |
(Screen)
(Printer) |
| 10. | State-Space Search: Breadth-first Search | 15.03.2017 |
(Screen)
(Printer) |
| 11. | State-Space Search: Uniform Cost Search | 15.03.2017 |
(Screen)
(Printer) |
| 12. | State-Space Search: Depth-first Search & Iterative Deepening | 20.03.2017 |
(Screen)
(Printer) |
| 13. | State-Space Search: Heuristics | 20.03.2017 |
(Screen)
(Printer) |
| 14. | State-Space Search: Analysis of Heuristics | 22.03.2017 |
(Screen)
(Printer) |
| 15. | State-Space Search: Best-first Graph Search | 22.03.2017 |
(Screen)
(Printer) |
| 16. | State-Space Search: Greedy BFS, A*, Weighted A* | 27.03.2017 |
(Screen)
(Printer) |
| 17. | State-Space Search: IDA* | 27.03.2017 |
(Screen)
(Printer) |
| 18. | State-Space Search: Properties of A*, Part I | 29.03.2017 |
(Screen)
(Printer) |
| 19. | State-Space Search: Properties of A*, Part II | 29.03.2017 |
(Screen)
(Printer) |
| 20. | Combinatorial Optimization: Introduction and Hill-Climbing | 03.04.2017 |
(Screen)
(Printer) |
| 21. | Combinatorial Optimization: Advanced Techniques | 03.04.2017 |
(Screen)
(Printer) |
| 22. | Constraint Satisfaction Problems: Introduction and Examples | 05.04.2017 |
(Screen)
(Printer) |
| 23. | Constraint Satisfaction Problems: Constraint Networks | 05.04.2017 |
(Screen)
(Printer) |
| 24. | Constraint Satisfaction Problems: Backtracking | 10.04.2017 |
(Screen)
(Printer) |
| 25. | Constraint Satisfaction Problems: Arc Consistency | 10.04.2017 |
(Screen)
(Printer) |
| 26. | Constraint Satisfaction Problems: Path Consistency | 12.04.2017 |
(Screen)
(Printer) |
| 27. | Constraint Satisfaction Problems: Constraint Graphs | 12.04.2017 |
(Screen)
(Printer) |
| 28. | Constraint Satisfaction Problems: Decomposition Methods | 19.04.2017 |
(Screen)
(Printer) |
| 29. | Propositional Logic: Basics | 19.04.2017 |
(Screen)
(Printer) |
| 30. | Propositional Logic: Reasoning and Resolutions | 24.04.2017 |
(Screen)
(Printer) |
| 31. | Propositional Logic: DPLL Algorithm | 24.04.2017 |
(Screen)
(Printer) |
| 32. | Propositional Logic: Local Search and Outlook | 26.04.2017 |
(Screen)
(Printer) |
| 33. | Automated Planning: Introduction | 26.04.2017 |
(Screen)
(Printer) |
| 34. | Automated Planning: Planning Formalisms | 03.05.2017 |
(Screen)
(Printer) |
| 35. | Automated Planning: Delete Relaxation | 03.05.2017 |
(Screen)
(Printer) |
| 36. | Automated Planning: Delete Relaxation Heuristics | 08.05.2017 |
(Screen)
(Printer) |
| 37. | Automated Planning: Abstraction and Pattern Databases | 08.05.2017 |
(Screen)
(Printer) |
| 38. | Automated Planning: Landmarks | 10.05.2017 |
(Screen)
(Printer) |
| 39. | Automated Planning: Landmark Heuristics | 10.05.2017 |
(Screen)
(Printer) |
| 40. | Board Games: Introduction and State of the Art | 15.05.2017 |
(Screen)
(Printer) |
| 41. | Board Games: Minimax Search and Evaluation Functions | 15.05.2017 |
(Screen)
(Printer) |
| 42. | Board Games: Alpha-Beta Search | 17.05.2017 |
(Screen)
(Printer) |
| 43. | Monte-Carlo Tree Search: Introduction | 17.05.2017 |
(Screen)
(Printer) |
| 44. | Monte-Carlo Tree Search: Advanced Topics | 22.05.2017 |
(Screen)
(Printer) |
| 45. | AlphaGo and Outlook | 22.05.2017 |
(Screen)
(Printer) |
| 46. | Uncertainty: Introduction and Quantification | 24.05.2017 |
(Screen)
(Printer) |
| 47. | Uncertainty: Representation | 24.05.2017 |
(Screen)
(Printer) |
Exercise sheets
| No. | Due Date | Files |
| 1. | 01.03.2017 | Sheet 1 |
| 2. | 15.03.2017 |
Sheet 2
state-spaces.tar |
| 3. | 22.03.2017 |
Sheet 3
uniform-cost-search.tar |
| 4. | 29.03.2017 | Sheet 4 |
| 5. | 05.04.2017 |
Sheet 5
astar-search.tar |
| 6. | 12.04.2017 |
Sheet 6
chess-board.tex |
| 7. | 19.04.2017 | Sheet 7 |
| 8. | 26.04.2017 |
Sheet 8
cantons.dot |
| 9. | 03.05.2017 | Sheet 9 |
| 10. | 10.05.2017 |
Sheet 10
bridges-strips-domain.pddl koenigsberg-problem.pddl |
| 11. | 17.05.2017 |
Sheet 11
bridges-strips-fixed-domain.pddl koenigsberg-problem.pddl |
| 12. | 24.05.2017 | Sheet 12 |
Supplementary material
| Chap. | Description | Files |
| 1. | Turing's "Computation Machinery and Intelligence" | |
| 2. | Bowling et al.'s "Heads-up Limit Hold’em Poker is Solved" | |
| 2. | DARPA Grand Challenge, Video 1 | Video |
| 2. | DARPA Grand Challenge, Video 2 | Video |
| 6. | 8-Puzzle as explicit graph | BZ2 |
| 6. | 8-Puzzle declaratively represented | Zip |
| 6. | 8-Puzzle as black box | Zip |
| 6. | Delling et al.'s "Engineering Route Planning Algorithms" | |
| 8. | Burns et al.'s "Implementing Fast Heuristic Search Code" | |
| 10. | Korf and Schultze's "Large-Scale Parallel Breadth-First Search" | |
| 12. | Complexity estimation script | Python |
| 22. | McGuire et al.'s "There is no 16-Clue Sudoku" | |
| 22. | Numberphile video on Four Colour Problem | Youtube |
| 26. | Simonis' "Sudoku as a Constraint Problem" | |
| 32. | Katebi et al.'s "Empirical Study of the Anatomy of Modern SAT Solvers" |