Participation
Please register for the course to gain access to the Adam workspace. There you find the Zoom link for the live meetings.
We will teach the course as flipped classroom with prerecorded lectures, an online exercise on Monday and an online plenary meeting on Wednesday. We will present the details in the first meeting on Sep. 22.
Slides
| No. | Topic | Study until | Slides |
|---|---|---|---|
| A1 | Organizational Matters | 22.09. | printer screen |
| A2 | What is Planning? | 22.09. | printer screen |
| A3 | Transition Systems and Propositional Logic | 03.10. | printer screen |
| A4 | Planning Tasks | 03.10. | printer screen |
| A5 | Equivalent Operators and Normal Forms | 10.10. | printer screen |
| A6 | Positive Normal Form, STRIPS and SAS+ | 10.10. | printer screen |
| A7 | Invariants, Mutexes and Task Reformulation | 10.10. | printer screen |
| A8 | Computational Complexity of Planning | 10.10. | printer screen |
| B1 | Overview of Classical Planning Algorithms | 17.10. | printer screen |
| B2 | Progression and Regression Search | 17.10. | printer screen |
| B3 | General Regression | 17.10. | printer screen |
| B4 | Practical Issues of Regression Search | 17.10. | printer screen |
| B5 | SAT Planning: Core Ideas and Sequential Encoding | 24.10. | printer screen |
| B6 | SAT Planning: Parallel Encoding | 24.10. | printer screen |
| B7 | Symbolic Search: Binary Decision Diagrams | 24.10. | printer screen |
| B8 | Symbolic Search: Full Algorithm | 24.10. | printer screen |
| C1 | Delete Relaxation: Relaxed Planning Tasks | 31.10. | printer screen |
| C2 | Delete Relaxation: Properties of Relaxed Planning Tasks | 31.10. | printer screen |
| C3 | Hardness of Optimal Planning & AND/OR Graphs | 31.10. | printer screen |
| C4 | Delete Relaxation: Relaxed Task Graphs | 31.10. | printer screen |
| C5 | Delete Relaxation: hmax and hadd | 07.11. | printer screen |
| C6 | Delete Relaxation: Best Achievers, hFF and Comparison | 07.11. | printer screen |
| D1 | Abstractions: Introduction | 07.11. | printer screen |
| D2 | Abstractions: Formal Definition and Heuristics | 07.11. | printer screen |
| D3 | Abstractions: Additive Abstractions | 14.11. | printer screen |
| D4 | Pattern Databases: Introduction | 14.11. | printer screen |
| D5 | Pattern Databases: Multiple Patterns | 14.11. | printer screen |
| D6 | Pattern Databases: Pattern Selection | 14.11. | printer screen |
| D7 | Merge-and-Shrink: Factored Transition Systems | 21.11. | printer screen |
| D8 | Merge-and-Shrink: Algorithm and Heuristic Properties | 21.11. | printer screen |
| E1 | Constraints: Introduction | 21.11. | |
| E2 | Landmarks: RTG Landmarks & MHS Heuristic | 21.11. | |
| E3 | Landmarks: LM-Cut Heuristic | 28.11. | |
| E4 | Linear & Integer Programming | 28.11. | |
| E5 | Cost Partitioning | 28.11. | |
| E6 | Optimal Cost Partitioning | 05.12. | |
| E7 | Network Flow Heuristics | 05.12. | |
| E8 | Operator Counting | 05.12. | |
| F1 | Markov Decision Processes | 05.12. | |
| F2 | Bellman Equation & Linear Programming | 12.12. | |
| F3 | Policy Iteration | 12.12. | |
| F4 | Value Iteration | 12.12. | |
| F5 | Factored MDPs | 12.12. | |
| F6 | Real-time Dynamic Programming | 12.12. | |
| F7 | Monte-Carlo Tree Search: Framework | 19.12. | printer screen |
| F8 | MCTS: Algorithms I | 19.12. | printer screen |
| F9 | MCTS: Algorithms II | 19.12. | printer screen |
Exercises
| No. | Due Date | Files |
|---|---|---|
| Z | September 26 | PDF, virtual-machine-setup.pdf, Vagrantfile |
| A | October 14 | PDF, pddl-intro.pdf |
| B | October 28 | |
| C | November 11 | |
| D | November 25 | |
| E | December 9 | |
| F | December 16 | |
| X | December 21 |
Extra Material
| Title | Files |
|---|---|
| Daniel Fišer and Antonín Komenda. Fact-Alternating Mutex Groups for Classical Planning. Journal of Artificial Intelligence Research, 61, pp. 475-521, 2018. | |
| Tom Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2), pp. 165-204, 1994. | |
| Jussi Rintanen.Regression for Classical and Nondeterministic Planning. Proc. ECAI 2008, pp. 568-572, 2008. | |
| 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. | |
| 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. | |
| 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. | |
| Álvaro Torralba. Symbolic Search and Abstraction Heuristics for Cost-Optimal Planning. PhD thesis, 2015. | |
| Michael Katz, Jörg Hoffmann and Carmel Domshlak. Who Said we Need to Relax All Variables? Proceedings of ICAPS 2013, pp. 126–134, 2013. | |
| Stefan Edelkamp. Planning with Pattern Databases. Proc. ECP 2001, pp. 13-24, 2001. | |
| Stefan Edelkamp. Symbolic Pattern Databases in Heuristic Search Planning. Proc. AIPS 2002, pp. 274-283, 2002. | |
| Patrik Haslum, Blai Bonet and Héctor Geffner. New Admissible Heuristics for Domain-Independent Planning. Proc. AAAI 2005, pp. 1164-1168, 2005. | |
| Stefan Edelkamp. Automated Creation of Pattern Database Search Heuristics. Proc. MoChArt 2006, pp. 121-135, 2007. | |
| 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. | |
| Klaus Dräger, Bernd Finkbeiner and Andreas Podelski. Directed Model Checking with Distance-Preserving Abstractions. Proc. SPIN 2006, pp. 19-34, 2006. | |
| Malte Helmert, Patrik Haslum and Jörg Hoffmann. Flexible Abstraction Heuristics for Optimal Sequential Planning. Proc. ICAPS 2007, pp. 176-183, 2007. | |
| 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. | |
| 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. | |
| Silvan Sievers, Martin Wehrle and Malte Helmert. Generalized Label Reduction for Merge-and-Shrink Heuristics. Proc. AAAI 2014, pp. 2358-2366, 2014. | |
| 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. | |
| Silvia Richter, Malte Helmert & Matthias Westphal. Landmarks Revisited. In Proc. AAAI 2008, pp. 975-982, 2008. | |
| Malte Helmert & Carmel Domshlak. Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway? In Proc. ICAPS 2009, pp. 162-169, 2009. | |
| Emil Keyder, Silvia Richter & Malte Helmert: Sound and Complete Landmarks for And/Or Graphs, In Proc. ECAI 2010, pp. 335-340, 2010. | |
| 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. | |
| Blai Bonet: An Admissible Heuristic for SAS+ Planning Obtained from the State Equation. In Proc. IJCAI 2013, pp. 2268–2274, 2013. | |
| 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. | |
| Florian Pommerening, Gabriele Röger, Malte Helmert & Blai Bonet: LP-based Heuristics for Cost-optimal Planning. In Proc. ICAPS 2014, pp. 226–234, 2014. |