EP15/EP16.TOKT11121 · Introduction to Artificial Intelligence · NEU

Week 5 Lab — Answer Key

Faculty of Data Science & Artificial Intelligence, NEU

Instructor Copy
Exercise 3

Emergency Vaccine Delivery — Mekong Delta

State-space graphAbbreviation table

AbbrLocationh(n)
PCCProvincial Cold-Chain Center (Start)10
PHFPhú Hòa Ferry8
HLBHưng Long Bridge6
TACTân An Canal Road7
BMMBình Minh Market6
SHCSông Hậu Crossing4
MPLMỹ Phước Levee5
LKDLong Khánh Dock4
TTETrung Thành Elevated Road3
NBDNgã Ba Đình Crossroads2
RCCRemote Commune Clinic (Goal)0
 
                PCC (h=10)
              /     |     \
           2/      5|      \3
           /        |       \
       PHF(8)    HLB(6)   TAC(7)
       /   \     /   \    /   \
      3     6   2     4  3     7
     /       \ /       \/      \
  BMM(6)   SHC(4)  MPL(5)  LKD(4)
     \      /   \     \      /
      4    2     5     3    2
       \  /       \     \  /
      TTE(3)     NBD(2)<──┘
          \        /
           5      3
            \    /
            RCC(0)

Task 2A* Search trace

Tie-breaking: equal f → smaller g; still tied → alphabetical order of location name.

Step Expanded g h f Open list after expansion — format: Node[g, h, f]
1 PCC 01010 PHF[2,8,10], TAC[3,7,10], HLB[5,6,11]
2 PHF (g=2 < TAC g=3) 2810 TAC[3,7,10], BMM[5,6,11], HLB[5,6,11], SHC[8,4,12]
3 TAC 3710 BMM[5,6,11], HLB[5,6,11], MPL[6,5,11], SHC[8,4,12], LKD[10,4,14]
4 BMM (g=5=HLB, B<H) 5611 HLB[5,6,11], MPL[6,5,11], SHC[8,4,12], TTE[9,3,12], LKD[10,4,14]
5 HLB (g=5 < MPL g=6) 5611 MPL[6,5,11], SHC[7,4,11]†, TTE[9,3,12], LKD[10,4,14]
6 MPL (g=6 < SHC g=7) 6511 SHC[7,4,11], NBD[9,2,11], TTE[9,3,12], LKD[10,4,14]
7 SHC (g=7 < NBD g=9) 7411 NBD[9,2,11], TTE[9,3,12], LKD[10,4,14]
8 NBD 9211 TTE[9,3,12], RCC[12,0,12], LKD[10,4,14]
9 TTE (g=9 < RCC g=12) 9312 RCC[12,0,12], LKD[10,4,14]
10 RCC — GOAL 12012 —

† Step 5: HLB→SHC gives g=7 < current g=8 → SHC updated from [8,4,12] to [7,4,11].

Optimal path
PCC→ TAC→ MPL→ NBD→ RCC
Total cost: 3 + 3 + 3 + 3 = 12 hours
Reconstruction: RCC ← NBD ← MPL ← TAC ← PCC

Task 3Greedy Best-First Search trace

Greedy always expands the node with the smallest h, ignoring g entirely.

StepExpandedhNeighbors added to Open
1PCC10HLB (h=6), TAC (h=7), PHF (h=8)
2HLB6SHC (h=4), MPL (h=5)
3SHC4NBD (h=2), TTE (h=3)
4NBD2RCC (h=0)
5RCC — GOAL0—
Greedy path
PCC→ HLB→ SHC→ NBD→ RCC
Total cost: 5 + 2 + 5 + 3 = 15 hours

QuestionsAnswers

Q1 — Same route?

No. A* found PCC → TAC → MPL → NBD → RCC (12 h); Greedy found PCC → HLB → SHC → NBD → RCC (15 h). A* is faster by 3 hours.

Greedy chose HLB (h=6) over TAC (h=7) because HLB looks closer by heuristic. However, the edge PCC→HLB costs 5 h while PCC→TAC costs only 3 h — Greedy never counts the cost already paid.

Q2 — Admissibility check

h*(n) = true shortest path cost from n to RCC:

NodeKey paths to RCCh*(n)h(n)h ≤ h*?
PCCPCC→TAC→MPL→NBD→RCC = 3+3+3+31210✓
PHFPHF→BMM→TTE→RCC = 3+4+5 = 12
PHF→SHC→TTE→RCC = 6+2+5 = 13		128✓
HLBHLB→SHC→TTE→RCC = 2+2+5 = 9
HLB→MPL→NBD→RCC = 4+3+3 = 10		96✓
SHCSHC→TTE→RCC = 2+5 = 7
SHC→NBD→RCC = 5+3 = 8		74✓
MPLMPL→NBD→RCC = 3+3 = 665✓

