AI Tutorial Problems

-Dr. Radhika V. Kulkarni

Sources:
1. Stuart Russell & Peter Norvig, "Artificial Intelligence : A Modern Approach", Pearson Education, 2nd Edition.
2. Elaine Rich and Kevin Knight, "Artificial Intelligence" Tata McGraw Hill
3. Deepak Khemani, “A First Course in Artificial Intelligence”, McGraw Hill
4. Saroj Kaushik, “Artificial Intelligence”, Cengage Publication.

RVK-AI-Tutorial Problems 1
 DISCLAIMER

This presentation is created as a reference material for the

RVK-AI-Tutorial Problems 2
 Water Jug Problem

Sources:
1. Elaine Rich and Kevin Knight, "Artificial Intelligence" Tata McGraw Hill.

RVK-AI-Tutorial Problems 3
 Water Jug Problem (1)
• Problem Description: We are given two jugs, a 4-gallon one and 3-gallon one. Neither has any measuring
marked on it. There is a pump, which can be used to fill the jugs with water. How can we get exactly 2 gallons
of water into 4-gallon jug?

• Solution:
• The state space 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; X is the number of gallons of water in the 4-gallon jug and Y the quantity of
water in the 3-gallon jug.
• The start state is (0, 0) and the goal state is (2, n) for any value of n, as the problem does not specify how
many gallons need to be filled in the 3-gallon jug (0, 1, 2, 3). So, the problem has one initial state and many
goal states. Some problems may have many initial states and one or many goal states.
• As provided in the problem statement, at any given state we can do either of the following operations:
1. Fill a jug
2. Empty a jug
3. Transfer water from one jug to another until either of them gets completely filled or empty.
RVK-AI-Tutorial Problems 4
 Water Jug
Problem (2)

• The operators to be
used to solve the
problem can be
described as shown
in Fig. 2.3:

RVK-AI-Tutorial Problems 5
 Water Jug Problem (3)
• To solve the water jug problem, all we need, in addition to given problem description, 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.
• 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.
• There are several sequences of operators which will solve the problem, two such sequences are shown here:
• Solution1:

RVK-AI-Tutorial Problems 6
 Water Jug Problem (4)
• Solution2:

• There may be more than one solutions.

RVK-AI-Tutorial Problems 7
Water Jug Problem (5)
• BFS Algorithm for water jug
problem:

RVK-AI-Tutorial Problems 8
Water Jug Problem (6)
• DFS Algorithm for water jug
problem:

RVK-AI-Tutorial Problems 9
 Missionaries and Cannibals Problem

Source:
1. Stuart Russell & Peter Norvig, "Artificial Intelligence : A Modern Approach", Pearson Education, 2nd Edition.
2. Elaine Rich and Kevin Knight, "Artificial Intelligence" Tata McGraw Hill.

RVK-AI-Tutorial Problems 10
 Missionaries and Cannibals Problem (1)
• Problem Description: Three missionaries and three cannibals want to cross a river. There is a boat on their side of
the river that can be used by either one or two persons. How should they use this boat to cross the river in such a
way that cannibals never outnumber missionaries on either side of the river? If the cannibals ever outnumber the
missionaries (on either bank) then the missionaries will be eaten. How can they all cross over without anyone
being eaten?

• Solution:
• The initial state is shown to the right here, where black triangles represent missionaries and red circles represent
cannibals.

• Goal: Move all the missionaries and cannibals across the river.
• Constraint: Missionaries can never be outnumbered by cannibals on either side of river, or else the missionaries
are killed.
• State: configuration of missionaries and cannibals and boat on each side of river.
• Operators/ Actions: Move boat containing some set of occupants across the river (in either direction) to the other
side.
RVK-AI-Tutorial Problems 11
 Missionaries and Cannibals Problem (2)
• We should make a graph search which traverse the graph from initial state and find out the final state in
fewest moves. There are many AI searches that search the graphs like Breadth first search, Depth first search,
or iterative deepening search.

RVK-AI-Tutorial Problems 12
 Missionaries and Cannibals Problem (3)
• Problem space for this problem can be described as the set of ordered pairs of left and right bank of the river
as (L, R) where each bank is represented as a list State(no_of_missionaries, no_of_cannibals,
presence_of_the_boat) i.e.[nM, mC, B]
– n is the number of missionaries M, m is the number of cannibals C, and B represents boat.

• Start state: (L, R) = ( [3M, 3C, 1B], [0M, 0C, 0B] ) or (L, R) = ( [3,3,1], [0,0,0] )
– 1B means that boat is present and 0B means it is not there on the bank of river.

