xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

微信客服：xiaoxionga100

微信客服：ITCS521

reasoning and agents代写-INFR08010

时间：2021-04-20

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

UNIVERSITY OF EDINBURGH

COLLEGE OF SCIENCE AND ENGINEERING

SCHOOL OF INFORMATICS

INFR08010 INFORMATICS 2D: REASONING AND AGENTS

Saturday 18 th May 2019

09:30 to 11: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: D.K.Arvind

External Examiner: J.Gibbons

THIS EXAMINATION WILL BE MARKED ANONYMOUSLY

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

Part A

ANSWER ALL QUESTIONS IN PART A. Use the special mark sheet.

1. Which of the following does not describe utility-based agents?

(a) optimizes utilities over a range of goals

(b) a measure of goodness is needed

(c) may use probability theory

(d) agent may be juggling conflicting goals

(e) actions only depend on immediate percepts

2. Which of the following leads to an exploration problem during search?

(a) deterministic, fully observable environments

(b) unknown state space

(c) nondeterministic, fully observable environments

(d) deterministic conformant problems

(e) nondeterministic conformant problems

3. Which of the following is not correct? (Here, as in the lectures, b is maximum

branching factor of search tree, d is depth of least-cost solution, and m is maxi-

mum depth of the state space.)

(a) Breath-first search has time complexity O(bd)

(b) Breath-first search has space complexity O(bd)

(c) Depth-first search is complete with finite depth

(d) Depth-first search has time complexity O(bm)

(e) Depth-first search has space complexity O(bm)

4. Which of the following statements about Minimax search is not correct?

(a) If tree is finite, it is complete

(b) It has time complexity O(bm)

(c) α− β pruning does not affect final result

(d) Space complexity is O(bm)

(e) Move ordering may affect the effectiveness of pruning

Page 1 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

5. In A∗ search, the evaluation function for a node n is f(n) = g(n) + h(n). Which

of the following statements is not correct?

(a) h(n) is admissible if and only if h(n) ≤ g(n)

(b) for admissible heuristic h(n), A∗ using TREE-SEARCH is optimal

(c) f(n) should never overestimate the true cost of the solution

(d) h(n) is the estimated cost from n to the goal

(e) A∗ needs exponential time

6. Consider the propositional logic symbols A,B,C. Which of the following state-

ments is not correct?

(a) (A⇒ B) ∧ C is equivalent to C ∧ (¬B ⇒ ¬A)

(b) ((B ∨ C) ∧ ¬A) ∧B is satisfiable

(c) C ∧ (B ∨ A) is equivalent to (B ∧ C) ∨ (A ∧ C)

(d) (A⇒ B) ∨ ¬(¬B ⇒ ¬A) is valid

(e) (A⇒ B) ∧ C is equivalent to (A⇒ C) ∧ (¬B ⇒ C)

7. Which of the following is not correct of the DPLL algorithm as given in the

lectures?

(a) sentence is false if any of the clauses is false

(b) pure symbol heuristic identifies propositions that appear with alternating

polarities in clauses

(c) unit clauses are processed by making the corresponding remaining literal

true

(d) sentences are in conjunctive normal form

(e) a sentence is false if all of its clauses are false

8. Consider a constraint satisfaction problem with variablesA ∈ {0, 1}, B ∈ {0, 1}, C ∈

{0, 1, 2} and constraints A = 1 − B, C ≤ A. Which of the following statements

is not correct?

(a) The most constraining variable is A

(b) The least constraining value of A is 1

(c) The least constraining value of C is 2

(d) A→ B is consistent

(e) B → A is consistent

Page 2 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

9. Which of the following is a unifier of A(x, y) ∧ B(x) ∧ C(y) and a ∧ b ∧ C(a)?

(Note that x, y, a, b are all variables.)

(a) {a/A(x, y), b/B(x), a/y}

(b) {a/y}

(c) {a/A(x, y), b/B(x)}

(d) {b/B(x)}

(e) None of the above

10. Which of the following are specified by “successor state axioms” in the situation

calculus?

(a) Conditions for efficiency when planning

(b) Future ramifications of actions

(c) The conditions under which fluents are unaffected

