GAMES: three-level game tree with leaf values A=3, B=1, C=4, D=5, E=9, F=2, G=6, H=8 Based on the above data, answer the given subquestions. Figure from the original question paper

(C) Only a solved node at the top of the priority queue will determine when its parent will be marked as solved.

(D) A live terminal node that is at the top of the priority queue will be immediately marked as solved.

(A) As soon as a MIN node is solved and added to the priority queue, immediately its MAX parent is also marked as solved and added to the priority queue.

(B) As soon as a last MAX child is solved and added to the priority queue, immediately its MIN parent is also marked as solved and added to the priority queue.

AUTOMATED PLANNING The domain description of a Blocks World with a single one-armed robot is given below. Note: this is the same domain description used in the weekly assignments. PREDICATES armEmpty The arm is not holding any block, it is empty. holding(X) The arm is holding X. onTable(X) X is on the table. clear(X) X has nothing above it, it is clear. on(X,Y) X is directly placed on Y. OPERATORS Pickup(X): pick up X from the table. Preconditions: { armEmpty, clear(X), onTable(X) } Add Effects : { holding(X) } Del Effects : { armEmpty, onTable(X) } Putdown(X): place X on the table. Preconditions: { holding(X) } Add Effects : { armEmpty, onTable(X) } Del Effects : { holding(X) } Unstack(X,Y): pick up X that is directly sitting on Y. Preconditions: { armEmpty, clear(X), on(X,Y) } Add Effects : { clear(Y), holding(X) } Del Effects : { armempty, on(X,Y) } Stack(X,Y): place X directly on top of Y. Preconditions: { holding(X), clear(Y) } Add Effects : { armEmpty, on(X,Y) } Del Effects : { holding(X), clear(Y) } Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to dead-ends or cycles. Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list. A planning problem is given below, find a pla…

(D) onTable(C); on(A,B); onTable(B); { onTable(B), on(A,B), onTable(C) }; BOTTOM

(A) { onTable(B), on(A,B), onTable(C) }; onTable(B); on(A,B); onTable(C); BOTTOM

(B) { onTable(B), on(A,B), onTable(C) }; onTable(C); on(A,B); onTable(B); BOTTOM

(C) onTable(B); on(A,B); onTable(C); { onTable(B), on(A,B), onTable(C) }; BOTTOM

September 2025 term · AI: Search Methods for Problem Solving · BSCS3003

AI: Search Methods for Problem Solving Quiz 2: 23 November 2025 (September 2025 term)

The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 2 paper sat on 23 Nov 2025, in the September 2025 term: 25 questions for 25 marks in 120 minutes. Every question is below with its answer. Take it as a timed mock test to be marked, or read it through first.

Questions: 25
Marks: 25
Duration: 120 min
MCQ: 9
MSQ: 4
Numerical: 6
Written: 6

Take as mock test Practise with answers

Updated 25 Sept 2026

Official paper: IIT M IMPROVEMENT AN EXAM QIA2 23 Nov 2025 · No negative marking.

Question 1

+1 markOne correct option

Based on the above data, answer the given subquestions.

Does the Depth First Search algorithm find the path to the goal?

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

B
No

Question 1 on its own page

Question 2

+1 markOne correct option

Based on the above data, answer the given subquestions.

Does the Best-First Search algorithm find the path to the goal?

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

B
No

Question 2 on its own page

Question 3

+1 markOne correct option

Based on the above data, answer the given subquestions.

Does the Branch and Bound algorithm find the path to the goal?

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

A
Yes

Question 3 on its own page

Question 4

+1 markOne correct option

Based on the above data, answer the given subquestions.

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

B
No

Question 4 on its own page

Question 5

+1 markOne correct option

Based on the above data, answer the given subquestions.

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

B
No

Question 5 on its own page

Question 6

+1 markOne correct option

Based on the above data, answer the given subquestions.

Is the heuristic admissible in the given state space?

A
Yes
B
No
C
Cannot be determined

Show answer

Correct answer

B
No

Question 6 on its own page

Question 7

+1 markOne correct option

SEARCH METHODS
Based on the above topic, answer the given subquestions.

Which of the following algorithms can be used to find the most expensive path to goal in a state space where every move is reversible and the edge costs are greater than 1?

