TDDD48 Automated Planning

Spring 2024

Welcome to the course website for TDDD48 Automated Planning!

Automated planning is a central topic in AI that deals with intelligent sequential decision making. It is the task of automatically deciding which sequence of actions needs to be applied to reach a given set of goals. Planning technology is currently used with great success in applications ranging from production lines and elevators to unmanned aerial vehicles (UAVs) and space applications such as the Hubble Space Telescope and the Mars rovers. The aim of this course is to provide a comprehensive view of state-of-the-art planning techniques, as well as hands-on experience in constructing and modeling planning domains to solve specific planning problems.

Lectures

Date Chapter Title Extra Material
2024-03-27 A1 Organizational Matters
2024-03-27 A2 What is Planning?
2024-03-28 A3 Getting to Know a Planner
2024-03-28 B1 Transition Systems and Propositional Logic
2024-03-28 B2 Introduction to Planning Tasks
2024-04-03 B3 Formal Definition of Planning
2024-04-03 C1 Overview of Classical Planning Algorithms
2024-04-05 C2 Progression and Regression Search
2024-04-05 C3 SAT Planning: Core Idea and Sequential Encoding
2024-04-10 C4 Symbolic Search: Binary Decision Diagrams
2024-04-10 C5 Symbolic Search: Full Algorithm
2024-04-12 D1 Delete Relaxation: Relaxed Planning Tasks
2024-04-12 D2 Delete Relaxation: Finding Relaxed Plans
2024-04-17 D3 Delete Relaxation: Relaxed Task Graphs
2024-04-17 D4 Delete Relaxation: hmax and hadd
2024-04-17 D5 Delete Relaxation: Analysis of hmax and hadd
2024-04-17 D6 Delete Relaxation: hFF and Comparison of Heuristics
2024-04-19 E1 Planning Tasks in Finite-Domain Representation
2024-04-19 E2 Invariants and Mutexes
2024-04-19 E3 Abstractions: Introduction
2024-04-24 E4 Abstractions: Formal Definition and Heuristics
2024-04-24 E5 Abstractions: Orthogonality and Additivity
2024-04-24 E6 Pattern Databases
2024-04-26 E7 Merge-and-Shrink: Factored Transition Systems
2024-04-26 E8 Merge-and-Shrink: Algorithm
2024-04-26 E9 Merge-and-Shrink: Strategies and Label Reduction
2024-05-02 F1 Constraints: Introduction
2024-05-02 F2 Landmarks: RTG Landmarks
2024-05-02 F3 Landmarks: Minimum Hitting Set Heuristic
2024-05-02 F4 Landmarks: Cut Landmarks & LM-Cut Heuristic
2024-05-03 F5 Linear & Integer Programming
2024-05-03 F6 Cost Partitioning
2024-05-08 F7 Optimal and General Cost Partitioning
2024-05-08 F8 Post-hoc Optimization
2024-05-15 F9 Network Flow Heuristics
2024-05-15 F10 Operator Counting
2024-05-17 F11 Potential Heuristics
2024-05-17 Z1 Planning the Future

Labs

Due Date Material
2024-04-08 8:00 a.m. Lab 1, Vagrantfile
2024-04-15 8:00 a.m. Lab 2
2024-04-22 8:00 a.m. Lab 3
2024-04-29 8:00 a.m. Lab 4
2024-05-06 8:00 a.m. Lab 5
2024-05-13 8:00 a.m. Lab 6
2024-05-20 8:00 a.m. Lab 7

Exam

You may prepare and use one sheet of A4 paper with notes (using both sides). Other aids such as lecture slides, books, or calculators are not allowed. All electronic devices must be turned off during the exam.

Open positions in Machine Reasoning Lab

MSc and PhD projects: https://mrlab.ai/positions/