(d) The conditions that make the fluent true and the conditions that make the

fluent false

(e) The preconditions and sensing percepts

11. Given the action schema

Action(Put(x, y),

Precond:Block(x), Block(y), InHand(x), Clear(y)

Effect:on(x, y),¬Clear(y),¬InHand(x))

how many executable actions are there in the following state?

on(A,B), InHand(A),Block(C ),Block(D),Block(E ),

on(D ,E ), InHand(C ),Clear(D)

(a) 1

(b) 2

(c) 4

(d) 6

(e) 8

Page 3 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

12. Which of the following statements is incorrect?

(a) Unlike problem-solving agents based on heuristic search, planning agents

avoid the problem of having to define heuristic values for every possible

state.

(b) Problem-solving agents based on search will often explore irrelevant actions.

(c) Search-based agents may consider undoing the effects of actions achieved by

previous actions.

(d) Partial-order planning ensures that the agent does not commit to overly

restrictive courses of execution at the time of planning.

(e) State-space search based planning methods are never goal-directed.

13. Assume that you have to add an action D with postconditions p and q in a

plan with the existing causal links A

¬p→ B and B ¬q→ C. Which of the following

orderings resolves all conflicts that might arise from adding the action D to the

partial order plan?

(a) A ≺ B ≺ D ≺ C

(b) A ≺ D ≺ B ≺ C

(c) A ≺ B ≺ C ≺ D

(d) D ≺ A ≺ C ≺ B

(e) A ≺ C ≺ D ≺ B

14. You are given four action descriptions:

Action(A,Precond:{X},Effect:{(when P : ¬X), Z})

Action(B,Precond:{Y },Effect:{(when Z : ¬P ),¬Y,¬Z,X})

Action(C,Precond:{¬X},Effect:{(when Q : X)})

Action(D,Precond:{Z},Effect:{(when Q : ¬Z)})

What state would result from executing the action sequence [D,C,A,B,A] in

the state {P,Q, Y, Z}?

(a) {P,Q, Y }

(b) {P,Q, Y, Z}

(c) {Q,X,Z}

(d) The plan isn’t executable because the preconditions for action C aren’t met.

(e) The plan isn’t executable because the preconditions for action B aren’t met.

Page 4 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

15. A house has 2 rooms, and the robot moves from one room to the other, cleaning

each room. It can sense its location and whether the room it is currently in is

currently clean or dirty. Sometimes when it cleans, its filter deposits dirt onto

the floor. Moreover, rooms sometimes get dusty from the airconditioning system

that runs throughout the house.

Which of the following statements is incorrect?

(a) The robot is working in a partially observable environment.

(b) The robot can use contingent planning to clean the room it’s in.

(c) A plan to clean a particular room in the house includes a loop.

(d) It is impossible for the robot to guarantee that it has achieved the goal of

making each room in the house clean.

(e) The robot must use replanning to clean a room in the house.

The following table specifies a joint probability distribution for three Boolean

random variables X , Y , Z that will be used for questions 16 and 17.

x ¬x

y ¬y y ¬y

z a b c d

¬z e f g h

16. Which of the following statements is incorrect?

(a) P(X) = 〈a+ b+ e+ f, c+ d+ g + h〉

(b) P (z|y) = (a+ c)/(a+ c+ e+ g)

(c) If Z and Y are conditionally independent, then (a+b+c+d) = (a+c)/(a+

e+ c+ g) holds

(d) P (¬x|y) = c+ g

(e) P (x ∧ y ∧ ¬z) = e

17. Which of the following is the correct value for P (z ∧ ¬x)?

(a) 1/(c+ d)

(b) (c+ d)/(c+ d+ g + h)

(c) c/(c+ d)

(d) c+ d

(e) 〈c/(c+ d), d/(c+ d)〉

Page 5 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

18. Assume the following inhibition probabilities between Boolean cause variables

Poor , Healthydiet , Exercise and Boolean effect variable Slim:

P (¬slim|poor ,¬healthydiet ,¬exercise) = 0.2

P (¬slim|¬poor , healthydiet ,¬exercise) = 0.5

P (¬slim|¬poor ,¬healthydiet , exercise) = 0.5

