CSE 473: Introduction to Artificial Intelligence Autumn 2007

Hw Assignment 3 (Exercise): Due Friday, October 12 in class: 25 points

• (5 pts) Problem 4.7
• Show how the A* search algorithm works with the following evaluation functions. Do the same search problem we did in class (slide 21 of Informed Search I). At each node of the search tree, show the state of the puzzle and give the values for f, g, and h in that order. Put a box around the f value so it stands out (or make it bold if you are typing).
  • (5 pts) greedy search where g=0 and h=h1 (page 106)
  • (5 pts) A* search where g=depth and h=h2 (page 106)
• (5 pts) Try the applet at http://www.cs.rochester.edu/u/kautz/Mazes/search/applet.html . For at least 2 different problems (use create to start a new problem) try each of the 5 search techniques and record the values it shows for 1.(length of) solution and 2. (number of) nodes. What does this show you about the different techniques?
• (5 pts) A camera is looking at a 3D object and produces an image of that object on a plane called the image plane. We can see the image plane and can see the object. We will represent the image plane by a 2D array of integers whose values are 1 for array elements on the outline of the object and 0 otherwise. This is called a binary image.

  We would like to determine where the camera is located and the direction in which it is pointing. This is represented by a set of camera parameters. There are six parameters: t1, t2, t3, r1, r2, and r3. The ti's are translation parameters and the ri's are rotation parameters. We know approximately where the camera is and are given an initial state (t10, t20, t30, r10, r20, r30). We are also given a black box function called project(t1,t2,t3,r1,r2,r3) that when given the 6 parameters, projects the object onto the image plane from that view point. It essentially produces another array showing where the outline of the object would be from the given view point.

  Suppose the actual image plane array with the real outline of the object is in array A[*,*] and the project method writes its outline from the current set of parameters in another array B[*,*]. The goal of the problem is to find the set of parameters for which the 2 outlines line up perfectly. The start state is (t10,t20,t30,r10,r20,r30). The parameters of the goal state are the unknowns to be found.

  Define a heuristic function h that estimates how far the current state (set of parameters) is from the goal. Use the two arrays A and B to compute your answer. A is what should happen at the goal state. B is what is happening at the current state. Note that this problem took a lot of space to explain, but your function just has to decide how close the A array is to the B array, and we are only interested in the 1-elements.

  Here is a picture of the problem setup.