AI: Search Methods for Problem Solving · End Term · Sep 2022 · AN

You are the chairman of your colony association, which consist of volunteer members who are residents in your neighbourhood. At a recent meeting, you delegated a substantial amount of work to some of the other members. "I know these are difficult tasks, but you're part of this team and you need to get this work done", you told them. But at your next monthly meeting, you were surprised those association members weren't there as they simply decided to quit because they had better things to do with their time. Which aspect of teamwork is missing in this example?

**SEARCH** Consider a 5-4-1 water jug puzzle with three jugs a, b, c of capacity 5L, 4L, 1L, respectively. A state is represented as a three digit string ABC, where A, B, C denote the volume of water present in the jugs a, b, c, respectively. For example, 140 denotes a state where jug a has 1 liter of water, jug b has 4 liters of water and jug c is empty. Two types of moves (state transitions) are allowed: xEy: pick up jug x and empty it into jug y, xFy: pick up jug x and fill up (top up) jug y. So the possible moves are: aEb, aEc, aFb, aFc, bEa, bEc, bFa, bFc, cEa, cEb, cFa, cFb. **Tie-breaker:** in some states, both xEy and xFy may produce the same output state, in such cases, choose xEy to break the tie. For example, from the 140 state, both aEc and aFc produce the same output state 041, therefore, to break the tie choose aEc as the move. For the 5-4-1 water jug puzzle, the MoveGen function takes a state ABC and returns a set of states that can be produced in one move. For example, MoveGen(500) returns {140, 401 }. Based on the above data, answer the given subquestions.

Let 500 be the start state and 221 be the goal state, find the shortest path from start to goal. Enter the path starting with 500 as a comma separated list of states. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 500,411,747

**SEARCH** Consider a 5-4-1 water jug puzzle with three jugs a, b, c of capacity 5L, 4L, 1L, respectively. A state is represented as a three digit string ABC, where A, B, C denote the volume of water present in the jugs a, b, c, respectively. For example, 140 denotes a state where jug a has 1 liter of water, jug b has 4 liters of water and jug c is empty. Two types of moves (state transitions) are allowed: xEy: pick up jug x and empty it into jug y, xFy: pick up jug x and fill up (top up) jug y. So the possible moves are: aEb, aEc, aFb, aFc, bEa, bEc, bFa, bFc, cEa, cEb, cFa, cFb. **Tie-breaker:** in some states, both xEy and xFy may produce the same output state, in such cases, choose xEy to break the tie. For example, from the 140 state, both aEc and aFc produce the same output state 041, therefore, to break the tie choose aEc as the move. For the 5-4-1 water jug puzzle, the MoveGen function takes a state ABC and returns a set of states that can be produced in one move. For example, MoveGen(500) returns {140, 401 }. Based on the above data, answer the given subquestions.

Let 500 be the start state and 221 be the goal state, find the sequence of moves that produce the shortest path from start to goal. Enter the sequence of moves as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: aFc,cFb,aEc

**SEARCH FOR OPTIMAL SOLUTION** Under what cases does Depth First Iterative Deepening (DFID) guarantee an optimal solution?

**SEARCH FOR OPTIMAL SOLUTION** In the map, nodes are placed on a grid where each tile is 10x10 in size, is the Manhattan distance heuristic admissible?

**SEARCH FOR OPTIMAL SOLUTION** Given a finite state space with unit edge costs, and a heuristic function whose properties are not known, which of the following algorithms are suitable for finding the optimal path?

**SEARCH FOR OPTIMAL SOLUTION** Given a state space with Euclidean edge costs, and with the best admissible heuristics, which of the following algorithms will find the optimal path?

**SEARCH FOR OPTIMAL SOLUTION** Which of the following are true about the Branch-and-Bound method (discussed in the lecture) that is used for finding optimal tours for the Traveling Salesman Problem?

**GAMES** The figure shows a 4-ply game tree with evaluation function values at the horizon. The nodes in the horizon are assigned labels A,B,C,...,P. 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 are strategies for MAX?

**GAMES** The figure shows a 4-ply game tree with evaluation function values at the horizon. The nodes in the horizon are assigned labels A,B,C,...,P. 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 4-ply game tree with evaluation function values at the horizon. The nodes in the horizon are assigned labels A,B,C,...,P. 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 first five 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

**CONSTRAINT SATISFACTION** The figure shows a constraint graph of a Binary CSP and a part of the matching diagram. When a pair of variables (like, X1 and X5) do not have a constraint in the constraint graph then assume a UNIVERSAL RELATION in the matching diagram.

Process the variables, and their values, in ALPHABETIC order Based on the above data, answer the given subquestions.

The Forward-Checking algorithm begins by assigning X1=a. What are the NEXT four values assigned to variables by the Forward-Checking algorithm? List the values as a comma separated list in the order they are assigned. Enter a comma separated list of values. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: a,6,1,p**

**CONSTRAINT SATISFACTION** The figure shows a constraint graph of a Binary CSP and a part of the matching diagram. When a pair of variables (like, X1 and X5) do not have a constraint in the constraint graph then assume a UNIVERSAL RELATION in the matching diagram.

Process the variables, and their values, in ALPHABETIC order Based on the above data, answer the given subquestions.

What is the first solution found by the Forward-Checking algorithm? Enter a comma separated list of values. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: a,6,1,p**

**PROBLEM DECOMPOSITION** The figure shows an AND-OR graph that depicts how a problem S can be decomposed and transformed 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 with 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. **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.

Each edge has a unit cost. Solve for 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 and transformed 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 with 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. **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.

Each edge has a unit cost. Solve for S, then answer the given subquestions

Determine the value of the start node S after each node expansion. List the first three values of S that correspond to 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 and transformed 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 with 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. **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.

Each edge has a unit cost. Solve for 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**

**PROBLEM DECOMPOSITION** The figure shows an AND-OR graph that depicts how a problem S can be decomposed and transformed 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 with 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. **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.

Each edge has a unit cost. Solve for S, then answer the given subquestions

In the given AND-OR graph, is the heuristic admissible?

**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, ..., B1, B2, ..., B5, R1, R2, ..., R8, uniquely identify the nodes in the network. When required, use the above label ordering to **break ties** and to enter your answers.

Run the Rete algorithm for the Working Memory shown below, where 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, ..., B1, B2, ..., B5, R1, R2, ..., R8, uniquely identify the nodes in the network. When required, use the above label ordering to **break ties** and to enter your answers.

Run the Rete algorithm for the Working Memory shown below, where 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 tuples that will be ready to fire. If multiple rule-data tuples qualify then choose one. Enter a comma separated list with a rule label followed by timestamps in sorted order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: R1,101,102,103**

**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, ..., B1, B2, ..., B5, R1, R2, ..., R8, uniquely identify the nodes in the network. When required, use the above label ordering to **break ties** and to enter your answers.

Run the Rete algorithm for the Working Memory shown below, where 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. Enter a comma separated list with a rule label followed by timestamps in sorted order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: R1,101,102,103**

**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 for the given problem?

**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 for the given problem?

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