Quiz Space

May 2023 term · AI: Search Methods for Problem Solving · BSCS3003

AI Search Methods End Term: 3 September 2023, Set QPE1-S2 (May 2023 term)

The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) End Term paper sat on 3 Sept 2023, in the May 2023 term, set QPE1-S2: 25 questions for 25 marks in 180 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
180 min
Written
14
MCQ
3
Numerical
2
MSQ
6
Take as mock testPractise with answers

Updated

Official paper: IIT M DEGREE ET1 EXAM QPE1 S2 03 Sep · No negative marking.

Question 1

+1 markWritten answer

SEARCH
The figure shows a map on a uniform grid where each tile is 10x10 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in alphabetical order.
Use Manhattan Distance as the heuristic function.
Tie-breaker: If several nodes have the same cost, use node labels to break the tie.

Based on the above data, answer the given subquestions.

What is the path found by the Depth First Search algorithm? Enter the path as a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: S,X,Y,Z

Show answer

Correct answer: S,A,C,G

Question 1 on its own page

Question 2

+1 markWritten answer

SEARCH
The figure shows a map on a uniform grid where each tile is 10x10 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in alphabetical order.
Use Manhattan Distance as the heuristic function.
Tie-breaker: If several nodes have the same cost, use node labels to break the tie.

Based on the above data, answer the given subquestions.

What is the path found by the Best First Search algorithm? Enter the path as a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: S,X,Y,Z

Show answer

Correct answer: S,D,F,G

Question 2 on its own page

Question 3

+1 markWritten answer

SEARCH
The figure shows a map on a uniform grid where each tile is 10x10 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in alphabetical order.
Use Manhattan Distance as the heuristic function.
Tie-breaker: If several nodes have the same cost, use node labels to break the tie.

Based on the above data, answer the given subquestions.

What is the path found by A* search algorithm? Enter the path as a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: S,X,Y,Z

Show answer

Correct answer: S,B,E,G

Question 3 on its own page

Question 4

+1 markWritten answer

SEARCH
The figure shows a map on a uniform grid where each tile is 10x10 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in alphabetical order.
Use Manhattan Distance as the heuristic function.
Tie-breaker: If several nodes have the same cost, use node labels to break the tie.

Based on the above data, answer the given subquestions.

What is the path found by Branch-and-Bound search algorithm? Enter the path as a comma separated list of node labels.
Use the Branch-and-Bound variation that avoids cyclic expansions like S,A,S,A,S,A,...
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: S,X,Y,Z

Show answer

Correct answer: S,A,C,G

Question 4 on its own page

Question 5

+1 markOne correct option

SEARCH
The figure shows a map on a uniform grid where each tile is 10x10 in size.
The start node is S and the goal node is G.
The MoveGen function returns nodes in alphabetical order.
Use Manhattan Distance as the heuristic function.
Tie-breaker: If several nodes have the same cost, use node labels to break the tie.

Based on the above data, answer the given subquestions.

For the given map, which algorithm finds the shortest path from S to G?

  1. A

    A* Search Algorithm

  2. B

    Branch-and-Bound Search Algorithm

  3. C

    None of these

Show answer

Correct answer

  • B

    Branch-and-Bound Search Algorithm

Question 5 on its own page

Question 6

+1 markWritten answer

TSP Branch-and-Bound
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to breakties. When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree.

Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes (2nd to 5th node) that are refined by the TSP Branch-and-Bound algorithm. Enter the nodes (node reference numbers) in the order they are refined.
Enter a comma separated list of node reference numbers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: a9,b9,c9,d9

Show answer

Correct answer: b1,c2,b2,c3

Question 6 on its own page

Question 7

+1 markWritten answer

TSP Branch-and-Bound
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to breakties. When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree.

Which node represents the optimal tour and what is the cost of the optimal tour? Enter the node reference number and the tour cost in the text box, or enter NIL if it is not possible to determine the optimal tour.
Enter a node reference number followed by tour cost, separated by comma.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: a9,42

