TDDD48-2022 Reading Instructions

The main literature for this course is the book Automated Planning: Theory and Practice by Malik Ghallab, Dana Nau and Paolo Traverso. The current printing of the book contains a number of errors – please check the errata list! We may also provide additional references for specific topics.

Some of the material discussed in the book will also be covered during the lectures. However, some of the essential issues discussed in the book are more suitable for reading at your own pace. Lectures are a complement to the book, not a replacement!

At the same time, you should be aware that the lectures cover some topics that are not discussed in the book.

Focus on understanding

Understanding terminology and basic notation is essential. Remembering the more esoteric functions defined in the book is less essential. Here are a few examples illustrating this focus.

• Notation: You must be able to read and understand basic notation such as γ(s,a) for the state transition function and S for the set of states in a state transition system. These symbols are used in many places throughout the book and will also been used during the lectures. You must also understand the concept of reachable states, but you do not necessarily have to remember the notation Γ^{^}(s), since this is less commonly used and not as central to your understanding.

• You must understand and be able to explain the general structure of a state transition system and its components (states, actions, transition function). However, you don't necessarily have to remember if the transition system is defined as Σ=(S,A,γ) or Σ=(A,S,γ).

• You should understand the various restrictions we place on the state transition system for classical planning (A0-A7), so that if you are asked whether classical planning allows (for example) non-deterministic actions, you know the answer. You don't have to be able to enumerate the restrictions by heart.

Though we focus less on formal notation, you still need to be able to clearly demonstrate what you have understood. For example, if you are asked to explain a particular heuristic such as landmark heuristics, your explanation should be sufficiently detailed, coherent and comprehensible that (a) someone who is not familiar with the area easily understands the main issues involved, and (b) someone familiar with the area sees that you have understood the critical characteristics of the method. It should be possible to apply the explanation to a simple example and see how it works. As long as you can do this, being able to write down the exact definition of an algorithm in the book from memory in pseudo-code is less important!

Reading Instructions

What are you expected to learn? As in any course, it is naturally impossible to give you an exact definition of the relative importance of every issue covered in the book. However, we can still give you some general guidelines through the reading instructions below.

In addition to the chapter and section numbes, the reading instructions include some examples of what we focus on in particular. These are only examples, not an exhaustive list of everything you need to know in each chapter.

• Chapter 1: Introduction and Overview.
  Appendix A: Search Procedures and Computational Complexity.
  Appendix B: First-Order Logic.
  The first chapter provides a useful introduction to various forms of planning. Reading it will help you understand the remainder of the book.

  Also, please take a look at Appendixes A and B to ensure that you have the basic prerequisites for taking this course. In particular, sections A.1, A.2 and B.[1-3] are essential.

• Chapter 2: Representations for Classical Planning.
  We will mostly be using the classical and state-variable representations. A basic understanding of the set-theoretic representation (2.2) may also be useful in order to fully understand the properties of the other representations, but we will not actually be using this representation.

  You must understand these representations to the extent that you can use them to model various planning problems, and understand planning problems modeled in classical or state-variable representations. You must obviously also understand those fundamental concepts that have also been discussed during the lectures, such as states, reachable states, effects, preconditions, applicable actions and so on.

  Again, notatation is less important than understanding concepts. You do have to understand common notation that has been used in the lectures, such as γ(s,a), π, S=(Σ,s0,g), and so on. If we use less common notation, such as Γ(s) [page 22], it will be briefly explained: The exam will remind you that "Γ(s) is the set of all successors of s", or "Γ^-1(g) is defined as { γ^-1(g,a) | a is relevant for g }". You will still have to understand the concepts "successor", "relevant action for a goal", and so on.

  Section 2.4 can be quite interesting but is not included in the course, except to the extent that anything in that section is also discussed during the lectures.

• Chapter 3: Complexity of Classical Planning.
  Formal complexity analysis is no longer part of the course.

• Chapter 4: State-Space Planning.
  Chapter 5: Plan-Space Planning.
  These chapters provide a number of fundamental concepts used in a very large number of planners, and are consequently very important for your understanding of the material in the remainder of the course.

  Lifted versions of planning are also included in the course, to the extent that they are included in the lectures.

  Section 4.4, on STRIPS, is not included. Sections 5.4.2, on the PoP procedure, and 5.5, on extensions to partial-order planning, are not included. You will not be asked to prove properties such as soundness or completeness.

• Chapter 6: Planning-Graph Techniques.
  You do not need to know general planning graph techniques. However, you do need to understand the application of planning graphs in Relaxed Planning Graph heuristics as discussed during the lectures.

• Chapter 7: Propositional Satisfiability Techniques.
  This is no longer part of the course.

• Chapter 8: Constraint Satisfaction Techniques.
  Not included in the course.

• Chapter 9: Heuristics in Planning.
  Heuristics are a very important concept that should be understood in detail for state-space planning. We do not focus on heuristics for plan-space planning, though understanding something about this may help you better understand heuristics in general (so it's useful to read the introduction to Part III carefully).

  For example, you need to understand the concept of relaxation and to distinguish between different types of relaxation. You need to understand how forward search can benefit from the use of heuristics. Understanding this in the context of backward search is also useful, but as it has not been extensively discussed during the lectures, it will not be part of the exam.

  Section 9.3.2 is not included.

  The particular heuristic functions defined in Section 9 are not included, except if they are also discussed during the lectures. For example, you no longer need to understand how the h_m heuristics work. These have been replaced with newer heuristics in the lectures.

  Section 9.4 is not included.

• Chapter 10: Control Rules in Planning.
  

  This chapter is not included during 2023; we are instead focusing on Hierarchical Task Network planning.

• Chapter 11: Hierarchical Task Network Planning.
  

  Sections 11.4-11.8 are not included.

• Chapter 12: Control Strategies in Deductive Planning.
  Not included in the course.

• Chapter 13: Time for Planning.
  Chapter 14: Temporal Planning.
  Chapter 15: Planning and Resource Scheduling.
  Not included in the course.

• Chapter 16: Planning Based on Markov Decision Processes.
  Chapter 17: Planning Based on Model Checking.
  Appendix C: Model Checking.
  Chapter 18: Uncertainty with Neoclassical Techniques.

  Sections 16.1 and 16.2 are included in the course. Sections 16.3 and 16.4 are not included.

  You should be able to apply policy iteration and value iteration to a simple problem instance.

  Chapter 17 and the associated Appendix C are not included.

  Chapter 18 is not included.

• Chapter 19: Space Applications.
  Chapter 21: Planning for Manufacturability Analysis.
  Chapter 22: Emergency Evacuation Planning.
  Chapter 23: Planning in the Game of Bridge.
  These chapters are not included in the course, but provide an interesting view of different ways in which automated planning can be applied to solve real-world problems.

• Chapter 20: Planning in Robotics.
  Section 20.2, covering path and motion planning, is included in the course. The course slides on path planning are of course also included.

• Chapter 24: Other Approaches to Planning.
  This chapter provides a high-level overview of various important aspects of planning and is part of the course to the extent that you should be aware of the issues discussed in the chapter. There will be no exam questions specifically on this material.

Page responsible: Jonas Kvarnstr�m
Last updated: 2023-04-25