slide 1: BE Computer Engineering
Unit II
Problem Decomposition and Planning
1
slide 2: Outline
Problem Decomposition:
Goal Trees Rule Based Systems Rule Based Expert Systems.
Planning:
STRIPS Forward and Backward State Space Planning Goal Stack
Planning Plan Space Planning
Constraint Satisfaction
2
slide 3: Goal Trees
An AND-OR Tree. And Arcs represent subproblems to be solved individually.
3
slide 4: Rule Based Systems
Rule based systems have been used in general to decompose a problem
and address it in parts.
Pattern Action
Dinner Pizza Hut | KFC
4
slide 5: Reasoning
Backward Reasoning: If the goal is to have dinner then it could be
archived by going to one of the two restaurants. This form of reasoning
is also called as backward reasoning because the reasoning is done
backwards from the goal.
Forward reasoning: In this rules are triggered by patterns in the data.
5
slide 6: Planning
The goal of action planning is to choose actions and ordering relations
among these actions to achieve specified goals
Search-based problem solving applied to 8-puzzle was one example of
planning but our description of this problem used specific data
structures and functions
Here we will develop a non-specific logic-based language to represent
knowledge about actions states and goals and we will study how
search algorithms can exploit this representation
6
slide 7: STRIPS Language through Examples
7
slide 8: Planning-Planner
In classical planning reasoning about actions involves simulation of
changes in mental model that the agent has.
The agent peers into the future to examine the different possibilities and
select the desirable course of action projection in future. The planner
searches through the possible combination of action to find the plan that
will work.
Alternative approach is to use agents experience. If agent has memory
it can reuse a plan the worked earlier or reuse the problem solving
experience to solve problems.
8
slide 9: STRIPS
In artificial intelligence STRIPS Stanford Research Institute Problem
Solver is an automated planner developed by Richard Fikes and Nils
Nilsson in 1971.
The same name was later used to refer to the formal language of the
inputs to this planner.
This language is the base for most of the languages for expressing
automated planning problem instances in use today such languages are
commonly known as action languages.
9
slide 10: • A robot hand can move blocks on a table
• The hand cannot hold more than one block at a time
• No two blocks can fit directly on the same block
• The table is arbitrarily large
A B
C
TABLE
Blocks-World Example
• Precondition: The assertions
needed to be true for the operator
to be applicable.
• Add List: The assertions that
become true as a consequence of
the operator being applied.
• Delete List: The assertions that are
no longer true as a consequence of
the operator being applied.
22
slide 11: State
BlockA BlockB BlockC OnATABLE
OnBTABLE OnCA ClearB ClearC
Handempty
A B
C
TABLE
23
slide 12: Goal
A
B
C
OnATABLE OnBA OnCB ClearC
24
slide 13: A B
C
OnATABLE OnCB
A
B
C
Goal
25
slide 14: Unstackxy
P Handempty Blockx Blocky Clearx
Onxy
D Handempty Clearx Onxy
A Holdingx Cleary
Goal
26
slide 15: Unstackxy
P Handempty Blockx Blocky Clearx Onxy
D Handempty Clearx Onxy
A Holdingx Cleary
A B
C
BlockA BlockB BlockC
OnATABLE OnBTABLE OnCA
ClearB ClearC Handempty
UnstackCA
P Handempty BlockC BlockA ClearC OnCA
D Handempty ClearC OnCA
A HoldingC ClearA
Action
27
slide 16: C
Unstackxy
P Handempty Blockx Blocky Clearx Onxy
D Handempty Clearx Onxy
A Holdingx Cleary
BlockA BlockB BlockC
OnATABLE OnBTABLE OnCA
ClearB ClearC Handempty
HoldingC ClearA
UnstackCA
P Handempty BlockC BlockA ClearC OnCA
D Handempty ClearC OnCA
A HoldingC ClearA
C
A B
Action
28
slide 17: BlockA BlockB BlockC
OnATABLE OnBTABLE OnCA
ClearB ClearC Handempty
HoldingC ClearA
UnstackCA
P Handempty BlockC BlockA ClearC OnCA
D Handempty ClearC OnCA
A HoldingC ClearA
C
A B
Unstackxy
P Handempty Blockx Blocky Clearx Onxy
D Handempty Clearx Onxy
A Holdingx Cleary
Action
29
slide 18: Unstackxy
P Handempty Blockx Blocky Clearx Onxy
D Handempty Clearx Onxy
A Holdingx Cleary
Stackxy
P Holdingx Blockx Blocky Cleary
D Cleary Holdingx
A Onxy Clearx Handempty
Pickupx
P Handempty Blockx Clearx OnxTable
D Handempty Clearx OnxTable
A Holdingx
Putdownx
P Holdingx Blockx
D Holdingx
A OnxTable Clearx Handempty
All Action
30
slide 19: Unstackxy
P Handempty Blockx Blocky Clearx Onxy
D Handempty Clearx Onxy
A Holdingx Cleary
Stackxy
P Holdingx Blockx Blocky Cleary
D Cleary Holdingx
A Onxy Clearx Handempty
Pickupx
P Handempty Blockx Clearx OnxTable
D Handempty Clearx OnxTABLE
A Holdingx
Putdownx
P Holdingx Blockx
D Holdingx
A OnxTABLE Clearx Handempty
A block can always fit
on the table
31
slide 20: InitAtC1 SFO AtC2JFK AtP1SFO AtP2JFK CargoC1 CargoC2
PlaneP1 PlaneP2 AirportJFK AirportSFO
GoalAtC1JFK AtC2SFO
ActionLoadcpa
PRECOND: Atca Atpa Cargoc Planep Airporta
EFFECT: ¬Atca Incp
ActionUnloadcpa
PRECOND: Incp Atpa Cargoc Planep Airporta
EFFECT: Atca ¬Incp
ActionFlypfromto
PRECOND: Atpfrom Planep Airportfrom Airportto
EFFECT: ¬ Atpfrom Atpto
LoadC1P1SFO FlyP1SFOJFK LoadC2P2JFK FlyP2JFKSFO
Example: Air cargo transport
32
slide 21: Planning Methods
33
slide 22: PLANNING WITH STATE-SPACE SEARCH
• The most straightforward approach is to use state-space
search. Because the descriptions of actions in a planning
problem specify both preconditions and effects
• It is possible to search in either direction: either forward
from the initial state or backward from the goal as shown
in Figure next slide.
• We can also use the explicit action and goal
representations to derive effective heuristics
automatically.
34
slide 23: PLANNING WITH STATE-SPACE SEARCH
• Both forward and backward search possible
• Progression planners
• forward state-space search
• Consider the effect of all possible actions in a given state
• Regression planners
• backward state-space search
• To achieve a goal what must have been true in the previous
state.
35
slide 24: Two approaches to searching for a plan. a Forward progression state-space search starting in
the initial state and using the problems actions to search forward for the goal state. b Backward
regression state-space search: a belief-state search starting at the goal states and using the
inverse of the actions to search backward for the initial state.
Progression and Regression
36
slide 25: Progression algorithm
• Formulation as state-space search problem:
• Initial state initial state of the planning problem
• Literals not appearing are false
• Actions those whose preconditions are satisfied
• Add positive effects delete negative
• Goal test does the state satisfy the goal
• Step cost each action costs 1
• No functions … any graph search that is complete is a
complete planning algorithm.
• E.g. A
• Inefficient:
• irrelevant action problem
• good heuristic required for efficient search
37
slide 26: Forward State Space Planning
• Consider an air cargo problem with 10 airports where each airport
has 5 planes and 20 pieces of cargo.
• The goal is to move all the cargo at airport A to airport B. There is a
simple solution to the problem: load the 20 pieces of cargo into one of
the planes at A fly the plane to B and unload the cargo.
• But finding the solution can be difficult because the average
branching factor is huge: each of the 50 planes can fly to 9 other
airports and each of the 200 packages can be either unloaded if it is
loaded or loaded into any plane at its airport if it is unloaded.
• It is clear that a very accurate heuristic will be needed to make this
kind of search efficient. We will discuss some possible heuristics after
looking at backward search.
38
slide 27: Regression algorithm
• How to determine predecessors
• What are the states from which applying a given
action leads to the goal
• Goal state AtC1 B AtC2 B … AtC20 B
• Relevant action for first conjunct: UnloadC1pB
• Works only if pre-conditions are satisfied.
• Previous state InC1 p Atp B AtC2 B …
AtC20 B
• Subgoal AtC1B should not be present in this state.
• Main advantage: only relevant actions are
considered.
39
slide 28: Forward State Space Planning
From ref book
44
slide 29: OnBA OnCB
A B
C
Initial state
Backward Planning
45
slide 30: OnBA OnCB
StackCB
OnBA HoldingC ClearB
ClearC OnCTable ClearA Handempty ClearB OnBTable
ClearC OnCTABLE HoldingB ClearA
StackBA
PickupB
PutdownC
ClearA ClearB OnBTable HoldingC
UnstackCA
ClearB OnBTable ClearC Handempty OnCA
PickupC
OnBA ClearB Handempty ClearC OnCTable
A B
C
Initial state
Backward Planning
46
slide 31: OnBA OnCB
StackCB
OnBA HoldingC ClearB
ClearC OnCTable ClearA Handempty ClearB OnBTable
ClearC OnCTABLE HoldingB ClearA
StackBA
PickupB
PutdownC
ClearA ClearB OnBTable HoldingC
UnstackCA
ClearB OnBTable ClearC Handempty OnCA
PickupC
OnBA ClearB Handempty ClearC OnCTable
A B
C
Initial state
Backward Planning
47
slide 32: Backward State Space Planning
• One way to take the goal state into account is to start searching
backwards from the goal. From ref book
48
slide 33: • Backward planning searches a space of goals
from the original goal of the problem to a goal
that is satisfied in the initial state
• There are often much fewer actions relevant to a
goal than there are actions applicable to a state
smaller branching factor than in forward planning
• The lengths of the solution paths are the same
Search Tree
50
slide 34: • Push the original goal to the stack. Repeat until
the stack is empty:
• GSP works by pushing the goal description onto the stack.
• It pushes both the conjunct as well as each of the
individual goal predicates separately. The algorithm pops
the element on the top of stack.
• If it is goal predicate that is true in the current state then nothing is
done and next element is popped from the stack.
• If it is goal predicate that is not true in the current state a relevant
action is pushed onto the stack followed by the preconditions
• The precondition on the top of the stack becomes the next subgoal to
be addressed recursively.
Goal Stack Planning
51
slide 35: Goal Stack Planning
52
slide 36: Goal Stack Planning
1. UNSTACKC A
2. PUTDOWNC
3. PICKUPA
4. STACKA B
5. UNSTACKA B
6. PUTDOWNA
7. PICKUPB
8. STACKB C
9. PICKUPA
10. STACKA B
Goal Stack Planning
53
slide 37: Goal Stack Planning
54
slide 38: • Any planning algorithm that can place two actions into a plan without
which comes first is a PO plan.
Plan Space Planning
55
slide 39: Constraint Satisfaction Problems
56
slide 40: • Constraint satisfaction problems CSPs
are mathematical problems defined as a set of objects whose
state must satisfy a number of constraints or limitations.
• CSPs are the subject of intense research in both artificial
intelligence and operations research.
• CSPs often exhibit high complexity requiring a combination
of heuristics and combinatorial search methods to be solved in a
reasonable time.
Constraint satisfaction problems CSPs
57
slide 41: Constraint satisfaction problems CSPs
• CSP:
A constraint satisfaction problem is defined as a three
V D C
Goal test is a set of constraints
• Standard search problem:
State of problem is defined by an assignment of values to
some or all variables.
Assignment that does not violate any constraint is called
consistent assignment.
58
slide 42: Constraint satisfaction problems CSPs
59
slide 43: Constraint satisfaction problems CSPs
60
slide 44: Constraint satisfaction problems CSPs
61
slide 45: Constraint satisfaction problems CSPs
62
slide 46: Constraint satisfaction problems CSPs
63
slide 47: Constraint satisfaction problems CSPs
64
slide 48: Constraint satisfaction problems CSPs
65
slide 49: Constraint satisfaction problems CSPs
66
slide 50: Constraint satisfaction problems CSPs
67
slide 51: Constraint satisfaction problems CSPs
68
slide 52: Constraint satisfaction problems CSPs
69
slide 53: Constraint satisfaction problems CSPs
70
slide 54: Example: Map-Coloring
Variables WA NT Q NSW V SA T
Domains D
i
redgreenblue
Constraints: adjacent regions must have different colors
e.g. WA ≠ NT or WANT in redgreenredbluegreenred
greenblueblueredbluegreen
71
slide 55: Example: Map-Coloring
Solutions are complete and consistent assignments e.g. WA
red NT greenQ redNSW greenV redSA
blueT green
72
slide 56: Backtracking example
74
slide 57: Backtracking example
75
slide 58: Backtracking example
76
slide 59: Backtracking example
77
slide 60: Constraint propagation
Forward checking propagates information from assigned to unassigned
variables but doesnt provide early detection for all failures:
NT and SA cannot both be blue
Constraint propagation repeatedly enforces constraints locally
78
slide 61: Arc consistency
Simplest form of propagation makes each arc consistent
X Y is consistent iff
for every value x of X there is some allowed y of Y
79
slide 62: Arc consistency
Simplest form of propagation makes each arc consistent
X Y is consistent iff
for every value x of X there is some allowed y of Y
80
slide 63: Arc consistency
Simplest form of propagation makes each arc consistent
X Y is consistent iff
for every value x of X there is some allowed y
If X loses a value neighbors of X need to be rechecked
81