CS121

Introduction to Artificial Intelligence

Winter 2004

 

 

 

Homework #2

(Search Problems)

Out: 1/21/03 — Due: 1/28/03

 

 

How to complete this HW: First copy this file; then insert your answers in the file immediately below each question; finally email the completed file to [email protected] before 1/28 at midnight.

When you e-mail your homework, your subject line should be your leland username and then the homework you are submitting (e.g. "mykel: hw1"). If you must resubmit, make this clear in the subject line (e.g. "mykel: hw1 RESUBMIT").

 

Note on Honor Code: You must NOT look at previously published solutions of any of these problems in preparing your answers. You may discuss these problems with other students in the class (in fact, you are encouraged to do so) and/or look into other documents (books, web sites), with the exception of published solutions, without taking any written or electronic notes. If you have discussed any of the problems with other students, indicate their name(s) here:

………………………………………………………………………………………………

Any intentional transgression of these rules will be considered an honor code violation.

 

General information: In the following, whenever an explanation is required (“Why?”), there will not be full-credit without an explanation. Keep explanations short and to the point. Excessive verbosity will be penalized. If you have any doubt on how to interpret a question, either tell us in advance, so that we can help you understand the question, or tell us how you understand it in your returned solution.

 

Grading:

 

Problem#

Max. grade

Your grade

I

5

 

II

5

 

III

5

 

IV

5

 

V

5

 

VI

5

 

Total

10

 

 

I. (5 points) Consider a finite search tree of uniform branching factor 6, in which all leaves lie at depth 10. There is a single goal node at depth 7. Recall that depth of the root (start node) is 0, the depth of its immediate successors is 1, etc…

 

In the worst-case, how many nodes are generated by:

1.      Breadth-first search.

2.      Depth-first search with not cutoff.

3.      Depth-first search with cutoff 8.

4.      Iterative-deepening search.

In each case, give the solution for the two search algorithms presented in class: in one, the goal test is applied to a node when this node is generated; in the second algorithm, the goal test is applied when the node is removed from the fringe. Explain very briefly each answer.

 

II. (5 points) Consider the robot navigation problem shown in class and illustrated in the figure below:

 

The navigation problem is as follows: The robot is a point moving on a planar regular grid. We assume that the robot moves between grid nodes, so that the state space is the set of grid nodes. There are static obstacles and the robot is only allowed to be at grid nodes not contained in obstacles. The successors of any grid node (a state) are all the neighbors of this node (up to 8) that are not contained in obstacles. The cost of a horizontal/vertical step is 1. The cost of a diagonal step is sqrt(2). The robot must go from a start grid node to a goal grid node. Each grid node is defined by its two coordinates (x,y) in a coordinate system.

 

Give 4 heuristic functions h1, h2, h3, and h4 that are, each, both admissible and consistent. Rank them from the least to the most informed. Explain briefly your answers.

 

III. (5 points) Prove each of the following statement:

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

2.      Breadth-first search is a special case of best-first search.

3.      Depth-first search is a special case of best-first search.

4.      Uniform-cost search is a special case of A* search.

Briefly explain your answers. In particular, for each of the two statements 2 and 3, what is the evaluation function used by the equivalent best-first search? For statement 4, what is the heuristic function used by the equivalent A* search?

 

IV. (5 points) Invent a heuristic function for the 8-puzzle that sometimes overestimates the cost to reach the goal, and show how it can lead to a suboptimal solution on a particular problem.

 

V. (5 points) Prove that if a heuristic function h never overestimates the cost to reach the goal by more than a positive constant c, that is:

for every node N:    0 £ h(N) £ h*(N)+c,

where h*(N) is the cost of the minimum-cost path from N to a goal node, then A* search using h returns a solution whose cost does not exceed that of the minimum-cost path by more than c. 

 

VI. (5 points) Perform A* on the search tree shown below with edge costs shown near each edge (in red) and the goal node shown shaded.  Label the nodes (inside the circles depicting the nodes) in the order that they are expanded by the algorithm (1 for the start node, 2 for the second node, etc.). Also fill in the f-value (the value of the evaluation function f = g + h) of each node that is put into the priority queue (fringe), and leave the f-values for all other nodes blank.