AI: Search Methods for Problem Solving · End Term · Jan 2023 · AN

Find the total number of prime paths in the given CFG?

**SEARCH** A MoveGen for a state space where S is the start node and G is the goal node is shown in the table. The MoveGen function returns nodes in the order as shown in the table. Use DFS and BFS to find a path from S to G. Note: DFS and BFS inspect only new nodes.

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

**TSP BnB** TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below. Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, …, f1, f2). Use the reference numbers to break ties. When required, use 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**

**TSP BnB** TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below. Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, …, f1, f2). Use the reference numbers to break ties. When required, use 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 BnB 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 BnB** TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below. Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, …, f1, f2). Use the reference numbers to break ties. When required, use 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? Enter the node reference number in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter a node reference number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: a9**

**TSP BnB** TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below. Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, …, f1, f2). Use the reference numbers to break ties. When required, use 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.

What is the cost of the optimal tour? Enter the cost of the optimal tour in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter an integer. NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: 42**

**TSP BnB** TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below. Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, …, f1, f2). Use the reference numbers to break ties. When required, use 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**

**SEARCH FOR OPTIMAL SOLUTION** 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 and the cost of each edge is **5 units**. The MoveGen function returns nodes in alphabetical order. Use Manhattan Distance as the heuristic function. Where necessary, use node labels to break ties.

Based on the above data, answer the given subquestions.

What is the path found by A*? 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 FOR OPTIMAL SOLUTION** 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 and the cost of each edge is **5 units**. The MoveGen function returns nodes in alphabetical order. Use Manhattan Distance as the heuristic function. Where necessary, use node labels to break ties.

Based on the above data, answer the given subquestions.

What is the cost of the path found by A*? Enter an integer. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: 17**

**SEARCH FOR OPTIMAL SOLUTION** 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 and the cost of each edge is **5 units**. The MoveGen function returns nodes in alphabetical order. Use Manhattan Distance as the heuristic function. Where necessary, use node labels to break ties.

Based on the above data, answer the given subquestions.

Is the Manhattan Distance admissible for the given problem?

**GAMES** The figure shows a 3-ply game tree with evaluation function values defined at horizon. The nodes in the horizon are labeled from A to L. Use these labels when asked to enter a horizon node or a list of horizon nodes. **Tie-breaker:** when several nodes qualify then select the left most node, if tie persists then select the deepest node among the left most nodes.

Based on the above data, answer the given subquestions.

Which of the following is a strategy for MAX?

**GAMES** The figure shows a 3-ply game tree with evaluation function values defined at horizon. The nodes in the horizon are labeled from A to L. Use these labels when asked to enter a horizon node or a list of horizon nodes. **Tie-breaker:** when several nodes qualify then select the left most node, if tie persists then select the deepest node among the left most nodes.

Based on the above data, answer the given subquestions.

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

**GAMES** The figure shows a 3-ply game tree with evaluation function values defined at horizon. The nodes in the horizon are labeled from A to L. Use these labels when asked to enter a horizon node or a list of horizon nodes. **Tie-breaker:** when several nodes qualify then select the left most node, if tie persists then select the deepest node among the left most nodes.

Based on the above data, answer the given subquestions.

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

**GAMES** The figure shows a 3-ply game tree with evaluation function values defined at horizon. The nodes in the horizon are labeled from A to L. Use these labels when asked to enter a horizon node or a list of horizon nodes. **Tie-breaker:** when several nodes qualify then select the left most node, if tie persists then select the deepest node among the left most nodes.

Based on the above data, answer the given subquestions.

Force the MinMax value to 36 by changing the eval of only one horizon node. Select the horizon node that you want to change and select the largest possible value for that node. Enter the node label and the new value as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: X,17**

**PROBLEM DECOMPOSITION** The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or more simpler 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:** For nodes with the same cost, expand in the ascending order of 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 given 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**

**PROBLEM DECOMPOSITION** The figure shows an AND-OR graph that depicts how a problem S can be decomposed into one or more simpler 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:** For nodes with the same cost, expand in the ascending order of 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 given subquestions.

Determine the value of the start node S after each node expansion. Ignore the initial value of S and list the first three values of S computed from the first three node expansions. 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 simpler 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:** For nodes with the same cost, expand in the ascending order of 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 given 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**

**RULE BASED EXPERT SYSTEMS** A Rete Net for classification of machines is shown in the figure. The labels A1, A2, A3, ..., A10, A11, A12, A13, ..., and B1, B2, B3 uniquely identify 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.

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?

**RULE BASED EXPERT SYSTEMS** A Rete Net for classification of machines is shown in the figure. The labels A1, A2, A3, ..., A10, A11, A12, A13, ..., and B1, B2, B3 uniquely identify 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.

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.

**RULE BASED EXPERT SYSTEMS** A Rete Net for classification of machines is shown in the figure. The labels A1, A2, A3, ..., A10, A11, A12, A13, ..., and B1, B2, B3 uniquely identify 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.

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.

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

Based on the above data, answer the given subquestions.

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.

Based on the above data, answer the given subquestions.

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.

Based on the above data, answer the given subquestions.

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.

Based on the above data, answer the given subquestions.

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.

Apply a suitable algorithm to assign labels to edges/junctions in the 2D line drawings given in the sub-questions, process the edges and junctions in any order you see fit. **Note:** A 2D line drawing of trihedral objects is valid if and only if all the edges and junctions in the drawing are assigned consistent labels, otherwise the drawing is inconsistent and all labels are reset to NIL. Based on the above data, answer the given subquestions.

For the 2D line drawing, assign consistent labels to all edges and junctions. 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**

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

Apply a suitable algorithm to assign labels to edges/junctions in the 2D line drawings given in the sub-questions, process the edges and junctions in any order you see fit. **Note:** A 2D line drawing of trihedral objects is valid if and only if all the edges and junctions in the drawing are assigned consistent labels, otherwise the drawing is inconsistent and all labels are reset to NIL. Based on the above data, answer the given subquestions.

For the 2D line drawing, assign consistent labels to all edges and junctions. Enter the labels of the junctions 1, 2, 3 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**