COMS30013
ARTIFICIAL INTELLIGENCE
Units Examined - COMS30013 & COMS30072
Part I - Answer all 15 questions. Each question is worth 1 Mark.
1. Which one of the following is a well-formed Prolog variable?
A. VAR(1)
B. Var'
C. _var
D. var1
2. What is the standard logical interpretation of the Prolog operator ":-"?
A. ∧
B. ∨
C. ←→
D. ←
3. If (x,y) is the current location of an agent in a standard GridWorld setting of size NxN (where the agent can move one square at a time North, East, South or West), which of the following is an admissible heuristic for the length of shortest path back to the start cell (1,1)?
A. 1
B. N
C. (x+y)/2
D. | x-y |
4. Given two admissible two heuristics h1 and h2, which of the following must also be admissible – where avg, min and max denote the average (i.e. mean), the minimum, and the maximum of two functions, respectively?
A. min(h1,h2)
B. avg(h1,h2)
C. max(h1,h2)
D. All of the above
5. Which one of the following statements is FALSE (assuming that the heuristic cost of any goal state is always zero)?
A. depth-first search will never visit more nodes than A*
B. breadth-first search will never return a worse solution than A*
C. A* will never return a worse solution than depth-first search
D. A* will never visit more nodes than breadth-first search
6. Which genetic algorithm feature can defeat the problem of the “invisible needle”?
A. Crossover
B. Quasi-Species
C. Mutation
D. Elitism
7. Which of the following genotypes is a possible result of 1-point crossover between these two parents: [01110011] [11001100]
A. [11111100]
B. [01001101]
C. [01110001]
D. None of the above
8. Consider a simple two-variable search problem in which each variable can take one of five different values, A, B, C, D, or E. The two-dimensional search space can be viewed from above as a 5-by-5 grid with each cell containing the score of the associated solution. Which of the following fitness landscapes is deceptive (assuming local search changes one variable to its immediately adjacent value, e.g., a B can be changed to A or C)?
A. A B C D E
A 5 4 5 4 4
B 4 4 5 4 4
C 4 4 5 4 4
D 4 5 4 4 4
E 5 4 4 4 5
B. A B C D E
A 1 1 5 5 8
B 2 1 2 9 5
C 3 1 1 2 5
D 4 2 1 1 1
E 5 4 3 2 1
C. A B C D E
A 1 0 1 5 9
B 2 1 0 1 5
C 3 2 1 0 1
D 4 3 2 1 0
E 5 4 3 2 1
D. A B C D E
A 9 8 7 8 9
B 8 7 6 7 8
C 7 6 5 6 7
D 8 7 6 7 8
E 9 8 7 8 9
9. Which of the following is NOT away of increasing diversity in a population?
A. Restricted mating
B. Discarding duplicate offspring
C. Fitness sharing
D. Decreasing mutation rate
10. The "methinks it is like a weasel" problem has:
A. Low epistasis
B. High epistasis
C. No Epistasis
D. Moderate epistasis
11. An agent needs to be told what actions to perform to satisfy its user's goals.
A. TRUE
B. FALSE
12. Proactive agents maintain a lookup table consisting of a list of stimulus and response pairs.
A. TRUE
B. FALSE
13. Which of these is an agent communication language?
A. KML
B. XML
C. KQL
D. KQML
14. Which of these operations is not a commitment operation?
A. Cancel
B. Declare
C. Assign
D. Release
15. A protocol for payment through a third party could naturally be specified using the __X__ of a commitment to pay (select the correct operation):
A. X=Assign
B. X=Declare
C. X=Delegate
D. X=Release
Part II - Answer TWO of the three questions. Each is worth 15 Marks.
II.1 Logic Programming and Search (this question has two sub-parts: a and b):
a) Suppose you are given a Prolog program consisting of ground instances of the following five predicates, which represent facts about movie titles in terms of their release year, their directors, their cast of actors/actresses, and any Oscar nominations: movie(Title, Year), director(Title, Name), actor(Title, Name, Role), actress(Title, Name, Role) and nominated(Title, Category) — where Category is a Prolog term of the form: best_picture, best_director, best_actor(Name, Role) or best_actress(Name, Role). Note that the first four predicates are the same as the movie database in the lectures, while the fifth predicate associates a movie with any of the four possible Oscar nomination categories listed above. Also note that, unlike actors/actresses (who will each be nominated for a specific role in a particular film), a best_director nomination will be implicitly shared by each of a film’s directors. Here is a sample encoding of a famous movie:
movie(sleuth, 1972).
director(sleuth, joseph_mankiewicz).
actor(sleuth, laurence_olivier, andrew_wyke).
actor(sleuth, michael_caine, milo_tindle).
nominated(sleuth, best_director).
nominated(sleuth, best_actor(laurence_olivier, andrew_wyke)). nominated(sleuth, best_actor(michael_caine, milo_tindle)).
You are now required to solve each of the following three tasks by writing a “simple” Prolog query that only contains variables, constants, the five predicates listed above along with the standard operators for conjunction ( ,), disjunction (;), negation (\+), term equality (==), integer comparison (<) and term comparison (@<). Each of your queries should terminate after returning all correct answers (at most some finite number of times) under default Prolog computation and search rules.
i Write a simple Prolog query which returns any director D (like joseph_mankiewicz) who received at least one best_director nomination. [1 mark]
ii Write a simple Prolog query which returns any director D who received at least two best_director nominations (for any films in any years). [2 marks]
iii Write a simple Prolog query which returns any director D who has never received any nominations for a best_director award. [3 marks]
b) This part of the question concerns a search problem in which a knight chess piece must move from the bottom left corner to the top right corner of a 5x5 grid. On each turn, the knight must go two cells horizontally or vertically followed by one cell orthogonally (while staying on grid). As shown below, a knight at cell “x” has 6 possible moves to any of the cells “a-f” – which have been labelled in order of a particular tie-breaking strategy, assumed in this question, that gives precedence to rows closer to the top of the grid and columns closer to the left of the grid (in that order of priority):
i Given that the knight initially starts in the bottom left corner of the grid, complete the following representation of the grid, which indicates the order in which cells would be added to a breadth-first search agenda (under the tie-breaking strategy described above). Note that you may assume the algorithm stops as soon as the goal cell in the top right corner has been added to the agenda. [3 marks]
ii Explain how breadth-first search would compare with depth-first search on this particular problem (assuming the same tie-breaking strategy) in terms of the length of the path computed, the number of nodes added to agenda (i.e. opened) and the number of nodes expanded (i.e. closed) before the goal is reached. Justify your answer. [3 marks]
iii Explain which, if any, of these observations are guaranteed to hold in any search problem. [1 mark]
iv In order to use A* search on this problem, it is necessary to find an admissible heuristic for estimating the number of moves needed by the knight to reach the goal. Prove that the Manhattan distance is not admissible and state a simple variation that is admissible. [2 marks]
II.2 Genetic Algorithms
Tom is exploring whether genetic algorithms might be used to optimise his university's exam schedule. He has watched some videos related to Richard Dawkins' ideas from the Blind Watchmaker book and has started to code a simple genetic algorithm. But he is struggling with some of the concepts.
a) Tom's first question concerns an example that Richard Dawkins uses. Was Dawkins’ Biomorphs system an example of natural selection or artificial selection? Explain. [3 marks]
b) Tom thinks that the “methinks it is like a weasel” problem that Dawkins describes is a perfect analogy for biological evolution. Explain how it oversimplifies evolution by ignoring epistasis and development. [6 marks]
c) Tomis considering whether to use roulette-wheel selection or tournament selection. What is the difference between them in terms of the probability that an individual will get picked to be a parent? [2 marks]
d) Tom's GA keeps getting stuck on local optima. He thinks that doubling the mutation rate might be a good idea. Is it? Explain your answer. [4 marks]
II.3 Multi-Agent Systems
Consider ExampleSoft as a software company. Ava, Bhuvan, Charlie are three software developers with ExampleSoft, and Denise is their manager. Consider a scenario where ExampleSoft gives Denise the responsibility of developing a software project with a delivery date as September 15, 2021. Denise agrees to complete the project. She divides the project into three tasks (T1, T2, and T3) and gives responsibility of these tasks to the three developers. Ava is responsible for T1, Bhuvan is responsible for T2, and Charlie is responsible for T3. Denise wants that the project (1) is delivered on time, (2) meets the functionality requirements, and (3) meets the security requirements. Denise asks Ava, Bhuvan, and Charlie to write code for their allocated task and to perform functional testing and security testing of their code. Ava, Bhuvan, and Charlie agree to this.
a) List and describe the commitments norms needed to characterize the various interactions between ExampleSoft, Denise, Ava, Bhuvan, and Charlie in this scenario. Use the commitment-based notation to define the identified norms. For each identified norm, also list who is accountable to whom. [8 marks]
Note that you may use the following propositions to indicate the events in the scenario (or you may create more if needed) and you may combine these using the Boolean operators NOT (negation), AND (conjunction) and OR (disjunction):
• project, delivery-date
• code-task-t1, code-task-t2, code-task-t3
• functional-test-t1, functional-test-t2, functional-test-t3
• security-test-t1, security-test-t2, security-test-t3
b) Are there any interdependencies in the commitment norms that you identified? List and briefly describe these dependencies. [1 mark]
c) Consider a case where Denise has to go on leave. Denise asks Flora to take over the project. Which commitment operations do we need to perform on the initial specification to arrive at the normative specification for the new setting? Describe the commitment changes in the new setting and describe the required refinement process using the commitment operations to arrive at the new specification. [6 marks]
Recall that commitment operations include ASSIGN, CANCEL, CREATE, DECLARE,
DELEGATE and RELEASE (although you may not need all of them) which behave as follows:
• CREATE(x,y,r,u) is performed by x, and it causes C(x,y,r,u) to hold
• CANCEL(x,y,r,u) performed by x, and it causes C(x,y,r,u) to not hold
• RELEASE(x,y,r,u) is performed by y, and it causes C(x,y,r,u) to not hold
• DELEGATE(x,y,z,r,u) is performed by x, and it causes C(z,y,r,u) to hold
• ASSIGN(x,y,z,r,u) is performed by y, and it causes C(x,z,r,u) to hold