QUESTION: The block's world problem consists of five blocks numbered from 1 to 5. The left figure below (a) shows two possible configurations of such blocks; note that the relative position of the piles does not matter, thus the configuration on the left is equivalent to the one in the right in Fig. 1(a). Every block can be either on the table or atop any other block. The goal is to stack the blocks into a single pile in the sequence shown in the right figure (b), from 1 (at the top of the pile) to 5 (at the bottom of the pile), starting from a given set of piles, by moving the smallest possible number of blocks. Only a block that is not under another block can be moved and can be only placed either on the table or atop another pile. 1 2 3 4 2 5 3 N | 4 4 5 or Goal: (a) (b) Figure 1: Illustration of the blocks world problem 1. Formulate the above block's world as a search problem by answering the following questions: (a) Propose a simple state representation? (b) What is the initial state? (C) What is the goal state? (d) What are the actions? (e) What is the path cost? 2. Assuming that the initial configuration is the one shown on the left in the figure above, show how the uniform cost search builds the search tree, avoiding repeated states, by clearly showing the order of expansion of each node, the actions associated to the edges of the tree and their cost, the state and the path cost of each node. 3. Assuming that the initial configuration is the one shown on the left in the figure above, and considering a heuristic function defined as the number of blocks that are not in the highest pile (or in one of the highest piles), show how the A* search strategy builds the search tree the first four nodes, avoiding repeated states. Clearly show the order of expansion of each node, the actions associated with the edges of the tree and their cost, and the state, the path cost and the value of the heuristic of each node. QUESTION: The block's world problem consists of five blocks numbered from 1 to 5. The left figure below (a) shows two possible configurations of such blocks; note that the relative position of the piles does not matter, thus the configuration on the left is equivalent to the one in the right in Fig. 1(a). Every block can be either on the table or atop any other block. The goal is to stack the blocks into a single pile in the sequence shown in the right figure (b), from 1 (at the top of the pile) to 5 (at the bottom of the pile), starting from a given set of piles, by moving the smallest possible number of blocks. Only a block that is not under another block can be moved and can be only placed either on the table or atop another pile. 1 2 3 4 2 5 3 N | 4 4 5 or Goal: (a) (b) Figure 1: Illustration of the blocks world problem 1. Formulate the above block's world as a search problem by answering the following questions: (a) Propose a simple state representation? (b) What is the initial state? (C) What is the goal state? (d) What are the actions? (e) What is the path cost? 2. Assuming that the initial configuration is the one shown on the left in the figure above, show how the uniform cost search builds the search tree, avoiding repeated states, by clearly showing the order of expansion of each node, the actions associated to the edges of the tree and their cost, the state and the path cost of each node. 3. Assuming that the initial configuration is the one shown on the left in the figure above, and considering a heuristic function defined as the number of blocks that are not in the highest pile (or in one of the highest piles), show how the A* search strategy builds the search tree the first four nodes, avoiding repeated states. Clearly show the order of expansion of each node, the actions associated with the edges of the tree and their cost, and the state, the path cost and the value of the heuristic of each node