Artificial Intelligence: Question 7

Syllabus 18.1

Structured A2 8 marks

A search-and-rescue drone models its flying area as a graph. The nodes S, P, Q, R and T are waypoints, where S is the drone's launch point and T is a stranded hiker's last known location. The edges are direct flight paths between waypoints, weighted with the flight time, in minutes, needed to fly directly between them.

Edge	Flight time (min)
`S` – `P`	2
`S` – `Q`	5
`P` – `Q`	2
`P` – `R`	6
`Q` – `R`	3
`R` – `T`	4

The drone's onboard sensor also estimates, for each waypoint, the remaining flight time to reach T in a straight line. These heuristic estimates, h(n), are:

Node `n`	`S`	`P`	`Q`	`R`	`T`
`h(n)` (min)	8	6	5	3	0

The drone uses the A* algorithm, starting at S, to find its route to T.

(a) State the two values that A* combines to calculate f(n) for a node n, and explain what each one represents in this scenario. [2]

(b) Trace the A* algorithm from S. For each node expanded, state the order of expansion and the values of g(n), h(n) and f(n) used to expand it. [5]

Show worked solution Hide worked solution

Part (a): What f(n) combines

A* calculates, for each node n, the value:

f(n) = g(n) + h(n)

g(n) is the actual flight time already flown along the path found so far from S to reach n.
h(n) is the heuristic estimate of the remaining flight time from n to the goal T (here, the drone’s onboard straight-line estimate).

A* always expands the open node with the smallest f(n), so it balances progress already made against an estimate of what is still left to do.

[2 marks]: [1] for stating f(n) = g(n) + h(n), [1] for correctly explaining what g(n) and h(n) each represent in this scenario.

Part (b): Tracing the A* algorithm

Step 1, expand S (the only open node): g(S) = 0, h(S) = 8, f(S) = 8.

Neighbour P via S–P (2): g(P) = 0 + 2 = 2, f(P) = 2 + 6 = 8.
Neighbour Q via S–Q (5): g(Q) = 0 + 5 = 5, f(Q) = 5 + 5 = 10.

Open list: P (f = 8), Q (f = 10).

Step 2, expand P (smallest f, 8): g(P) = 2, h(P) = 6, f(P) = 8.

Neighbour Q via P–Q (2): g = 2 + 2 = 4, which is less than the current g(Q) = 5, so update: g(Q) = 4, f(Q) = 4 + 5 = 9.
Neighbour R via P–R (6): g(R) = 2 + 6 = 8, f(R) = 8 + 3 = 11.

Open list: Q (f = 9), R (f = 11).

Step 3, expand Q (smallest f, 9): g(Q) = 4, h(Q) = 5, f(Q) = 9.

Neighbour R via Q–R (3): g = 4 + 3 = 7, which is less than the current g(R) = 8, so update: g(R) = 7, f(R) = 7 + 3 = 10.

Open list: R (f = 10).

Step 4, expand R (smallest f, 10): g(R) = 7, h(R) = 3, f(R) = 10.

Neighbour T via R–T (4): g(T) = 7 + 4 = 11, f(T) = 11 + 0 = 11.

Open list: T (f = 11).

Step 5, expand T (smallest f, 11): g(T) = 11, h(T) = 0, f(T) = 11. T is the goal, so the algorithm stops.

Order	Node expanded	g(n)	h(n)	f(n)
1	`S`	0	8	8
2	`P`	2	6	8
3	`Q`	4	5	9
4	`R`	7	3	10
5	`T`	11	0	11

[5 marks]: [1] for expanding S and finding g(P) = 2 and g(Q) = 5; [1] for expanding P next and updating g(Q) to 4 via P; [1] for expanding Q next and updating g(R) to 7 via Q; [1] for expanding R next and correctly finding g(T) = 11; [1] for correctly expanding T last, in this order, to complete the trace.

Part (c): Route and total flight time

Backtracking from T using the node each value was last updated via: T reached via R, R reached via Q, Q reached via P, P reached via S.

So the route is S → P → Q → R → T, with total flight time:

2 + 2 + 3 + 4 = 11 minutes.

[1 mark] for the correct route and total flight time of 11 minutes.

Final answers

(a) f(n) = g(n) + h(n); g(n) = actual flight time so far, h(n) = heuristic estimate of the remaining flight time to T
(b) Expansion order S, P, Q, R, T, with final values g(S)=0, g(P)=2, g(Q)=4, g(R)=7, g(T)=11
(c) Route S – P – Q – R – T, total flight time 11 minutes

Common mistakes

Expanding the open node with the smallest h(n) alone (treating A* as if it only used the heuristic), rather than expanding the node with the smallest combined f(n) = g(n) + h(n).
After finding a shorter route to an already-open node (for example, reaching Q via P with g = 4, cheaper than the earlier g = 5 via S), failing to update that node's g(n) and f(n), and continuing to use the old, larger value.
Believing every edge in the table can only be used in the direction it happens to be written, rather than recognising these are two-way flight paths, so an edge can be used from either waypoint it connects.
Stopping the trace as soon as T first appears in the open list with some f(n) value, instead of continuing until T is actually expanded, since a later update could still lower T's g(n) before then.
In (b), recalculating g(n) as if it restarts from 0 at every step, rather than always adding the new edge's flight time onto the g(n) already reached at the node being expanded from.