07 Classical Planning

Question 1

What is planning?

Answer 1

Planning is a type of problem solving in which the agent uses beliefs about actions and their consequences to find a solution plan, where a plan is a sequence of actions that leads from an initial state to a goal state.

Previously described approaches
Planning by search (section 2)
• Atomic representations of states
• Very large number of possible actions
• Needs good domain heuristics to bound search space

Planning by logical reasoning (section 3)
• Hybrid agent can use domain-independent heuristics
• But relies on propositional inference (no variables)
• Model size rises sharply with problem complexity

Neither of these approaches scale directly to industrially significant problems.

Question 2

Factored plan representation

Answer 2

Factored representation of:
• Initial state
• Available actions in a state
• Results of applying actions
• Goal tests

Representation language PDDL (Planning Domain Definition Language)
Developed from early AI planners, e.g. STRIPS, pioneering robot work at Stanford in early 1970’s

Used for classical planning:
Environment is observable, deterministic, finite, static, and discrete

Question 3

PDDL: Representation of states and goals

Answer 3

States are represented by conjunctions of function-free ground literals in first-order logic.

Example: At(Plane1,Melbourne)^ At(Plane2,Sydney).

• *Closed-world assumption**: Any condition not mentioned in a state is assumed to be false.
• *Goal state** - a partially specified state, satisfied by any state that contains the goal conditions. Example goal: At(P lane2, T ahiti).

Question 4

PDDL: Representation of actions

Answer 4

An action schema has three components:
• Action description: Name and parameters (universally quantified variables)
• Precondition: Conjunction of positive literals stating what must be true before action application
• Effect: Conjunction of positive or negative literals stating how situation changes with operator application

Example:

Action(Fly(p, from, to),
PRECOND: At(p, from) ^ Plane(p) ^ Airport(from) ^ Airport(to),
EFFECT: ¬At(p,from) ^ At(p,to))

Question 5

PDDL: How are planning actions applied?

Answer 5

Actions are applicable in states that satisfy its preconditions (by binding variables)
• State: At(P1,JFK) ^ At(P2,SFO) ^ Plane(P1) ^ Plane(P2) ^ Airport(JFK) ^ Airport(SFO)
• Precondition: At(p, f rom) ^ Plane(p) ^ Airport(f rom) ^ Airport(to)
• Binding: p/P1, from/JFK, to/SFO

State after executing action is same as before, except positive effects added (add list) and negative deleted (delete list).

New state: At(P1,SFO) ^ At(P2,SFO) ^ Plane(P1) ^ Plane(P2) ^ Airport(JFK) ^ Airport(SFO)

Question 6

Planning solution

Answer 6

Planning solution
The planned actions that will take the agent from the initial state to the goal state.

Simple version: An action sequence, such that when executed from the initial state, results in a final state that satisfies the goal.

More complex cases: Partially ordered set of actions, such that every action sequence that respects the partial order is a solution

Question 7

Current popular planning approaches

Answer 7

Current popular planning approaches

• Forward state-space search with strong heuristics
• Planning graphs and GRAPHPLAN algorithm
• Partial order planning in plan space
• Planning as Boolean satisfiability (SAT)
• Planning as first-order deduction
• Planning as constraint-satisfaction

Question 8

Forward state-space search

Answer 8

Forward state-space search
• Start in initial state
• Apply actions whose preconditions are satisfied
• Generate successor states by adding/deleting literals
• Check if successor state satisfies goal test

Can be highly inefficient
• All actions are applied, even when irrelevant
• Large branching factor (many possible actions)

Heuristics to guide search are required!

Question 9

Backward state-space search

Answer 9

Backward state-space search

Regression planning:

• Start in goal state
• Apply actions that are relevant and consistent
• Relevant: The action can lead to the goal (adds goal literal)
• Consistent: The action does not undo (delete) a goal literal
• Create predecessor states
• Continue until initial state is satisfied