Show answer

Correct answer

Question 7 on its own page

Question 8

+1 markOne or more correct options

SEARCH METHODS
Based on the above topic, answer the given subquestions.

If h(x) and k(x) are admissible then which of the following is/are admissible?

Select all that apply.

A
h(x)/2 + k(x)/2
B
h(x) + k(x)
C
max( h(x), k(x) )
D
min( h(x), k(x) )

Show answer

Correct answers

A
h(x)/2 + k(x)/2
C
max( h(x), k(x) )
D
min( h(x), k(x) )

Question 8 on its own page

Question 9

+1 markNumerical answer

TSP

The distance matrix for 5 cities (A to E) and the sorted edge list is provided below.

For each city the distances to other cities are listed in ascending order.

For example, in row one, the distance from A to D is 50, A to E is 76 and so on.

A	D:50	E:76	B:88	C:92
B	D:40	C:80	A:88	E:140
C	B:80	A:92	D:96	E:100
D	B:40	A:50	C:96	E:120
E	A:76	C:100	D:120	B:140

BD	AD	AE	BC	AB
40	50	76	80	88

AC	CD	CE	DE	BE
92	96	100	120	140

A segment is a two-way edge between two cities. After adding/dropping a permanent segment, infer as many new permanent segments as possible to compute the lower bound.
Run TSP BnB to find the optimal tour.
Determine the first three segments xy, uv and pq processed by TSP BnB.
Based on the above data, answer the given subquestions.

What is the lower bound on the cost of the tour as per the TSP BnB algorithm discussed in class? Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 342

Question 9 on its own page

Question 10

+1 markWritten answer

TSP

The distance matrix for 5 cities (A to E) and the sorted edge list is provided below.

For each city the distances to other cities are listed in ascending order.

For example, in row one, the distance from A to D is 50, A to E is 76 and so on.

A	D:50	E:76	B:88	C:92
B	D:40	C:80	A:88	E:140
C	B:80	A:92	D:96	E:100
D	B:40	A:50	C:96	E:120
E	A:76	C:100	D:120	B:140

BD	AD	AE	BC	AB
40	50	76	80	88

AC	CD	CE	DE	BE
92	96	100	120	140

What is the first segment (xy) selected for refining S0?
Enter edge label xy
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: XY

Show answer

Correct answer: BD or DB

Question 10 on its own page

Question 11

+1 markNumerical answer

TSP

The distance matrix for 5 cities (A to E) and the sorted edge list is provided below.

For each city the distances to other cities are listed in ascending order.

For example, in row one, the distance from A to D is 50, A to E is 76 and so on.

A	D:50	E:76	B:88	C:92
B	D:40	C:80	A:88	E:140
C	B:80	A:92	D:96	E:100
D	B:40	A:50	C:96	E:120
E	A:76	C:100	D:120	B:140

BD	AD	AE	BC	AB
40	50	76	80	88

AC	CD	CE	DE	BE
92	96	100	120	140

What is the cost of the node ~xy (that permanently excludes segment xy)?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 394

Question 11 on its own page

Question 12

+1 markNumerical answer

TSP

The distance matrix for 5 cities (A to E) and the sorted edge list is provided below.

For each city the distances to other cities are listed in ascending order.

For example, in row one, the distance from A to D is 50, A to E is 76 and so on.

A	D:50	E:76	B:88	C:92
B	D:40	C:80	A:88	E:140
C	B:80	A:92	D:96	E:100
D	B:40	A:50	C:96	E:120
E	A:76	C:100	D:120	B:140

BD	AD	AE	BC	AB
40	50	76	80	88

AC	CD	CE	DE	BE
92	96	100	120	140

How many tours are represented by the node (S0,xy,uv)?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 2

Question 12 on its own page

Question 13

+1 markNumerical answer

TSP

The distance matrix for 5 cities (A to E) and the sorted edge list is provided below.

For each city the distances to other cities are listed in ascending order.

For example, in row one, the distance from A to D is 50, A to E is 76 and so on.

A	D:50	E:76	B:88	C:92
B	D:40	C:80	A:88	E:140
C	B:80	A:92	D:96	E:100
D	B:40	A:50	C:96	E:120
E	A:76	C:100	D:120	B:140

