AIML Lecture for teach to the students by teacher

AIML dmfjm dfk wdwfnwel dfwnelf wlkenfw wwenfl eflnwe a b c jkefdj dfkljwe wefwjf edfjkwe wejhfhw wewjkfwenmwef mkiefj werkw jwfowj wefljwf wefjewo

1. 1
State Space SearchState Space Search
Lecture # 2Lecture # 2

2. 2
Problem Solving as SearchProblem Solving as Search
• Humans solve problems by considering and evaluating
alternate choices, until one set of choices lead to an
acceptable solution of the problem
- A traveler considers a number of possible alternates
to reach his destination, including intermediate
stops
- A doctor examines several possible diagnosis, and
refines his search by collecting more data about
the patient
• Hence search among alternate choices is an important
tool for exhibiting intelligence

3. 3
Problem Solving as SearchProblem Solving as Search
• Requirements of search
- Definition of starting state and the goal state
e.g. I am in Islamabad and want to be in Paris
- Definition of possible intermediate states
e.g. different cities between Islamabad & Paris
- Rules for transition between these states
e.g. air flights available from one city to another

4. 4
Example: RomaniaExample: Romania

5. 5
Problem Solving as SearchProblem Solving as Search
• Searching the entire set of states for solving a problem is
called exhaustive search
• Human beings do not use exhaustive search
e.g. a doctor may form a diagnosis just on the basis of
“season” or “frequency of a disease in other patients”
• Such shortcuts are called heuristics

6. 6
Problem SpacesProblem Spaces
• Water Jug Problem
- We have two jugs of 4 gallon and 3 gallons capacity
- The jugs do not have any measuring markers
- How can we get exactly 2 gallons of water into the
4 gallon jug?
• We can define the possible states for the problem and make
a list of legal or valid operations
• The possible states for this problem can be described as the
set of ordered pairs of integers (x, y), such that
x = 0, 1, 2, 3, or 4 and y = 0, 1, 2, or 3. Here x and y
represent the gallons of water in the two jugs
• Our start state is (0,0) and our goal state is (2,n)

7. 7
Problem SpacesProblem Spaces
Water Jug Problem Operators
1. Fill the x-jug, if x < 4(x, y)  (4, y)
2. Fill the y-jug, if y < 3(x, y)  (x, 3)
3. Empty the x-jug, if x > 0 (x, y)  (0, y)
4. Empty the y-jug, if y > 0 (x, y)  (x, 0)
5. Pour water from the y-jug into the x-jug, until the x-jug is full
if x + y >= 4 and y > 0(x, y)  (4, y – (4 – x))
6. Pour water from the x-jug into the y-jug, until the y-jug is full
if x + y >= 3 and x > 0(x, y)  (x – (3 – y), 3)
7. Pour all the water from the y-jug, into the x-jug
if x + y <= 4 and if y > 0(x, y)  (x + y, 0)
8. Pour all the water from the x-jug, into the y-jug
if x + y <= 3 and if x > 0(x, y)  (0, y + x)

8. 8
Problem SpacesProblem Spaces
Water in the x-jugWater in the y-jugRule applied
0 0
2
0 3
7
3 0
2
3 3
5
4 2
3
0 2
7
2 0

9. 9
Example: vacuum worldExample: vacuum world
•Single-state, start in #5.
Solution?

10. 10
•Single-state, start in #5.
Solution? [Right, Suck]
•Sensorless, start in
{1,2,3,4,5,6,7,8} e.g.,
Right goes to {2,4,6,8}
Solution?
Example: vacuum worldExample: vacuum world

11. 11
•Sensorless, start in
{1,2,3,4,5,6,7,8} e.g.,
Right goes to {2,4,6,8}
Solution?
[Right,Suck,Left,Suck]
•Contingency
–Nondeterministic: Suck may
dirty a clean carpet (Murphy’s law)
–Partially observable: location, dirt at current location.
–Percept: [L, Clean], i.e., start in #5 or #7
Solution?
Example: vacuum worldExample: vacuum world

12. 12
•Sensorless, start in
{1,2,3,4,5,6,7,8} e.g.,
Right goes to {2,4,6,8}
Solution?
[Right,Suck,Left,Suck]
•Contingency
–Nondeterministic: Suck may
dirty a clean carpet
–Partially observable: location, dirt at current location.
–Percept: [L, Clean], i.e., start in #5 or #7
Solution? [Right, if dirt then Suck]
Example: vacuum worldExample: vacuum world

