TDDD48 Automated Planning

Teaching Machines to Think

Welcome to the course website!

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.

Update 2025-03-28

The slides are continuously updated for the 2025 iteration. Sessions that have a date in front of them have updated slides already.

Lectures

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

Labs

Labs with a due date are finalized for the 2025 iteration.

Due Date	Material
2025-04-14 8:00 a.m.	Lab 1, Vagrantfile
	Lab 2
	Lab 3
	Lab 4
	Lab 5
	Lab 6
	Lab 7

Exam

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

Here is an example exam, whose solution we will discuss shortly before the exam.

Example planning task

Visualization of an example planning task for a household robot. The robot nees to transport packages between locations in different rooms.

Opportunities in the Machine Reasoning Lab

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