You’re lost in a forest. What’s the best way to get out?
The great macroeconomist Bob Lucas once asked me this question, and I had no answer for him. I still don’t.
The assumption is that you know the size and shape of the forest, but you don’t know where you are or which way you’re facing. And the forest is so dense that you can never see any significant distance in front of you. What path should you follow?
The answer depends on your goal. Are you trying to minimize your escape time in the average scenario (the average being taken over all possible starting positions)? Or are you trying to minimize your escape time in the worst-case scenario? Either way, I don’t know the answer.
The easiest case might be a forest in the shape of a disk, say of radius 1. Then if you walk a straight line in a random direction, the distance to the boundary is 4/3 on average and 2 in the worst possible case. (The worst case, of course, is when you start right on the edge and set off in exactly the wrong direction.)
I expect you might do better to spiral, though. That way, if you start off anywhere near an edge, you’re sure to get out in a hurry. I suspect (but do not know) that with the right spiral, you could beat that 4/3 average, though the worst case might be pretty bad. How tight should the spiral be? I dunno.
If you’re in a long narrow rectangular forest, a spiral seems like an even better bet, and this time it looks pretty good even in the worst case. But maybe something else is better.
It might be reasonably straightforward to set this up as a problem in the calculus of variations, but I haven’t done that. Nor have I Googled around to find out if this is a well-known problem (perhaps with a well-known solution). All thoughts are welcome thoughts.
From a practical point of view, it is hard enough to follow a straight line bearing in a forest, I would think a spiral would be near impossible! I suppose you would set it up with something like 10 pace North, 20 paces East, 30 paces South, 40 paces West etc.
You say that the assumption is that you know the size and shape of the forest. This suggests different answers for different shapes, so perhaps long and thin = spiral, circular = straight line. Is there a solution for any unknown forest?
Lost in a Forest problems are reasonably well-studied (and closely related to Leo Moser’s “worm problem”), but there are a still a lot of open questions there. For a circle, the minimax solution is indeed to walk in a straight line (for any path of length less than two, just put it’s midpoint on the centre of the circle, and the whole thing is contained in the circle by the triangle inequality). As far as I’m aware, the average case problem is still open (but I haven’t looked lately).
This paper from 2004 provides a solution for a “fat” forest and for several specially shaped forests:
http://mathdl.maa.org/images/upload_library/22/Ford/Finch645-654.pdf
This is assuming that one strategy is used throughout the whole escape. If –in the circular forest– you start walking in a random direction, the longer you walk for the more certain you become of where you are in the forest, finishing with when you’ve walked 2R paces, if you’re still in the forest, you can be sure that you’re nearly out and you’ve walked a diameter.
John Faben and Bob Knaus: Thanks for these pointers.
In particular, for a disk-shaped forest, the argument John Faben gives certainly settles the “worst case scenario” problem, so cleanly and simply that I’m embarrassed not to have thought of it.
And the paper Bob Knaus points to is certainly the reference I should have Googled for. (It also contains John Faben’s argument.)
Having been lost in the forest a few times, but completely unaware of a mathematical solution, I can safely suggest that the best route is the one that is:
1) Easiest to follow/remember (e.g. straight lines are better than making turns, etc.)
2) Least likely to result in getting even more lost (e.g. avoid thick vegetation, swamps, obstacles, etc.
3) Most likely to lead to a fellow human being (e.g. aim for highways, powerlines, railroad tracks, etc.)
4) Easiest to retrace your steps if you have to (e.g. don’t rappel down cliffs, don’t slide down ravines, etc.)
I guess you can take these concepts and express them as constraints in an optimization model or transportation problem, and you’d be on your way.
The best way to get out would be to call the forest ranger on your cell phone.
Cunningly I have placed you in a spiral shaped forest.
The strategy for getting out of a theoretical forest (which is
composed soley of flat ground and randomly placed trees) differs
from the strategy for getting out of a real forest.
In a real forest, walking until you come to a stream and then
following it downstream is usually your most reliable way to hit
civilization fastest.
Economists are widely known for their survival skills: “Assume a can opener….” In that vein, perhaps the appropriate strategy is to simply challenge anyone to prove that the forest even exists – given that all these damn trees keep obstructing your view.
Alternatively, there’s David Koch’s strategy: “I don’t need to find a way out. Over the years I’ve given $25 million to my alma mater, so no matter where I go I know that THEY will find ME.”
Serpentine, Shelly!
I’d heard that Moser’s worm problem had been solved with medication.
It worries me vaguely that in this uncertain economy the thoughts of the country’s premier macroeconomist are on “being lost in a forest”.
It seems to me you could determine the best path for any given criteria pretty quickly with monte carlo simulations. Either with a machine learning algorithm, or just testing all the strategies you can think of. Since I could do this in an afternoon, I assume this has been done by others, though I don’t know where.
During the Tuesdays Child question, someone offered the helpful hypothesis/rule of thumb: No probability question that is three sentences long or shorter results in the answer 50%.
Here’s a less whimsical hypothesis/rule of thumb: No set of strategies works if the degenerative case of the strategy does not work.
Landsburg suggests that a spiral might provide an optimal strategy for escaping a forest. But that strategy immediately poses the question, “How tight a spiral?” The only relevant answer to the question would seem to require some reference to the size of the forest – a variable omitted from the question.
So what are the degenerative answers to the “How tight” question? The tightest spiral would involve pivoting on a point: clearly not a winning strategy. And the loosest spiral would be … a straight line. This causes me to suspect that a straight line is the optimal strategy.
nobody.really: The straight clearly isn’t the best possible solution for a long and skinny forest, as a it might make you walk all the way down the long part. Indeed, the paper that Bob Knaus linked to says that the that shortest path for a long, skinny strip is (and I think it’s completely crazy that this is right) “the symmetric path formed by four line segments and two circular arcs” shaped kind of like a “V”.
“Mother worm’s blanket” has been one of my day-dream problems for something like 15 years now. I remember reading it in the “Mathematical Recreations” section of Scientific American when I was in high school.
Do your best to go up. Once at a highpoint you’ll get a better survey of the forest.
Hopefully, you’ll find the best direction to go to escape nature’s maze.
Yeah, I would think that the strategy should change given the shape of the forest. If it’s a rectangular forest (with dimensions a x b, a<b), I think the worst case scenario is traveling 'b' (Walk 'a' paces, if you're not out, then you have at most 'b-a' to go). In a circular pattern, a straight line is what I would choose. I think spiraling would only really help if you were truly unlucky. If I were stuck in the woods, I would assume the average scenario.
With regards to Ryan's practical answer, I mostly agree with you. I've had some training with regards to getting lost in the woods (I was a Boy Scout). I remember being told, though, that telephone lines are actually *not* good markers to follow. Phone lines can go for miles without hitting civilization (they're built to go between big cities, but they're out of the way of everything) so you could be walking for a very long time. Rivers are a safe bet if you're out in the middle of nowhere, because humans inevitably set up communities near water. I realize that this answer strays from the original intent of the post but… who cares.
No matter where you are lost, there are two rules (seems like I learned them at grammar-school age.
1. If it is certain (because you told somebody where you were going and what time you expected to be back) that somebody will come looking for you, sit down someplace safe and visible.
2. If you are sure you are going to have to save yourself, walk down hill–always down hill. (Keeps your from walking in a left-turn circle, and every watercourse eventually gets to a stream or river which WILL have a settlement on it.)
harold– Oddly it’s very easy to keep a straith line while in a forrest. Flag a tree (or break a low twig) every 100 paces (less if visibility is an issue) then regularly look back to be sure your flags all line up.
As for the question– I doubt it is optimal but for a long skinny forrest, if you know the size and shape, then walk a straight line a bit more than the width of the forrest and if you are not out turn 90 degrees and do it again.
Benkyou Burrito: Yes, good point for a flat forrest. I was imagining terrain features might get in the way. Similarly, in hilly areas following a stream down is not a good strategy for safety as you tend to find yourself trapped in a gully at the top of a waterfall.
Back to the mathematical forrest, it would be nice if the optimum spiral were one based on Fibonacci series, like a snail shell. This crops up often in nature, and intuitively seems to offer a good solution. It could end up with you going in effectively a straight line too early though.
“The easiest case might be a forest in the shape of a disk, say of radius 1. Then if you walk a straight line in a random direction, the distance to the boundary is 4/3 on average”
Ok, I give up.. is there an easier way of seeing this than setting up the double integral over the angle you walk in and your distance to the centre (weighted by the pdf of the distance to the centre)?
A random point is distance 2/3 from the centre, which seems as though it might somehow be relevant, but I can’t quite see how…
John Faben: Given the symmetry, you don’t have to integrate over angles. You can assume you’re facing (say) east and then integrate over all starting points in the disk.
I had been thinking along similar lines as Harold. However, straight line walking beats a fibonacci walk.
Formalizing the fibonacci path as straight lines (there’s a better solution that’s curved) where the path goes 1 step, turns 90 degrees left, goes 1 step, turns 90 degrees left, goes 2 steps, turns .., goes 3 steps, etc ie F_i steps then make a 90 degree turn left, then F_{i+1} steps, etc.
After walking F_{n-2} steps along the F_n side, the total distance traveled is F_{n+1} + F_{n-2} – 1 (convex shape defined is a rectangle) and the convex area enclosed by the path is F_{n-1} * F_{n-2}.
The distance walked is also 2 * (F_{n-1} + F_{n-2}) – 1 or one step less than once around the perimeter.
While in the worst case of a convex forest, fibonacci travelling distance is equal to the perimeter, but no more, walking in a straight line still wins as it’s worst case is the maximal internal distance which is somewhere between 2 and nearly pi times more efficient (worst case vs worst case) depending on the forest’s shape.
“The easiest case might be a forest in the shape of a disk, say of radius 1. Then if you walk a straight line in a random direction, the distance to the boundary is 4/3 on average”
I believe that the average distance in this case is 8/(3 * pi). We can take the random direction as +X by symmetry, integrate over the circle area and divide over the area:
http://tinyurl.com/circular-forest
I also made a simulation that matches this result (or makes the same error :-)
http://codepad.org/wZZIQ6Fi
Mariano M. Chouza:
Right you are. I somehow made the mistake of dividing by 2 instead of by pi.
If you are in a long skinny forest the odds aren’t very good that if you walked in a random direction you would walk directly through the whole forest, and not on a diagonal toward an exit, that would def be the worst case scenario.
I really like the nobody.really solution of determining a strategy. Though ironically the first move one would/should do would be to pivot in a circle to make sure you aren’t in sight view of an exit!