Participation

Please register for the course to gain access to the Adam workspace.

Lecture Slides

No.TopicDateSlides
A1Organizational Matters18.09.printer
handout
screen
A2What is Planning?18.09.printer
handout
screen
A3Getting to Know a Planner23.09.printer
handout
screen
B1Transition Systems and Propositional Logic23.09.printer
handout
screen
B2Introduction to Planning Tasks25.09.printer
handout
screen
B3Formal Definition of Planning25.09.printer
handout
screen
B4Equivalent Operators and Normal Forms30.09.printer
handout
screen
B5Positive Normal Form and STRIPS30.09.printer
handout
screen
B6Computational Complexity of Planning02.10.printer
handout
screen
C1Overview of Classical Planning Algorithms07.10.printer
handout
screen
C2Progression and Regression Search09.10.printer
handout
screen
C3General Regression09.10.printer
handout
screen
C4SAT Planning: Core Idea and Sequential Encoding14.10.printer
handout
screen
C5SAT Planning: Parallel Encoding14.10.printer
handout
screen
C6Symbolic Search: Binary Decision Diagrams16.10.printer
handout
screen
C7Symbolic Search: Full Algorithm16.10.printer
handout
screen
D1Delete Relaxation: Relaxed Planning Tasks21.10.printer
handout
screen
D2Delete Relaxation: Properties of Relaxed Planning Tasks21.10.printer
handout
screen
D3Delete Relaxation: Finding Relaxed Plans23.10.printer
handout
screen
D4Delete Relaxation: AND/OR Graphs23.10.printer
handout
screen
D5Delete Relaxation: Relaxed Task Graphs28.10.printer
handout
screen
D6Delete Relaxation: hmax and hadd28.10.printer
handout
screen
D7Delete Relaxation: Analysis of hmax and hadd30.10.printer
handout
screen
D8Delete Relaxation: hFF and Comparison of Heuristics30.10.printer
handout
screen
E1Planning Tasks in Finite-Domain Representation04.11.printer
handout
screen
E2Invariants and Mutexes04.11.printer
handout
screen
E3Abstractions: Introduction06.11.printer
handout
screen
E4Abstractions: Formal Definition and Heuristics06.11.printer
handout
screen
E5Abstractions: Additive Abstractions11.11.printer
handout
screen
E6Pattern Databases: Introduction11.11.printer
handout
screen
E7Pattern Databases: Multiple Patterns13.11.printer
handout
screen
E8Pattern Databases: Pattern Selection13.11.printer
handout
screen
E9Merge-and-Shrink: Factored Transition Systems18.11.printer
handout
screen
E10Merge-and-Shrink: Algorithm18.11.printer
handout
screen
E11Merge-and-Shrink: Properties and Shrink Strategies20.11.printer
handout
screen
E12Merge-and-Shrink: Merge Strategies and Label Reduction20.11.
25.11.
printer
handout
screen
E13Merge-and-Shrink: Pruning and Usage in Practise25.11.printer
handout
screen
F1Constraints: Introduction27.11.printer
handout
screen
F2Landmarks: RTG Landmarks27.11.printer
handout
screen
F3Landmarks: Orderings & LM-Count Heuristic02.12.printer
handout
screen
F4Landmarks: Minimum Hitting Set Heuristic02.12.printer
handout
screen
F5Landmarks: Cut Landmarks & LM-Cut Heuristic04.12.printer
handout
screen
F6Linear & Integer Programming04.12.printer
handout
screen

 

Extra Material

No.TitleFiles
B6Tom Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2), pp. 165-204, 1994.PDF
C1/D8Jö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.PDF
C1Silvia Richter and Matthias Westphal. The LAMA planner: Guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research, 39, pp. 127-177, 2010.PDF
C3Jussi Rintanen.Regression for Classical and Nondeterministic Planning. Proc. ECAI 2008, pp. 568-572, 2008.PDF
C5Jussi 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.PDF
C7Álvaro Torralba. Symbolic Search and Abstraction Heuristics for Cost-Optimal Planning. PhD thesis, 2015.PDF
C7David Speck. Symbolic Search for Optimal Planning with Expressive Extensions. PhD thesis, 2022.PDF
D6Blai Bonet and Hector Geffner. Planning as Heuristic Search. Artificial Intelligence, 129(1), pp. 5-33, 2001.PDF
D8Emil Keyder and Hector Geffner. Heuristics for Planning with Action Costs Revisited. ECAI 2008, pp. 588-592, 2008.PDF
E1Jussi Rintanen. An Iterative Algorithm for Synthesizing Invariants. Proc. AAAI 2000, pp. 806-811, 2000.PDF
E2Daniel Fišer and Antonín Komenda. Fact-Alternating Mutex Groups for Classical Planning. Journal of Artificial Intelligence Research, 61, pp. 475-521, 2018.PDF
E8Stefan Edelkamp. Planning with Pattern Databases. Proc. ECP 2001, pp. 13-24, 2001.PDF
E8Patrik Haslum, Blai Bonet and Héctor Geffner. New Admissible Heuristics for Domain-Independent Planning. Proc. AAAI 2005, pp. 1164-1168, 2005.PDF
E8Stefan Edelkamp. Automated Creation of Pattern Database Search Heuristics. Proc. MoChArt 2006, pp. 121-135, 2007.PDF
E8Patrik 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.PDF
E8Santiago Franco, Álvaro Torralba, Levi H. S. Lelis and Mike Barley. On Creating Complementary Pattern Databases. Proc. IJCAI 2017, pp. 4302-4309, 2017.PDF
E13Klaus Dräger, Bernd Finkbeiner and Andreas Podelski. Directed Model Checking with Distance-Preserving Abstractions. Proc. SPIN 2006, pp. 19-34, 2006.PDF
E13Malte Helmert, Patrik Haslum and Jörg Hoffmann. Flexible Abstraction Heuristics for Optimal Sequential Planning. Proc. ICAPS 2007, pp. 176-183, 2007.PDF
E13Raz 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.PDF
E13Malte 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.PDF
E13Silvan Sievers, Martin Wehrle and Malte Helmert. Generalized Label Reduction for Merge-and-Shrink Heuristics. Proc. AAAI 2014, pp. 2358-2366, 2014.PDF
E13Gaojian 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.PDF
E13Malte 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.PDF
E13Silvan Sievers and Malte Helmert. Merge-and-Shrink: A Compositional Theory of Transformations of Factored Transition Systems. JAIR 71, pp. 781-883, 2021.PDF
E13Silvan Sievers, Florian Pommerening, Thomas Keller and Malte Helmert. Cost-Partitioned Merge-andShrink Heuristics for Optimal Classical Planning. Proc. IJCAI 2020, pp. 4152-4160, 2020.PDF