UNIVERSITY OF BRISTOL DECEMBER 2020 FACULTY OF ENGINEERING
Third Year Examination for the Degrees of Bachelor of Science and Master of Engineering
COMS30013-SAMPLE ARTIFICIAL INTELLIGENCE
This sample paper is not timed.
The real exam paper will be set for TWO HOURS.
Answer ALL questions in Part I Each question in Part I is worth 1 mark.
Answer TWO of the three questions in Part II Each question in Part II is worth 15 marks.
For each multiple-choice question in Part I, only one answer is considered correct. If you think more than one answer is correct, choose the most correct answer. There is no penalty (negative mark) for incorrect answers.
In Part I, questions that require you to fill in a blank part of a sentence, need one or more words added to each blank to complete the sentence. The size of the blank space is not related to the length of the answer.
This sample paper contains 15 questions in Part I. The real exam paper will contain 30 questions in Part I, each worth 1 mark.
For Part II, indicate CLEARLY and UNAMBIGUOUSLY which part of which question each of your answers relates to. Ensure your answers are presented in the correct order with all of your work related to one answer in the same place, and each answer clearly separated from the next by a line of dashes (——————————————————–).
If you answer MORE than two questions from Part II, the two questions for which you achieve the best marks will be used.
Calculators must have the Faculty of Engineering Seal of Approval.
Part I – Answer all 15 questions. Each question is worth 1 Mark.
1. Which one of the following is a well-formed Prolog term?
A. _r(_a) B. R(a,B) C. r_(a_) D. R’
2. What is the standard logical interpretation of the Prolog operator “;”?
A. OR B. XOR C. IF
D. AND
3. Which one of the following is a unifier of the Prolog terms p(W,f(W,X)) and p(Y ,f(a,Z))?
A. { W/a }
B. { W/Y , Y/a }
C. { W/a, Y/a, X/V, Z/V }
D. {}
4. If (x,y) are the coordinates of an agent in a modified GridWorld where it can move one square at a time up, down, left, right OR diagonally, which one of the following is an admissible heuristic for the length of the shortest path back to the origin (0,0)?
A. (x*x) + (y*y) B. x+y
C. x*y
D. x
5. Which one of the following statements is FALSE?
A. A* will never return a worse solution than breadth-first search
B. breadth-first search will never visit more nodes than A*
C. breadth-first search will never return a worse solution than depth-first
search
D. depth-first search may visit fewer nodes than A*
6. Which of the following is NOT a real bio-inspired computing paradigm?
A. DNA computing
B. SwarmIntelligence
C. Geneticprogramming
D. Artificial Immune Systems
E. Trick question – they are all real
7. What is an “allele”?
A. A value taken by a gene
B. A loci
C. A chromosome
D. A genotype
8. Which of the following statements is least true? Hillclimbing methods are:
A. Effective for unimodal landscapes
B. Good at finding local optima
C. Efficient
D. Local search methods
9. The fitness score assigned to individual A in generation G of a GA’s execution is X before fitness sharing is applied but becomes Y afterwards. If Y
B. Commitment(University, Student, True, Move-Learning-Online)
C. Commitment(Student, University, CurrentDate > 9 Dec 2020,
Move-Learning-Online)
D. Commitment(University, Student, CurrentDate > 9 Dec 2020,
Move-Learning-Online)
END OF PART I
Part II – Answer TWO of the three questions. Each is worth 15 Marks. II.1 Logic Programming
You are given the following Prolog program which concerns natural numbers expressed in Peano notation – where successive integers are represented by the terms 0, s(0), s(s(0)), s(s(s(0))), etc. The program contains one fact (stating that zero is an even number), one rule (stating the double-successor of an even number is also even) and one query (aiming to verify that one is not even):
even(0).
even(s(s(N))) :- even(N). ?- \+ even(s(0)).
Note that, when Prolog encounters a query while loading a program, it will either proceed silently after finding the first successful answer, or it will issue an error message if the query fails (in order to notify the user that the specified goal/directive failed).
a) State whether the above query succeeds or fails.
b) Rewrite the two clauses in the above program as a single equivalent rule.
[1 mark]
[2 marks]
c) Give the standard translation of the rule you wrote down for part (b) above into First- Order Logic (FOL) by simply replacing each Prolog operator by its closest classical counterpart and quantifying over any variables.
NOTE: You should assume standard operator binding conventions (inserting parentheses where necessary) and use the following ASCII symbols to represent the quantifiers (A and E) and connectives (^, v, ¬, <-, -> and <->).
[2 marks]
d) Consider the following definition of predicate odd/1 – which is intended to characterise odd Peano numbers in the same way that even/1 characterises even Peano numbers.
odd(X) :- \+ even(X).
Draw SLD trees to explain the behaviour of this definition when it is called with ground and variable arguments, respectively, and argue why this definition is not fit for purpose.
NOTE: Assume the standard Prolog search strategy with the “cut-fail” definition of negation and use the ascii notation illustrated below to write your tree (where a “?-” precedes each goal, “+” is a choice point, “X” marks a subtree pruned by cut, “#” is a failure branch, “:” is an infinite branch, “[]” is a success branch, and {..} represents any computed answer):
?- goal.
|
?- resolvent.
|
+——————–+———-X———-. |||
?- branch_1 ?- branch_2 ?- branch_n |||
… .!. … |||
?- success ?- failure ?- infinite ||:
[] # :
{..}
[8 marks]
e) Write down an alternative definition of odd/1 which is fit for purpose (and whose argument can be treated as an input or an output).
[2 marks]
II.2 Genetic Algorithms
a)
Gary is interested in evolving images using a genetic algorithm. Each image is a 50-by-50 grid of coloured pixels. Each genotype is a one-dimensional array of N alleles that each explicitly specify one Red-Green-Blue colour component of one pixel. The colour of one pixel is defined by three consecutive alleles on the genotype, specifying the red, green, and blue components of the pixel’s colour, respectively. Each allele can take a floating point value in the legal range [0,1]. The first three alleles in the genotype define the colour of the top-left pixel, the next three alleles define the colour of the pixel immediately to the right of this first pixel. The final triple of alleles defines the colour of the bottom-right pixel in the image.
If each allele can take one of 2^16 different values between 0 and 1, how many different images does the search space contain?
[1 mark]
b) Gary implements mutation in the following way. Each allele in the genotype of a new offspring image has independent probability m of being mutated. When an allele is mutated, the parental value is perturbed by adding a value drawn uniformly at random from the range [-0.1, +0.1]. If the new, perturbed value is outside the legal range of [0,1] it is truncated to the nearest legal value.
When Gary runs his genetic algorithm, he is interested to see that images with bright bold colours tend to be evolved. Explain how his mutation operator may be contributing to this result.
[4 marks]
c) Gary is thinking of implementing sexual recombination. He wants to combine two high fitness parental images to create an offspring. He has considered one- point crossover at a randomly selected position on the genotype, but he isn’t convinced that this will be a good choice. Define a simple crossover operator that will take two parental genotypes and create a single offspring genotype. The offspring genotype should comprise a rectangular section of one parent replacing the equivalent part of the image provided by the second parent.
[4 marks]
d) Gary is a little disappointed with the results generated by his genetic algorithm. The images in the population tend to be quite similar and it takes a long time to discover interesting images. Gary has been told by Sue that his “direct genotype-phenotype mapping might be too simplistic”, but he has not come across this idea before. Help Gary to understand the concept of a genotype-phenotype mapping and explain how a less direct mapping could allow evolution to generate more diverse images more quickly.
[6 marks]
II.3 Multi-Agent Systems
a)
Consider a case in which two students (Grace and Judy) live together in a rented house. They need to agree on which Internet service to sign up for from their local cable company (Example Media Co.). Grace will sign the contract with the cable company and pay for the service but she would like to also sign a side contract with Judy in which Judy agrees to pay her share.
List and describe the social norms needed to characterize the interactions in this setting. Use the commitment-based notation to define the identified norms.
[6 marks]
b) Describe a scenario in which one of these norms is violated. State the relevant event sequence using the notation from your answer to part (a) above. Who is accountable for this norm violation?
[3 marks]
c) Grace and Judy graduate. Grace (who signed the contract with the cable company) leaves the city. Judy finds a job in the same city and continues to stay in the same rented house. Judy takes over the contract with Example Media Co. from Grace. Olivia and Alice join Judy as her new house mates. Olivia and Alice sign side contracts with Judy to pay their shares of the cost for the Internet service.
Refine the initial normative specification and produce the new normative specification for the new setting. You should describe the required commitment changes and then use (some of) the ASSIGN, CANCEL, CREATE, DECLARE, DELEGATE and RELEASE commitment operations to define the required refinement process.
[6 marks]