Participation

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

In the workspace forum you find the Zoom link for the lecture.

Slides

No.TopicDateSlides
A1Organizational Matters16.09.printer
screen
A2What is Planning?16.09.printer
screen
A3Transition Systems and Propositional Logic21.09.printer
screen
A4Planning Tasks23.09.printer
screen
A5Equivalent Operators and Normal Forms28.09.printer
screen
A6Positive Normal Form, STRIPS and SAS+28.09.printer
screen
A7Invariants, Mutexes and Task Reformulation 30.09.printer
screen
A8Computational Complexity of Planning30.09.printer
screen
B1Overview of Classical Planning Algorithms05.10.printer
screen
B2Progression and Regression Search05.10.printer
screen
B3General Regression07.10.printer
screen
B4Practical Issues of regression Search07.10.printer
screen
B5SAT Planning: Core Idea and Sequential Encoding12.10.printer
screen
B6SAT Planning: Parallel Encoding12.10.printer
screen
B7Symbolic Search: Binary Decision Diagrams14.10.printer
screen
B8Symbolic Search: Full Algorithm14.10.printer
screen
C1Delete Relaxation: Relaxed Planning Tasks19.10.printer
screen
C2Delete Relaxation: Properties of Relaxed Planning Tasks19.10.printer
screen
C3Delete Relaxation: Hardness of Optimal Planning & AND/OR Graphs21.10.printer
screen
C4Delete Relaxation: Relaxed Task Graphs21.10.printer
screen
C5Delete Relaxation: hmax and hadd26.10.printer
screen
C6Delete Relaxation: Best Achievers, hFF and Comparison26.10.printer
screen
D1Abstractions: Introduction02.11.printer
screen
D2Abstractions: Formal Definition and Heuristics02.11.printer
screen
D3Abstractions: Additive Abstractions04.11.printer
screen
D4Pattern Databases: Introduction04.11.printer
screen
D5Pattern Databases: Multiple Patterns09.11.printer
screen
D6Pattern Databases: Pattern Selection09.11.printer
screen
D7Merge-and-Shrink: Factored Transition Systems11.11.printer
screen
D8Merge-and-Shrink: Algorithm and Heuristic Properties11.11.

printer
screen

E1Constraints: Introduction16.11.

printer
screen

E2Landmarks: RTG Landmarks & MHS Heuristic16.11.

printer
screen

E3Landmarks: LM-Cut Heuristic18.11.

printer
screen

E4Linear & Integer Programming18.11.

printer
screen

E5Cost Partitioning23.11.

printer
screen

E6Optimal Cost Partitioning23.11.

printer
screen

E7Network Flow Heuristics25.11.

printer
screen

E8Operator Counting25.11.

printer
screen

F1Markov Decision Processes30.11.

printer
screen

F2Bellman Equation & Linear Programming30.11.

printer
screen

F3Policy Iteration02.12

printer
screen

F4Value Iteration02.12

printer
screen

Exercises

No.Due DateFiles
X1(classroom)PDF, virtual-machine-setup.pdf, Vagrantfile
A04.10.PDF
X2(classroom)PDF
X3(classroom)PDF
B18.10.PDF
C01.11.PDF
D15.11.PDF
E29.11PDF
F06.12PDF

Extra Material

TitleFiles
Daniel Fišer and Antonín Komenda. Fact-Alternating Mutex Groups for Classical Planning. Journal of Artificial Intelligence Research, 61, pp. 475-521, 2018.PDF
Tom Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2), pp. 165-204, 1994.PDF
Jussi Rintanen.Regression for Classical and Nondeterministic Planning. Proc. ECAI 2008, pp. 568-572, 2008.PDF
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.PDF
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.PDF
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.PDF
Álvaro Torralba. Symbolic Search and Abstraction Heuristics for Cost-Optimal Planning. PhD thesis, 2015.PDF
Michael Katz, Jörg Hoffmann and Carmel Domshlak. Who Said we Need to Relax All Variables? Proceedings of ICAPS 2013, pp. 126–134, 2013.PDF
Stefan Edelkamp. Planning with Pattern Databases. Proc. ECP 2001, pp. 13-24, 2001.PDF
Stefan Edelkamp. Symbolic Pattern Databases in Heuristic Search Planning. Proc. AIPS 2002, pp. 274-283, 2002.PDF
Patrik Haslum, Blai Bonet and Héctor Geffner. New Admissible Heuristics for Domain-Independent Planning. Proc. AAAI 2005, pp. 1164-1168, 2005.PDF
Stefan Edelkamp. Automated Creation of Pattern Database Search Heuristics. Proc. MoChArt 2006, pp. 121-135, 2007.PDF
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.PDF
Klaus Dräger, Bernd Finkbeiner and Andreas Podelski. Directed Model Checking with Distance-Preserving Abstractions. Proc. SPIN 2006, pp. 19-34, 2006.PDF
Malte Helmert, Patrik Haslum and Jörg Hoffmann. Flexible Abstraction Heuristics for Optimal Sequential Planning. Proc. ICAPS 2007, pp. 176-183, 2007.PDF
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.PDF
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.PDF
Silvan Sievers, Martin Wehrle and Malte Helmert. Generalized Label Reduction for Merge-and-Shrink Heuristics. Proc. AAAI 2014, pp. 2358-2366, 2014.PDF
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.PDF
Silvia Richter, Malte Helmert & Matthias Westphal. Landmarks Revisited. In Proc. AAAI 2008, pp. 975-982, 2008.PDF
Malte Helmert & Carmel Domshlak. Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway? In Proc. ICAPS 2009, pp. 162-169, 2009.PDF
Emil Keyder, Silvia Richter & Malte Helmert: Sound and Complete Landmarks for And/Or Graphs, In Proc. ECAI 2010, pp. 335-340, 2010.PDF
Florian Pommerening, Gabriele Röger & Malte Helmert: Getting the Most Out of Pattern Databases for Classical Planning.In Proc. IJCAI 2013, pp. 2357–2364, 2013.PDF
Blai Bonet: An Admissible Heuristic for SAS+ Planning Obtained from the State Equation. In Proc. IJCAI 2013, pp. 2268–2274, 2013.PDF
Tatsuya Imai and Alex Fukunaga: A Practical, Integer-linear Programming Model for the Delete-relaxation in Cost-optimal Planning. In Proc. ECAI 2014, pp. 459–464, 2014.PDF
Florian Pommerening, Gabriele Röger, Malte Helmert & Blai Bonet: LP-based Heuristics for Cost-optimal Planning. In Proc. ICAPS 2014, pp. 226–234, 2014.PDF