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 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]

Approaches

A proven solution is only known for a few shapes or classes of shape, such as a square and a circle. Others, such as an equilateral triangle, remain unknown.^[4] A general solution would be in the form of a geometric algorithm which takes the shape of the forest as input and returns the optimal escape path as the output.

References

This page was last edited on 1 March 2024, at 15:20