INFR08010 INFORMATICS 2D: REASONING AND AGENTS
INFORMATICS 2D: REASONING AND AGENTS
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
FOR INTERNAL SCRUTINY
COLLEGE OF SCIENCE AND ENGINEERING
SCHOOL OF INFORMATICS
INFR08010 INFORMATICS 2D: REASONING AND AGENTS
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.
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 ]