Consider the 3 blocks world in which only one block can be on another block and in which the operators include: picking up a block from the table, putting a block down on the table, stacking a block on another block, and unstacking a block from another block. The complete state space for this problem is illustrated below:

Notes:

• In the figure, states in this space are given arbitrary numbers as names in order to easily refer to them.
• When drawing search trees, number the nodes in the order they are expanded, circle these numbers to distinguish them from the numbers naming the nodes.
• Assume that all children of a state are shown in a search tree but that states resulting in a cycle in the resulting path from the root are eliminated as dead-end states as soon as they are generated (draw an X through them).
• If heuristic search is being used, next to each node generated, show the value of the evaluation function (e.g. "h=2" if just using h, or "1+2=3" for g+h=f when using A*).
• When there is an undetermined decision (tie) regarding which node to expand next, assume nodes with lowered numbered state names are preferred (i.e. expand node 1 before node 2, etc.).
• Assume a goal is detected immediately when it is generated (rather than waiting until it is expanded), except for A*, where waiting to check for goal-hood until expansion is critical to guaranteeing an optimal solution (with an admissible heuristic).

Consider the problem of starting in state 5 with the goal of getting to state 17:

1. Draw the search tree resulting from depth-first search. How many nodes are expanded? In what order? (That's "expanded" not "generated"; remember "expansion" is when a node's successors are generated.) (20 points)
2. Draw the search tree resulting from breadth-first search. How many nodes are expanded? In what order? (20 points)
3. Draw the search tree resulting from best-first search using as an evaluation function the number of blocks not in the correct place as an estimate of the remaining distance to the goal. For example, the heuristic value for state 6 is 2 since blocks A and C are not in the correct place (but block B is) relative to the goal state, 18. How many nodes are expanded? In what order? (20 points)
4. Repeat problem for hill-climbing instead of best-first search. Which expands fewer nodes? Why? (20 points)
5. Draw the search tree resulting from using A* with g being the level of the node being expanded in the tree and h being the same heuristic as above and assuming tie-breaking based on node numbers (i.e. expand the node with lower number). How many nodes are expanded? In what order? (20 points)
    

(stack B C) D 22 199 (unstack A C) 18 (puldown A) 17 B O (pickup B) (unstack B C) 21 1 (unstack C B) (stack CA) (putdown B) 20 (stack B A) (stack A C) a (pickup A) (unstuck C A) (pickup B) (stack C B) 16 AB (putdown C) (stack A C) (pickup A) Da (unstack B C) (unstack B A) (unstack A B) (pickup C) 8 ABU (putdown A) (putdown B) (putdown B) 13 (pickup B) (putdown A) 4 (unstack A C) (stack B A) (pickup C) (stack A B) (unstack A B) 5 15 (pickup A) 13 (stack A B) (stack B C) (unstack B A) 14 (stack C A) (putdown C) 6 (putdown C) 9 (pickup C) B (stack C B) (unstack C A) 7 (unstack C B) 12 DAK