xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

扫码添加客服微信

扫描添加客服微信

程序代写案例-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

学霸联盟

- 留学生代写
- Python代写
- Java代写
- c/c++代写
- 数据库代写
- 算法代写
- 机器学习代写
- 数据挖掘代写
- 数据分析代写
- Android代写
- html代写
- 计算机网络代写
- 操作系统代写
- 计算机体系结构代写
- R代写
- 数学代写
- 金融作业代写
- 微观经济学代写
- 会计代写
- 统计代写
- 生物代写
- 物理代写
- 机械代写
- Assignment代写
- sql数据库代写
- analysis代写
- Haskell代写
- Linux代写
- Shell代写
- Diode Ideality Factor代写
- 宏观经济学代写
- 经济代写
- 计量经济代写
- math代写
- 金融统计代写
- 经济统计代写
- 概率论代写
- 代数代写
- 工程作业代写
- Databases代写
- 逻辑代写
- JavaScript代写
- Matlab代写
- Unity代写
- BigDate大数据代写
- 汇编代写
- stat代写
- scala代写
- OpenGL代写
- CS代写
- 程序代写
- 简答代写
- Excel代写
- Logisim代写
- 代码代写
- 手写题代写
- 电子工程代写
- 判断代写
- 论文代写
- stata代写
- witness代写
- statscloud代写
- 证明代写
- 非欧几何代写
- 理论代写
- http代写
- MySQL代写
- PHP代写
- 计算代写
- 考试代写
- 博弈论代写
- 英语代写
- essay代写
- 不限代写
- lingo代写
- 线性代数代写
- 文本处理代写
- 商科代写
- visual studio代写
- 光谱分析代写
- report代写
- GCP代写
- 无代写
- 电力系统代写
- refinitiv eikon代写
- 运筹学代写
- simulink代写
- 单片机代写
- GAMS代写
- 人力资源代写
- 报告代写
- SQLAlchemy代写
- Stufio代写
- sklearn代写
- 计算机架构代写
- 贝叶斯代写
- 以太坊代写
- 计算证明代写
- prolog代写
- 交互设计代写
- mips代写
- css代写
- 云计算代写
- dafny代写
- quiz考试代写
- js代写
- 密码学代写
- ml代写
- 水利工程基础代写
- 经济管理代写
- Rmarkdown代写
- 电路代写
- 质量管理画图代写
- sas代写
- 金融数学代写
- processing代写
- 预测分析代写
- 机械力学代写
- vhdl代写
- solidworks代写
- 不涉及代写
- 计算分析代写
- Netlogo代写
- openbugs代写
- 土木代写
- 国际金融专题代写
- 离散数学代写
- openssl代写
- 化学材料代写
- eview代写
- nlp代写
- Assembly language代写
- gproms代写
- studio代写
- robot analyse代写
- pytorch代写
- 证明题代写
- latex代写
- coq代写
- 市场营销论文代写
- 人力资论文代写
- weka代写
- 英文代写
- Minitab代写
- 航空代写
- webots代写
- Advanced Management Accounting代写
- Lunix代写
- 云基础代写
- 有限状态过程代写
- aws代写
- AI代写
- 图灵机代写
- Sociology代写
- 分析代写
- 经济开发代写
- Data代写
- jupyter代写
- 通信考试代写
- 网络安全代写
- 固体力学代写
- spss代写
- 无编程代写
- react代写
- Ocaml代写
- 期货期权代写
- Scheme代写
- 数学统计代写
- 信息安全代写
- Bloomberg代写
- 残疾与创新设计代写
- 历史代写
- 理论题代写
- cpu代写
- 计量代写
- Xpress-IVE代写
- 微积分代写
- 材料学代写
- 代写
- 会计信息系统代写
- 凸优化代写
- 投资代写
- F#代写
- C#代写
- arm代写
- 伪代码代写
- 白话代写
- IC集成电路代写
- reasoning代写
- agents代写
- 精算代写
- opencl代写
- Perl代写
- 图像处理代写
- 工程电磁场代写
- 时间序列代写
- 数据结构算法代写
- 网络基础代写
- 画图代写
- Marie代写
- ASP代写
- EViews代写
- Interval Temporal Logic代写
- ccgarch代写
- rmgarch代写
- jmp代写
- 选择填空代写
- mathematics代写
- winbugs代写
- maya代写
- Directx代写
- PPT代写
- 可视化代写
- 工程材料代写
- 环境代写
- abaqus代写
- 投资组合代写
- 选择题代写
- openmp.c代写
- cuda.cu代写
- 传感器基础代写
- 区块链比特币代写
- 土壤固结代写
- 电气代写
- 电子设计代写
- 主观题代写
- 金融微积代写
- ajax代写
- Risk theory代写
- tcp代写
- tableau代写
- mylab代写
- research paper代写
- 手写代写
- 管理代写
- paper代写
- 毕设代写
- 衍生品代写
- 学术论文代写
- 计算画图代写
- SPIM汇编代写
- 演讲稿代写
- 金融实证代写
- 环境化学代写
- 通信代写
- 股权市场代写
- 计算机逻辑代写
- Microsoft Visio代写
- 业务流程管理代写
- Spark代写
- USYD代写
- 数值分析代写
- 有限元代写
- 抽代代写
- 不限定代写
- IOS代写
- scikit-learn代写
- ts angular代写
- sml代写
- 管理决策分析代写
- vba代写
- 墨大代写
- erlang代写
- Azure代写
- 粒子物理代写
- 编译器代写
- socket代写
- 商业分析代写
- 财务报表分析代写
- Machine Learning代写
- 国际贸易代写
- code代写
- 流体力学代写
- 辅导代写
- 设计代写
- marketing代写
- web代写
- 计算机代写
- verilog代写
- 心理学代写
- 线性回归代写
- 高级数据分析代写
- clingo代写
- Mplab代写
- coventorware代写
- creo代写
- nosql代写
- 供应链代写
- uml代写
- 数字业务技术代写
- 数字业务管理代写
- 结构分析代写
- tf-idf代写
- 地理代写
- financial modeling代写
- quantlib代写
- 电力电子元件代写
- atenda 2D代写
- 宏观代写
- 媒体代写
- 政治代写
- 化学代写
- 随机过程代写
- self attension算法代写
- arm assembly代写
- wireshark代写
- openCV代写
- Uncertainty Quantificatio代写
- prolong代写
- IPYthon代写
- Digital system design 代写
- julia代写
- Advanced Geotechnical Engineering代写
- 回答问题代写
- junit代写
- solidty代写
- maple代写
- 光电技术代写
- 网页代写
- 网络分析代写
- ENVI代写
- gimp代写
- sfml代写
- 社会学代写
- simulationX solidwork代写
- unity 3D代写
- ansys代写
- react native代写
- Alloy代写
- Applied Matrix代写
- JMP PRO代写
- 微观代写
- 人类健康代写
- 市场代写
- proposal代写
- 软件代写
- 信息检索代写
- 商法代写
- 信号代写
- pycharm代写
- 金融风险管理代写
- 数据可视化代写
- fashion代写
- 加拿大代写
- 经济学代写
- Behavioural Finance代写
- cytoscape代写
- 推荐代写
- 金融经济代写
- optimization代写
- alteryxy代写
- tabluea代写
- sas viya代写
- ads代写
- 实时系统代写
- 药剂学代写
- os代写
- Mathematica代写
- Xcode代写
- Swift代写
- rattle代写
- 人工智能代写
- 流体代写
- 结构力学代写
- Communications代写
- 动物学代写
- 问答代写
- MiKTEX代写
- 图论代写
- 数据科学代写
- 计算机安全代写
- 日本历史代写
- gis代写
- rs代写
- 语言代写
- 电学代写
- flutter代写
- drat代写
- 澳洲代写
- 医药代写
- ox代写
- 营销代写
- pddl代写
- 工程项目代写
- archi代写
- Propositional Logic代写
- 国际财务管理代写
- 高宏代写
- 模型代写
- 润色代写
- 营养学论文代写
- 热力学代写
- Acct代写
- Data Synthesis代写