CMSC 471

Artificial Intelligence -- Fall 2011

out Tues 10/18/11; due Tues 11/1/11

NOTE: The material covered on this homework assignment will be on the midterm on October 27. I have kept the due date for the homework as November 1, but you are strongly urged to complete the homework assignment as part of your preparation for the midterm (even if you don't neatly type it for submission). You can expect to see very similar problems on the midterm, so completing this assignment is one of the best ways that you can study for the midterm.  

You are encouraged to work on this homework assignment in groups of up to three students. If you work in a group, you only need to turn in one shared solution. All students in the group will receive the same grade on the assignment. If you choose to work in a group, you must actually produce group solutions, not have each member work independently on one part of the assignment, then submit the collection of independent solutions. To acknowledge that you have worked as intended, you must include the following statement at the top of the submitted assignment:

"We, <students' names>, worked equally as a group on this assignment, and each of us fully understands and acknowledges the group solutions that we are submitting. We understand that we will receive a common grade for this assignment."
Please be sure to include all group members' names on the assignment!

I. Knowledge-Based Agents (15 points)

(Adapted from Russell & Norvig 2nd edition, Exercise 7.1.) Describe the Wumpus world according to the properties of task environments listed in Chapter 2 (i.e., the seven characteristics described in Section 2.3.2). Your answer should include a brief (single sentence or phrase) justification for each of the seven answers.. Note: Use the description of the Wumpus world from the book (not the online variations that we saw in class).

How would your answer change for a Wumpus variant in which the wumpus could move according to fixed rules (i.e., rules that are known to the agent)? How would your answer change for a world in which the wumpus moved using an unknown mechanism?

II. Logic (55 points)

(a) Russell & Norvig Exercise 7.7, page 281 (15 pts).

(b) Russell & Norvig Exercise 7.8 (b,c), page 281 (15 pts).

(c) Russell & Norvig Exercise 7.22 (a), page 284 (10 pts).

(d) Russell & Norvig Exercise 8.28 (c,f,h,k.l), page 321 (15 pts).

III. Resolution Theorem Proving (30 points)

(a) (8 points) Represent the following knowledge base in first-order logic.  Use the predicates

where arguments x have the domain of all people, and arguments t have the domain of all tests.
  1. Everyone who is smart, studies, and attends class will be prepared.
  2. Everyone who is prepared will pass a test if it is fair.
  3.  A student passes a test if and only if they don't fail it.
  4.  Every UMBC student is smart.
  5.  If a test isn't fair, everyone will fail the test.
  6.  Aidan is a UMBC student.
  7.  Sandy passed the 471 exam.
  8.  Aidan attends class.

(b) (8 points) Convert the KB to conjunctive normal form.

(c) (2 points) We wish to prove that

study(Aidan) -> pass(Aidan, 471-exam)

Express the negation of this goal in conjunctive normal form.

(c) (12 points) Add the negated goal to the KB, and use resolution refutation to prove that it is true. You may show your proof as a series of sentences to be added to the KB or as a proof tree.  In either case, you must clearly show which sentences are resolved to produce each new sentence, and what the unifier is for each resolution step.