A* on a Warehouse Grid: Unit-Cost Diagonals
An autonomous forklift plans on a 200×200 grid of free and blocked cells. The planner is A* with 8-connected moves and a uniform cost model: orthogonal moves cost 1 and diagonal moves also cost 1. Corner cutting through a blocked cell is forbidden: a diagonal step is legal only if both adjacent orthogonal cells are free. Moves into blocked cells are impossible. The heuristic is Manhattan distance to the goal. Maps contain long walls with single-cell gaps and open halls with no obstacles at all. On random maps A* always finds a path, but on maps with long walls the returned paths are up to 12% longer than the BFS optimum computed offline, and this repeats. The team also reports an average of about 9,000 node expansions per query, while the SLA requires fewer than 5,000. Three proposals are on the table: (i) keep Manhattan and add a tie-break, (ii) switch to Chebyshev, (iii) switch to octile distance.
1. Explain why Manhattan distance destroys A*'s optimality guarantee on this grid, using numbers. Why does the planner still always find a path?
Read the worked answer
Under this cost model a diagonal move advances both coordinates by one for cost 1, so the true cost of crossing a displacement of (dx, dy) with no obstacles is max(dx, dy). Manhattan gives dx + dy, which overestimates by min(dx, dy).
Take a node 4 columns and 4 rows from the goal: true remaining cost is 4 (four diagonal steps), Manhattan returns 8 - a factor of two. Any heuristic with h(n) > h*(n) for some node is inadmissible, and A* with an inadmissible heuristic loses its guarantee: it can expand a node with a suboptimal g and close it, so the first goal it pops need not be on an optimal path. The observed 12% excess path length is exactly the symptom, and its repeatability on wall maps is expected - walls force long diagonal detours where the overestimate is largest.
A* still terminates with a path because the heuristic is non-negative and finite and the search is on a finite graph with a closed list; it explores the whole reachable component if it must. Termination and optimality are different properties, and only the first survives an inadmissible h. On open halls Manhattan happens to be tolerable because the straight-line structure keeps the error small; the failures cluster on wall maps.
2. Evaluate the three proposals against this specific cost model and corner-cutting rule. Which heuristic is correct, and is it consistent?
Read the worked answer
Chebyshev, h = max(|dx|, |dy|), is the right choice. With unit-cost diagonals it equals the exact obstacle-free distance, and obstacles can only raise the true cost, so h ≤ h* - admissible. Consistency: one legal move changes |dx| and |dy| by at most 1 each, so max(|dx|, |dy|) changes by at most 1, and every move costs exactly 1, hence h(n) − h(n') ≤ c(n, n'). Consistent, therefore admissible, and with a closed list no node needs re-expansion.
Octile distance, based on orthogonal cost 1 and diagonal cost √2, is the wrong heuristic here. For a displacement of (4, 4) it returns 4√2 ≈ 5.66 against a true cost of 4 - inadmissible. It is the correct heuristic for the standard √2-diagonal model, which this planner does not use. Proposal (iii) actively reintroduces the bug.
The no-corner-cutting rule does not break Chebyshev's admissibility: the rule can only make some paths more expensive, so the true cost only grows relative to the relaxation. It does mean Chebyshev is no longer perfectly informed near wall corners, which is acceptable.
Proposal (i) is not a fix. Tie-breaking changes which among equal-f nodes is expanded; it cannot repair h > h*. It may reduce expansions, but optimality stays broken.
3. With Chebyshev in place, how would you get expansions under 5,000, and what must remain true for the answer to stay optimal?
Read the worked answer
Chebyshev is consistent, so the search frontier is dominated by ties: on an open hall every cell on a monotone staircase to the goal has the same f = g + h, and a naive FIFO tie-break spreads the search across the whole hall. Break ties by preferring the larger g (the deeper node), which is a standard and cheap change: among nodes with equal f, the one closest to the goal is expanded first, and the search commits to a corridor instead of fanning out. On empty and lightly obstructed maps this alone typically cuts expansions by an order of magnitude - from the thousands into the hundreds - with no loss of optimality, because the tie-break only reorders nodes of identical f.
Guard the details. The tie-break must be applied after the f comparison, never as part of it; adding a small weight to h converts the algorithm into weighted A*, which is bounded-suboptimal, not optimal. Keep h consistent (Chebyshev) so a closed list is safe. Use a binary heap with a stable secondary key, and dedupe by state.
If expansions are still high on wall maps, the next step is Jump Point Search, which is valid for uniform-cost 8-connected grids including the no-corner-cutting variant, or bidirectional A*. Both preserve optimality when both directions use consistent heuristics, and both should be validated against the offline BFS optimum on a regression set of wall maps before rollout.