V R Siddhartha Engineering College

Department of Computer Science & Engineering

Problems, Problem Spaces, and Search

Chapter 2
Steps involved to build a system, to solve a
particular problem

• Define the problem precisely.

• Defining initial states & what final states constitutes the
solution
• Analyze the problem.

• Isolate and represent the task knowledge that is

necessary to solve the problem.

• Choose the best problem solving technique and apply it

to the particular problem.
Defining the problem as State Space Search

Problem = Searching for a goal state

❖ Playing Chess

❖ Water Jug Problem

State Space Search: Playing Chess

• Each position can be described by an 8-by-8 array.

• Initial position is the game opening position.
• Goal position is any position in which the opponent
does not have a legal move and his or her king is
under attack.
• Legal moves can be described by a set of rules:
− Left sides are matched against the current state.
− Right sides describe the new resulting state.
Playing Chess ?

• State space is a set of legal positions.

• Starting at the initial state.
• Using the set of rules to move from one state to another.
• Attempting to end up in a goal state.
‘State Space’
k
r k b q b k r
i
p p p p p p p p

Initial state

P P P P P P P P
R K B
•K Q B K R operators
I
p p

Goal state(s) q
K
I
 How rules can be stated ?

1. Specifying all board positions

2 problems
(i) No person could supply a complete set of such rules
(ii) No program could easily handle all those rules.
10120 board positions
i.e difficulty in searching
storage
 How rules can be stated ?

2. Specifying in general way

white pawn at
square(file e, rank 2)
AND Move pawn from
Square(file e, rank 2)
square(file e, rank 3)
to
is empty
Square(file e, rank 4)
square(file e, rank 4)
is empty
Contd..

• The problem, play chess, has been described as a problem of

moving around in a state space; where each state
corresponds to a legal position of the board.
• Starting from initial state and using a set of rules to move
from one state to another can give rise to one of a set of
final states.
• The combination of all these states gives rise to what is
called the state space.
Contd..

• The playing of chess is a simple example of problem solving,

as the board states here are well organized (structured).
• The 8-puzzle problem is also equally structured. The same
kind of state representation can also be used in the case of
less structured problems, although it may be necessary to
use more complex structures than a matrix (array) used
here, to describe the state.
Contd..

• In order to show the generality of state space representation let us

take another problem Water Jug Problem which is stated as…
State Space Search: Water Jug Problem

We are given 2 jugs,

• a 4-litre one and
• a 3-litre one.

• Neither has any measuring markers on it.

• There is a pump that can be used to fill the jugs with water.

How can you get exactly 2 litres of water

into 4-litre jug?
State Space Search: Water Jug Problem

• State space for water-jug problem is described as…

• State: (x, y)

∍ x = 0, 1, 2, 3, or 4, and y = 0, 1, 2, 3
• Start state: (0, 0).
• Goal state: (2, n) for any n.
• Attempting to end up in a goal state.
 ● Possible operators:
1. We can fill a jug from the tap.
2. We can pour water out of a jug on to the ground.
3. We can pour water from one jug to another.

Operator/rule: includes information about

what must be true in the world before the action can take place
and how the world is changed by the action.
Water Jug Problem

“Operators” to be used to solve the problem, represented as

rules…
1. (x, y) → (4, y)
Fill the 4-gallon jug
if x < 4
2. (x, y) → (x, 3) Fill the 3-gallon jug
if y < 3
3. (x, y) → (x − d, y) Pour some water out of the
if x > 0 4-gallon jug

4. (x, y) → (x, y − d) Pour some water out of the

if y > 0 3-gallon jug
Water Jug Problem

5. (x, y) → (0, y) Empty the 4-gallon jug on

if x > 0 the ground

6. (x, y) → (x, 0) Empty the 3-gallon jug on

the ground
if y > 0
Pour water from the
7. (x, y) → (4, y − (4 − x)) 3-gallon jug into the
if x + y ≥ 4, y > 0 4-gallon jug until the
4-gallon jug is full
8. (x, y) → (x − (3 − y), 3) Pour water from the
if x + y ≥ 3, x > 0 4-gallon jug into the
3-gallon jug until the
3-gallon jug is full
Water Jug Problem
9. (x, y) → (x + y, 0)
Pour all the water from
if x + y ≤ 4, y > 0 3-gallon jug into the
4-gallon jug
10. (x, y) → (0, x + y)
Pour all the water from
if x + y ≤ 3, x > 0 4-gallon jug into the
3-gallon jug
11. (0, 2) → (2, 0)
Pour the 2 gallons
from the 3-gallon jug
into the 4-gallon jug
12. (2, y) → (0, y)
Empty the 2 gallons
in the 4-gallon jug
on the ground
Water Jug Problem ?
1. current state = (0, 0)
2. Loop until reaching the goal state (2, 0)
− Apply a rule whose left side matches the current
state
− Set the new current state to be the resulting state

