Question 1 (10 marks) [Write your answers on this page]

Pick the most appropriate answer to each of the following questions.  Please write your answer to each question in the boxes below.

(a) The environment for a lecture timetabling system is:

1. observable, stochastic, discrete

2. partially-observable, stochastic, continuous

3. observable, deterministic, discrete

4. partially-observable, stochastic, continuous

(b) What is the time complexity of iterative deepening search:

1.  O(bd )

2.  O(bd)

3.  O(bd/2)

4. none of the above

(c) Which of the following problems is not suited to using constraint satisfaction search:

1. staff roster in a cafe

2. poker

3. exam scheduling

4. office layout design

(d) An auction has a dominant strategy if:

1. the goods go to the agent who values them the most

2. the auction mechanism discourages agreements between bidders to manipulate prices

3. the strategy results in bidders revealing their true value for a good

4. none of the above

(e) Given P (a) = 0.5 and P (b) = 0.4 for two Boolean random variables A and B, in which of the following joint probability tables are A and B absolutely independent :

Question 2 (10 marks) [Write your answers on this page]

For each part of the following question you should write a brief answer in the box provided.

(a)  [2 marks] Briefly explain what is the difference between a  goal-based  agent and a utility-based agent.

While  goal-based  agents  can  identify  action  sequences  that  achieve  a  given  goal,  utility- based agents can choose between alternative action sequences that satify a goal, by using a utility measure on the sequence of states in the solution.

(b)  [2 marks] Briefly explain what is the main difficulty in using Voronoi diagrams for skeletonisation in robot path planning.

It can be computationally difficult to compute  Voronoi diagrams in high-dimensional con- figuration spaces.

(c) [2 marks] Briefly exaplain in what way can a sealed-bid auction help prevent collusion.

Bidders  cannot see  each  others’  bids.   Hence,  they  cannot use  their  bids  to  send  a price signal to the other bidders.

(d) [2 marks] Briefly give two reasons why supervised learning with gradient descent search is not a good approach for learning in game playing search.

Delayed reinforcement – the reward from  an  action is not known until several time steps later, which slows down learning.

Credit assignment – difficult to know which action was responsible for the outcome.

(e) [2 marks] Briefly describe the operation of the most-constrained-variable heuristic for the forward checking search algorithm.

When backtracking, choose the variable with the most constraints with respect to the other unassigned variables.

Question 3 (10 marks) [Write your answers on this page]

Consider the game tree shown in Figure 3-1.

-1

1

-2

-3            -3

Figure 3-1

(a) [2 marks] What would be the next move if the minimax procedure is applied at the root of the tree to select your next move?                                              Answer: Move 2

(b)  [5 marks] Which nodes do not need to be evaluated if alpah-beta pruning is used? Mark with an ”X” on Figure 3-1 the nodes that do not need to be evaluated (i.e., are pruned). Assume that nodes are explored in the order they are shown from left to right.

(c) [3 marks] Briefly describe two methods for setting the cut-off depth in minimax search.

– Predefined depth limit on search

–  Use  quiescence search to  detect a state that is unlikely to  exhibit substantial changes in value in the near future.

Question 4 (10 marks) [Write your answers in the answer book]

The following questions relate to a trip-planner to be equipped in cars.  The planner is equipped with a road map of the city and a Global Positioning System that allows it to accurately estimate the position of the car at any time.  The map of the central city is shown below, the position of intersection nodes corresponds with the corners of the regular square grid, and are labelled. The system will suggest a path that the car might take from its current position to any specified goal location.

In the following the start point is A1, and the goal is G3. A table of straight-line distances from each node to the goal is also shown (e.g., the distance from B2 to G3 is 5.10).

A1     A2     A3     A4

0        1        2        3        4

(a) [2 marks] If the system used breadth-first search, which path would be chosen from A1 to G3?  Assume that nodes with the same depth are explored in increasing order of their node label.

A1, A2, A3, B3,  C3, E3, F3,  G3

(b) [2 marks] If the system used greedy search with the heuristic h(x) = straight-line distance from node x to the goal state G, which path would be chosen from A1 to G3?

A1, B1,  C1,  C2, B2, B3,  C3, E3, F3,  G3 or

A1, B1, B2, B3,  C3, E3, F3,  G3 depending on which instance of B2 in the search tree is chosen

(c) [3 marks] If the system used A* search with the heuristic h(x) defined as above and g(x) = distance travelled from the start state S to node x, which path would be chosen from A1 to G3?

A1, A2, A3, B3,  C3, E3, F3,  G3

(d)  [3 marks] Suggest another heuristic function for A* search that may lead to more efficient searching for this problem.   Briefly justify your answer,  and explain why the heuristic is admissible.

Use manhattan distance from  G3 to node at (x, y) = lx · 2l + ly · 1l

This is  admissible  because the manhattan distance is less than or equal to  the  actual dis- tance of a grid of streets such as this.

The manhattand distance dominates the straight line distance because it is always greater than or equal to straight line distance.