AI: Search Methods for Problem Solving · End Term · Jan 2024 · FN

**SEARCH**

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**

**SEARCH**

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**

**SEARCH**

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**

**SEARCH**

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

**SEARCH**

What can you say about the heuristic function for the given graph?

**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, c2, d1, d2, e1, e2, e3, e4). Use the reference numbers to break ties. 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.

Based on the above data, answer the given subquestions.

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**

**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, c2, d1, d2, e1, e2, e3, e4). Use the reference numbers to break ties. 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.

Based on the above data, answer the given subquestions.

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**

**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, c2, d1, d2, e1, e2, e3, e4). Use the reference numbers to break ties. 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.

Based on the above data, answer the given subquestions.

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**

**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, c2, d1, d2, e1, e2, e3, e4). Use the reference numbers to break ties. 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.

Based on the above data, answer the given subquestions.

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**

**GAMES** The figure shows a game tree with evaluation function values at the leaf nodes. The leaf nodes are labeled from A to J. Use these labels to enter a leaf node or a list of leaf 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.

Based on the above data, answer the given subquestions.

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

**GAMES** The figure shows a game tree with evaluation function values at the leaf nodes. The leaf nodes are labeled from A to J. Use these labels to enter a leaf node or a list of leaf 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.

Based on the above data, answer the given subquestions.

List the leaf 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**

**GAMES** The figure shows a game tree with evaluation function values at the leaf nodes. The leaf nodes are labeled from A to J. Use these labels to enter a leaf node or a list of leaf 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.

Based on the above data, answer the given subquestions.

List the leaf 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**

**GAMES** The figure shows a game tree with evaluation function values at the leaf nodes. The leaf nodes are labeled from A to J. Use these labels to enter a leaf node or a list of leaf 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.

Based on the above data, answer the given subquestions.

List the leaf nodes solved (assigned SOLVED status) 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**

**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 2 units. **Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels. **Tie-breaker 2:** For AND nodes, select the unsolved branch with the highest cost.

Use AO* algorithm to solve S, then answer the sub-questions.

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**

**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 2 units. **Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels. **Tie-breaker 2:** For AND nodes, select the unsolved branch with the highest cost.

Use AO* algorithm to solve S, then answer the sub-questions.

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**

**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 2 units. **Tie-breaker 1:** If several nodes have the same cost then break the tie using node labels. **Tie-breaker 2:** For AND nodes, select the unsolved branch with the highest cost.

Use AO* algorithm to solve S, then answer the sub-questions.

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

**RULE BASED EXPERT SYSTEMS** A Rete Net for classifying lenses based on surface properties (convex, concave, planar, radius of curvature, and number of sides) is shown in the figure. Each lens is uniquely identified by “itemNo” attribute, the remaining classes and attributes are self explanatory. A part of the Rete Net that classifies mushrooms (as edible or poisonous) is shown in the figure. The labels A1, A2, ..., A15, ..., B1, B2, …, B5, R1, …, R6 uniquely identify the nodes in the network. When required, use the above label ordering to **break ties** and to enter short answers. **Note:** beta nodes B4 and B5 compare the radius of curvature of two surfaces.

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

**RULE BASED EXPERT SYSTEMS** A Rete Net for classifying lenses based on surface properties (convex, concave, planar, radius of curvature, and number of sides) is shown in the figure. Each lens is uniquely identified by “itemNo” attribute, the remaining classes and attributes are self explanatory. A part of the Rete Net that classifies mushrooms (as edible or poisonous) is shown in the figure. The labels A1, A2, ..., A15, ..., B1, B2, …, B5, R1, …, R6 uniquely identify the nodes in the network. When required, use the above label ordering to **break ties** and to enter short answers. **Note:** beta nodes B4 and B5 compare the radius of curvature of two surfaces.

If the Inference Engine uses **Specificity** as the conflict resolution strategy then which of the following rule-data tuples will qualify?

**RULE BASED EXPERT SYSTEMS** A Rete Net for classifying lenses based on surface properties (convex, concave, planar, radius of curvature, and number of sides) is shown in the figure. Each lens is uniquely identified by “itemNo” attribute, the remaining classes and attributes are self explanatory. A part of the Rete Net that classifies mushrooms (as edible or poisonous) is shown in the figure. The labels A1, A2, ..., A15, ..., B1, B2, …, B5, R1, …, R6 uniquely identify the nodes in the network. When required, use the above label ordering to **break ties** and to enter short answers. **Note:** beta nodes B4 and B5 compare the radius of curvature of two surfaces.

If the Inference Engine uses **Recency** as the conflict resolution strategy then which of the following rule-data tuples will qualify?.

**AUTOMATED PLANNING** The domain description of a Blocks World with a single one-armed robot is given below. This is the same domain used in the assignments.

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

**AUTOMATED PLANNING** The domain description of a Blocks World with a single one-armed robot is given below. This is the same domain used in the assignments.

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

**AUTOMATED PLANNING** The domain description of a Blocks World with a single one-armed robot is given below. This is the same domain used in the assignments.

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

**AUTOMATED PLANNING** The domain description of a Blocks World with a single one-armed robot is given below. This is the same domain used in the assignments.

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

**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. Based on the above data, answer the given subquestions.

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. Otherwise 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: Y9,T9,W9,L9**

**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. Based on the above data, answer the given subquestions.

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. Otherwise 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: Y9,T9,W9,L9**