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
    • \(v_{AB} = 2\) m/s
    • \(v_{AD} = 2\) m/s
    • \(v_{AC} = 2\) m/s
    • \(v_{BC} = 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(best_k) \approx round(as_expr(best_k), 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(best_route) \approx round(as_expr(best_route), 2) \] and takes (in seconds)

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

\[ tex(best_l) \approx round(as_expr(best_l), 2) \]

The best route can be illustrated, too: