Problem space

AI

2. Problem
Defining problem in state space
Production system
Characteristics of production system
Control strategy
Search Space algo’s
◦Breadth first Search
◦Depth first search
◦Heuristic Search
Problem Characteristics

3. Any task to be done or goal to be achieved.
A problem can be solved by
◦Defining configuration of problem precisely.
◦Analyzing the problem
◦Defining essential features – which can have an
impact on accuracy of problem solving
techniques.
◦Defining knowledge to solve a particular problem
◦Applying best possible technique to solve it.

4. A problem should be defined in state space,
which will include
◦Initial state – Starting position in chess
◦Legal possible Solutions – Possible moves in chess
◦Goal state – Not only playing but also winning
◦Rules applicable
•But it tough to state all the rules correctly and will
cause some storage problem also.

5. We have 2 jugs, one of 4-gallon, second of
3-gallon. No measurement or no marking is
there on jugs. We have fill 4-gallon jug with
2 gallon water.
Assumptions
◦X  range from 0 to 4 for 4-gallon jug
◦Y  range from 0 to 3 for 3-gallon jug
◦We can fill water through pump.
◦We can pour waste water on ground.
◦We can put water from one jug to another.

6. Initial state – (X, Y) = (0, 0)
Goal State – (X, Y) = (2, n)
Production system –
◦(x, y) ResultDescription
◦If(x<4) (4, y) Fill X jug in full
◦If(y<3) (X, 3) Fill Y jug in full
◦If(x>0) (X-d, Y) Take some water out
of X jug
◦If(y>0) (X, Y-d) Take some water out
of Y jug

7. ◦(x, y) Result Description
◦If(x>0) (0, Y) Empty 4 gallon jug
◦If(Y>0) (X, 0) Empty 3 gallon jug
◦If(x+y>=4, y>0) (4, y-(4-x))Put some water
in 4 from 3 gallon jug to fill it up.
◦If(x+y>=3, x>0) (x-(3-y), 3)Put some water
in 3 from 4 gallon jug to fill it up.
◦If(x+y<=4, y>0) (x+y, 0)Put all water in 4 from
3 gallon jug to fill it up.
◦If(x+y<=3, x>0) (0, x+y)Put some water in 3
from 4 gallon jug to fill it up.

8. ◦(x, y) Result Description
◦(0, 2) (2, 0) Put water from 3 gallon
jug to 4 gallon jug
◦(2, Y) (0, Y) Empty 4 gallon jug by
dropping water on ground.
•Problems are
if jugs are already filled then 1, 2 rules
Take some water out of jugs, but we are supposed to
add water (3, 4)
If we are with 2 gallon jug at end then what is the need
to go for 11, 12 rule

9. 4- Gallon jug3- Gallon jugRules
0 0
0 3 2
3 0 9
3 3 2
3+1=4 3-1=2 7
0 2 11
2 0

10. 4- Gallon jug3- Gallon jugRules
0 0
4 0
4-3=1 0+3=3
1 0
0 1
4 1
4-2=2 1+2=3

11. A structure that helps in describing and
performing search in order to solve a
problem is known as production system.
It contains
◦Rules to follow
◦LHS shows current situation
◦RHS shows resulting state after applying the rule
on current state.
◦Database describing rules, Information regarding
rules can be temporary or permanent.

12. Control strategy to specify order of rules
which are applicable.
A rule applier like a chess player.
Example production systems are:
◦Basic production system like OPS5.
◦Complex and Hybrid systems known as expert
system shells to generate knowledge based
systems.
◦General problem solver system like SOAR

13. Control strategy specifies the order of
essential rules which should be followed to
solve a particular problem.
Control Strategies can be of 2 types
◦Movable strategies: Strategies should have motion
like in water jug problem, every time we have to
start from first rule. But if first rule is not applicable
then we will not be able to move further.

14. ◦Systematized: It should have some system or order
to be followed. If water jug problem can be solved
by picking random rules and repeating rules then
that could have motion but again no order to be
followed.
◦Motion should be local as well as global

15. Breadth first search: Representing water jug
problem starting with its initial state along
with its off springs i.e. various possible
solutions until for reaching a goal state.
◦It gives local as well as global motion.
Depth first search: One node of tree is
explored until either dead end or goal state
is not found.
◦In case of dead end chronological back tracking is
done to explore various other ways to solve that
problem. It also keeps current searching path in
memory.

16. library
school
hospital
factory
park newsagent
university
church
Explore nodes in tree order: library, school,
hospital, factory, park, newsagent, uni, church.
(conventionally explore left to right at each level)

17. Nodes explored in order: library, school,
factory, hospital, park, newsagent,
university.
library
school
hospital
factory
park newsagent
university

18. 0, 0
4, 0 0, 3
4, 3 0, 0 1, 3 4, 3 0, 0 3, 0
Initial state
One level BFS
Second level BFS
1.Create a variable node list and specify it with its initial state.
2.Take first node from node list, if it is empty go for quit else generate its
successors.
3.For every successor: generate a new state, apply rule
1.If it is a goal state return success and quit else add new state to a
new list.
This is supposed to be done until or unless solution is found or node list
is empty.

19. It does not takes us to the blind way.
It will definitely give us the solution, if that
exists.
It gives us solution with minimum value.
It guarantees that a solution with minimum
value will be explored first, only at last all
nodes with maximum values will be explored.

