1. Prove that if h(n) = h∗ (n) for all n, then whenever A* expands a node n, n must lie on an optimal path to a goal.

2. Let h be an admissible function and let f(·) = wc(·) + (1 − w)h(·) for 0 ≤ w ≤ 1. Will A* find an optimal solution when w = 1?, w = 1/2?, w = 3/4?.

3.  Consider the graph below:

We want to search for the shortest path from A to D using weighted A* (f(·) := wc(·) + (1 − w)h(·)). Assume h is defined so that:

 8,S = A 

h(S) =   

 0,S = D .

(a) Is h admissible? Justify your answer.

(b) Is h consistent? Justify your answer.

(c)  Show the order in which paths are explored and the contents of the frontier at each iteration for each of the following cases:

i. w = 0.

ii. w = 1.

iii. w = 1/2.

Do not use any form of path checking.

(d) Repeat (c) using path checking.         (e) Repeat (c) using multi-path checking.

4. If h is admissible and s0  is the initial state, how is h(s0 ) related to the cost of the solution found by A* search?

5. What happens if we use a heuristic h in A* search that does not have the guarantee that h(n) ≤ h∗ (n) for all states n?

6. We have 6 blocks: 3 black, and 3 white. They are arranged as follows: B B B W W W E,

where B denotes a black block, W denotes a white block, and E denotes an empty space.  The goal is to arrange the blocks such that all the white blocks are on the left, and the black blocks are on the right (without regard to the position of the empty space).

The blocks can be moved as follows:

❼ A block may move to an adjacent empty cell with unit cost.

❼ A block may hop over at most two other tiles into an empty cell with a cost

equal to the number of tiles hoped over.

(a) Does this problem have cycles? Can you find one of length 3 or more? (b)  Specify a heuristic function for this problem.

(c) Describe the first 10 nodes that would expanded by BFS, in the order they are expanded.

7.  Consider the problem of finding a path in the grid shown below from the position s to the position g .  The robot can move on the grid horizontally and vertically, one square at a time (each step has a cost of one).  No step may be made into a forbidden shaded area.  The search space and the shaded areas are illustrated. On the grid, number the nodes in the order in which they are removed from the frontier in a depth-first search from s to g, given that the order of the operators you will test is: up, left, right, then down. Assume there is a cycle check. Number the nodes in order in which they are taken off the frontier for an A* search for the same graph. Manhattan distance should be used as the heuristic function. That is, h(n) for any node n is the Manhattan distance from n to g .