Bellman's lost-in-a-forest problem

Unsolved problem in mathematics

What is the optimal path to take when lost in a forest?

More unsolved problems in mathematics

Solutions for several shapes:

1–4.	Straight path of length equal to the shape's diameter w (dotted black), circles of radius w centred on each vertex show that every point on the shape is within w of it
5.	"Broadworm" for an infinitely wide strip

Bellman's lost-in-a-forest problem is an unsolved minimization problem in geometry, originating in 1955 by the American applied mathematician Richard E. Bellman. ^[2] The problem is often stated as follows: "A hiker is lost in a forest whose shape and dimensions are precisely known to him. What is the best path for him to follow to escape from the forest?" ^[1] It is usually assumed that the hiker does not know the starting point or direction he is facing. The best path is taken to be the one that minimizes the worst-case distance to travel before reaching the edge of the forest. Other variations of the problem have been studied.

Although non-contrived real-world applications are not apparent, the problem falls into a class of geometric optimization problems, including search strategies that are of practical importance. A bigger motivation for study has been the connection to Moser's worm problem. It was included in a list of 12 problems described by the mathematician Scott W. Williams as "million buck problems" because he believed that the techniques involved in their resolution will be worth at least a million dollars to mathematics. ^[3]

Known cases

Although it is not known how to find an optimal solution for an arbitrary shape, the optimal solution is known for some special shapes and special classes of shapes:

• If the forest contains a 60° rhombus whose long diagonal is a diameter of the forest, then the optimal escape path length is the diameter, and walking in a straight line for this distance will provide an optimal escape. This case includes, for instance, a circular forest. ^[1]
• The optimal escape path for a semicircular forest, or more generally a forest in the shape of a circular sector with angle at least 60°, is also the diameter of the forest, as is the optimal escape path for a regular polygon with more than three sides. ^[1]
• The optimal escape path for an infinite strip of width ${\displaystyle w}$ is a V-shaped path formed from four straight line segments and two shallow circular arcs, of length approximately ${\displaystyle 2.2783w}$. This same path is also optimal for rectangles of height ${\displaystyle w}$ whose diameter is greater than or equal to the length of this path. For rectangles with a shorter diameter, the optimal escape path length is the diameter. A rectangle whose diameter equals the length of the escape path for a strip of the same height provides an example of a shape with two very different optimal escape paths, the path for the strip and a single line segment of the same length as the diameter. ^[1]

References

1. Finch, S. R.; Wetzel, J. E. (2004). "Lost in a forest" (PDF). American Mathematical Monthly . 11 (8): 645–654. doi:10.2307/4145038. JSTOR   4145038. MR   2091541.
2. Bellman, R. (1956). "Minimization problem". Research problems. Bulletin of the American Mathematical Society . 62 (3): 270. doi: 10.1090/S0002-9904-1956-10021-9 .
3. Williams, S. W. (2000). "Million buck problems" (PDF). National Association of Mathematicians Newsletter. 31 (2): 1–3.