Computing Science Examination Autumn Semester 2015 CSCU9YE: Artificial Intelligence Date 1.5 hour exam Attempt BOTH questions. Both questions carry equal marks (25 each). The distribution of marks among the parts of each question is indicated. IMPORTANT NOTE Read the instructions on the front of each answer book carefully. It is essential that you write your student number on the front of each answer book. Also, when you have completed the examination, the number of answer books that you have used must be prominently written on the front of one book. COMPUTING SCIENCE & MATHEMATICS 2 CSCU9YE XX December 2015 End/ 1. (a) In the context of Artificial Intelligence, briefly describe: i. What is an agent? ii. What is an uninformed search strategy? Mention two algorithms that use this strategy. [3] [4] (b) (c) Consider an autonomous robot designed for planetary exploration: the Mars rover: i. Describe its design in terms of the four main components of intelligent agents. ii. Describe its environment in terms of two main distinctions or classifications of environments. In the 3-puzzle problem, the board is 2x2 and there are three tiles, numbered A, B, and C, and one blank. The objective of the game is to produce a configuration where the tiles are in consecutive order, with the blank tile in the bottom right. The Start and End states are given below. Start: B C A End: A B C i. Formulate the problem as a search problem indicating the required components. Hint: consider that the actions are to move the white space Right, Left, Up, Down. Of course not all actions are possible from all states. ii. Draw the search tree that would result from expanding 6 nodes (including the start) of the state-space using a Depth-First-Search approach that avoids revisiting states. The actions should be considered in the order (R, L, U, D). As nodes of the tree, draw the state as the 2x2 board with the specific configuration. Label the edges with the action executed. Also enumerate each node with consecutive numbers indicating the sequence of expansion. [4] [4] [4] [6] 3 CSCU9YE XX December 2015 End/ 2. (a) (b) (c) In the context of local search and evolutionary algorithms, briefly describe: i. What is a search space? Give an example of a search space. ii. What is a neighbourhood? Give an example of a neighbourhood. As the logistics manager in a supermarket, you need to coordinate the home delivery of shopping baskets to 10 clients. Consider that you have a single van and the 10 shopping baskets fit in it. You have the addresses of the 10 clients. Your job is to deliver all the orders and return to your base. Formulate this as an optimisation problem indicating: i. How will you encode a solution to the problem and how will this be interpreted? ii. What will be the fitness function and how will you implement it? Consider the data below for training a cleaning robot. The robot needs to decide to which rooms to go for collecting recycled paper. Assume that an indication of the information gain of each attribute is given by: Role = 0.66, Floor = 0.06, Subject = 0.0, Size = 0.06 i. Construct the smallest possible decision tree (in terms of the number of attributes required) to solve this classification task given the information you have. Label the non-terminal nodes with the attributes, and the edges with attribute values. For each terminal node (leaf) of the tree indicate the examples classified. ii. Is this the only tree you can construct of this size? Justify your answer. Room # Role Floor Subject Size Recycling bin? 307 Lecturer 3 Math Large No 309 Researcher 3 Math Small No 408 Lecturer 4 CS Medium Yes 415 Student 4 Math Large Yes 509 Researcher 5 CS Medium No 517 Lecturer 5 CS Large Yes 316 Student 3 Math Small Yes 420 Researcher 4 CS Medium No [3] [4] [4] [4] [6] [4]
欢迎咨询51作业君
