Lernzettel: Planning I — Classical Planning
Methods of AI — SoSe 2026 · 1-page exam sheet
For more depth: STRIPS (full merged hub: 3 problems, Sit. Calc., STRIPS, PDDL, heuristics, algorithms with pseudocode) · quiz_planning_30-04-26 (covers Planning I + II) · sibling: lernzettel_planning-ii_30-04-26 (MDP)
Core Ideas
- Planning = find a sequence of actions transforming an initial state into a goal state (fully observable, deterministic, static).
- Unlike local search (don’t care about path) or classical search (opaque states): planning exploits the internal structure of states (sets of properties).
- Three challenges: Frame, Qualification, Ramification.
- Two classical formalisms (lecture): Situation Calculus (deductive/logical) and STRIPS (state-based). PDDL = modern STRIPS extension. (MDPs → Planning II.)
Mini-glossary
| Term | Meaning |
|---|---|
| Frame problem | How to efficiently represent what does not change after an action |
| Qualification problem | Actions may have endless preconditions we can’t enumerate |
| Ramification problem | Actions may have unintended side-effects |
| Fluent | Predicate that changes over time; in Sit. Calc. carries an extra S arg |
| Situation | Term in Sit. Calc.; atomic (S1) or complex (put(A,B,S₁)) |
| PRE / ADD / DEL | STRIPS operator: preconditions / atoms to add / atoms to remove |
| CWA | Closed-World Assumption — atoms not in the state are false (STRIPS yes, Sit. Calc. no) |
| Effect axiom | Sit. Calc.: describes what becomes true after an action |
| Frame axiom | Sit. Calc.: describes what stays unchanged (≈ O(actions × fluents) of them) |
| Ignore-PRE-DEL | Heuristic: drop PRE & DEL → set-cover (NP-hard, not admissible) |
| Ignore-DEL | Heuristic: drop only DEL → no op undoes goals (NP-hard, not admissible) |
⚠️ Frame ≠ Qualification ≠ Ramification — most-confused trio. Have one concrete example per problem ready.
Formulas / Notation
| Symbol | Meaning |
|---|---|
Fluent(args, S) | Time-varying predicate in situation S |
put(X, Y, S) | Lecture’s situation term (not R&N’s do(a,S)) |
PRE(o) ⊆ s | STRIPS applicability |
s' = (s \ DEL(o)) ∪ ADD(o) | STRIPS state update |
G ⊆ s | STRIPS goal test |
(:requirements :strips :typing) | PDDL flags actually used in slides |
Common Exam Traps ⚠️
- Frame ≠ Qualification ≠ Ramification. Know each by an example.
- STRIPS uses CWA; Situation Calculus does not.
- STRIPS “solves” the frame problem only by convention — it doesn’t dissolve it. Sit. Calc. pays explicitly via O(actions × fluents) frame axioms.
- DEL contains positive atoms that will be removed; don’t write
¬clear(B)into ADD. - Ignore-PRE-DEL and Ignore-DEL are NOT admissible → A* loses optimality guarantee.
- Lecture writes
put(A,B,S₁), not R&N’sdo(a, S). - PDDL in the slides =
:strips,:typing, numeric fluents, derived predicates.:adl, conditional effects, action costs, durative actions are NOT lecture material. - Plan-space search (POP) is NOT in the slides — only forward / backward state-space search.
- “Syntactic vs. ontological” frame-problem framing is external philosophy of AI — not the lecture’s framing.
- PSPACE-completeness of classical planning is R&N background, not in the lecture.
Quick Comparison Table
| Formalism | State rep. | Frame problem | CWA? | Planner |
|---|---|---|---|---|
| Situation Calculus | Logical fluents (FOL) | Explicit frame axioms (O(actions × fluents)) | No | Theorem prover |
| STRIPS | Set of ground atoms | Implicit (only DEL changes things) | Yes | Classical state-space search |
| PDDL | STRIPS + types + numeric fluents + derived predicates | Implicit (inherits STRIPS convention) | Yes | Modern classical planners (IPC) |
Related Q&A & Notes
Quiz
- quiz_planning_30-04-26 — 8 Qs (Planning I + II)
Targeted exam questions in Questions for Methods of AI
- Q30–39 (basics: Sit. Calc., STRIPS, PDDL) · Q86 (Frame/Qualification/Ramification) · Q98 (Fluents) · Q99 (PDDL) · Q114–116 (deep / exam-trap: STRIPS and the Frame Problem)
Atomic notes
- Why an an AI struggles with Planning · Frame Problem · Situation Calculus · STRIPS · PDDL and STRIPS
See also
Tags: methods-of-ai lernzettel planning ai-generated
Full reference: STRIPS (merged hub — formerly planning-i_30-04-26)
Quiz: quiz_planning_30-04-26
Sibling: lernzettel_planning-ii_30-04-26
Superlink: Methods of AI Lecture
Questions hub: Questions for Methods of AI
Created: 30/04/26