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. | Topic | Date | Slides |
|---|---|---|---|
| A1 | Organizational Matters | 16.09. | printer screen |
| A2 | What is Planning? | 16.09. | printer screen |
| A3 | Transition Systems and Propositional Logic | 21.09. | printer screen |
| A4 | Planning Tasks | 23.09. | printer screen |
| A5 | Equivalent Operators and Normal Forms | 28.09. | printer screen |
| A6 | Positive Normal Form, STRIPS and SAS+ | 28.09. | printer screen |
| A7 | Invariants, Mutexes and Task Reformulation | 30.09. | printer screen |
| A8 | Computational Complexity of Planning | 30.09. | printer screen |
| B1 | Overview of Classical Planning Algorithms | 05.10. | printer screen |
| B2 | Progression and Regression Search | 05.10. | printer screen |
| B3 | General Regression | 07.10. | printer screen |
| B4 | Practical Issues of regression Search | 07.10. | printer screen |
| B5 | SAT Planning: Core Idea and Sequential Encoding | 12.10. | printer screen |
| B6 | SAT Planning: Parallel Encoding | 12.10. | printer screen |
| B7 | Symbolic Search: Binary Decision Diagrams | 14.10. | printer screen |
| B8 | Symbolic Search: Full Algorithm | 14.10. | printer screen |
| C1 | Delete Relaxation: Relaxed Planning Tasks | 19.10. | printer screen |
| C2 | Delete Relaxation: Properties of Relaxed Planning Tasks | 19.10. | printer screen |
| C3 | Delete Relaxation: Hardness of Optimal Planning & AND/OR Graphs | 21.10. | printer screen |
| C4 | Delete Relaxation: Relaxed Task Graphs | 21.10. | printer screen |
| C5 | Delete Relaxation: hmax and hadd | 26.10. | printer screen |
| C6 | Delete Relaxation: Best Achievers, hFF and Comparison | 26.10. | printer screen |
| D1 | Abstractions: Introduction | 02.11. | printer screen |
| D2 | Abstractions: Formal Definition and Heuristics | 02.11. | printer screen |
| D3 | Abstractions: Additive Abstractions | 04.11. | printer screen |
| D4 | Pattern Databases: Introduction | 04.11. | printer screen |
| D5 | Pattern Databases: Multiple Patterns | 09.11. | printer screen |
| D6 | Pattern Databases: Pattern Selection | 09.11. | printer screen |
| D7 | Merge-and-Shrink: Factored Transition Systems | 11.11. | printer screen |
| D8 | Merge-and-Shrink: Algorithm and Heuristic Properties | 11.11. | |
| E1 | Constraints: Introduction | 16.11. | |
| E2 | Landmarks: RTG Landmarks & MHS Heuristic | 16.11. | |
| E3 | Landmarks: LM-Cut Heuristic | 18.11. | |
| E4 | Linear & Integer Programming | 18.11. | |
| E5 | Cost Partitioning | 23.11. | |
| E6 | Optimal Cost Partitioning | 23.11. | |
| E7 | Network Flow Heuristics | 25.11. | |
| E8 | Operator Counting | 25.11. | |
| F1 | Markov Decision Processes | 30.11. | |
| F2 | Bellman Equation & Linear Programming | 30.11. | |
| F3 | Policy Iteration | 02.12. | |
| F4 | Value Iteration | 02.12. | |
| G1 | Factored MDPs | 07.12. | |
| G2 | Real-time Dynamic Programming | 07.12. | |
| G3 | Asymptotically Suboptimal Monte-Carlo Methods | 09.12. | |
| G4 | Monte-Carlo Tree Search: Framework | 09.12. | |
| G5 | Monte-Carlo Tree Search Algorithms I | 14.12. | |
| G6 | Monte-Carlo Tree Search Algorithms II | 14.12. |
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. |