xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：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

学霸联盟