AI: Search Methods for Problem Solving End Term: 21 December 2025 (September 2025 term)

SEARCH The figure shows a map on a uniform grid where each tile is 1x1 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,G Answers Case Sensitive : No

SEARCH The figure shows a map on a uniform grid where each tile is 1x1 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.

Answers Case Sensitive : No

SEARCH The figure shows a map on a uniform grid where each tile is 1x1 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. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: S,X,Y,Z,G Answers Case Sensitive : No

SEARCH The figure shows a map on a uniform grid where each tile is 1x1 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?

SEARCH The figure shows a map on a uniform grid where each tile is 1x1 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.

Select the correct statement about the given graph.

GAMES: ALPHA-BETA Consider a game tree with the root node as MAX. Alpha-Beta algorithm is in mid-flight currently processing a path from the root to a node labeled N. The snapshot of evals of nodes along the current path is: 2, 14, 4, 10, N. Where evals are restricted to EVEN NUMBERS greater than zero and less than 15. Based on the above data, answer the given subquestions.

Determine the eval of node N that will induce a cutoff to prune its siblings. Enter an even number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 16

GAMES: ALPHA-BETA Consider a game tree with the root node as MAX. Alpha-Beta algorithm is in mid-flight currently processing a path from the root to a node labeled N. The snapshot of evals of nodes along the current path is: 2, 14, 4, 10, N. Where evals are restricted to EVEN NUMBERS greater than zero and less than 15. Based on the above data, answer the given subquestions.

What type of cut-off is induced by the eval selected for N?

GAMES: SSS STAR The figure shows a game tree with evaluation function values at the horizon nodes. The horizon nodes are labeled from A to D. Use these labels to enter a horizon node or a list of horizon nodes in short answers. 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.

Run SSS* algorithm on the game tree, then answer the sub-questions.

Answers Case Sensitive : No

GAMES: SSS STAR The figure shows a game tree with evaluation function values at the horizon nodes. The horizon nodes are labeled from A to D. Use these labels to enter a horizon node or a list of horizon nodes in short answers. 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.

Run SSS* algorithm on the game tree, then answer the sub-questions.

Answers Case Sensitive : No

PROBLEM DECOMPOSITION The figure shows an AND-OR decomposition of problem S into smaller problems. The nodes are uniquely identified by labels (S, A, B, C, …). Each node shows the heuristic estimate of the cost of solving that node. Nodes shown in double lines are primitive nodes and their values are actual costs. A primitive node is added to the graph, with SOLVED status, when its parent is expanded. And therefore, a primitive node is never expanded. 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.

Answers Case Sensitive : No

PROBLEM DECOMPOSITION The figure shows an AND-OR decomposition of problem S into smaller problems. The nodes are uniquely identified by labels (S, A, B, C, …). Each node shows the heuristic estimate of the cost of solving that node. Nodes shown in double lines are primitive nodes and their values are actual costs. A primitive node is added to the graph, with SOLVED status, when its parent is expanded. And therefore, a primitive node is never expanded. 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.

Answers Case Sensitive : No

PROBLEM DECOMPOSITION The figure shows an AND-OR decomposition of problem S into smaller problems. The nodes are uniquely identified by labels (S, A, B, C, …). Each node shows the heuristic estimate of the cost of solving that node. Nodes shown in double lines are primitive nodes and their values are actual costs. A primitive node is added to the graph, with SOLVED status, when its parent is expanded. And therefore, a primitive node is never expanded. 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 can you conclude about the given AND-OR decomposition?

RULE BASED EXPERT SYSTEMS A Rete Net for classification of vehicles is shown in the figure. 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.

The Working Memory contains the following WMEs uniquely identified by timestamps (sequence numbers). Assume that WMEs reside in the appropriate Alpha node, and Beta nodes simply point to WMEs in the Alpha nodes.

For each WME identify its location (node label) in the Rete Net, then prepare the conflict set for the first Match-Resolve-Execute cycle, then answer the sub-questions.

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

RULE BASED EXPERT SYSTEMS A Rete Net for classification of vehicles is shown in the figure. 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.

The Working Memory contains the following WMEs uniquely identified by timestamps (sequence numbers). Assume that WMEs reside in the appropriate Alpha node, and Beta nodes simply point to WMEs in the Alpha nodes.

For each WME identify its location (node label) in the Rete Net, then prepare the conflict set for the first Match-Resolve-Execute cycle, then answer the sub-questions.

If the Inference Engine uses Specificity for conflict resolution then which rule-data tuple will fire in the first round?

RULE BASED EXPERT SYSTEMS A Rete Net for classification of vehicles is shown in the figure. 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.

The Working Memory contains the following WMEs uniquely identified by timestamps (sequence numbers). Assume that WMEs reside in the appropriate Alpha node, and Beta nodes simply point to WMEs in the Alpha nodes.