(0, 0) (0, 3) (3, 0) (3, 3)

(4, 2) (0, 2) (2, 0)
Speed ?
depends on the mechanism that is used to select the next
operation to be performed.

⮚There are several sequences of operators that solve the

problem, But we look for
Cheapest/shortest or maximized
depending on the problem.
Contd..

In order to describe the operators completely here are some

assumptions, not mentioned, in the problem state.
•1. We can fill a jug from the pump.
•2. We can pour water out a jug, onto the ground.
•3. We can pour water out of one jug into the other.
•4. No other measuring devices are available.
All such additional assumptions need to be given when
converting a problem statement in English to a formal
representation of the problem, suitable for use by a program.
Contd..

• To solve the water jug problem, all we need, in

addition to the problem description given above, is
a control structure which loops through a simple
cycle in which some rule whose left side matches
the current state is chosen, the appropriate change
to the state is made as described in the
corresponding right side and the resulting state is
checked to see if it corresponds to a goal state.
Contd..

• The loop continues as long as it does not lead to the

goal.
• The speed with which the problem is solved
depends upon the mechanism, control structure,
which is used to select the next operation.
Contd..

• Thus, the state space representation forms the basis of most

of the AI methods for problem solving.
Its structure corresponds to the structure of problem solving,
conforming to the following two steps:
(a) Converts the given situation into some desired situation
using permissible operations.
(b) Combines the known operators, each representing a rule
defining a single step, in the space.
• Thus, the general technique of exploring the space is to try
to find some path from the current state to a goal state.
Water Jug Problem

• It has been shown above how an informal problem state (stated in

English) has been converted into a formal one with the help of a
water jug problem.
Water Jug Problem

Issues that arise in converting an

informal problem statement to formal problem statement

1st
The role of the conditions in the left side of the
rules.
⇒ restrict the application of the rule
⇒ more efficient
1. (x, y) → (4, y)
if x < 4
2. (x, y) → (x, 3)
if y < 3
Contd..

• The rules should be stated explicitly and not written because they are
allowable.
• For example, the first rule states that “Fill the 4-gallon jug”, but it should
have been written as “if the 4-gallon jug is not already full, fill it” but the
rule in its stated form is not wrong as there is no condition that the
already filled jug cannot be filled (may be after emptying).
• No doubt this is physically possible but not wise; as this won’t change
the problem state.
• In order to increase the efficiency of the problem solving program, it is
imperative to encode some constraints in the left side of the rules so
that the rules should lead to a solution that is the rules should be made
more general.
2nd should they or should they not be included in the list of
available operators? i.e RULES 3 & 4

3. (x, y) → (x − d, y) Pour some water out of the

if x > 0 4-gallon jug

4. (x, y) → (x, y − d) Pour some water out of the

3-gallon jug
if y > 0

• Emptying an unmeasured amount of water onto the ground

is certainly allowed by the problem statement, but do these
rules lead us near to a solution. The answer is ‘no’ so these
can be ignored.
• So, such rules which are really applicable to the problem in
arriving at the solution should be considered.
Contd..

Including…
will never get us any closer to a solution.

∴trade off between

- writing a set of rules that describe just the problem
itself.
And
- writing a set of rules that describe both the
problem and some knowledge about its solution.
State Space Search: Water Jug Problem
i.e RULES 11 & 12
3rd Special-purpose rules, written to capture special-
case knowledge that can be used at some stage
in solving a problem

11. (0, 2) → (2, 0) RULE 9

12. (2, y) → (0, y) RULE 5

Contd..

• Consider the last two steps of the solution, once the state (4,
2) is reached it is obvious what to do next? The desired 2-
gallons have been produced, but they are in a wrong jug.
• Move 2-gallons of water to 4-gallon jug-rule 11 (or rule 9).
• But before that the water already in 4-gallon jug need to be
emptied, rule 12 (or rule 5).
• These two special purpose rules do not help in solving the
problem since the operators they describe are already
provided by rules 9 and 5 respectively, so could have been
avoided.
• Sometimes special rules improve performance if preference
is given to special case rules.
Until now we have discussed 2 different problems, by now it should
be clear that,
1st step toward the design of a program to solve a problem must
be…
the creation of formal and manipulable description of the
problem itself.

