1. Here is a graph of some cities of Europe. Each city c in the graph is annotated with a value h(c) indicating a heuristic estimate of the city's distance from Zagreb. We would like to find an optimal path from Prague to Zagreb.
Is this heuristic admissible?
Is this heuristic consistent?
If we use a greedy best-first search, will we necessarily find an optimal path? Might we find an optimal path?
If we use A*, how many nodes will be expanded in the search?
2. In chess, a rook can move any number of squares horizontally or vertically, but cannot jump over other pieces. Is Manhattan distance is an admissible heuristic for the minimum number of moves to move a rook between two given squares with a certain set of pieces on the board?
3. True or false?
A* always expands nodes in decreasing order of h(n).
A* always expands nodes in increasing order of f(n).
Uniform-cost search (Dijkstra's algorithm) always expands at least as many nodes as A* with a consistent heuristic.
Whenever A* expands a node, it has found the optimal path from the start node to that node.
4. Is the heuristic function h(n) = 0 consistent? How will A* behave using this heuristic function?
5. Consider a heuristic function h(n) that returns the exact cost of the cheapest path from a node n to a goal state. Is h consistent? How will A* behave using this heuristic function?
6. True or false?
The maximum of two admissible heuristics is admissible.
The maximum of two consistent heuristics is consistent.
The sum of two admissible heuristics is admissible.
8. In A* we use a cost function f(n) = g(n) + h(n), where g(n) is the total cost of the path from the start node to node n, and h(n) estimates the cost of the path from n to the goal. Assume that h is a consistent heuristic, and consider the optimal path from the start node to the goal. As we walk along this path, how will f(n) change from node to node? Will it be (a) increasing, (b) decreasing, (c) non-increasing, (d) non-decreasing, or (e) not necessarily any of these? What about g(n)? h(n)?
9. Consider a variant of A* that uses f(n) = (2 – ω) g(n) + ω h(n) for some constant ω. What kind of search does this perform for ω = 0, ω = 1, and ω = 2? For which values of ω is the search optimal, assuming that h is admissible?
10. In 2 dimensions, a robot has a circular shape with radius r. It is at position p1 and is moving at velocity v1. A player has a circular shape with radius p, and is at position p2.
a) Suppose that the player chooses velocity v₂. Will the player and robot collide? Write a GDScript function that will answer this question:
func collide(p1: Vector2, r: float, v1: Vector2,
p2: Vector2, p: float, v2: Vector2): # return true if they will collide
...
b) Suppose that the player would ideally like to travel at velocity v2, but must not collide with the robot. Write a GDScript function that returns a velocity that is as close as possible to v2 (i.e. minimizes |v1 - v2|) and will avoid a collision:
func avoid(p1: Vector2, r: float, v1: Vector2,
p2: Vector2, p: float, v2: Vector2): # return an acceptable velocity
...11. Extending the previous exercise, suppose that the player and robot want to cooperate to avoid a collision. Ideally the robot would like to travel at velocity v1, and the player would like to travel at velocity v2. Write a GDScript function
func coop_avoid(p1: Vector2, r: float, v1: Vector2,
p2: Vector2, p: float, v2: Vector2): # return an acceptable velocity
...
that the player can call to choose a velocity. (The robot can call the same function, swapping the arguments for p1/r/v1 and p2/p/v2.)
12. Suppose that we are searching in a grid of squares where a horizontal or vertical move costs 1, and a diagonal move costs sqrt(2).
Suppose that the grid is completely empty, i.e. there are no obstacles at all, and we are searching from a start point S at (0, 0) to a target T at (0, d). How many queue nodes will be expanded in the search if we use each of the following algorithms?
a) breadth-first search
b) Dijkstra's algorithm (note: for this algorithm it is difficult to compute an exact number, but answer with an expression that is asymptotically optimal as d goes to ∞.)
c) A*, with Euclidean distance as the heuristic function
d) JPS
13. Extending the previous example, now suppose that we are searching from a start point S at (0, 0) to a target T at (0, 2d). There are obstacles at squares (x, d) for all x in the range -d < x < d.
a) What is the cost of the optimal path to the target?
b) If we use A* to search, approximately how many nodes will be expanded?
c) If we use JPS to search, how many nodes will be expanded?