Lezione n. !
Corso di Laurea: ! Insegnamento: !
Email: !
A.A. 2014-2015 !
Silvia Rossi !
Planning
Lezione n. 4
Informatica !
Insegnamento:
Sistemi !
multi-agente !
Email:
silrossi@unina.it !
Agent Planning !
(R&N:11.1,11.2)
Additional reading:
Malik Ghallab, Dana Nau, Paolo Traverso, "Automated Task Planning. Theory & Practice", Morgan Kaufmann, (2004).
2
Block words !
• !A set of blocks, a table and a robot arm.
• !All the blocks are equal in size, form and color, distinguished only by name.
• !The table has an unlimited extension.
• !A block can be on the table, on top of another block or held by the robot.
• !The robot arm can only hold one block at a time.
• !Solve problems by changing the initial configuration (state) into a state that meets the goals.
3
Planning vs. problem solving !
• ! Planning and problem solving methods can often solve the same sorts of problems
• ! Planning is more powerful because of the representations and methods used
• ! States, goals, and actions are decomposed into sets of sentences (usually in first-order logic)
• ! Search often proceeds through plan space
rather than state space (though there are also state-space planners)
• ! Subgoals can be planned independently,
reducing the complexity of the planning
problem
• ! Choose actions to achieve a certain goal
• ! But isn’t it exactly the same goal as for problem solving?
• ! Some difficulties with problem solving:
– ! The successor function is a black box: it must be
“applied” to a state to know which actions are possible in that state and what are the effects of each one
Goal of Planning !
• ! Suppose that the goal is HAVE(MILK).
• ! From some initial state where HAVE(MILK) is not satisfied, the successor function must be repeatedly applied to eventually generate a state where
HAVE(MILK) is satisfied.
• ! An explicit representation of the possible actions and their effects would help the problem solver
select the relevant actions
Otherwise, in the real world an agent would
be overwhelmed by irrelevant actions
Goal of Planning !
•! Choose actions to achieve a certain goal
•! But isn’t it exactly the same goal as for problem solving?
•! Some difficulties with problem solving:
– ! The goal test is another black-box function, states are domain-specific data structures, and heuristics must be supplied for each new problem
Suppose that the goal is HAVE(MILK)!HAVE(BOOK) Without an explicit representation of the goal, the problem solver cannot know that a state where
HAVE(MILK) is already achieved is more promising than a state where neither HAVE(MILK) nor
HAVE(BOOK) is achieved
Goal of Planning !
• ! Choose actions to achieve a certain goal
• ! But isn’t it exactly the same goal as for problem solving?
• ! Some difficulties with problem solving:
– ! The goal may consist of several nearly
independent subgoals, but there is no way for the problem solver to know it
HAVE(MILK)and HAVE(BOOK) may be achieved by
two nearly independent sequences of actions
Planning opens up the black- boxes by using logic to
represent:
– !Actions – !States – !Goals
Problem solving Logic representation
Planning
STRIPS (Fikes and Nilsson 1971) !
Stanford Research Institute Problem Solver ! Control System for the Shakey robot !
http://www.ai.sri.com/shakey/ !
Knowledge Representation in Strips !
A state is represented as a conjunction of instantiated predicates !
at(object1,airport1), at(plane1,airport1), !
at(truck1,airport1), at(truck2,post-o "ce2), ...!
Normally, it is assumed that the facts not present in a state are
false: closed world assumption. !
States and Goals in Block world !
The following predicates can be used: !
!on(x,y): block x is on top of block y!
!on-table(x): block x is on the table!
!clear(x): block x has no block above it and is not being held by the robot arm !
!holding(x): the robot arm is holding block x!
!arm-empty: the robot arm is not holding a block!
Basic representations for planning !
Classic approach first used in STRIPS planner circa 1970
States represented as a conjunction of ground literals
at(Home)
Goals are conjunctions of literals, but may have existentially quantified variables
at(x) ^ have(Milk) ^ have(bananas) ...
Do not need to fully specify state
Non-specified either don’t-care or assumed false Represent many cases in small storage
Often only represent changes in state rather than entire situation
Unlike theorem prover, not seeking whether the goal is
true, but is there a sequence of actions to attain it
Operator/action representation !
Operators contain three components:
Action description
Precondition - conjunction of positive literals
Effect - conjunction of positive or negative literals which describe how situation changes when operator is applied
Example:
Op[Action: Go(there),
Precond: At(here) ^ Path(here,there), Effect: At(there) ^ ~At(here)]
All variables are universally quantified
Situation variables are implicit
preconditions must be true in the state immediately before operator is
applied; effects are true immediately after
Blocks world !
The blocks world is a micro-world that consists of a table, a set of blocks and a robot hand.
Some domain constraints:
Only one block can be on another block Any number of blocks can be on the table The hand can only hold one block
Typical representation:
ontable(a) ontable(c) on(b,a)
handempty clear(b) clear(c)
A B
C
TABLE
State Representation !
Conjunction of propositions:
BLOCK(A), BLOCK(B), BLOCK(C),
ON(A,TABLE), ON(B,TABLE), ON(C,A), CLEAR(B), CLEAR(C), HANDEMPTY
A B C
TABLE
Goal Representation !
A B C
Conjunction of propositions:
ON(A,TABLE), ON(B,A), ON(C,B)
The goal G is achieved in a state S if all
the propositions in G are also in S
Action Representation !
Unstack(x,y)
• ! P =HANDEMPTY, BLOCK(x), BLOCK(y), CLEAR(x), ON(x,y)
• !E =¬HANDEMPTY, ¬CLEAR(x), HOLDING(x),
¬ON(x,y), CLEAR(y)
Precondition: Effect: list of literals conjunction of propositions
Means: Remove HANDEMPTY
from state Means: Add
HOLDING(x) to state
Example !
A B C
Unstack(C,A)
• ! P =HANDEMPTY, BLOCK(C), BLOCK(A), CLEAR(C), ON(C,A)
• !E =¬HANDEMPTY, ¬CLEAR(C), HOLDING(C),
¬ON(C,A), CLEAR(A)
BLOCK(A), BLOCK(B), BLOCK(C),
ON(A,TABLE), ON(B,TABLE), ON(C,A),
CLEAR(B), CLEAR(C), HANDEMPTY
Example !
A B
C BLOCK(A), BLOCK(B), BLOCK(C),
ON(A,TABLE), ON(B,TABLE), ON(C,A), CLEAR(B), CLEAR(C), HANDEMPTY,
HOLDING(C), CLEAR(A) Unstack(C,A)
• ! P =HANDEMPTY, BLOCK(C), BLOCK(A), CLEAR(C), ON(C,A)
• !E =¬HANDEMPTY, ¬CLEAR(C), HOLDING(C),
¬ON(C,A), CLEAR(A)
Action Representation !
Unstack(x,y)
• ! P = HANDEMPTY, BLOCK(x), BLOCK(y), CLEAR(x), ON(x,y)
• !E = ¬HANDEMPTY, ¬CLEAR(x), HOLDING(x), ¬ ON(x,y), CLEAR(y)
Stack(x,y)
• ! P = HOLDING(x), BLOCK(x), BLOCK(y), CLEAR(y)
• ! E = ON(x,y), ¬CLEAR(y), ¬HOLDING(x), CLEAR(x), HANDEMPTY
PutDown(x)
• ! P = HOLDING(x)
• ! E = ON(x,TABLE), ¬HOLDING(x), CLEAR(x), HANDEMPTY
Pickup(x)
• ! P = HANDEMPTY, BLOCK(x), CLEAR(x), ON(x,TABLE)
• ! E = ¬HANDEMPTY, ¬CLEAR(x), HOLDING(x), ¬ ON(x,TABLE)
Typical BW planning problem !
Initial state:
clear(a) clear(b) clear(c) ontable(a) ontable(b) ontable(c) handempty
Goal:
on(b,c) on(a,b) ontable(c)
A C B
A B C
A plan:
pickup(b)
stack(b,c)
pickup(a)
stack(a,b)
Another BW planning problem !
Initial state:
clear(a) clear(b) clear(c) ontable(a) ontable(b) ontable(c) handempty
Goal:
on(a,b) on(b,c) ontable(c)
A C B
A B C
A plan:
pickup(a) stack(a,b)
unstack(a,b)
putdown(a)
pickup(b)
stack(b,c)
pickup(a)
stack(a,b)
Forward Planning !
A B C
A B C
A B C A C
B
A C B
A
C B
A C B A
B C
A B C
Unstack(C,A)) Pickup(B)
Forward planning searches a state space
In general, many actions are applicable
to a state ! huge branching factor
Forward Search !
Operators are applied until the goals are reached ProgWS(state, goals, actions, path)
If state satisfies goals, then return path else a = choose(actions), s.t.
preconditions(a) satisfied in state if no such a, then return failure
else return
ProgWS(apply(a, state), goals, actions, concatenate(path, a))
First call: ProgWS(IS, G, Actions, ())
25
26
" ! Forward planning still suffers from an
excessive branching factor
" ! In general, there are much fewer actions
that are relevant to achieving a goal than actions that are applicable to a state
" ! How to determine which actions are
relevant? How to use them?
" ! ! Backward planning
Relevant Action ! An action is relevant to a goal if one of its effects matched a goal proposition
Stack(B,A)
P = HOLDING(B), BLOCK(A), CLEAR(A)
E = ON(B,A), ¬CLEAR(A), ¬HOLDING(B), CLEAR(B), HANDEMPTY
is relevant to ON(B,A), ON(C,B)
Regression of a Goal ! The regression of a goal G through an
action A is the weakest precondition R[G,A] such that:
If a state S satisfies R[G,A] then:
1. !The precondition of A is satisfied in S 2. !Applying A to S yields a state that
satisfies G
Example !
• ! G = ON(B,A), ON(C,B)
• ! Stack(C,B)
– ! P = HOLDING(C), BLOCK(C), BLOCK(B), CLEAR(B)
– ! E = ON(C,B), ¬CLEAR(B), ¬HOLDING(C), CLEAR(C), HANDEMPTY
• ! R[G,Stack(C,B)] =
ON(B,A), HOLDING(C), BLOCK(C),
BLOCK(B), CLEAR(B)
Example !
• ! G = CLEAR(B), ON(C,B)
• ! Stack(C,B)
– ! P = HOLDING(C), BLOCK(C), BLOCK(B), CLEAR(B)
– ! E = ON(C,B), ¬CLEAR(B), ¬HOLDING(C), CLEAR(C), HANDEMPTY
• ! R[G,Stack(C,B)] = False
Computation of R[G,A] !
1. ! If any element of G is deleted by A then return False
2. ! G’ # Precondition of A
3. ! For every element SG of G do
If SG is not added by A then add SG to G’
4. ! Return G’
Computation of R[G,A] !
1. ! If any element of G is deleted by A then return False
2. ! G’ # Precondition of A
3. ! For every element SG of G do
If SG is not added by A then add SG to G’
4. ! If an inconsistency rule applies to G’ then return False
5. ! Return G’
Backward Chaining !
ON(B,A), ON(C,B)
Stack(C,B)
ON(B,A), HOLDING(C), CLEAR(B)
A B C
In general, there are much fewer actions relevant to a goal than there are actions
applicable ! smaller branching factor
than with forward planning
Backward Chaining !
ON(B,A), ON(C,B)
Stack(C,B)
ON(B,A), HOLDING(C), CLEAR(B) A B C
CLEAR(C), ON(C,TABLE), CLEAR(A), HANDEMPTY, CLEAR(B), ON(B,TABLE) CLEAR(C), ON(C,TABLE), HOLDING(B), CLEAR(A)
Stack(B,A)
Pickup(B) Putdown(C)
CLEAR(A), CLEAR(B), ON(B,TABLE), HOLDING(C)
Unstack(C,A)
CLEAR(B), ON(B,TABLE), CLEAR(C), HANDEMPTY, ON(C,A)
Pickup(C)
ON(B,A), CLEAR(B), HANDEMPTY, CLEAR(C), ON(C,TABLE)
Backward planning searches a goal space
Progression vs. Regression !
Both algorithms are:
• !Sound: the result plan is valid
• !Complete: if valid plan exists, they find one Non-deterministic choice => search!
• !Brute force: DFS, BFS, Iterative Deepening, ..,
• !Heuristic: A*, IDA*, …
Complexity: O(b n ) worst-case
b = branching factor, n = |“choose”|
Regression: often smaller b, focused by goals
Progression: full state to compute heuristics 35
STRIPS !
• !Symbolic representations of knowledge about the problem domain.
• !Goal decomposition.
• !Incorporate relevant operators to the plan even when they can not be applied to the current state.
• !Mixed of regression and progression.
36
• !Search:
• ! Nodes: current state and a stack of goals-operators
• ! Root node: initial state and goal configuration
• !Idea:
• ! Push onto the stack the goals to achieve and the operators that achieve these goals
• ! Pop from the stack goals that are present in the current state, and operators that are executable
37
STRIPS planning !
• ! STRIPS maintains two additional data structures:
– ! State List - all currently true predicates.
– ! Goal Stack - a push down stack of goals to be solved, with current goal on top of stack.
• ! If current goal is not satisfied by present state,
examine add lists of operators, and push operator and preconditions list on stack. (Subgoals)
• ! When a current goal is satisfied, POP it from stack.
• ! When an operator is on top stack, record the
application of that operator on the plan sequence
and use the operator’s add and delete lists to update
the current state.
1. Match: if the objective of the top of the stack
matches with the current state, this objective is
deleted from the stack. !
2. Decompose: If the goal in the top of the stack is a
conjunction, then add the literal components at the top
of the stack in a certain order. !
3. Solve: When the goal at the top of the stack is one
unresolved literal, then find an operator whose adds
list contains a literal that matches with the objective. !
4. Apply: When the object on top of the stack is an operator, then delete it from the stack and
apply it on the current state. !
The process is repeated until the stack is
empty. !
• !Can Strips always find a plan if there is one?!
• !When Strips returns a plan, is it always
correct? e "cient?!
Example 2 !
Goal interaction !
• ! Simple planning algorithms assume that the goals to be achieved are independent
– !Each can be solved separately and then the solutions concatenated
• ! This planning problem, called the “Sussman Anomaly,” is the classic example of the goal interaction problem:
– ! Solving on(A,B) first (by doing unstack(C,A), stack(A,B) will be undone when solving the second goal on(B,C) (by doing
unstack(A,B), stack(B,C)).
– !Solving on(B,C) first will be undone when solving on(A,B)
• ! Classic STRIPS could not handle this, although minor modifications can get it to do simple cases
A B
C
Initial state
A
B
C
Goal state
State-space planning !
• ! We initially have a space of situations (where you are, what you have, etc.)
• ! The plan is a solution found by “searching”
through the situations to get to the goal
• ! A progression planner searches forward from initial state to goal state
• ! A regression planner searches backward from the goal
– ! Ideally this leads to reduced branching –you are only
considering things that are relevant to the goal
Plan-space planning !
An alternative is to search through the space of plans, rather than situations.
Start from a partial plan which is expanded and refined until a complete plan that solves the problem is generated.
Refinement operators add constraints to the partial plan and modification operators for other changes.
We can still use STRIPS-style operators:
Op(ACTION: RightShoe, PRECOND: RightSockOn, EFFECT: RightShoeOn) Op(ACTION: RightSock, EFFECT: RightSockOn)
Op(ACTION: LeftShoe, PRECOND: LeftSockOn, EFFECT: LeftShoeOn) Op(ACTION: LeftSock, EFFECT: leftSockOn)
could result in a partial plan of
[RightShoe, LeftShoe]
Partial-order planning !
A linear planner builds a plan as a totally ordered sequence of plan steps
A non-linear planner (aka partial-order planner) builds up a plan as a set of steps with some temporal constraints
constraints of the form S1<S2 if step S1 must comes before S2.
One refines a partially ordered plan (POP) by either:
adding a new plan step, or
adding a new constraint to the steps already in the plan.
A POP can be linearized (converted to a totally ordered
plan) by topological sorting
Least commitment !
• ! Non-linear planners embody the principle of least commitment
– ! only choose actions, orderings, and variable
bindings that are absolutely necessary, leaving other decisions till later
– ! avoids early commitment to decisions that don’t really matter
• ! A linear planner always chooses to add a plan step in a particular place in the
sequence
• ! A non-linear planner chooses to add a step
and possibly some temporal constraints
Non-linear plan !
A non-linear plan consists of
(1) A set of steps {S
1, S
2, S
3, S
4…}
Each step has an operator description, preconditions and post- conditions
(2) A set of causal links { … (S
i,C,S
j) …}
Meaning a purpose of step S
iis to achieve precondition C of step S
j(3) A set of ordering constraints { … S
i<S
j… }
if step S
imust come before step S
jCausal Link:
Action Ac (consumer) has precondition Q that is established in the plan by Ap(producer).
73
Step At threatens link (Ap, Q, Ac) if:
1. At has (not Q) as an effect, and
2. At could come between Ap and Ac, i.e.
O u (Ap< At< Ac) is consistent
74
Soluzione !
Una soluzione è un piano completo e consistente In un piano completo ogni precondizione di un passo viene raggiunta da qualche altro passo. Un passo
raggiunge una condizione se la condizione è uno degli
effetti del passo e se nessun altro passo può eliminare la condizione.
In un piano consistente non c’è alcuna contraddizione nell’ordinamento o nei vincoli sui legami (se validi
entrambi c’è contraddizione)
The initial plan !
Every plan starts the same way
S1:Start
S2:Finish
Initial State
Goal State
Initial Plan !
For uniformity, represent initial state and goal with two special actions: !
Start: !
• ! no preconditions,
• ! initial state as effects,
• ! must be the first step in the plan.
Finish: !
• ! no effects
• ! goals as preconditions
• ! must be the last step in the plan.
Trivial example !
Operators:
Op(ACTION: RightShoe, PRECOND: RightSockOn, EFFECT:
RightShoeOn)
Op(ACTION: RightSock, EFFECT: RightSockOn)
Op(ACTION: LeftShoe, PRECOND: LeftSockOn, EFFECT: LeftShoeOn) Op(ACTION: LeftSock, EFFECT: leftSockOn)
S1:Start
S2:Finish
RightShoeOn ^ LeftShoeOn
Steps: {S1:[Op(Action:Start)], S2:[Op(Action:Finish, Pre: RightShoeOn^LeftShoeOn)]}
Links: {}
Orderings: {S1<S2}
Solution !
Start Left
Sock
Right Sock Right
Shoe Left
Shoe
Finish
Linearizzazioni !
POP !
POP is sound and complete POP Plan is a solution if:
!All preconditions are supported (by causal links), i.e., no open conditions.
!No threats
!Consistent temporal ordering
By construction, the POP algorithm reaches a solution plan
81
Example !
Op(ACTION: START, PRECONDITION: nil, EFFECT: AT(HOME) and SELLS(STORE,DRILL) and SELLS(SUPER,MILK) and SELLS(SUPER, BREAD))
Op(ACTION: FINISH, PRECONDITION: HAVE(DRILL) and
HAVE(MILK) and HAVE(BREAD) and AT(HOME), EFFECT: nil)
Op(ACTION: GO(x), PRECONDITION: AT(x), EFFECT: AT(y) and not AT(x))
Op(ACTION: BUY(x), PRECONDITION: AT(SHOP) and SELLS(SHOP,x), EFFECT: HAVE(x))
82
Initial Plan !
83
84
85
86
Corretto? !
87
Piani con condizioni !
88
Demotion !
89
Promotion !
90
91
92
Piano Totale !
93
POP !
94
Heuristics !
Heuristics for selecting plans:
!Number of steps N
!Unsolved preconditions OP
Often uses analgorithm A * with heuristics:
f(P)=N(P) + OP(P)
95
Least commitment !
Non-linear planners embody the principle of least commitment
only choose actions, orderings, and variable bindings that are absolutely necessary, leaving other
decisions till later
avoids early commitment to decisions that don’t really matter
A linear planner always chooses to add a plan step in a particular place in the sequence
A non-linear planner chooses to add a step and
possibly some temporal constraints
Non-linear plan !
A non-linear plan consists of
(1) A set of steps {S
1, S
2, S
3, S
4…}
Each step has an operator description, preconditions and post- conditions
(2) A set of causal links { … (S
i,C,S
j) …}
Meaning a purpose of step S
iis to achieve precondition C of step S
j(3) A set of ordering constraints { … S
i<S
j… }
if step S
imust come before step S
jA non-linear plan is complete iff
Every step mentioned in (2) and (3) is in (1)
If S
jhas prerequisite C, then there exists a causal link in (2) of the form (S
i,C,S
j) for some S
iIf (S
i,C,S
j) is in (2) and step S
kis in (1), and S
kthreatens
(S
i,C,S
j) (makes C false), then (3) contains either S
k<S
ior
S
j>S
kConsistent Plan !
Consistent plan:
• ! No cycles in the ordering constraint;
• ! No conflicts with the causal links.
A consistent plan with no open precondition is a solution
98
1) The initial plan contains Start and Finish
• ! the ordering constraint Start < Finish,
• ! no causal links
• ! all the preconditions in Finish as open preconditions.
99
2) The successor function arbitrarily picks one open precondition p on an action B and
generates a successor plan for every possible consistent way of choosing an action A that achieves p.
Consistency is enforced as follows:
1. The causal link A ->p B and the ordering constraint A
< B are added to the plan.
Action A may be an existing action in the plan or a new one. If it is new, add it to the plan and also add Start <
A and A < Finish. 100
2) The successor function arbitrarily picks one open precondition p on an action B and
generates a successor plan for every possible consistent way of choosing an action A that achieves p.
2. Resolve conflicts between the new causal link and all existing actions.
A conflict between A ->p B and C is resolved by making C occur at some time outside the protection interval
B < C C < A
We add successor states for either or both if they result
in consistent plans 101
3) The goal test checks whether a plan is a solution to the original planning problem.
Because only consistent plans are generated, the goal test just needs to check that there are no open
preconditions.
102
Nonlinear Planning !
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
P: HOLDING(B) CLEAR(A) -: CLEAR(A) HOLDING(B) +: ON(B,A) CLEAR(B) HANDEMPTY
Stack(B,A)
The plan is incomplete
Open preconditions
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
P: HOLDING(B) CLEAR(A) -: CLEAR(A) HOLDING(B) +: ON(B,A) CLEAR(B) HANDEMPTY
Stack(B,A)
P: HOLDING(C) CLEAR(B) -: CLEAR(B) HOLDING(C) +: ON(C,B) CLEAR(C) HANDEMPTY
Stack(C,B)
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C)
P: HOLDING(B) CLEAR(A) -: CLEAR(A) HOLDING(B) +: ON(B,A) CLEAR(B) HANDEMPTY
P: HOLDING(C)
CLEAR(B)
-: CLEAR(B)
HOLDING(C)
+: ON(C,B)
CLEAR(C)
HANDEMPTY
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
P: CLEAR(B)
Achievers
Threat Other possible
achiever
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
P: CLEAR(B)
P: CLEAR(B)
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
Note the similarity with constraint propagation
A consistent plan is one in which there is no cycle and no conflict between achievers and threats
A conflict can be eliminated by constraining the ordering among the actions or by
adding new actions
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
P: HANDEMPTY
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
P: HANDEMPTY
P: HANDEMPTY
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
P: HANDEMPTY CLEAR(C) ON(C,TABLE)
P: HOLDING(C) CLEAR(B) P: HOLDING(B) CLEAR(A) P: HANDEMPTY
CLEAR(B) ON(B,TABLE)
~ Most-constrained-variable heuristic in CSP
! choose the unachieved precondition that can be satisfied in the fewest number of ways
! ON(C,TABLE)
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
Putdown(C)
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
Putdown(C)
Unstack(C,A)
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
Putdown(C) Unstack(C,A)
P: HANDEMPTY
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
Putdown(C)
Unstack(C,A)
P: -:
+: ON(A,TABLE) ON(B,TABLE) ON(C,A) CLEAR(B) CLEAR(C) HANDEMPTY
P: ON(B,A) ON(C,B) -:
+:
Stack(B,A)
Stack(C,B)
Pickup(C) Pickup(B)
Putdown(C) Unstack(C,A)
P: HANDEMPTY CLEAR(C) ON(C,TABLE)
P: HOLDING(C) CLEAR(B) P: HOLDING(B) CLEAR(A) P: HANDEMPTY
CLEAR(B) ON(B,TABLE)
P: HOLDING(C) P: HANDEMPTY
CLEAR(C) ON(C,A)
The plan is complete because every precondition of every step is added
by some previous step, and no
intermediate step deletes it
Hierarchical Planning !
(R&N:12.2)
Hierarchical Planning Brief History !
Originally developed about 25 years ago Knowledge-based ! Scalable
Task Hierarchy is a form of domain-specific knowledge
Practical, applied to real world problems (linear time vs. exponential)
Lack of theoretical understanding until early 1990’s
Formal semantics, sound/complete algorithm,
Hierarchical Decomposition !
HTN Planning !
• ! Capture hierarchical structure of the planning domain
• ! Planning domain contains non-primitive actions and schemas for reducing them
• ! Reduction schemas:
– !given by the designer
– !express preferred ways to accomplish a
task
Hierarchical decomposition !
• !Hierarchical decomposition, or hierarchical task
network (HTN) planning, uses abstract operators to incrementally decompose a planning problem from a high-level goal statement to a primitive plan network
• !Primitive operators represent actions that are executable, and can appear in the final plan
• !Non-primitive operators represent goals
(equivalently, abstract actions) that require further decomposition (or operationalization) to be executed
• !There is no “right” set of primitive actions: One
agent’s goals are another agent’s actions!
HTN planning: example !
Hierarchical Decomposition !
From a high-level
action to a partially
ordered set of lower-
level actions.
HTN Planning !
A plan library contains both primitive and non- primitive actions.
Non-primitive actions have external
preconditions, as well as external effects.
Sometimes useful to distinguish between
primary effects and secondary effects.
HTN Formalization (1) !
State: list of ground atoms Tasks:
Primitive tasks: do[f(x 1 , …, x n )]
Non-primitive tasks:
Goal task: achieve(l) (l is a literal) Compound task: perform[t(x 1 , …, x n )]
Plan Library
Operator:
[operator f(x 1 , …, x n ) (pre: l 1 , …, l n ) (post: l’ 1 , …, l’ n )]
Method: Decompose( ! , d)
" is a non-primitive task and d is a task network
Plan: sequence of ground primitive tasks
(operators)
Task Reduction !
Example action descriptions !
Action(BuyLand, PRECOND:money, EFFECT: Land Money)
Action(GetLoan, PRECOND: GoodCredit, EFFECT: Money Mortage) Action(BuildHouse, PRECOND:Land, EFFECT: House)
Action(GetPermit, PRECOND: Land, EFFECT: Permit) Action(HireBuilder, EFFECT: Contract)
Action(Construction, PRECOND: Permit Contract, EFFECT: HouseBuild Permit)
Action(PayBuilder, PRECOND:Money HouseBuilt,
EFFECT: Money House Contract) 128
Example action descriptions !
Decompose(BuildHouse,
Plan(STEPS:{S1: GetPermit, S2: HireBuilder, S3: Construction, S4: PayBuilder}
ORDERINGS: {Start S1S3 S4 Finish, Start S2 S3,
LINKS: {Start Land S1, Start Money S4, S1 Permit S3, S2 Contract S3, S3 HouseBuilt S4,
S4 House Finish, S4 Money Finish}))
129
Correctness !
• ! A decomposition should be a correct implementation of the action.
• ! A plan d implements an action a correctly if d is a complete and consistent partial-order plan for the problem of achieving the
effects of a given the preconditions of a (result of a sound POP).
• ! The plan library contains several decompositions for any high- level action.
• ! Each decomposition might have different preconditions and effects. The preconditions of the high-level action should be the intersection of the preconditions of the decompositions (similarly for the external effects.)
130
Information hiding !
The high-level description hides all the internal effects of decompositions (e.g., Permit and
Contract).
It also hides the duration the internal preconditions and effects hold.
Advantage: reduces complexity by hiding details Disadvantage: conflicts are hidden too
131
Example !
132
HTN Planning Algorithm (intuition) !
Problem reduction:
Decompose tasks into subtasks Handle constraints
Resolve interactions
If necessary, backtrack and try other
decompositions
Basic HTN Procedure !
1. ! Input a planning problem P
2. ! If P contains only primitive tasks, then
resolve the conflicts and return the result. If the conflicts cannot be resolved, return
failure
3. ! Choose a non-primitive task t in P 4. ! Choose an expansion for t
5. ! Replace t with the expansion
6. ! Find interactions among tasks in P and
suggest ways to handle them. Choose one.
7. ! Go to 2
For each decomposition d of an action a !
Remove the high level action, and insert/reuse actions for each action in d
Reuse -> subtask sharing
Merge the ordering constraints (If there is an ordering constraint of the form B should every step of d come after B?
Merge the causal links
135
Comments on HTN planning !
The major idea is to gain efficiency by using the library of preconstructed plans.
When there is recursion, it is undecidable even if the underlying state space is finite.
recursion can be ruled out
the length of solutions can be bound
can use a hybrid POP and HTN approach
136
SHOP (Simple Hierarchical Ordered Planner) !
• ! Domain-independent algorithm for Ordered Task Decomposition
– ! Sound/complete
• ! Input:
– ! State: a set of ground atoms – ! Task List: a linear list of tasks
– ! Domain: methods, operators, axioms
• ! Output: one or more plans, it can return:
– ! the first plan it finds – ! all possible plans
– ! a least-cost plan
– ! all least-cost plans
• ! Initial task list: ((travel home park))
• ! Initial state: ((at home) (cash 20) (distance home park 8))
• ! Methods (task, preconditions, subtasks):
– ! (:method (travel ?x ?y)
((at ?x) (walking-distance ?x ?y)) ' ((!walk ?x ?y)) 1) – ! (:method (travel ?x ?y)
((at ?x) (have-taxi-fare ?x ?y))
' ((!call-taxi ?x) (!ride ?x ?y) (!pay-driver ?x ?y)) 1)
• ! Axioms:
– ! (:- (walking-dist ?x ?y) ((distance ?x ?y ?d) (eval (<= ?d 5)))) – ! (:- (have-taxi-fare ?x ?y)
((have-cash ?c) (distance ?x ?y ?d) (eval (>= ?c (+ 1.50 ?d))))
• ! Primitive operators (task, delete list, add list) – ! (:operator (!walk ?x ?y) ((at ?x)) ((at ?y)))
– ! …
Simple Example !
Optional cost;
default is 1
Precond: Precond:
(travel home park)
(!walk home park)
(!call-taxi home) (!ride home park) (!pay-driver home park) Fail (distance > 5)
Succeed (we have $20, and the fare is only $9.50) Succeed
Succeed (at home) (walking-distance
Home park)
(have-taxi-fare home park)
(at park) (cash 10.50) (distance home park 8)
Simple Example (Continued) !
(at home)
Initial state:
Final state:
(at home)
(cash 20)
(distance home park
8)
The SHOP Algorithm !
procedure SHOP (state S, task-list T, domain D) 1. if T = nil then return nil
2. t
1= the first task in T
3. U = the remaining tasks in T
4. if t is primitive & an operator instance o matches t
1then 5. P = SHOP (o(S), U, D)
6. if P = FAIL then return FAIL 7. return cons(o,P)
8. else if t is non-primitive
& a method instance m matches t
1in S
& m’s preconditions can be inferred from S then 9. return SHOP (S, append (m(t
1), U), D)
10. else
11. return FAIL 12. end if
end SHOP
state S; task list T=( t
1,t
2,…) operator instance o
state o(S) ; task list T=(t
2, …)
task list T=( t
1,t
2,…) method instance m
task list T=( u
1,…,u
k,t
2,…) nondeterministic
choice among all
methods m whose
preconditions can be
inferred from S
Introduction to Distributed Planning !
142
Distributed problem solving !
143
Distributed planning !
What can be distributed:
$ ! The process of coming out with a plan is distributed among agents
$ ! Execution is distributed among agents
Centralized planning for distributed plans !
Operators
" !move(b,x,y)
!movetotable(b,x)
Precond: on(b,x) ! clear(b) ! clear(y) Precond: on(b,x) ! clear(b)
Postcond: on(b,y) ! clear(x) ! Postcond: on(b,T ) ! clear(x) ! ¬on(b,x)
¬on(b,x) ! ¬clear(y)
144
A
B D
C E
F
Si
C A
E
B F
D
Sf
I'm Bill Agent1 I'm Tom
Agent2
on(A,B) on(C,D) on(E,F) on(B,T) on(D,T) on(F,T)
on(B,A) on(F,D) on(A,E) on(D,C) on(E,T) on(C,T) on(B,A)
S1: move(B,T,A)
on(B,T) clear(B) clear(A) movetotable(A,B) move(A,B,y)
S2: move(A,B,E) clear(A) clear(E) on(A,B)
on(E,T)
S3: movetotable(E,F)
1. Given a goal description, a set of operators,
and an initial state description
generate a partial order plan
S1: move(B,T,A) To satisfy the preconditions, we have:
S2: move(A,B,E) S2 < S1, S3 < S4 S3:movetotable(E,F) S6 < S4, S6 < S5 S4: move(F,T,D) Also
S5: move(D,T,C) S2 threat to S3 # S3 < S2 S6: movetotable(C,D) S4 threat to S5 # S5 < S4 Then the partial ordering is: S3 < S2 < S1
S6 < S5 < S4
S3 < S4
S3: movetotable(E,F) S2: move(A,B,E) S1: move(B,T,A) S6: movetotable(C,D) S5: move(D,T,C) S4: move(F,T,D)
Any total ordering that satisfies this partial ordering is a good plan for Agent1 What if we have 2 agents?
DECOMP1
Subplan1 S3 < S2 < S1 Subplan2 S6 < S5 < S4 and S3 < S4 Agent1 S3 < send(clear(F)) < S2 < S1
Agent2 S6 < S5 < wait(clear(F)) < S4 145
< <
2. Decompose the plan into
subproblems so as to minimize order relations across plans 3. Insert synchronization
4. Allocate subplans to agents
S3: movetotable(E,F) S2: move(A,B,E) S1: move(B,T,A) S6: movetotable(C,D) S5: move(D,T,C) S4: move(F,T,D) DECOMP2
Subplan1 S3 < S5 < S4 Subplan2 S6 < S2 < S1
and S3 < S2 and S6 < S5
Agent1 S3 < send(don't_care(E)) < wait(clear(D)) < S5 < S4 Agent2 S6 < wait(don't_care(E)) < wait(clear(D)) < S2 < S1
"!Obviously, DECOMP2 has more order relations among subplans than DECOMP1
"!Therefore, we choose DECOMP1
S3 < send(clear(F)) < S2 < S1 S6 < S5 < wait(clear(F)) < S4
But
then back to DECOMP2
146
then back to DECOMP2
< <
4. If failure to allocate subplans then redo decomposition (2)
If failure to allocate subplans with any decomposition
then redo generate plan (1) 5. Execute and monitor subplans
I know how to move only
D, E, F
I know how to move only
A, B, C
S3 <
S6 < S5 <
S6 < S5 <
Distributed planning for centralized plans !
Each of the planning agents generate a partial plan in parallel then merge these plans into a global plan
"!parallel to result sharing
"!may involve negotiation
Agent 1 - is specialized in doing movetotable(b,x) Agent 2 - is specialized in doing move(b,x,y)
Agent 1 - based on Sf it comes out with the partial plan
PAgent1 = { S3: movetotable(E,F) satisfies on(E,T)
S6: movetotable(C,D) satisfies on(C,T)
no ordering }
Agent 2 - based on Sf it comes out with the partial plan
PAgent 2 = { S1: move(B,T,A), S2: move(A,B,E) satisfies on(B,A) ! on(A,E) S4: move(F,T,D), S5: move(D,T,C) satisfies on(F,D) ! on(D,C) ordering S2 < S1 and S5 < S4 }
Merge PAgent1 with PAgent2 by checking preconditons and threats
Establish thus order S3 < S2, S6 < S5, S3 < S4 + order of PAgent2
Then give any instance of this partial plan to an execution agent to carry it out
147
The problem is decomposed and distributed among various planning specialists, each of which proceeds then to
generate its portion of the plan
" ! similar to task sharing
" ! may involve backtracking
Agent 1 - knows only how to deal with 2-block stacks Agent 2 - knows only how to deal with 3-block stacks
148
C A
E
B F
D
Sf
C A
E B F
D A
B D
C E
F
Si
Distributed planning for distributed plans !
149
" !movehigh(b,x,y)
Precond: have_lifter ! clear(b) ! clear(y) ! on(y,z) ! z$ T
Postcond: on(b,y) ! clear(x) ! ¬on(b,x) ! ¬ clear(y) ! free_lifter
" !pick_lifter
Precond: free_lifter
Postcond: have_lifter ! ¬free_lifter
Agent1: { S1:move(A,T,B) < S2: pick_lifter < S3: movehigh(E,T,B) } Agent2: { R1:move(C,T,D) < R2: pick_lifter < R3: movehigh(F,T,C) }
150
A B D F E C
Si
D A
B
E F
C
Sf
S1
S2 S3
R1
R3 R2
need_l
free_l
