Student Number:
The University of Melbourne Semester 1 Assessment 2022
School of Computing and Information Systems
COMP30024 Artificial Intelligence
Copyright By PowCoder代写 加微信 powcoder
Time for writing and upload: 3 hours 15 minutes. This paper has 14 pages including this cover page. Common Content Papers: None
Authorised Materials: None.
Instructions to Students:
• This paper counts for 70% of your final grade.
• There are 7 questions, with marks as indicated. Attempt all questions.
• Answer all the questions on the exam paper if possible, and then upload the com- pleted exam paper containing your solutions. If you are unable to print the exam paper or electronically edit the exam paper, you may write on your own blank paper and then upload images of your written answers.
• You may upload your exam answers multiple times if you need to revise an answer at any time during the exam.
• You must not communicate with other students or seek assistance from anyone else whilst taking this exam, e.g., using messaging, chat rooms, email, telephone or face- to-face. Also, you must not assist anyone else taking the exam. You must not post answers to the questions or discuss the questions online. Failure to comply with these instructions may be considered as academic misconduct.
• You are free to use the course materials and your laptop/PC in this exam but note that there is a strict time window for the exam hence you should be mindful of the time spent using such resources.
• Answer the questions as clearly and precisely as you can.
• Your writing should be clear. Unreadable answers will be deemed wrong. Excessively
long answers or irrelevant information may be penalised.
• For numerical methods, marks will be given for applying the correct method. Stu- dents will not be heavily penalised for arithmetic errors.
Library: This paper may NOT be reproduced and held by the Baillieu Library.
Page 1 of 14 Please turn over
Question 1 (10 marks) [Write your answers on this page]
Question (a) (b) (c) (d) (e) Answer
(a) A* search is applied to a finite search tree with branching factor b and depth d using an admissible heuristic h(n) that estimates the cost of reaching the goal from a node n. Assume that h∗(n) is the true cost of reaching the goal from a node n. If h(n) = h∗(n), how many nodes would be expanded using A* search? (Note that a node is expanded when it is removed from the queue of nodes used by the search algorithm, and its successor nodes are generated, if any.)
4. None of the above
(b) Which of the following is the most accurate summary of the limitations of the Turing test?
1. It does not test language understanding
2. It is not reproducible
3. It is too easy to pass
4. All of the above
(c) Which one of the following statements is true about the effect of the choice of evaluation function on the behaviour of the Expectiminimax game search algorithm?
1. Behaviour is preserved for any transformation of the evaluation function
2. Behaviour is preserved only for any positive transformation of the evaluation function
3. Behaviour is preserved only for any positive linear transformation of the evaluation function
4. None of the above
(d) X, Y and Z are Boolean random variables, and D is a random variable whose domain is {d1,d2,d3}. What is the minimum number of parameters (i.e., probability values) needed to fully specify the distribution P(x,D|Y,Z)? (Note that x denotes X = True)
4. None of the above
Page 2 of 14 Please turn over
Question 1 (continued)
(e) Figure 1-1 shows a robot arm that is made up of two sections Arm1 and Arm2. Arm1 can rotate around the shoulder joint A, while Arm2 is connected to Arm1 at the elbow joint B, and can rotate around the joint B. The configuration of the robot arm can be specified by the angle θ1 between the horizontal axis and Arm1, and the angle θ2 between Arm1 and Arm2. Both angles are measured in radians. There is also one fixed obstacle shown, which restricts the movement of the robot arm.
Figure 1-1
Which of the following four figures best represents the configuration space for this robot? The figures are labelled (1) to (4).
(1) (2) (3) (4)
2π 2π 2π 2π θ2 θ2 θ2 θ2
0 π 2π 0 π 2π 0 π 2π 0 π 2π θ1 θ1 θ1 θ1
Figure 1-2
Page 3 of 14 Please turn over
Question 2 (10 marks) [Write your answers on this page]
For each part of the following question you should write a brief answer in the box provided.
(a) [4 marks] Consider the problem of using machine learning to adjust the weights of an evaluation function for use in game-playing search. Two possible learning approaches to this problem are (1) supervised learning or (2) temporal-difference learning. Briefly explain two reasons why temporal-difference learning is better suited than supervised learning for this task.
(b) [2 marks] Briefly explain how machine learning can be used to improve the efficiency of α-β pruning in game playing search.
(c) [4 marks] In what types of problems can Bidirectional search be applied? Give an example of an application where we can use Bidirectional search and discuss how it satisfies the Bidirectional search’s requirements.
Page 4 of 14 Please turn over
Question 3 (10 marks) [Write your answers on this page]
Consider the 3-ply game tree shown in Figure 3-1. Each node has an identifier (e.g., the root of the tree is node 1; it has three successor nodes 2, 12 and 22), and each terminal node has an associated value (e.g., the value of node 4 is 4).
3 6 9 13 16
19 23 26 29
4 5 7 8 10 11 14 15 17 18 20 21 24 25 27 28
VALUE 4 7 1 2 5 6 0 8 5 3 9 7 6 2 4 1 6 6
Figure 3-1
In the following questions, you are NOT required to redraw the search tree in your answer. (a) [1 mark] What is the minimax value at node 1 after applying the minimax algorithm
to this search tree?
(b) [4 marks] If the nodes are examined in the order shown by the identifier in each node in Figure 3-1, which nodes would be pruned if alpha-beta pruning is used? For each node that would be pruned, place a cross in the corresponding box below.
Node 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Pruned
Node 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Pruned
(c) [3 marks] If we come up with the perfect ordering of the nodes, what is the maximum
number of nodes that we can prune?
Page 5 of 14 Please turn over
Question 3 (continued) [Write your answers on this page]
(d) [2 marks] Suppose you have made a large batch of images (as GIF files) that you want to sell as Non-fungible tokens (NFTs) on OpenSea. You know that the work is reproducible so you want to sell as many as you can as fast as you can.
Which auction model would you choose? What are the pros and cons of your method. Briefly justify your answer.
Page 6 of 14 Please turn over
Question 4 (10 marks) [Write your answers on this page]
Consider a tourist who is visiting Melbourne. The tourist has heard about the great food in Melbourne, and she wants to visit a cafe for a coffee and a bakery for a cake. The tourist is given a map, which divides Melbourne city into a grid, where the grid is N cells wide and M cells high. Each cell can be empty, contain a cafe, or contain a bakery (but not both). There are C ≥ 1 cells with a cafe, and B ≥ 1 cells with a bakery.
The tourist starts in an initial cell, and needs to find the shortest possible tour that will visit one cafe and one bakery (in either order). The tour ends when the tourist has visited one cafe and one bakery. At each step, the tourist can perform one of four different actions: move up, down, left or right. The tourist cannot move off the edge of the map, can visit the same cell multiple times if necessary, and can visit more than one bakery or cafe if necessary. To complicate matters, some cells are blocked off and cannot be visited, i.e., the tourist cannot move into a blocked off cell.
Figure 4-1 below shows a map for an instance of the problem comprising a grid where N=5,M=4,C=3andB=3. Therearefourcellsinthisexamplemapthatare blocked off (shown in black). The starting location of the tourist in this instance of the problem is shown by the symbol T.
Figure 4-1
(a) [2 marks] Give a tight upper bound on the size of the state space of the problem in general, and briefly justify your answer.
(Note: your answer should be a general expression in terms of N and M, it should include any constant terms, and you can assume the locations of the cafes and bakeries are fixed)
Page 7 of 14 Please turn over
Question 4 (continued) [Write your answers on this page]
(b) [2 marks] Give a tight upper bound on the branching factor of the search problem in general, and briefly justify your answer.
(c) [6 marks] For each of the following three heuristics, state whether it is admissible or not admissible, and briefly justify your answer in each case.
• Heuristic 1: The number of remaining cafes and bakeries that have not been visited.
• Heuristic 2: The smallest Manhattan distance to any remaining cafe or bakery that
has not been visited, or zero if the tourist is in a goal state.
• Heuristic 3: The maximum Manhattan distance between any two of the remaining cafes or bakeries that have not been visited. For example, if there is one remaining cafe C1 and two remaining bakeries B1 and B2, there are three possible distances.
Page 8 of 14 Please turn over
Question 5 (10 marks) [Write your answers on this page]
Qantas Melbourne has hired three new pilots (PA, PB and PC) and has to determine which pilot will take care of which flights on a given day (24h shift). Each pilot can only travel once per half-day and only once at night. The same pilot can fly an AM shift and successive PM or overnight (ON) shift, provided the mid-point is the same location.
We provide the list flights below. The flights are:
• F1 – Melbourne- M • F2 – Melbourne-Adelaide AM • F3 – Melbourne-Brisbane PM • F4 – Sydney-Melbourne AM • F5 – Sydney-Adelaide PM
• F6 – Sydney-Melbourne ON
• F7 – Adelaide-Melbourne ON
Note that we are looking at scheduling all these flights in a single day.
(a) [4 marks] Formulate this as a Constraint Satisfaction Problem (CSP) in which there is one variable per flight. State the variables and their domains, and the constraints. Constraints should be specified formally and precisely.
(b) [2 marks] Draw the constraint graph associated with your CSP.
Page 9 of 14 Please turn over
Question 5 (continued) [Write your answers on this page]
(c) [2 marks] Show the domains of the variables after running arc-consistency on this initial graph (after having already enforced any unary constraints).
(d) [2 marks] Give one solution to this CSP.
Page 10 of 14 Please turn over
Question 6 (10 marks) [Write your answers on this page]
Two drones observe the same part of a nature reserve from two different angles and make measurements M1 and M2 of the number of zebras N in a small region of the African savanna, each using a thermal camera. Normally, there is a small probability e of error by up to one zebra in each direction. Each thermal camera can also (with a much smaller probability f) be out of calibration (events C1 and C2), in which case the drones will undercount by three or more zebras (or if N is less than 3, fail to detect any zebra at all).
(a) [2 marks] Consider the three networks shown in the Figure 6-1 below. Which of these Bayesian networks are correct (but not necessarily efficient) representations of the preceding information? Which is the best network? Explain briefly.
Figure 6-1 Possible networks.
(b) [3 marks] Write out a conditional distribution for P(M1 = 0|N = 1). The conditional distribution should be expressed as a function of the parameters e and/or f.
Page 11 of 14 Please turn over
Question 6 (continued) [Write your answers on this page]
(c) [2 marks] Suppose M1 = 3 and M2 = 1. What are the possible numbers of zebras if you assume no prior constraint on the values of N?
(d) [3 marks] What is the most likely number of zebras, given these observations? Ex- plain how to compute this, or if it is not possible to compute, explain what additional information is needed and how it would affect the result.
Page 12 of 14 Please turn over
Question 7 (10 marks) [Write your answers on this page]
Schrodinger would like to know if his cat stays in the house at night. Every day, he observes whether the cat’s bowl still contains food and if the litter box was used. We can assume the following:
– The prior probability of the cat staying in the house at night with no observations, is 0.8.
– The probability of the litter box being used is 0.6 if the cat was in the house at night, and 0.2 if not.
– The probability of the bowl of food being full is 0.3 if a cat was in the house, and 0.5 if not.
(a) [2 marks] Formulate this information as a Bayesian Belief Network that Schrodinger could use to infer if his cat ran away based on his observations. Provide the diagram.
(b) [3 marks] Give the complete probability tables for the model.
Page 13 of 14 Please turn over
Question 7 (continued) [Write your answers on this page]
(c) [2 marks] Over three nights, Schrodinger notes down the following observations:
Night Bowl 1 Empty 2 Empty 3 Full
Litter Box Used Not Used Not Used
Compute the probability of the cat staying in the house for each of these nights in turn given the successive observations.
(d) [3 marks] Schrodinger wants to investigate the potential reasons for his cat running away at night and he considers the following two options:
– A possum scares his cat. The prior probability of this event is 0.1.
– A neighbour keeps the cat at night. The prior probability of this event is 0.3.
With this update of the belief network, compute the probability of the neighbour keeping the cat given that the bowl is empty and that the litter box hasn’t been used.
Page 14 of 14 End of Exam
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com