Show answer

Correct answer: d3,434

Question 7 on its own page

Question 8

+1 markNumerical answer

TSP Branch-and-Bound
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to breakties. When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree.

Determine the number of cities in the TSP instance. Enter the number of cities in the text box, or enter NIL if it is not possible to determine the number of cities.
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 5

Question 8 on its own page

Question 9

+1 markWritten answer

TSP Branch-and-Bound
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to breakties. When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree.

Start from city A, what is the path representation of the optimal tour? Enter the path
representation in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter a comma separated list of cities (city labels).
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: A,B,C

Show answer

Correct answer: A,B,D,E,C or A,C,E,D,B

Question 9 on its own page

Question 10

+1 markOne or more correct options

GAMES
The figure shows a game tree with evaluation function values at the horizon nodes.
The horizon nodes are labeled from A to G.
Use these labels to enter a horizon node or a list of horizon nodes in short answers (textbox). Tie-breaker: when several nodes carry the same best cost then select the deepest node, if tie persists then select the leftmost of the deepest nodes to break the tie.

Based on the above data, answer the given subquestions.

Which of the following is a strategy for the MAX player?

Select all that apply.

  1. A

    C,D,E

  2. B

    A,C

  3. C

    A,B

  4. D

    A,D,F

Show answer

Correct answers

  • A

    C,D,E

  • C

    A,B

Question 10 on its own page

Question 11

+1 markWritten answer

GAMES
The figure shows a game tree with evaluation function values at the horizon nodes.
The horizon nodes are labeled from A to G.
Use these labels to enter a horizon node or a list of horizon nodes in short answers (textbox). Tie-breaker: when several nodes carry the same best cost then select the deepest node, if tie persists then select the leftmost of the deepest nodes to break the tie.

Based on the above data, answer the given subquestions.

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

Show answer

Correct answer: C,F,G

Question 11 on its own page

Question 12

+1 markWritten answer

GAMES
The figure shows a game tree with evaluation function values at the horizon nodes.
The horizon nodes are labeled from A to G.
Use these labels to enter a horizon node or a list of horizon nodes in short answers (textbox). Tie-breaker: when several nodes carry the same best cost then select the deepest node, if tie persists then select the leftmost of the deepest nodes to break the tie.

Based on the above data, answer the given subquestions.

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

Show answer

Correct answer: F,G

Question 12 on its own page

Question 13

+1 markWritten answer

GAMES
The figure shows a game tree with evaluation function values at the horizon nodes.
The horizon nodes are labeled from A to G.
Use these labels to enter a horizon node or a list of horizon nodes in short answers (textbox). Tie-breaker: when several nodes carry the same best cost then select the deepest node, if tie persists then select the leftmost of the deepest nodes to break the tie.

Based on the above data, answer the given subquestions.

List the horizon nodes SOLVED by SSS*.
Enter a comma separated list of node labels in alphabetical order.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: A,C,D,E

Question 13 on its own page

Question 14

+1 markWritten answer

PROBLEM DECOMPOSITION
The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or more smaller problems. Nodes are uniquely identified by labels (S, A, B, …). The number in each node is the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs. Observe that a primitive node is added to the graph by its parent when the parent is expanded, and the primitive node is labeled as SOLVED and it will not be expanded subsequently.
The cost of each edge is 10 units.
Tie-breaker 1: If several nodes have the same cost then break the tie using node labels. Tie-breaker 2: For AND nodes, expand the unsolved branch with the highest cost.

Use AO* algorithm to solve S, then answer the subquestions.

List the first three nodes (including S) expanded by AO* algorithm. List the nodes in the order they are expanded. Observe that primitive nodes are not expanded.
Enter a comma separated list of node labels.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X,Y,Z

Show answer

Correct answer: S,C,A or C,A,E

Question 14 on its own page

Question 15

+1 markWritten answer

