微信客服：xiaoxionga100
微信客服：ITCS521
程序代写案例-RMATICS 2D
时间：2021-04-10
UNIVERSITY OF EDINBURGH
COLLEGE OF SCIENCE AND ENGINEERING
SCHOOL OF INFORMATICS
INFORMATICS 2D: REASONING AND AGENTS
Friday 15 th August 2014
14:30 to 16:30
INSTRUCTIONS TO CANDIDATES
1. Answer Parts A, B and C.
2. The multiple choice questions in Part A are worth 50% in total and
are each worth the same amount. Mark one answer only for each
question - multiple answers will score 0. Marks will not be deducted
for incorrect multiple choice exam answers.
3. Parts B and C are each worth 25%. Answer ONE question from Part
B and ONE question from Part C.
4. Use the special mark sheet for Part A. Answer Parts B and C each in
a separate script book.
CALCULATORS ARE PERMITTED.
Convener: J. Bradfield
External Examiner: C. Johnson
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
Part A
ANSWER ALL QUESTIONS IN PART A. Use the special mark sheet.
1. Which one of the following best describes the statement entailment for first-order
logic is semidecidable?
(a) Algorithms exist that say yes to every entailed sentence, but no algorithm
exists that also says no to every nonentailed sentence.
(b) Algorithms exist that say yes to some entailed sentence, but no algorithm
exists that also says no to every nonentailed sentence.
(c) Algorithms exist that say no to every nonentailed sentence, but no algorithm
exists that also says yes to every entailed sentence.
(d) No algorithm exists that says yes to every entailed sentence, but algorithms
exist that say no to every nonentailed sentence.
(e) Algorithms exist that say yes to every entailed sentence and no to every
nonentailed sentence.
2. In the context of informed search, what is meant by a relaxed problem?
(a) It is one with fewer actions.
(b) It is one with fewer restrictions on the states.
(c) It is one with fewer restrictions on the actions.
(d) It is one with fewer restrictions on the heuristic.
(e) It is one with fewer restrictions on the environment.
3. Which of the following, if any, is the most general unifier of f(x)+f(y) < g(x)×x
and f(x) + f(x) < g(g(y))× x, where x and y are variables?
(a) Unification fails due to a conflict.
(b) {y/g(y)}
(c) {y/x, x/g(x)}
(d) Unification fails due an occurs-check violation.
(e) {x/g(x)}
Page 1 of 15
4. In the context of the situation calculus, fluents are functions and predicates that
can vary from one situation to the next. Which one of the following statements
best describes the form taken by a successor-state axiom?
(a) Action is possible ⇒
(Fluent was true before and action left it alone
∨ Action’s effect made it true)
(b) Fluent is true in result state ⇔
(Fluent was true before and action left it alone
∨ Action’s effect made it true)
(c) (Fluent is true in result state ⇔
(Fluent was true before and action left it alone
∧ Action’s effect made it true))
⇒ Action is possible
(d) Action is possible ⇒
(Fluent is true in result state ⇔ Action’s effect made it true)
(e) Action is possible ⇒
(Fluent is true in result state ⇔
(Fluent was true before and action left it alone
∨ Action’s effect made it true))
5. In a vocabulary with 4 propositional symbols A, B, C and D how many models
are there for the sentence A⇒ B?
(a) 3
(b) 6
(c) 1
(d) 2
(e) 12
Page 2 of 15
6. Consider the following lookahead tree for a two-person game, which is searched
depth first, left-to-right. Each node is named by a letter. Nodes with shape ∆ are
where Max is due to play; nodes with shape ∇ are where Min is due to play. The
numbers below the leaves of the tree are the results of the evaluation function
applied to that leaf.
Which nodes would an α/β search not need to visit?
(a) I and J .
(b) L and M .
(c) M .
(d) D, K, L and M .
(e) I, J , K, L and M .
7. Which of the following is not part of the DPLL algorithm, as given in Russell &
Norvig and the lectures?
(a) A clause is true if one of its literals is true.
(b) A pure symbol can be set to false.
(c) A literal in a unit clause can be set to true.
(d) A sentence is true if any of its clauses is true.
(e) A pure symbol can be set to true.
8. Which of the following sets of clauses – where a and b are new Skolem constants,
and F is a new Skolem function – is the clausal normal form (CNF) of the formula
∃x.[P (x)↔ ∀y.Q(x, y)]?
(a) {¬P (x) ∨Q(x, y), P (x) ∨ ¬Q(x, y)}
(b) {¬P (x) ∨Q(x, F (x)), P (x) ∨ ¬Q(x, y), }
(c) {¬P (a) ∨Q(a, y), P (a) ∨ ¬Q(a, b)}
(d) {¬P (x) ∨Q(x, a), P (x) ∨ ¬Q(x, y)}
(e) {¬P (a) ∨Q(a, y), P (a) ∨ ¬Q(a, F (a))}
Page 3 of 15
9. Consider a constraint satisfaction problem (CSP) with variablesA,B,C,D,E, F,G
that can take values from the domain {1, 2, 3} and the following constraints only:
• A 6= B,A 6= F
• B 6= C,B 6= F
• C 6= D,C 6= F
• D 6= E,D 6= F
• E 6= F
Assuming that the following partial assignment with A = 1 and B = 3 has been
generated, and that the next variable to be chosen is C, what would the least
constraining value heuristic do next?
(a) Assign C = 1.
(b) Assign C = 2.
(c) Assign C = {1, 2}.
(d) Delete C from the problem.
(e) Assign C = 3.
10. Which of the following statements is false of Generalised Modus Ponens (GMP)?
(a) GMP is sound.
(b) GMP is complete when combined with factoring.
(c) GMP can be applied both forwards and backwards.
(d) GMP uses unification.
(e) GMP may not terminate on non-theorems.
Page 4 of 15
11. “Contingency planning that includes sensing actions and a description of different
paths for different circumstances” is an accurate description for which of the
following planning techniques?
(a) Replanning and execution monitoring
(b) Sensorless/Conformant planning
(c) Hierarchical task network planning
(d) Continuous planning
(e) Conditional planning
12. Assume you have to add an action D with postconditions ¬p and ¬q in a plan
with existing causal links A
p→ B and B q→ C. Which of the following total
orderings resolves all conflicts that might arise from addition of D?
(a) A ≺ B ≺ D ≺ C
(b) A ≺ C ≺ B ≺ D
(c) A ≺ C ≺ D ≺ B
(d) D ≺ A ≺ B ≺ C
(e) A ≺ D ≺ B ≺ C
13. In how many ways is the action schema
Action(Fly(p, from, to),
Precond:At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
Effect:¬At(p, from) ∧ At(p, to))
applicable in the following state:
At(P1, SFO) ∧ At(P2,Heathrow)∧
Airport(CDG) ∧ Airport(Heathrow) ∧ Airport(SFO)∧
Plane(P1) ∧ Plane(P2)
(a) 1
(b) 2
(c) 4
(d) 6
(e) 9
Page 5 of 15
14. You are given four action descriptions with conditional effects:
Action(A,Precond:{P,X},Effect:{(when Z : ¬X)})
Action(B,Precond:{¬Y },Effect:{(when P : Z,X)})
Action(C,Precond:{Z},Effect:{(when P : ¬Y ), X})
Action(D,Precond:{¬X},Effect:{(when P : Z,X)})
What state would result from executing the action sequence [D,C,B,A] in the
state {P, Y }?
(a) The plan isn’t executable because the preconditions for action B aren’t met.
(b) {P,X,Z}
(c) {P,Z}
(d) {P,¬X,¬Y, Z}
(e) {X, Y, Z}
15. Which of the following statements about Hierarchical Task Network (HTN) Plan-
ning is correct?
(a) All refinements of high-level actions (HLAs) are a sequence of only primitive
actions.
(b) A refinement of an HLA always has the same preconditions as the HLA.
(c) If no states in the pessimistic description of the reachable states of a high-
level plan (HLP) satisfy the goal, then that HLP is guaranteed to fail.
(d) If A is in the Effect of one refinement of HLA h, and ¬A is in another
refinement of h, then +˜A is in Reach+(s, h).
(e) An HLA that achieves a goal has the downward refinement property only if
all its implementations also achieve that goal.
16. The following table specifies a joint probability distribution for three Boolean
random variables A, B , C :
a ¬a
b ¬b b ¬b
c 0.28 0.03 0.08 0.04
¬c 0.09 0.23 0.11 0.14
Which of the following is the correct value for P (b ∨ ¬a)?
(a) 0.19
(b) 0.74
(c) 0.63
(d) 0.37
(e) 0.52
Page 6 of 15
17. Suppose that a direct sampling method produces the event [false, true, true, true]
for the Boolean variables [Cloudy , Sprinker ,Rain,WetGrass ] in the Bayesian net-
work shown below in exactly 4 out of 100 trials. Then what is the size of the
difference between the true probability P (¬cloudy , sprinkler , rain,wetgrass) and
its estimated probability from direct sampling?
(a) 0.095
(b) 0.04
(c) 0.0495
(d) 0.0895
(e) 0.0095
Page 7 of 15
18. Assume we generate 100 samples in a Bayes net with three variables A, B, and
C to estimate the distribution P(C|¬a,¬b) and obtain the following results:
b ¬b
a ¬a a ¬a
c 15 5 10 5
¬c 20 10 20 15
What is the correct estimated distribution 〈P (c|¬a,¬b), P (¬c|¬a,¬b)〉 that we
would obtain by applying the rejection sampling method to this problem?
(a) 〈 1
20
, 3
20
〉
(b) 〈 7
20
, 13
20
〉
(c) 〈1
4
, 3
4
〉
(d) 〈1
3
, 2
3
〉
(e) 〈1
6
, 5
6
〉
19. The process of computing P(Xt+k|e1:t) for k > 0 in a temporal probabilistic
model with state variables X and evidence variables e is called
(a) prediction
(b) smoothing
(c) abstraction
(d) monitoring
(e) filtering
20. Let strict preference be denoted by the relation symbol , indifference by ∼,
weak preference by %, and lotteries be written as [p1, O1; . . . ; pn, On], where each
pi is the probability associated with outcome Oi. Which of the following is not
an axiom of utility theory?
(a) (A B) ∨ (B A) ∨ (A ∼ B)
(b) (A B) ∧ (B C)⇒ (A C)
(c) A B C ⇒ ∃p [p,A; 1− p, C] ∼ B
(d) A ∼ B ⇒ [p,A; 1− p, C] [p,B; 1− p, C]
(e) A B ⇒ (p ≥ q ⇔ [p,A; 1− p,B] % [q, A; 1− q, B])
Page 8 of 15
Part B
ANSWER ONE QUESTION FROM PART B
1. (a) Define clausal form for propositional logic formulae.
[2%]
(b) State and describe the three improvements that the Davis-Putnam-Logemann-
Loveland (DPLL) algorithm has over truth-table enumeration. Illustrate
each of these improvements with an appropriate example.
[12%]
(c) Apply the DPLL procedure to the following set of clauses:
{S,Q}, {¬Q,R}, {¬Q,S}, {¬R, S,Q}, {R, S}, {¬R,¬S}
Is the set of clauses satisfiable? Show all the steps of the procedure.
[5%]
(d) Find a refutation of the clauses (1)–(4) below using binary resolution and
factoring. Use clause (4) as one of your starting clauses and indicate both
the selected literals and clauses used at each step. Note that X is a variable,
and a and b are constants.
¬Q(b) ∨ P (1)
P ∨Q(X) (2)
¬Q(X) ∨ ¬P (3)
¬P ∨Q(a) (4)
[6%]
Page 9 of 15
2. Consider the following CSP problem:
You are arranging a series of interviews for the film stars attending the Edinburgh
Film Festival. There are several time slots, each represented by a variable: Early
Morning (EM), Late Morning (LM), Early Afternoon (EA), and Late Afternoon
(LA). The domains for the variables, i.e. the possible interviewees for each time
slot, are as follows (with letters used to abbreviate the various choices):
EM : Scarlett Johansson (s), Jennifer Lawrence (l)
LM : Angelina Jolie (a), Tom Hanks (h), Tom Cruise (t)
EA: Robert Downey Jr (d), Walter White (w), Vin Diesel (v)
LA: Brad Pitt (p), George Clooney (c), Liam Neeson (n)
However, to ensure that the stars, fans and film studios are happy, the arrange-
ment must satisfy the following constraints:
• As she wakes up at 5am everyday to meditate, the early morning slot must
be for Scarlett Johansson, or else the early afternoon slot must be Robert
Downey Jr or Vin Diesel, who go to bed late.
• If you decide to arrange an interview for Jennifer Lawrence then you must
also schedule one for Tom Cruise, to ensure he gets some of the limelight.
• You must ensure that at least one of the following interviews happens to
give the Festival plenty of media attention: George Clooney, Brad Pitt, or
Tom Hanks.
(a) Give the constraint graph for the variables EM , LM , EA, and LA.
[3%]
(b) Explain what the most constrained variable heuristic is.
[4%]
(c) Explain what the most constraining variable heuristic is.
[4%]
(d) What is meant by constraint propagation? Why is it an effective procedure?
[3%]
(e) In the given CSP, assume that your first decision is to schedule Jennifer
Lawrence for the early morning slot, i.e. EM=l, give the domain for each
of the variables after forward-checking. Explain your answer.
[3%]
Page 10 of 15
(f) In the given CSP, assuming once more that you start with EM=l, give the
domain for each of the variables after forward-checking and arc-consistency
have been enforced. Explain your answer.
[4%]
(g) Explain how a single ternary arithmetic constraint such as A + B = C can
be turned into binary constraints.
[4%]
Page 11 of 15
Part C
ANSWER ONE QUESTION FROM PART C
1. Planning and Decision Making
You want to catch a train tomorrow. You know that there are two possible
departure times: 8am or 11am. The actions available to you are:
• To Write down the departure times by 7pm tonight, so you remember what
they are.
• To GoEarly to the station (i.e., between 7:45am and 8am), in which case
you catch the train but may have to wait longer than 1 hour.
• To GoLate to the station (i.e., between 10:45 and 11am), in which case you
might miss the train.
If you don’t Write down the departure times, then there is a chance that an
external force—let’s call it nature—will make you forget one of the departure
times by tomorrow morning.
Assume the following formulae for describing this situation:
• Tonight means that the current time is before 7pm this evening, EarlyTime
means that the current time is between 7:45am and 8am, and LateTime
means that the current time is between 10:45am and 11am.
• 8am and 11am mean respectively that the train’s departure time is 8am, or
11am.
• The vocabulary includes an operator B for representing belief: if p is for-
mula, then B(p) is a formula meaning that you believe that p.
• CatchTrain means that you catch the train.
• Wait means that you wait longer than an hour for the train to depart.
(a) Provide the action descriptions for:
i. Write [2%]
ii. GoEarly [2%]
iii. GoLate [2%]
(b) Your goal is to catch the train but not wait for it.
i. Write down a description of this goal state. [2%]
ii. Using the operator B, write down your belief about the departure times
tonight, and the possible belief states that you may be in tomorrow
morning given that you don’t Write down the departure times.
[4%]
Page 12 of 15
iii. Suppose you don’t Write down the train times. Then do any of your
possible belief states tomorrow morning entail that you also believe that
there is a plan that guarantees you will achieve your goal? Explain your
answer.
[4%]
(c) The following utility function U over state descriptions captures your pref-
erences:
U(Catch ∧Wait) = 2
U(Catch ∧ ¬Wait) = −2
U(¬Catch) = −10
Furthermore, suppose that there is an even chance that the train leaves
at 8am or 11am. And suppose that not writing down the departure times
results in a 50% chance that you forget one of the departure times, in which
case there is an even chance between forgetting that it might depart at 8am,
and forgetting that it might depart at 11am. Furthermore, you will GoEarly
if and only if you believe there is a chance that the train will depart at 8am;
otherwise you will GoLate.
i. Calculate the expected utilities of Write and of ¬Write, assuming that
your decisions about which actions to perform subsequent to this are
dependent on your beliefs as described above. Be sure to show the
details of your calculations.
[8%]
ii. Why is the plan [Write,GoEarly] more optimal than the plan [Write,GoLate]?
[1%]
Page 13 of 15
2. Bayesian Net
Consider the following Bayesian net for five Boolean random variables, A, B, C,
D and E.
C
D E
BA
P (a) 0.7 P (b) 0.3
A P (c)
a 0.5
¬a 0.6
C B P (e)
c b 0.1
c ¬b 0.3
¬c b 0.1
¬c ¬b 0.5
C P (d)
c 0.4
¬c 0.6
(a) Calculate the exact value of P(A|e, d). Show every step of the calculation,
and in particular how this probability distribution is defined as a sum of
probabilities of the conditional probabilities shown in the above conditional
probability tables. Give your final answer to 2 decimal places.
[12%]
(b) Assume that to estimate P(E|a, d) using rejection sampling, we have gener-
ated 100 samples with the following results for a and d:
a ¬a
d 60 2
¬d 35 3
i. How many samples would we reject from this set?
[2%]
ii. Assuming that 10 of the remaining samples have E = e, what will our
estimate of P(E|a, d) be?
[2%]
Page 14 of 15
(c) Suppose that you have a direct sampling method where whenever you’re
sampling from a probability distribution of a boolean variable, you set that
variable to the value with the highest probability. For instance, if the prob-
ability distribution for picking the value of variable X is 〈0.3, 0.7〉, then you
will choose ¬x (or X = false). If the probability distribution is 〈0.5, 0.5〉,
then you pick x (or X = true).
i. Applying this rule, generate an atomic event for the above network using
direct sampling, being sure to use the variable ordering required by the
network. For each variable, justify which probability distribution you’re
sampling from.
[2%]
ii. For query P(C|e, d), compute the weight that would be assigned to the
sample from part (i) if we used the likelihood weighting method.
[7%]
Page 15 of 15
Specimen Answers
Part A
1. a
2. c
3. d
4. e
5. e
6. b
7. b
8. c
9. a
10. b
11. e
12. d
13. d
14. c
15. d
16. b
17. e
18. c
19. a
20. d
i
Part B
1. (a) (Bookwork) A propositional formula in clausal form consists of a set of
clauses, where each clause consists of a set of literals and each literal is
either a proposition or a negated proposition. The clauses are implicitly
conjoined and the literals implicitly disjoined.
Marking guide: 2 marks for definition.
(b) (Bookwork: Descriptions) The three improvements (as described in R&N)
are as follows:
i. Early termination: The algorithm detects whether the sentence must
be true or false, even with a partially completed model. A clause is true
if any of its literals is true, even if other literals have not been assigned
any truth values; hence, the sentence as a whole could be judged true
even before the model is complete. For example, the sentence (A ∨
B) ∧ (A ∨ C) is true if A is true, regardless of the values of B and C.
Similarly, a sentence is false if any clause is false, which occurs when
each of its literals is false. Again, this can occur before the model is
complete. Early termination thus avoids examination of entire subtrees
in the search space.
ii. Pure symbol heuristic:
A pure symbol is one that always appears with the same sign (polarity)
in all clauses. For instance, in the three clauses {A∨¬B,¬B ∨¬C,C ∨
A}, the symbol A is pure because only the positive literals appear, B
is pure because only the negative literals appear, and C is impure. If a
sentence has a model, then it has one with the pure symbols assigned so
as to make their literals true, because this ensures that a clause can never
be false. In determining the purity of a symbol, the algorithm can ignore
clauses that are already known to be true in the model constructed so
far. For instance, in our example, if the model contains B = false, then
the clause ¬B ∨ ¬C is already true, and C then becomes pure because
it now only appears in C ∨ A.
iii. Unit clause heuristic A unit clause is one with just one literal. In the
context of DPLL, it also means clauses in which all literals but one are
already assigned false in the model. For example, if the model contains
B = false then B ∨ ¬C becomes a unit clause since it is equivalent to
false∨¬C i.e. ¬C. For this last clause to be true, C must be set to false.
The unit clause heuristic assigns all such symbols before branching on
the remainder.
Marking guide: 1 mark in each case for stating the name of the improvements
(for a total of 3 marks). 2 marks for each concise and clear description –
ii
including definitions, wherever appropriate – of the improvements. 1 mark
given for each of the three examples.
(c) With ET standing for Early Termination deleting a true clause, running the
DPLL procedure on the set of clauses:
{S,Q} {¬Q,R} {¬Q,S} {¬R, S,Q} {R, S} {¬R,¬S}
Case-split assume R is picked
{S,Q} ET {¬Q,S} {S,Q} ET {¬S} if R is true
{Q} {¬Q} {Q} unit ¬S
{} unit Q
{S,Q} {¬Q} {¬Q,S} ET {S} ET if R is false
{S} {S} unit ¬Q
no clauses left unit S
Original set of clauses is satisfiable as no clauses are left in the second branch
after case split.
Marking guide: 4 marks for correct answer. Deduct 1 mark if the steps are
not clearly shown and labelled. 1 mark for indicating that the set of clauses
is satisfiable. Note: Other runs of the procedure are possible (obviously).
iii
(d) One possible refutation using binary resolution and factoring (F), with se-
lected literals underlined in shown clauses:
(4) ¬P ∨Q(a)
(3)
(5) ¬P ∨ ¬P
(F)
(6) ¬P
(2)
(7) Q(X)
(1)
(8) P
(6)
False
Marking guide: 1 mark for factoring step. 2 marks for ancestor resolution
step. Remaining marks for other steps. Deduct 1 mark if selected literal is
not shown.
Note: This may be a difficult proof as, at some point, one needs to resolve
a derived resolvant against one of its ancestors (ancestor-resolution step).
This is generally required for non-Horn clauses. Partial credit should be
given for any incomplete proof that gets close to a successful refutation.
iv
2. (a) The constraint graph, with variables as nodes and constraints indicated by
–: EA – EM – LM – LA
(b) (Bookwork): This heuristic involves choosing the variable with the fewest
domain values. By picking the variable that is most likely to cause failure
soon, the search tree can be pruned early. If there are no legal values left
for a variable X, the heuristic will select X and failure will be detected
immediately, forcing backtracking.
Marking guide: 4 marks for a clear and concise answer.
(c) (Bookwork) The most constraining variable heuristic can tie break on the
previous heuristic. It attempts to reduce the branching factor on future
choices by selecting the variable that is involved in the largest number of
constraints on other unassigned variables.
Marking guide: 4 marks for a clear and concise answer.
(d) (Bookwork) Constraint propagation is a means of enforcing the implications
of a constraint on one variable onto the other variables by looking ahead for
inconsistencies. It is thus effective at pruning the search space and enabling
the early detection of failure.
Marking guide: 2 marks for explaining what constraint propagation is. 1
mark for mentioning that it reduces the search space and detecting failure
early.
(e) The domains after EM = l but before forward-checking (FC):
EM : [l], LM : [a, h, t], EA: [d, w, v], LA: [p, c, n]
After FC: EM : [l], LM : [t], EA: [d, v], LA: [p, c, n]
The values a and t are deleted from the domain of LM because they are
incompatible with l due to the second constraint. The value w is eliminated
from the domain of EA due to the first constraint.
Marking Guide: 2 marks for giving the correct domains. 2 marks for expla-
nation.
(f) The domains after EM = l but before arc-consistency:
EM : [l], LM : [a, h, t], EA: [d, w, v], LA: [p, c, n]
After arc-consistency: EM : [l], LM : [t], EA: [d, v], LA: [p, c]
As for (2e) above, the values a and t are deleted from the domain of LM
because they are incompatible with l due to the second constraint. The
value w is eliminated due to the first constraint. Additionally, though, the
value n is eliminated from the domain of LA as there is no value for LM
that is consistent with n due to the third constraint.
Marking Guide: 2 marks for giving the correct domains. 2 marks for expla-
nation.
v
(g) This ternary constraint A + B = C on A, B, and C can be expressed as a
set of binary constraints as follows: A new variable AB can be introduced
which has a domain consisting of pairs of numbers. We can now have a
binary constraint that states that the value of A must be equal to the first
element of the pair-value of AB, another one that states that the value of
B must be equal to the second element of the pair-value of AB, and finally
one saying that the sum of the pair of numbers i.e. the value of AB must
be equal to C.
Marking guide: 1 mark for stating that there are 3 binary constraints. 3
marks for a sensible explanation of how the conversion to binary constraints
can be done.
vi
Part C
1. (a) i.
Action(Write,
Precond:Tonight
Effect:[])
ii.
Action(GoEarly,
Precond:EarlyTime
Effect:Catch, (when 11am : Wait))
iii.
Action(GoLate,
Precond:LateTime
Effect:(when 8am : ¬Catch), (when 11am : Catch))
Deduct 1 point for any incorrect precondition and any incorrect effect. Deduct
1 point if there are redundant propositions in the preconditions or effects
(e.g., B(both) as an effect in Write).
(b) i. Catch ∧ ¬Wait
ii. Belief state today is: B(8am ∨ 11am)
iii. Belief state the following morning is one of the following:
• B(8am ∨ 11am)
• B(8am) ∧B(¬11am)
• B(11am) ∧B(¬8am)
iv. If your belief state is B(8am), then you will believe that the plan
[GoEarly] is guaranteed to achieve the goal, and if you are in the belief
state B(11am), then you will believe that [GoLate] is guaranteed to
achieve your goal.
(c) i.
EU(Write) =
∑
s P (s|Write)U(s)
= 0.5 ∗ −2 + 0.5 ∗ 2
= 0
EU(¬Write) = ∑s P (s|¬Write)U(s)
= 0.5 ∗ ((0.5 ∗ −2) + (0.5 ∗ 2)) + 0.25 ∗ ((0.5 ∗ 2) + (0.5 ∗ −2))+
0.25((0.5 ∗ −10) + (0.5 ∗ 2))
= 0 + 0 +−1
= −1
vii
ii. EU([Write,GoEarly]) = 0, as calculated in (c) part (i) above. EU([Write,GoLate]) =
0.5 ∗ 2 + 0.5 ∗ −10 = −4. So since [Write,GoEarly] has the higher ex-
pected utility, this action sequence is more optimal.
viii
2. Bayesian Nets
(a)
P(A|e, d) = α∑b∑cP(A)P (b)P(c|A)P (d|c)P (e|b, c)
= αP(A)
∑
b P (b)
∑
cP(c|A)P (d|c)P (e|b, c)
P (a|e, d) = αP (a)∑b P (b)∑c P (c|a)P (d|c)P (e|b, c)
= α(0.7 ∗ 0.3((0.5 ∗ 0.4 ∗ 0.1) + (0.5 ∗ 0.6 ∗ 0.1))+
0.7 ∗ 0.7 ∗ ((0.5 ∗ 0.4 ∗ 0.3) + (0.5 ∗ 0.6 ∗ 0.5)))
= α(0.7 ∗ 0.3 ∗ 0.05 + 0.7 ∗ 0.7 ∗ 0.15)
= α0.084
P (¬a|e, d) = αP (¬a)∑b P (b)∑c P (c|¬a)P (d|c)P (e|b, c)
= α(0.3 ∗ 0.3 ∗ ((0.6 ∗ 0.4 ∗ 0.1) + (0.4 ∗ 0.6 ∗ 0.1))+
0.3 ∗ 0.7 ∗ ((0.6 ∗ 0.4 ∗ 0.3) + (0.4 ∗ 0.6 ∗ 0.5)))
= α(0.3 ∗ 0.3 ∗ 0.048 + 0.3 ∗ 0.7 ∗ 0.84)
= α0.18072
P(A|e, d) = 1
0.084+0.18072
〈0.084, 0.18027〉
= 〈0.32, 0.68〉
Answer given to 2 decimal places.
Deduct half the points for not showing the workings. Deduct 1 point for each
algebraic error and 1 point for each arithmetic error.
(b) i. 40
ii.
P(E|a, d) = 〈10
60
, 50
60
〉
= 〈0.17, 0.83〉
(c) i. The atomic event you would get would be deterministic given this
method of direct sampling from a probability distribution of a Boolean
variable, and it would generate a,¬b, c,¬d,¬e.
ii. Set w = 1. As in part (i), sampling from P(A) and P(B) and P(C|a)
yields a,¬b, c. D is an evidence variable with value false, and so w ←
w ∗ P (¬d|c) = 1 ∗ 0.6 = 0.6. E is also an evidence variable with false,
and so w ← w ∗ P (¬e|¬b, c) = 0.6 ∗ 0.7 = 0.42. So the weight assigned
to this sample is 0.42.
Deduct 1 point for each error.
ix
学霸联盟
COLLEGE OF SCIENCE AND ENGINEERING
SCHOOL OF INFORMATICS
INFORMATICS 2D: REASONING AND AGENTS
Friday 15 th August 2014
14:30 to 16:30
INSTRUCTIONS TO CANDIDATES
1. Answer Parts A, B and C.
2. The multiple choice questions in Part A are worth 50% in total and
are each worth the same amount. Mark one answer only for each
question - multiple answers will score 0. Marks will not be deducted
for incorrect multiple choice exam answers.
3. Parts B and C are each worth 25%. Answer ONE question from Part
B and ONE question from Part C.
4. Use the special mark sheet for Part A. Answer Parts B and C each in
a separate script book.
CALCULATORS ARE PERMITTED.
Convener: J. Bradfield
External Examiner: C. Johnson
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
Part A
ANSWER ALL QUESTIONS IN PART A. Use the special mark sheet.
1. Which one of the following best describes the statement entailment for first-order
logic is semidecidable?
(a) Algorithms exist that say yes to every entailed sentence, but no algorithm
exists that also says no to every nonentailed sentence.
(b) Algorithms exist that say yes to some entailed sentence, but no algorithm
exists that also says no to every nonentailed sentence.
(c) Algorithms exist that say no to every nonentailed sentence, but no algorithm
exists that also says yes to every entailed sentence.
(d) No algorithm exists that says yes to every entailed sentence, but algorithms
exist that say no to every nonentailed sentence.
(e) Algorithms exist that say yes to every entailed sentence and no to every
nonentailed sentence.
2. In the context of informed search, what is meant by a relaxed problem?
(a) It is one with fewer actions.
(b) It is one with fewer restrictions on the states.
(c) It is one with fewer restrictions on the actions.
(d) It is one with fewer restrictions on the heuristic.
(e) It is one with fewer restrictions on the environment.
3. Which of the following, if any, is the most general unifier of f(x)+f(y) < g(x)×x
and f(x) + f(x) < g(g(y))× x, where x and y are variables?
(a) Unification fails due to a conflict.
(b) {y/g(y)}
(c) {y/x, x/g(x)}
(d) Unification fails due an occurs-check violation.
(e) {x/g(x)}
Page 1 of 15
4. In the context of the situation calculus, fluents are functions and predicates that
can vary from one situation to the next. Which one of the following statements
best describes the form taken by a successor-state axiom?
(a) Action is possible ⇒
(Fluent was true before and action left it alone
∨ Action’s effect made it true)
(b) Fluent is true in result state ⇔
(Fluent was true before and action left it alone
∨ Action’s effect made it true)
(c) (Fluent is true in result state ⇔
(Fluent was true before and action left it alone
∧ Action’s effect made it true))
⇒ Action is possible
(d) Action is possible ⇒
(Fluent is true in result state ⇔ Action’s effect made it true)
(e) Action is possible ⇒
(Fluent is true in result state ⇔
(Fluent was true before and action left it alone
∨ Action’s effect made it true))
5. In a vocabulary with 4 propositional symbols A, B, C and D how many models
are there for the sentence A⇒ B?
(a) 3
(b) 6
(c) 1
(d) 2
(e) 12
Page 2 of 15
6. Consider the following lookahead tree for a two-person game, which is searched
depth first, left-to-right. Each node is named by a letter. Nodes with shape ∆ are
where Max is due to play; nodes with shape ∇ are where Min is due to play. The
numbers below the leaves of the tree are the results of the evaluation function
applied to that leaf.
Which nodes would an α/β search not need to visit?
(a) I and J .
(b) L and M .
(c) M .
(d) D, K, L and M .
(e) I, J , K, L and M .
7. Which of the following is not part of the DPLL algorithm, as given in Russell &
Norvig and the lectures?
(a) A clause is true if one of its literals is true.
(b) A pure symbol can be set to false.
(c) A literal in a unit clause can be set to true.
(d) A sentence is true if any of its clauses is true.
(e) A pure symbol can be set to true.
8. Which of the following sets of clauses – where a and b are new Skolem constants,
and F is a new Skolem function – is the clausal normal form (CNF) of the formula
∃x.[P (x)↔ ∀y.Q(x, y)]?
(a) {¬P (x) ∨Q(x, y), P (x) ∨ ¬Q(x, y)}
(b) {¬P (x) ∨Q(x, F (x)), P (x) ∨ ¬Q(x, y), }
(c) {¬P (a) ∨Q(a, y), P (a) ∨ ¬Q(a, b)}
(d) {¬P (x) ∨Q(x, a), P (x) ∨ ¬Q(x, y)}
(e) {¬P (a) ∨Q(a, y), P (a) ∨ ¬Q(a, F (a))}
Page 3 of 15
9. Consider a constraint satisfaction problem (CSP) with variablesA,B,C,D,E, F,G
that can take values from the domain {1, 2, 3} and the following constraints only:
• A 6= B,A 6= F
• B 6= C,B 6= F
• C 6= D,C 6= F
• D 6= E,D 6= F
• E 6= F
Assuming that the following partial assignment with A = 1 and B = 3 has been
generated, and that the next variable to be chosen is C, what would the least
constraining value heuristic do next?
(a) Assign C = 1.
(b) Assign C = 2.
(c) Assign C = {1, 2}.
(d) Delete C from the problem.
(e) Assign C = 3.
10. Which of the following statements is false of Generalised Modus Ponens (GMP)?
(a) GMP is sound.
(b) GMP is complete when combined with factoring.
(c) GMP can be applied both forwards and backwards.
(d) GMP uses unification.
(e) GMP may not terminate on non-theorems.
Page 4 of 15
11. “Contingency planning that includes sensing actions and a description of different
paths for different circumstances” is an accurate description for which of the
following planning techniques?
(a) Replanning and execution monitoring
(b) Sensorless/Conformant planning
(c) Hierarchical task network planning
(d) Continuous planning
(e) Conditional planning
12. Assume you have to add an action D with postconditions ¬p and ¬q in a plan
with existing causal links A
p→ B and B q→ C. Which of the following total
orderings resolves all conflicts that might arise from addition of D?
(a) A ≺ B ≺ D ≺ C
(b) A ≺ C ≺ B ≺ D
(c) A ≺ C ≺ D ≺ B
(d) D ≺ A ≺ B ≺ C
(e) A ≺ D ≺ B ≺ C
13. In how many ways is the action schema
Action(Fly(p, from, to),
Precond:At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
Effect:¬At(p, from) ∧ At(p, to))
applicable in the following state:
At(P1, SFO) ∧ At(P2,Heathrow)∧
Airport(CDG) ∧ Airport(Heathrow) ∧ Airport(SFO)∧
Plane(P1) ∧ Plane(P2)
(a) 1
(b) 2
(c) 4
(d) 6
(e) 9
Page 5 of 15
14. You are given four action descriptions with conditional effects:
Action(A,Precond:{P,X},Effect:{(when Z : ¬X)})
Action(B,Precond:{¬Y },Effect:{(when P : Z,X)})
Action(C,Precond:{Z},Effect:{(when P : ¬Y ), X})
Action(D,Precond:{¬X},Effect:{(when P : Z,X)})
What state would result from executing the action sequence [D,C,B,A] in the
state {P, Y }?
(a) The plan isn’t executable because the preconditions for action B aren’t met.
(b) {P,X,Z}
(c) {P,Z}
(d) {P,¬X,¬Y, Z}
(e) {X, Y, Z}
15. Which of the following statements about Hierarchical Task Network (HTN) Plan-
ning is correct?
(a) All refinements of high-level actions (HLAs) are a sequence of only primitive
actions.
(b) A refinement of an HLA always has the same preconditions as the HLA.
(c) If no states in the pessimistic description of the reachable states of a high-
level plan (HLP) satisfy the goal, then that HLP is guaranteed to fail.
(d) If A is in the Effect of one refinement of HLA h, and ¬A is in another
refinement of h, then +˜A is in Reach+(s, h).
(e) An HLA that achieves a goal has the downward refinement property only if
all its implementations also achieve that goal.
16. The following table specifies a joint probability distribution for three Boolean
random variables A, B , C :
a ¬a
b ¬b b ¬b
c 0.28 0.03 0.08 0.04
¬c 0.09 0.23 0.11 0.14
Which of the following is the correct value for P (b ∨ ¬a)?
(a) 0.19
(b) 0.74
(c) 0.63
(d) 0.37
(e) 0.52
Page 6 of 15
17. Suppose that a direct sampling method produces the event [false, true, true, true]
for the Boolean variables [Cloudy , Sprinker ,Rain,WetGrass ] in the Bayesian net-
work shown below in exactly 4 out of 100 trials. Then what is the size of the
difference between the true probability P (¬cloudy , sprinkler , rain,wetgrass) and
its estimated probability from direct sampling?
(a) 0.095
(b) 0.04
(c) 0.0495
(d) 0.0895
(e) 0.0095
Page 7 of 15
18. Assume we generate 100 samples in a Bayes net with three variables A, B, and
C to estimate the distribution P(C|¬a,¬b) and obtain the following results:
b ¬b
a ¬a a ¬a
c 15 5 10 5
¬c 20 10 20 15
What is the correct estimated distribution 〈P (c|¬a,¬b), P (¬c|¬a,¬b)〉 that we
would obtain by applying the rejection sampling method to this problem?
(a) 〈 1
20
, 3
20
〉
(b) 〈 7
20
, 13
20
〉
(c) 〈1
4
, 3
4
〉
(d) 〈1
3
, 2
3
〉
(e) 〈1
6
, 5
6
〉
19. The process of computing P(Xt+k|e1:t) for k > 0 in a temporal probabilistic
model with state variables X and evidence variables e is called
(a) prediction
(b) smoothing
(c) abstraction
(d) monitoring
(e) filtering
20. Let strict preference be denoted by the relation symbol , indifference by ∼,
weak preference by %, and lotteries be written as [p1, O1; . . . ; pn, On], where each
pi is the probability associated with outcome Oi. Which of the following is not
an axiom of utility theory?
(a) (A B) ∨ (B A) ∨ (A ∼ B)
(b) (A B) ∧ (B C)⇒ (A C)
(c) A B C ⇒ ∃p [p,A; 1− p, C] ∼ B
(d) A ∼ B ⇒ [p,A; 1− p, C] [p,B; 1− p, C]
(e) A B ⇒ (p ≥ q ⇔ [p,A; 1− p,B] % [q, A; 1− q, B])
Page 8 of 15
Part B
ANSWER ONE QUESTION FROM PART B
1. (a) Define clausal form for propositional logic formulae.
[2%]
(b) State and describe the three improvements that the Davis-Putnam-Logemann-
Loveland (DPLL) algorithm has over truth-table enumeration. Illustrate
each of these improvements with an appropriate example.
[12%]
(c) Apply the DPLL procedure to the following set of clauses:
{S,Q}, {¬Q,R}, {¬Q,S}, {¬R, S,Q}, {R, S}, {¬R,¬S}
Is the set of clauses satisfiable? Show all the steps of the procedure.
[5%]
(d) Find a refutation of the clauses (1)–(4) below using binary resolution and
factoring. Use clause (4) as one of your starting clauses and indicate both
the selected literals and clauses used at each step. Note that X is a variable,
and a and b are constants.
¬Q(b) ∨ P (1)
P ∨Q(X) (2)
¬Q(X) ∨ ¬P (3)
¬P ∨Q(a) (4)
[6%]
Page 9 of 15
2. Consider the following CSP problem:
You are arranging a series of interviews for the film stars attending the Edinburgh
Film Festival. There are several time slots, each represented by a variable: Early
Morning (EM), Late Morning (LM), Early Afternoon (EA), and Late Afternoon
(LA). The domains for the variables, i.e. the possible interviewees for each time
slot, are as follows (with letters used to abbreviate the various choices):
EM : Scarlett Johansson (s), Jennifer Lawrence (l)
LM : Angelina Jolie (a), Tom Hanks (h), Tom Cruise (t)
EA: Robert Downey Jr (d), Walter White (w), Vin Diesel (v)
LA: Brad Pitt (p), George Clooney (c), Liam Neeson (n)
However, to ensure that the stars, fans and film studios are happy, the arrange-
ment must satisfy the following constraints:
• As she wakes up at 5am everyday to meditate, the early morning slot must
be for Scarlett Johansson, or else the early afternoon slot must be Robert
Downey Jr or Vin Diesel, who go to bed late.
• If you decide to arrange an interview for Jennifer Lawrence then you must
also schedule one for Tom Cruise, to ensure he gets some of the limelight.
• You must ensure that at least one of the following interviews happens to
give the Festival plenty of media attention: George Clooney, Brad Pitt, or
Tom Hanks.
(a) Give the constraint graph for the variables EM , LM , EA, and LA.
[3%]
(b) Explain what the most constrained variable heuristic is.
[4%]
(c) Explain what the most constraining variable heuristic is.
[4%]
(d) What is meant by constraint propagation? Why is it an effective procedure?
[3%]
(e) In the given CSP, assume that your first decision is to schedule Jennifer
Lawrence for the early morning slot, i.e. EM=l, give the domain for each
of the variables after forward-checking. Explain your answer.
[3%]
Page 10 of 15
(f) In the given CSP, assuming once more that you start with EM=l, give the
domain for each of the variables after forward-checking and arc-consistency
have been enforced. Explain your answer.
[4%]
(g) Explain how a single ternary arithmetic constraint such as A + B = C can
be turned into binary constraints.
[4%]
Page 11 of 15
Part C
ANSWER ONE QUESTION FROM PART C
1. Planning and Decision Making
You want to catch a train tomorrow. You know that there are two possible
departure times: 8am or 11am. The actions available to you are:
• To Write down the departure times by 7pm tonight, so you remember what
they are.
• To GoEarly to the station (i.e., between 7:45am and 8am), in which case
you catch the train but may have to wait longer than 1 hour.
• To GoLate to the station (i.e., between 10:45 and 11am), in which case you
might miss the train.
If you don’t Write down the departure times, then there is a chance that an
external force—let’s call it nature—will make you forget one of the departure
times by tomorrow morning.
Assume the following formulae for describing this situation:
• Tonight means that the current time is before 7pm this evening, EarlyTime
means that the current time is between 7:45am and 8am, and LateTime
means that the current time is between 10:45am and 11am.
• 8am and 11am mean respectively that the train’s departure time is 8am, or
11am.
• The vocabulary includes an operator B for representing belief: if p is for-
mula, then B(p) is a formula meaning that you believe that p.
• CatchTrain means that you catch the train.
• Wait means that you wait longer than an hour for the train to depart.
(a) Provide the action descriptions for:
i. Write [2%]
ii. GoEarly [2%]
iii. GoLate [2%]
(b) Your goal is to catch the train but not wait for it.
i. Write down a description of this goal state. [2%]
ii. Using the operator B, write down your belief about the departure times
tonight, and the possible belief states that you may be in tomorrow
morning given that you don’t Write down the departure times.
[4%]
Page 12 of 15
iii. Suppose you don’t Write down the train times. Then do any of your
possible belief states tomorrow morning entail that you also believe that
there is a plan that guarantees you will achieve your goal? Explain your
answer.
[4%]
(c) The following utility function U over state descriptions captures your pref-
erences:
U(Catch ∧Wait) = 2
U(Catch ∧ ¬Wait) = −2
U(¬Catch) = −10
Furthermore, suppose that there is an even chance that the train leaves
at 8am or 11am. And suppose that not writing down the departure times
results in a 50% chance that you forget one of the departure times, in which
case there is an even chance between forgetting that it might depart at 8am,
and forgetting that it might depart at 11am. Furthermore, you will GoEarly
if and only if you believe there is a chance that the train will depart at 8am;
otherwise you will GoLate.
i. Calculate the expected utilities of Write and of ¬Write, assuming that
your decisions about which actions to perform subsequent to this are
dependent on your beliefs as described above. Be sure to show the
details of your calculations.
[8%]
ii. Why is the plan [Write,GoEarly] more optimal than the plan [Write,GoLate]?
[1%]
Page 13 of 15
2. Bayesian Net
Consider the following Bayesian net for five Boolean random variables, A, B, C,
D and E.
C
D E
BA
P (a) 0.7 P (b) 0.3
A P (c)
a 0.5
¬a 0.6
C B P (e)
c b 0.1
c ¬b 0.3
¬c b 0.1
¬c ¬b 0.5
C P (d)
c 0.4
¬c 0.6
(a) Calculate the exact value of P(A|e, d). Show every step of the calculation,
and in particular how this probability distribution is defined as a sum of
probabilities of the conditional probabilities shown in the above conditional
probability tables. Give your final answer to 2 decimal places.
[12%]
(b) Assume that to estimate P(E|a, d) using rejection sampling, we have gener-
ated 100 samples with the following results for a and d:
a ¬a
d 60 2
¬d 35 3
i. How many samples would we reject from this set?
[2%]
ii. Assuming that 10 of the remaining samples have E = e, what will our
estimate of P(E|a, d) be?
[2%]
Page 14 of 15
(c) Suppose that you have a direct sampling method where whenever you’re
sampling from a probability distribution of a boolean variable, you set that
variable to the value with the highest probability. For instance, if the prob-
ability distribution for picking the value of variable X is 〈0.3, 0.7〉, then you
will choose ¬x (or X = false). If the probability distribution is 〈0.5, 0.5〉,
then you pick x (or X = true).
i. Applying this rule, generate an atomic event for the above network using
direct sampling, being sure to use the variable ordering required by the
network. For each variable, justify which probability distribution you’re
sampling from.
[2%]
ii. For query P(C|e, d), compute the weight that would be assigned to the
sample from part (i) if we used the likelihood weighting method.
[7%]
Page 15 of 15
Specimen Answers
Part A
1. a
2. c
3. d
4. e
5. e
6. b
7. b
8. c
9. a
10. b
11. e
12. d
13. d
14. c
15. d
16. b
17. e
18. c
19. a
20. d
i
Part B
1. (a) (Bookwork) A propositional formula in clausal form consists of a set of
clauses, where each clause consists of a set of literals and each literal is
either a proposition or a negated proposition. The clauses are implicitly
conjoined and the literals implicitly disjoined.
Marking guide: 2 marks for definition.
(b) (Bookwork: Descriptions) The three improvements (as described in R&N)
are as follows:
i. Early termination: The algorithm detects whether the sentence must
be true or false, even with a partially completed model. A clause is true
if any of its literals is true, even if other literals have not been assigned
any truth values; hence, the sentence as a whole could be judged true
even before the model is complete. For example, the sentence (A ∨
B) ∧ (A ∨ C) is true if A is true, regardless of the values of B and C.
Similarly, a sentence is false if any clause is false, which occurs when
each of its literals is false. Again, this can occur before the model is
complete. Early termination thus avoids examination of entire subtrees
in the search space.
ii. Pure symbol heuristic:
A pure symbol is one that always appears with the same sign (polarity)
in all clauses. For instance, in the three clauses {A∨¬B,¬B ∨¬C,C ∨
A}, the symbol A is pure because only the positive literals appear, B
is pure because only the negative literals appear, and C is impure. If a
sentence has a model, then it has one with the pure symbols assigned so
as to make their literals true, because this ensures that a clause can never
be false. In determining the purity of a symbol, the algorithm can ignore
clauses that are already known to be true in the model constructed so
far. For instance, in our example, if the model contains B = false, then
the clause ¬B ∨ ¬C is already true, and C then becomes pure because
it now only appears in C ∨ A.
iii. Unit clause heuristic A unit clause is one with just one literal. In the
context of DPLL, it also means clauses in which all literals but one are
already assigned false in the model. For example, if the model contains
B = false then B ∨ ¬C becomes a unit clause since it is equivalent to
false∨¬C i.e. ¬C. For this last clause to be true, C must be set to false.
The unit clause heuristic assigns all such symbols before branching on
the remainder.
Marking guide: 1 mark in each case for stating the name of the improvements
(for a total of 3 marks). 2 marks for each concise and clear description –
ii
including definitions, wherever appropriate – of the improvements. 1 mark
given for each of the three examples.
(c) With ET standing for Early Termination deleting a true clause, running the
DPLL procedure on the set of clauses:
{S,Q} {¬Q,R} {¬Q,S} {¬R, S,Q} {R, S} {¬R,¬S}
Case-split assume R is picked
{S,Q} ET {¬Q,S} {S,Q} ET {¬S} if R is true
{Q} {¬Q} {Q} unit ¬S
{} unit Q
{S,Q} {¬Q} {¬Q,S} ET {S} ET if R is false
{S} {S} unit ¬Q
no clauses left unit S
Original set of clauses is satisfiable as no clauses are left in the second branch
after case split.
Marking guide: 4 marks for correct answer. Deduct 1 mark if the steps are
not clearly shown and labelled. 1 mark for indicating that the set of clauses
is satisfiable. Note: Other runs of the procedure are possible (obviously).
iii
(d) One possible refutation using binary resolution and factoring (F), with se-
lected literals underlined in shown clauses:
(4) ¬P ∨Q(a)
(3)
(5) ¬P ∨ ¬P
(F)
(6) ¬P
(2)
(7) Q(X)
(1)
(8) P
(6)
False
Marking guide: 1 mark for factoring step. 2 marks for ancestor resolution
step. Remaining marks for other steps. Deduct 1 mark if selected literal is
not shown.
Note: This may be a difficult proof as, at some point, one needs to resolve
a derived resolvant against one of its ancestors (ancestor-resolution step).
This is generally required for non-Horn clauses. Partial credit should be
given for any incomplete proof that gets close to a successful refutation.
iv
2. (a) The constraint graph, with variables as nodes and constraints indicated by
–: EA – EM – LM – LA
(b) (Bookwork): This heuristic involves choosing the variable with the fewest
domain values. By picking the variable that is most likely to cause failure
soon, the search tree can be pruned early. If there are no legal values left
for a variable X, the heuristic will select X and failure will be detected
immediately, forcing backtracking.
Marking guide: 4 marks for a clear and concise answer.
(c) (Bookwork) The most constraining variable heuristic can tie break on the
previous heuristic. It attempts to reduce the branching factor on future
choices by selecting the variable that is involved in the largest number of
constraints on other unassigned variables.
Marking guide: 4 marks for a clear and concise answer.
(d) (Bookwork) Constraint propagation is a means of enforcing the implications
of a constraint on one variable onto the other variables by looking ahead for
inconsistencies. It is thus effective at pruning the search space and enabling
the early detection of failure.
Marking guide: 2 marks for explaining what constraint propagation is. 1
mark for mentioning that it reduces the search space and detecting failure
early.
(e) The domains after EM = l but before forward-checking (FC):
EM : [l], LM : [a, h, t], EA: [d, w, v], LA: [p, c, n]
After FC: EM : [l], LM : [t], EA: [d, v], LA: [p, c, n]
The values a and t are deleted from the domain of LM because they are
incompatible with l due to the second constraint. The value w is eliminated
from the domain of EA due to the first constraint.
Marking Guide: 2 marks for giving the correct domains. 2 marks for expla-
nation.
(f) The domains after EM = l but before arc-consistency:
EM : [l], LM : [a, h, t], EA: [d, w, v], LA: [p, c, n]
After arc-consistency: EM : [l], LM : [t], EA: [d, v], LA: [p, c]
As for (2e) above, the values a and t are deleted from the domain of LM
because they are incompatible with l due to the second constraint. The
value w is eliminated due to the first constraint. Additionally, though, the
value n is eliminated from the domain of LA as there is no value for LM
that is consistent with n due to the third constraint.
Marking Guide: 2 marks for giving the correct domains. 2 marks for expla-
nation.
v
(g) This ternary constraint A + B = C on A, B, and C can be expressed as a
set of binary constraints as follows: A new variable AB can be introduced
which has a domain consisting of pairs of numbers. We can now have a
binary constraint that states that the value of A must be equal to the first
element of the pair-value of AB, another one that states that the value of
B must be equal to the second element of the pair-value of AB, and finally
one saying that the sum of the pair of numbers i.e. the value of AB must
be equal to C.
Marking guide: 1 mark for stating that there are 3 binary constraints. 3
marks for a sensible explanation of how the conversion to binary constraints
can be done.
vi
Part C
1. (a) i.
Action(Write,
Precond:Tonight
Effect:[])
ii.
Action(GoEarly,
Precond:EarlyTime
Effect:Catch, (when 11am : Wait))
iii.
Action(GoLate,
Precond:LateTime
Effect:(when 8am : ¬Catch), (when 11am : Catch))
Deduct 1 point for any incorrect precondition and any incorrect effect. Deduct
1 point if there are redundant propositions in the preconditions or effects
(e.g., B(both) as an effect in Write).
(b) i. Catch ∧ ¬Wait
ii. Belief state today is: B(8am ∨ 11am)
iii. Belief state the following morning is one of the following:
• B(8am ∨ 11am)
• B(8am) ∧B(¬11am)
• B(11am) ∧B(¬8am)
iv. If your belief state is B(8am), then you will believe that the plan
[GoEarly] is guaranteed to achieve the goal, and if you are in the belief
state B(11am), then you will believe that [GoLate] is guaranteed to
achieve your goal.
(c) i.
EU(Write) =
∑
s P (s|Write)U(s)
= 0.5 ∗ −2 + 0.5 ∗ 2
= 0
EU(¬Write) = ∑s P (s|¬Write)U(s)
= 0.5 ∗ ((0.5 ∗ −2) + (0.5 ∗ 2)) + 0.25 ∗ ((0.5 ∗ 2) + (0.5 ∗ −2))+
0.25((0.5 ∗ −10) + (0.5 ∗ 2))
= 0 + 0 +−1
= −1
vii
ii. EU([Write,GoEarly]) = 0, as calculated in (c) part (i) above. EU([Write,GoLate]) =
0.5 ∗ 2 + 0.5 ∗ −10 = −4. So since [Write,GoEarly] has the higher ex-
pected utility, this action sequence is more optimal.
viii
2. Bayesian Nets
(a)
P(A|e, d) = α∑b∑cP(A)P (b)P(c|A)P (d|c)P (e|b, c)
= αP(A)
∑
b P (b)
∑
cP(c|A)P (d|c)P (e|b, c)
P (a|e, d) = αP (a)∑b P (b)∑c P (c|a)P (d|c)P (e|b, c)
= α(0.7 ∗ 0.3((0.5 ∗ 0.4 ∗ 0.1) + (0.5 ∗ 0.6 ∗ 0.1))+
0.7 ∗ 0.7 ∗ ((0.5 ∗ 0.4 ∗ 0.3) + (0.5 ∗ 0.6 ∗ 0.5)))
= α(0.7 ∗ 0.3 ∗ 0.05 + 0.7 ∗ 0.7 ∗ 0.15)
= α0.084
P (¬a|e, d) = αP (¬a)∑b P (b)∑c P (c|¬a)P (d|c)P (e|b, c)
= α(0.3 ∗ 0.3 ∗ ((0.6 ∗ 0.4 ∗ 0.1) + (0.4 ∗ 0.6 ∗ 0.1))+
0.3 ∗ 0.7 ∗ ((0.6 ∗ 0.4 ∗ 0.3) + (0.4 ∗ 0.6 ∗ 0.5)))
= α(0.3 ∗ 0.3 ∗ 0.048 + 0.3 ∗ 0.7 ∗ 0.84)
= α0.18072
P(A|e, d) = 1
0.084+0.18072
〈0.084, 0.18027〉
= 〈0.32, 0.68〉
Answer given to 2 decimal places.
Deduct half the points for not showing the workings. Deduct 1 point for each
algebraic error and 1 point for each arithmetic error.
(b) i. 40
ii.
P(E|a, d) = 〈10
60
, 50
60
〉
= 〈0.17, 0.83〉
(c) i. The atomic event you would get would be deterministic given this
method of direct sampling from a probability distribution of a Boolean
variable, and it would generate a,¬b, c,¬d,¬e.
ii. Set w = 1. As in part (i), sampling from P(A) and P(B) and P(C|a)
yields a,¬b, c. D is an evidence variable with value false, and so w ←
w ∗ P (¬d|c) = 1 ∗ 0.6 = 0.6. E is also an evidence variable with false,
and so w ← w ∗ P (¬e|¬b, c) = 0.6 ∗ 0.7 = 0.42. So the weight assigned
to this sample is 0.42.
Deduct 1 point for each error.
ix
学霸联盟