What is the probability P (slim|poor , healthydiet ,¬exercise) assuming that the

conditional probabilities of Slim are computed using a noisy-OR relation?

(a) 0.1

(b) 0.25

(c) 0.4

(d) 0.95

(e) 0.9

19. 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 a

valid axiom of utility theory?

(a) (A B) ∨ (B A) ∨ (A ∼ B)

(b) (A B) ∧ (B C)⇒ (A C)

(c) A ∼ B ⇒ [p,A; 1− p, C] [p,B; 1− p, C]

(d) A B C ⇒ ∃p [p,A; 1− p, C] ∼ B

(e) A B ⇒ (p ≥ q ⇔ [p,A; 1− p,B] % [q, A; 1− q, B])

20. Imagine the UK is preparing for the outbreak of an unusual disease. With no

treatment, it is expected to kill 600 people. If they adopt Programme A for

combating the disease, then 400 people will die. If they adopt Programme B,

then there is a 1

3

chance that no one will die and a 2

3

chance that 600 people will

die.

What should a rational agent do?

(a) Take no action.

(b) Adopt Programme A.

(c) Adopt Programme B.

(d) You can choose to adopt either Programme A or B because their expected

utility is the same.

(e) It is impossible to say without knowing more about the utility function for

people dying (or surviving).

Page 6 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

Part B

ANSWER ONE QUESTION FROM PART B

1. Propositional Logic

(a) What are knowledge bases, and what are the key features? [3 marks ]

(b) Give the semantics for ¬,∧,⇒,⇔. [3 marks ]

(c) Give the conjunctive normal form equivalent for (A⇒ B) ∧ (¬C ⇔ B). [2 marks ]

(d) Is (A⇒ B) valid? Explain your answer. [1 mark ]

(e) Give the DPLL algorithm as introduced in the lectures. [5 marks ]

(f) Describe the three heuristics used in DPLL. Explain how they work by

means of examples. [5 marks ]

(g) Apply DPLL to the CNF obtained in (c), and give a model if one exists. [3 marks ]

(h) What are the properties of the WALKSAT algorithm? What is the key

difference to DPLL in terms of correctness? [3 marks ]

Page 7 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

2. First-Order Logic (FOL)

(a) Give the pros and cons of propositional logic, and explain the underlying

features of FOL that improves on propositional logic? [4 marks ]

(b) Define the atomic and complex formulas in FOL. [2 marks ]

(c) Give the semantics of FOL. [3 marks ]

(d) In the context of entailment in FOL, explain universal and existential in-

stantiation and provide examples for both of them. [4 marks ]

(e) Provide the statement and explain the motivation behind Herbrand’s theo-

rem. Sketch an algorithm for applying this theorem. What is the Church-

Turing thesis, and how does it relate to the theorem? [5 marks ]

(f) What are the two key problems with the propositionalization of a first-order

knowledge base? [2 marks ]

(g) Give the forward chaining algorithm. [5 marks ]

Page 8 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

Part C

ANSWER ONE QUESTION FROM PART C

1. Planning

An agent has a large supply of eggs and its goal is to get the contents of (at

least) two good eggs and no bad ones into one of two bowls. Each egg is good

with a probability of 50%. The agent can Break an unbroken egg, and empty its

contents into one of the bowls (this is one action execution); it can Transfer all

the contents of a bowl into another bowl or into a garbage can; and it can Smell

the bowl, in order to find out whether its contents contains only good eggs.

Answer the questions using the following vocabulary:

good(x): All the contents of the eggs in x is good

egg(x ): x is an egg

broken(x ): x is a broken egg

bowl(x ): x is a bowl

garbage(x ): x is a garbage can

contents(x , y) The egg x contains (yolk and egg white) y

in(x , y): x is in (bowl or garbage can) y

(a) Define the goal state.

Hint: you can use inequality. [4 marks ]

(b) Define the following actions and percepts in PDDL so that they match the

above informal descriptions:

i. The action Break

ii. The action Transfer

iii. The percept Smell, where you find out whether a bowl contains the

contents of only good eggs. [9 marks ]

(c) What kind of planning is relevant for solving the planning problem? Explain

