Maximum Received

Problem 1 30
Problem 2 50
Problem 3 20
Total 100
Note: Please make sure to read the last page of the exam which is about the instructions, before
start to solve the exam

Problem 1: Given the following puzzle you are requested to design an agent to go around
in the puzzle. Your agent can move only two squares right and left, one square up
and down. For example, if start point is S(2,2) and it moves towards right it can go to
(4,2) as in the figure below. While the agent moves, it can jump over a black square but it
cannot land over it. For example, no move can go over the point (3,3). In every 3 moves
in the system one of the black squares randomly changes place.

Assume that this agent first moves to up ( ) then right( ), then down ( ) and then left
( ).

0 1 2 3 4 5 6
0              
1              
2     S        
3              
4              
5              
6              

(y- axis)

a) Starting from point S, please draw a search space for this agent (you can use
coordinates for that. Please apply loop detection. (15 pts)
b) For the above agent and its environment, please answer the following
questions. Please write one sentence problem specific explanation and do
not forget to tell the answer (ex: because of …. It is episodic). One word
answers (ex: static or dynamic) or the definitional answers which is not specific
to the problem will not get any points. (16 points)

1-Is the environment Accessible or Inaccessible?

2-Is the environment Deterministic or Non-deterministic?

3-Is the environment Static or Dynamic?

4-Is the environment Discrete or Continuous?

 c) What is the type of this problem? Explain in one sentence. (Single word
answers will not get any point) (4 pts)

Problem 2 : Consider the following search space where we want to find a path from
the start state S to the goal state G. The table shows heuristic function h1

7 A 5 Nod h1
1
e
2
S 4 S 6
C G A 2
4 B 4
B
C 1
8
2 D D 5
R 0

: Consider the following search problem as represented in the below tree. The start state
is given as A and the goal state is represented as G (all of the nodes represented as G1,
G2, G3, G4 are actually the same goal G but they are numbered to ease your work in
solution)

In the below tree, number on the edges which are black represents the actual cost
between the nodes and the red values on the nodes represent the heuristic value.

Please answer the following questions. Some of the rules you should follow in your
solutions as follow.

 Do not use colors in your solution.

 In order to write numbers next to G do not use G1 but either use subscript and
write G1.
 Any cost information written like B2 will not be accepted you should use superscript
and it should be written B2
 In the questions you should use the queueing techniques as it is done in the
lectures even it is possible to solve it in another way, the solutions with different
methods won’t be accepted.
 While using the letters in the queue use font-14 (Arial) ex: A
 For queuing techniques please use the reserved places for you. To show the
expanded nodes please use the word (insert-shapes-line) so that it can be easily
detected as an example A
 Follow the line numbers in an order when your write your queue which is top to
down.
 Do not change the font or the format of the below reserved spaces for the
questions
 If you need to draw, please use (insert-shapes)
 In the queue if you have a node with the same cost of the new expanded one, add
the new expanded one after the one available in the queue.

a) Transfer the above graph to tree. Preferably construct the tree from left to right (B
can be considered left and A can be considered right). If you need to write the
same node more than one place please use numbering with subscript ( such as B 1)

b) What solution path will Breadth First Search returns? Write the path and show how you
reach the goal by using queuing technique (10 pts )

A
1------------------------ 6-------------------------- 11--------------------------

2----------------------- 7-------------------------- 12--------------------------

 3----------------------- 8-------------------------- 13--------------------------

4----------------------- 9 --------------------------- 14--------------------------

5----------------------- 10--------------------------- 15--------------------------

Path:

c) What solution path will Uniform Cost Search returns? Write the path and show how you
reach the goal by using queuing technique e (10 pts )

1------------------------ 6-------------------------- 11--------------------------

2----------------------- 7-------------------------- 12--------------------------

3----------------------- 8-------------------------- 13--------------------------

4----------------------- 9 --------------------------- 14--------------------------

5----------------------- 10--------------------------- 15--------------------------

Path:

d) What solution path will A* Search returns? Write the path and show how you reach the
goal by using queuing technique (10 pts )

1------------------------ 6-------------------------- 11--------------------------

2----------------------- 7-------------------------- 12--------------------------

3----------------------- 8-------------------------- 13--------------------------

 4----------------------- 9 --------------------------- 14--------------------------

5----------------------- 10--------------------------- 15--------------------------

Path:

e)For the above given grap and the solutions of the three search algorithms you
solved ( BFS, UCS, A* ), what is the highest space complexity among all the
algorithms particularly for this example and how did you obtain it? Please
explain in 2 sentences ( Please note the I am not asking bigO notation I am asking
a literal number like 20 specific to this example)In your explanation, If you need to
refer to the above solutions please do so. (10 points)

Problem 3: You are given a game which has the following rules:

You have a single token x, and it can move,

Two squares right which has to follow with two square up or down (ex: if the token (x)
in (1,2) goes to right, it should also either go to (3,0) or (3,4))
Two squares left which has to follow with two square up or down
Two squares up which has to follow with two square right or left
Two squares down which has to follow with two square right or left

0 1 2 3 4 5 6
0              
1              
 
2   x          
 3            
4              
5              
6              

a) Provide an admissible heuristic, means it should be admissible for a given any start state to
any goal state (example below). Please provide your heuristic like a formula and then explain
the formula if it is needed with an example ( not more than 2 sentences) (10 points)

EX
: 0 1 2 3 4 5 6 0 1 2 3 4 5 6 (in the example the first grid is a start
  state and the second grid is a goal
0               0         G     state)

1               1              
2             2              
3               3              
 
4 S             4              
5               5              
6               6            

b)Independent than the above problem. Assume that for any game, the actual cost from
start state to the goal state is 100. You have two non-admissible heuristics which a1
have an estimate 110 and a2 has an estimate 120. Which one of the two non-
admissible heuristics would you choose to use in your algorithm for a better solution?
Explain the reason in two sentences (answer with no explanation will not get any
point) (10 points)