Transcript presentation source

Roots of planning


problem solving through state-space
search
software agents (e.g. robotics)
EXAMPLE: “Shakey” (pg. 360)
 a robot that roamed the halls of SRI in
the early 1970’s
 actions were based on plans
The Problem
Find a sequence of actions that achieves
a given goal when performed starting in
a given state.
START
Initial State
Operator
Instances
Goal
State
FINISH
PLAN
A Simple Planning Agent
plans ahead before acting (ch3)
selects actions based on explicit,
logical representations of the
current state and the effects of
actions (ch6)
agent uses beliefs about actions
and their consequences to
search for a solution over a
space of plans rather than a
space of situations
A Simple Planning Agent
Algorithm: (pg. 338)
1. Generate a goal to achieve
2. Construct a plan to achieve goal from
current state
3. Execute plan until finished
4. Begin again with new goal
A Simple Planning Agent

Assumptions:
– Atomic time
– no concurrent actions allowed
– deterministic actions
– agent is the sole cause of change in the
world
– agent is omniscient
– Closed World Assumption
“The Blocks World”
Domain:
– set of cubic blocks sitting on
a table
Actions:
– blocks can be stacked
– can pick up a block and
move it to another position
– can only pick up one block
at a time
Goal:
– to build a specified stack of
blocks
A
C
B
INITIAL STATE
A
C
B
GOAL STATE
So what’s the difference?
Problem-Solving:
(State-space search)




representation of actions,
states, goals, plans
actions are represented by a
program that generates
complete state descriptions
“black box”
unbroken sequences of
actions beginning from the
initial state to the goal state
Planning:
(Situation Calculus)



“open up” the representation
of states, goals, and actions
planner is free to add actions
to the plan wherever they
are needed
most parts of the world are
independent of most other
parts -> divide and conquer
Important Points


Planning agents use
lookahead
Planning agents differ from
problem-solving agents
– use of more flexible
representations of states,
actions, goals, and plans
Situation Calculus

Augment FOL so that it can reason
about actions in time
– Add situation variables to specify time
– Add predicate holds(f,s)
– Add function result(a,s)

