Monday, June 4, 2001
9.30a.m. – 11.15a.m.
University of Glasgow
DEGREES OF M.Eng., B.Eng., B.Sc., M.A. and M.A. (Social Sciences)
COMPUTING SCIENCE – SINGLE AND COMBINED HONOURS
ELECTRONIC & SOFTWARE ENGINEERING-HONOURS
SOFTWARE ENGINEERING-HONOURS
COMPUTING SCIENCE 4
ARTIFICIAL INTELLIGENCE 4
(Answer all questions.)
1.	(a)	Give a definition of the rational agent approach to artificial intelligence. Why is it often hard to be perfectly rational?
[2]
	(b)	Draw a rational agent structure for a utility-based agent, with a brief description of the components and explanation of its working.
[4]
(c)	A web agent is designed to scan daily news updates and events on the Internet for a particular user, and prioritise items for presentation at certain times of the day.  The agent should learn to present those stories the user is most interested in. The agent has necessary Internet communication protocols, such that its actions are accessing certain web-pages, and interpreting them. It has natural language and pattern recognition abilities to help it interpret the stories for information retrieval purposes.
(i)	Describe your interpretation of the Internet agent’s percepts, actions and goals.
[3]
(ii)	Describe the properties of this agent’s environment.
[5]
(iii)	What are the advantages and disadvantages of adding learning capability to a general intelligent agent?
[2]
(iv)	Some learning agents include a problem generator to aid learning. What does this do, and what are the trade-offs involved?
[3]
(v)	Where could learning be introduced in the Internet agent, and if it were to include a problem generator and include active learning, how might it go about this?
[5]
(vi)	When deciding which sites to visit next, given current state of knowledge E, how could the Internet agent estimate the expected value of perfect information of accessing new evidence Enew from one web-site from a list of N possible web-sites? Provide an equation to support the decision process.
[6]

2.	(a)	Search is used in many AI applications. Describe four features of search strategies which provide dimensions one can use to choose a suitable strategy for a given application.
[4]
(b)	Describe the issues related to design of an Evaluation function in a search-based game player.
[4]
(c)	Draw the game tree below, filling in the backed-up values at each node, from the leaf nodes in a MINIMAX run. Draw a second game tree showing which would nodes on the tree would be expanded on an alpha-beta run., and fill in only those values at nodes which would be evaluated.
[4]
MAX

MIN

MAX

MIN  2 3 5 9 0 7 4 2 1 5 6
(d)	Explain (including an equation) why a game with chance elements has a higher time complexity than a deterministic game.
[3]
(e)	Give a description of the term Heuristic, and how heuristics are commonly used in AI.
[3]
(f)	What properties does an admissible heuristic have and why is a dominant heuristic better for an A* search process?
[4]
(g)	What is metareasoning, and why is it useful? Give an example of its use.
[3]

3.	(a)	Give three reasons why a domain like medical diagnosis is not well suited to first-order logic.
[3]
(b)	A doctor says that an infant who predominantly turns the head to the right while lying on the back will be right-handed, and one who turns to the left will be left handed. 90% of the population is right handed.
		What is the probability of a baby who turns her head to the left being right-handed? Provide the conditional probability equations for the solution of this problem, and calculate the answer if the test is 90% accurate and a second answer for the case of the test being 80% accurate. (Final answers can be left as fractions.)
[5]
	(c)	A mobile robot has two sensors, an ultrasound sensor U which activates when 
physical distance D <= 1 metre, and a laser rangefinder sensor which gives the probability of the estimated distance DL being in a number of discrete ranges. The laser sensor is unreliable, and failures leading to readings of DL well outside normal tolerances are common.
		A belief network model of the system used to fuse these sensor readings to create a virtual proximity sensor is shown below:

DL
laser sensor reading

Distance D to object

U Ultrasound sensor activated

laser sensor failure

(i)	If evidence for U being active is inserted, do values of DL change? Explain your answer.
[2]
(ii)	If distance D is known does this change the answer to i) and why?
[2]
(iii)	Explain how sensor fusion works, and why it is used in real systems (consider the issues involved in sensing using different physical principles).
[3]
(iv)	Explain how a model like that shown in the figure could provide self-diagnosis of possible sensor failure.
[2]
(d)	Give two common examples of non-optimal behaviour in human decision-making that would not occur in a normative decision maker. What is the significance of this when building an intelligent agent to do what human experts have traditionally done?
[4]
(e)	An autonomous robot is to be designed to tidy an office environment by picking up empty cans. Compare and contrast the behaviour-based robotics approach to design with the classical robot control model using features from this application to illustrate your points.
[4]