your answer. [2 marks ]

(d) Using your choice of planning technique from part (c) and your action de-

scriptions from part (b), write a plan for reaching the goal state defined in

part (a).

Hint: Refer to the two bowls as B1 and B2, to the garbage can as G and

use variables to refer to the eggs, so as to express free choice on which eggs

you use next. [8 marks ]

(e) Does your plan guarantee that the goal state will (eventually) be reached?

Explain your answer. [2 marks ]

Page 9 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

2. Inference in Bayesian Networks

You are given the following Bayesian network with conditional probability tables

(CPTs) for five Boolean random variables A, B, C, D, and E:

E

BA

D

C

C P (d)

F 0.2

T 0.5

C P (e)

F 0.6

T 0.3

P (b) 0.7P (a) 0.2

A B P (c)

F F 0.4

T F 0.1

F T 0.3

T T 0.5

(a) Calculate P (a|e, d). You are expected to produce a formula for calculating

this that simplifies the initial “inference by enumeration” formula as much

as possible. Numerical probabilities should not be used to replace symbolic

values until they can be identified directly from the CPTs (unless it becomes

obvious in the process that some sub-term in your calculation is 0). Your

answer need not compute the numeric value of the normalising factor α =

1

P (e,d)

(i.e., express your final answer as a numeric multiple of α). [12 marks ]

(b) Using direct sampling, what is the most likely atomic event that you would

generate? Where there’s a tie when sampling a value for a boolean variable

X, assume that sampling produces X = true. [3 marks ]

(c) For query P(C|e, d) compute the weight that would be assigned to the sam-

ple you generated from part (b) if we used the likelihood weighting method.

[6 marks ]

(d) Assume that to estimate P(E|a, d) using rejection sampling we have gen-

erated 100 samples with the following results for a and d (each table entry

shows the number of samples for which the two variables had the respective

value):

a ¬a

d 60 2

¬d 35 3

Page 10 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

How many samples would we reject from this set? Assuming that 10 of the

remaining samples have E = e, what will our estimate of P(E|a, d) be? [4 marks ]

Page 11 of 11

学霸联盟

UNIVERSITY OF EDINBURGH

COLLEGE OF SCIENCE AND ENGINEERING

SCHOOL OF INFORMATICS

INFR08010 INFORMATICS 2D: REASONING AND AGENTS

Saturday 18 th May 2019

09:30 to 11: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: D.K.Arvind

External Examiner: J.Gibbons

THIS EXAMINATION WILL BE MARKED ANONYMOUSLY

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

Part A

ANSWER ALL QUESTIONS IN PART A. Use the special mark sheet.

1. Which of the following does not describe utility-based agents?

(a) optimizes utilities over a range of goals

(b) a measure of goodness is needed

(c) may use probability theory

(d) agent may be juggling conflicting goals

(e) actions only depend on immediate percepts

2. Which of the following leads to an exploration problem during search?

(a) deterministic, fully observable environments

(b) unknown state space

(c) nondeterministic, fully observable environments

(d) deterministic conformant problems

(e) nondeterministic conformant problems

3. Which of the following is not correct? (Here, as in the lectures, b is maximum

branching factor of search tree, d is depth of least-cost solution, and m is maxi-

mum depth of the state space.)

(a) Breath-first search has time complexity O(bd)

(b) Breath-first search has space complexity O(bd)

(c) Depth-first search is complete with finite depth

(d) Depth-first search has time complexity O(bm)

(e) Depth-first search has space complexity O(bm)

4. Which of the following statements about Minimax search is not correct?

(a) If tree is finite, it is complete

(b) It has time complexity O(bm)

(c) α− β pruning does not affect final result

(d) Space complexity is O(bm)

(e) Move ordering may affect the effectiveness of pruning

Page 1 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

5. In A∗ search, the evaluation function for a node n is f(n) = g(n) + h(n). Which

of the following statements is not correct?

(a) h(n) is admissible if and only if h(n) ≤ g(n)

(b) for admissible heuristic h(n), A∗ using TREE-SEARCH is optimal

(c) f(n) should never overestimate the true cost of the solution

(d) h(n) is the estimated cost from n to the goal

