Assignment Details:

Question 1: Search and Planning
Transport for London helpfully provides visitors with a map that shows walking times between stations on the London Underground: see http://content.tfl.gov.uk/walking-tube-map.pdf. Suppose you are doing research for a book on the architecture of Underground stations, and your task for today is to walk between Victoria Station and Leicester Square, making sure you walk past each intermediate station on your route (no short cuts).

a. Write a problem formulation for this activity including precise descriptions of the initial state, the actions available at each state, a goal test and a path cost function.
Please note, you are only required to specify the actions available at stations that feature in the search trees you construct in your answers to (b) below.

b. Show how the quickest route will be calculated by each of the following search strategies:
i. Breadth-first search.
ii. Depth-limited search, to a depth limit determined by you (give reasons for your decision).
iii. Uniform-cost search.

c. Now find the fastest walking time from each relevant station to Leicester Square using https://walkit.com/. Use these timings as a heuristic to determine the route that will be calculated by the A* algorithm.

d. Read up on the situation calculus, for example in section 10.4.2 of AIMA or 15.1.1 of Mackworth and Poole. Rewrite the planning problem from page 36 of the subject guide using the situation calculus, with formulas of the calculus in place of literals such as KettleFull, JamToast.
[40 marks]

Question 2: Machine Learning
You have probably encountered the term “deep learning” (DL) in your general reading, and you may have seen claims that this approach will eventually replace other current techniques in AI, such as “classic” Machine Learning or “symbolic” methods of the kind that are addressed in this course.

Study the readings listed below, and any other literature you consider relevant. Write a report of up to 1200 words summarising the strengths and limitations of DL as presented in these articles, and giving your assessment of the actual and potential achievements of this technology.

Chollet, F. Deep Learning with Python. (Greenwich, CT: Manning Publications, 2017) [ISBN 9781617294433] chapter 1. Freely downloadable from: https://www.manning.com/books/deep-learning-with-python.

Marcus, G. ‘Deep Learning: A Critical Appraisal’. 2018. Available from arxiv.org at https://arxiv.org/ftp/arxiv/papers/1801/1801.00631.pdf.
[30 marks]

Question 3: Natural Language Processing
a. Explain what is meant by the Chomsky hierarchy. How does it apply to the
grammatical analysis of natural language? Write no more than 600 words.

b. Study the list of formal grammar rules on page 42 of the subject guide for this course. Please note, there is at least one typo: ‘Conf’ should read ‘Conj’. Propose new or amended rules so that the grammar generates examples (i-viii) below, but not the ungrammatical (ix-xii). Explain your answers.

Credit will be given for compactness and generality in your grammar. Avoid giving ‘ad hoc’ rules that match these particular examples but do not generalise to other grammatical sentences.

i. 76 trombones led the big parade.
ii. 300 Spartans defended the pass at Thermopylae.
iii. Jana saw either a wumpus or a shamus at the end of the street.
iv. The hideously ugly wumpus chortled and whiffled as it came through the
wood.
v. The wumpus floated in a most peculiar way.
vi. The students agreed that their professor was tough but fair.
vii. If you see a wumpus then you should be very careful.
viii. Either Fatima saw a wumpus or she dreamed it.
ix. *The Wumpus floated in a most way.
x. *The students agreed that their professor was very.
xi. *Ivan saw either a wumpus and a shamus.
xii. *If Ali saw a wumpus or it was a shamus.
c. Draw syntax trees for (iii), (v) and (vii) using your amended grammar.
[30 marks]
[Total: 100 marks]