• Goal state: (L, R) = ( [0M, 0C, 0B], [3M, 3C, 1B] ) or (L, R) = ( [0,0,0], [3,3,1] )

• Any state: ([n1M, m1C, 1B], [n2 M, m2 C, 0B]) ,

• Note: By no means, this representation is unique. In fact, one may have number of different representations
for the same problem.

RVK-AI-Tutorial Problems 13
 Missionaries and Cannibals Problem (4)
• Production rules for Missionaries and Cannibals problem:

RVK-AI-Tutorial Problems 14
Missionaries and Cannibals Problem (5)

RVK-AI-Tutorial Problems 15
 Missionaries and Cannibals Problem (5)
• BFS algorithm for Missionaries and Cannibals Problem:

RVK-AI-Tutorial Problems 16
 8-Puzzle Problem

Source:
1. Stuart Russell & Peter Norvig, "Artificial Intelligence : A Modern Approach", Pearson Education, 2nd Edition.
2. Elaine Rich and Kevin Knight, "Artificial Intelligence" Tata McGraw Hill.

RVK-AI-Tutorial Problems 17
 8-Puzzle Problem (1)
• Problem Description: The 8-puzzle is a 3 × 3 array containing eight square pieces, numbered 1 through 8,
and one empty space. A piece/tile can be moved horizontally or vertically into the empty space, in effect
exchanging the positions of the piece and the empty space.
• There are four possible moves, UP (move the blank space up), DOWN, LEFT and RIGHT. The aim of the game
is to make a sequence of moves that will convert the board from the start state into the goal state. This
example can be solved by the operator sequence UP, RIGHT, UP, LEFT, DOWN.
Initial State 2 8 3 Goal State 1 2 3
1 6 4 8 4
7 5 7 6 5

• Solution: Without heuristic it will explore each and every state using uninformed search techniques.
However, applying heuristics it can explore lesser number of states and get optimal solution.
• Different heuristics:
1. h= No. of misplaced tiles by comparing current state and goal state; explore the node with the least heuristic value.
2. h= Sum of Euclidian distances of the tiles from their goal positions.(Euclidian distance=
(x1−x2)2+ (y1−y2)2).
3. h= Sum of Manhattan distances of the tiles from their goal positions. (Manhatten distance=|x1-x2|+| y1-y2|)
4. h= Number of tiles out of row + Number of tiles out of column.
RVK-AI-Tutorial Problems 18
 8-Puzzle Problem (2)

• BFS for 8-Puzzle Problem:

RVK-AI-Tutorial Problems 19
 8-Puzzle
Problem (3)
• Heuristics for 8-Puzzle
Problem:
• h= no. of misplaced tiles by
comparing current state and
goal state;
• Explore the node with the least
heuristic value.

RVK-AI-Tutorial Problems 20
 Monkey Banana Problem

Source:
1. Stuart Russell & Peter Norvig, "Artificial Intelligence : A Modern Approach", Pearson Education, 2nd Edition.
2. Elaine Rich and Kevin Knight, "Artificial Intelligence" Tata McGraw Hill.
3. [Link]

RVK-AI-Tutorial Problems 21
 Monkey Banana Problem (1)
• Problem Description: A hungry monkey is in a room, and he is near the door. The monkey is on the floor.
Bananas have been hung from the center of the ceiling of the room. There is a block (or chair) present in
the room near the window. The monkey wants the banana but cannot reach it.
• The monkey and box have height Low, but if the monkey climbs onto the box he will have height High, the
same as the bananas.
• The actions available to the monkey include Go from one place to another, Push an object from one place to
another, ClimbUp onto or ClimbDown from an object, and Grasp or Ungrasp an object.
• The result of a Grasp is that the monkey holds the object if the monkey and object are in the same place at
the same height.

RVK-AI-Tutorial Problems 22
 Monkey Banana Problem (2)
• If the monkey is clever enough, he can come to the block, drag the block to the center, climb on it, and get
the banana. Below are few observations in this case −
• Monkey can reach the block, if both of them are at the same level. From the above image, we can see that both the
monkey and the block are on the floor.
• If the block position is not at the center, then monkey can drag it to the center.
• If monkey and the block both are on the floor, and block is at the center, then the monkey can climb up on the
block. So, the vertical position of the monkey will be changed.
• When the monkey is on the block, and block is at the center, then the monkey can get the bananas.

For more details refer to: [Link]

RVK-AI-Tutorial Problems 23
Thank you!

RVK-AI-Tutorial Problems 24