HW1 : Search

Submission Guidelines

DUE Sunday March 11th 11:59 PM

Send the homework to: chipp@sci.brooklyn.cuny.edu as PLAIN TEXT or PDF.

Please DO NOT SEND WORD DOCUMENTS!!!

(Total Points 6)

Questions

1. (2 points)
   The female solitary wasp, Sphex, layes her eggs in a cricket that she has paralyzed and brought to her burrow nest. The wasp grubs hatch and then feed on this cricket... The female wasp exhibits the following behavior:

...the wasp's routine is to bring the paralyzed cricket to the burrow, leave it on the threshold, go inside to see that all is well, emerge, and then drag the cricket in. If the cricket is moved a few inches away while the wasp is inside making her preliminary inspection, the wasp, on emerging from the burrow, will bring the cricket back to the threshold, but not inside, and will then repeat the preparatory procedure of entering the burrow to see that everything is all right. If again the cricket is removed a few inches while the wasp is inside, once again she will move the cricket to the threhold and reenter the borrow for a final check...

Source: Nils J. Nilsson (1998), "Artificial Intelligence: A New Synthesis", Morgan Kaufmann Publishers, Inc. p82.

Pretend that you are going to program a robot to exhibit the same behavior as the wasp described above. Invent states, actions and a production system that describes the behavior.

2. (2 points)
   Suppose that you have a driveway that looks like the figure below, where the colored blocks are cars and the grey blocks are empty parking spaces. The red car is at the end of the driveway and can be moved out into the street, but the other cars are all blocked, first by the red car and then by the others in succession. There is a fence along the edge of the driveway preventing sideways movement from the driveway to any of the grey parking spots on either side.
   

		R
		G
		Y
		B


You need to program a robot chauffeur to re-order the cars so that they are in alphabetical order, i.e., yellow at the far end of the driveway (where blue is now), followed by red, then green, then blue nearest the street. Your robot can pull the car nearest the street into an available parking space by backing it out and pulling it into the column of spaces on either the left or right side of the driveway.
Use DEPTH-LIMITED SEARCH to find a solution to the problem, drawing the tree of nodes searched, where each node is a state diagram in the format of the figure above. Use arrows to indicate the order in which the states are searched.

What is a good DEPTH LIMIT for this problem?
3. (2 points)
   In the Four-Queens puzzle, we try to place four queens on a 4 x 4 chess board so that none can capture any other. (That is, only one queen can be on any row, column, or diagonal of the array.) Suppose we try to solve this puzzle using the following problem space: The start node is labeled by and empty 4 x 4 array; the successor function creates new 4 x 4 arrays containing one additional legal placement of a queen anywhere in the array; the goal test is satisfied if and only if there are four queens in the array (legally positioned).
   
   
   1. Invent an admissible heuristic function for this problem based on the number of queen placements remaining to acheive the goal. (Note that all goal nodes are precisely four steps from the start node!)
      
      
   2. Use your heuristic function in an A* search to a goal node. Draw the search tree consisting of all 4 x 4 arrays produced by the search and label each array by its value of g h. (Note that symmetry considerations mean we have to generate only three successors of the start node)