Operationalization ?
The process of writing programs, that can themselves
produce formal descriptions from informal ones.
Inorder to provide a formal description of a problem, we must do the
following…

1.Define a state space that contains all the possible

configurations of the relevant objects.
2.Specify one or more states within that space that describe
possible situations from which the problem solving
process may start, called as INITIAL states.

3.Specify one or more states that would be acceptable as

solutions to the problem, called as GOAL states.

4.Specify a set of rules that describe the actions(operators)

available. Giving thought to the following issues…
- what unstated assumptions are present in the informal problem description.
- how general should the rules be?
- how much of the work required to solve the problem should be
precomputed and represented in the rules.
Contd..

• The problem can be solved by collecting all knowledge of the problem,

(in the present case, water jug problem) with the help of production
rules and using an appropriate control strategy; move through the
problem space until a path from an initial state to goal state is found.
• This is the process of search which is fundamental to the problem
solving process.
• Since search provides the core of many intelligent processes, it is useful
to structure AI program in a way which facilitates describing and
performing the search process.
How problem can be solved?
- using rules. and
- control strategy (to move through the problem space until a path from
an initial state to a goal state is found )

SEARCH ?
- is fundamental to the problem solving process
- is a general mechanism that can be used when no more direct
method is known.
PRODCUTION
SYSTEMS
Production system consists of …
1) a set of rules, each consisting of
a LEFT side: that determines the applicability of the rule.
a RIGHT side: that is a result of the application of the rule.

2) one/more knowledge/data bases

contains what ever information is appropriate for the particular
task, structured in any appropriate way.

3) a control strategy, specifies

- The order in which the rules will be compared to the database.
- A way of resolving conflicts that arise when several rules
match at once.

4) a RULE supplier.
 Control strategies

Decide which rule to apply next, when more than one state have its
left side match the current state. Which have a crucial impact on…

- How quickly the problem is solved.

- Whether the problem is finally solved or not.

Requirements of a good control strategy ?

1. It cause motion
2. It be systematic
- for global motion
- for local motion

not systematic (choosing rules at RANDOM):

likely to arrive at the same state several times.
 Search Strategies
1. Uninformed search/blind search / Brute Force Techniques
1. where you generate and try out every possible solution may work.
2. Having no information about the number of steps from the current
state to the goal.
3. often very inefficient, as there are just too many possibilities to try.
4. Do not need ‘domain knowledge’.

2. Informed search/Heuristic search

5. where you only try the options which you think (based on your current
best guess) are most likely to lead to a good solution.
6. More efficient than uninformed search.
7. Guiding the search with domain knowledge.
Search Strategies: Blind Search

• Breadth-first search
Expand all the nodes of
one level first.

• Depth-first search
Expand one of the nodes at
the deepest level.
 Systematic control strategy
•Construct a tree with the initial state as its root.
•Generate all the offspring of the root by applying each
of the applicable rules to the initial state.
R1 R2 R3
•For each leaf node, generate all its successors by
applying all the rules that are appropriate.
• Continue this process until some rule
produces a goal state.

( Breadth first search )

 Systematic control strategy for the water jug problem

(0,0)

(4,0) (0,3) 1st-level of BFS

(4,3) (0,0) (1,3) (4,3) (0,0) 2( nd3-level

, 0 ) of BFS
 The Water Jugs Problem – Search Tree

0,0

0,3 4,0

0,0 4,3 3,0 4,3 1,3 0,0

4,0 0,3 4,0 3,3 0,3 0,0 4,0 0,3 1,0 0,3 4,3

0,3 3,0 4,2 4,3 4,0 0,1 1,3 0,0

4,0 3,3 0,2 4,3 0,0 4,1 1,0

0,0 4,2 2,0 0,3 0,1 4,0 3,3 4,3

 Breadth first search : Algorithm

1. Create a variable called NODE-LIST and set it to the initial state.

2. Until a goal state is found or NODE-LIST is empty do:

a) remove the first element from NODE-LIST and call it E.
if NODE-LIST was empty, quit.
b) for each way that each rule can match the state described
in E do:
i) apply the rule to generate a new state.
ii) if the new state is a goal state, quit and return this state.
iii) otherwise, add the new state to the end of NODE-LIST.
Other systematic control strategies… : DFS

