AI: Search Methods for Problem Solving · End Term · May 2026 · AN

Answer the given sub-questions based on the above problem using algorithms presented in the lectures.

Is it possible to construct a TSP tour by traversing only along the edges in the graph?

Answer the given sub-questions based on the above problem using algorithms presented in the lectures.

What will be the size of the OPEN list when GoalTest returns true during Breadth First search? (Note: nodes already seen are not reopened.)

Answer the given sub-questions based on the above problem using algorithms presented in the lectures.

What will be the cost of the path found by the A* algorithm? Use Big-O notation.

Answer the given sub-questions based on the above problem using algorithms presented in the lectures.

The heuristic is __________ .

Answer the given sub-questions based on the above problem using algorithms presented in the lectures.

What is the full form of DC BFHS?

**GAMES** Consider any k-ply game tree having MAX as root, where k is an ODD number, and each player having exactly 2 moves at all levels except the leaf level, and the evals of the leaf nodes (from left to right) form a sequence starting from zero, incremented by 1. The minimax value is __________ . Give a precise and concise answer.

Let the SSS* algorithm process the subtree with h=30, identify the leaf node(s) solved by the algorithm, and enter those nodes in the text box. (Note: when nodes have the same h-value break ties in Depth-First search order.)

Enter a comma separated list of node labels. NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS.

**PROBLEM DECOMPOSITION** The figure shows an AND-OR decomposition of problem S into subproblems. The nodes are uniquely identified by labels (S, A, B, C, …). Each node displays its heuristic cost, but primitive nodes (double border) display the actual cost. Primitive nodes attain SOLVED status when their parent is expanded, so primitive nodes are 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 given sub-questions.

For each node expanded by AO* algorithm, determine the value assigned/propagated to the start node S. Enter the values of S in the time order, in the order it was updated. Enter a comma separated list of integers. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

**PROBLEM DECOMPOSITION** The figure shows an AND-OR decomposition of problem S into subproblems. The nodes are uniquely identified by labels (S, A, B, C, …). Each node displays its heuristic cost, but primitive nodes (double border) display the actual cost. Primitive nodes attain SOLVED status when their parent is expanded, so primitive nodes are 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 given sub-questions.

Did AO* return the optimal solution for the given problem?

**RULE BASED EXPERT SYSTEMS** A Rete Net for classification of properties is shown in the figure. The labels A1, A2, A3, ..., A10, A11, A12, A13, ..., and B1, B2, B3, B4 uniquely identify nodes in the network. When required, use the above label ordering to **break ties** and to enter short answers.

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 sub-questions.

Identify the rule-data tuples in the conflict-set. Enter one rule data tuple from the conflict-set as a comma separated list in the text box: rule name followed by timestamps in **ascending order**. NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: R9,201,202,203,204**

**RULE BASED EXPERT SYSTEMS** A Rete Net for classification of properties is shown in the figure. The labels A1, A2, A3, ..., A10, A11, A12, A13, ..., and B1, B2, B3, B4 uniquely identify nodes in the network. When required, use the above label ordering to **break ties** and to enter short answers.

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 sub-questions.

If the Inference Engine uses **Specificity** as the conflict resolution strategy then which rule-data tuple(s) will qualify? Enter one rule data tuple as a comma separated list in the text box: rule name followed by timestamps in **ascending order**. NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: R9,201,202,203,204**

**RULE BASED EXPERT SYSTEMS** A Rete Net for classification of properties is shown in the figure. The labels A1, A2, A3, ..., A10, A11, A12, A13, ..., and B1, B2, B3, B4 uniquely identify nodes in the network. When required, use the above label ordering to **break ties** and to enter short answers.

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 sub-questions.

If the Inference Engine uses **Recency** as the conflict resolution strategy then which rule-data tuple(s) will qualify? Enter one rule data tuple as a comma separated list in the text box: rule name followed by timestamps in **ascending order**. NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS. **Answer format: R9,201,202,203,204**

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

**Tie-breaker 1**: Treat the goal description, preconditions and effects as lists that are accessed from left to right. **Tie-breaker 2**: When list elements are pushed one by one to a stack, the last element in the list will be at the top of the stack. The GSP stack shown below grows downwards, so the last line is the top of the stack, it shows the first three actions pushed and no other action has been pushed/popped yet, and the plan is currently empty.

Analyze the stack, determine the three actions and then answer the sub-questions.

After ACTION-2 is pushed to the stack, determine the propositions in the current state that caused ACTION-3 to be pushed to the stack. Enter those propositions (in sorted order) in the text box. Enter NIL or enter a comma separated list of propositions in alphabetical order. NO SPACES, TABS OR EXTRANEOUS CHARACTERS. **Answer format: armEmpty,clear(X),holding(X),on(X,Y),onTable(X)**

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

