Bellman's lost in a forest problem

From HandWiki
Short description: What is the best path for a lost hiker to follow to escape from a forest of known shape?
Question, Web Fundamentals.svg Unsolved problem in mathematics:
What is the optimal path to take when lost in a forest?
(more unsolved problems in mathematics)

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.[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.

The lost-in-a-forest problem has been studied from a blind man's perspective[clarification needed] by Surajit Dutta, where he explored the problem based on the condition that the endpoint of the escape path always lies outside the forest.[5]

There have been several specific answers found for specific instances, but no general solution has yet been established. For a partial solution that uses an algorithmic approach based on close curve magnetization as an example.[clarification needed][6]

References

  1. Bellman, R. (1956). "Minimization problem". Bulletin of the American Mathematical Society 62 (3): 270. doi:10.1090/S0002-9904-1956-10021-9. 
  2. Finch, S. R.; Wetzel, J. E. (2004). "Lost in a forest". American Mathematical Monthly 11 (8): 645–654. doi:10.2307/4145038. https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Finch645-654.pdf. 
  3. Williams, S. W. (2000). "Million buck problems". National Association of Mathematicians Newsletter 31 (2): 1–3. http://www.math.buffalo.edu/~sww/0papers/million.buck.problems.mi.pdf. 
  4. Ward, John W. (2008). "Exploring the Bellman Forest Problem". http://wardsattic.com/joomla/Download/BellmanForestProblem.pdf. 
  5. Dutta, Surajit (2022). "When a blind man is lost in a forest". Journal of Research in Applied Mathematics 8 (1): 10–14. http://www.questjournals.org/jram/papers/v8-i1/C08011014.pdf. 
  6. Agama, T. (2021-05-10). [clarification needed].com/files/1636528854_(4)_IJPAMR06012021MTN003_(p_48-54).pdf "Simple Close Curve Magnetization and Application to Bellman's Lost in the Forest Problem". International Journal of Pure and Applied Mathematics Research 1 (1): 48. doi:10.51483/IJPAMR.1.1.2021.48-54. ISSN 2789-9160. https://www.svedbergopen[clarification needed].com/files/1636528854_(4)_IJPAMR06012021MTN003_(p_48-54).pdf.