Chair of Robotics, Artificial Intelligence and Real-time Systems
Department of Informatics
Technical University of Munich
Note:
Ecorrection • During the attendance check a sticker containing a unique code will be put on this exam.
Place student sticker here • This code contains a unique number that associates this exam with your registration number.
• This number is printed both next to the code and to the signature field in the attendance check list.
Grundlagen der künstlichen Intelligenz
n
Exam: IN2062 / Endterm Date: Monday 1st March, 2021
Prof. Dr.-Ing. Matthias Althoff 18:15 – 19:45
tio
Examiner: Time:
P1 P2 P3 P4 P5 P6 P7 P8 P9 P 10
I
Working instructions
• This exam consists of 18 pages with a total of 10 problems.
lu
So
Please make sure that you received a complete copy of the exam.
• The total amount of achievable credits in this exam is 61.5 credits.
• Detaching pages from the exam is prohibited.
es
• Allowed resources:
e
– a pen or PDF editor (do not write with red or green colors nor use pencils)
ot
– a non-programmable pocket calculator
N
l
– the provided formula sheet
p
– empty scratch paper (do not submit)
on
• Please write answers on the exam booklet only. If you run out of space, write on the additional pages provided.
m
Notes on other paper will be disregarded.
i
ct
• You must hand in all pages of the exam.
• Answers are only accepted if the solution approach is documented. Give a reason for each answer
re
Sa
unless explicitly stated otherwise in the respective subproblem.
or
• All subproblems are solvable independently from each other if not explicitly stated differently.
• Multiple-Choice questions are evaluated automatically. Use a cross to select your answer:
C
Answer A
Answer B
If you want to correct your answer, fill out the checkbox, and cross your new answer:
Answer A
Answer B
Notes next to the checkboxes cannot be evaluated.
Left room from to / Early submission at
– Page –
, Problem 1 Search (10.5 credits)
In the following tasks we search for a path from node A to node G , if not stated otherwise. If multiple nodes can be
explored next, alphabetic ordering should be used as the tie breaker, e.g., if B and C are added to the frontier, B is
added first.
On each of the following graphs we apply breadth-first (BFS) and depth-first (DFS) Graph-Search. Find out which
graphs are explored by each algorithm in the order A , B, C, D .
1 2 3
A B A B A B
C D C D C D
n
tio
E G E G E G
a) Tick all graphs that are explored in the order A , B, C, D by BFS:
3 ×1 ×2
×3 lu
b) Tick all graphs that are explored in the order A , B, C, D by DFS:
×2
So
1
0 c) Name another uninformed search algorithm that explores the nodes in graph 1 in the same order as BFS:
1
es
Iterative Deepening Search, Uniform-cost search / Dijktstra with unitary cost
e
ot
N
l
d) Does Depth-First Tree-Search terminate for graph 2 (0.5 points)?
p
on
Yes × No
m
i
e) State the first four nodes visited by DFS Tree-Search searching from A to G on graph 2.
ct
0
½
re
A - right neighbor - A - right neighbor
Sa
or
C
– Page –
, A 3 E
f) Tick the third node visited by Uniform Cost Search on the graph to the left
5 4 (once more starting at A and searching for G ). The start node A is the first visited
node. The numbers on each edge indicate the path costs between nodes (1
8 B C point).
6 7 A B D
D G E ×C G
g) Alter as few edge costs as possible on the graph from 1.f) such that B is visited third. You may either do so in the 0
printed graph or by writing the changed edge costs, i.e., if you change the cost between node X and Y to Z , write
d(X , Y ) = Z . 1
n
In the end d(topright, middleright) > d(topright, middleleft). X
-.5 if more than one changed cost but still
middle-left visited third. If more changed also make sure d(A , bottomleft) > d(A , topright)+d(topright, middleleft)
tio
must hold
For another search problem, the following two heuristics h1 and h2 are used for searching from A to G . We want to
lu
construct an optimal meta heuristic h ∗ taking into account information from both h1 and h2 .
h) Fill in the values for an admissible heuristic h ∗ dominating h1 and h2 assuming h1 and h2 are admissible. 0
So
1
Node n A B C D E F G
2
h1 (n) 4 3 10 11 9 5 8
h2 (n) 7 11 7 8 4 8 9
es
h ∗ (n)
h ∗ (n) = max {h1 (n), h2 (n)}, so always the bigger of the two should be chosen -0.5 for each wrong value
e
ot
i) Use the heuristic h1 from 1.h) for greedy best-first graph search on 0
E A B
the graph to the left starting from A and searching for G . State the
N
l
nodes in the order they are explored before completing the search. 1
C
p
on
F D G Depends on graph (encoded by two left nodes, first one top
left)
m
BF - A - B - E - F - G (1)
i
BD - A - B - F - E - G (6)
ct
EF - A - B - E - C - G (13)
j) Would A ∗ Tree-Search be optimal when using h2 as a heuristic (0.5 points)?
EB - A - F - E - C - G (18)
re
×
Sa
Yes FB - A - F - E - No
B - G (22)
-0.5 if single mistake, otherwise 0
or
k) Give a reason why (not)? 0
C
1
Not admissible / not underestimate / h2 (G) > 0 / cost of goal bigger 0
– Page –
Department of Informatics
Technical University of Munich
Note:
Ecorrection • During the attendance check a sticker containing a unique code will be put on this exam.
Place student sticker here • This code contains a unique number that associates this exam with your registration number.
• This number is printed both next to the code and to the signature field in the attendance check list.
Grundlagen der künstlichen Intelligenz
n
Exam: IN2062 / Endterm Date: Monday 1st March, 2021
Prof. Dr.-Ing. Matthias Althoff 18:15 – 19:45
tio
Examiner: Time:
P1 P2 P3 P4 P5 P6 P7 P8 P9 P 10
I
Working instructions
• This exam consists of 18 pages with a total of 10 problems.
lu
So
Please make sure that you received a complete copy of the exam.
• The total amount of achievable credits in this exam is 61.5 credits.
• Detaching pages from the exam is prohibited.
es
• Allowed resources:
e
– a pen or PDF editor (do not write with red or green colors nor use pencils)
ot
– a non-programmable pocket calculator
N
l
– the provided formula sheet
p
– empty scratch paper (do not submit)
on
• Please write answers on the exam booklet only. If you run out of space, write on the additional pages provided.
m
Notes on other paper will be disregarded.
i
ct
• You must hand in all pages of the exam.
• Answers are only accepted if the solution approach is documented. Give a reason for each answer
re
Sa
unless explicitly stated otherwise in the respective subproblem.
or
• All subproblems are solvable independently from each other if not explicitly stated differently.
• Multiple-Choice questions are evaluated automatically. Use a cross to select your answer:
C
Answer A
Answer B
If you want to correct your answer, fill out the checkbox, and cross your new answer:
Answer A
Answer B
Notes next to the checkboxes cannot be evaluated.
Left room from to / Early submission at
– Page –
, Problem 1 Search (10.5 credits)
In the following tasks we search for a path from node A to node G , if not stated otherwise. If multiple nodes can be
explored next, alphabetic ordering should be used as the tie breaker, e.g., if B and C are added to the frontier, B is
added first.
On each of the following graphs we apply breadth-first (BFS) and depth-first (DFS) Graph-Search. Find out which
graphs are explored by each algorithm in the order A , B, C, D .
1 2 3
A B A B A B
C D C D C D
n
tio
E G E G E G
a) Tick all graphs that are explored in the order A , B, C, D by BFS:
3 ×1 ×2
×3 lu
b) Tick all graphs that are explored in the order A , B, C, D by DFS:
×2
So
1
0 c) Name another uninformed search algorithm that explores the nodes in graph 1 in the same order as BFS:
1
es
Iterative Deepening Search, Uniform-cost search / Dijktstra with unitary cost
e
ot
N
l
d) Does Depth-First Tree-Search terminate for graph 2 (0.5 points)?
p
on
Yes × No
m
i
e) State the first four nodes visited by DFS Tree-Search searching from A to G on graph 2.
ct
0
½
re
A - right neighbor - A - right neighbor
Sa
or
C
– Page –
, A 3 E
f) Tick the third node visited by Uniform Cost Search on the graph to the left
5 4 (once more starting at A and searching for G ). The start node A is the first visited
node. The numbers on each edge indicate the path costs between nodes (1
8 B C point).
6 7 A B D
D G E ×C G
g) Alter as few edge costs as possible on the graph from 1.f) such that B is visited third. You may either do so in the 0
printed graph or by writing the changed edge costs, i.e., if you change the cost between node X and Y to Z , write
d(X , Y ) = Z . 1
n
In the end d(topright, middleright) > d(topright, middleleft). X
-.5 if more than one changed cost but still
middle-left visited third. If more changed also make sure d(A , bottomleft) > d(A , topright)+d(topright, middleleft)
tio
must hold
For another search problem, the following two heuristics h1 and h2 are used for searching from A to G . We want to
lu
construct an optimal meta heuristic h ∗ taking into account information from both h1 and h2 .
h) Fill in the values for an admissible heuristic h ∗ dominating h1 and h2 assuming h1 and h2 are admissible. 0
So
1
Node n A B C D E F G
2
h1 (n) 4 3 10 11 9 5 8
h2 (n) 7 11 7 8 4 8 9
es
h ∗ (n)
h ∗ (n) = max {h1 (n), h2 (n)}, so always the bigger of the two should be chosen -0.5 for each wrong value
e
ot
i) Use the heuristic h1 from 1.h) for greedy best-first graph search on 0
E A B
the graph to the left starting from A and searching for G . State the
N
l
nodes in the order they are explored before completing the search. 1
C
p
on
F D G Depends on graph (encoded by two left nodes, first one top
left)
m
BF - A - B - E - F - G (1)
i
BD - A - B - F - E - G (6)
ct
EF - A - B - E - C - G (13)
j) Would A ∗ Tree-Search be optimal when using h2 as a heuristic (0.5 points)?
EB - A - F - E - C - G (18)
re
×
Sa
Yes FB - A - F - E - No
B - G (22)
-0.5 if single mistake, otherwise 0
or
k) Give a reason why (not)? 0
C
1
Not admissible / not underestimate / h2 (G) > 0 / cost of goal bigger 0
– Page –