PROBLEM DECOMPOSITION
The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or more smaller problems. Nodes are uniquely identified by labels (S, A, B, …). The number in each node is the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs. Observe that a primitive node is added to the graph by its parent when the parent is expanded, and the primitive node is labeled as SOLVED and it will not be expanded subsequently.
The cost of each edge is 10 units.
Tie-breaker 1: If several nodes have the same cost then break the tie using node labels. Tie-breaker 2: For AND nodes, expand the unsolved branch with the highest cost.

Use AO* algorithm to solve S, then answer the subquestions.

Determine the value of the start node S after each node is expanded. What are the values of S after the 1st, 2nd and 3rd nodes are expanded, respectively? Enter the 3 values in the textbox. Enter a comma separated list of numbers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 12,42,17

Show answer

Correct answer: 50,60,70 or 60,70,90

Question 15 on its own page

Question 16

+1 markNumerical answer

PROBLEM DECOMPOSITION
The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or more smaller problems. Nodes are uniquely identified by labels (S, A, B, …). The number in each node is the heuristic estimate of the cost of solving that node.
Nodes shown in double lines are primitive nodes and their values are actual costs. Observe that a primitive node is added to the graph by its parent when the parent is expanded, and the primitive node is labeled as SOLVED and it will not be expanded subsequently.
The cost of each edge is 10 units.
Tie-breaker 1: If several nodes have the same cost then break the tie using node labels. Tie-breaker 2: For AND nodes, expand the unsolved branch with the highest cost.

Use AO* algorithm to solve S, then answer the subquestions.

What is the final value of the start node S?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42

Show answer

Correct answer: 90

Question 16 on its own page

Question 17

+1 markOne or more correct options

RULE BASED EXPERT SYSTEMS
A small part of the Rete Net for classifying resistors is shown in the figure. The labels A1, A2, ..., A10, A11, ..., B1, ..., B5 uniquely identify the nodes in the network. When required, use the above label ordering to break ties and to enter short answers.

Run the Rete algorithm for the Working Memory shown below, the WMEs are in timestamp order. Assume that WMEs reside at appropriate Alpha nodes, and the Beta nodes point to WMEs residing in Alpha nodes.

text
101.  (Band-1  ^itemNo 2B  ^colour brown)
102.  (Band-1  ^itemNo 3C  ^colour black)
103.  (Band-2  ^itemNo 2B  ^colour yellow)
104.  (Band-2  ^itemNo 3C  ^colour yellow)
105.  (Band-3  ^itemNo 1A  ^colour blue)
106.  (Band-3  ^itemNo 2B  ^colour blue)
107.  (Band-3  ^itemNo 3C  ^colour orange)
108.  (Band-4  ^itemNo 2B  ^colour gold)
109.  (Band-2  ^itemNo 1A  ^colour red)
110.  (Band-1  ^itemNo 1A  ^colour black)

For each WME identify its location (node label) in the Rete Net, and prepare the conflict set for the first cycle, then answer the given subquestions.

Which of the following rule-data tuples are in the conflict-set?

Select all that apply.

  1. A

    R1,102,107,109

  2. B

    R2,105,109,110

  3. C

    R3,101,104,105,108

  4. D

    R3,101,103,106,108

Show answer

Correct answers

  • B

    R2,105,109,110

  • D

    R3,101,103,106,108

Question 17 on its own page

Question 18

+1 markOne correct option

RULE BASED EXPERT SYSTEMS
A small part of the Rete Net for classifying resistors is shown in the figure. The labels A1, A2, ..., A10, A11, ..., B1, ..., B5 uniquely identify the nodes in the network. When required, use the above label ordering to break ties and to enter short answers.

Run the Rete algorithm for the Working Memory shown below, the WMEs are in timestamp order. Assume that WMEs reside at appropriate Alpha nodes, and the Beta nodes point to WMEs residing in Alpha nodes.

