Description
1 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.
xs
A
B
C
D
E
F
G
H
xg
1
5
3
1
1
4
4
1
1
2
7
8
1
2
1
2
2
3
3
1. 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.
2. Show the tree produced by Dijkstra’s algorithm at the end, together with the costs associated
with each vertex.
2 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
xs
A
B C
D
E
F xg
G
3
2
5
10
2
6
3 2 10
2
1 8
7
4
2
2
Vertex xs A B C D E F G xg
h 7 7 7 3 1 2 4 1 0
3 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. Define 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
4 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 define a
valid navigation function.
1. explain why the provided values do not define a valid navigation function;
2. 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
