[SOLVED] prolog-AI: CMP2020M

END OF UNIT ASSESSMENT: FACULTY:
DEPARTMENT:
UNIT:

UNIT CODE:
LEVEL:
CO-ORDINATOR: ===========================================================

INSTRUCTIONS TO STUDENTS:

You are to complete this assignment by writing a report and submitting a PDF on blackboard for RESIT Assessment Item 2 of CMP2020M.

QUESTIONS TO ANSWER: Answer ALL SIX questions.

MARKING SCHEME: The marks are indicated for each individual question.

RESIT assignment for examination Science
School of Computer Science Artificial Intelligence

CMP2020M
Two
Dr. Marc Hanheide

Page 1 of 5

Question 1: Knowledge Representation [20 marks]

1. Represent (i.e., draw!) the knowledge about (at least three different types of) vehicles (e.g. lorry, car, estates, bicycle, motorbike, wheelchair, ) using a semantic network. Include (at least two) properties: weight (e.g. heavy, medium, light) and fuel-type (e.g. diesel, petrol, electricity human,). Assume a super class vehicle with a default property fuel-type petrol. Explain your design and argue its plausibility. [10 marks]
2. Explain why semantic networks are believed to be plausible model of the organisation principles of knowledge in our brains. Which experimental evidence led to this conclusion? [5 marks]
3. Explain the main differences in inference in the hierarchical representation of

frames and semantic networks.

Question 2: Probabilistic Reasoning [20 marks]

Probabilistic Reasoning (medical expert system):
The following diagram shows a Bayesian belief network representing what happens when you eat sweets, i.e, if you eat sweets you may have toothache.

The conditional probabilities are (where S=sweets and T=toothache):

• P(S)=0.7 probability of eating sweets
• P(T|S)=0.1 indicates the probability of

  having toothache after eating sweets

• P(T|S)=0.01 indicates probability of

  having toothache without eating sweets.

[5 marks]

Page 2 of 5

Please answer the following questions, and make
sure you evidence you way of thinking by using the correct formulas:

1. Calculate the prior probability P(S).
Calculate the conditional probability p(T|S). Calculate P(T), i.e the probability of having toothache

[3 marks]

5. [5 marks]
6. [6 marks]

2. Calculate the conditional probability P(S|T), i.e. which is the probability of having eaten sweets if you have toothache

[6 marks]

Question 3: Planning [20 marks]

Look a simple version of the Towers of Hanoi problem:
The objective of the Towers of Hanoi puzzle is to move disks stacked on rods onto the rightmost rod (here referred to as rod 3), obeying the following simple rules for the action of moving disks:

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.

  The states are simply described by listing all disks from bottom to top on each rod as indicated in the figure above. So, a configuration with disk 1 on rod 2
  and disk 2 on rod 3 would be represented as shown on the right. By
  convention, disks with lower numbers are smaller.

  The start state and the intended goal state (all stacked on the rightmost rod) are shown in the figure on the right. Please answer the following questions:

1. Draw a search tree (up to depth 3, i.e. two actions to be executed) using the notation above, i.e. in each node of the search tree indicate the disks (only two in our example, with disk 1 being smaller than disk 2) stacked on each rod.

   [10 marks]

   The outcome should look similar to this tree (obviously, you need to complete the nodes and also the number of leaves will be different for you):

2. According to your tree, can the correct goal state be reached within two actions? Highlight the optimal path towards the goal state in your search tree visually and also write down the actions in the form of a sequence of move(X,Y) actions, with X being the disk number to move and Y being the rod to move it to. Explain in a short paragraph how the tree is traversed using depth-first search to find a solution. [10 marks]

Page 3 of 5

Question 4: Logic Programming [10 marks]

1. Given that t1, t2 are two atoms as follows: t1 = p(A, q(Y, a)),

t2 = p(q(a, Y), A), and

w = {q(a, Y)/A, a/Y}.
Is w a unifier of the two atoms? Explain your answer. (5 marks)

2. Build a truth table to verify if the proposition (p!q) (p q) is a tautology, a contradiction, or neither of the two. (5 marks)

Question 5: Search [20 marks]

1. Using the following node tree, explain the difference between depth-first and breadth-first search. What is the node search order in each case? (6 marks)

A

BC

A

D

EF

G

2. Dikstras algorithm searches through a node graph or grid by iteratively closing the node on the list of current open nodes which has the lowest cost. Explain what the term cost means within the context of Dijkstras algorithm. (3 marks)
3. After a node is closed, what operation is performed on its neighbouring nodes? (5 marks)

4. Explain how the A* algorithm improves on Dijkstas algorithm, by changing the way that the next open node is selected (6 marks).

Question 6: Games AI [10 marks]

1. Explain why computational speed is an important requirement of AI in video games

(2 marks).

2. The A* algorithm is commonly used in games to navigate agents around a level map. Explain how dynamically changing the map could invalidate a path calculated by A*, and also how that could result in unacceptable computational overhead. (5 marks)

3. Suggest a method for adapting the A* algorithm, to reduce the computational overhead that might result from dynamically changing the level map. (3 marks)

Page 4 of 5

Appendix: Useful Formulas

Truth Tables

Inference Rules

Probability Theory

Page 5 of 5