CMSC 671

Artificial Intelligence -- Fall 2003

HOMEWORK FOUR
out 10/22/03 due 11/5/03

http://www.cs.umbc.edu/671/fall03/hw/hw4.html

1. Logic Warm-Up (10 points)

Assume that x and y have the domain of all people, and N has the domain of integers. Using the basic relations Child(x,y), Sibling(x,y), Female(x), Male(x), and Spouse(x,y):

(a) (7 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.)
(b) (3 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.

Note: For 2-place predicates P(x,y), you should use the semantics "x is a P of y," e.g., Child(x,y) means "x is a child of y."x

2. State Space Search (30 points)

Consider a simple puzzle with the following structure: There is a game board with three spaces in a row, and three tokens that are black on white side and white on the other. The moves you can make are:

Place a token, black side up, in the leftmost empty square
Remove the rightmost token on the board.
Flip all of the tokens on the board to the other side (i.e., black tokens become white, and white tokens become black).

For this problem, you should represent the states as an ordered triple:

(x1, x2, x3)

where x_i represents the contents of the ith square (counting from left to right) on the board, and can take on the values - [blank], B[black], or W [white]. The initial state is the empty board:

(-, -, -)

(a) (8 pts) How many possible states are there? How many states are reachable from the initial state using the actions above? (If you're not quite sure, try solving part (b) first; that should give you some insight into the answer to this question). Enumerate the reachable states systematically (i.e., using a reasonable lexical ordering of the states).

(b) (10 pts) Draw the state space graph for this problem, including only reachable states. Are there any bidirected edges in the graph (i.e., edges that permit a transition from state s1 to s2 and from s2 to s1)? What action(s) do these edges correspond to? Are there any unidirectional edges in the graph (i.e., edges that permit a transition from state s1 to s2 but not from s2 to s1)? What action(s) do these edges correspond to?

(c) (2 pts) Suppose that flipping costs two points, and adding and removing tokens each cost one point. Label the edges on the graph you drew for the previous question with the corresponding costs.

(d) (10 pts) Suppose that the goal state is WWW. Give the sequence of states that uniform-cost search would expand in the process of finding the optimal solution to this puzzle. What is the optimal solution (sequence of steps), and what is the total cost?

3. Constraint Satisfaction (30 points)

Consider the map coloring problem corresponding to the following map:

In this problem, there are three types of regions: cities (represented by variable names starting with "C"), land regions (variables starting with "L"), and water regions (variables starting with "W"). The domain of each variable is {R,Y,B,G} (corresponding to colors red, blue, yellow, and green). The unary constraints on the variables are:

All city variables must be colored green.
Water regions may not be colored red.
Land regions may not be colored blue.

The binary constraints are that no two adjacent regions (defined as regions that touch along any edge) may be assigned the same color.

(a) (4 pts) Draw the constraint graph for this problem.

(b) (2 pts) Reduce the domains of the variables to make the graph node-consistent; you may enumerate these reduced domains, or you may label the variables in the graph you drew for (a).

(c) (4 pts) Is the resulting CSP arc-consistent? If so, demonstrate that this is the case. If not, reduce the domains of the variables minimally so that the graph is arc-consistent.

(d) (5 pts) Give the variable orderings that would be selected by (i) the static Fail-First Principle, (ii) the degree heuristic (minimum cardinality ordering), and (iii) the cycle-cutset heuristic (clearly indicate the cutset you used). Assume that node and arc consistency have been achieved before these heuristics are applied. Break any ties using lexical (alphabetical) ordering of the variables.

(e) (8 pts) Show the instantiation steps that would be performed by (i) the dynamic Fail-First Principle with partial lookahead, and (b) the static Fail-First Principle with partial lookahead. (Note that the book does not mention partial lookahead, but the assigned papers do, and it is described in the class slides.) Which heuristic do you think performs best for this problem? Justify your answer.

4. Resolution Theorem Proving (30 points)

(Adapted from Problem #5 at http://www.classroomtools.com/logic1.htm.)

There are three people in a room: Alice, Bob, and Chris. Each person is either an angel (always tells the truth) or a devil (always lies). Alice says, "All of us are devils." Bob says, "Exactly one of us is an angel." The question is: which of Alice, Bob, and Chris are angels, and which are devils? (Try figuring this out by yourself, but if you get stuck or want to make sure you've gotten it right, you can follow this link for the solution.)

(a) (8 points) Encode this knowledge base in first-order logic. You should only use the predicate angel(x),. A devil is just someone who isn't an angel. Statements by an individual can be conditioned on whether (or not) the individual is an angel, since the statement will be true if and only if the speaker is an angel. For example, if Chris said "I am a devil," it could be encoded as:

angel(Chris) <-> ~angel(Chris)

(a contradiction!)

Hint: Bob's statement has many different correct encodings. Encoding it as two implications yields a simpler conversion to CNF. If Bob is an angel, what can you infer directly from his statement about Alice and Bob? (How many angels must there be?) If Bob is not an angel, and is lying, then what can you infer about the possible number of angels? How can you represent this information using only the angel predicate?

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

(c) (4 points) Which sentences in the resulting (CNF) KB are subsumed by other sentences in the KB? You should remove these subsumed sentences from the KB before completing question (d).

(d) (10 points) Use resolution refutation to prove that the solution you found (or were given...) is correct.

Comments: This problem is easier in some ways than the resolution refutation proof on the midterm, because none of the statements are quantified. In fact, you could easily convert this to a simple propositional representation. (How?) (No, answering that question isn't part of the homework!) However, it's very tricky to encode the statements just right, even given some suggested strategies, as I've done. This highlights the need for very careful KB encoding and verification in logic-based system development!