CM3112 Artificial Intelligence
Planning Finding plans
Steven Schockaert
SchockaertS1@cardiff.ac.uk
School of Computer Science & Informatics Cardiff University
Planning as a search problem
Finding a solution to a planning problem (i.e. a plan which reaches the goal from an initial state) can be formalised as a standard search problem
Naive approach:
‣ States: sequences of actions from the planning problem
‣ Initial state: empty plan
‣ Goal state: sequence of actions that reaches the goal
‣ “Actions”: add one planning action to the current sequence
Note:
‣ Actions from the planning problem ≠ actions from the search problem
‣ States from the planning problem ≠ states from the search problem
Planning as a search problem
Search vs. Planning
Naive approach often not sufficiently effective, as there are too Consider the task: get milk, bananas, and a cord-less drill
many actions to choose from in any given state Standard search algorithms fail miserably
After-the-fact heuristic/goal test inadequate
Planning as a search problem
Often there are independent sub-goals: more effective to find
partial plans for each sub-goal individually
n 11.3. Partial-Order Planning 389
Partial-Order Plan:
Start
Left Sock
LeftSockOn
Left Shoe
Right Sock
RightSockOn
Right Shoe
LeftShoeOn, RightShoeOn
Finish
Total-Order Plans:
Start
Start
Start
Start
Start
Start
Right Sock
Right Sock
Left Sock
Left Sock
Right Sock
Left Sock
Left Sock
Left Sock
Right Sock
Right Sock
Right 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
Figure 11.6 A partial-order plan for putting on shoes and socks, and the six corresponding
Finish
Finish
Finish
Finish
o
linearizations into total-order plans.
Planning as a search problem
To formalise planning as a search problem, we work backwards
from the goal state
We search for a partially ordered plan
Every linearisation of such a partially ordered plan will correspond to a valid totally ordered plan
Section 11.3. Partial-Order Planning
Planning as a search problem
Partial-Order Plan:
Total-Order Plans:
Start Start
Right Right Sock Sock
Left Left Sock Sock
Right Left Shoe Shoe
Left Right Shoe Shoe
Finish Finish
Left Sock
Start
Start
Start
LeftSockOn
RightSockOn
Left Left Sock Sock
Right Right Sock Sock
Right Left Shoe Shoe
Left Shoe
LeftShoeOn, RightShoeOn
Left Shoe
Finish
Right Shoe
Finis
Right Sock
Right Shoe
Finish
Figure 11.6 A partial-order plan for putting on shoes and socks, and t linearizations into total-order plans.
h
n 11.3. Partial-Order Planning
389
Planning as a search problem: states
Partial-Order Plan:
Total-Order Plans:
States are represented as:
‣ Start Start Start Start Start A set of actions from the planning
problem (including two special actions:
Start
Left Sock
LeftSockOn
RightSockOn
Right Sock
Right Right Left Left Right
Start
Left Sock
“Start” and “Finish”)
Sock Sock Sock Sock Sock
‣ The effects of Start are those atoms that are true in the initial state
Left‣ Left Right Right Right Left Sock Sock Sock Sock Shoe Shoe
atoms that are required to be true in the
Right Sock
Right Shoe
Finish
The preconditions of Finish are the
goal state
Left Shoe
Right Shoe
Right Left Right Left Left
Shoe Shoe Shoe Shoe Sock
LeftShoeOn, RightShoeOn
Left Right Left Right Left Shoe Shoe Shoe Shoe Shoe
{Start, Left-Sock, Left-Shoe,
Finish
Finish Finish Finish Finish Finish
Figure 11.6 A partial-order plan for putting on shoes and socks, and the six corresponding linearizations into total-order plans.
Right-Shoe, Finish}
o
n 11.3. Partial-Order Planning
389
Planning as a search problem: states
Partial-Order Plan:
Total-Order Plans:
States are represented as:
‣Start Start Start Start A set of actions
LeftSockOn
RightSockOn
Left Left Sock Sock
Right Left Shoe Shoe
Right Right Sock Sock
Right Left Shoe Shoe
Start
A≺B indicating that action A needs to be
Sock Sock Sock Sock
executed before action B
Sock
Right Left Shoe Shoe
Left Right Sock Sock
Start
Start
‣ A set of ordering constraints of the form
Right Right Left
Left Right Left
Sock
Left Sock
LeftShoeOn, RightShoeOn
Left-Shoe, Left-Shoe ≺ Finish,
Finish Finish Finish Finish Finish Finish
Right Sock
Left Shoe
Right Shoe
{Start ≺ Left-Sock, Left-Sock ≺ Shoe Shoe Shoe Shoe Shoe Shoe
Left Right Left Right Left Right
Finish
Figure 11.6 A partial-order plan for putting on shoes and socks, and the six corresponding linearizations into total-order plans.
Right-Shoe ≺ Finish}
o
o
⌅¬⌅
h s
s t
a •Finishareadded.o
m ,
l
n 11.3. Partial-Order Planning
Left Sock
LeftSockOn
(ii)
RightSockOn
onTable(C) ⇤ on(B, C) ⇤ empty
Right Left Right Left Left Right
Effect:Hold(Monkey, Bananas) ⌅ Taken(Bananas))
389
Planning as a search problem: states
(d) (BOOKWORK)
Partial-Order Plan: Total-Order Plans:
(i) States consist of four components:
Right Sock
•As use
States are represented as:
Action(PutDown(A, B),
‣ Start Start Start
• A set of actions, taken from the planning proble
A set of actions Precond:holding(A) ⇤ clear(B),
Effect:¬holding(A) ⇤ empty ⇤ clear(A) ⇤ on(A, B) ⇤ ¬c Right Right Left Left Right Left
‣ A set of causal links of the form
e executed before B. Sock Sock Sock
Sock Sock Sock
p
et of
causal links A ⇤ B, indicating that t
Start Start Start
et of orAdseertinofgorcdoenrisntgracointsstraoinfttshe form A ⇥ B ‣
be
d as a precondition for B, i.e. that A achieve indSiockating Sthocakt effeScoctkp of aScoctkion ASihsoeusedSahose a
Left Left Right Right Right Left
• A set of open preconditions, which are precond
precondition for B.
en achTiehviseedncboydeasnthaectoinosntraAin.t that no actions
Left Shoe
Right
Shoe
⇤ clear(A) ⇤ on(A, B)
executed between A and B are allowed to make
Shoe Shoe Shoe Shoe
Sock Sock
• A successor of a given state is obtained by choo p false
LeftShoeOn, RightShoeOn
Left-Sock ⇥ Left-Shoe p
Figure 11.6
A partial-order plan for putting on shoes and socks, and the six corresponding
Start
Finish
•As to b
conditions p of an action B, and an action A tha
Left Right Left Right Left Right
Shoe Shoe Shoe Shoe
Shoe Shoe
can be consistently added to the plan as follows.
the plan.
Finish Finish FinLieshftShoeFOinnish Finish Finish
• The causal link A ⇤ B and the ordering constr
LeftSockOn
Left-Shoe ⇥ Finish RightShoeOn
Right-Shoe ⇥ Finish
linearizations intIoftotAal-odrdiedr plnanos.t yet occur in the plan, the ordering c
n 11.3. Partial-Order Planning
389
Planning as a search problem: states
Partial-Order Plan:
Total-Order Plans:
States are represented as:
‣ Start Start Start Start A set of actions
‣ A set of ordering constraints
‣
LeftSockOn
RightSockOn
effect of another action
Start
Start
Right ‣ Sock Sock Sock Sock Sock
Start
Left Sock
Right Right Left Left
A set of causal links
Left Sock
Right Sock
A set of open preconditions which are those preconditions of actions in the partial
Left Left Right Right Right Left Sock Sock Sock Sock Shoe Shoe
plan that have not yet been achieved as the
Left Shoe
Right Shoe
Right Left Shoe Shoe
Left Right Shoe Shoe
Finish Finish
Right Left Left Shoe Shoe Sock
Left Right Left Shoe Shoe Shoe
Right Sock
Right Shoe
Finish
LeftShoeOn, RightShoeOn
Finish
Figure 11.6 A partial-order plan for putting on shoes and socks, and the six corresponding linearizations into total-order plans.
Finish Finish Finish
{RightSockOn}
o
n 11.3. Partial-Order Planning
389
Planning as a search problem: states
Partial-Order Plan:
Total-Order Plans:
Start
Start Start Start
Start Start
Start
Left Sock
Initial state of the search problem
‣ Only actions are Start and Finish
Right Right Left Left Right
Left Sock
LeftSockOn
Left Shoe
Right Sock
RightSockOn
Right Shoe
‣ Only ordering constraint is Start≺Finish Left Left Right Right Right Left
Sock Sock Sock
Sock Sock
‣ There are no causal links
‣Sock Sock Sock Sock Shoe Shoe
The set of open preconditions are the
preconditions of the action Finish
Right Left Right Left Left Shoe Shoe Shoe Shoe Sock
Right Sock
Right Shoe
Finish
LeftShoeOn, RightShoeOn
Left Right Left Right Left Shoe Shoe Shoe Shoe Shoe
Finish Finish Finish Finish Finish
Finish
Figure 11.6 A partial-order plan for putting on shoes and socks, and the six corresponding linearizations into total-order plans.
o
n 11.3. Partial-Order Planning 389
Planning as a search problem: states
Partial-Order Plan:
Total-Order Plans:
Start
Start Start Start
Start Start
Start
Goal state of the search problem
‣ Any state for which the list of open
Right Right Left Left Right Left
Sock Sock Sock
Sock Sock Sock
preconditions is empty
Left Sock
Right Sock
LeftSockOn
RightSockOn
Left Left Sock Sock
Right Left Shoe Shoe
Left Right Shoe Shoe
Finish Finish
Right Right Right Left Sock Sock Shoe Shoe
Right Left Left Right Shoe Shoe Sock Sock
Left Right Left Right Shoe Shoe Shoe Shoe
Finish Finish Finish Finish
Left Shoe
Right Shoe
LeftShoeOn, RightShoeOn
Finish
Figure 11.6 A partial-order plan for putting on shoes and socks, and the six corresponding linearizations into total-order plans.
o
n(Grasp(Bananas)
O
•theplan. ⇤ ⇥a
)
t
f n
h h
,
Precond:At(Monkey, R) ⌅ ¬Taken(Bananas) ⌅ On(Monkey, Box
Planning as a search problem: actions
Effect:Hold(Monkey, Bananas) ⌅ Taken(Bananas)) Successor states in the search problem are found as follows
KWORK)
‣
‣ Choose an action A (from the planning problem) which has p as an
Pick one of the open preconditions p, which is needed for action B States consist of four components:
• A set of actions, taken from the planning problem. effect
• A set of ordering constraints of the form A ⇥ B, indicating ‣ The ordering constraint A ≺ B is added, as well as the causal link
to be executed before B.
• A set of causal links A ⇤ B, indicating that the e ect p o
p
used as a precondition for B, i.e. that A achieves p for actio ‣ If action A did not yet occur in the plan, add the ordering
• A set of open preconditions, which are preconditions that constraints Start ≺ A and A ≺ Finish
been achieved by an action A.
‣ For every action C in the plan with effect ¬p, add either the ordering
constraint C ≺ A or B ≺ C
• A successor of a given state is obtained by choosing one of t
c‣onditions p of an action B, and an action A that achieves p, constraints is cycle-free
The resulting partial plan is only a valid state if the set of ordering
can be consistently added to the plan as follows.
The causal link A p B and the ordering constraint A B
Example
Initial state: hungry, atHome
Goal state: atWork
Action: (eat, preconditions: hungry effect: ¬hungry)
Action: (driveToWork, preconditions: ¬hungry, atHome effect: ¬atHome, atWork)
Example
Actions = {start, finish}
Ordering constraints = {start < finish} Causal links = {}
Open preconditions = {atWork}
initial state of the search problem
Example
S0
Actions = {start, finish}
Ordering constraints = {start < finish} Causal links = {}
Open preconditions = {atWork}
Actions = {start, finish, driveToWork}
Ordering constraints = {start < driveToWork,
driveToWork