(e) A∗ needs exponential time

6. Consider the propositional logic symbols A,B,C. Which of the following state-

ments is not correct?

(a) (A⇒ B) ∧ C is equivalent to C ∧ (¬B ⇒ ¬A)

(b) ((B ∨ C) ∧ ¬A) ∧B is satisfiable

(c) C ∧ (B ∨ A) is equivalent to (B ∧ C) ∨ (A ∧ C)

(d) (A⇒ B) ∨ ¬(¬B ⇒ ¬A) is valid

(e) (A⇒ B) ∧ C is equivalent to (A⇒ C) ∧ (¬B ⇒ C)

7. Which of the following is not correct of the DPLL algorithm as given in the

lectures?

(a) sentence is false if any of the clauses is false

(b) pure symbol heuristic identifies propositions that appear with alternating

polarities in clauses

(c) unit clauses are processed by making the corresponding remaining literal

true

(d) sentences are in conjunctive normal form

(e) a sentence is false if all of its clauses are false

8. Consider a constraint satisfaction problem with variablesA ∈ {0, 1}, B ∈ {0, 1}, C ∈

{0, 1, 2} and constraints A = 1 − B, C ≤ A. Which of the following statements

is not correct?

(a) The most constraining variable is A

(b) The least constraining value of A is 1

(c) The least constraining value of C is 2

(d) A→ B is consistent

(e) B → A is consistent

Page 2 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

9. Which of the following is a unifier of A(x, y) ∧ B(x) ∧ C(y) and a ∧ b ∧ C(a)?

(Note that x, y, a, b are all variables.)

(a) {a/A(x, y), b/B(x), a/y}

(b) {a/y}

(c) {a/A(x, y), b/B(x)}

(d) {b/B(x)}

(e) None of the above

10. Which of the following are specified by “successor state axioms” in the situation

calculus?

(a) Conditions for efficiency when planning

(b) Future ramifications of actions

(c) The conditions under which fluents are unaffected

(d) The conditions that make the fluent true and the conditions that make the

fluent false

(e) The preconditions and sensing percepts

11. Given the action schema

Action(Put(x, y),

Precond:Block(x), Block(y), InHand(x), Clear(y)

Effect:on(x, y),¬Clear(y),¬InHand(x))

how many executable actions are there in the following state?

on(A,B), InHand(A),Block(C ),Block(D),Block(E ),

on(D ,E ), InHand(C ),Clear(D)

(a) 1

(b) 2

(c) 4

(d) 6

(e) 8

Page 3 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

12. Which of the following statements is incorrect?

(a) Unlike problem-solving agents based on heuristic search, planning agents

avoid the problem of having to define heuristic values for every possible

state.

(b) Problem-solving agents based on search will often explore irrelevant actions.

(c) Search-based agents may consider undoing the effects of actions achieved by

previous actions.

(d) Partial-order planning ensures that the agent does not commit to overly

restrictive courses of execution at the time of planning.

(e) State-space search based planning methods are never goal-directed.

13. Assume that you have to add an action D with postconditions p and q in a

plan with the existing causal links A

¬p→ B and B ¬q→ C. Which of the following

orderings resolves all conflicts that might arise from adding the action D to the

partial order plan?

(a) A ≺ B ≺ D ≺ C

(b) A ≺ D ≺ B ≺ C

(c) A ≺ B ≺ C ≺ D

(d) D ≺ A ≺ C ≺ B

(e) A ≺ C ≺ D ≺ B

14. You are given four action descriptions:

Action(A,Precond:{X},Effect:{(when P : ¬X), Z})

Action(B,Precond:{Y },Effect:{(when Z : ¬P ),¬Y,¬Z,X})

Action(C,Precond:{¬X},Effect:{(when Q : X)})

Action(D,Precond:{Z},Effect:{(when Q : ¬Z)})

What state would result from executing the action sequence [D,C,A,B,A] in

the state {P,Q, Y, Z}?

(a) {P,Q, Y }

(b) {P,Q, Y, Z}

(c) {Q,X,Z}

(d) The plan isn’t executable because the preconditions for action C aren’t met.

(e) The plan isn’t executable because the preconditions for action B aren’t met.

