Consider the following graph. Let the start vertex be x_s and the goal vertex be x_g. 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 OPEN queue have the same priority value, sort them by alphabetical order.

1. Show how the algorithm plans a path from x_s to x_g. 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 Dijkstras 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 x_s and x_g. Follow the same method used in class and in example 4.5 in the lecture notes.

3 Navigation functions 1

Consider the following grid environment and let the cell marked as x_g 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₀ for each cell/vertex in the grid. You can write the value of the value function directly in the grid.

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.