07 Classical Planning Flashcards
What is planning?
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.
Factored plan representation
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
PDDL: Representation of states and goals
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).
PDDL: Representation of actions
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))
PDDL: How are planning actions applied?
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)
Planning solution
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
Current popular planning approaches
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
Forward state-space search
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!
Backward state-space search
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.
Heuristics for planning
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*.
State-space search
Forward and backward state search
Planning graphs
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
GRAPHPLAN algorithm
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.
Partial order planning
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.
Partial-order plan representation
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.
Protected causal links
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.