Page 4 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

15. A house has 2 rooms, and the robot moves from one room to the other, cleaning

each room. It can sense its location and whether the room it is currently in is

currently clean or dirty. Sometimes when it cleans, its filter deposits dirt onto

the floor. Moreover, rooms sometimes get dusty from the airconditioning system

that runs throughout the house.

Which of the following statements is incorrect?

(a) The robot is working in a partially observable environment.

(b) The robot can use contingent planning to clean the room it’s in.

(c) A plan to clean a particular room in the house includes a loop.

(d) It is impossible for the robot to guarantee that it has achieved the goal of

making each room in the house clean.

(e) The robot must use replanning to clean a room in the house.

The following table specifies a joint probability distribution for three Boolean

random variables X , Y , Z that will be used for questions 16 and 17.

x ¬x

y ¬y y ¬y

z a b c d

¬z e f g h

16. Which of the following statements is incorrect?

(a) P(X) = 〈a+ b+ e+ f, c+ d+ g + h〉

(b) P (z|y) = (a+ c)/(a+ c+ e+ g)

(c) If Z and Y are conditionally independent, then (a+b+c+d) = (a+c)/(a+

e+ c+ g) holds

(d) P (¬x|y) = c+ g

(e) P (x ∧ y ∧ ¬z) = e

17. Which of the following is the correct value for P (z ∧ ¬x)?

(a) 1/(c+ d)

(b) (c+ d)/(c+ d+ g + h)

(c) c/(c+ d)

(d) c+ d

(e) 〈c/(c+ d), d/(c+ d)〉

Page 5 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

18. Assume the following inhibition probabilities between Boolean cause variables

Poor , Healthydiet , Exercise and Boolean effect variable Slim:

P (¬slim|poor ,¬healthydiet ,¬exercise) = 0.2

P (¬slim|¬poor , healthydiet ,¬exercise) = 0.5

P (¬slim|¬poor ,¬healthydiet , exercise) = 0.5

What is the probability P (slim|poor , healthydiet ,¬exercise) assuming that the

conditional probabilities of Slim are computed using a noisy-OR relation?

(a) 0.1

(b) 0.25

(c) 0.4

(d) 0.95

(e) 0.9

19. 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 a

valid axiom of utility theory?

(a) (A B) ∨ (B A) ∨ (A ∼ B)

(b) (A B) ∧ (B C)⇒ (A C)

(c) A ∼ B ⇒ [p,A; 1− p, C] [p,B; 1− p, C]

(d) A B C ⇒ ∃p [p,A; 1− p, C] ∼ B

(e) A B ⇒ (p ≥ q ⇔ [p,A; 1− p,B] % [q, A; 1− q, B])

20. Imagine the UK is preparing for the outbreak of an unusual disease. With no

treatment, it is expected to kill 600 people. If they adopt Programme A for

combating the disease, then 400 people will die. If they adopt Programme B,

then there is a 1

3

chance that no one will die and a 2

3

chance that 600 people will

die.

What should a rational agent do?

(a) Take no action.

(b) Adopt Programme A.

(c) Adopt Programme B.

(d) You can choose to adopt either Programme A or B because their expected

utility is the same.

(e) It is impossible to say without knowing more about the utility function for

people dying (or surviving).

Page 6 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

Part B

ANSWER ONE QUESTION FROM PART B

1. Propositional Logic

(a) What are knowledge bases, and what are the key features? [3 marks ]

(b) Give the semantics for ¬,∧,⇒,⇔. [3 marks ]

(c) Give the conjunctive normal form equivalent for (A⇒ B) ∧ (¬C ⇔ B). [2 marks ]

(d) Is (A⇒ B) valid? Explain your answer. [1 mark ]

(e) Give the DPLL algorithm as introduced in the lectures. [5 marks ]

(f) Describe the three heuristics used in DPLL. Explain how they work by

means of examples. [5 marks ]

(g) Apply DPLL to the CNF obtained in (c), and give a model if one exists. [3 marks ]

(h) What are the properties of the WALKSAT algorithm? What is the key

difference to DPLL in terms of correctness? [3 marks ]

Page 7 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