**Tie-breaker 1**: Treat the goal description, preconditions and effects as lists that are accessed from left to right. **Tie-breaker 2**: When list elements are pushed one by one to a stack, the last element in the list will be at the top of the stack. The GSP stack shown below grows downwards, so the last line is the top of the stack, it shows the first three actions pushed and no other action has been pushed/popped yet, and the plan is currently empty.

Analyze the stack, determine the three actions and then answer the sub-questions.

Determine the proposition(s) in the current state that will trigger the popping of ACTION-3, ACTION-2 and ACTION-1 in that order. Enter those propositions (in sorted order) in the text box. Enter NIL or enter a comma separated list of propositions in alphabetical order. NO SPACES, TABS OR EXTRANEOUS CHARACTERS. **Answer format: armEmpty,clear(X),holding(X),on(X,Y),onTable(X)**

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

The GraphPlan algorithm is in flight constructing the planning graph (P0, A1, P1, A2, P2, ...); the propositions and mutex pairs in k-th propositional layer (Pk) are provided.

Based on the above data, answer the given subquestions.

Find the applicable actions in layer k+1? Enter one of the applicable actions in the text box.

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

The GraphPlan algorithm is in flight constructing the planning graph (P0, A1, P1, A2, P2, ...); the propositions and mutex pairs in k-th propositional layer (Pk) are provided.

Based on the above data, answer the given subquestions.

Find the new propositions that will be added to layer k+1? Enter one of the new propositions in the text box.

**AUTOMATED PLANNING** Consider a planning problem in the multiarm blocks-world domain, with 2^(k^2) blocks and k^2 arms, for k greater than 5, where multiple empty arms cannot simultaneously pick up (respectively, unstack) the same block, and multiple arms holding different blocks cannot simultaneously stack on the same block, but multiple arms can simultaneously perform independent tasks. Extend the operators in single-arm case to multiarm case by adding an arm parameter. In the multiarm case, Pickup(n,X) and Unstack(n,X,Y) actions will delete clear(X), and Putdown(n,X) and Stack(n,X,Y) actions will add clear(X). The start state which is a valid state is not given to us. The goal state has all the blocks as a single tower resting on the table. Compute the worst case makespan. Give a precise and concise answer.

Given a valid planning problem, under what conditions will GraphPlan return a valid plan? Give a precise and concise answer. **NOTE:** Your answer should not exceed 64 words.

Can GraphPlan solve the Sussman anomaly?

**CONSTRAINT SATISFACTION** Consider a CSP over 3 variables A, B, C, where the domains and constraints are:

where, mod(n,d) returns the remainder after dividing integer n by integer d, for example, mod(8,3)=2, mod(12,3)=0, mod(16,3)=1. Compute the three constraints such that the values are from respective domains, draw the constraint graph and matching-diagram, then answer the given sub-questions.

Is the given CSP network 3-consistent?

**CONSTRAINT SATISFACTION** Consider a CSP over 3 variables A, B, C, where the domains and constraints are:

where, mod(n,d) returns the remainder after dividing integer n by integer d, for example, mod(8,3)=2, mod(12,3)=0, mod(16,3)=1. Compute the three constraints such that the values are from respective domains, draw the constraint graph and matching-diagram, then answer the given sub-questions.

Count the number of solutions to the given CSP. Enter the count in the text box. Enter an integer.

**CONSTRAINT SATISFACTION** Consider a CSP over 3 variables A, B, C, where the domains and constraints are:

where, mod(n,d) returns the remainder after dividing integer n by integer d, for example, mod(8,3)=2, mod(12,3)=0, mod(16,3)=1. Compute the three constraints such that the values are from respective domains, draw the constraint graph and matching-diagram, then answer the given sub-questions.

If the 8-Queens problem is modelled as a Binary Constraint Network, the number of binary relations in the constraint set will be __________ . Enter an integer.

**CONSTRAINT SATISFACTION** Consider a CSP over 3 variables A, B, C, where the domains and constraints are:

where, mod(n,d) returns the remainder after dividing integer n by integer d, for example, mod(8,3)=2, mod(12,3)=0, mod(16,3)=1. Compute the three constraints such that the values are from respective domains, draw the constraint graph and matching-diagram, then answer the given sub-questions.

When is a CSP network considered to be i-Consistent? Give a precise and concise answer. **NOTE:** Your answer should not exceed 64 words.

**CONSTRAINT SATISFACTION** Consider a CSP over 3 variables A, B, C, where the domains and constraints are:

where, mod(n,d) returns the remainder after dividing integer n by integer d, for example, mod(8,3)=2, mod(12,3)=0, mod(16,3)=1. Compute the three constraints such that the values are from respective domains, draw the constraint graph and matching-diagram, then answer the given sub-questions.

The Waltz Algorithm __________ .