BD	AD	AE	BC	AB
40	50	76	80	88

AC	CD	CE	DE	BE
92	96	100	120	140

What is the cost of the node (S0,xy,uv,pq)?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17

Show answer

Correct answer: 346

Question 13 on its own page

Question 14

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the horizon nodes in the best strategy for the MAX player.
Enter node labels as comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: E,H

Question 14 on its own page

Question 15

+1 markNumerical answer

Based on the above data, answer the given subquestions.

Enter the total number of strategies available for the MAX player.
Enter an integer
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 8

Question 15 on its own page

Question 16

+1 markWritten answer

Based on the above data, answer the given subquestions.

Of all the strategies available for the MAX player, identify the MAX strategy that is most favorable for the MIN player. Enter the horizon nodes of that MAX strategy in the textbox.
Enter node labels as comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: B,C or B,D

Question 16 on its own page

Question 17

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the horizon nodes pruned by Alpha-Beta algorithm.
Enter node labels as comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: D

Question 17 on its own page

Question 18

+1 markWritten answer

Based on the above data, answer the given subquestions.

List the horizon nodes in the initial cluster formed by SSS* algorithm.

Enter node labels as comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: A,B,E,F

Question 18 on its own page

Question 19

+1 markWritten answer

Based on the above data, answer the given subquestions.

Solve the game tree using SSS* algorithm. List the horizon nodes (not in the initial cluster) that are assigned SOLVED status.

Enter node labels as comma separated list in ASCENDING order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: G,H

Question 19 on its own page

Question 20

+1 markOne or more correct options

Based on the above data, answer the given subquestions.

Select all that apply.

A
As soon as a MIN node is solved and added to the priority queue, immediately its MAX parent is also marked as solved and added to the priority queue.
B
As soon as a last MAX child is solved and added to the priority queue, immediately its MIN parent is also marked as solved and added to the priority queue.
C
Only a solved node at the top of the priority queue will determine when its parent will be marked as solved.
D
A live terminal node that is at the top of the priority queue will be immediately marked as solved.

Show answer

Correct answers

C
Only a solved node at the top of the priority queue will determine when its parent will be marked as solved.
D
A live terminal node that is at the top of the priority queue will be immediately marked as solved.

Question 20 on its own page

Question 21

+1 markNumerical answer

AUTOMATED PLANNING

The domain description of a Blocks World with a single one-armed robot is given below.

Note: this is the same domain description used in the weekly assignments.

text

1PREDICATES
2
3armEmpty         The arm is not holding any block, it is empty.
4holding(X)       The arm is holding X.
5onTable(X)       X is on the table.
6clear(X)         X has nothing above it, it is clear.
7on(X,Y)          X is directly placed on Y.
8
9OPERATORS
10
11Pickup(X): pick up X from the table.
12      Preconditions: { armEmpty, clear(X), onTable(X) }
13      Add Effects  : { holding(X) }
14      Del Effects  : { armEmpty, onTable(X) }
15
16Putdown(X): place X on the table.
17      Preconditions: { holding(X) }
18      Add Effects  : { armEmpty, onTable(X) }
19      Del Effects  : { holding(X) }
20
21Unstack(X,Y): pick up X that is directly sitting on Y.
22      Preconditions: { armEmpty, clear(X), on(X,Y) }
23      Add Effects  : { clear(Y), holding(X) }
24      Del Effects  : { armempty, on(X,Y) }
25
26Stack(X,Y): place X directly on top of Y.
27      Preconditions: { holding(X), clear(Y) }
28      Add Effects  : { armEmpty, on(X,Y) }
29      Del Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to dead-ends or cycles.

Tie-breaker: Treat the goal description, preconditions and effects as lists that are accessed from left to right. When the elements in a list are pushed one by one to a stack, the last element in the list will be at the top of the stack. It has the effect of reversing the list.

A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Start: { clear(A), clear(B), holding(A), on(B,C), onTable(C) }

Goal Description: { onTable(B), on(A,B), onTable(C) }

Based on the above data, answer the given subquestions.

What is the length of the optimal plan? Enter the number of actions in the optimal plan. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 5

Question 21 on its own page