For each WME identify its location (node label) in the Rete Net, then prepare the conflict set for the first Match-Resolve-Execute cycle, then answer the sub-questions.

If the Inference Engine uses Recency for conflict resolution which rule-data tuple will fire in the first round?

AUTOMATED PLANNING 1 Answer the given subquestions.

Consider actions a and b and two feasible orderings (a then b) and (b then a). Which of the following conditions will produce different outcomes for each ordering?

AUTOMATED PLANNING 1 Answer the given subquestions.

In planning graphs constructed by GraphPlan, actions a and b in layer n are mutex __________ .

AUTOMATED PLANNING 1 Answer the given subquestions.

In planning graphs constructed by GraphPlan, propositions P and Q in layer n are mutex __________ .

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

The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two consecutive propositional layers (layer k and k+1) are presented in the figure. Both proposition layers are fully populated (no missing propositions).

Mutex proposition pairs in layer k are: (on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)). Populate the action layer and mutex links, then answer the sub-questions.

What can you conclude about layer k?

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

The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two consecutive propositional layers (layer k and k+1) are presented in the figure. Both proposition layers are fully populated (no missing propositions).

Mutex proposition pairs in layer k are: (on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)). Populate the action layer and mutex links, then answer the sub-questions.

Which of the following are applicable actions in layer k+1?

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

The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two consecutive propositional layers (layer k and k+1) are presented in the figure. Both proposition layers are fully populated (no missing propositions).

Mutex proposition pairs in layer k are: (on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)). Populate the action layer and mutex links, then answer the sub-questions.

Which of the following are mutex pairs in layer k+1?

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

The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two consecutive propositional layers (layer k and k+1) are presented in the figure. Both proposition layers are fully populated (no missing propositions).

Mutex proposition pairs in layer k are: (on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)). Populate the action layer and mutex links, then answer the sub-questions.

armEmpty and clear(B) in layer k+1 are non mutex because __________ .

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C (processed in that order) with domains and constraints as shown below.

Draw the constraint graph and matching-diagram then answer the sub-questions.

Is the given CSP arc consistent?

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C (processed in that order) with domains and constraints as shown below.

Draw the constraint graph and matching-diagram then answer the sub-questions.

If the given CSP is not already arc consistent, make it arc consistent, then check if it is path consistent.

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C (processed in that order) with domains and constraints as shown below.

Draw the constraint graph and matching-diagram then answer the sub-questions.

Does the given CSP have a solution? Enter the solution for the variables A,B,C as a comma separated list. Enter NIL if there is no solution. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 1,2,3 Answers Case Sensitive : No

SEARCH The figure shows a map on a uniform grid where each tile is 1x1 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.

GAMES: ALPHA-BETA Consider a game tree with the root node as MAX. Alpha-Beta algorithm is in mid-flight currently processing a path from the root to a node labeled N. The snapshot of evals of nodes along the current path is: 2, 14, 4, 10, N. Where evals are restricted to EVEN NUMBERS greater than zero and less than 15. Based on the above data, answer the given subquestions.

GAMES: SSS STAR The figure shows a game tree with evaluation function values at the horizon nodes. The horizon nodes are labeled from A to D. Use these labels to enter a horizon node or a list of horizon nodes in short answers. 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.

Run SSS* algorithm on the game tree, then answer the sub-questions.

PROBLEM DECOMPOSITION The figure shows an AND-OR decomposition of problem S into smaller problems. The nodes are uniquely identified by labels (S, A, B, C, …). Each node shows the heuristic estimate of the cost of solving that node. Nodes shown in double lines are primitive nodes and their values are actual costs. A primitive node is added to the graph, with SOLVED status, when its parent is expanded. And therefore, a primitive node is never expanded. 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.

RULE BASED EXPERT SYSTEMS A Rete Net for classification of vehicles is shown in the figure. 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.

The Working Memory contains the following WMEs uniquely identified by timestamps (sequence numbers). Assume that WMEs reside in the appropriate Alpha node, and Beta nodes simply point to WMEs in the Alpha nodes.

For each WME identify its location (node label) in the Rete Net, then prepare the conflict set for the first Match-Resolve-Execute cycle, then answer the sub-questions.

AUTOMATED PLANNING 1 Answer the given subquestions.

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

The GraphPlan algorithm is in mid-flight solving a planning problem, from the planning graph two consecutive propositional layers (layer k and k+1) are presented in the figure. Both proposition layers are fully populated (no missing propositions).

Mutex proposition pairs in layer k are: (on(A,B), holding(A)), (on(A,B), clear(B)), (armEmpty, clear(B)), (armEmpty, holding(A)). Populate the action layer and mutex links, then answer the sub-questions.

CONSTRAINT SATISFACTION Consider a CSP over 3 variables A, B, C (processed in that order) with domains and constraints as shown below.

Draw the constraint graph and matching-diagram then answer the sub-questions.