20. 0, 0
4, 0
4, 3
Initial state
Subordinates
1.Create a variable node list and set it to initial state, If it is a goal state then
return success and quit, else chose one node n from node list.
2.Mark it as initial state, If it is empty then return failure and quit.
3.Otherwise apply an operator to generate its successor, if it is a goal state
return success and quit.
4.Otherwise continue the loop until solution is not found.

21. Advantages:
◦It takes less memory as compared to BFS as BFS
requires entire tree to be stored but this requires
only one path.
◦Sometimes solution lies in earlier stages then DFS is
better.
◦If there are multiple solutions then DFS stops when
first solution is found. Where as BFS gives all the
solutions at the same time.

22. Disadvantages:
◦Sometimes it gives dead
end after searching a lot.
◦It can or cannot give
solution to a problem.
Traveling Salesman
Problem
A B  C  D  A =
5700
A  D  C B  A =
5450 (Best path)
CIT
IES
ABCD
AX250140
0
900
B650180
0
200110
0
CX200
0
360
0
400
0
D125
0
X190
0
600

23. In order to solve hard problems, we have to
lack mobility or system.
Some techniques are good enough to choose
area of some ones interest.
Some are bad enough to lack interest.
For some solutions, we have to lack
completeness and accuracy.

24. Simple or General heuristic functions are
applicable in every domain.
◦It can be used for having optimal solution.
◦For having deep understanding of knowledge and
problem.
◦Where a large problem is not decomposable into
smaller parts.
◦If value of x and y is same then what will be the
value of F(x, y).
Square if f is for multiplication.
Identity if f is a union function.
Suicide if f is a killing function.
.

25. Special heuristic functions are for complex
problems eg. Nearest neighbor is used to
solve salesman problem.
◦They can be used as a rule itself
◦As a heurist function, which gives description of
state as well as its desirability.
◦Chess  High value of heuristics
◦Tic-Tac-Toe  High value
◦Salesman  Low value.

26. Is problem
decomposable or not?
◦If problem can be solved
immediately then its ok,
otherwise if
decomposable then
decompose it into simpler
one, else apply some
hard technique.
Is problem undone or
not?
◦Chess  cannot undone
(irrecoverable)
◦Puzzle  can be undone
(recoverable)
2 8 3
1 6 4
7 5
1 2 3
8 4
7 6 5
Initial state
Goal state

27. Is universe predictable: solutions or moves
predictable in advance or not?
◦In case of card game we cannot predict what is in
opponents hand and what would be his reaction
after our show. We can move according to our
choice.
◦Some problems are uncertain and undone, for
them planning leads to high cost and time.
◦Controlling a robot arm  uncertain
◦8 Puzzle  certain
◦Depending a client against murder charge is 
uncertain.

28. Is good solution a solution or a way to the solution?
◦Each state opted for solving a problem must have
interaction with next or previous states.
◦Eg. A bank president ate a dish of pasta salad with fork.
◦Natural language understanding and numerical problems
can better distinguish between a state or a solution.
What is the role of the knowledge?
◦How much knowledge is required like chess requires only
knowledge of legal and possible moves
◦Which newspaper supports republicans or democrats
requires high knowledge.

29. If problem requires interaction or not?
◦How much interaction between user and a system
is required?
◦Interaction can be for taking input, giving output,
taking or giving instructions, updating knowledge
base.
Is a good solution absolute or relative?
◦If we know initial state, goal state to be achieved
and instructions to be followed then solution would
be absolute else relative.

30. To which classification a problem belongs:
Like Medical or Mechanical.

31. 1.Marcus is a man
2.All men are mortal.
3.Marcus is a pompien.
4.All pompiens died in volcano in 79 AD.
5.No mortal can live more than 150 years.
6.It is now 1991.
7.Marcus born in 40 AD.
Q:  Is Marcus alive?

32. Monotonic
Repetition of rules
is allowed
Non-Monotonic
No such Repetition
is allowed
Partially Commutative
If x gives y then
permutation of x also
gives y
Theorem Proving Robot Navigation
Non Partially
Commutative
It is both monotonic
and partial
commutative
Chemical Synthesis Bridge

33. Forward or Backward Reasoning i.e from
Initial to goal state or vice versa.
Rule Matching: applying rule to initial state
and moving on to the goal state.
Representation of knowledge can be in frame,
fact or Script format.

34. 0, 0
4, 0 0, 3
4, 3 0, 0 1, 3 4, 3 0, 0 3, 0
Search Tree
Search Graph
0, 0
4, 0 0, 3
4, 3 0, 0 1, 3 4, 3 0, 0 3, 0
0,0 is appearing 2 times and it is one of our previous state
so instead of repeating it we just linked it. It requires a
small book-keeping which is called a graph.

35. Check for new node, if it already exists then
just point to the already existing.
Otherwise add it to the graph.
If it already exists then
◦Set a pointer pointing to that previous node.
◦Keep track of all the paths and select the best path
out of all generated paths and record them.
Advantages:-
It saves our time
It is useful for dealing with partial
commutative systems.

36. Missionaries and Cannibals problem.
Tower of Hanoi.
Monkey and Banana’s Problem
Crypt arithmetic problem:
◦SEND + MORE=MONEY
◦DONALD + GERALD=ROBERT
◦CROSS + ROADS=DANGER.

37. If problem satisfies all the above
characteristics then we can best answers in
less time with less cost.
This is the main aim of AI.