CS440 -INTRODUCTION TO ARTIFICIAL INTELLIGENCE  -  Assignment 2 - Solved

Search Problems in AI


Problem 1 (10 points): Trace the operation of A∗ search (the tree version) applied to the problem of getting to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes that the algorithm will consider and the f, g, and h score for each node. You don’t need to draw the graph, just right down a sequence of (city,f(city),g(city),h(city)) in the order in which the nodes are expanded.

 

Figure 1: A simplified road map of part of Romania indicating distances between different cities.

Arad

Bucharest

Craiova

Drobeta

Eforie

Fagaras

Giurgiu Hirsova

Iasi

Lugoj
366

 0

160

242

161

176 77

151

226

244
Mehadia

Neamt

Oradea

Pitesti

Rimnicu Vilcea

Sibiu

Timisoara

Urziceni

Vaslui

Zerind
241

234

380

100 193

253

329

80

199

374
Figure 2: Straight-line distances to Bucharest

Problem 2 (10 points): Consider a state space where the start state is number 1 and each state k has two successors: numbers 2k and 2k +1.

(a)    Suppose the goal state is 11. List the order in which states will be visited for breadthfirst search, depth-limited search with limit 3, and iterative deepening search.

(b)    How well would bidirectional search work on this problem? List the order in which states will be visited. What is thebranching factor in each direction of the bidirectional search?

Problem 3 (5 points): Which of the following statements are correct and which ones are wrong?

(a)    Breadth-first search is a special case of uniform-cost search.

(b)    Depth-first search is a special case of best-first tree search.

(c)    Uniform-cost search is a special case of A∗ search.

(d)    Depth-first graph search is guaranteed to return an optimal solution.

(e)    Breadth-first graph search is guaranteed to return an optimal solution.

(f)     Uniform-cost graph search is guaranteed to return an optimal solution.

(g)    A∗ graph search is guaranteed to return an optimal solution if the heuristic is consistent.

(h)    A∗ graph search is guaranteed to expand no more nodes than depth-first graph search if the heuristic is consistent.

(i)      A∗ graph search is guaranteed to expand no more nodes than uniform-cost graph search if the heuristic is consistent.

Problem 4 (2 points): Iterative deepening is sometimes used as an alternative to breadth first search. Give one advantage of iterative deepening over BFS, and give one disadvantage of iterative deepening as compared with BFS. Be concise and specific.

Problem 5 (10 points): Prove that if a heuristic is consistent, it must be admissible. Construct an example of an admissible heuristic that is not consistent. (Hint: you can draw a small graph of 3 nodes and write arbitrary cost and heuristic values so that the heuristic is admissible but not consistent).

Problem 6 (3 points): In a Constraint Satisfaction Problem (CSP) search, explain why it is a good heuristic to choose the variable that is most constrained but the value that is least constraining.

Problem 7 (10 points): Consider the following game tree, where the first move is made by the MAX player and the second move is made by the MIN player.

(a)    What is the best move for the MAX player using the minimax procedure?

(b)    Perform a left-to-right (left branch first, then right branch) alpha-beta pruning on the tree. That is, draw only the partsof the tree that are visited and don’t draw branches that are cut off (no need to show the alpha or beta values).

(c)    Do the same thing as in the previous question, but with a right-to-left ordering of the actions. Discuss why differentpruning occurs.

 

Problem 8 (10 points): Which of the following are admissible, given admissible heuristics h1, h2? Which of the following are consistent, given consistent heuristics h1, h2? Justify your answer.

a)    h(n) = min{h1(n),h2(n)}

b)    h(n) = wh1(n)+(1− w)h2(n), where 0 ≤ w ≤ 1

c)    h(n) = max{h1(n),h2(n)}

Which one of these three new heuristics (a, b or c) would you prefer to use for A*? Justify your answer.

Problem 9 (10 points): Simulated annealing is an extension of hill climbing, which uses randomness to avoid getting stuck in local maxima and plateaux.

a)    For what types of problems will hill climbing work better than simulated annealing? In other words, when is therandom part of simulated annealing not necessary?

b)    For what types of problems will randomly guessing the state work just as well as simulated annealing? In otherwords, when is the hill-climbing part of simulated annealing not necessary?

c)    Reasoning from your answers to parts (a) and (b) above, for what types of problems is simulated annealing a usefultechnique? In other terms, what assumptions about the shape of the value function are implicit in the design of simulated annealing?

d)    As defined in your textbook, simulated annealing returns the current state when the end of the annealing schedule isreached and if the annealing schedule is slow enough. Given that we know the value (measure of goodness) of each state we visit, is there anything smarter we could do?

(e)   Simulated annealing requires a very small amount of memory, just enough to store two states: the current state andthe proposed next state. Suppose we had enough memory to hold two million states. Propose a modification to simulated annealing that makes productive use of the additional memory. In particular, suggest something that will likely perform better than just running simulated annealing a million times consecutively with random restarts. [Note: There are multiple correct answers here.]

(f)     Gradient ascent search is prone to local optima just like hill climbing. Describe how you might adapt randomness insimulated annealing to gradient ascent search avoid trap of local maximum.