State space representation and search.pdf

Topics covered:
1. State space representation
2. Concept of Search

1. State space representation
& Concept of Search
By:
Vijeta Rani
Delhi Technological University
©Delhi Technological University 2024

2. Requirements to solve a problem
To build a system to solve a particular problem, we need four
things:
1Define the problem precisely.
2Analyze the problem.
3Isolate and represent the task that is necessary to solve the
problem.
4Choose the best problem solving technique(s) and apply it
(them) to the particular problem.

3. State space representaion of problems
A state space representation of a problem includes four things:-
1A state space
2An Initial State
3A goal state
4Operators

4. A State Space
A set of all possible states or configurations for a given problem is
known as the state space of the problem.
Note: It is possible to define this space without explicitly
enumerating all of the states it contains.

5. Initial state & Goal state
One or more states within a state space that describe the
possible situations from which the problem solving process may
start are called as initial states.
One or more state within a state space that would be acceptable
as solutions to the problem are called as goal states.

6. Operators
Operators are a set of rules that describe the actions available.
If a state space representation for a problem is given, it is
possible to trace the path from the initial state to the goal state
and identify the sequence of operators necessary for doing it.

7. Example Problem : Play Chess
"Initial State = 8 X 8 matrix with 16 black and 16 white pieces on
their appropriate squares.
"Goal state = Any board position in which the opponent doesn t
have any legal move and his/her king is under attack.
"The legal moves provide a path from an initial state to a goal
state. They can be described as a set of rules in which the left
side is current state and right side is next state after move.

9. Need of Generalisation of rules
"If we write rules for each of 16 pawns and other pieces on the
chess board separately, then there has to be a rule for each of
10
120
board positions, which is not easy to program.
"In order to minimise the number of rules, we should describe
the rules (legal moves) in as general form as possible.

11. State space in chess game
"A state space in the chess game is the set of all states, where
each state corresponds to a legal position (set up after a legal
move) of the board.
"Hence the problem of playing chess is a problem of moving
around in a state space.
"Hence solving a problem, can be described in terms of
searching across its space.

12. Example Problem: Water Jug
"Problem: You are given two jugs, a 4-gallon and a 3-gallon one.
Neither has measuring markes on it. There is a pump that can
be used to fill the jugs with water. How can you get exactly 2
gallons of water into the 4-gallon jug?
"The state space for this problem can be described as the set of
ordered pairs of integers (x,y) such that (x >=0 && x <=4) and
(y >=0 && y <=3), x represents the amount of water in 4-gallon
jug and y represents the quantity of water in the 3-gallon jug.

13. Water Jug & contd..
"Start state = (0,0)
"Goal state = (2,n)
"Necessary assumptions that are not mentioned in problem
statement:-
1. We can fill a jug from the pump
2. We can pour water of a jug onto the ground
3. We can pour water from one jug to another
4. There are no other measuring devices available.

17. Advantages of state space representation
"It allows for a formal definition of a problem as the need to
convert some given situation into some desired situation using
a set of permissible operations.
"It permits us to define the process of solving a particular
problem as a combination of known techniques and search.
"Search is the general technique of exploring the state space to
try to find some path from the current state to a goal state.
"Search is a very important process in the solution of hard
problems for which no direct techniques are available.

18. Limitations of state space representation
"It is not possible to visualize all the states for a given problem.
"The resources of the computer system are limited to handle
the huge state space representations.
"It doesn t provide the order of the search that can give a
solution to the problem.

19. Production systems
Production systems provide structures that facilitate describing
and performing the search process.
A production system consists of :-
1A set of rules
2One or more Knowledge/databases
3A control strategy
4A rule applier

20. Production system rules
"Forward rules: The left side determine the applicability of the
rule and the right side describes the operation to be
performed, if the rule is applied.
"Backward rules: The right side determine the applicability of
the rule and the left side describes the operation to be
performed, if the rule is applied.

21. Knowledge DB
"They contain the information appropriate for a particular task.
"Some parts of the DB may be permanent, while other parts of
it may pertain only to the solution of the current problem.
"The information in these DB may be structured in any
appropriate way.

22. Tasks of a Control Strategy
"It specifies the order in which the rules will be compared to the
DB.
"It decides which rule to apply next during the process of
searching for a solution to a problem.
"It provides a way of resolving the conflicts that arise when
several rules match at once.

23. Requirements of a good control strategy
"It causes motion : In water Jug problem, if we apply a simple
control strategy of starting each time at the top of the list of
rules and choosing the first applicable and then we will never
move towards solution.
"It is systematic: If we choose another control strategy saying
that choose at random from among the applicable rules then
definitely it cause motion and eventually will lead to a solution.
But this control strategy is not systematic. We may arrive at the
same state several times & thus waste time.

