Artificial Intelligence: Final Exam May 1996 Take home exam Due Friday, May 10 10:00 AM Email: davise@cs.nyu.edu Hard copy: Slide under door of Warren Weaver, 429 Fax: 995-4121 Problem 1: (20 points) Consider the following sentences: i. Cats and dogs are animals. ii. Everyone in this room either owns a cat or owns a dog. iii. Anyone who owns an animal has a friend. iv. Everyone in this room has a friend. Let L be a first-order language containing the following predicates: c(X) --- X is a cat. d(X) --- X is a dog. a(X) --- X is an animal. o(X,Y) --- X owns Y. r(X) --- X is in the room. f(X,Y) --- X is a friend of Y.` A. State each of the sentences (i) -- (iv) in L. B. Show that (iv) can be proven from (i) -- (iii) using resolution. You should show the Skolemized form of all the clauses involved and each step of the resolution proof. You need not show the intermediate steps of Skolemization. Problem 2: (15 points) The K-CLIQUE problem is defined as follows: Given an undirected graph G and an integer K, find a set S of K vertices in G such that any pair of vertices in S is connected by an edge in G. For instance, if the vertices are people, and there is an arc connecting I and J if persons I and J are acquainted, the problem is that of forming a party of K people where everyone knows one another. We wish to find a search technique for solving K-CLIQUE that is guaranteed to find an answer if one exists. A. Describe a suitable search space. In particular, you should state (a) what are the states; (b) what are the operators; (c) what is the start state; (d) what are the goal states. B. What is the maximal branching factor in your state space? C. Is your state space systematic (tree-structured)? If not, can you modify it to be systematic? D. What search technique would you use to search the space? Give some simple easy upper bounds on the time and space requirement of this search technique. Problem 3: (10 points) Consider the following variant of chess: On a player's turn, he does not make a single move. Rather, he suggests two possible alternative moves, and his opponent may choose between those two. (If there is only one legal move, then that move is made.) A. How would the process of game tree evaluation be modified for this new game? B. There is an analogue of alpha-beta pruning that can be applied to this new game. Give an example of a game tree where pruning is possible. (You need not give the general rule.) Problem 4: (10 points) Let L be a first-order language where terms take integer values containing the following primitives: 3, 6 : Constants s(X) : Function -- the successor of X less(X,Y) : Predicate -- X is less than Y. Consider the following two rules i. forall(X,Y) less(X,Y) implies less(X,s(Y)). ii. forall(X,Y) less(s(X),Y) implies less(X,Y). Given the fact "less(s(3),6)" you wish to prove "less(3,s(6))" A. Show how this inference can be carried out using backward chaining. B. Show how this inference can be carried out using forward chaining. C. In a system of directed inference, where each rule can be tagged either to be used in forward chaining or to be used in backward chaining, how should the two rules (i) and (ii) be tagged? Why? Problem 5: (10 points) A. Construct a multi-layer, feed-forward neural network to carry out the following: There are four input cells. An input signal has an activation level of 1 or 0 at each input cell. We want the neural network to recognize signals with exactly two 1's and two 0's in input. B. Prove that no single perceptron can carry out this task. Problem 6: (Open-ended) (15 points) The logical structure of kinship relations can be complex. For instance: X is a step-brother of Y if X is male and one of X's parents is married to one of Y's parents, but X and Y do not have a common parent. X is a sister-in-law of Y if X is female and either (a) X is a sibling of the spouse of Y; (b) X is the spouse of a sibling of Y; (c) X is the spouse of a sibling of the spouse of Y. "ancestor" is the transitive closure of "parent" X is the kth cousin m times removed of Y if either some (k+1)st level ancestor of X is a (k+m+1)st level ancestor of Y or vice versa. Suppose you had the task of writing a program to learn the meaning of kinship terms in some unknown society. How would you set up the inductive bias for the program? Assume that the input is given in the form of a large family tree --- that is, a database showing all parenthood and all marriage relations, and the sex of each individual --- and a series of triples of the form < person, person, relation> (e.g. ). Problem 7: (20 points) Consider the following variation on the blocks world. Blocks are rectangular and may be placed either vertically or horizontally. Blocks oriented the same way can be stacked, and a vertical block can be placed on top of a horizontal block, but a horizontal block cannot be placed on a vertical block. A block can be rotated to switch its orientation, but only if it is clear and if it is on top of some other block (not if it is on the table). As usual, the table has infinite capacity, and a block at the top of one stack can be moved to the top of another stack, as long as the orientations don't conflict. A. How can this world be characterized in the STRIPS representation? B. Show how POP can solve the following problem: From the starting state shown below, attain the goal "on(B,A)". ___ | | | | |A| __________ | | |____B_____| |_| ________________________________ | | | | | Table | | |