pursue a single branch of the tree

- until it yields a solution or
- until a decision to terminate the path is made.

When to terminate?
• If it reaches dead-end.
• Produces a previous state.
• Path becomes longer than some prespecified “futility” limit.
⇒ Backtracking
backtracking:
the most recently created state from which alternative moves are
available will be revisited and a new state will be created. Called
as chronological backtracking.
Why named as chronological backtracking?
Because, the order in which steps are undone depends only on the
temporal sequence in which the steps were originally made.

There are other ways of retracting steps of computation….

dependency-directed
backtracking(ch7)
 Depth-First Search : Algorithm

1. If the initial state is a goal state,quit and return success .

2. Otherwise ,do the following until success or failure is signaled:

(a) Generate a successor,E,of the initial state, If there
are no more successors,signal failure .
(b) Call Depth-First Search with E as the initial state .
(c) If success is returned, signal success.
Otherwise continue in this loop .
Blind Search – Breadth First
0,0

0,3 4,0

4,3 3,0 4,3 1,3

3,3 1,0

4,2 0,1

0,2 4,
1
2,
0
Blind Search – Depth First
0,0

0,3

4,3 3,0

4,0 3,3

4,2

0,
2
2,
0
Breadth-first vs. depth-first

• Depth-first:
• Requires less memory. Since only the nodes on the
current path are stored.
• May find a solution without searching much of the search
space

• Breadth-first:
• Will not get trapped exploring a blind alley
• Will find minimal solution (if more than one exist)
 Search Strategies: Heuristic Search
(The Travelling Salesman Problem)
⮚A salesman has a list of cities.
⮚Each of which he must visit exactly once.
⮚There are direct roads between each pair of cities on the list.

Find the route the salesman should follow for the

shortest possible round trip that both starts and
finishes at any one of the cities.
T Salesman problem
simple way:
explore all paths in the graph and return the one
with the shortest length. But breaks down as the
no.of cities grow. (for N nodes: N! paths)
i.e suffer from combinatorial explosion.

Combinatorial explosion?
The phenomenon of taking more time to solve the
problem than he would be willing to spend.

∴ a new control strategy, Branch-and-bound technique

begin generating complete paths, keeping track of the shortest
path found so far. Give up exploring any path as soon as its
partial length becomes greater than the shortest path found so
far.
 Heuristic search (incorporate domain knowledge)

- Heuristic is a technique that improves the efficiency of a search process.

- Heuristic search use some function that estimates the cost from the
current state to the goal.
General purpose Heuristics:
Nearest neighbor Heuristic
-Works by selecting the locally superior alternative at
each step.
- Useful for a variety of combinatorial problems.
Ex: Travelling salesman problem.
1. Select a starting city.
2. Out of all cities not yet visited, Select the one closest to
the current city.
3. Repeat step 2 until all cities have been visited.

Special purpose Heuristics:

Exploit domain specific knowledge to solve particular problems.
There are two major ways in which domain specific heuristic
knowledge can be incorporated into a rule based search
procedure.
1. In the rules themselves. Ex: Chess Playing
Rules might describe not simply the set of ‘legal’
moves but rather a set of ‘sensible’ moves.
2. As a heuristic function that evaluates individual problem
states and determines how desirable they are.
Well designed heuristic functions guide a search
process towards a solution.
Problem Heuristic function
Chess, Tic-Tac-Toe Advantage of our side over the
opponent (High value)
Travelling Salesman The sum of the distances so far
(low value)
Purpose of Heuristic function?
Is to guide the search process in the most profitable direction by
suggesting which path to follow first when more than one is
available.
Problem characteristics
Heuristic search is a very general method encompasses a
variety of specific techniques.
Inorder to choose a particular method for a
potential problem, it is necessary to analyze the problem
along several key dimensions.
 Problem Characteristics
key dimensions:
To choose an appropriate method for a particular problem.

1. Is the problem decomposable?

2. Can solution steps be ignored or undone?
3. Is the universe predictable?
4. Is a good solution absolute or relative?
5. Is the solution a state or a path?
6. What is the role of knowledge?
7. Does the task require human-interaction?
1. Is the problem decomposable?

• Can the problem be broken down to smaller

problems to be solved independently?

• Decomposable problem can be solved easily.

1. Is the problem decomposable?

❖ Symbolic integration ( decomposable – independent)