More efficient, but still requires heuristics. State-space searches can only produce linear plans.

Question 10

Heuristics for planning

Answer 10

Neither forward nor backward search is efficient without a good heuristic, which has to be admissible (i.e. optimistic). Possible heuristics include:

• Adding more edges to the search graph, thereby making it easier to find a solution path, e.g. ignore pre-conditions or ignore delete lists
• Create state abstractions, many-to-one mapping from ground states to abstract ones, solve problem in the abstract space, and map down to ground again

Heuristics generate estimates h(s) for remaining cost of a state that can be used by e.g. A*.

Question 11

State-space search

Answer 11

Forward and backward state search

Question 12

Planning graphs

Answer 12

Planning graphs

A planning graph is a special data structure that can be used as a heuristic in search algorithms or directly in an algorithm that generates a solution plan. Directed graph organized into one level for each time step of plan, where a level contains all literals that may be true at that step. Literals may be mutually exclusive (mutex links). Works only for propositional planning problems (no variables), but action schemas with variables may be converted to this form.

(image:) Alternating state and action layers. Real and “persistence” actions (small rectangles). Mutex links (grey arcs) btw. incompatible states. Graph levels off at S2 (states repeat themselves).

Mutex links (mutual exclusion)
Between two actions:
- Inconsistent effects - one action negates an effect of the other (e.g. Eat(Cake) and persistent Have(Cake))
- Interference - an effect of one action negates a pre-condition of the other (e.g. Eat(Cake) and Have(Cake))
- Competing needs - a pre-condition of one action negates a pre-condition of the other (e.g. Eat(Cake) and Bake(Cake))

Between two states (literals):
• One literal is the negation of the other
• Each possible pair of actions that could achieve the two literals is mutually exclusive

Question 13

GRAPHPLAN algorithm

Answer 13

GRAPHPLAN algorithm

Uses a planning graph to extract a solution to a planning problem. Repeatedly:

• Extend planning graph by one level
• If all goal literals are included non-mutex in level
• Try to extract solution that does not violate any mutex links, by following links backward in graph
• Return solution if successful extraction
• If the graph has leveled off then report failure

Creating planning graph is only of polynomial complexity, but plan extraction is exponential.

Question 14

Partial order planning

Answer 14

Partial order planning in plan space

Each node in the search space corresponds to a (partial) plan. Search starts with empty plan that is expanded progressively until complete plan is found. Search operators work in plan space, e.g. add step, add ordering, etc. The solution is the final plan, the path to it is irrelevant. Can create partially ordered plans.

Question 15

Partial-order plan representation

Answer 15

Partial-order plan representation
A set of steps, where each step is an action (taken from action set of planning problem). Initial empty plan contains just Start (no precondition, initial state as effect) and Finish (goal as precondition, no effects).

A set of step ordering constraints of the form A < B (“A before B”): A must be executed before B.

A set of causal links A – c –> B, “A achieves c for B”: the purpose of A is to achieve precondition c for B; no action is allowed between A and B that negates c.

Set of open preconditions, not achieved by any action yet. The planner must reduce this set to empty set.

Question 16

Protected causal links

Answer 16

Causal links in a partial plan are protected by ensuring that threats (steps that might delete the protected condition) are ordered to come before or after the protected link.

Question 17

POP - Partial Order Planning

Answer 17

POP - Partial Order Planning

Start with initial plan
• Contains Start and Finish steps
• All preconditions of Finish (goals) as open preconditions
• The ordering constraint Start < Finish, no causal links

Repeatedly
• Pick arbitrarily one open precondition c on an action B
• Generate a successor plan for every consistent way of choosing an action A that achieves c
• Stop when a solution has been found, i.e. when there are no open preconditions for any action

Successful solution plan
• Complete and consistent plan the agent can execute
• May be partial, agent may choose arbitrary linearization

(See example: 7.6.4.1)