Example: agent-walks-to-location-y
("x)("y)("s)(at(Agent,x,s)) =
at(Agent,y,result(walk(y),s))
Situation Calculus


You must also specify what doesn’t
change!
Example: agent-walks-to-location-y
– ("x)("y)("s)(at(Agent,x,s)) =
at(Agent,y,result(walk(x,y),s))
– ("x)("y)("s)(at(Bananas,x,s)) =
at(Bananas,x,result(walk(x,y),s))
Practical Planning


Restrict the language with which we
define problems
Use a special-purpose algorithm called
a planner rather
Important Points


A planning problem is
represented in situation
calculus by logical
sentences
Planning by unguided
logical inference is
inefficient and gives no
guarantees about the
resulting plan
Representing States & Goals

STRIPS:
– describes states & operators in a restricted
language

States:
– a conjunction of “facts” (ground literals that
do not contain variable symbols)

Goals:
– a conjunction of positive literals
Representing States & Goals
C
Initial State:
ontable(A) L
ontable(B) L
on(C, B) L
clear(A) L
clear(C) L
handempty
Goal:
ontable(B) L
on(C,B) L
on(A,C) L
clear(A) L
handempty
A
B
INITIAL STATE
A
C
B
GOAL STATE
Representing Actions
1. Action description
Name: pickup(x)
2. Precondition
Preconditions: ontable(x), clear(x), handempty
3. Effect
Effect: holding(x), ~ontable(x), ~clear(x),
~handempty
Actions in “Blocks World”

pickup(x)
– picks up block ‘x’
from table

stack(x,y)
– if holding block ‘x’,
puts it on top of
block ‘y’

putdown(x)
– if holding block ‘x’,
puts it down on table

unstack(x,y)
– picks up block ‘x’ that
is currently on
block ‘y’
An operator is APPLICABLE if all preconditions are
satisfied.
Important Points

The STRIPS language
describes actions in terms
of their preconditions and
effects. It captures much of
the expressive power of
situation calculus, but not
all domains and problems
can be described in the
STRIPS language
Planning as Search

putdown(A)
Situation Space
– start at initial
state, apply
operators until
reached goal
(e.g. searching)
stack(A,C)
pickup(A)
...
Start
Finish
putdown(C)
unstack(C,B)
stack(C,A)
stack(C,B)
See Figure 11.2 (pg. 340)
Start

Plan Space
– search through a
space of plans
handempty
pickup(A)
holding(A)
stack(A,C)
on(A,C)
Finish
See Figure 11.5 (pg. 348)
Situation-Space Planners

Progression
– Forward chaining from initial state to goal
state

Regression
– Backward chaining from goal state to initial
state
Progression Situation Space



Like a state-space search except
STRIPS operators specified instead a
set of next-move functions
Use any search method you like (e.g.
BFS, DFS, A*)
PROBLEM:
– huge search space to explore, so usually
very inefficient
Progression Situation-Space
Algorithm:
1. Start from initial state
2. Find all operators whose
preconditions are true in
the initial state
3. Compute effects of
operators to generate
successor states
4. Repeat steps 2-3, until a
new state satisfies the
goal conditions
C
A
B
INITIAL STATE
A
C
B
GOAL STATE
Important Points

There are 2 approaches to
solving planning problems:
– situation-space planners
– plan-space planners

Progression is one type of
situation-space planners
Regression Situation-Space

Usually more efficient than progression
– progression: many operators are
applicable at each state
– regression: only a small number of
operators are applicable for achieving a
given goal

PROBLEM:
– cannot always find a plan even if one
exists!
Regression Situation-Space
Algorithm:
1. Start with goal node
corresponding to goal to
be achieved
2. Choose an operator that
will add one of the goals
3. Replace that goal with
the operator’s
preconditions
4. Repeat steps 2-3 until
you have reached the
initial state
C
A
B
INITIAL STATE
A
C
B
GOAL STATE
Important Points

Regression is the second
type of situation-space
planner

It is more efficient than
progression
Where Situation-Space fails…


If the order of solving a set of goals fails
because solving a later goal undoes an
earlier goal
Does not allow for interleaving of steps
in any solution it finds
“Sussman Anomaly”

Solving on(A,B) first will be undone
when solving the second goal on(B,C)
and vice versa.
B
C
A
INITIAL STATE
A
B
C
GOAL STATE
Plan-Space Planners



Use when ordering of sub-goals matters
Make commitments only as necessary
Least Commitment planning:
– never making a choice unless required to
do so
• Advantage: don’t have to backtrack later!
Important Points


Use situation space
planners when goals are
not interleaved
Use plan space planners
when goals are interleaved
– the ordering of goals affects
the outcome
Definition of a plan

A plan is formally defined as a data structure
consisting of the following 4 components:
–
–
–
–
A set of plan steps
A set of step ordering constraints
A set of variable binding constraints
A set of causal links
Plan(STEPS:{S1:Op(ACTION: Start),
S2:Op(ACTION: Finish,
PRECOND: On(c, table)  On(b,c)  On(a,b) },
ORDERINGS: {S1 < S2},
BINDINGS: {},
LINKS: {})
Representation for Plans
Partial Order Plans:
 can represent plans
in which some steps
are ordered with
respect to each
other and other
steps are unordered
Total Order Plans:
 plans consist of a
simple list of steps
Partial vs. Total Order Plans
Partial Order Plan:
Start
Start
Left
Sock
Right
Sock
Left
Shoe
Right
Shoe
Finish
Total Order Plan:
Start
Start
Start
Start
Start
Right Right
Sock Sock
Left
Sock
Left
Sock
Right
Sock
Left
Sock
Left
Sock
Left
Sock
Right Right Right
Sock Sock Shoe
Left
Shoe
Right
Shoe
Left
Shoe
Right
Shoe
Left
Shoe
Left
Sock
Right
Sock
Left
Shoe
Right
Shoe
Left
Shoe
Right
Shoe
Left
Shoe
Right
Shoe
Finish Finish Finish Finish Finish Finish
Important Points

Partial-ordering constraints
and uninstantiated
variables allow us to follow
a least-commitment
approach
Chapter 11 - Planning
Section 11.5
Partial-Order Planning
Example
Partial-Order Planning Example

Return to shopping problem:
– Buy milk, bananas, a drill, and then return
back home


Start with the definitions of the initial
and final states
Also give the actions involved in the
example
State Definitions

Initial State
Op(ACTION: Start,
EFFECT: At(Home)  Sells(HWS,Drill) 
Sells(SM, Milk)  Sells
(SM,Bananas))

Goal State
Op(ACTION: Finish,
PRECOND: Have(Drill)  Have(Milk) 
Have(Bananas)  At(Home))
Action Definitions

Actions
Op(ACTION: Go(there),
PRECOND: At(here),
EFFECT: At(there)  At(here))
Op(ACTION: Buy(x),
PRECOND: At(store)  Sells(store, x),
EFFECT: Have(x))
Initial Plan


Bold arrows are causal links
Thin arrows are ordering constraints
Figure 11.6 From Artificial Intelligence: A Modern Approach
Extending the Plan


Since there is no other way to achieve the Have(x)
preconditions of the goal state, planner must
extend plan by adding actions that will achieve
them
Extend plan by adding Buy actions
Figure 11.7a From Artificial Intelligence: A Modern Approach
Causal Links Protect Conditions


Causal link between Buy(Drill) and
Finish means it was added to achieve
the Finish precondition Have(Drill)
If a new step comes that deletes
Have(Drill) condition the planner will
make sure it won’t go between
Buy(Drill) and Finish.
Achieving Preconditions


Now planner achieves the Sells preconditions by
linking them to the initial state by causal links
Since this is the only operator that achieves the Sells
precondition, the planner must choose this one
Figure 11.17b From Artificial Intelligence: A Modern Approach
How Well Are We Doing?

Large improvement over the problemsolving approach
– Planner was able to choose the right
actions without considering all of the other
alternatives
– Don’t need to worry about ordering of
actions because the POP will do that later
Adding the Go Actions


Planner must now extend the plan by adding Go
actions to achieve At condition of Buy action
This will get us to the HWS and the SM
Figure 11.8 From Artificial Intelligence: A Modern Approach
Problem with the Go Actions I


If planner links both Go actions to the initial state,
both actions will interact with each other
Problem: agent can’t be at two places at once
Figure 11.9 From Artificial Intelligence: A Modern Approach
Problem with Go Actions II


If the agent takes one link, then the
precondition At(Home) for the other link
will be negated
This is a threat, and must be resolved
before continuing
Problem with Go Actions III



We realize that neither promotion nor
demotion can solve this threat
No matter which of the two is chosen
first, At(Home) precondition of the other
is deleted
When this occurs, the planner must give
up on partial plan and back up to a
previous choice
Solution to Go Actions


Instead of linking both Go actions to initial state, the
planner decides to go from Home to the HWS, then
from the HWS to the SM
This is done by linking Go(HWS) to Go(SM)
Modified Figure 11.11 From Artificial Intelligence: A Modern Approach
Another Threat



Go(SM) step threatens the At(HWS) precondition of
the Buy(Drill) step which is protected
Might go from HWS to the SM and forget to buy the
drill!
Solution: promotion
– constrain Go(SM) to come after the Buy(Drill) step
– add an ordering constraint from Buy(Drill) to Go(SM)
Modified Figure 11.11 From Artificial Intelligence: A Modern Approach
Final Step I




Only At(Home) precondition of goal state
left to achieve
Now planner must extend plan by adding
Go(Home) step to achieve this
Try to achieve At(x) by linking At(Home) to
the initial state, this will threaten At(Home)
precondition of At(HWS) step
There is no way to resolve this threat, so
planner must back up and try again
Final Step II



Now planner tries to link At(x) to the
Go(HWS) step, then this will also be a
threat
Threatens At(HWS) step of the Go(SM)
step
Again, can’t resolve this, so planner
must backtrack and try another path
Final Step III


It now tries to link to Go(SM) step
Another threat:
– Threatens At(SM) preconditions of the
Buy(Milk) and Buy(Bananas) steps

But this can be solved with promotion
– Constrain the Go(Home) step to come after
the Buy(Milk) and Buy(Bananas) steps

Now we’re done!
Final Plan
Figure 11.11 From Artificial Intelligence: A Modern Approach
Advantages of POP



POP can take a problem that would take
many search states for problem-solving
approach and solve it in only a few steps
Least commitment nature of planner means it
only needs to search where subplans interact
Causal links allow planner to know when to
stop a bad plan without wasting time
expanding irrelevant parts of the plan
Summary






POP starts with a minimal plan and adds to it until all
preconditions have been satisfied
POP is a regression planner
POP can take a problem that would take many
search states for problem-solving approach and solve
it in only a few steps
Causal links protect conditions
If threat occurs, promote/demote threatening steps
POP can be extended to allow partially-instantiated
operators
– need to worry about possible threats