cis32 homework #1

sklar/spring-2006

• The homework is due AT THE BEGINNING OF CLASS on Wednesday March 8.

• Send the homework to: sklar@sci.brooklyn.cuny.edu as PLAIN TEXT or PDF.
Please DO NOT SEND WORD DOCUMENTS!!!

• This homework is worth 6 points in total. The distribution of points is indicated below.

and the questions are...

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 BREADTH-FIRST SEARCH to find a solution to this 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.

3. (2 points)
Use DEPTH-LIMITED SEARCH to find a solution to the problem. As above, draw the tree of nodes searched, indicating nodes by drawing states and next node searched using arrows.
What is a good DEPTH LIMIT for this problem?