Assignment 6 – CSE 473 Introduction to AI – Fall 2003

Each question on this assignment is worth 10 points, for a total of 40 points. I estimate that it will take between 1 hour and 2 hours to complete this assignment. If you find it is taking you much longer than that, feel free to ask for help from the TA, the professor, and/or other students in the class. All questions are due on Friday Nov 14^th. The reading summaries specified separately on the Calendar page that was handed out today and is posted on the web site under both “Assignments” and “Lectures”:

http://www.cs.washington.edu/education/courses/cse473/03au/

1. Consider the Hungry Monkey probabilistic planning domain we discussed in class on Nov 7^th and 10^th. Now suppose that each action has an associated cost to perform: A jump costs 0.25 units (measured in bananas). A shake costs 0.10 units.

Where n is a max node and a is an action, define child(n,a) as the chance node reached by performing a in s. Then ExpectiMax with action costs becomes:

Write down the complete ExpectiMax search tree for plans where the Monkey performs exactly two actions. (See the Powerpoint slides from Nov 10 for such a tree without action costs.) State what the Monkey’s optimal 2-step plan should be.

shake: cost 0.10

if (~ontable)

1/6 -> +1 banana

5/6 -> no change

if (ontable)

2/3 -> +1 banana

1/3 -> no change

jump: cost 0.25

if (~ontable)

2/3 -> ontable

1/3 -> ~ontable

if (ontable)

ontable

2. Suppose you believe that P(A)=0.4 and P(B)=0.3. What is the range of possible consistent values that you assign to P(A and B)? What is the range of consistent values for P(A or B)?

3. R&N problem 13.8.

4. R&N problem 13.18. Your answer need not be exhaustive – half a page is fine. The purpose of this problem is to get you thinking about how you might build your spam filter later in the course.