2. First-Order Logic (FOL)

(a) Give the pros and cons of propositional logic, and explain the underlying

features of FOL that improves on propositional logic? [4 marks ]

(b) Define the atomic and complex formulas in FOL. [2 marks ]

(c) Give the semantics of FOL. [3 marks ]

(d) In the context of entailment in FOL, explain universal and existential in-

stantiation and provide examples for both of them. [4 marks ]

(e) Provide the statement and explain the motivation behind Herbrand’s theo-

rem. Sketch an algorithm for applying this theorem. What is the Church-

Turing thesis, and how does it relate to the theorem? [5 marks ]

(f) What are the two key problems with the propositionalization of a first-order

knowledge base? [2 marks ]

(g) Give the forward chaining algorithm. [5 marks ]

Page 8 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

Part C

ANSWER ONE QUESTION FROM PART C

1. Planning

An agent has a large supply of eggs and its goal is to get the contents of (at

least) two good eggs and no bad ones into one of two bowls. Each egg is good

with a probability of 50%. The agent can Break an unbroken egg, and empty its

contents into one of the bowls (this is one action execution); it can Transfer all

the contents of a bowl into another bowl or into a garbage can; and it can Smell

the bowl, in order to find out whether its contents contains only good eggs.

Answer the questions using the following vocabulary:

good(x): All the contents of the eggs in x is good

egg(x ): x is an egg

broken(x ): x is a broken egg

bowl(x ): x is a bowl

garbage(x ): x is a garbage can

contents(x , y) The egg x contains (yolk and egg white) y

in(x , y): x is in (bowl or garbage can) y

(a) Define the goal state.

Hint: you can use inequality. [4 marks ]

(b) Define the following actions and percepts in PDDL so that they match the

above informal descriptions:

i. The action Break

ii. The action Transfer

iii. The percept Smell, where you find out whether a bowl contains the

contents of only good eggs. [9 marks ]

(c) What kind of planning is relevant for solving the planning problem? Explain

your answer. [2 marks ]

(d) Using your choice of planning technique from part (c) and your action de-

scriptions from part (b), write a plan for reaching the goal state defined in

part (a).

Hint: Refer to the two bowls as B1 and B2, to the garbage can as G and

use variables to refer to the eggs, so as to express free choice on which eggs

you use next. [8 marks ]

(e) Does your plan guarantee that the goal state will (eventually) be reached?

Explain your answer. [2 marks ]

Page 9 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

2. Inference in Bayesian Networks

You are given the following Bayesian network with conditional probability tables

(CPTs) for five Boolean random variables A, B, C, D, and E:

E

BA

D

C

C P (d)

F 0.2

T 0.5

C P (e)

F 0.6

T 0.3

P (b) 0.7P (a) 0.2

A B P (c)

F F 0.4

T F 0.1

F T 0.3

T T 0.5

(a) Calculate P (a|e, d). You are expected to produce a formula for calculating

this that simplifies the initial “inference by enumeration” formula as much

as possible. Numerical probabilities should not be used to replace symbolic

values until they can be identified directly from the CPTs (unless it becomes

obvious in the process that some sub-term in your calculation is 0). Your

answer need not compute the numeric value of the normalising factor α =

1

P (e,d)

(i.e., express your final answer as a numeric multiple of α). [12 marks ]

(b) Using direct sampling, what is the most likely atomic event that you would

generate? Where there’s a tie when sampling a value for a boolean variable

X, assume that sampling produces X = true. [3 marks ]

(c) For query P(C|e, d) compute the weight that would be assigned to the sam-

ple you generated from part (b) if we used the likelihood weighting method.

[6 marks ]

(d) Assume that to estimate P(E|a, d) using rejection sampling we have gen-

erated 100 samples with the following results for a and d (each table entry

shows the number of samples for which the two variables had the respective

value):

a ¬a

d 60 2

¬d 35 3

Page 10 of 11

FOR INTERNAL SCRUTINY (date of this version: 4/2/2019)

How many samples would we reject from this set? Assuming that 10 of the

remaining samples have E = e, what will our estimate of P(E|a, d) be? [4 marks ]

Page 11 of 11

学霸联盟