Bellman's lost-in-a-forest problem

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.^[1] 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?"^[2] 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]

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.^[2]
• 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.^[2]
• 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.^[2]