Participation
Please register for the course to gain access to the Adam workspace.
Lecture Slides
| No. | Topic | Date | Slides |
|---|---|---|---|
| A1 | Organizational Matters | 17.09. | printer handout screen |
| A2 | What is Planning? | 17.09. | printer handout screen |
| A3 | Getting to Know a Planner | 22.09. | printer handout screen |
| B1 | Transition Systems and Propositional Logic | 22.09. | printer handout screen |
| B2 | Introduction to Planning Tasks | 24.09. | printer handout screen |
| B3 | Formal Definition of Planning | 24.09. | printer handout screen |
| B4 | Equivalent Operators and Normal Forms | 29.09. | printer handout screen |
| B5 | Positive Normal Form and STRIPS | 29.09. | printer handout screen |
| B6 | Computational Complexity of Planning: Background | 01.10. | printer handout screen |
| B7 | Computational Complexity of Planning: Results | 01.10. | printer handout screen |
| C1 | Overview of Classical Planning Algorithms (Part 1) | 06.10. | printer handout screen |
| C2 | Overview of Classical Planning Algorithms (Part 2) | 06.10. | printer handout screen |
| C3 | Progression and Regression Search | 08.10. | printer handout screen |
| C4 | General Regression | 08.10. | printer handout screen |
| C5 | SAT Planning: Core Idea and Sequential Encoding | 13.10. | printer handout screen |
| C6 | SAT Planning: Parallel Encoding | 13.10. | printer handout screen |
| C7 | Symbolic Search: Binary Decision Diagrams | 15.10. | printer handout screen |
| C8 | Symbolic Search: Full Algorithm | 15.10. | printer handout screen |
| D1 | Delete Relaxation: Relaxed Planning Tasks | 20.10. | printer handout screen |
| D2 | Delete Relaxation: Properties of Relaxed Planning Tasks | 20.10. | printer handout screen |
| D3 | Delete Relaxation: Finding Relaxed Plans | 22.10. | printer handout screen |
| D4 | Delete Relaxation: AND/OR Graphs | 22.10. | printer handout screen |
| D5 | Delete Relaxation: Relaxed Task Graphs | 27.10. | printer handout screen |
| D6 | Delete Relaxation: hmax and hadd | 27.10. | printer handout screen |
| D7 | Delete Relaxation: Analysis of hmax and hadd | 29.10. | printer handout screen |
| D8 | Delete Relaxation: hFF and Comparison of Heuristics | 29.10. | printer handout screen |
| E1 | Planning Tasks in Finite-Domain Representation | 03.11. | printer handout screen |
| E2 | Invariants and Mutexes | 03.11. | printer handout screen |
| E3 | Abstractions: Introduction | 05.11. | printer handout screen |
| E4 | Abstractions: Formal Definition and Heuristics | 05.11. | printer handout screen |
| E5 | Abstractions: Additive Abstractions | 10.11. | printer handout screen |
| E6 | Pattern Databases: Introduction | 10.11. | printer handout screen |
| E7 | Pattern Databases: Multiple Patterns | 12.11. | printer handout screen |
| E8 | Pattern Databases: Pattern Selection | 12.11. | printer handout screen |
| E9 | Merge-and-Shrink: Factored Transition Systems | 17.11. | printer handout screen |
| E10 | Merge-and-Shrink: Algorithm | 17.11. | printer handout screen |
| E11 | Merge-and-Shrink: Properties and Shrink Strategies | 19.11. | printer handout screen |
| E12 | Merge-and-Shrink: Merge Strategies & Outlook | 19.11. | printer handout screen |
| All slides (up to and including E12) | printer handout screen |
Extra Material
| No. | Title | Files |
|---|---|---|
| B7 | Tom Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2), pp. 165-204, 1994. | |
| B7 | Hayyan Helal and Gerhard Lakemeyer. Simple Numeric Planning with Two Variables is Decidable. Proc. ECAI 2025, to appear. | |
| C2/D8 | Jörg Hoffmann and Bernhard Nebel. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research, 14, pp. 253-302, 2001. | |
| C2 | Silvia Richter and Matthias Westphal. The LAMA planner: Guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research, 39, pp. 127-177, 2010. | |
| C4 | Jussi Rintanen. Regression for Classical and Nondeterministic Planning. Proc. ECAI 2008, pp. 568-572, 2008. | |
| C6 | Jussi Rintanen, Keijo Heljanko, and Ilkka Niemelä. Planning as satisfiability: parallel plans and algorithms for plan search. Artificial Intelligence, 170(12-13), pp. 1031-1080, 2006. | |
| C8 | David Speck and Malte Helmert. On Performance Guarantees for Symbolic Search in Classical Planning. Proc. ECAI 2025, to appear. | |
| C8 | Álvaro Torralba. Symbolic Search and Abstraction Heuristics for Cost-Optimal Planning. PhD thesis, 2015. | |
| C8 | David Speck, Jendrik Seipp, and Álvaro Torralba. Symbolic Search for Cost-Optimal Planning with Expressive Model Extensions. Journal of Artificial Intelligence Research, 82, pp. 1349–1405, 2025. | |
| D6 | Blai Bonet and Hector Geffner. Planning as Heuristic Search. Artificial Intelligence, 129(1), pp. 5-33, 2001. | |
| D8 | Emil Keyder and Hector Geffner. Heuristics for Planning with Action Costs Revisited. ECAI 2008, pp. 588-592, 2008. | |
| E2 | Jussi Rintanen. An Iterative Algorithm for Synthesizing Invariants. Proc. AAAI 2000, pp. 806-811, 2000. | |
| E2 | Daniel Fišer and Antonín Komenda. Fact-Alternating Mutex Groups for Classical Planning. Journal of Artificial Intelligence Research, 61, pp. 475-521, 2018. | |
| E8 | Stefan Edelkamp. Planning with Pattern Databases. Proc. ECP 2001, pp. 84-90, 2001. | |
| E8 | Patrik Haslum, Blai Bonet and Héctor Geffner. New Admissible Heuristics for Domain-Independent Planning. Proc. AAAI 2005, pp. 1164-1168, 2005. | |
| E8 | Stefan Edelkamp. Automated Creation of Pattern Database Search Heuristics. Proc. MoChArt 2006, pp. 35-50, 2007. | |
| E8 | Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet and Sven Koenig. Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning. Proc. AAAI 2007, pp. 1007-1012, 2007. | |
| E8 | Santiago Franco, Álvaro Torralba, Levi H. S. Lelis and Mike Barley. On Creating Complementary Pattern Databases. Proc. IJCAI 2017, pp. 4302-4309, 2017. | |
| E12 | Klaus Dräger, Bernd Finkbeiner and Andreas Podelski. Directed Model Checking with Distance-Preserving Abstractions. Proc. SPIN 2006, pp. 19-34, 2006. | |
| E12 | Malte Helmert, Patrik Haslum and Jörg Hoffmann. Flexible Abstraction Heuristics for Optimal Sequential Planning. Proc. ICAPS 2007, pp. 176-183, 2007. | |
| E12 | Raz Nissim, Jörg Hoffmann and Malte Helmert. Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning. Proc. IJCAI 2011, pp. 1983-1990, 2011. | |
| E12 | Malte Helmert, Patrik Haslum, Jörg Hoffmann and Raz Nissim. Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces. Journal of the ACM 61 (3), pp. 16:1-63, 2014. | |
| E12 | Silvan Sievers, Martin Wehrle and Malte Helmert. Generalized Label Reduction for Merge-and-Shrink Heuristics. Proc. AAAI 2014, pp. 2358-2366, 2014. | |
| E12 | Gaojian Fan, Martin Müller and Robert Holte. Non-linear merging strategies for merge-and-shrink based on variable interactions. Proc. SoCS 2014, pp. 53-61, 2014. | |
| E12 | Malte Helmert, Gabriele Röger and Silvan Sievers. On the Expressive Power of Non-Linear Merge-and-Shrink Representations. Proc. ICAPS 2014, pp. 106-114, 2015. | |
| E12 | Silvan Sievers and Malte Helmert. Merge-and-Shrink: A Compositional Theory of Transformations of Factored Transition Systems. JAIR 71, pp. 781-883, 2021. | |
| E12 | Silvan Sievers, Florian Pommerening, Thomas Keller and Malte Helmert. Cost-Partitioned Merge-and-Shrink Heuristics for Optimal Classical Planning. Proc. IJCAI 2020, pp. 4152-4160, 2020. |