text
101.  (Band-1  ^itemNo 2B  ^colour brown)
102.  (Band-1  ^itemNo 3C  ^colour black)
103.  (Band-2  ^itemNo 2B  ^colour yellow)
104.  (Band-2  ^itemNo 3C  ^colour yellow)
105.  (Band-3  ^itemNo 1A  ^colour blue)
106.  (Band-3  ^itemNo 2B  ^colour blue)
107.  (Band-3  ^itemNo 3C  ^colour orange)
108.  (Band-4  ^itemNo 2B  ^colour gold)
109.  (Band-2  ^itemNo 1A  ^colour red)
110.  (Band-1  ^itemNo 1A  ^colour black)

For each WME identify its location (node label) in the Rete Net, and prepare the conflict set for the first cycle, then answer the given subquestions.

If the Inference Engine uses Specificity as the conflict resolution strategy then identify the rule- data tuple that will be ready to fire.

  1. A

    R1,102,107,109

  2. B

    R2,105,109,110

  3. C

    R3,101,104,105,108

  4. D

    R3,101,103,106,108

Show answer

Correct answer

  • D

    R3,101,103,106,108

Question 18 on its own page

Question 19

+1 markOne correct option

RULE BASED EXPERT SYSTEMS
A small part of the Rete Net for classifying resistors is shown in the figure. The labels A1, A2, ..., A10, A11, ..., B1, ..., B5 uniquely identify the nodes in the network. When required, use the above label ordering to break ties and to enter short answers.

Run the Rete algorithm for the Working Memory shown below, the WMEs are in timestamp order. Assume that WMEs reside at appropriate Alpha nodes, and the Beta nodes point to WMEs residing in Alpha nodes.

text
101.  (Band-1  ^itemNo 2B  ^colour brown)
102.  (Band-1  ^itemNo 3C  ^colour black)
103.  (Band-2  ^itemNo 2B  ^colour yellow)
104.  (Band-2  ^itemNo 3C  ^colour yellow)
105.  (Band-3  ^itemNo 1A  ^colour blue)
106.  (Band-3  ^itemNo 2B  ^colour blue)
107.  (Band-3  ^itemNo 3C  ^colour orange)
108.  (Band-4  ^itemNo 2B  ^colour gold)
109.  (Band-2  ^itemNo 1A  ^colour red)
110.  (Band-1  ^itemNo 1A  ^colour black)

For each WME identify its location (node label) in the Rete Net, and prepare the conflict set for the first cycle, then answer the given subquestions.

If the Inference Engine uses Recency as the conflict resolution strategy then identify the rule-data tuples that will be ready to fire. If multiple rule-data tuples qualify then choose one.

  1. A

    R1,102,107,109

  2. B

    R2,105,109,110

  3. C

    R3,101,104,105,108

  4. D

    R3,101,103,106,108

Show answer

Correct answer

  • B

    R2,105,109,110

Question 19 on its own page

Question 20

+1 markOne or more correct options

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

PREDICATES

text
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

text
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) }

Consider the planning problem with the following start state and goal description.

Based on the above data, answer the given subquestions.

Which of the following are applicable actions in the start state?

Select all that apply.

  1. A

    Putdown(B)

  2. B

    Stack(B,C)

  3. C

    Stack(C,D)

  4. D

    Stack(B,A)

  5. E

    Stack(A,B)

Show answer

Correct answers

  • A

    Putdown(B)

  • B

    Stack(B,C)

  • D

    Stack(B,A)

Question 20 on its own page

Question 21

+1 markOne or more correct options

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

PREDICATES

text
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

text
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) }

Consider the planning problem with the following start state and goal description.

Based on the above data, answer the given subquestions.

Which of the following are relevant actions in the goal state?

Select all that apply.

  1. A

    Putdown(B)

  2. B

    Stack(B,C)

  3. C

    Stack(C,D)

  4. D

    Stack(B,A)

  5. E

    Stack(A,B)

Show answer

Correct answers

  • B

    Stack(B,C)

  • C

    Stack(C,D)

  • E

    Stack(A,B)

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.

PREDICATES

