eyeprolog

GPS route choice

Which route should we take from Gent to Oostende?

A small road map lists four drives, each with a duration, a cost, a reliability, and a comfort score. EyeProlog finds the two routes, totals their scores, and recommends the direct route only because it is better on every count.

Run it in the playground · Source

The question

A traveller in Gent wants to reach Oostende. One route goes straight through Brugge; the other detours through Kortrijk. Which route should the GPS recommend, and can it justify the choice?

The map

map_graph(mapBE, (
  gps_description(mapBE, description(location(S, gent), true, location(S, brugge), drive_gent_brugge, 1500.0, 0.006, 0.96, 0.99)),
  gps_description(mapBE, description(location(S, gent), true, location(S, kortrijk), drive_gent_kortrijk, 1600.0, 0.007, 0.96, 0.99)),
  gps_description(mapBE, description(location(S, kortrijk), true, location(S, brugge), drive_kortrijk_brugge, 1600.0, 0.007, 0.96, 0.99)),
  gps_description(mapBE, description(location(S, brugge), true, location(S, oostende), drive_brugge_oostende, 900.0, 0.004, 0.98, 1.0))
)).

Each drive has a duration in seconds, a cost, a belief (how likely the drive goes as planned), and a comfort score. The map is one term, read with ordinary term traversal rather than asserted as separate facts.

Composing a route

path(From, To, Actions, Duration, Cost, Belief, Comfort) :-
  map_description(From, Mid, Action, D1, C1, B1, F1),
  path(Mid, To, Restactions, D2, C2, B2, F2),
  append([Action], Restactions, Actions),
  (Duration is D1 + D2),
  (Cost is C1 + C2),
  (Belief is B1 * B2),
  (Comfort is F1 * F2).

Durations and costs add up; beliefs and comfort multiply, as probabilities of independent drives going well do.

The recommendation

recommended_route(routeDirect) :-
  route_metrics(routeDirect, Directduration, Directcost, Directbelief, Directcomfort),
  route_metrics(routeViaKortrijk, Viaduration, Viacost, Viabelief, Viacomfort),
  (Directduration < Viaduration),
  (Directcost < Viacost),
  (Directbelief > Viabelief),
  (Directcomfort > Viacomfort).

The direct route is recommended only if it dominates: shorter, cheaper, more reliable, and more comfortable. No weights are needed when one option wins on every criterion.

The answer

eyeprolog examples/gps.pl

outcome(decision, "Take the direct route via Brugge.").
recommendedRoute(decision, routeDirect).
durationSeconds(routeDirect, 2400.0).
durationSeconds(routeViaKortrijk, 4100.0).
cost(routeDirect, 0.01).
cost(routeViaKortrijk, 0.018).
belief(routeDirect, 0.9408).
belief(routeViaKortrijk, 0.903168).

21 facts in all, including the five passed checks c1–c5 and a comparison report stating that the direct route dominates.

The reason

eyeprolog --proof examples/gps.pl

step(route_metrics(routeDirect, 2400.0, 0.01, 0.9408, 0.99),
     rule(13),
     ['Duration' = 2400.0, 'Cost' = 0.01, 'Belief' = 0.9408, 'Comfort' = 0.99],
     [traveller_path(i1, [drive_gent_brugge, drive_brugge_oostende], 2400.0, 0.01, 0.9408, 0.99)]).

The direct route’s 2400 seconds come from a concrete path of two drives, 1500 + 900. The recommendation step cites these metrics and the four comparisons that made it dominate.

The check

condition('C1', resolution, ok, 69).
condition('C5', re_decision, ok, 25).
steps(94).
verified(69).
recomputed(25).
trusted(0).
claims(21).
verdict(checked).

All 94 steps hold: 69 replayed against the program and 25 sums, products and comparisons recomputed by the checker. The recommendation rests on nothing unchecked.

Try it

Make the Kortrijk drives 100 seconds each. The detour becomes faster (1100 s), check c3 disappears, and no route is recommended: neither dominates any more.
Add a third route and a rule that recommends a route when it dominates every other one.
When neither route dominates, what extra information would a principled recommendation need?

Learn more in The Art of EyeProlog, Chapter 14.

This site is open source. Improve this page.