24. Forward vs Backward reasoning
"Forward Reasoning : Control strategy starts with known fact and
works towards a conclusion.
"Backward Reasoning: Goal directed control strategy. Begin with
final conclusion, draw sub goals, generate further sub goals until all
sub goals are satisfied.

25. 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.
(0,0)
(0,3)

(4,0)
Now for each leaf node, generate all its successors by applying all
the rules that are applicable:
Continue this process until some rules produces a goal state. This
process is called Breadth First Search
A Systematic control strategy

27. Breadth First Search
Step 1: Put the initial node on a list NODE-LIST
Step 2: If (NODE-LIST is empty) or (NODE-LIST= GOAL) terminate search
Step 3: Remove the first node from NODE-LIST . Call this node a
Step 4: If (a = GOAL) terminate search with success
Step 5: Else if node a has successors, generate all of them and add them at the tail of
NODE-LIST
Step 6: Goto Step 2

28. !’ one could pursue a single branch of the tree until it yields a
solution or some pre specified depth has been reached & only then
go back and explore other branches. This is called Depth first search.
!’ These are uniformed or blind search
Advantages of Depth First search
-Require less Memory
-May find a solution without exploring much of state space
Advantages of Breadth First search
- It is not blind i.e. it does not search a path which is unfruitful
- If there is solution it is found

29. Depth First Search
Step 1 : Put the initial node on a list NODE-LIST
Step 2: If (NODE-LIST is empty) or (NODE-LIST = GOAL) terminate search
Step 3: Remove the first node from NODE-LIST Call this node a
Step 4 : If(a=GOAL) terminate search with success
Step 5 : Else if a node a has successors , generate all of them and add them at the
beginning of NODE-LIST
Step 6 : Goto step 2

30. Traveling Salesman Problem
A salesman must visit each of the cities in his list exactly once. There
is a road between every pair of cities & the distance is given for every
road between two cities. The problem is to find a route of minimal
distance that visits each of these cities only once & return to the
starting city.

31. Solutions to Traveling Salesman Problem
"Solution 1:
Explore all possible path in the tree and choose the shortest one.
This solution is simple, motion causing and systematic. But this
approach takes exponential time to solve because there are (N-1)!
paths between the N cities.
"Solution 2: Branch and bound technique.

32. Branch and Bound Method
"Begin generating complete paths. Before generating a new path,
keep track of the shortest path found so far. Give up exploring any
new path as soon as its partial length becomes greater than
shortest path found so far.
"Although this algorithm is more efficient than the solution 1, it will
still require exponential time.

33. Heuristic Search
"A heuristic search is a technique that improves the efficiency
of a search process, possibly by sacrificing claims of
completeness like mobility and systematicity.
"A heuristic function is a function that maps from problem state
description to measures of desirability, usually represented as
numbers.

34. Nearest neighbour heuristic
"It works by selecting the locally superior alternative at each
step.
"Applying it to the traveling salesman problem, we get below
steps:-
1. Arbitrarily select a starting city.
2. To select the next city, look at all cities not yet visited and
select the closest to the current city. Go to it next.
3. Repeat step 2 until cities have been visited.
"It executes in time proportional to N
2
.

36. Benefits of heuristic search
" Good possible estimate of distance of the node from goal.
" Guide the search process toward solution.
" For real world problems, it is often useful to introduce heuristics
based on relatively unstructured knowledge. It is often impossible
to define this knowledge in such a way that mathematical analysis
can be performed.

37. Problem Characteristics
"Is problem decomposable?
"Can solution steps be ignored or undone?
"Is Universe predictable?
"Is a good solution absolute or relative?
"Is the solution a state or a path?
"What is the role of knowlege?
"Does the task require interaction with a person?

38. " Decomposability
Problem of integration : decomposable
Block Game [On(B,C) ^ON(A,B)]: No
" Nature of solution Steps
Ignored: Theorem proving
Recoverable: 8-puzzle
Unrecoverable: Game of bridge
" Is solution absolute or relative
8- puzzle: any path
Traveling Sales man: best path
" Is problem s universe predictable (certain or uncertain)
8-puzzle or game of Bridge

39. " Is desired solution a state or path
NLP Solution is state
Water Jug Problem solution is path
" What is Role of Knowledge
Chess- Lot of knowledge to constraint search
Newspaper Heading- recognize solution
Is it Consistent
"Does the task require interaction with person
Theorem proving: No
Expert system: Yes

40. Production system characteristics
"A monotonic production system is one 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 selected.
"A partially commutative production system is one in which if the
application of a sequence of rules transforms state x to state y, then
any permutation of those rules that is allowable also transforms
state x into state y.
"A Commutative Production system is both monotonic and Partially
commutative.

41. Additional Problems
"8 Puzzle
"The missionaries and cannibals
"The tower of hanoi
"The Monkeys and banana
"Criptarithmetic