Answers

U9.4 A* and the heuristic

Planning · University · about 40 min

What this lesson is about

Guessing what is left to pay, why the guess must never be too high, and why greedy best first is not A*.

• Admissible
• Consistent
• Why greedy best first is not A*
• Weighted A*

Questions 7 marks in all

1. [1 mark]What does this program print?

   import math
   CELL = 5.0
   goal = (34, 34)
   c = (30, 20)
   dx, dy = abs(c[0] - goal[0]), abs(c[1] - goal[1])
   octile = CELL * (max(dx, dy) + (math.sqrt(2) - 1) * min(dx, dy))
   euclid = CELL * math.hypot(dx, dy)
   manhattan = CELL * (dx + dy)
   print(round(octile, 1), round(euclid, 1), round(manhattan, 1))
   

   Answer:

   78.3 72.8 90.0

   With dx = 4 and dy = 14 the cheapest eight-connected route on an empty grid is 4 diagonals and 10 straights, 78.3 cm, which octile gives exactly. Euclidean is below it; Manhattan, at 90, overestimates it.

2. [1 mark]A* runs on an eight-connected grid with the Manhattan heuristic dx + dy. Is that heuristic admissible?

   1. ANo: a diagonal step costs sqrt(2) but Manhattan counts it as 2, so it can overestimate the remaining cost
   2. BYes: Manhattan distance never exceeds the true cost on any grid
   3. CYes, because Manhattan is consistent
   4. DNo, because it is smaller than the Euclidean distance
   Answer: A. Manhattan is admissible only on a four-connected grid. On eight neighbours it overestimates, and A* can return a longer route than necessary.

3. [1 mark]What is the difference between greedy best first search and A*?

   1. AGreedy orders the queue by h alone, dropping g, so it ignores what has already been spent and is not optimal
   2. BGreedy uses an admissible heuristic and A* does not
   3. CGreedy expands more cells than A* but finds the same path
   4. DGreedy uses a stack instead of a priority queue
   Answer: A. On this map greedy expands about 250 cells for a 410 cm route; A* expands about 680 for 331 cm. The g term is what remembers the cost so far.

4. [1 mark]Weighted A* with w = 1.5 is run on a map where the optimal path is 331 cm. What is the longest path, in cm, it is guaranteed never to exceed?

   Answer: 496.5 (accept within 0.1). With f = g + w h, the path is never worse than w times optimal: 1.5 x 331 = 496.5 cm.

5. [1 mark]Which of these heuristics are admissible for A* on an eight-connected grid?

   Tick every answer that is true.

   1. Ah = 0
   2. BEuclidean distance
   3. COctile distance
   4. DManhattan distance
   5. ETwice the octile distance
   Answer: A, B, C. Zero, Euclidean and octile never exceed the true remaining cost. Manhattan overestimates diagonals, and doubling octile overestimates everywhere.

6. [1 mark]What does a consistent heuristic buy A* beyond admissibility?

   1. Af never decreases along a path, so a node's g is final the first time it is popped and nodes never need reopening
   2. BA* then returns the optimal path, which an admissible heuristic does not guarantee
   3. CA* then expands fewer cells than greedy best first
   4. DA* then works with negative edge costs
   Answer: A. Admissibility already guarantees optimality. Consistency saves putting improved nodes back on the queue.

7. [1 mark]Why is octile distance a better heuristic than Euclidean distance on an eight-connected grid?

   1. AIt is still admissible and closer to the true cost, so A* expands fewer cells
   2. BEuclidean distance is not admissible on a grid
   3. COctile distance always equals the true cost, even with walls
   4. DOctile distance makes A* ignore the walls
   Answer: A. Octile is the exact cost on an empty grid, as tight as possible without overestimating. Walls only make the true cost larger.

The task: the same answer, less work

from bugbot import *
import heapq
import math
connect()

CELL = 5.0
N = 40
INFLATE = 8.0
WALLS = [(70.0, 0.0, 8.0, 115.0), (125.0, 85.0, 8.0, 115.0)]

from bugbot import *
import heapq
import math
connect()

CELL = 5.0
N = 40
INFLATE = 8.0
WALLS = [(70.0, 0.0, 8.0, 115.0), (125.0, 85.0, 8.0, 115.0)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

def blocked(i, j):
    x, y = i * CELL + CELL / 2, j * CELL + CELL / 2
    if x < INFLATE or y < INFLATE or x > 200 - INFLATE or y > 200 - INFLATE:
        return True
    for ox, oy, ow, oh in WALLS:
        if ox - INFLATE <= x <= ox + ow + INFLATE and oy - INFLATE <= y <= oy + oh + INFLATE:
            return True
    return False

grid = [[blocked(i, j) for j in range(N)] for i in range(N)]
start, goal = (6, 6), (34, 34)

def octile(c):
    dx, dy = abs(c[0] - goal[0]), abs(c[1] - goal[1])
    return CELL * (max(dx, dy) + (math.sqrt(2) - 1) * min(dx, dy))

def search(h):
    """h is the estimate of what is left: return zero from it and this is Dijkstra."""
    g = {start: 0.0}
    queue = [(h(start), start)]
    done = set()
    expanded = 0
    while queue:
        _f, cur = heapq.heappop(queue)
        if cur in done:
            continue
        done.add(cur)
        expanded += 1
        if cur == goal:
            break
        for dx, dy in STEPS:
            nxt = (cur[0] + dx, cur[1] + dy)
            if not (0 <= nxt[0] < N and 0 <= nxt[1] < N) or grid[nxt[0]][nxt[1]]:
                continue
            step = CELL * math.hypot(dx, dy)
            if g[cur] + step < g.get(nxt, 1e18):
                g[nxt] = g[cur] + step
                heapq.heappush(queue, (g[nxt] + h(nxt), nxt))
    return g[goal], expanded

flat_cost, flat_expanded = search(lambda c: 0.0)
star_cost, star_expanded = search(octile)
print("cost:", round(star_cost, 1))
print("dijkstra:", flat_expanded)
print("a star:", star_expanded)
print("same answer:", abs(flat_cost - star_cost) < 1e-6)