University of Basel

Department of
Mathematics and Computer Science

Participation

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

Lecture Slides

No.TopicDateSlides
A1Organizational Matters20.09.printer
screen
A2What is Planning?20.09.printer
screen
A3Getting to Know a Planner25.09.printer
screen
B1Transition Systems and Propositional Logic25.09.printer
screen
B2Introduction to Planning Tasks27.09.printer
screen
B3Formal Definition of Planning27.09.printer
screen
B4Equivalent Operators and Normal Forms02.10.printer
screen
B5Positive Normal Form and STRIPS02.10.printer
screen
B6Computational Complexity of Planning04.10.printer
screen
C1Overview of Classical Planning Algorithms04.10.printer
screen
C2Progression and Regression Search09.10.printer
screen
C3General Regression09.10.printer
screen
C4SAT Planning: Core Idea and Sequential Encoding11.10.printer
screen
C5SAT Planning: Parallel Encoding11.10.printer
screen
C6Symbolic Search: Binary Decision Diagrams16.10.printer
screen
C7Symbolic Search: Full Algorithm16.10.printer
screen
D1Delete Relaxation: Relaxed Planning Tasks18.10.printer
screen
D2Delete Relaxation: Properties of Relaxed Planning Tasks18.10.printer
screen
D3Delete Relaxation: Finding Relaxed Plans23.10.printer
screen
D4Delete Relaxation: AND/OR Graphs23.10.printer
screen
D5Delete Relaxation: Relaxed Task Graphs25.10.printer
screen
D6Delete Relaxation: hmax and hadd25.10.printer
screen
D7Delete Relaxation: Analysis of hmax and hadd30.10.printer
screen
D8Delete Relaxation: hFF and Comparison of Heuristics30.10.printer
screen
E1Planning Tasks in Finite-Domain Representation01.11.printer
screen
E2Invariants and Mutexes01.11.printer
screen
E3Abstractions: Introduction06.11.printer
screen
E4Abstractions: Formal Definition and Heuristics06.11.printer
screen
E5Abstractions: Additive Abstractions08.11.printer
screen
E6Pattern Databases: Introduction08.11.printer
screen
E7Pattern Databases: Multiple Patterns13.11.printer
screen
E8Pattern Databases: Pattern Selection13.11.printer
screen
E9Merge-and-Shrink: Factored Transition Systems15.11.printer
screen
E10Merge-and-Shrink: Algorithm15.11.printer
screen
E11Merge-and-Shrink: Properties and Shrink Strategies20.11.printer
screen
E12Merge-and-Shrink: Merge Strategies and Label Reduction 20/22.11.printer
screen
E13Merge-and-Shrink: Pruning and Usage in Practise22.11.printer
screen
F1Critical Path Heuristics: hm27.11.printer
screen
F2Critical Path Heuristics: Properties and Πm Compilation27.11.printer
screen
G1Constraints: Introduction29.11.printer
screen
G2Landmarks: RTG Landmarks29.11.printer
screen
G3Landmarks: Orderings and LM-Count Heuristic04.12.printer
screen
G4Landmarks: Minimum Hitting Set Heuristic04.12.printer
screen
G5Landmarks: Cut Landmarks & LM-Cut Heuristic06.12.printer
screen
G6Linear & Integer Programming06.12.printer
screen
G7Cost Partitioning11.12.printer
screen
G8Optimal and General Cost-Partitioning11.12.printer
screen
G9Post-hoc Optimization13.12.printer
screen
G10Network Flow Heuristics13.12.printer
screen
G11Operator Counting18.12.printer
screen
G12Potential Heuristics18.12.printer
screen

 

Exercises

No.Due DateFiles
X1(classroom)PDF, Vagrantfile
01October 02PDF
02October 09PDF
03October 16PDF, ex3.3
04October 23PDF
05November 06PDF
06November 13PDF
07November 20PDF
08November 27PDF
09December 04PDF
10December 11PDF
11December 18PDF

 

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
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
E8Stefan Edelkamp. Symbolic Pattern Databases in Heuristic Search Planning. Proc. AIPS 2002, pp. 274-283, 2002.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
F2Patrik Haslum and Hector Geffner. Admissible Heuristics for Optimal Planning. Proc. AIPS 2000, pp.140-149, 2000.PDF
F2Patrik Haslum. hm(P) = h1(Pm): Alternative Characterisations of the Generalisation From hmax to hm. Proc. ICAPS 2009, pp. 354-357, 2009.PDF
F2Patrik Haslum. Incremental Lower Bounds for Additive Cost Planning Problems. Proc. ICAPS 2012, pp. 74-82, 2012.PDF
F2Emil Keyder, Jörg Hoffmann and Patrik Haslum. Improving Delete Relaxation Heuristics Through Explicitly Represented Conjunctions. JAIR 50, pp. 487-533, 2014.PDF
To top