Question 22

+1 markOne or more correct options

AUTOMATED PLANNING

The domain description of a Blocks World with a single one-armed robot is given below.

Note: this is the same domain description used in the weekly assignments.

text

1PREDICATES
2
3armEmpty         The arm is not holding any block, it is empty.
4holding(X)       The arm is holding X.
5onTable(X)       X is on the table.
6clear(X)         X has nothing above it, it is clear.
7on(X,Y)          X is directly placed on Y.
8
9OPERATORS
10
11Pickup(X): pick up X from the table.
12      Preconditions: { armEmpty, clear(X), onTable(X) }
13      Add Effects  : { holding(X) }
14      Del Effects  : { armEmpty, onTable(X) }
15
16Putdown(X): place X on the table.
17      Preconditions: { holding(X) }
18      Add Effects  : { armEmpty, onTable(X) }
19      Del Effects  : { holding(X) }
20
21Unstack(X,Y): pick up X that is directly sitting on Y.
22      Preconditions: { armEmpty, clear(X), on(X,Y) }
23      Add Effects  : { clear(Y), holding(X) }
24      Del Effects  : { armempty, on(X,Y) }
25
26Stack(X,Y): place X directly on top of Y.
27      Preconditions: { holding(X), clear(Y) }
28      Add Effects  : { armEmpty, on(X,Y) }
29      Del Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to dead-ends or cycles.

A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Start: { clear(A), clear(B), holding(A), on(B,C), onTable(C) }

Goal Description: { onTable(B), on(A,B), onTable(C) }

Based on the above data, answer the given subquestions.

Which of the following are applicable actions for the given planning problem?

Select all that apply.

A
Pickup(A)
B
Putdown(A)
C
Putdown(B)
D
Putdown(C)
E
Stack(A,B)

Show answer

Correct answers

B
Putdown(A)
E
Stack(A,B)

Question 22 on its own page

Question 23

+1 markOne or more correct options

AUTOMATED PLANNING

The domain description of a Blocks World with a single one-armed robot is given below.

Note: this is the same domain description used in the weekly assignments.

text

1PREDICATES
2
3armEmpty         The arm is not holding any block, it is empty.
4holding(X)       The arm is holding X.
5onTable(X)       X is on the table.
6clear(X)         X has nothing above it, it is clear.
7on(X,Y)          X is directly placed on Y.
8
9OPERATORS
10
11Pickup(X): pick up X from the table.
12      Preconditions: { armEmpty, clear(X), onTable(X) }
13      Add Effects  : { holding(X) }
14      Del Effects  : { armEmpty, onTable(X) }
15
16Putdown(X): place X on the table.
17      Preconditions: { holding(X) }
18      Add Effects  : { armEmpty, onTable(X) }
19      Del Effects  : { holding(X) }
20
21Unstack(X,Y): pick up X that is directly sitting on Y.
22      Preconditions: { armEmpty, clear(X), on(X,Y) }
23      Add Effects  : { clear(Y), holding(X) }
24      Del Effects  : { armempty, on(X,Y) }
25
26Stack(X,Y): place X directly on top of Y.
27      Preconditions: { holding(X), clear(Y) }
28      Add Effects  : { armEmpty, on(X,Y) }
29      Del Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to dead-ends or cycles.

A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Start: { clear(A), clear(B), holding(A), on(B,C), onTable(C) }

Goal Description: { onTable(B), on(A,B), onTable(C) }

Based on the above data, answer the given subquestions.

Which of the following are relevant actions for the given planning problem?

Select all that apply.

A
Pickup(A)
B
Putdown(A)
C
Putdown(B)
D
Putdown(C)
E
Stack(A,B)

Show answer

Correct answers

C
Putdown(B)
D
Putdown(C)
E
Stack(A,B)

Question 23 on its own page

Question 24

+1 markOne correct option

AUTOMATED PLANNING

The domain description of a Blocks World with a single one-armed robot is given below.

Note: this is the same domain description used in the weekly assignments.

text