All nodes satisfy h(n) ≤ h*(n) → heuristic is admissible.

Q3 — PHF shut down

The optimal A* route PCC → TAC → MPL → NBD → RCC does not pass through PHF at all. Removing PHF (and its edges PHF→BMM, PHF→SHC) leaves the optimal path completely unaffected — A* still returns the same 12-hour route.

Exercise 7

Grid Pathfinding — Warehouse Robot

Warehouse 5×5 grid with blocked cells
Warehouse 5 × 5 grid — blocked cells (###) are storage shelves the robot cannot enter.
Coordinate convention — each cell is written as (r, c) where:
  • r = row — 0 at the top, 4 at the bottom
  • c = column — 0 at the left, 4 at the right
So: S = (0, 0) top-left corner; G = (4, 4) bottom-right corner.
c=0
c=1
c=2
c=3
c=4
r=0
S
×
r=1
×
r=2
×
×
r=3
×
r=4
G

Blocked: (0,3), (1,1), (2,1), (2,3), (3,3)

Step 1Compute h1 and h2

Cell (r, c) h1 = √[(r−4)² + (c−4)²] h2 = |r−4| + |c−4|
(0, 0) = S√(16+16) = √32 ≈ 5.664+4 = 8
(0, 2)√(16+4) = √20 ≈ 4.474+2 = 6
(1, 0)√(9+16) = √25 = 5.003+4 = 7
(2, 2)√(4+4) = √8 ≈ 2.832+2 = 4
(1, 4)√(9+0) = 3.003+0 = 3

Step 2Check dominance

For every cell: h2 ≥ h1 ✓
"h2 dominates h1 because for any cell (r, c), Manhattan distance is always greater than or equal to Euclidean distance."

Proof sketch: the straight line is the shortest possible path between two points, so the Euclidean distance is a lower bound on any axis-aligned (Manhattan) path — by the triangle inequality applied to horizontal + vertical steps.

Step 3Verify admissibility

BFS backward from G=(4,4) ignoring blocked cells gives the true shortest paths h*(n):

Cell h1 h2 h*(n) h1 ≤ h*? h2 ≤ h*?
(0,0)5.6688✓✓
(0,2)4.4766✓✓
(1,0)5.0077✓✓
(2,2)2.8344✓✓
(1,4)3.0033✓✓

Note: h2 equals h* exactly for all five cells — the obstacles happen not to force any detour on these particular paths.

Step 4A* trace with h2 (Manhattan distance)

Tie-breaking: equal f → smaller h2; still tied → smaller (r, c) lexicographically.

Step Expanded g h2 f Open list after expansion — format: (r,c)[g, h, f]
1(0,0) 088 (0,1)[1,7,8], (1,0)[1,7,8]
2(0,1) (h same, (0,1)<(1,0)) 178 (1,0)[1,7,8], (0,2)[2,6,8]
3(0,2) (h=6 < (1,0) h=7) 268 (1,0)[1,7,8], (1,2)[3,5,8]
4(1,2) (h=5 < (1,0) h=7) 358 (1,0)[1,7,8], (1,3)[4,4,8], (2,2)[4,4,8]
5(1,3) (h same, (1,3)<(2,2)) 448 (1,0)[1,7,8], (2,2)[4,4,8], (1,4)[5,3,8]
6(1,4) (h=3 smallest) 538 (1,0)[1,7,8], (2,2)[4,4,8], (2,4)[6,2,8], (0,4)[6,4,10]
7(2,4) (h=2 smallest) 628 (1,0)[1,7,8], (2,2)[4,4,8], (3,4)[7,1,8], (0,4)[6,4,10]
8(3,4) (h=1 smallest) 718 (1,0)[1,7,8], (2,2)[4,4,8], (4,4)[8,0,8], (0,4)[6,4,10]
9(4,4) = G 808 —
Optimal path
(0,0)→ (0,1)→ (0,2)→ (1,2)→ (1,3)→ (1,4)→ (2,4)→ (3,4)→ (4,4)
Cost: 8 steps
Note: (1,0) remains in Open throughout but is never expanded — its f=8 is always beaten by a node with smaller h2.

Step 5Effect of extra wall at (3,4)

1. Does h2(2,4) change?

No. h2(2,4) = |2−4| + |4−4| = 2. Manhattan distance is computed purely from coordinates — it ignores obstacles entirely.

2. h*(2,4) with the new wall

With (3,4) blocked, (2,4)'s only accessible neighbor is (1,4). The robot must take a long detour:

(2,4)→(1,4)→(1,3)→(1,2)→(2,2)→(3,2)→(4,2)→(4,3)→(4,4)   →  8 steps

h*(2,4) = 8. Since h2(2,4) = 2 ≤ 8, h2 remains admissible.

3. Effect on tightness

h2 = 2 but h* = 8 — the heuristic underestimates by 6 steps. Heavy obstacles create large gaps between h2 and h*, causing A* to explore many more nodes. Admissibility is preserved; search efficiency degrades.

Exercise 8

Metro Navigation — City Airport

City metro map with Line 1 (Red) and Line 2 (Blue)
City metro map — Line 1 (Red Express) and Line 2 (Blue Local) with transfer points.
Abbreviations: Ce Central · Ri Riverside · Mi Midtown · We Westgate · Up Uptown · Do Docklands · Ea Eastfield · Sk Skyview · G Airport

Task 1A* Search trace

Tie-breaking: equal f → smaller h; still tied → alphabetical order.

Step Expanded g h f Open list after expansion — format: Name[g, h, f]
1Ce 01010 Up[2,3,5], Ri[3,8,11]
2Up 235 Do[5,3,8], Ri[3,8,11]
3Do 538 Ri[3,8,11], Ea[9,2,11]
4Ri (g=3 < Ea g=9) 3811 Ea[9,2,11], Mi[7,5,12]
5Ea 9211 Mi[7,5,12], Sk[11,1,12]
6Sk (h=1 < Mi h=5) 11112 Mi[7,5,12], G[20,0,20]
7Mi 7512 We[10,2,12], G[20,0,20]
8We (f=12 < G f=20) 10212 G[12,0,12]†
9G = Airport 12012 —

† Step 8: We→Airport g=12 < current g=20 → Airport updated from [20,0,20] to [12,0,12].

Optimal path (all Line 1 — Red Express)
Central→ Riverside→ Midtown→ Westgate→ Airport
Total: 3 + 4 + 3 + 2 = 12 minutes

Task 2Greedy Best-First Search trace

StepExpandedhNext choice
1Ce10Up (h=3), Ri (h=8) → choose Up
2Up3Do (h=3) → choose Do
3Do3Ea (h=2) → choose Ea
4Ea2Sk (h=1) → choose Sk
5Sk1G (h=0) → choose G
6G = Airport0—
Greedy path (Blue Line + shuttle)
Central→ Uptown→ Docklands→ Eastfield→ Skyview→ Airport
Total: 2 + 3 + 4 + 2 + 9 = 20 minutes

Tasks 3–7Analysis & Questions

Task 3 — Comparison

A* and Greedy find different routes. A* is faster by 8 minutes (12 min vs 20 min).

Task 4 — Why Greedy fails

At step 1, Greedy sees Ce's neighbors: Riverside (h=8) vs Uptown (h=3). It picks Uptown because h=3 looks very close. But Uptown's only outgoing path is the Blue Line, which ends with a 9-minute shuttle from Skyview. True h*(Uptown) = 18 minutes — far from h=3.

The heuristic is misleading at Central Station: Greedy commits to a branch that looks promising locally but has already "locked in" a slow final leg it cannot escape. It never looks back at accumulated cost.

Task 5 — How A* escapes the same trap

When A* expands Skyview (step 6, g=11), it adds Airport at g=11+9=20, f=20. But Midtown is still in Open with f=12. A* expands Midtown first, then Westgate, which updates Airport to g=12, f=12.

The key: f = g + h. g(Skyview)=11 reflects the 11 minutes already spent on the Blue Line. A* balances past cost against future estimate — it refuses to commit until the full picture (g + h) is cheapest.

Task 6 — Admissibility verification
StationBest path to Airporth*(n)h(n)h ≤ h*?
Uptown Up→Do→Ea→Sk→G = 3+4+2+9 18 3 ✓
Skyview Sk→G = 9 9 1 ✓
Midtown Mi→We→G = 3+2 5 5 ✓ (tight)
Task 7 (Bonus) — Admissible ≠ Tight

Skyview: h=1, h*=9 → underestimates by 8 minutes. This is not an admissibility violation — admissibility only forbids overestimating (h > h*). Underestimating is always allowed.

The Skyview example reveals the distinction:

  • Admissible: h(n) ≤ h*(n) for all n → guarantees A* finds an optimal path.
  • Tight (accurate): h(n) ≈ h*(n) → minimises nodes A* must explore.

A loose heuristic (h=1 vs h*=9) still leads to the correct answer but causes A* to explore the Skyview branch before ruling it out (step 6). A tight h(Sk)≈9 would make f≈20 from the start, and A* would skip Skyview entirely.