CMSC 671

Artificial Intelligence -- Fall 2001

HOMEWORK FIVE
out 10/30/01 due 11/15/01

http://www.cs.umbc.edu/671/fall01/hw/hw5.html

PART I. Logic Warm-Up (15 points)

(Russell & Norvig 7.6) Using the basic relations Child (x,y), Sibling (x,y), Female (x), Male(x), and Spouse (x,y):

(10 points) Write axioms describing the predicates GrandChild, Sister, Brother, Daughter, Son, Aunt, Uncle, and FirstCousin. (A first cousin is a parent's sibling's child.)
(5 points) A second cousin is a child of one's parent's first cousin; a third cousin is a grandchild of one's grandparent's first cousin; and so on. Write a definition of Nth-cousin (N, x, y), as a recursive expression in terms of the predicates defined above.

PART II. Resolution and Crime (50 points)

Dipsy has been murdered and Tinkey-Winkey, Laa-Laa, and Po are the only suspects. Chief detective Barney is on the case, and brings them in for questioning. Each one tells the truth except for the culprit, who may be lying. Here is what they told Barney.

Tinkey-Winkey says that she is innocent. She says that Laa-Laa and Dipsy were not friends, and Po and Dipsy were not friends.
Laa-Laa says that he is innocent, plus that he and Dipsy were friends.
Po says that she is innocent, and that Laa-Laa and Dipsy were not friends.

As an astute detective, Barney makes the following assumptions about the world:

Friends don't murder each other.
There is exactly one killer, and it is one of the Telletubbies.
Teletubbies are either good or bad.
When Teletubbies go bad, they may lie.
Good Teletubbies always tell the truth and only say things they know to be true..

Your task is to do the following:

(b) Write a set of FOL sentences representing the general knowledge assumptions you've made. If necessary for (e) below, include here any other general knowledge sentences that you need.

(d) State the goal to be solved as an FOL sentence and solve the crime using a resolution refutation proof, showing your result as a proof tree that derives False.

(e) Po later tells you that she was a friend of Dipsy. Is the knowledge base containing all of the sentences satisfiable? If so, give an interpretation that makes it true. If not, prove unsatisfiability using resolution.

Part III. STRIPS Planning Operators (35 points)

(Russell & Norvig 11.7 (a) - (c)) For this problem, you will need to refer to the description of the Shakey world on pp. 359-362 of the textbook.

(a) Describe Shakey's six actions (Go, Push, Climb, Down, TurnOn, and TurnOff) in situation calculus notation. These action descriptions should characterize how the situation changes as a result of Shakey's actions, in terms of the predicates in the Shakey world. Notationally, each action description should look something like this:

Forall x,y,s Condition (Shakey, y, Result(a,s)) <=> Condition (Shakey, x, s) ^ a = Action(x,y)

Obviously your action descriptions will (a) make sense and (b) be more complicated than this.

(b) Translate them into the STRIPS language. These operators should look something like this:

Op(Action: A(x,y), Precond: Condition (Shakey, x), Effect: Condition (Shakey, y))