Slides

No.TopicDateSlides
A1Organizational Matters18.09.printer
screen
A2What is Planning?18.09.printer
screen
X1Hands-on 118.09.printer
screen
A3Transition Systems and Propositional Logic23.09.printer
screen
A4Planning Tasks23.09.

printer
screen

A5Equivalent Operators and Normal Forms25.09.

printer
screen

A6Positive Normal Form, STRIPS and SAS+25.09.

printer
screen

A7Invariants, Mutexes and Task Reformulation30.09.

printer
screen

A8Computational Complexity of Planning30.09.

printer
screen

B1Overview of Classical Planning Algorithms02.10.

printer
screen

B2Progression and Regression Search02.10.

printer
screen

X1Hands-on 202.10.printer
screen
B3General Regression07.10.printer
screen
B4Practical Issues of Regression Search07.10.printer
screen
B5SAT Planning: Core Idea and Sequential Encoding09.10.printer
screen
B6SAT Planning: Parallel Encoding09.10.printer
screen
B7Symbolic Search: Binary Decision Diagrams14.10.printer
screen
B8Symbolic Search: Full Algorithm14.10.printer
screen
C1Delete Relaxation: Relaxed Planning Tasks16.10.printer
screen
C2Delete Relaxation: Properties of Relaxed Planning Tasks16.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 hadd23.10.printer
screen
C6Delete Relaxation: Best Achievers, hFF and Comparison23.10.printer
screen
D1Abstractions: Introduction28.10.printer
screen
D2Abstractions: Formal Definition and Heuristics28.10.printer
screen
D3Abstractions: Additive Abstractions30.10.printer
screen
D4Pattern Databases: Introduction30.10.printer
screen
D5Pattern Databases: Multiple Patterns04.11.printer
screen
D6Pattern Databases: Pattern Selection04.11.printer
screen
D7Merge-and-Shrink: Factored Transition Systems06.11.printer
screen
D8Merge-and-Shrink: Algorithm and Heuristic Properties06.11.printer
screen
E1Constraints: Introduction11.11.printer
screen
E2Landmarks: RTG Landmarks & MHS Heuristic11.11.printer
screen
E3Landmarks: LM-cut Heuristic13.11.printer
screen
E4Linear & Integer Programming13.11.printer
screen
E5Cost Partitioning18.11.printer
screen
E6Optimal Cost-Partitioning18.11.printer
screen
E7Post-hoc Optimization20.11.printer
screen
E8Network Flow Heuristics20.11.printer
screen
E9Operator Counting25.11.printer
screen
E10Potential Heuristics25.11.printer
screen
F1Markov Decision Processes27.11.printer
screen
F2Bellman Equation & Linear Programming27.11.printer
screen
F3Policy Iteration02.12.printer
screen
F4Value Iteration02.12.printer
screen
G1Factored MDPs04.12.printer
screen
G2AO* & LAO*04.12.printer
screen
G3Real-time Dynamic Programming09.12.printer
screen
G4Heuristics for Probabilistic Planning09.12.printer
screen
G5Asymptotically Suboptimal Monte-Carlo Methods11.12.printer
screen
G6Monte-Carlo Tree Search: Framework11.12.printer
screen
G7Monte-Carlo Tree Search Algorithms (Part I)16.12.printer
screen
G8Monte-Carlo Tree Search Algorithms (Part II)16.12.printer
screen

Exercises

No.Due DateFiles
X1(classroom)PDF, Vagrantfile
A06.10.PDF
B20.10.PDF
C27.10.PDF
D10.11.PDF
E01.12.PDF
F08.12.PDF
G15.12.PDF

Extra Material

TitleFiles
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 Hoffman 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
Emil Keyder and Héctor Geffner. Heuristics for Planning with Action Costs Revisited. Proc. ECAI 2008, pp. 588-592, 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
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
Richter, Helmert & Matthias Westphal. Landmarks Revisited. In Proc. AAAI 2008, pp. 975-982, 2008.PDF
Helmert & Domshlak. Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway? In Proc. ICAPS 2009, pp. 162-169, 2009.PDF
Keyder, Richter & Helmert: Sound and Complete Landmarks for And/Or Graphs, In Proc. ECAI 2010, pp. 335-340, 2010.PDF