text
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

text
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) }

Consider the planning problem with the following start state and goal description.

Based on the above data, answer the given subquestions.

In the planning graph, which of the following are mutex action pairs in Layer 1?

Select all that apply.

  1. A

    Stack(B,C), Putdown(B)

  2. B

    Stack(B,A), Putdown(B)

  3. C

    Stack(B,C), Stack(B,A)

  4. D

    Pickup(C), Putdown(B)

  5. E

    Unstack(A,D), Putdown(B)

Show answer

Correct answers

  • A

    Stack(B,C), Putdown(B)

  • B

    Stack(B,A), Putdown(B)

  • C

    Stack(B,C), Stack(B,A)

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.

PREDICATES

text
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

text
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) }

Consider the planning problem with the following start state and goal description.

Based on the above data, answer the given subquestions.

In the planning graph, which of the following are mutex proposition pairs in Layer 1?

Select all that apply.

  1. A

    clear(A), holding(B)

  2. B

    onTable(A), on(B,C)

  3. C

    onTable(B), on(B,C)

  4. D

    on(B,C), on(B,A)

Show answer

Correct answers

  • C

    onTable(B), on(B,C)

  • D

    on(B,C), on(B,A)

Question 23 on its own page

Question 24

+1 markWritten answer

CONSTRAINT SATISFACTION
The set of junctions (L, W, Y and T type junctions) that occur in a 2D line drawing of trihedral objects is provided below. The in-plane clockwise/counterclockwise rotations of these junctions are valid as well. These junctions provide constraints on the possible edge assignments (convex, concave, arrow) for the edges/lines in 2D line drawings of trihedral objects.
The junctions carry unique labels: L1, L2, L3, L4, L5, L6, T1, T2, T3, T4, W1, W2, W3, Y1, Y2, Y3. When required, use the labels in short answers.

Note: A 2D line drawing of trihedral objects is considered to be consistent if all the edges and junctions can be assigned labels that are consistent with each other, otherwise the drawing is considered to be inconsistent and all labels are reset to NIL.
Apply a suitable algorithm to assign consistent labels to edges/junctions in the 2D line drawings in the sub-questions. Choose a suitable edge and junction order for solving the problems.

Assign consistent labels to all the edges and junctions in the 2D line drawing shown below. Enter the labels of the junctions 1, 2, 3, 4 in the text box, in that order. Or enter NIL if the drawing has no consistent label assignment.

Enter a comma separated list of junction labels, or enter NIL.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X9,Y9,Z9,W9

Show answer

Correct answer: Y1,W1,L5,T4 or Y2,W2,L5,T4

Question 24 on its own page

Question 25

+1 markWritten answer

CONSTRAINT SATISFACTION
The set of junctions (L, W, Y and T type junctions) that occur in a 2D line drawing of trihedral objects is provided below. The in-plane clockwise/counterclockwise rotations of these junctions are valid as well. These junctions provide constraints on the possible edge assignments (convex, concave, arrow) for the edges/lines in 2D line drawings of trihedral objects.
The junctions carry unique labels: L1, L2, L3, L4, L5, L6, T1, T2, T3, T4, W1, W2, W3, Y1, Y2, Y3. When required, use the labels in short answers.

Note: A 2D line drawing of trihedral objects is considered to be consistent if all the edges and junctions can be assigned labels that are consistent with each other, otherwise the drawing is considered to be inconsistent and all labels are reset to NIL.
Apply a suitable algorithm to assign consistent labels to edges/junctions in the 2D line drawings in the sub-questions. Choose a suitable edge and junction order for solving the problems.

Assign consistent labels to all the edges and junctions in the 2D line drawing shown below. Enter the labels of the junctions 1, 2, 3, 4 in the text box, in that order. Or enter NIL if the drawing has no consistent label assignment.

Enter a comma separated list of junction labels, or enter NIL.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: X9,Y9,Z9,W9

Show answer

Correct answer: NIL

Question 25 on its own page