∫(x2 + 3x + sin2x.cos2x)dx

∫x2dx ∫3xdx ∫sin2x.cos2xdx

∫(1 − cos2x)cos2xdx
X3/3 3 ∫xdx
∫cos2xdx ∫cos4xdx

3x2/2
1. Is the problem decomposable?

❖ Blocks World Problem ( nondecomposable – not independent)

Start Goal A
: :
C B
A B C

ON(C,A) ON(B,C) and ON(A,B)

Operators available are …

CLEAR(x) → ON(x, Table)
CLEAR(x) and CLEAR(y) → ON(x, y)
Decomposing the problem into
getting B on C and A on B , to 2 separate problems

The two problems are not independent.

They interact and those interactions must be considered in order to arrive at a

solution for the entire problem.
2. Can solution steps be ignored or undone?
❖ Theorem Proving
A lemma that has been proved can be ignored for
next steps.
⮚ Ignorable!
2. Can solution steps be ignored or undone?

❖ The 8-Puzzle

2 8 3 1 2 3
1 6 4 8 4
7 5 7 6 5
Moves can be undone and backtracked.

⮚Recoverable!
2. Can solution steps be ignored or undone?

❖ Playing Chess
Moves cannot be retracted.

⮚ Irrecoverable!
2. Can solution steps be ignored or undone?

• Ignorable problems can be solved using a simple control

structure that never backtracks.
• Recoverable problems can be solved using backtracking.

can be solved by recoverable style

• Irrecoverable problems
methods via planning.
 Recoverability of the problem plays an important role in
determining the complexity of the control structure necessary
for the problems solution.
 Important classes of problems

1. Ignorable problems
Ex: Theorem Proving
--- in which solution steps can be ignored.
--- solved using a simple control structure that never backtracks.
--- such a control structure is easy to implement
2. Recoverable Problems
Ex: 8-Puzzle
--- in which solution steps can be undone.
--- solved by a straight more complicated control strategy.
--- backtracking will be necessary to recover from such mistakes.
∴ control structure must be implemented using a
pushdown stack
3. Irrecoverable problems
Ex: Chess
--- in which solution steps can’t be undone.
--- solved by a system that expends a great deal of effort
making each decision, since the decision
must be final.

Note: Some irrecoverable problems can be solved by

recoverable style methods used in a “planning” process.
In which an entire sequence of steps is analyzed in advance to discover
where it will lead before the first step is actually taken.
3. Is the universe predictable?

❖ The 8-Puzzle
Every time we make a move,
we know exactly what will happen.

⮚ Certain outcome!
 3. Is the universe predictable?

❖ Playing Bridge
We cannot know exactly where all the cards are
or what the other players will do on their turns.

⮚ Uncertain outcome!
 3. Is the universe predictable?

• For certain-outcome problems, planning can be

used to generate a sequence of operators that is
guaranteed to lead to a solution.
• For uncertain-outcome problems, a sequence of
generated operators can only have a good
probability of leading to a solution.
Plan revision is made as the plan is carried
out and the necessary feedback is provided.
The 2 problem characteristics
recoverability, certainity interact…

solving irrecoverable problems ?

- Plan an entire solution before embarking on an
implementation of the plan.
- But, this planning process can only be done effectively
for certain outcome problems

Hardest types of problems?

Irrecoverable, uncertain problems.
Ex: Playing Bridge.
Controlling a Robot arm.
4. Is a good solution absolute or relative?

1. Marcus was a man.

2. Marcus was a Pompeian.
3. Marcus was born in 40 A.D.
4. All men are mortal.

5. All Pompeians died when the volcano erupted in 79 A.D.

6. No mortal lives longer than 150 years.
7. It is now 1991 A.D.

Is Marcus alive ?
 Is Marcus alive?
Different reasoning paths lead to the answer. It does not matter which path we follow.

Path 2
Path 1
⮚ Absolute
( since, we are not going to compare a path with other paths, which may find an answer)

1. Marcus was a man. axiom 1 7. It is now 1991 A.D. axiom 7

4. All men are mortal. axiom 4 5. All Pompeians died in 79 A.D axiom 5
8. Marcus is mortal. 1,4 11. All Pompeians are died now. 7,5
3. Marcus was born in 40 A.D. axiom 3 2. Marcus was a Pompeian. axiom
7. It is now 1991 A.D. axiom 2
7 12. Marcus is died. 11,2
9. Marcus’ age is 1951 years. 3,7
6. No mortal lives longer than 150 years axiom 6
10. Marcus is dead. 8,6,9
4. Is a good solution absolute or relative?