1PREDICATES
2
3armEmpty         The arm is not holding any block, it is empty.
4holding(X)       The arm is holding X.
5onTable(X)       X is on the table.
6clear(X)         X has nothing above it, it is clear.
7on(X,Y)          X is directly placed on Y.
8
9OPERATORS
10
11Pickup(X): pick up X from the table.
12      Preconditions: { armEmpty, clear(X), onTable(X) }
13      Add Effects  : { holding(X) }
14      Del Effects  : { armEmpty, onTable(X) }
15
16Putdown(X): place X on the table.
17      Preconditions: { holding(X) }
18      Add Effects  : { armEmpty, onTable(X) }
19      Del Effects  : { holding(X) }
20
21Unstack(X,Y): pick up X that is directly sitting on Y.
22      Preconditions: { armEmpty, clear(X), on(X,Y) }
23      Add Effects  : { clear(Y), holding(X) }
24      Del Effects  : { armempty, on(X,Y) }
25
26Stack(X,Y): place X directly on top of Y.
27      Preconditions: { holding(X), clear(Y) }
28      Add Effects  : { armEmpty, on(X,Y) }
29      Del Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to dead-ends or cycles.

A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Start: { clear(A), clear(B), holding(A), on(B,C), onTable(C) }

Goal Description: { onTable(B), on(A,B), onTable(C) }

Based on the above data, answer the given subquestions.

Which of the following can be pushed as the first three elements onto the stack by the Goal Stack Planning algorithm? In the stack representation, the bottom is on the right side marked by the entry BOTTOM. Use appropriate tie-breakers listed in the main data.

A
{ onTable(B), on(A,B), onTable(C) }; onTable(B); on(A,B); onTable(C); BOTTOM
B
{ onTable(B), on(A,B), onTable(C) }; onTable(C); on(A,B); onTable(B); BOTTOM
C
onTable(B); on(A,B); onTable(C); { onTable(B), on(A,B), onTable(C) }; BOTTOM
D
onTable(C); on(A,B); onTable(B); { onTable(B), on(A,B), onTable(C) }; BOTTOM

Show answer

Correct answer

D
onTable(C); on(A,B); onTable(B); { onTable(B), on(A,B), onTable(C) }; BOTTOM

Question 24 on its own page

Question 25

+1 markOne correct option

AUTOMATED PLANNING

The domain description of a Blocks World with a single one-armed robot is given below.

Note: this is the same domain description used in the weekly assignments.

text

1PREDICATES
2
3armEmpty         The arm is not holding any block, it is empty.
4holding(X)       The arm is holding X.
5onTable(X)       X is on the table.
6clear(X)         X has nothing above it, it is clear.
7on(X,Y)          X is directly placed on Y.
8
9OPERATORS
10
11Pickup(X): pick up X from the table.
12      Preconditions: { armEmpty, clear(X), onTable(X) }
13      Add Effects  : { holding(X) }
14      Del Effects  : { armEmpty, onTable(X) }
15
16Putdown(X): place X on the table.
17      Preconditions: { holding(X) }
18      Add Effects  : { armEmpty, onTable(X) }
19      Del Effects  : { holding(X) }
20
21Unstack(X,Y): pick up X that is directly sitting on Y.
22      Preconditions: { armEmpty, clear(X), on(X,Y) }
23      Add Effects  : { clear(Y), holding(X) }
24      Del Effects  : { armempty, on(X,Y) }
25
26Stack(X,Y): place X directly on top of Y.
27      Preconditions: { holding(X), clear(Y) }
28      Add Effects  : { armEmpty, on(X,Y) }
29      Del Effects  : { holding(X), clear(Y) }

Tie-breaker: When actions are chosen non-deterministically, choose actions that lead to a plan. Throw away the actions that lead to dead-ends or cycles.

A planning problem is given below, find a plan using the operators and predicates defined in the blocks-world domain.

Start: { clear(A), clear(B), holding(A), on(B,C), onTable(C) }

Goal Description: { onTable(B), on(A,B), onTable(C) }

Based on the above data, answer the given subquestions.

For the subgoal ordering given in the goal description (and using the given tie breaking rules), which of the following is the first action popped out of the stack in Goal Stack Planning?

A
Pickup(A)
B
Putdown(A)
C
Putdown(B)
D
Putdown(C)
E
Stack(A,B)

Show answer

Correct answer

E
Stack(A,B)

Question 25 on its own page