AI Search, Formal Logic, and Probabilistic Reasoning

AI search algorithms and problem formulation

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 requires you to walk from Tottenham Court Road to Kings Cross St Pancras, following the routes of the Underground lines to ensure you walk past each station on your chosen route. You may take whichever route you prefer, and for the purposes of this question it is assumed you favour the fastest route. When answering parts (c) and (d) below, you should briefly describe each algorithm and show the contents of the open list at each step from the start state until a goal state is found.

a.Explain in your own words what is meant by the following terms, in the context of AI Search:

i.Frontier

ii.Successor function

iii.Heuristic

iv.Admissibility

[4 marks]

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

(d) below

c.Show how the quickest route will be calculated by each of the following search strategies:

i.Breadth-first search

ii.Depth-first search with iterative deepening

iii.Uniform-cost search

d.Now find the fastest walking time from each relevant station to Kings Cross using an online application such as http://walkit.com/. Show a list of these timings and use them as a heuristic to determine the route that will be calculated by the A* algorithm.

Prolog is a declarative programming language that allows you to create a knowledge base by writing first-order logic sentences, and then pose queries to that knowledge base. The language itself takes care of performing the necessary inference; your role is primarily that of correctly specifying the problem and the query you need answered.

You may use any implementation of Prolog for this question. SWI-Prolog is recommended as it is very straightforward to install and use. A current stable version for your platform can be freely downloaded from http://www.swi-prolog.org/, where you will also find comprehensive documentation.

You are advised to read through the whole of parts (c) and (d) before starting to answer them.

a.Explain in your own words what is meant by the following terms, in the context of formal logic:

i.soundness

ii.completeness

iii.entailment

iv.satisfiability

b.Using truth tables, show whether:

i.(p → q) & (q → r) entails p → r

ii.(p → q) → r is equivalent to p → (q v r)

c.Represent the following statements as formulas of Predicate Calculus, stating the intended interpretation of any predicates and constants that you use. You should give two versions of each formula, one using the existential quantifier ? and one using the universal quantifier 

i.Someone who writes novels is a novelist.

ii.All novels are books.

iii.All novelists, poets and journalists are writers.

iv.Poets are not the only writers.

v.Some novelists are American and some are Indian.

vi.Not all writers are American or Indian.

d.Encode the following facts as Prolog clauses. NB you may need to code more than one clause for each numbered sentence. You should keep the queries (i-v) below in mind when deciding how to structure your clauses.

1.Olga Tokarczuk is Polish and wrote the novel Flights.

2.Martha Gellhorn was an American novelist and journalist.

3.Sylvia Plath was American and wrote a poem called “Ariel”.

4.Arundhati Roy is an Indian activist and novelist.

5.George Eliot was British and wrote the novel Middlemarch.

Use your Prolog implementation to derive answers to the following queries, based on the information given in 1?5 above. You may need to encode some of your answers to Question 2(c) and/or other reasonable general statements as Prolog clauses, in addition to your encodings of 1-5 above. Explain your results.

i.Give the name of a British writer.

ii.Is Tokarczuk a novelist?

iii.Was Gellhorn a poet?

iv.Name an American writer who was not a journalist.

v.Give the nationality of a writer who is also an activist.

a.Explain the following terms in your own words, in the context of probabilistic reasoning:

i.Probability distribution

ii.Marginalising

iii.Conditioning

iv.Prior probability

v.Posterior probability

b.Suppose there is a test for an illness called Galen’s Disease, which shows positive in 90 per cent of patients who have the disease and in 2 per cent of patients who do not have the disease. Suppose 30,000 out of a population of 6 million have Galen’s Disease at any given time. If everyone in the population is tested, what is the probability that someone who tests positive for the disease actually has it? Explain your answer with reference to Bayes’ Rule.