❖ The Travelling Salesman Problem

We have to try all paths to find the shortest one.

New
Boston Miami Dallas S.F.
York
Boston 250 1450 1700 3000
New
250 1200 1500 2900
York
Miami 1450 1200 1600 3300
Dallas 1700 1500 1600 1700
S.F. 3000 2900 3300 1700
 Boston

New
San Francisco York

Dallas Miami

New
Dallas
York

Miami San Francisco

Two Paths Among The Cities

Boston Boston
Total(8850) Total(7750)
 Travelling salesman problem
• A salesman must visit 5 cities exactly once.
• What is the shortest route?

Aberdeen Brighton Cardiff Dover Edinburgh

Aberdeen 0 594 524 619 127

Brighton 594 0 184 78 467
Cardiff 524 184 0 233 395
Dover 619 78 233 0 493
Edinburgh 127 467 395 493 0
Heuristic Search
• heuristic = rule of thumb

5
A
1
9 2
5 6
B 4 C 2 1 D 7 E
4 9 4 4
3 9
6
B 7 C9 3 D
5
1 2
8 3
4B D3
7
8
784 D
4. Is a good solution absolute or relative?

• Any-path problems can be solved using heuristics that suggest

good paths to explore.
• For best-path problems, much more exhaustive search will be
performed.
5. Is the solution a state or a path?

❖ Finding a consistent interpretation (state)

“The bank president ate a dish of pasta salad with the fork”.

• “bank” refers to a financial situation or to a side of a river?

• “dish” or “pasta salad” was eaten?
• Does “pasta salad” contain pasta, as “dog food” does not contain
“dog”?
• Which part of the sentence does “with the fork” modify?
What if “with vegetables” is there?

No record of the processing is necessary.

5. Is the solution a state or a path?

❖ The Water Jug Problem ( path )

The path that leads to the goal must be reported.
6. What is the role of knowledge
❖ Playing Chess
Knowledge is important only to
constrain the search for a solution.

❖ Reading Newspaper
Knowledge is required even to be able to
recognize a solution.
7. Does the task require human-interaction?

• Solitary problem, in which there is no intermediate

communication and no demand for an explanation of the
reasoning process.

• Conversational problem, in which intermediate

communication is to provide either additional assistance to
the computer or additional information to the user.
Problem Classification
• There is a variety of problem-solving methods, but there is
no one single way of solving all problems.

• Not all new problems should be considered as totally new.

Solutions of similar problems can be exploited.
Production System Characteristics
Production systems are good way to describe the operations
that can be performed in a search for a solution to a problem.
Questions:
1. Can production systems described by a set of characteristics?
Ans: yes. ( as that of problems )
If so,
2. what relationships are there between
problem types Types of production systems
 1. Classes and Production systems
a) Monotonic production system:
is a production system in which the application of
a rule never prevents the later application of another rule
that could also have been applied at the time the first rule
was selected.
b) Nonmonotonic production system:
One in which this is not true.
c) Partially commutative production system:
A production system with the property that if the
application of a particular sequence of rules transforms
state X into state Y then,
any permutation of those rules that is allowable also
transforms state X into state Y.
d) Commutative:
This can satisfy the properties of monotonic and partial
commutative.
 Monotonic Non Monotonic
Partially
Theorem Proving Robot Navigation
Commutative

Not Partially Chemical Bridge

Commutative Analysis
Partially Commutative , Monotonic PS
- Used for solving ‘ignorable problems’
- These are implemented without backtracking
⇒ increase in efficiency
- Good for problems where
Things do not change
New things get created

Ex: Theorem proving

Making deductions
Partially Commutative, Nonmonotonic PS
Useful for problems in which changes occur but can be
reversed and in which order of operation is not critical.
Ex: Robot Navigation on a flat plane
N-N-E=N-E-N
8 - puzzle
Blocks world problem
Both types of partially commutative production systems
-lead to duplication of individual states during the
search process.
Not Partially Commutative
-Useful for problems in which irreversible changes occur.
Ex: Problem of determining a process to produce a
desired chemical compound.
The order in which the operations are performed is very
important in determining the final output.

(x+y) + z != x + (y+z)
planning can be used to take correct decisions

Non partially commutative production systems are less likely to

produce the same node many times in the search process.