CMSC471/671 -- Artificial Intelligence
Final Exam -- Fall 1998
A philosopher, which is what I am supposed to be, is a sort of
intellectual yokel who gapes and stares at what sensible people
take for granted, a person who cannot get rid of the feeling
that the barest facts of everyday life are unbelievably odd.
-- Alan Watts, "Does It Matter?", 1968.
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.
Write recursive prolog predicates height/2 and weight/2, which compute
the "height" and "weight" of prolog lists.
height(+List, ?N) is true if List is a prolog list and it's "height" is the integer N.
weight(+List, ?N) is true if List is a prolog list and it's "weight" is the integer N.
where notions of the height and weight of a list are defined as follows:
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]).
Place a T or an F in the space before each statement to indicate
whether the statement is True or False.
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.
Briefly describe the advantages of the iterative deepening} search algorithm for trees over (a) depth first search and (b) breadth first search.
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.
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.
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.
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.