INFR08010 INFORMATICS 2D: REASONING AND AGENTS 2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
INFR08010 INFORMATICS 2D: REASONING AND AGENTS
2021
1. Search
Consider the search problem described by the state space represented below, where 1 is the initial state, 5 is the only state that satisfies the goal test, the step costs are reported close to the corresponding actions, and values of a heuristic function are shown.
(a) Solve the problem using uniform-cost search strategy and GRAPH-SEARCH.
Report the search tree and the solution found.
(b) Solve the problem using A* search strategy and GRAPH-SEARCH. Report
the search tree and the solution found.
(c) Are these solutions guaranteed to be optimal?
(d) Explain the answer given at point c) in detail, using both the heuristic
function and the solutions found as arguments to support your answer.
(e) Are these search strategies optimal if TREE-SEARCH is used?
2. First-Order Logic (FOL)
(a) Define the syntax of FOL.
(b) Define the models of a given FOL signature.
(c) Give the satisfaction relation for implications and universal quantifications.
(d) Consider FOL without equational atoms. Are there first-order signatures for which every sentence is equivalent to a propositional sentence?
Explain how propositional logic could be seen as a fragment of FOL:
i. For every set of propositional symbols P , define a corresponding FOL signature Σ .
ii. For every propositional sentence for P , show how one can obtain a sentence for Σ .
iii. For every Σ-model M, show how one can define a corresponding valua- tion v for P .
iv. Is it true that a conjunction of literals for P is valid if and only if its corresponding Σ-formula is valid? Justify your answer.
(e) Define the most general unifier.
(f) Give the unification algorithm.
(g) Write a FOL sentence that expresses the following:
Two individuals are friends if and only if they like the same books.
3. Planning and Decision Making
You have a dentist appointment tomorrow. You know that there are two possible appointment times: 11am or 2pm. The actions available to you are:
● To Write down the possible appointment times by 7pm tonight, so you remember what they are.
● To GoEarly to the dentist (i.e., between 10:45am and 11am), in which case you are sure to have your appointment, but may have to wait longer than 1 hour.
● To GoLate to the dentist (i.e., between 1:45pm and 2pm), in which case you might miss your appointment.
If you don’t Write down the possible appointment times, then there is a chance that an external force—let’s call it nature—will make you forget one of them by tomorrow morning.
Assume the following PDDL formulae for describing this situation:
● Tonight means that the current time is before 7pm this evening, EarlyTime means that the current time is between 10:45am and 11am, and LateTime means that the current time is between 1:45pm and 2pm.
● 11am and 2pm mean respectively that the dentist appointment is at 11am, or 2pm.
● The vocabulary includes an operator B for representing belief: if p is a formula, then B(p) is a formula meaning that you believe that p.
● MakeApp means that you make it to your dentist appointment.
● Wait means that you wait longer than an hour for your dentist appointment.
(a) Provide the action descriptions in PDDL for GoEarly and GoLate.
(b) Your goal is to make it your dentist appointment, but not to wait for it.
Write down a description of this goal state.
(c) Using the operator B, write a formula that represents your belief state about the appointment times in the morning, assuming that you performed the Write action the night before. Write also a formula that represents the belief state about the appointment times in the morning, assuming that you did not perform the Write action the night before.
Hint: Use the disjunction symbol A to express alternatives you believe, and
also to express the alternative beliefs you might have.
(d) Suppose you don’t Write down the appointment 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.
(e) The following utility function U over state descriptions captures your pref-
erences:
U (MakeApp V Wait) = 2
U (MakeApp V -Wait) = ·2
U (-MakeApp) = · 10
Furthermore, suppose that there is an even chance that the dentist ap- pointment is at 11am or 2pm. And suppose that not writing down the appointment times results in a 50% chance that you forget one of the times, in which case there is an even chance between forgetting that it might be at 11am, and forgetting that it might be at 2pm. Furthermore, you will GoEarly if and only if you believe there is a chance that the appointment time is at 11am; otherwise you will GoLate.
. 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.
. Why is the plan [Write, GoEarly] of greater utility than the plan [Write, GoLate]?
4. Bayesian Net
Consider the following Bayesian net for five Boolean random variables, A, B , C , D and E .
(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 3 decimal places.
(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 -d |
60 35 |
2 3 |
i. How many samples would we reject from this set?
ii. Assuming that 10 of the remaining samples have E = e, what will our
estimate of P(E[a, d) be?
(c) What is the most likely atomic event that direct sampling will generate? Justify your answer by showing your calculations, highlighting which prob- ability distribution you are sampling from for each variable (and in what
order).
(d) For the query P(C[e, d), compute the weight that would be assigned to the atomic event that you generated via direct sampling in answer to part (c)
using the likelihood weighting method.
2022-08-01