13. 13
Problem SpacesProblem Spaces
• The problem can be seen as that of moving around in
the state space from one legal state to another, until
a path from an initial state to a goal state is found
• The transition between states is by application of the
operators defined
• There are different possible search strategies for selecting
one of the different possible states at each step:
Informed strategies use agent’s background
information about the problem map, costs of actions.
E.g. Best-First Search(greedy, A*), Local Search(Hill
Climbing, Simulated Annealing, Genetics Algo).
Uninformed strategies use only the information
available in the problem definition Breadth-first
search Uniform-cost search Depth-first search
Depth-limited search

14. 14
Problem SpacesProblem Spaces
For defining any problem as a state space search we must:
• Define a state space that contains all the possible
configurations of the relevant objects. This does not
mean that all the states should be defined explicitly.
Example: (x,y) for water jug problem
• Specify one or more states as initial and one or more states
as final or goal states
• Specify a set of rules (operators) that describe the actions
available

15. 15
Problem SpacesProblem Spaces
Vacuum world

16. 16
Problem SpacesProblem Spaces
Traveling Problem

17. 17
Problem SpacesProblem Spaces
Traveling Problem

18. 18
Problem SpacesProblem Spaces
Tile Puzzle

19. 19
Problem SpacesProblem Spaces
Tile Puzzle

20. 20
A B
CD 4
6
35
2
Problem SpacesProblem Spaces
Travelling Salesman problem: A salesman need to visit n
cities for the advertisement of its product. He likes to visit a
city only once (no city should be visited twice). Which
shortest path he will follows to visit all the cities and return
back to the starting city.

21. 21
Problem SpacesProblem Spaces
Missionaries and cannibals problem
Three missionaries & three cannibals are on one side of a river
They would all like to get to the other side, but the
missionaries do not trust the cannibals
So the missionaries want to manage the trip across the river
in such a way that the number of missionaries on
either side of the river is never less than the number
of cannibals who are on the same side
The only boat available holds only two people at a time. How
can everyone get across the river without the
missionaries risking being eaten

22. Solution?
•
22

23. Solution??
•
23

24. Solution??

24

25. 25
Problem SpacesProblem Spaces
The Monkey and Bananas
A hungry monkey finds himself in a room in which a bunch of
bananas is hanging from the ceiling
The monkey, cannot reach the bananas
In the room there is also a stick and a chair
If the monkey stands on the chair he can knock the bananas
down with a stick
What is the best sequence of actions for the monkey to get the
bananas

26. 26
Problem SpacesProblem Spaces
Many of the techniques (search and other techniques) that
have been developed for these toy problems have become
the core of real world problems
• Jug
• 8 puzzle
• Traveling salesman
• Missionaries and cannibals
• Monkey and bananas
Try to define an appropriate state space representation for
each of these problems, make any required assumptions

27. 27
Search StrategiesSearch Strategies
• Blind or Uninformed search
We are not informed about the quality of our choices

28. 28
Depth First SearchDepth First Search
Method
• When a state is examined, all of its children and their
descendants are examined before any of its siblings
• The siblings are considered only when no further descendants
of a state can be found

29. 29
Depth First SearchDepth First Search

30. 30
Depth First SearchDepth First Search

31. 31
Depth First SearchDepth First Search

32. 32
Depth First SearchDepth First Search
Advantages
• It quickly goes deep into search space, hence it is efficient for
search spaces with many branches
• Requires less memory since only the nodes on the current
path are stored
Disadvantages
• Shortest path is not guaranteed. A state may be reached
by a longer path when it is encountered the first time. It
may get lost deep in a graph, missing shorter paths to a
goal. If the shortest path is required each state may be
stored as a triplet (state, parent, length-of-path)
Note that cost means computational cost expended when finding
a path and not the actual travel cost of traversing that path

33. 33
Reading Assignment & ReferencesReading Assignment & References
• Structures for state space search (Luger 3.1.1)
• State space representation of problems (Luger 3.1.2)
• Implementing graph search (Luger 3.2.2)
• Depth first search (Luger 3.2.3)
• Search on Internet:
Who won the last Loebner prize contest?

34. Golden Pearl 2
LISTEN MORE AND TALK LESS
WE HAVE TWO EARS AND ONE
TONGUE FOR THAT PURPOSE
34