22 - Fastest route through the forest

library(caracas)

A problem was posted by the Danish newspaper, Ingeniøren, and it goes like this:

You are in the middle of a dense forest located at A. You need to get to C in the fastest way possible, and you can only change direction once. You can walk directly via AB to the dedicated walking path BC where you can walk fast, you can take the direct path through the forest (AC) where you have to walk slower, or cross through the forest to the dedicated walking path (AD and then DC).

Information given

  • Distances
    • |AB|= 300 m
    • |AC|= 1,000 m
  • Velocities
    • vAB = 2 m/s
    • vAD = 2 m/s
    • vAC = 2 m/s
    • vBC = 5 m/s

Length of line segments

We parameterise with k = |BD|, the distance between B and D. That is, how much to walk on fast walking path before crossing into the forest.

Formulating using caracas:

AB <- as_sym('300')
AB
AC <- as_sym('1000')
AC
BC <- sqrt(AC^2 - AB^2)
BC
k <- symbol('k') # |BD|
DC <- BC - k
AD <- sqrt(AB^2 + k^2)
AD

So for a distance of |AD|, you travel by 5 m/s, and then for a distance of tex(DC) you travel by 2 m/s. Thus it takes tex(AD/2) to travel AD and tex(DC/5) to travel DC.

The question is: What is the fastest way to get from A to C?

First, the total duration of the route is:

l <- AD/2 + DC/5
l
lfun <- as_expr(l)
lfun
ks <- seq(0, as_expr(AC), length.out = 100)
ls <- eval(lfun, list(k = ks))
plot(ks, ls, type = "l", xlab = "k", ylab = "Time A to C")

It looks like a minimum around k = 150.

We find the analytical solution by first finding critical points:

dl <- der(l, k)
dl
crit_points <- solve_sys(dl, k)
crit_points
best_k <- crit_points[[1]]$k
best_k

The type of the critical point is found by considering the Hessian:

eval(as_expr(der(dl, k)), list(k = as_expr(best_k)))

Thus the critical point is indeed a minimum as suggested by the plot.

The fastest route is thus obtained for k = tex(bestk) ≈ round(asexpr(bestk), 2). It has a length of (in meters)

DC_best <- BC - best_k
AD_best <- sqrt(AB^2 + best_k^2)
AD_best
best_route <- AD_best + DC_best
best_route
as_expr(best_route)

tex(bestroute) ≈ round(asexpr(bestroute), 2) and takes (in seconds)

best_l <- subs(l, "k", best_k)
best_l
as_expr(best_l)

tex(bestl) ≈ round(asexpr(bestl), 2)

The best route can be illustrated, too: