Description
Important Information
-
This homework is due at 4:15pm. The deadline is strict and will be enforced by CatCourses. No exceptions.
-
Your solution must be submitted in electronic form through CatCourses. Paper submissions will not be accepted. No exceptions.
-
If you write your solution by hand, write clearly. Unreadable documents will not be graded.
-
The method you follow to determine the solution is more important than the nal results. Clearly illustrate and explain the intermediate steps. If you just write the nal result you will get not credit.
-
THIS HOMEWORK MUST BE SOLVED INDIVIDUALLY. NO EXCEPTIONS.
-
Dijkstra’s algorithm
Consider the following graph. Let the start vertex be xs and the goal vertex be xg. Important: if a node has multiple outgoing edges, when the node is expanded the vertices adjacent to the node are processed in alphabetical order. Similarly, if multiple nodes in the OP EN queue have the same priority value, sort them by alphabetical order.
A 4 
D 2 
G
-
1
1
2
1
7
1
xs 5 
B 4 
E 8 
xg
-
3
1
3
2
1
2
C 1 F 3 H
-
Show how the algorithm plans a path from xs to xg. To display the various steps, follow exactly the same format used in the lecture notes (Example 4.4) and presented in class.
-
Show the tree produced by Dijkstra’s algorithm at the end, together with the costs associated with each vertex.
-
A
Consider the directed weighted graph shown at page 2.
Show how the algorithm A would determine the shortest path between xs and xg. Follow the same method used in class and in example 4.5 in the lecture notes.
1
A 10 
E 7 
G
-
2
2
4
1
8
2
xs 5 F D 2 
xg
-
3
3
2
2
10
-
6
C
-
Vertex
xs
A
B
C
D
E
F
G
xg
h
7
7
7
3
1
2
4
1
0
-
Navigation functions 1
Consider the following grid environment and let the cell marked as xg be the goal cell. Assume the planning graph associated with the grid includes the standard four actions (up/down/left/right) similarly to what presented in the lecture notes, and let the black cells be untraversable. De ne a navigation function : V ! R 0 for each cell/vertex in the grid. You can write the value of the value function directly in the grid.
xg
-
Navigation functions 2
In the following grid, assume the goal cell is the one with the 0 value. As in the previous example assume that the set of actions is up/down/left/right. The assigned numeric values do not de ne a valid navigation function.
-
explain why the provided values do not de ne a valid navigation function;
-
show the changes that must be made to the given values to get a valid navigation function. Your answer should list the smallest number of changes.
2
-
6
5
4
3
2
1
2
3
7
6
8
2
1
0
8
8
8
7
8
3
2
1
2
3
9
8
8
8
3
2
3
4
10
7
8
5
4
3
4
5
9
8
8
6
5
4
5
6
10
9
8
7
6
5
8
7
15
10
9
8
7
6
9
8
3
