Please put your name and SSN on this exam and your name on all of the exam booklets you use. Hand in this exam and all of the exam booklets you use. You are free to use any books or notes you want. The points add up to 120 and you have 120 minutes to finish the exam. Good luck.

1. Prolog I [20]

Write recursive prolog predicates height/2 and weight/2, which compute

the "height" and "weight" of prolog lists.

where notions of the height and weight of a list are defined as follows:

• the height of a term, which is not a list, is 0.
• the height of a list is one plus the maximum height of any of the elements of the list.
• the weight of a term, which is not a list, is 1.
• the weight of the empty list is 0.
• the weight of a list is the sum of the weights of its elements.

1. Prolog II [15]

Consider two possible definitions of the member predicate:

Version one:

member1(X,[X|Tail]).

member1(X,[Y|Tail]) :- member1(X,Tail).

Version two:

member2(X,[X|Tail]) :- !.

member2(X,[Y|Tail]) :- member2(X,Tail).

Both of these definitions are in fact useful. Describe in high level terms (i) how they differ; (ii) why one would chose to use one definition rather than the other and (iii) show all possible solutions to the two goals member1(X,[1,2,3]). and member2(X,[1,2,3]).

2. True/False [15]

1. Algorithm A* is simply and instance of Algorithm A with an additive evaluation function of the form f = g + h.
2. Algorithm A will perform a breadth-first search if H(n) = G(n).
3. Algorithm A will perform a depth-first search if the heuristic function H(n) = -G(n).
4. Alpha-Beta Search is Minimax search in which alpha > beta.
5. Given a poor plausible move generator (i.e. one that generates all the legal moves properly but does a bad job of ordering them from best to worst), the alpha-beta algorithm can prevent spectacular moves such as (in chess) a queen sacrifice leading to a checkmate.
6. First-order predicate calculus allows quantified variables to refer to objects in the domain of discourse, and not to predicates or functions.
7. Every sound inference rule is complete and every complete inference rule is sound.
8. Two expressions in the propositional calculus are equivalent if they have the same value under all truth value assignments.
9. If x is a variable and s is a propositional calculus sentence, then $ x s is a propositional calculus sentence.
10. A most general unifier is a unifier that is not restricted to first-order predicate calculus.
11. Strips is a sound planner but not a complete planner.
12. One way a partial order planner can fail is to find a complete partial-order plan that satisfies the constraints but for which no linear order can be computed.
13. The ID3 decision tree induction algorithm is guaranteed to find the optimal decision tree consistent with a given training set.
14. One drawback of the ID3 decision tree induction algorithm is that it can not be used if the training data contains values which are drawn from finite sets, i.e. real numbers are not allowed.

1. Backward vs. Forward Chaining [10]

General methods can be given for both backward chaining and forward chaining which are both sound and complete. Give at least three different reasons why one might prefer to use a forward chaining algorithm to a backward chaining one.

2. Iterative Deepening [10]

Briefly describe the advantages of the iterative deepening} search algorithm for trees over (a) depth first search and (b) breadth first search.

3. Unification [10]

For each of the following pairs of literals, state whether they unify. If they do unify, state the binding of each of the variables. If they do not unify, give the reason.

1. p(f(Z), Y, g(Y)) p(f(X), c, g(X))
2. p(f(X, X), a) p(f(Y, f(Y, a)), a)
3. p(a, X, c, X) p(b, c, Z, c)
4. p(f(Y), Y, g(a, Z), b) p(f(b), W, g(X, X), W)
5. p(X, Y) p(a, b, c)

1. STRIPS operators and the situation calculus [15]

Translate the following situation calculus axioms into one STRIPS operator:

" s, x, p Edible (x) Ù Holding (p, x, s) Þ

Inside (x, p, Result (Eat (p, x), s))

" s, x, p Edible (x) Ù Holding (p, x, s) Þ

Ø Holding (p, x, Result (Eat (p, x), s))

" s, x, y, p Holding (p, y, s) Ù Ø (x=y) Þ

Holding (p, y, Result (Eat (p, x), s))

" s, x, y, p Inside (y, p, s) Þ

Inside (y, p, Result (Eat (p, x), s))

" s, x, y, p Ø Inside (y, p, s) Ø (x=y) Þ

Ø Inside (y, p, Result (Eat (p, x), s))

making reasonable assumptions about what the predicates edible, holding and eat mean.

2. Partial-Order Planning I [5]

List all possible totally-ordered step sequence plans that are represented by the following

partially-ordered plan containing six steps for putting your shoes and socks on. Indicate a step using its number. You are not allowed to touch or look at your feet in working out the solution to this problem.

---

---

 

3. Partial-Order Planning II [20]

Consider the following partially-ordered plan. Solid arcs are causal links; the letter labeling the arc is the literal that is added by the source step and a precondition of the destination step. Dotted arcs are temporal ordering constraint links. Literals at the upper-left corner of a step are the preconditions of the step; literals at the bottom-right corner of a step are the effects of the step.

Positive effects indicate additions and negated effects denote deletions. As usual, for each causal link, there is an implicit temporal constraint link between the same two nodes that is not drawn to keep the figure less cluttered.

1. [4] List all the linearizations (i.e., total orderings) implicit in the above partially ordered plan.

 

 

2. [4] Are all of the preconditions of the Finish step guaranteed to be achieved in the above partial-order plan? Explain briefly why or why not.

 

 

3. [4] Which step(s) threaten the causal link connecting step B to step C?

 

 

4. [4] Modify the partial-order plan in the above figure to remove the threat(s) to the causal link connecting B to C. Do not delete anything already in the figure. Mark your addition(s) with "(d)".
5. [4] Modify the partial-order plan in the above figure by adding a new step to fix a problem in the plan. Add whatever nodes and/or arcs that are necessary. Do not delete anything already in the figure. Mark your change(s) with "(e)" on the figure.